Символьное дифференцирование

[avelon]

Имеется обратная польская запись некоторой функции, как вычислить аналитическую производную?

[Kitayets]

в чём сложность? или это опять контрольное задание для не очень ответственного студента?

вы сами без программы призводную от функции аналитически брать умеете?

или вас смущает обратная польская запись?

или вы ищете готовое решение?

[avelon]

аналитически на бумажке без проблем решу.
это не контрольное задание. я сам химик и приходиться писать проги под свои задачи. есть конечно математические пакеты где легко берется производная, но это не удобно+большой объем экспериментальных данных, что приводит к очень муторной работе, хотелось бы автоматизировать этот труд.
обратная польская нотация не смущает, но не понятно как по ней брать производную
готовое решение это крайний случай, лучше самому писать, чтобы раз разобраться и на всегда
можно и без обратной польской нотации предложить алгоритм если кто знает

[Mr.Smart]

Вычисление производится на стеке. Алгоритм не заурядный и довольно простой. Алгоритм можно посмотреть тут [url]http://ru.wikipedia.org/wiki/Обратная_польская_запись#.D0.92.D1.8B.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F_.D0.BD.D0.B0_.D1.81.D1.82.D0.B5.D0.BA.D0.B5[/url].
Ссылка плохо вставляется.

[avelon]

по ссылке со способом вычисления выражения то все понятно, но не доходит как это употребить к правилам дифференцирования

[hinst]

Mr.Smart, почему в википедии алгоритм на Delphi в хрен-знает-сколько раз длиннее, чем на C++? что за бардак...

[Mr.Smart]

hinst не знаю. Википедию не правлю Да не очень-то мне данный ресурс симпатизирует...

Добавлено спустя 19 минут 35 секунд:
avelon, а вы начните с простого +-*/() - далее вам помогут, если будут проблемы.

п.с. Я удивляюсь людям, которые сами не пробовав чего либо просят помочь.

[Kitayets]

google великая сила!
4-ая ссылка по запросу "дифференцирование":
http://ice_diff.chat.ru/gl2/gl2.htm

Добавлено спустя 57 минут 28 секунд:

Mr.Smart, почему в википедии алгоритм на Delphi в хрен-знает-сколько раз длиннее, чем на C++? что за бардак...

там с примерами всё туго.
Про хаскель судить сложно, но вроде там вычисление выражения записанного в ОПН. Т.е. на входе "2 3 +" - на выходе 5.
Примеры же на с++ и делфи - перевод выражения из обычной нотации в ОПН, т.е. на входе "2 + 3 + х" - на выходе "2 3 х +". Пример на делфи длиннее потому, что обрабатывает ещё и скобки. Т.е. пример на делфи "круче", чем на с++.

При этом - не думаю, что алгоритм дифференцирования зависит от нотации. Мне кажется тут 2 этапа (для функции одной переменной):
1. привезти функцию к полиномиальному виду
2. пройтись по каждому члену полинома и применить к нему правила дифференцирования (из школьной таблички).

[avelon89]

написал программу переводящую все в ОПН.
задаем функцию в программе например x^3+2*x+x-2
на выходе строка x 3.0 ^2.0 x *+x +2.0 -
вроде как правильно получается))
как дальше дефференцировать пошагово кто нибудь может рассказать?

[Kitayets]

написал программу переводящую все в ОПН.
задаем функцию в программе например x^3+2*x+x-2
на выходе строка x 3.0 ^2.0 x *+x +2.0 -
вроде как правильно получается))
как дальше дефференцировать пошагово кто нибудь может рассказать?

avelon89 - почему вы так прицепились к ОПН?

ОПН - это вообще средство для промежуточного представления выражений, которое имеет бонус при вычислении выражения. Вам то как раз и не нужно вычислять его! Вам нужно такое представление, которое позволит Вам дифференцировать его.

[avelon]

насколько я знаю. можно дифференцировать через деревья и через ОПН. выбрал ОПН.
нашел вот такую статью. кто нибудь может помочь разобраться с алгоритмом, а то я прочитал но не со всем понял как его реализовать(

Добавлено спустя 2 минуты 36 секунд:
да и ОПН тоже имеет тоже самое представление что и дерево выражения. так что без разницы что выбирать. но у меня уже реализован ОПН, зачем мне заново писать код для дерева

[avelon]

у кого нибудь есть идеи?

[Kitayets]

2 avelon

там в abstract же написано - простой алгоритм для численного решения производной функции БЕЗ генерации компьютерного представления дифференцированного выражения. Т.е. автор статьи как раз разработал алгоритм вычисления производной функции без стадии аналитического символьного дифференцирования.

т.е. статья Вам не подходит.

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

Добавлено спустя 11 минут 42 секунды:
кстати в статье в первом параграфе написано, что "обычно", в те времена (начало 80'х), вычислительные пакеты сначала аналитически находили производную функцию переводя исходную функцию в удобное "алгебраическое" (инфиксную нотацию) представление и вычисляли производную по частям.

т.е. точно так, как я Вам советовал выше http://freepascal.ru/forum/viewtopic.php?f=13&t=6762&p=51501#p50758

Добавлено спустя 2 часа 28 секунд:
и всётаки советую ещё раз почитать: http://ice_diff.chat.ru/ написано муторно но верно, там же есть список литературы - http://ice_diff.chat.ru/lit.htm.

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

Рассматривается алгоритм создания такого представления из ОПН и алгоритм дифф. по кодовым спискам., на выходе получается кодовый список - который можно вывести обратно в ОПН.

Читать довольно сложно, потому что во первых рассматривается общий случай - дифференцирование произвольной степени по произвольному количеству переменных. Во вторых описывается программа которая на входе получает программу на одном из языков программирования (с расширениями) с функциями, и работая квк препроцессор анализируя подставляет в неё уже дифф. функции.

[daesher]

"Прикрутил" обратную польскую нотацию (перевод в неё) к моему vvfstat.sf.net, правда, совершенно для других целей

[Kitayets]

Кстати в FCL есть модуль symbolic - в котором есть кое-чего интересного, включая ОПН.

вот из доки:

Код: Выделить всё

Key features:
--------------
...
- Expression parsing and conversion:
      - Infix to RPN
      - infix to Parsetree
      - Parsetree to infix
      - Parsetree to RPN

- Symbolic Expression handling.
   - Simple operators on expressions + / * - ^
   - Derivation of simple functions (all operators + most functions in math
     unit)
   - taylor polynomal.
   - Precalculate Newton. (almost non-feature :-)
   - Primitives for rearranging
                - Identifying of terms.
                - Simple simplying (2*2*x -> 4*x)
                - (de)factoring (*)
                - Rearrange so that when converted to RPN, maximal stack depth
                  for evaluation is 4. This also needs a detector routine
                  (determine required RPN stack room)
   - Operator overloading possible?

- High speed evaluating. (parse once, evaluate often principle)
   - Infinite variables
   - Infinite (symbolic) constants.
   - Fast (hopefully)
   - Structure designed so that a lowlevel (processor dependant) version of
      the core evaluating routine is possible.