Введение
Алгоритм поиска корней полиномов
В численном анализе метод Лагерра — это алгоритм поиска корней, специально разработанный для полиномов. Иными словами, метод Лагерра может быть использован для численного решения уравнения f(x) = 0 для заданного полинома p(x). Одно из наиболее полезных свойств этого метода заключается в том, что, согласно обширным эмпирическим исследованиям, он очень близок к методу, гарантированно сходящемуся к корню, то есть почти всегда гарантированно сходится к некоторому корню полинома, независимо от выбранного начального приближения. Однако для компьютерных вычислений существуют более эффективные методы, которые гарантированно находят все корни (см.) или все действительные корни (см. Изоляция действительных корней). Этот метод назван в честь Эдмона Лагерра, французского математика.
In numerical analysis, Laguerre's method is a root finding algorithm tailored to polynomials. In other words, Laguerre's method can be used to numerically solve the equation for a given polynomial p(x). One of the most useful properties of this method is that it is, from extensive empirical study, very close to being a "sure fire" method, meaning that it is almost guaranteed to always converge to some root of the polynomial, no matter what initial guess is chosen. However, for computer computation, more efficient methods are known, with which it is guaranteed to find all roots (see ) or all real roots (see Real root isolation). This method is named in honour of Edmond Laguerre, a French mathematician.
Свойства
Если x является простым корнем многочлена p(x), то метод Лагерра сходится кубически, когда начальное приближение x₀ достаточно близко к корню x. С другой стороны, если x является кратным корнем, то сходимость лишь линейная. Это достигается ценой вычисления значений многочлена и его первой и второй производных на каждом этапе итерации. Важным преимуществом метода Лагерра является то, что он почти гарантированно сходится к некоторому корню многочлена, независимо от выбора начального приближения. Это в отличие от других методов, таких как метод Ньютона-Рафсона, который может не сходиться при неудачном выборе начального приближения. Он может даже сходиться к комплексному корню многочлена, поскольку квадратный корень, извлекаемый при вычислении вышеуказанного выражения, может быть из отрицательного числа. Это можно рассматривать как преимущество или недостаток, в зависимости от области применения метода. Эмпирические данные показывают, что случаи расходимости крайне редки, что делает его хорошим кандидатом для алгоритма поиска корней многочлена общего назначения. Однако, учитывая довольно ограниченное теоретическое понимание алгоритма, многие численные аналитики не решаются использовать его в качестве такового и предпочитают более изученные методы, такие как алгоритм Дженкинса-Трауба, для которого разработана более надежная теория. Тем не менее, алгоритм довольно прост в использовании по сравнению с этими другими "надежными" методами, достаточно прост для ручного вычисления или с использованием карманного калькулятора, когда автоматизированный компьютер недоступен. Высокая скорость сходимости метода означает, что очень редко требуется вычислять более нескольких итераций для достижения высокой точности.