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

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

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

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

Leprecon Спасибо за самый реальный подход из предложенных
Только фвозникает вопрос как w'(x) будет Bыглядеть  для (Sin(x))^m

Trurl Полностью согласен тем более что мне необходимо опериро?ть и бес того  мaлыми Bеличинaми

ну ежели тебе надо вычислять производную только от (sin(x))^m, то тогда можно сделать ещё проще и в то же время точнее - продифференцировать её и подставлять значения в найденную производную.

  ((sin(x))^m)'=m*(sin(x))^(m-1)*cos(x)

А ты попробуй найти производную n-й степени от sinⁿ(x) ?

Цитата wormball, 15.03.03, 19:13:59

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

Я ведь так понял, что ты самый ...  8)

Цитата True_Hart, 29.03.03, 11:21:08

Leprecon Спасибо за самый реальный подход из предложенных
Только фвозникает вопрос как w'(x) будет Bыглядеть  для (Sin(x))^m

w'(x) - это не производная от w(x), это выражение, которое находится по формуле которую,я привел. Более того, если ты подставишь туда x_k - то это будет просто константа. Не забудь пропустить (x-x_k), как там написанно
x₀, x₁, ... - это узлы сетки, на которую ты разобьешь отрезок [a,b], на котором тебе надо найти производную.

Сообщение отредактировано: Leprecon - 29.03.03, 17:52

#14 Мысль правильная, но многочлен Лагранжа имеет слишком мало общего с самой функцией. Лучше использовать аппроксимацию на основе разложения в ряд. Проще всего посмотреть в каком-нибудь справочнике - там все коэффициенты уже посчитаны.
Точнее всего сделать аналитически, но как я понимаю, задача по численным методам .

Цитата

Лучше использовать аппроксимацию на основе разложения в ряд.

Пожалуй это действительно удобнее. Может для такой функции имеет смысл построить ряд Фурье?

Цитата

Точнее всего сделать аналитически, но как я понимаю, задача по численным методам

Ряд и его производную наверно можно аналитически. А оставшиеся вычисления численно

Численно ряд построить не так уж сложно. Но для ряда Тейлора, придется все равно вычислять n-ую производную, хоть и в одной точке. Численно лучше всего вычислять ряд Фурье, там производных не нужно.

Сообщение отредактировано: Leprecon - 31.03.03, 10:53

На досуге почитай Кнута первый том (глава 2 - Структуры данных). Там как пример работы с деревом показано вычисление производной ЛЮБОЙ функции. Код для машины MIX конечно, разобрать можно, но и теоретические идеи очень хороши  8D

tserega
Обязательно почитаю...

Цитата Leprecon, 31.03.03, 14:48:24

Численно лучше всего вычислять ряд Фурье, там производных не нужно.

Извини за глупый вопрос "Что такое ряд Фурье?"

касаемо фурье см тут: http://pascal.sources.ru/cgi-bin/forum/YaBB.cgi?board=algorithm;action=display;num=1016036282

http://pascal.sources.ru/cgi-bin/forum/YaBB.cgi?board=algorithm;action=display;num=1037119227
но я думаю оно тут не поможет. ежели функцию раскладывать в ряд на каком-то промежутке, то получится не обязательно производная твоей функции, всё зависит от точности разложения. вплоть до того, что получится число, отличающееся на порядок.

тебе всё-таки надо найти аналитический вид производной - или маткадом, или самому помучаться (если умеешь....). если повезёт, она будет не такой уж и громоздкой 8D.

тут на меня снизошёл приступ альтруизма и я решил взять ея прямо тут.

((sin(x))^m)' = m*(sin(x))^(m-1)*cos(x)
((sin(x))^m)'' = m*(m-1)*(sin(x))^(m-2)*(cos(x))^2 - m*(sin(x))^m
((sin(x))^m)''' = m*(m-1)*(m-2)*(sin(x))^(m-3)*(cos(x))^3 - 2*m*(m-1)*(sin(x))^(m-1)*cos(x) - m*m*(sin(x))^(m-1)*cos(x) = m*(m-1)*(m-2)*(sin(x))^(m-3)*(cos(x))^3 - m*(3*m-2)*(sin(x))^(m-1)*cos(x)

....

дааааа..... не повезлоооо.......

тогда остаётся только численный метод

Сообщение отредактировано: wormball - 01.04.03, 10:09

Цитата True_Hart, 01.04.03, 00:54:22

Извини за глупый вопрос "Что такое ряд Фурье?"

Рассматривается функция в интервале (-L, L)
Ряд Фурье, это ряд вида:
f(x) = a₀/2 + Сумма(a_ncos(Пnx/L) + b_nsin(Пnx/L))
Cумма по n от 1 до бесконечности.
П - это константа Пи.

Где
a_n = 1/L Инт(f(x)cos(Пnx/L))dx   - Интеграл от -L до L, n = 0,1,2,3,...
b_n = 1/L Инт(f(x)sin(Пnx/L))dx   - Интеграл от -L до L, n = 1,2,3,...

Определенный интеграл вычислить несложно, можно применить простые методы: прямоугольников, трапеций или парабол. Скажи если нужно их описать.

Конечно до бесконечности ряд делать не стоит - скорее всего тебе нужно вручную, пробами, посмотреть до каких n нужно суммировать, чтобы получить нужную точность. А уж вычислить n-ую производную от этого ряда проще простого.

Сообщение отредактировано: Leprecon - 02.04.03, 17:42

2Leprecon

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

2True_Hart

для чего хоть ето тебе надо? может стоящую перед тобой задачу можно решить более гуманными способами?

Сообщение отредактировано: wormball - 04.04.03, 13:12

Цитата wormball, 04.04.03, 17:06:13

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

Я хотя бы решение предлагаю, вместо того, чтобы скептически обсуждать чужие ответы.  Почитай любой учебник по численным методам, там тебе сначало скажут, что численное нахождение производной через разностное выражение (Это то, что ты вначале предложил) не корректно, а потом предложат аппроксимировать функцию f(x), многочленом (Это то, что ты сейчас критикуешь). Я предлагаю, заменить функцию, рядом Фурье, так как для его построения не нужно находить производную, и не нужно раскрывать много скобок, как в интерполяционных многочленах. Точность производной будет зависить только от кол-ва слагаемых в ряде, так что можно вычислить ее с какой угодно точностью, повторю: все зависит от длинны ряда.

Цитата wormball, 04.04.03, 17:06:13

для чего хоть ето тебе надо?

Это все нужно только для того что бы вычеслить
центральную аномалию планеты используя формулу Кеплера с применением ряда Лагранжа
Нечто вроде
E = M + a*sin M + (a^2)/2! * d/dM (sin M)^2 + .... + (a^n)/n! * d/dM^n-1 (sin M)^n
Где M - средняя аномалия, a - эксентриситет планетной орбиты

Ну, тогда о численном методе и не думай! Только аналитически.

Численно это решать, конечно ужасно Несколько вложенных численных методов :
Но аналитически, не представляю, как тут можно что-либо сделать с этими дифферециалами. Раз есть такой ряд, может для него уже придуманы прикладные методы?