Метод Лобачевского — Греффе

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

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

Рассмотрим многочлен ${\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.}$

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

В результате в формулах Виета для последнего многочлена ${\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}.}$

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

${\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. Graeffe's Method (англ.) на сайте Wolfram MathWorld.
• Module for Graeffe's Method by John H. Mathews