|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 06 Dec 2001 20:06:13
To : Andrey Romanov
Subject : Re: определение корней полинома
--------------------------------------------------------------------------------
AR> Hужна информация о сабже. Желательно разными методами. Исходники
AR> приветствуются.
Тебе что надо? Узнать что такое корень многочлена? Или как его искать?
Я надеюсь что второе. При этом тебя интересуют численные методы.
Так по моему самый простой алгоритм для программирования выглядит примерно так:
P(x)=a0x^n+a1x^(n-1)+...+an
1. Факт доказываемый в курсе высшей алгебре. Корни многочлена находятся на
отрезке
[-N,N], где N=(max(a1,a2,a3,a4,a5,a6,...,an)/a0)+1, оценка грубая, но на
сложность
не сильно влияет.
2. Далее. Корни многочелена находятся между корнями производной(но не обратно),
при
этом кратные корни совпадают с корнями производной.
3. Таким образом если мы занем корни производной наш отрезок [-N,N] разбивается
на
кучу отрезков, на каждом из которых либо один, либо ноль корней. А корни
производной
можно найти рекурсивно, спустившись до полинома второй, или если хочешь первой
степени.
4. Теперь о поиске корня на отрезке [a,b], если P(a)*P(b)>0, то корней на этом
отрезке
нет, если же P(a)*P(b)=0, то либо a, либо b - корень. Теперь если P(a)*P(b)<0.
То
рассмотрим точку c=(a+b)/2, если P(a)*(c)>0, то корень отрезке [c,b], в
противном случае
на отрезке [a,c]. Теперь проделаем то же самое для нового осрезка, и так до тех
пока
расстояние от a до b, не станет меньше фиксированого эпсилон, которое
выбирается в
зависимости от того с какой точностью тебе нужен корень. Так вот как только
b-a<eps, то
объявляем a корнем.
Если чего не понял пиши, я знаю что объяснят я не умею.
Bye ..
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Metal Invaders. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
