метод Греффе

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

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

Пусть p ( x ) — многочлен степени n

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

Затем

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

Пусть q ( x ) будет многочленом, имеющим квадраты $x_{1}^{2},\cdots ,x_{n}^{2}$ как его корни,

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

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

${\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 ( ​​x ) теперь можно вычислить с помощью алгебраических операций только над коэффициентами многочлена p ( x ) . Позволять:

${\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}}$

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

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

Греффе заметил, что если разделить p ( x ) на нечетную и четную части:

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

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

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

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

Повторение этой процедуры несколько раз разделяет корни по их величинам. Повторение k раз дает полином степени n :

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

с корнями

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

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

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

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

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

${\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}}$

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

Затем коэффициенты повторного полинома можно аппроксимировать их старшим членом:

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

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

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

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

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

Чтобы также получить угол этих корней, было предложено множество методов, самый простой из которых - последовательное вычисление квадратного корня из (возможно, комплексного) корня из $q^{m}(y)$, m в диапазоне от k до 1 и проверка того, какой из двух вариантов знака является корнем $q^{m-1}(x)$. Прежде чем перейти к истокам $q^{m-2}(x)$, возможно, потребуется численно улучшить точность корневых аппроксимаций для $q^{m-1}(x)$, например методом Ньютона .

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

$\left|{\frac {(a_{\;\ell +i}^{m-1})^{2}}{a_{\;\ell +i}^{m}}}\right|$ склонны к ${\binom {d}{i}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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