- RU.ALGORITHMS (2:5030/1334.67) ------------------------------ RU.ALGORITHMS -
 Msg  : 1 из 858
 From : Alexander Tsyplakov                 2:5020/400      Чтв 02 Hоя 00 11:17
 To   : All                                                 Суб 04 Hоя 00 01:09
 Subj : Re: Первообразная
-------------------------------------------------------------------------------
From: "Alexander Tsyplakov" <tsy@land4.nsu.ru>

В связи с тем, что автор исходного вопроса о первообразной в
личной переписке проявил интерес, попытаюсь описать алгоритм
аналитического дифференцирования. От моего исходника толку
мало, там врядли можно что-то понять. Hо идею могу описать.

Алгоритм я нашел в статье
"Эффективный алгоритм вычисления производных в экстремальных
задачах" // Экономика и матем. методы 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)