Нахождение производной

Подскажите пожалуйста алгоритм нахождения производной...

  Переведи свое выражение в польско-инверсную или польско-префиксную запись. А потом в лоб переведи ее в производную.
  А вообще я эту тему переношу в раздел "Алгоритмы". Так как спп я в ней не вижу.

2leprecon

ну ты блин даёшь. человек спрашивает, как найти производную, а ты ему что????
один из шагов одного из многих способов решения одного из вариантов постановки задачи. для него (да и для меня в какой-то степени) это звучит как магическое заклинание или как издевательство. наверняка он и с с++ом-то не знаком! ну при чём сдесь польша???????????

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

начнём с первой. делаешь так: находишь значение функции в твоей точке, назовём её х, находишь его же в точке, удалённой от х на малое_по_твоему_мнению_расстояние dx, напр 0,001 - точка будет называться x+dx. разность значений функций, поделённое на dx, и будет производной. для вящей пущности следует также найти производную, используя точку x-dx, а потом посчитать среднее арифметическое. ежели тебе дана величина максимально допустимой ошибки, то надо уменьшить dx например в 10 раз и снова посчитать производную, а затем сравнить с предыдущим её значением. если разница превышает твою ошибку, надо снова уменьшить dx, в противном случае удовлетвориться полученным значением.

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

программы писать лень, к тому же я не очень дружу с с++ом.

Цитата wormball, 13.03.03, 18:51:55

2leprecon ну ты блин даёшь. ...........
наверняка он и с с++ом-то не знаком! ну при чём сдесь польша?

При чем сдесь C++ ???
Если бы ты знал что такое польско-инверсная или префиксная запись, то не стал бы спрашивать при чем здесь она.

Цитата wormball, 13.03.03, 18:51:55

найти аналитический вид производной функции, заданной в аналитическом же виде (т е в виде строки).

Так вот, польская запись, получается из аналитического вида функции (т.е. в виде строки). И представляет собой наиболее удобный вид для алгоритмической работы с функцией.
аналитический вид: a+b*c/d+e  
польско-инверсный: abc*d/+e+
польско-префиксный: ++a/*bcde

Цитата wormball, 13.03.03, 18:51:55

будет у тебя рекурсивная функция, которая будет последовательно применять к строке правила нахождения производной.

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

Дифференцируем по b
Если найти производную в лоб, то получится вот что: 0+((1*c+b*0)*d-(b*c)*0)/d^2+0 => Это тоже самое что c/d

Если пройтись рекурсией по польско префиксной записи, то как раз получится
0+((1*c+b*0)*d-(b*c)*0)/d^2+0. Останется только упростить выражение и все - аналитический вид производной в польско-префиксной нотации получен!

Если делать тоже самое с польско-инверсной записью, то вместо рекурсии будет цикл и стек.

Т.е. для нахождения аналитического вида производной алгоритм такой:
1. Дано выражение : a+b*c/d+e  
2. Переводим в польскую запись, например префиксная: ++a/*bcde
3. Рекурсивным алгоритмом считаем производную.
   Получается ++0/-*+*1с*b0d*bc*dd0
   Или в нормальной записи 0+((1*c+b*0)*d-(b*c)*0)/d^2+0
4. Упрощаем выражение. Убираем все умножения на нули и сложения с нулями.
   Получается /cd
5. Переводим обратно в нормальный вид c/d

Сообщение отредактировано: Leprecon - 13.03.03, 19:15

Попробую объяснить польскую запись:
Префиксная это когда впереди стоит операция а за ней стоят два параметра.

Цитата

т.е. a+b это +ab

Цитата

a+b+с это ++abc
Первый плюс: 1 операнд +ab.
                   2 операнд c
Второй плюс 1 операнд a
                 2 операнд b

Инверсная запись наоборот:
a+b  = ab+
a+b+c = ab+c+ или abc++
Например двигаемся по инверсной записи ab+c+ с самого начала:
1. Толкаем в стек a
2. Толкаем в стек b
3. Оператор + => берем из стека два верних значения, складываем и толкаем в стек результат.
4. Толкаем в стек с
5. Оператор + => берем из стека c и значение a+b, складываем и заносим в стек.
6. В конце верхний элемент стек это результат выражения.

В префиксной записи сложнее, там не цикл со стеком, а рекурсия.
++abc
         +
  +           c
a    b

Цитата wormball, 13.03.03, 18:51:55

2leprecon:
ну ты блин даёшь. человек спрашивает, как найти производную, а ты ему что????
...наверняка он и с с++ом-то не знаком! ну при чём сдесь польша???????????

Раз с С/С++ не знаком, знач заставляем юзера взять калькулятор и считать самому производную, потому что сами, как ты сказал, С/С++ не знаем и ессно "польско-инверсную" и " польско-префиксную" запись не можем воплотить в код...

Так что будь любезен не упрекать человека (тем более модера... почему? читай >> этот ФАК <<) в том, чего сам не знаешь...

ЗЫ
Ты сначала спроси, что это за записи, а потом строй из себя кого-то!

Сообщение отредактировано: SUnteXx - 14.03.03, 00:19

Нет, вы тут что демагогию решили развести. Устроили тут ромашка прав-неправ, польская - не польская, знает - не знает....

2True_Hart:
Будьте любезны задавайте вопросы более конкретно...
Какой алгоритм и для какого случаю конкретно... в численном или явном виде надо найти производную... Для численного поиска, кажется проблем вообще нет...

Всем большое спасибо.....
Производнуй n-ой степени надо найти в числовом виде , следующей функции, (sin x)^n
Еще раз большое спасибо....

2True_Hart

ну вот, я как всегда оказался прав 8).

как я понимаю, спасибо мне 8).

зы. я где-то слышал версию, что форма называется не польской, а венгерской 8)

Венгерская - ЭтоТакойСпособДаватьИменаПеременным.
(сорри за оффтоп)

Сообщение отредактировано: volatile - 17.03.03, 13:58

Проблемы с численным решением все же есть.
df(x) = (f(x+h)-f (x)) / h
если уменьшать шаг разность f(x+h)-f (x) будет становиться все меньше и
в конце концов получим что угодно, но не производную.

Цитата Trurl, 24.03.03, 14:54:46

Проблемы с численным решением все же есть.
df(x) = (f(x+h)-f (x)) / h
если уменьшать шаг разность f(x+h)-f (x) будет становиться все меньше и
в конце концов получим что угодно, но не производную.

Не понял ???
Единственный косяк может иногда получиться только в окрестностях точек, разрыва....

>Проблемы с численным решением все же есть.  
> df(x) = (f(x+h)-f (x)) / h
>если уменьшать шаг разность f(x+h)-f (x) будет становиться все меньше и  
>в конце концов получим что угодно, но не производную.
2GrAnd:
Я думаю, что Trurl здесь имел ввиду следующее:
 Чем меньше число, тем менее оно точно. Все таки число занимает ограниченное количество памяти.
 Но я думаю что это не существенно. Все таки 64 бита не так уж мало. Если только мы не возьем dx=0,00000000000...0000001!

f(x) всегда вычисляется с некоторой погрешностью.
При вычитании близких чисел относительная погрешность увеличивается,
а при делении на h увеличивается абсолютная погрешность.
Т.е. с уменьшением шага погрешность будет сначала уменьшаться, а затем увеличиваться.
Например ищем производную ln(sin(x))  в т. x=0.1
Начинаем с h= 0.001 - получаем 1 значащую цифру.
Затем последовательно уменьшаем h в 10 раз.
Количество значащих цифр: 2,3,4,5,6,7,6,5,4,3,2,2,1.

Вычисление производной через разностное отношение - не корректно.
Самый распространенный способ - это разбить функцию на отрезке [a,b] сеткой:
a = x₀ < x₁ < .... < x_n < x_n+1 = b
т.е. вычислить ее значения в этой сетке, соответственно f₀, f₁, ... f_n, f_n+1.
По этим значениям построить многочлен n+1 степени. К примеру Лангранжа:
L_n(x) = C₀f(x₀) + C₁f(x₁) + ... C_nf(x_n)
где C_k = w(x)/((x-x_k)w'(x_k))
где w(x) = (x-x₀)(x-x₁)....(x-x_n)
а w'(x_k) = (x-x₀)(x-x₁)...(x-x_k-1)(x-x_k+1)...(x-x_n)
Раскрыть скобки, найти коэффициенты a₀, a₁, ... , a_n+1. По ним найти n-ую производную этого многочлена, все, примерное значение производной готово.

Сообщение отредактировано: Leprecon - 28.03.03, 16:36