Метод Бэрстова - Википедия - Bairstows method

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

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

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

Подход Бэрстоу заключается в использовании Метод Ньютона для настройки коэффициентов ты и v в квадратичный пока его корни не станут также корнями решаемого многочлена. Затем можно определить корни квадратичного уравнения, а полином можно разделить на квадратичный, чтобы исключить эти корни. Затем этот процесс повторяется до тех пор, пока многочлен не станет квадратичным или линейным, и все корни не будут определены.

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

к дает частное и остаток такой, что

Второй дивизион к выполняется для получения частного и остальное с

Переменные , а являются функциями и . Их можно найти рекурсивно следующим образом.

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

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

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

Пример

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

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

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

Итерационные шаги метода Бэрстоу
тыvдлина шагакорни
01.833333333333−5.5000000000005.579008780071−0.916666666667±2.517990821623
12.979026068546−0.0398967844382.048558558641−1.489513034273±1.502845921479
23.6353060530911.9006930099461.799922838287−1.817653026545±1.184554563945
33.0649380397610.1935308755381.256481376254−1.532469019881±1.467968126819
43.4618341912321.3856797311010.428931413521−1.730917095616±1.269013105052
53.3262443865650.9787429271920.022431883898−1.663122193282±1.336874153612
63.3333409093511.0000227011470.000023931927−1.666670454676±1.333329555414
73.3333333333401.0000000000200.000000000021−1.666666666670±1.333333333330
83.3333333333331.0000000000000.000000000000−1.666666666667±1.333333333333

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

Спектакль

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

Bairstow-фрактал 1 0 0 0 0 m1 scale 03.pngБэрстов-фрактал 1 0 0 0 0 m1 0 scale 3.pngBairstow-фрактал 6 11 m33 m33 11 6 масштаб 03.png

Изображения представляют пары . Очки в верхней полуплоскости т > 0 соответствуют линейному множителю с корнями , то есть . Очки в нижней полуплоскости т <0 соответствуют квадратичным множителям с корнями , то есть, так что в целом . Точки окрашены в соответствии с последней точкой итерации Бэрстоу, черные точки указывают на расходящееся поведение.

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

Ссылка

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

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