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

Міркування, близькі до ідеї даного методу, висловлювали ще в XVII столітті Ньютон (в «Універсальній арифметиці») і Воринг в «Аналітичних етюдах»[3]. Перший короткий виклад ідеї опублікував французький математик Ж. Данделен у 1826 році[4]. Цей мемуар залишився непоміченим. Вісім років потому аналогічну ідею детальніше виклав і розвинув М. І. Лобачевський у своєму підручнику «Алгебра або обчислення скінченних» (1834), але і його робота не привернула уваги наукової спільноти[5].

1836 року Берлінська академія наук оголосила конкурс на розробку зручного методу відшукання комплексних коренів многочлена. Серед призерів була стаття швейцарського професора К. Г. Греффе «Die Auflösung der höheren numerischen Gleichungen» (1837). Греффе виклав метод розгорнуто, з численними прикладами. Надалі цей алгоритм трохи вдосконалив Й. Ф. Енке (1841) і Е. Карвалло (E. Carvallo, 1890). Уперше імена всіх трьох першовідкривачів названо в книзі Е. Віттекера і Р. Робінсона «Математична обробка результатів спостережень» («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},b_{k}}$ відповідно:

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

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

то коефіцієнти обох многочленів пов'язані формулою:

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

де прийнято, що ${\displaystyle a_{j}=0}$ при ${\displaystyle j<0}$ чи ${\displaystyle j>n,a_{0}=b_{0}=1.}$

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

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

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

всі одночлени, крім одного, в кожній тотожності зникаюче малі, і система Вієта зводиться до простих лінійних рівностей[6]:

${\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.
• Демидович Б. П., Марон И. А. Основы вычислительной математики. — Изд. 2-е. — М. : Физматлит, 1963. — С. 176—195.
• Лобачевский Н. И. Алгебра или вычисления конечных, Полн. собр. соч., т. 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