Метод Лобачевского — Греффе — эффективный алгоритм для нахождения корней многочлена . Иногда называется по именам первооткрывателей «Метод Лобачевского — Греффе — Данделена» или «Метод Данделена — Лобачевского — Греффе».

По сравнению с другими алгоритмами решения той же задачи (например, методом Ньютона ), данный метод имеет несколько преимуществ. Он не требует предварительной работы по выяснению, где примерно находятся корни и сколько среди них комплексных — данный метод даёт в результате все вещественные корни, а при некоторой модификации — также и комплексные.

Недостатками метода являются отсутствие сопутствующего контроля ошибок при ручном счёте и сложность оценки точности результата. Точность метода может оказаться невысокой из-за численной неустойчивости, то есть быстрого накопления погрешности в ходе вычислений . Кроме того, метод медленно сходится, если у многочлена есть корни, равные или очень близкие по модулю (например, +4 и —4) .

История

Рассуждения, близкие к идее данного метода, высказывали ещё в XVII веке Ньютон (в « Универсальной арифметике ») и Варинг в «Аналитических этюдах» . Первое краткое изложение идеи опубликовал французский математик Жерминаль Данделен в 1826 году . Этот мемуар остался незамеченным. Восемь лет спустя аналогичную идею более подробно изложил и развил Н. И. Лобачевский в своём учебнике «Алгебра или вычисление конечных» (1834), но и его работа не привлекла внимания научной общественности .

В 1836 году Берлинская академия наук объявила конкурс на разработку удобного метода нахождения комплексных корней многочлена. Среди призёров была статья швейцарского профессора Карла Греффе « Die Auflösung der höheren numerischen Gleichungen » (1837). Греффе изложил метод развёрнуто, с многочисленными примерами. В дальнейшем этот алгоритм был несколько усовершенствован Иоганном Энке (1841) и (1896) ), Впервые имена всех трёх первооткрывателей были указаны в книге Эдмунда Уиттекера и Г. Робинсона «Математическая обработка результатов наблюдений» (« The calculus of observations », 1924) .

Обоснование

Рассмотрим многочлен ${\displaystyle n}$ -й степени ${\displaystyle p(x)}$ , корни которого (пока неизвестные) обозначим ${\displaystyle x_{1};\ x_{2}\cdots \ x_{n}}$ :

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

Временно сделаем предположение, что все корни этого многочлена вещественны и различны (нет кратных корней). Обозначим ${\displaystyle q(x)}$ многочлен, корни которого равны квадратам корней ${\displaystyle p(x)}$ :

${\displaystyle q(x)=(x-x_{1}^{2})(x-x_{2}^{2})\cdots (x-x_{n}^{2}).}$

Его коэффициенты можно вычислить следующим образом. Поскольку ${\displaystyle x^{2}-x_{k}^{2}=(x-x_{k})(x+x_{k}),}$ получаем:

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

Если обозначить коэффициенты ${\displaystyle p(x),q(x)}$ через ${\displaystyle a_{k}=a_{\;k}^{0},a_{\;k}^{1}}$ соответственно:

${\displaystyle p(x)=x^{n}+a_{\;1}^{0}x^{n-1}+\cdots +a_{\;n-1}^{0}x+a_{\;n}^{0},}$

${\displaystyle q(x)=x^{n}+a_{\;1}^{1}x^{n-1}+\cdots +a_{\;n-1}^{1}x+a_{\;n}^{1},}$

то коэффициенты обоих многочленов связаны формулой:

${\displaystyle a_{\;k}^{1}=(-1)^{k}\,(a_{\;k}^{0})^{2}+2\sum _{j=1}^{k}(-1)^{j}\,a_{\;k-j}^{0}a_{\;k+j}^{0},}$

где принято, что ${\displaystyle a_{\;j}^{0}=0}$ при ${\displaystyle j<0}$ или ${\displaystyle j>n,a_{\;0}^{0}=a_{\;0}^{1}=1.}$

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

В результате в формулах Виета для последнего многочлена ${\displaystyle q(y)}$ :

${\displaystyle a_{\;1}^{k}=-(y_{1}+y_{2}+\cdots +y_{n});\ a_{\;2}^{k}=y_{1}y_{2}+y_{1}y_{3}+\cdots +y_{n-1}y_{n};\ \dots a_{\;n}^{k}=(-1)^{n}y_{1}y_{2}\cdots y_{n}.}$

все одночлены, кроме одного, в каждом тождестве исчезающе малы, и система Виета сводится к простым линейным равенствам :

${\displaystyle y_{1}\approx -a_{\;1}^{k},\;y_{2}\approx -a_{\;2}^{k}/a_{\;1}^{k},\;\dots \;y_{n}\approx -a_{\;n}^{k}/a_{\;n-1}^{k}.}$

Для возврата к исходным неизвестным ${\displaystyle x_{k}}$ осталось извлечь из ${\displaystyle y_{k}}$ корни соответствующей степени и выбрать знаки для полученных корней. Для определения знака можно использовать грубую подстановку или формулы Виета.

При ручном счёте все вычисления удобно проводить с плавающей точкой , отделяя мантиссу и порядок числа. Нередко рекомендуется полученные результаты дополнительно уточнить (например, методом Ньютона ).

Применение

Описанный выше алгоритм лучше всего работает для уравнений, все корни которых вещественны (тогда и коэффициенты многочлена вещественны). Возникают затруднения, если у многочлена есть кратные корни, поэтому перед применением следует избавиться от них. Стандартная процедура для этого следующая. Находим наибольший общий делитель ${\displaystyle d(x)}$ для исходного многочлена ${\displaystyle p(x)}$ и его производной ${\displaystyle p'(x)}$ . Если степень ${\displaystyle d(x)}$ больше нулевой, следует применить метод к частному от деления ${\displaystyle p(x)}$ на ${\displaystyle d(x)}$ (у этого частного кратные корни всегда отсутствуют).

При наличии у ${\displaystyle p(x)}$ комплексных корней метод также применим, но включает некоторые усложнения, подробно описанные в приведенной ниже литературе.

См. также

• Численное решение уравнений

Литература

• Березин И. С. , Жидков Н. П. Методы вычислений. — М. : Физматлит, 1960. — Т. 2. — С. 103—128. — 620 с.
• Демидович Б. П. , Марон И. А. Основы вычислительной математики. — Изд. 2-е. — М. : Физматлит, 1963. — С. 176—195. — 660 с.
• Лобачевский Н. И. Алгебра или вычисления конечных, Полн. собр. соч., т. 4, М. - П., 1948.
• Лобачевского метод // Математическая энциклопедия (в 5 томах). — М. : Советская Энциклопедия , 1982. — Т. 3.

Ссылки

• Брудно А. Л. .// Квант. № 4 (1989), С. 51—53.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .

Примечания