Метод Дюрана – Кернера - Durand–Kerner method

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

ж(Икс) = 0,

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

Объяснение

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

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

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

для всех Икс.

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

Пусть (комплексные) числа п, Q, р, S быть корнями этого многочлена ж.

потом

{displaystyle f (x) = (x-P) (x-Q) (x-R) (x-S)}

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

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

Так что если использовать как фиксированная точка итерация

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

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

Кроме того, если заменить нули Q, р и Sприближениями q ≈ Q, р ≈ р, s ≈ S, так что q, р, s не равны п, тогда постается неподвижной точкой возмущенной итерации с фиксированной точкой

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

поскольку

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

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

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

Инициализировать п, q, р, s:

п₀ := (0.4 + 0.9я)⁰,

q₀ := (0.4 + 0.9я)¹,

р₀ := (0.4 + 0.9я)²,

s₀ := (0.4 + 0.9я)³.

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

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

{displaystyle 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})}},}

{displaystyle 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})}},}

{displaystyle 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})}},}

{displaystyle 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})}}.}

Повторяйте до тех пор, пока числа п, q, р, sпо существу перестают изменяться относительно желаемой точности. Затем они принимают значения п, Q, р, S в каком-то порядке и с выбранной точностью. Итак, проблема решена.

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

Вариации

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

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

они находятся внутри некоторого не слишком большого круга, содержащего также корни ж(Икс), например круг вокруг начала координат с радиусом ${displaystyle 1 + max {ig (} | a |, | b |, | c |, | d | {ig)}}$ , (где 1, а, б, c, d являются коэффициентами при ж(Икс))

и это

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

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

Если коэффициенты действительные и степень многочлена нечетная, то он должен иметь хотя бы один действительный корень. Чтобы найти это, используйте реальное значение п₀ как первоначальное предположение и сделать q₀ и р₀, так далее., комплексно сопряженный пары. Тогда итерация сохранит эти свойства; то есть, п_п всегда будет реальным, и q_п и р_пи т. д. всегда будут сопряженными. Таким образом, п_п сведется к настоящему корню п. Или же сделайте все первоначальные предположения реальностью; они останутся такими.

Пример

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

it.-no.	п	q	р
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.

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

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

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

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

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

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

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

{displaystyle {egin {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}}}

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

{displaystyle 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 _ {jeq k} (X-z_ {j}).}

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

{displaystyle -sum _ {k = 1} ^ {n} w_ {k} prod _ {jeq k} (X-z_ {j}) = f (X) -prod _ {j = 1} ^ {n} ( X-z_ {j})}

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

{displaystyle -w_ {k} prod _ {jeq k} (z_ {k} -z_ {j}) = - w_ {k} g_ {vec {z}} '(z_ {k}) = f (z_ {k })}

, то есть

{displaystyle w_ {k} = - {frac {f (z_ {k})} {prod _ {jeq k} (z_ {k} -z_ {j})}}.}.

Включение корня через круги Гершгорина

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

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

{displaystyle b_ {k} (X) = prod _ {1leq jleq n,; jeq k} (X-z_ {j}), quad k = 1, dots, n,}

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

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

${displaystyle Xcdot b_ {k} (X) mod f (X) = Xcdot b_ {k} (X) -f (X)}$	${displaystyle = 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})}}}$
	${displaystyle = z_ {k} cdot b_ {k} (X) + sum _ {j = 1} ^ {n} w_ {j} cdot b_ {j} (X)}$ ,

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

Сопутствующая матрица ƒ (Икс) следовательно является

{displaystyle A = mathrm {diag} (z_ {1}, точки, z_ {n}) + {egin {pmatrix} 1 vdots 1end {pmatrix}} cdot left (w_ {1}, dots, w_ {n}) ight).}

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

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

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

Результаты сходимости

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

Для вывода о линейной сходимости есть более конкретный результат (см. Ссылку Petkovic et al. 1995). Если исходный вектор ${displaystyle {vec {z}}}$ и его вектор обновлений Weierstrass ${displaystyle {vec {w}} = (w_ {1}, точки, w_ {n})}$ удовлетворяет неравенству

{displaystyle max _ {1leq kleq n} | w_ {k} | leq {frac {1} {5n}} min _ {1leq j

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

{displaystyle Dleft (z_ {k} + w_ {k}, {frac {1} {4}} | w_ {k} | ight), quad k = 1, dots, n,}

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

Отсутствие общей конвергенции

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

внешняя ссылка

Ada Generic_Roots с использованием метода Дюрана – Кернера - ан Открытый исходный код реализация в Ада
Полиномиальные корни - ан Открытый исходный код реализация в Ява
Извлечение корней из многочленов: метод Дюрана – Кернера - содержит Java-апплет демонстрация

[Petković-1] Петкович, Миодраг (1989). Итерационные методы одновременного включения нулей полиномов. Берлин [u.a.]: Springer. С. 31–32. ISBN 978-3-540-51485-5.

[1]