метод Aberth

редактировать

Метод Aberth, или метод Аберта – Эрлиха, названный в честь Оливера Аберта и Луи У. Эрлиха, представляет собой алгоритм поиска корней, разработанный в 1967 году для одновременного приближения всех корней одномерный многочлен.

Этот метод сходится кубически, что является улучшением по сравнению с методом Дюрана – Кернера, другим алгоритмом для аппроксимации всех корней сразу, который сходится квадратично. (Однако оба алгоритма сходятся линейно в нескольких нулях.)

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

Содержание

1 Описание
2 Вывод из метода Ньютона
3 Литература
4 См. Также

Описание

Пусть $p (x) = pnxn + pn - 1 xn - 1 + ⋯ + p 1 x + p 0 {\ displaystyle p (x) = p_ {n} x ^ {n} + p_ {n-1} x ^ {n-1} + \ cdots + p_ {1} x + p_ {0}}$ $p (x) = p_nx ^ n + p_ {n-1} x ^ {n-1} + \ cdots + p_1x + p_0$ быть одномерным многочленом степени $n {\ displaystyle n}$ $n$ с действительными или комплексными коэффициентами. Тогда существуют комплексные числа $z 1 ∗, z 2 ∗,…, zn ∗ {\ displaystyle z_ {1} ^ {*}, \, z_ {2} ^ {*}, \ dots, z_ {n} ^ {*}}$ $z ^ * _ 1, \, z ^ * _ 2, \ dots, z ^ * _ n$ , корни $p (x) {\ displaystyle p (x)}$ $p (x)$ , которые дают факторизацию :

p (x ) = pn ⋅ (x - z 1 ∗) ⋅ (x - z 2 ∗) ⋯ (x - zn ∗). {\ Displaystyle п (х) = п_ {п} \ cdot (х-z_ {1} ^ {*}) \ cdot (x-z_ {2} ^ {*}) \ cdots (x-z_ {n} ^ {*}).}

p (x) = p_n \ cdot (xz ^ * _ 1) \ cdot (xz ^ * _ 2) \ cdots (xz ^ * _ n).

Хотя эти числа неизвестны, верхняя и нижняя границы для их абсолютных значений вычисляются из коэффициентов полинома. Теперь можно выбрать $n {\ displaystyle n}$ $n$ различных чисел в комплексной плоскости - случайным или равномерно распределенным - так, чтобы их абсолютные значения находились в тех же пределах. (Кроме того, если нули симметричны, начальные точки не должны быть точно симметричными по одной и той же оси, так как это может предотвратить сходимость.) Набор таких чисел называется начальным приближением набора корней $p ( х) {\ Displaystyle р (х)}$ $p (x)$ . Это приближение можно итеративно улучшить, используя следующую процедуру.

Пусть $z 1,…, zn ∈ C {\ displaystyle z_ {1}, \ dots, z_ {n} \ in \ mathbb {C}}$ $z_ {1}, \ dots, z_ {n} \ in {\ mathbb C}$ будет текущим приближения нулей $p (x) {\ displaystyle p (x)}$ $p (x)$ . Затем числа смещения $w 1,…, wn ∈ C {\ displaystyle w_ {1}, \ dots, w_ {n} \ in \ mathbb {C}}$ $w_1, \ dots, w_n \ in \ mathbb C$ вычисляются как

wk знак равно п (zk) p ′ (zk) 1 - p (zk) p ′ (zk) ⋅ ∑ j ≠ k 1 zk - zj, {\ displaystyle w_ {k} = {\ frac {\ frac {p (z_ { k})} {p '(z_ {k})}} {1 - {\ frac {p (z_ {k})} {p' (z_ {k})}} \ cdot \ sum _ {j \ neq k} {\ frac {1} {z_ {k} -z_ {j}}}}},}

w_{k}={\frac {\frac {p(z_{k})}{p'(z_{k})}}{1-{\frac {p(z_{k})}{p'(z_{k})}}\cdot \sum _{j\neq k}{\frac {1}{z_{k}-z_{j}}}}},

где $p ′ (zk) {\ displaystyle p '(z_ {k})}$ $p'(z_{k})$ - полиномиальная производная от $p {\ displaystyle p}$ $p$ , вычисленная в точке $zk {\ displaystyle z_ {k}}$ $z_ {k}$ .

Следующий набор приближений корней из $p (x) {\ displaystyle p (x)}$ $p (x)$ тогда $z 1 - w 1,…, zn - wn {\ displaystyle z_ {1} -w_ {1} , \ точки, z_ {n} -w_ {n}}$ ${\ displaystyle z_ {1} -w_ {1}, \ dots, z_ {n} -w_ {n}}$ . Качество текущего приближения можно измерить по значениям полинома или по размеру смещений.

Концептуально этот метод использует аналогию электростатического, моделируя приближенные нули как подвижные отрицательные точечные заряды, которые сходятся к истинным нулям, представленным фиксированными положительными точечными зарядами.. Прямое применение метода Ньютона к каждому приближенному нулю часто приводит к неправильному схождению нескольких начальных точек к одному корню. Метод Аберта позволяет избежать этого, также моделируя отталкивающий эффект, который подвижные заряды оказывают друг на друга. Таким образом, когда подвижный заряд сходится к нулю, их заряды нейтрализуются, так что другие подвижные заряды больше не притягиваются к этому месту, побуждая их сходиться к другим «незанятым» нулям. (Стилтьес также моделировал положения нулей многочленов как решения электростатических задач.)

Внутри формулы метода Аберта можно найти элементы метода Ньютона и метод Дюрана – Кернера. Детали для эффективной реализации, особенно. о выборе хороших начальных приближений можно найти в Bini (1996).

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

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

Вывод из метода Ньютона

Формула итерации - это одномерная итерация Ньютона для функция

F (x) = p (x) ∏ j = 0; J ≠ Kn (Икс - Zj) {\ Displaystyle F (x) = {\ гидроразрыва {p (x)} {\ prod _ {j = 0; \, j \ neq k} ^ {n} (x-z_ { j})}}}

F (x) = \ frac {p (x)} {\ prod_ {j = 0; \, j \ ne k} ^ n (x-z_j)}

Если значения $z 1,…, zn {\ displaystyle z_ {1}, \ dots, z_ {n}}$ $z_ {1}, \ dots, z_ {n}$ уже близки к корням $p (x) {\ displaystyle p (x)}$ $p (x)$ , тогда рациональная функция $F (x) {\ displaystyle F (x)}$ $F (x)$ почти линейна с доминирующим корнем, близким к $zk {\ displaystyle z_ {k}}$ $z_ {k}$ и полюсами в $z 1,…, zk - 1, zk + 1,…, zn {\ displaystyle z_ {1}, \ dots, z_ {k-1}, z_ {k + 1}, \ dots, z_ {n}}$ $z_1, \ dots, z_ {k-1}, z_ {k + 1}, \ dots, z_n$ , которые направляют итерацию Ньютона от корней p (x), которые близки к ним. То есть соответствующие области притяжения становятся довольно маленькими, в то время как корень, близкий к $z k {\ displaystyle z_ {k}}$ $z_ {k}$ , имеет широкую область притяжения.

Шаг Ньютона $F (x) F '(x) {\ displaystyle {\ tfrac {F (x)} {F' (x)}}}$ $\tfrac{F(x)}{F'(x)}$ в одномерный случай - это величина, обратная логарифмической производной

F ′ (x) F (x) = ddx ln ⁡ | F (x) | знак равно d d x (ln ⁡ | p (x) | - j = 0; j ≠ k n ln ⁡ | x - z j |) = p ′ (x) p (x) - ∑ j = 0; j ≠ kn 1 x - zj {\ displaystyle {\ begin {align} {\ frac {F '(x)} {F (x)}} & = {\ frac {d} {dx}} \ ln | F ( x) | \\ & = {\ frac {d} {dx}} {\ big (} \ ln | p (x) | - \ sum _ {j = 0; \, j \ neq k} ^ {n} \ ln | x-z_ {j} | {\ big)} \\ & = {\ frac {p '(x)} {p (x)}} - \ sum _ {j = 0; \, j \ neq k} ^ {n} {\ frac {1} {x-z_ {j}}} \ end {align}}}

\begin{align} \frac{F'(x)}{F(x)} &= \frac{d}{dx}\ln|F(x)|\\ &= \frac{d}{dx}\big(\ln|p(x)|-\sum_{j=0;\,j\ne k}^n\ln|x-z_j|\big)\\ &= \frac{p'(x)}{p(x)}-\sum_{j=0;\,j\ne k}^n\frac1{x-z_j} \end{align}

Таким образом, новое приближение вычисляется как

zk ′ = zk - F (zk ) F ′ (zk) = zk - 1 p ′ (zk) p (zk) - ∑ j = 0; j ≠ kn 1 zk - zj, {\ displaystyle z_ {k} '= z_ {k} - {\ frac {F (z_ {k})} {F' (z_ {k})}} = z_ {k} - {\ frac {1} {{\ frac {p '(z_ {k})} {p (z_ {k})}} - \ sum _ {j = 0; \, j \ neq k} ^ {n } {\ frac {1} {z_ {k} -z_ {j}}}}} \ ,,}

z_k'=z_k-\frac{F(z_k)}{F'(z_k)}=z_k-\frac1{\frac{p'(z_k)}{p(z_k)}-\sum_{j=0;\,j\ne k}^n\frac1{z_k-z_j}}\,,

, которая является формулой обновления метода Аберта – Эрлиха.

Литература

^ Аберт, Оливер (1973). «Итерационные методы поиска всех нулей многочлена одновременно». Математика. Комп. Математика вычислений, Vol. 27, № 122. 27(122): 339–344. DOI : 10.2307 / 2005621. JSTOR 2005621. Из-за очевидной аналогии с электростатикой это поле можно назвать полем единицы плюс заряд... Чтобы избежать этого, мы присваиваем единицу минус заряда в каждой точке выборки. Идея здесь в том, что, когда точка выборки z близка к простому нулю, поле от отрицательного заряда в z должно противодействовать полю от положительного заряда в нуле, предотвращая схождение второй точки выборки к этому нулю.
^ Эрлих, Луис В. (1967). «Модифицированный метод Ньютона для многочленов». Comm. ACM. 10(2): 107–108. doi : 10.1145 / 363067.363115.
^ Бини, Дарио Андреа (1996). «Численное вычисление полиномиальных нулей методом Аберта». Численные алгоритмы. 13(2): 179–200. Bibcode : 1996NuAlg..13..179B. doi : 10.1007 / BF02207694.
^Bauer, F.L.; Стоер, Дж. (1962). «Алгоритм 105: Ньютон Мэли». Comm. ACM. 5(7): 387–388. doi : 10.1145 / 368273.368423.

См. Также

MPSolve Пакет для численного вычисления полиномиальных корней. Бесплатное использование в научных целях.