Жертва не удалась

Метод Аберта , или метод Аберта-Эрлиха или метод Эрлиха-Аберта , названный в честь Оливера Аберта. ^[1] и Луи В. Эрлих, ^[2] — алгоритм поиска корней, разработанный в 1967 году для одновременной аппроксимации всех корней одномерного многочлена .

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

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

Описание

Позволять $p(x)=p_{n}x^{n}+p_{n-1}x^{n-1}+\cdots +p_{1}x+p_{0}$ — одномерный полином степени $n$ с действительными или комплексными коэффициентами. Тогда существуют комплексные числа $z_{1}^{*},\,z_{2}^{*},\dots ,z_{n}^{*}$ , корни $p(x)$ , что дает факторизацию :

p(x)=p_{n}\cdot (x-z_{1}^{*})\cdot (x-z_{2}^{*})\cdots (x-z_{n}^{*}).

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

Позволять $z_{1},\dots ,z_{n}\in \mathbb {C}$ быть текущими приближениями нулей $p(x)$ . Затем сместите числа $w_{1},\dots ,w_{n}\in \mathbb {C}$ вычисляются как

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'(z_{k})$ является полиномиальной производной $p$ оценивается в точке $z_{k}$ .

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

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

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

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

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

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

Итерационная формула представляет собой одномерную итерацию Ньютона для функции

F(x)={\frac {p(x)}{\prod _{j=1;\,j\neq k}^{n}(x-z_{j})}}

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

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

{\begin{aligned}{\frac {F'(x)}{F(x)}}&={\frac {d}{dx}}\ln |F(x)|\\&={\frac {d}{dx}}{\big (}\ln |p(x)|-\sum _{j=1;\,j\neq k}^{n}\ln |x-z_{j}|{\big )}\\&={\frac {p'(x)}{p(x)}}-\sum _{j=1;\,j\neq k}^{n}{\frac {1}{x-z_{j}}}\end{aligned}}

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

z_{k}'=z_{k}-{\frac {F(z_{k})}{F'(z_{k})}}=z_{k}-{\frac {1}{{\frac {p'(z_{k})}{p(z_{k})}}-\sum _{j=1;\,j\neq k}^{n}{\frac {1}{z_{k}-z_{j}}}}}\,,

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

Литература

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

См. также

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

[:0-1] Jump up to: Перейти обратно: ^а ^б ^с ^д Аберт, Оливер (1973). «Итерационные методы одновременного нахождения всех нулей многочлена» . Математика. Комп . 27 (122). Математика вычислений, Vol. 27, № 122: 339–344. дои : 10.2307/2005621 . JSTOR 2005621 . Из-за очевидной аналогии с электростатикой это поле можно назвать полем единицы плюс заряд... Чтобы избежать этого, в каждой точке отбора проб присваиваем единицу минус заряд. Идея здесь заключается в том, что, когда точка выборки z находится рядом с простым нулем, поле минусового заряда в точке z должно противодействовать положительному заряду в нуле, предотвращая сходимость второй точки выборки к этому нулю.

[:2-2] Jump up to: Перейти обратно: ^а ^б Эрлих, Луи В. (1967). «Модифицированный метод Ньютона для полиномов» . Комм. АКМ . 10 (2): 107–108. дои : 10.1145/363067.363115 .

[:1-3] Jump up to: Перейти обратно: ^а ^б Бини, Дарио Андреа (1996). «Численное вычисление полиномиальных нулей методом Аберта». Численные алгоритмы . 13 (2): 179–200. Бибкод : 1996NuAlg..13..179B . дои : 10.1007/BF02207694 . S2CID 23899456 .

[4] Бауэр, Флорида; Стер, Дж. (1962). «Алгоритм 105: Ньютон Мэйли» . Комм. АКМ . 5 (7): 387–388. дои : 10.1145/368273.368423 .

[1]

[2]

[3]

[4]

v т и Алгоритмы поиска корня
Брекетинг (без производной)	Метод бисекции Подделки правил метод ИТП
Домохозяин	метод Ньютона метод Галлея
Квазиньютон	метод Бройдена Метод секущего метод Стеффенсена
Гибридные методы	метод Брента Метод рыцарей
Полиномиальные методы	Жертва не удалась Метод Бэрстоу Метод Дюрана – Кернера метод Греффе Алгоритм Дженкинса – Трауба Алгоритм Лемера – Шура метод Лагерра Метод расщепления круга
Другие методы	Итерация с фиксированной точкой Обратная квадратичная интерполяция метод Мюллера Обобщенный метод секущих Сиди