Метод Бэрстоу

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

см. в разделе «Алгоритм поиска корня» Другие алгоритмы .

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

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

Полное деление полинома, который нужно решить

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

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

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

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

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

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

{\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}}

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

c(u,v)=d(u,v)=0.\,

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

{\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}}

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

Пример

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

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

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

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, когда сходимость к этому коэффициенту является линейной. Особый вид нестабильности наблюдается, когда многочлен имеет нечетную степень и только один действительный корень. Квадратичные коэффициенты, имеющие небольшое значение в этом действительном корне, имеют тенденцию расходиться до бесконечности.


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

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

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

Ссылки

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

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

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

[ 1 ]

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