Метод Бэрстовса - Bairstows method

В числовой анализ, Метод Бэрстова эффективный алгоритм для поиска корни настоящего многочлен произвольной степени. Алгоритм впервые появился в приложении к книге 1920 г. Прикладная аэродинамика к Леонард Бэрстоу.^{[1][неосновной источник необходим ]} Алгоритм находит корни в комплексно сопряженный пары, использующие только реальную арифметику.

Видеть алгоритм поиска корней для других алгоритмов.

Описание метода

Подход Бэрстоу заключается в использовании Метод Ньютона для настройки коэффициентов ты и v в квадратичный ${\displaystyle x^{2}+ux+v}$ пока его корни не станут также корнями решаемого многочлена. Затем можно определить корни квадратичного уравнения, а полином можно разделить на квадратичный, чтобы исключить эти корни. Затем этот процесс повторяется до тех пор, пока многочлен не станет квадратичным или линейным, и все корни не будут определены.

Длинное деление решаемого многочлена

${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}$

к ${\displaystyle x^{2}+ux+v}$ дает частное ${\displaystyle Q(x)=\sum _{i=0}^{n-2}b_{i}x^{i}}$ и остаток ${\displaystyle cx+d}$ такой, что

${\displaystyle P(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-2}b_{i}x^{i}\right)+(cx+d).}$

Второй дивизион ${\displaystyle Q(x)}$ к ${\displaystyle x^{2}+ux+v}$ выполняется для получения частного ${\displaystyle R(x)=\sum _{i=0}^{n-4}f_{i}x^{i}}$ и остальное ${\displaystyle gx+h}$ с

${\displaystyle Q(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-4}f_{i}x^{i}\right)+(gx+h).}$

Переменные ${\displaystyle c,\,d,\,g,\,h}$, а ${\displaystyle \{b_{i}\},\;\{f_{i}\}}$ являются функциями ${\displaystyle u}$ и ${\displaystyle v}$. Их можно найти рекурсивно следующим образом.

${\displaystyle {\begin{aligned}b_{n}&=b_{n-1}=0,&f_{n}&=f_{n-1}=0,\\b_{i}&=a_{i+2}-ub_{i+1}-vb_{i+2}&f_{i}&=b_{i+2}-uf_{i+1}-vf_{i+2}\qquad (i=n-2,\ldots ,0),\\c&=a_{1}-ub_{0}-vb_{1},&g&=b_{1}-uf_{0}-vf_{1},\\d&=a_{0}-vb_{0},&h&=b_{0}-vf_{0}.\end{aligned}}}$

Квадратичная без остатка делит многочлен, когда

${\displaystyle c(u,v)=d(u,v)=0.\,}$

Ценности ${\displaystyle u}$ и ${\displaystyle v}$ для которого это происходит, можно обнаружить, выбрав начальные значения и повторяя метод Ньютона в двух измерениях.

${\displaystyle {\begin{bmatrix}u\\v\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\begin{bmatrix}{\frac {\partial c}{\partial u}}&{\frac {\partial c}{\partial v}}\\[3pt]{\frac {\partial d}{\partial u}}&{\frac {\partial d}{\partial v}}\end{bmatrix}}^{-1}{\begin{bmatrix}c\\d\end{bmatrix}}:={\begin{bmatrix}u\\v\end{bmatrix}}-{\frac {1}{vg^{2}+h(h-ug)}}{\begin{bmatrix}-h&g\\[3pt]-gv&gu-h\end{bmatrix}}{\begin{bmatrix}c\\d\end{bmatrix}}}$

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

Пример

Задача - определить пару корней многочлена

${\displaystyle f(x)=6\,x^{5}+11\,x^{4}-33\,x^{3}-33\,x^{2}+11\,x+6.}$

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

${\displaystyle u={\frac {a_{n-1}}{a_{n}}}={\frac {11}{6}};\quad v={\frac {a_{n-2}}{a_{n}}}=-{\frac {33}{6}}.\,}$

Затем итерация создает таблицу

Итерационные шаги метода Бэрстоу

№	ты	v	длина шага	корни
0	1.833333333333	−5.500000000000	5.579008780071	−0.916666666667±2.517990821623
1	2.979026068546	−0.039896784438	2.048558558641	−1.489513034273±1.502845921479
2	3.635306053091	1.900693009946	1.799922838287	−1.817653026545±1.184554563945
3	3.064938039761	0.193530875538	1.256481376254	−1.532469019881±1.467968126819
4	3.461834191232	1.385679731101	0.428931413521	−1.730917095616±1.269013105052
5	3.326244386565	0.978742927192	0.022431883898	−1.663122193282±1.336874153612
6	3.333340909351	1.000022701147	0.000023931927	−1.666670454676±1.333329555414
7	3.333333333340	1.000000000020	0.000000000021	−1.666666666670±1.333333333330
8	3.333333333333	1.000000000000	0.000000000000	−1.666666666667±1.333333333333

После восьми итераций метод произвел квадратный множитель, который содержит корни -1/3 и -3 в пределах представленной точности. Длина шага с четвертой итерации демонстрирует сверхлинейную скорость сходимости.

Спектакль

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

${\displaystyle f(x)=x^{5}-1}$	${\displaystyle f(x)=x^{6}-x}$	${\displaystyle {\begin{aligned}f(x)=&6x^{5}+11x^{4}-33x^{3}\\&-33x^{2}+11x+6\end{aligned}}}$

Изображения представляют пары ${\displaystyle (s,t)\in [-3,3]^{2}}$. Очки в верхней полуплоскости т > 0 соответствуют линейному множителю с корнями ${\displaystyle s\pm it}$, то есть ${\displaystyle x^{2}+ux+v=(x-s)^{2}+t^{2}}$. Очки в нижней полуплоскости т <0 соответствуют квадратичным множителям с корнями ${\displaystyle s\pm t}$, то есть, ${\displaystyle x^{2}+ux+v=(x-s)^{2}-t^{2}}$так что в целом ${\displaystyle (u,\,v)=(-2s,\,s^{2}+t\,|t|)}$. Точки окрашены в соответствии с последней точкой итерации Бэрстоу, черные точки указывают на расходящееся поведение.

Первое изображение является демонстрацией единственного реального корневого случая. Второй указывает на то, что можно исправить расходящееся поведение, введя дополнительный действительный корень, за счет снижения скорости сходимости. В случае многочленов нечетной степени можно сначала найти действительный корень, используя метод Ньютона и / или метод сокращения интервала, так что после дефляции остается полином четной степени с лучшим поведением. Третье изображение соответствует приведенному выше примеру.

Ссылка

1. Бэрстоу, Леонард (1920). «Приложение: Решение алгебраических уравнений с числовыми коэффициентами в случае, когда существует несколько пар комплексных корней». Прикладная аэродинамика. Лондон: Longmans, Green and Company. С. 551–560.

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

• Алгоритм Бэрстоу на Mathworld
• Числовые рецепты в Fortran 77 Online
• Пример полиномиального корневого решателя (deg (п) ≤ 10) методом Бэрстова
• LinBairstowSolve, реализация метода Lin-Bairstow с открытым исходным кодом на C ++, доступная как метод библиотеки VTK.
• Онлайн-поиск корня многочлена - метод Бэрстова Фархад Мазлуми