Метод Граффеса - Википедия - 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 {align} 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}) право } & = p (x) times left {(- 1) ^ {n} p (-x) right } & = (- 1) ^ {n} p (x) p (-x) конец {выровнено}}}

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

{ displaystyle { begin {align} 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 {выровнено}}}

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

{ 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 {align} 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 {выравнивается}}}

Если корни ${ 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} приблизительно -y_ {1}}

{ displaystyle a _ {; 2} ^ {k} приблизительно y_ {1} y_ {2}}

и так далее,

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

{ Displaystyle y_ {1} приблизительно -a _ {; 1} ^ {k}, ; y_ {2} приблизительно -a _ {; 2} ^ {k} / a _ {; 1} ^ {k }, ; dots ; y_ {n} приблизительно -a _ {; n} ^ {k} / a _ {; n-1} ^ {k}.}

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

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

Метод Граффа лучше всего работает для многочленов с простыми действительными корнями, хотя его можно адаптировать для многочленов со сложными корнями и коэффициентами, а также для корней с большей кратностью. Например, было замечено^[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 я = 0,1, точки, d}$ . Это позволяет оценить кратность структуры множества корней.

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

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

Этот метод заменяет числа на усеченные. степенной ряд степени 1, также известный как двойные числа. Символически это достигается введением «алгебраической бесконечно малой» ${ displaystyle varepsilon}$ с определяющим свойством ${ Displaystyle varepsilon ^ {2} = 0}$ . Тогда многочлен ${ Displaystyle р (х + 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 п ^ {2 ^ {k} -1} M ^ {2 ^ {k}}}$ для внутренних коэффициентов.

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

{ Displaystyle с = альфа , е ^ {- 2 ^ {к} , г},}

куда ${ 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}$ . Таким образом

{ 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 ( альфа _ {м}, г_ {м})}$ , ${ Displaystyle м = 0, точки, п}$ . Определив углы выпуклой оболочки множества точек ${ displaystyle {(m, r_ {m}): ; m = 0, dots, n }}$ можно определить кратности корней многочлена. Комбинируя эту перенормировку с касательной итерацией, можно напрямую извлечь из коэффициентов в углах огибающей корни исходного многочлена.