|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Tsyplakov 2:5020/400 12 Jun 2001 13:57:04
To : All
Subject : Re: Аналитическое диффиринцирование
--------------------------------------------------------------------------------
Dmitry Kalinin пишет в сообщении...
> Может кто подсказать идею алгоритма поиска
> первой производной любой функции (от одной переменной).
> Hапример: (x^5)` = 5x^4, и т.д.
> Все это, разумеется, должно работать на
> компьютере, человек вводит только функцию.
Я уже отвечал на этот вопрос в этой эхе. Поэтому просто себя
процитирую:
Алгоритм я нашел в статье
"Эффективный алгоритм вычисления производных в экстремальных
задачах" // Экономика и матем. методы 1984 том XX вып. 2
Однако статья не по делу перемудреная, поэтому опишу по
своему.
Пусть имеется функция n переменных:
f(x[1],...,x[n])
Передполагается, что ее вычисление можно разложить на m
элементарных операций, задаваемых функциями
f[l], l = 1,...m,
производные которых известны.
Введем дополнительные иксы, соответствующие результатам
элементарных операций: x[n+l] есть результат l-й
элементарной операции. l-я операция производится над
переменными-аргументами (иксами), задаваемыми упорядоченным
множеством индексов K[l]. Результат одной операции может
быть аргументом другой операции. Желательно упорядочить
операции так, чтобы они шли по порядку использования, т.е.
элементы K[l] принадлежат множеству {1,..,n,n+1,n+l-1}.
Получаем следующую рекуррентную формулу для вычисления
исходной функции:
x[n+l] = f[l](x[K[l]]),
где через x[K[l]] для краткости обозначен список иксов,
являющихся аргументами l-й операции.
В результате последней m-й операции получаем значение
исходной функции:
f(x[1],...,x[n]) = x[n+m] = f[m](x[K[m]]).
Все, что говорилось выше по сути дела представляет собой
представление исходной формулы в виде дерева (почти дерева),
узлы которого растянуты в список. Hечто вроде стека
(обратной польской записи). Это для того, чтобы удобнее было
формулы писать. Hа практике нам нужно именно дерево, а не
стек.
Теперь собственно о том, как это формульное дерево
дифференцировать. Идея проста. В мат. анализе это называется
производная сложной функции.
Hам требуется найти градиент:
g = (g[1],...,g[n]) = (de_f/de_x[1], de_f/de_x[1]),
где de_f/de_x[i] - частные производные.
В иксах можно записать:
g[i] = dx[n+m]/dx[i], i=1,...,n.
Можем ту же формулу распространить на все иксы:
g[i] = dx[n+m]/dx[i], i=1,...,n,n+1,...,n+m.
Эти производные вычисляются рекуррентно (i=1,...,n+m-1):
g[i] = Sum{l из L[i]} g[n+l] *
de_f[l](x[K[l]])/de_x[i].
Здесь L[i] для каждого икса x[i] (i=1,...,n+m-1) обозначает
множество тех элементарных операций, аргументами которых он
является. Частные производные de_f[l]/de_x[i] берутся из
таблицы производных.
Рекуррентная формула стартует с g[n+m] = 1 и дальше идет от
i=n+m-1 по порядку до i=1.
Все.
Теперь о конкретике. Пусть даны конкретные числа
x[1],...,x[n]. Как найти значения g[1],...,g[n]?
1) Парсером разбираем формулу и строим по ней формульное
дерево.
2) Вычисляем по порядку все остальные иксы
x[n+1],...,x[n+m].
3) По рекуррентной формуле вычисляем все g[i].
Как можно получить производную в виде формулы?
1) Парсером разбираем формулу и строим по ней формульное
дерево.
2) По рекурренной формуле дополняем формульное дерево
узлами, связанными с g[i]. Дополнительные узлы будут
включать как производные элементарных функций, так и
операцию суммирования.
3) Обратным парсером разворачиваем формульное дерево в
формульное выражение.
Я подозреваю, что полученные формулы будут выглядеть ужасно,
поскольку тут не делается никаких упрощений (типа команды
Simplify в программе Matematica).
Александр Цыплаков
-----------------------------
Alexander Tsyplakov
Novosibirsk State University
http://www.nsu.ru/ef/tsy/
--- ifmail v.2.15dev5
* Origin: Novosibirsk State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
