Метод Граффеса - Graeffes method

В математика, Метод Граффа или же Метод Данделина – Лобаческого – Греффа. является алгоритм нахождения всех корней многочлена. Он был разработан независимо Жерминаль Пьер Данделен в 1826 г. и Лобачевский в 1834 г. В 1837 г. Карл Генрих Греффе также открыл основную идею метода.^[1] Метод разделяет корни многочлена, многократно возводя их в квадрат. Это возведение корней в квадрат выполняется неявно, то есть работает только с коэффициентами полинома. Ну наконец то, Формулы Вьете используются для аппроксимации корней.

Итерация Данделина – Греффе

Позволять п(Икс) - многочлен степени п

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

потом

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

Позволять q(Икс) - многочлен с квадратами ${\displaystyle x_{1}^{2},\cdots ,x_{n}^{2}}$ как его корни,

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

Тогда мы можем написать:

${\displaystyle {\begin{aligned}q(x^{2})&=\left(x^{2}-x_{1}^{2}\right)\cdots \left(x^{2}-x_{n}^{2}\right)\\&=(x-x_{1})(x+x_{1})\cdots (x-x_{n})(x+x_{n})\\&=\left\{(x-x_{1})\cdots (x-x_{n})\right\}\times \left\{(x+x_{1})\cdots (x+x_{n})\right\}\\&=p(x)\times \left\{(-1)^{n}(-x-x_{1})\cdots (-x-x_{n})\right\}\\&=p(x)\times \left\{(-1)^{n}p(-x)\right\}\\&=(-1)^{n}p(x)p(-x)\end{aligned}}}$

q(Икс) теперь можно вычислить с помощью алгебраических операций над коэффициентами многочлена п(Икс) один. Позволять:

${\displaystyle {\begin{aligned}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}\end{aligned}}}$

то коэффициенты связаны соотношением

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

Грефф заметил, что если отделить п(Икс) на нечетные и четные части:

${\displaystyle p(x)=p_{e}\left(x^{2}\right)+xp_{o}\left(x^{2}\right),}$

то получается упрощенное алгебраическое выражение для q(Икс):

${\displaystyle q(x)=(-1)^{n}\left(p_{e}(x)^{2}-xp_{o}(x)^{2}\right).}$

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

Повторяя эту процедуру несколько раз, корни разделяются по величине. Повторение k раз дает многочлен степени п:

${\displaystyle q^{k}(y)=y^{n}+{a^{k}}_{1}\,y^{n-1}+\cdots +{a^{k}}_{n-1}\,y+{a^{k}}_{n}\,}$

с корнями

${\displaystyle y_{1}=x_{1}^{2^{k}},\,y_{2}=x_{2}^{2^{k}},\,\dots ,\,y_{n}=x_{n}^{2^{k}}.}$

Если бы величины корней исходного многочлена были разделены некоторым множителем ${\displaystyle \rho >1}$, то есть, ${\displaystyle |x_{k}|\geq \rho |x_{k+1}|}$, то корни k-я итерация разделена быстрорастущим множителем

${\displaystyle \rho ^{2^{k}}\geq 1+2^{k}(\rho -1)}$.

Классический метод Граффа

Далее Вьетские отношения используются

${\displaystyle {\begin{aligned}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}\\&\;\vdots \\a_{\;n}^{k}&=(-1)^{n}(y_{1}y_{2}\cdots y_{n}).\end{aligned}}}$

Если корни ${\displaystyle x_{1},\dots ,x_{n}}$ достаточно разделены, скажем, фактором ${\displaystyle \rho >1}$, ${\displaystyle |x_{m}|\geq \rho |x_{m+1}|}$, то повторные степени ${\displaystyle y_{1},y_{2},...,y_{n}}$ корней разделены множителем ${\displaystyle \rho ^{2^{k}}}$, который быстро становится очень большим.

Коэффициенты повторного полинома затем могут быть аппроксимированы их главным членом,

${\displaystyle a_{\;1}^{k}\approx -y_{1}}$

${\displaystyle a_{\;2}^{k}\approx y_{1}y_{2}}$ и так далее,

подразумевая

${\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 q^{m}(y)}$, м начиная с k к 1, и проверка того, какой из двух вариантов знака является корнем ${\displaystyle q^{m-1}(x)}$. Прежде чем перейти к корням ${\displaystyle q^{m-2}(x)}$, может потребоваться численное повышение точности аппроксимации корня для ${\displaystyle q^{m-1}(x)}$, например, Метод Ньютона.

Метод Граффа лучше всего работает для многочленов с простыми действительными корнями, хотя его можно адаптировать для многочленов со сложными корнями и коэффициентами, а также для корней с большей кратностью. Например, было замечено^[2] что для корня ${\displaystyle x_{\ell +1}=x_{\ell +2}=\dots =x_{\ell +d}}$ с множеством d, дроби

${\displaystyle \left|{\frac {(a_{\;\ell +i}^{m-1})^{2}}{a_{\;\ell +i}^{m}}}\right|}$ как правило ${\displaystyle {\binom {d}{i}}}$

за ${\displaystyle i=0,1,\dots ,d}$. Это позволяет оценить кратность структуры множества корней.

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

Тангенциальный метод Граффе

Этот метод заменяет числа на усеченные. степенной ряд степени 1, также известный как двойные числа. Символически это достигается введением «алгебраической бесконечно малой» ${\displaystyle \varepsilon }$ с определяющим свойством ${\displaystyle \varepsilon ^{2}=0}$. Тогда многочлен${\displaystyle p(x+\varepsilon )=p(x)+\varepsilon \,p'(x)}$ имеет корни ${\displaystyle x_{m}-\varepsilon }$, с полномочиями

${\displaystyle (x_{m}-\varepsilon )^{2^{k}}=x_{m}^{2^{k}}-\varepsilon \,{2^{k}}\,x_{m}^{2^{k}-1}=y_{m}+\varepsilon \,{\dot {y}}_{m}.}$

Таким образом, ценность ${\displaystyle x_{m}}$ легко получается как дробь ${\displaystyle x_{m}=-{\tfrac {2^{k}\,y_{m}}{{\dot {y}}_{m}}}.}$

Этот вид вычислений с бесконечно малыми числами легко реализовать аналогично вычислению с комплексными числами. Если принять комплексные координаты или начальный сдвиг на какое-то случайно выбранное комплексное число, то все корни многочлена будут различными и, следовательно, восстановимыми с итерацией.

Перенормировка

Каждый полином можно масштабировать в области и диапазоне так, чтобы в результирующем полиноме первый и последний коэффициенты имели размер один. Если размер внутренних коэффициентов ограничен M, то размер внутренних коэффициентов после одного этапа итерации Граффе ограничен величиной ${\displaystyle nM^{2}}$. После k этапы каждый получает предел ${\displaystyle n^{2^{k}-1}M^{2^{k}}}$ для внутренних коэффициентов.

Чтобы преодолеть ограничение, обусловленное ростом полномочий, Малайович – Зубелли предлагает представить коэффициенты и промежуточные результаты в k-й этап алгоритма масштабированной полярной формой

${\displaystyle c=\alpha \,e^{-2^{k}\,r},}$

куда ${\displaystyle \alpha ={\frac {c}{|c|}}}$ - комплексное число единичной длины и ${\displaystyle r=-2^{-k}\log |c|}$ положительный реальный. Отщепление власти ${\displaystyle 2^{k}}$ в экспоненте уменьшает абсолютное значение c к соответствующему диадическому корню. Поскольку при этом сохраняется величина (представления) начальных коэффициентов, этот процесс был назван перенормировкой.

Умножение двух чисел этого типа выполняется просто, тогда как сложение выполняется после факторизации. ${\displaystyle c_{3}=c_{1}+c_{2}=|c_{1}|\cdot \left(\alpha _{1}+\alpha _{2}{\tfrac {|c_{2}|}{|c_{1}|}}\right)}$, куда ${\displaystyle c_{1}}$ выбирается как большее из обоих чисел, то есть ${\displaystyle r_{1}<r_{2}}$. Таким образом

${\displaystyle \alpha _{3}={\tfrac {s}{|s|}}}$ и ${\displaystyle r_{3}=r_{1}+2^{-k}\,\log {|s|}}$ с ${\displaystyle s=\alpha _{1}+\alpha _{2}\,e^{2^{k}(r_{1}-r_{2})}.}$

Коэффициенты ${\displaystyle a_{0},a_{1},\dots ,a_{n}}$ заключительного этапа k итерации Граффа при некотором достаточно большом значении k, представлены парами ${\displaystyle (\alpha _{m},r_{m})}$, ${\displaystyle m=0,\dots ,n}$. Определив углы выпуклой оболочки множества точек ${\displaystyle \{(m,r_{m}):\;m=0,\dots ,n\}}$ можно определить кратности корней многочлена. Комбинируя эту перенормировку с касательной итерацией, можно напрямую извлечь из коэффициентов в углах огибающей корни исходного многочлена.

Смотрите также

• Алгоритм поиска корней

Рекомендации

1. Домохозяин, Алстон Скотт (1959). «Данделин, Лобачевский или Грефф». Американский математический ежемесячник. 66: 464–466. Дои:10.2307/2310626. JSTOR  2310626.
2. Бест, G.C. (1949). «Заметки о методе квадрата корня Греффа». Американский математический ежемесячник. 56 (2): 91–94. Дои:10.2307/2306166. JSTOR  2306166.

• Вайсштейн, Эрик В. «Метод Греффа». MathWorld.
• Малайович, Грегорио; Зубелли, Хорхе П. (2001). «Касательная итерация Граффа». Numerische Mathematik. 89 (4): 749–782. CiteSeerX  10.1.1.44.3611. Дои:10.1007 / s002110100278.