метод Лагерра

В численном анализе метод Лагерра представляет собой алгоритм поиска корня, адаптированный к полиномам . Другими словами, метод Лагерра можно использовать для численного решения уравнения p ( x ) = 0 для данного многочлена p ( x ) . Одним из наиболее полезных свойств этого метода является то, что, согласно обширным эмпирическим исследованиям, он очень близок к «надежному» методу, а это означает, что он почти гарантированно всегда сходится к некоторому корню многочлена, несмотря ни на что. выбрано первоначальное предположение. Однако для компьютерных вычислений известны более эффективные методы, с помощью которых гарантированно можно найти все корни (см. Алгоритм поиска корней § Корни многочленов ) или все вещественные корни (см. Изоляция вещественного корня ).

Этот метод назван в честь французского математика Эдмона Лагерра .

Определение

Алгоритм метода Лагерра для поиска одного корня многочлена p ( x ) степени n :

• Выберите начальное предположение x ₀
• Для к = 0, 1, 2,...
  • Если $p(x_{k})$ очень мало, выйдите из цикла
  • Рассчитать $G={\frac {p'(x_{k})}{p(x_{k})}}$
  • Рассчитать $H=G^{2}-{\frac {p''(x_{k})}{p(x_{k})}}$
  • Рассчитать $a={\frac {n}{G\pm {\sqrt {(n-1)(nH-G^{2})}}}}$, где знак выбран так, чтобы знаменатель имел большее абсолютное значение, чтобы избежать катастрофического сокращения .
  • Набор $x_{k+1}=x_{k}-a$
• Повторяйте до тех пор, пока a не станет достаточно маленьким или не будет достигнуто максимальное количество итераций.

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

Вывод

Основная теорема алгебры гласит, что каждый полином n- й степени $\ p\$ можно записать в форме

$\ p(x)=C\left(x-x_{1}\right)\left(x-x_{2}\right)\ \cdots \ \left(x-x_{n}\right)\ ,$

так что $\ x_{1},x_{2},\ \ldots ,\ x_{n}\ ,$ являются корнями многочлена. Если мы возьмем натуральный логарифм обеих частей, мы обнаружим, что

$\ln {\bigl |}\ p(x)\ {\bigr |}~=~\ln {\bigl |}\ C\ {\bigr |}\ +\ \ln {\bigl |}\ x-x_{1}\ {\bigr |}\ +\ \ln {\bigl |}\ x-x_{2}\ {\bigr |}\ +\ \cdots \ +\ \ln {\bigl |}\ x-x_{n}\ {\bigr |}~.$

Обозначим логарифмическую производную через

${\begin{aligned}\ G&~=~{\frac {\operatorname {d} }{\operatorname {d} x}}\ln {\Bigl |}\ p(x)\ {\Bigr |}~=~{\frac {1}{\ x-x_{1}\ }}+{\frac {1}{\ x-x_{2}\ }}+\ \cdots \ +{\frac {1}{\ x-x_{n}\ }}\\[0.3em]&~=~{\frac {\ p'(x)\ }{\ {\bigl |}\ p(x)\ {\bigr |}\ }}\ ,\end{aligned}}$

и отрицательная вторая производная

${\begin{aligned}\ H&~=~-{\frac {\operatorname {d} ^{2}}{\operatorname {d} x^{2}}}\ln {\Bigl |}\ p(x)\ {\Bigr |}~=~{\frac {1}{~~(x-x_{1})^{2}\ }}+{\frac {1}{~~(x-x_{2})^{2}\ }}+\ \cdots \ +{\frac {1}{~~(x-x_{n})^{2}\ }}\\[0.3em]&~=~-{\frac {\ p''(x)\ }{\ {\bigl |}\ p(x)\ {\bigr |}\ }}\ +\ \left({\frac {\ p'(x)\ }{\ p(x)\ }}\right)^{2}\cdot \ \operatorname {sgn} \!{\Bigl (}\ p(x)\ {\Bigr )}~.\end{aligned}}$

Затем мы делаем то, что Эктон (1970) называет «решительный набор предположений» , что корень, который мы ищем, скажем, $\ x_{1}\$ это небольшое расстояние, $\ a\ ,$ вдали от наших догадок $\ x\ ,$ а все остальные корни сгруппированы вместе на некотором расстоянии $\ b~.$ Если обозначить эти расстояния через

$\ a\ \equiv \ x-x_{1}\$

и

$\ b\ \approx \ x-x_{2}\ \approx \ x-x_{3}\ \approx \ \ldots \ \approx \ x-x_{n}\ ,$

или точно,

$\ b\ \equiv \ \operatorname {\mathsf {harmonic\ mean}} {\Bigl \{}\ x-x_{2},\ x-x_{3},\ \ldots \ x-x_{n}\ {\Bigr \}}\$

тогда наше уравнение для $\ G\$ может быть записано как

$G={\frac {\ 1\ }{a}}+{\frac {\ n-1\ }{b}}$

и выражение для $\ H\$ становится

$H={\frac {1}{~a^{2}\ }}+{\frac {\ n-1\ }{~b^{2}\ }}~.$

Решая эти уравнения для $\ a\ ,$ мы находим это

$a={\frac {n}{\ G\pm {\sqrt {{\bigl (}n-1{\bigr )}{\bigl (}n\ H-G^{2}{\bigr )}\ }}\ }}\ ,$

где в этом случае квадратный корень из (возможно) комплексного числа выбирается так, чтобы получить наибольшее абсолютное значение знаменателя и сделать $\ a\$ как можно меньше; эквивалентно, он удовлетворяет:

$\operatorname {\mathcal {R_{e}}} {\biggl \{}\ {\overline {G}}{\sqrt {\left(n-1\right)\left(n\ H-G^{2}\right)\ }}\ {\biggr \}}>0\ ,$

где $\ {\mathcal {R_{e}}}\$ обозначает действительную часть комплексного числа, а $\ {\overline {G}}\$ представляет собой комплексное сопряжение $\ G\ ;$ или

$a={\frac {\ p(x)\ }{p'(x)}}\cdot {\Biggl \{}\ {\frac {\ 1\ }{n}}+{\frac {\ n-1\ }{n}}\ {\sqrt {1-{\frac {n}{\ n-1\ }}\ {\frac {\ p(x)\ p''(x)\ }{~p'(x)^{2}\ }}\ }}\ {\Biggr \}}^{-1}\ ,$

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

Для небольших значений $\ p(x)\$ эта формула отличается от смещения метода Галлея третьего порядка погрешностью $\ \operatorname {\mathcal {O}} {\bigl \{}\ (p(x))^{3}\ {\bigr \}}\ ,$ поэтому сходимость вблизи корня также будет кубической.

Отступать

Даже если «решительный набор предположений» не работает хорошо для некоторого конкретного полинома p ( x ) , тогда p ( x ) можно преобразовать в связанный полином r , для которого предположения жизнеспособны; например, сначала сместив начало координат в сторону подходящего комплексного числа w , дав второй многочлен q ( x ) = p ( x − w ) , который дает разные корни, явно разные величины, если это необходимо (что будет, если некоторые корни являются комплексно сопряженными ).

После этого, получив третий полином r из q ( x ) , многократно применяя преобразование возведения в квадрат корня из метода Греффе , достаточное количество раз, чтобы сделать меньшие корни значительно меньшими, чем самый большой корень (и, таким образом, сгруппироваться сравнительно ближе к нулю). Приблизительный корень из метода Греффе затем можно использовать для запуска новой итерации метода Лагерра на r . Тогда приблизительный корень для p ( x ) может быть получен непосредственно из корня для r .

Если мы сделаем еще более радикальное предположение, что члены в $\ G\$ соответствующий корням $\ x_{2},\ x_{3},\ \ldots ,\ x_{n}\$ пренебрежимо малы по сравнению с корнем $\ x_{1}\ ,$ это приводит к методу Ньютона .

Характеристики

Зоны притяжения метода Лагерра для многочлена $~p(x)=x^{4}+2x^{3}+3x^{2}+4x+1~.$

Если x — простой корень многочлена $\ p(x)\ ,$ тогда метод Лагерра сходится кубически всякий раз, когда исходное предположение, $\ x^{(0)}\ ,$ достаточно близко к корню $\ x_{1}~.$ С другой стороны, когда $\ x_{1}\$ является множественной корневой сходимостью, которая является просто линейной, со штрафом в виде вычисления значений полинома, его первой и второй производных на каждом этапе итерации.

Главное преимущество метода Лагерра состоит в том, что он почти гарантированно сходится к некоторому корню многочлена независимо от того, где выбрано начальное приближение . В этом отличие от других методов, таких как метод Ньютона-Рафсона и метод Стефенсена , которые, как известно, не сходятся при плохо выбранных первоначальных предположениях. Метод Лагерра может даже сходиться к комплексному корню многочлена, поскольку подкоренное выражение квадратного корня может иметь отрицательное число в формуле поправки: $\ a\ ,$ приведенное выше – осуществимо, если для вычислений можно удобно использовать комплексные числа. Это можно считать преимуществом или недостатком в зависимости от приложения, в котором используется метод.

Эмпирические данные показывают, что неудачи сходимости случаются крайне редко, что делает его хорошим кандидатом для алгоритма поиска корня многочлена общего назначения. Однако, учитывая довольно ограниченное теоретическое понимание алгоритма, многие численные аналитики не решаются использовать его по умолчанию и предпочитают более понятные методы, такие как алгоритм Дженкинса-Трауба , для которого была разработана более надежная теория и чьи пределы известны. .

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

Ссылки

• Эктон, Форман С. (1970). Численные методы, которые ОБЫЧНО работают . Харпер и Роу. ISBN  0-88385-450-3 – через Интернет-архив (archive.org).
• Гедекер, С. (1994). «Замечание об алгоритмах поиска корней многочленов». Журнал SIAM по научным вычислениям . 15 (5): 1059–1063. Бибкод : 1994ГАК...15.1059Г . дои : 10.1137/0915064 .
• Мекви, Ванкере Р. (2001). Итерационные методы поиска корней полиномов (магистерская диссертация). Математика. Оксфорд, Великобритания: Оксфордский университет. Архивировано из оригинала 23 декабря 2012 года.
• Пан, В.Я. (1997). «Решение полиномиального уравнения: немного истории и недавнего прогресса». Обзор СИАМ . 39 (2): 187–220. Бибкод : 1997SIAMR..39..187P . дои : 10.1137/S0036144595288554 .
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 9.5.3 Метод Лагерра» . Численные рецепты : искусство научных вычислений (3-е изд.). Нью-Йорк, штат Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8 .
• Ралстон, Энтони; Рабиновиц, Филип (1978). Первый курс численного анализа . МакГроу-Хилл. ISBN  0-07-051158-6 .