ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Artem Gubenkov                       2:5020/400     07 Feb 2002  14:20:52
 To : Eduard Vatutin
 Subject : Re: Решение уравнения
 -------------------------------------------------------------------------------- 
 

 Hello, Eduard!
 You wrote to Zapadinsky Anatoly \(ZAB\) on Wed, 06 Feb 2002 01:16:50 :
 
  EV>>> Возникла необходимость решать уравнения вида
  EV>>>     A*x^n + B*x^(n-1) + ... + Z = 0
  EV>>> У такого уравнения, согласно основной теореме алгебры, должно быть
  EV>>> n корней.
  EV>>> Hеобходимо найти все его действительные корни. Выручайте...
  EV> ... Адреналин стекал в ботинки ...
 
 Обозначим полином степени n, корни которого мы ищем, как:
 
 P(x)=a[0]*x^n+a[1]*x^(n-1)+a[2]*x^(n-2)+...+a[n]=0, a[0]!=0
 
 Хорошие результаты дает решение таких уравнений методом Hьютона,
 *итерационная* формула которого имеет вид:
 
 x[n+1]=x[n]-P(x[n])/P'(x[n]), P'(x[n])!=0
 (производные любого порядка такого полинома считаются без дифференцирования)
 
 Этот метод обладает квадратичной сходимостью в окрестности корня.
 То есть, задавая начальное приближение, мы по-любому после нескольких
 итераций получаем значение _одного_ корня.
 
 Hо тебе-то нужны они все, поэтому примем во внимание следующее:
 *Все* (действительные корни - частный случай комплексных, у которых мнимая
 чать (или как она там называется) == 0) корни этого полинома локализованы
 в кольце на комплексной плоскости (надеюсь, слышал о такой) с центром в
 начале координат.
 При чем внутренний радиус кольца:
 
 r=|a[n]| / (|a[n]| + max( |a[0]|,...|a[n-1]| ))
 
 а внешний радиус:
 
 R=( |a[0]| + max( |a[1]|,...|a[n]| )) / |a[0]|
 
 Представил?
 
 А что, если разбить это кольцо "сеткой" на 10*n x 20*n сегментов
 (хотя можно и поменьше - это я так, с запасом :).
 Разбить отрезок (R-r) на 10*n сегментов, и рассматривать все
 получившиеся точки на нем, поворачивая отрезок на 360/(20*n) градусов.
 Получим 10*n*20*n точек на комплексной плоскости, лежащих в искомом кольце,
 каждую из которых используем как начальное приближение в методе Hьютона.
 В результате найдем столько же корней, среди которых много повторяющиеся.
 Из них выбираем n неповторяющихся (или будем запоминать только те корни,
 которые отличаются от найденных ранее).
 
 Если тебе нужны только действительные корни, то выбирай те, у которых
 мнимая часть == 0.
 
 P.S. не забудь, что все комплексные корни кратные (или как они там)
 т.е. если есть корень x+i*y, то всегда будет и корень x-i*y
 
 ...Проще надо быть, проще...
 With best regards, Artem Gubenkov.
 --- ifmail v.2.15dev5
  * Origin: News Server of JSC Saratov-Mobile (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор