Метод Лагерра - Laguerres method

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

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

Определение

Алгоритм метода Лагерра для нахождения одного корня многочлена п(Икс) степени п является:

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

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

Вывод

В основная теорема алгебры заявляет, что каждый пмногочлен степени ${\displaystyle p}$ можно записать в виде

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

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

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

Обозначим производную через

${\displaystyle G={\frac {d}{dx}}\ln |p(x)|={\frac {1}{x-x_{1}}}+{\frac {1}{x-x_{2}}}+\cdots +{\frac {1}{x-x_{n}}},}$

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

${\displaystyle H=-{\frac {d^{2}}{dx^{2}}}\ln |p(x)|={\frac {1}{(x-x_{1})^{2}}}+{\frac {1}{(x-x_{2})^{2}}}+\cdots +{\frac {1}{(x-x_{n})^{2}}}.}$

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

${\displaystyle a=x-x_{1}\,}$

и

${\displaystyle b=x-x_{i},\quad i=2,3,\ldots ,n}$

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

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

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

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

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

${\displaystyle a={\frac {n}{G\pm {\sqrt {(n-1)(nH-G^{2})}}}}}$,

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

${\displaystyle \operatorname {Re} \,({\overline {G}}{\sqrt {(n-1)(nH-G^{2})}}\,)>0}$,

куда Re обозначает действительную часть комплексного числа, а грамм является комплексным сопряжением грамм; или же

${\displaystyle a={\frac {p(x)}{p'(x)}}\cdot \left({\frac {1}{n}}+{\frac {n-1}{n}}\,{\sqrt {1-{\frac {n}{n-1}}\,{\frac {p(x)p''(x)}{p'(x)^{2}}}}}\right)^{-1}}$,

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

Для малых значений п(Икс) эта формула отличается от смещения третьего порядка Метод Галлея по ошибке О(п(Икс)³), поэтому близкая к корню сходимость также будет кубической.

Обратите внимание, что даже если «радикальный набор предположений» не работает для некоторого конкретного полинома п(Икс), п(Икс) можно преобразовать в связанный многочлен р для которых предположения верны, например сдвигая начало координат к подходящему комплексному числу ш, давая q(Икс) = п(Икс − ш), чтобы дать различным корням различные величины, если необходимо (что будет, если некоторые корни являются комплексно сопряженными), а затем получить р из q(Икс) многократно применяя преобразование квадратного корня, используемое в Метод Граффа достаточное количество раз, чтобы сделать меньшие корни значительно меньше, чем самый большой (и, таким образом, сгруппированные в сравнении); приближенный корень из метода Граффа затем может быть использован для запуска новой итерации метода Лагерра на р. Примерный корень для п(Икс) может быть получен непосредственно из этого для р.

Если мы сделаем более сильное предположение, что члены в грамм соответствующие корням Икс_я, я = 2, 3, …, п пренебрежимо малы по сравнению с членом, соответствующим корню Икс₁, это ведет к Метод Ньютона.

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

Зоны притяжения метода Лагерра для многочлена x ^ 4 + 2 * x ^ 3 + 3 * x ^ 2 + 4 * x + 1

Если Икс является простым корнем многочлена п(Икс), то метод Лагерра сходится кубически всякий раз, когда первоначальное предположение Икс₀ достаточно близко к корню Икс. С другой стороны, если Икс это множественный корень тогда сходимость только линейная. Это достигается с учетом штрафа в виде вычисления значений полинома и его первой и второй производных на каждом этапе итерации.

Основное преимущество метода Лагерра состоит в том, что он почти гарантированно сходится к немного корень многочлена независимо от того, где выбрано начальное приближение. Это контрастирует с другими методами, такими как Метод Ньютона – Рафсона которые могут не сойтись из-за плохо выбранных начальных предположений. Он может даже сходиться к комплексному корню из полинома, поскольку квадратный корень берется при вычислении а выше может иметь отрицательное число. Это можно рассматривать как преимущество или ответственность в зависимости от приложения, в котором используется метод. Эмпирические данные показали, что сбой сходимости крайне редок, что делает его хорошим кандидатом для универсального алгоритма поиска полиномиального корня. Однако, учитывая довольно ограниченное теоретическое понимание алгоритма, многие численные аналитики не решаются использовать его как таковой и предпочитают более понятные методы, такие как Алгоритм Дженкинса – Трауба, для которого разработана более прочная теория. Тем не менее, алгоритм довольно прост в использовании по сравнению с этими другими "надежными" методами, достаточно прост, чтобы использовать его вручную или с помощью карманного калькулятора, когда автоматический компьютер недоступен. Скорость, с которой метод сходится, означает, что очень редко требуется вычислить более нескольких итераций для получения высокой точности.

Рекомендации

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