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

Метод Лобачевського — Греффе — ефективний алгоритм для знаходження коренів многочлена. Іноді називається за іменами першовідкривачів «Метод Лобачевського — Греффе — Данделена» або «Метод Данделена — Лобачевського — Греффе».

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

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

Історія

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

1836 року Берлінська академія наук оголосила конкурс на розробку зручного методу відшукання комплексних коренів многочлена. Серед призерів була стаття швейцарського професора К. Г. Греффе «Die Auflösung der höheren numerischen Gleichungen» (1837). Греффе виклав метод розгорнуто, з численними прикладами. Надалі цей алгоритм трохи вдосконалив Й. Ф. Енке (1841) і Е. Карвалло (E. Carvallo, 1890). Уперше імена всіх трьох першовідкривачів названо в книзі Е. Віттекера і Р. Робінсона «Математична обробка результатів спостережень» («The calculus of observations», 1924).

Обґрунтування

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

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

Тимчасово зробимо припущення, що всі корені цього многочлена дійсні і різні (немає кратних коренів). Позначимо $q(x)$ многочлен, корені якого дорівнюють квадратам коренів $p(x)$:

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

Його коефіцієнти можна обчислити так. Оскільки $x^{2}-x_{k}^{2}=(x-x_{k})(x+x_{k}),$ отримуємо:

$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).$

Якщо позначити коефіцієнти $p(x),q(x)$ через $a_{k},b_{k}$ відповідно:

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

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

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

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

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

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

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

$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}.$

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

$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}.$

Для повернення до початкових невідомим $x_{k}$ залишилося добути з $y_{k}$ корені відповідного степеня і вибрати знаки для отриманих коренів. Для визначення знака можна використати грубу підстановку або формули Вієта.

За ручного розрахунку всі обчислення зручно проводити з рухомою комою, відокремлюючи мантису та порядок числа. Нерідко рекомендується отримані результати додатково уточнити (наприклад, методом Ньютона).

Застосування

Описаний вище алгоритм найкраще працює для рівнянь, всі корені яких дійсні (тоді й коефіцієнти многочлена дійсні). Виникають труднощі, якщо многочлен має кратні корені, тому перед застосуванням слід їх позбутися. Стандартна процедура для цього така. Знаходимо найбільший спільний дільник $d(x)$ для початково многочлена $p(x)$ та його похідної $p'(x)$. Якщо степінь $d(x)$ більший від нуля, слід застосувати метод до частки від ділення $p(x)$ на $d(x)$ (у цієї частки кратні корені завжди відсутні).

За наявності в $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