Метод Дюрана – Кернера

В численном анализе или метод Вейерштрасса метод Дюрана-Кернера , открытый Карлом Вейерштрассом в 1891 году и повторно открытый независимо Дюраном в 1960 году и Кернером в 1966 году, представляет собой алгоритм поиска корней для решения полиномиальных уравнений . Другими словами, метод можно использовать для численного решения уравнения

ж ( Икс ) = 0,

где f — заданный полином, который можно масштабировать так, чтобы старший коэффициент был равен 1.

Объяснение

Это объяснение рассматривает уравнения четвертой степени . Его легко обобщить на другие степени.

Пусть многочлен f определяется формулой

$f(x)=x^{4}+ax^{3}+bx^{2}+cx+d$

для всех х .

Известные числа a , b , c , d являются коэффициентами .

Пусть (потенциально комплексные) числа P , Q , R , S являются корнями этого многочлена f .

Затем

$f(x)=(x-P)(x-Q)(x-R)(x-S)$

для всех х . можно выделить значение P Из этого уравнения :

$P=x-{\frac {f(x)}{(x-Q)(x-R)(x-S)}}.$

Итак, если использовать как с фиксированной точкой итерацию

$x_{1}:=x_{0}-{\frac {f(x_{0})}{(x_{0}-Q)(x_{0}-R)(x_{0}-S)}},$

он сильно устойчив в том смысле, что каждая начальная точка x ₀ ≠ Q , R , S доставляет после одной итерации корень P = x ₁ .

Более того, если заменить нули Q , R и S аппроксимациями q ≈ Q , r ≈ R , s ≈ S , такие, что q , r , s не равны P , то P все еще является фиксированной точкой возмущенной итерации с фиксированной точкой

$x_{k+1}:=x_{k}-{\frac {f(x_{k})}{(x_{k}-q)(x_{k}-r)(x_{k}-s)}},$

с

$P-{\frac {f(P)}{(P-q)(P-r)(P-s)}}=P-0=P.$

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

Ключ к разгадке метода теперь заключается в объединении итерация с фиксированной точкой для P с аналогичными итерациями для Q , R , S в одновременную итерацию для всех корней.

Инициализируйте p , q , r , s :

р ₀ := (0,4 + 0,9 я ) ⁰ ,

q ₀ := (0,4 + 0,9 я ) ¹ ,

р ₀ := (0,4 + 0,9 я ) ² ,

с ₀ := (0,4 + 0,9 я ) ³ .

нет ничего особенного В выборе 0,4 + 0,9i , за исключением того, что это не действительное число и не корень из единицы .

Сделайте замены для n = 1, 2, 3, ...:

$p_{n}=p_{n-1}-{\frac {f(p_{n-1})}{(p_{n-1}-q_{n-1})(p_{n-1}-r_{n-1})(p_{n-1}-s_{n-1})}},$

$q_{n}=q_{n-1}-{\frac {f(q_{n-1})}{(q_{n-1}-p_{n})(q_{n-1}-r_{n-1})(q_{n-1}-s_{n-1})}},$

$r_{n}=r_{n-1}-{\frac {f(r_{n-1})}{(r_{n-1}-p_{n})(r_{n-1}-q_{n})(r_{n-1}-s_{n-1})}},$

$s_{n}=s_{n-1}-{\frac {f(s_{n-1})}{(s_{n-1}-p_{n})(s_{n-1}-q_{n})(s_{n-1}-r_{n})}}.$

Повторяйте, пока числа p , q , r , s по существу перестать изменяться относительно желаемой точности. Тогда они имеют значения P , Q , R , S в некотором порядке. и с выбранной точностью. Итак, проблема решена.

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

Вариации

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

Можно также выбрать начальные значения для p , q , r , s. какой-то другой процедурой, даже случайным образом, но таким образом, что

• они находятся внутри некоторого не слишком большого круга, содержащего также корни f ( x ), например круг вокруг начала координат с радиусом $1+\max {\big (}|a|,|b|,|c|,|d|{\big )}$, (где 1, a , b , c , d — коэффициенты при f ( x ))

и это

• они не слишком близко друг к другу,

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

Если коэффициенты вещественные и полином имеет нечетную степень, то он должен иметь хотя бы один действительный корень. Чтобы найти это, используйте действительное значение p ₀ в качестве первоначального предположения и сделайте q ₀ и r ₀ и т. д. комплексно-сопряженными парами. Тогда итерация сохранит эти свойства; то есть p _n всегда будет вещественным, а q _n и r _n и т. д. всегда будут сопряжены. Таким образом, сходиться _pn к вещественному корню P. будет Альтернативно, сделайте все первоначальные предположения реальными; они останутся такими.

Пример

Этот пример взят из справочника 1992 года. Решаемое уравнение: x ³ − 3x ² + 3 Икс - 5 знак равно 0 . Первые 4 итерации перемещают p , q , r , казалось бы, хаотично, но затем корни располагаются с точностью до 1 десятичного знака. После итерации номер 5 у нас есть 4 правильных десятичных знака, а последующая итерация номер 6 подтверждает, что вычисленные корни фиксированы. Такое общее поведение характерно для метода. Также обратите внимание, что в этом примере корни используются сразу после их вычисления на каждой итерации. Другими словами, при вычислении каждого второго столбца используются значения предыдущих вычисленных столбцов.

это.-нет.	п	д	р
0	+1,0000 + 0,0000i	+0,4000 + 0,9000i	−0,6500 + 0,7200i
1	+1,3608 + 2,0222i	−0,3658 + 2,4838i	−2,3858 − 0,0284i
2	+2,6597 + 2,7137i	+0,5977 + 0,8225i	−0,6320−1,6716i
3	+2,2704 + 0,3880i	+0,1312 + 1,3128i	+0,2821 − 1,5015i
4	+2,5428 − 0,0153i	+0,2044 + 1,3716i	+0,2056 − 1,3721i
5	+2,5874 + 0,0000i	+0,2063 + 1,3747i	+0,2063 − 1,3747i
6	+2,5874 + 0,0000i	+0,2063 + 1,3747i	+0,2063 − 1,3747i

Обратите внимание, что уравнение имеет один вещественный корень и одну пару комплексно-сопряженных корней, а сумма корней равна 3.

Вывод метода через метод Ньютона.

Для каждого n -кортежа комплексных чисел существует ровно один унитарный многочлен степени n , у которого они являются нулями (сохраняя кратность). Этот полином получается путем умножения всех соответствующих линейных коэффициентов, то есть

$g_{\vec {z}}(X)=(X-z_{1})\cdots (X-z_{n}).$

Этот полином имеет коэффициенты, зависящие от заданных нулей:

$g_{\vec {z}}(X)=X^{n}+g_{n-1}({\vec {z}})X^{n-1}+\cdots +g_{0}({\vec {z}}).$

Эти коэффициенты с точностью до знака представляют собой элементарные симметричные многочлены. $\alpha _{1}({\vec {z}}),\dots ,\alpha _{n}({\vec {z}})$ степеней 1,...,n .

Чтобы найти все корни заданного многочлена $f(X)=X^{n}+c_{n-1}X^{n-1}+\cdots +c_{0}$ с вектором коэффициентов $(c_{n-1},\dots ,c_{0})$ одновременно теперь то же самое, что найти вектор решения системы Виеты

${\begin{matrix}c_{0}&=&g_{0}({\vec {z}})&=&(-1)^{n}\alpha _{n}({\vec {z}})&=&(-1)^{n}z_{1}\cdots z_{n}\\c_{1}&=&g_{1}({\vec {z}})&=&(-1)^{n-1}\alpha _{n-1}({\vec {z}})\\&\vdots &\\c_{n-1}&=&g_{n-1}({\vec {z}})&=&-\alpha _{1}({\vec {z}})&=&-(z_{1}+z_{2}+\cdots +z_{n}).\end{matrix}}$

Метод Дюрана–Кернера получается как многомерный метод Ньютона, примененный к этой системе. Алгебраически удобнее рассматривать эти тождества коэффициентов как тождества соответствующих многочленов: $g_{\vec {z}}(X)=f(X)$. В методе Ньютона смотрят по некоторому начальному вектору ${\vec {z}}$, для вектора приращения ${\vec {w}}$ такой, что $g_{{\vec {z}}+{\vec {w}}}(X)=f(X)$ выполняется до членов второго и более высокого порядка приращения. Для этого решается тождество

$f(X)-g_{\vec {z}}(X)=\sum _{k=1}^{n}{\frac {\partial g_{\vec {z}}(X)}{\partial z_{k}}}w_{k}=-\sum _{k=1}^{n}w_{k}\prod _{j\neq k}(X-z_{j}).$

Если числа $z_{1},\dots ,z_{n}$ попарно различны, то многочлены в терминах правой части образуют базис n -мерного пространства $\mathbb {C} [X]_{n-1}$ полиномов максимальной степени n − 1. Таким образом, решение ${\vec {w}}$ в этом случае существует уравнение приращения. Координаты приращения ${\vec {w}}$ просто получаются путем вычисления уравнения приращения

$-\sum _{k=1}^{n}w_{k}\prod _{j\neq k}(X-z_{j})=f(X)-\prod _{j=1}^{n}(X-z_{j})$

в точках $X=z_{k}$, что приводит к

$-w_{k}\prod _{j\neq k}(z_{k}-z_{j})=-w_{k}g_{\vec {z}}'(z_{k})=f(z_{k})$, то есть $w_{k}=-{\frac {f(z_{k})}{\prod _{j\neq k}(z_{k}-z_{j})}}.$

Корневое включение через круги Гершгорина

В фактор-кольце (алгебре) классов вычетов по модулю ƒ( X ) умножение на X определяет эндоморфизм , который имеет нули ƒ( X ) в качестве собственных значений с соответствующими кратностями. Выбирая базис, оператор умножения представляется его матрицей коэффициентов A , сопутствующей матрицей ƒ( X ) для этого базиса.

Поскольку каждый многочлен можно привести по модулю ƒ( X ) к многочлену степени n - 1 или ниже, пространство классов вычетов можно отождествить с пространством многочленов степени, ограниченной n - 1. Основу конкретной задачи можно взять из интерполяции Лагранжа как набора из n полиномов.

$b_{k}(X)=\prod _{1\leq j\leq n,\;j\neq k}(X-z_{j}),\quad k=1,\dots ,n,$

где $z_{1},\dots ,z_{n}\in \mathbb {C}$ — попарно различные комплексные числа. Обратите внимание, что функции ядра для интерполяции Лагранжа: $L_{k}(X)={\frac {b_{k}(X)}{b_{k}(z_{k})}}$.

Для оператора умножения, примененного к базисным полиномам, из интерполяции Лагранжа получается

$X\cdot b_{k}(X)\mod f(X)=X\cdot b_{k}(X)-f(X)$	$=\sum _{j=1}^{n}{\Big (}z_{j}\cdot b_{k}(z_{j})-f(z_{j}){\Big )}\cdot {\frac {b_{j}(X)}{b_{j}(z_{j})}}$
	$=z_{k}\cdot b_{k}(X)+\sum _{j=1}^{n}w_{j}\cdot b_{j}(X)$,

где $w_{j}=-{\frac {f(z_{j})}{b_{j}(z_{j})}}$ снова обновления Вейерштрасса.

Таким образом, сопутствующая матрица ƒ( X ) равна

$A=\mathrm {diag} (z_{1},\dots ,z_{n})+{\begin{pmatrix}1\\\vdots \\1\end{pmatrix}}\cdot \left(w_{1},\dots ,w_{n}\right).$

Из транспонированного матричного случая теоремы Гершгорина об окружности следует, что все собственные значения A , то есть все корни ƒ( X ), содержатся в объединении дисков $D(a_{k,k},r_{k})$ с радиусом $r_{k}=\sum _{j\neq k}{\big |}a_{j,k}{\big |}$.

Здесь есть $a_{k,k}=z_{k}+w_{k}$, поэтому центры — это следующие итерации итерации Вейерштрасса, а радиусы $r_{k}=(n-1)\left|w_{k}\right|$ это кратно обновлениям Вейерштрасса. Если все корни ƒ( X ) хорошо изолированы (относительно точности вычислений) и точки $z_{1},\dots ,z_{n}\in \mathbb {C}$ являются достаточно близкими приближениями к этим корням, то все диски станут непересекающимися, так что каждый из них будет содержать ровно один нуль. Середины кругов будут лучшим приближением нулей.

Каждая сопряженная матрица $TAT^{-1}$ A X также является сопутствующей матрицей ƒ( ) . Выбор T в качестве диагональной матрицы оставляет структуру A инвариантной. Корень рядом с $z_{k}$ содержится в любом изолированном круге с центром $z_{k}$ независимо Т. от Выбор оптимальной диагональной матрицы T для каждого индекса приводит к лучшим оценкам (см. Petkovic et al. 1995).

Результаты конвергенции

Связь между разложением в ряд Тейлора и методом Ньютона предполагает, что расстояние от $z_{k}+w_{k}$ соответствующему корню имеет порядок $O{\big (}|w_{k}|^{2}{\big )}$, если корень хорошо изолирован от соседних корней и аппроксимация достаточно близка к корню. Итак, после того, как приближение близко, метод Ньютона сходится квадратично ; то есть ошибка возводится в квадрат на каждом шаге (что значительно уменьшает ошибку, если она становится меньше 1). В случае метода Дюрана–Кернера сходимость является квадратичной, если вектор ${\vec {z}}=(z_{1},\dots ,z_{n})$ близко к некоторой перестановке вектора корней f .

Для вывода о линейной сходимости есть более конкретный результат (см. Петкович и др., 1995). Если исходный вектор ${\vec {z}}$ и его вектор обновлений Вейерштрасса ${\vec {w}}=(w_{1},\dots ,w_{n})$ удовлетворяет неравенству

$\max _{1\leq k\leq n}|w_{k}|\leq {\frac {1}{5n}}\min _{1\leq j<k\leq n}|z_{k}-z_{j}|,$

то это неравенство справедливо и для всех итераций, всех дисков включения $D{\big (}z_{k}+w_{k},(n-1)|w_{k}|{\big )}$ не пересекаются, и имеет место линейная сходимость с коэффициентом сжатия 1/2. Кроме того, диски включения в этом случае можно выбрать как

$D\left(z_{k}+w_{k},{\tfrac {1}{4}}|w_{k}|\right),\quad k=1,\dots ,n,$

каждый из которых содержит ровно один ноль f .

Неудачная общая конвергенция

Метод Вейерштрасса/Дюрана-Кернера не является вообще сходящимся: другими словами, неверно, что для каждого многочлена набор начальных векторов, который в конечном итоге сходится к корням, открыт и плотен. Фактически, существуют открытые множества полиномов, которые имеют открытые множества начальных векторов, сходящихся к периодическим циклам, отличным от корней (см. Рейнке и др.).

Ссылки

• Вейерштрасс, Карл (1891). «Новое доказательство теоремы о том, что всякую целую рациональную функцию переменной можно представить в виде произведения линейных функций одной и той же переменной» . Отчеты о заседаниях Королевской прусской академии наук в Берлине . Архивировано из оригинала 2 ноября 2013 г. Проверено 31 октября 2013 г.
• Дюран, Э. (1960). «Уравнения типа F ( x ) = 0: корни многочлена». В Массоне; и др. (ред.). Численные решения алгебраических уравнений . Полет. 1.
• Кернер, Иммо О. (1966). «Общий пошаговый метод вычисления нулей многочленов». Численная математика . 8 (3): 290–294. дои : 10.1007/BF02162564 . S2CID   115307022 .
• Прешич, Марика (1980). «Теорема сходимости метода одновременного определения всех нулей многочлена» (PDF) . Публикации Математического института . Новая серия. 28 (42): 158–168.
• Петкович М.С., Карстенсен К. и Трайкович М. (1995). «Формула Вейерштрасса и методы поиска нуля». Числовая математика . 69 (3): 353–372. CiteSeerX   10.1.1.53.7516 . дои : 10.1007/s002110050097 . S2CID   18594004 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Бо Якоби, Нулевые точки для полиномов , CAE-nyt (периодическое издание Dansk CAE Group [Датская группа CAE]), 1988.
• Агнета Кнудсен, Численные методы (конспекты лекций), Копенгагенский технический университет.
• Бо Якоби, Численное решение уравнений , Статические уведомления о строительстве (Опубликовано Датским обществом структурных наук и инженерии), том 63, вып. 3–4, 1992, стр. 83–105.
• Гурдон, Ксавье (1996). Комбинаторика, алгоритмика и геометрия многочленов . Париж: Политехническая школа. Архивировано из оригинала 28 октября 2006 г. Проверено 22 августа 2006 г.
• Виктор Пэн (май 2002 г.): Поиск корня одномерного полинома с более низкой вычислительной точностью и более высокой скоростью сходимости . Технический отчет, Городской университет Нью-Йорка
• Ноймайер, Арнольд (2003). «Включающие кластеры нулей многочленов» . Журнал вычислительной и прикладной математики . 156 (2): 389–401. Бибкод : 2003JCoAM.156..389N . дои : 10.1016/S0377-0427(03)00380-7 .
• Ян Вершельде, Метод Вейерштрасса (также известный как метод Дюрана-Кернера) , 2003.
• Бернхард Рейнке, Дирк Шляйхер и Михаэль Столл, « Искатель корней Вейерштрасса в целом не сходится » , 2020 г.

Внешние ссылки

• Ada Generic_Roots с использованием метода Дюрана-Кернера (архив) — реализация с открытым исходным кодом в Ada.
• Полиномиальные корни - реализация с открытым исходным кодом на Java.
• Извлечение корней из полиномов: метод Дюрана – Кернера - содержит Java-апплета. демонстрацию