Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В численном анализе метод Бейрстоу — это эффективный алгоритм для нахождения корней вещественного многочлена любой степени. Алгоритм впервые был представлен в приложении к книге Леонарда Бейрстоу «Прикладная аэродинамика», опубликованной в 1920 году. Алгоритм находит корни в виде комплексно сопряжённых пар, используя только операции с вещественными числами. Подробнее о других алгоритмах см. в статье «Алгоритм поиска корней».
In numerical analysis, Bairstow's method is an efficient algorithm for finding the roots of a real polynomial of arbitrary degree. The algorithm first appeared in the appendix of the 1920 book Applied Aerodynamics by Leonard Bairstow. The algorithm finds the roots in complex conjugate pairs using only real arithmetic. See root finding algorithm for other algorithms.
Выступление
Алгоритм Бейрстоу наследует локальную квадратичную сходимость метода Ньютона, за исключением случая квадратичных факторов кратности выше 1, когда сходимость к этому фактору становится линейной. Особый вид неустойчивости наблюдается, когда полином имеет нечетную степень и только один вещественный корень. Квадратичные факторы, имеющие небольшое значение в этой точке, склонны расходиться к бесконечности. Изображения представляют собой пары точек: точки в верхней полуплоскости t > 0 соответствуют линейному фактору с корнями , то есть, точки в нижней полуплоскости t < 0 соответствуют квадратичным факторам с корнями , то есть , поэтому в целом точки окрашены в соответствии с конечной точкой итерации Бейрстоу, а черные точки указывают на расходящееся поведение. Первое изображение демонстрирует случай с единственным вещественным корнем. Второе показывает, что расходящееся поведение можно устранить, введя дополнительный вещественный корень, но это замедляет скорость сходимости. Также, в случае полиномов нечетной степени, можно сначала найти вещественный корень, используя метод Ньютона и/или метод сужения интервала, чтобы после понижения степени остался полином четной степени, демонстрирующий более устойчивое поведение. Третье изображение соответствует приведенному выше примеру.
Bairstow's algorithm inherits the local quadratic convergence of Newton's method, except in the case of quadratic factors of multiplicity higher than 1, when convergence to that factor is linear. A particular kind of instability is observed when the polynomial has odd degree and only one real root. Quadratic factors that have a small value at this real root tend to diverge to infinity. The images represent pairs Points in the upper half plane t > 0 correspond to a linear factor with roots , that is Points in the lower half plane t < 0 correspond to quadratic factors with roots , that is, , so in general Points are colored according to the final point of the Bairstow iteration, black points indicate divergent behavior. The first image is a demonstration of the single real root case. The second indicates that one can remedy the divergent behavior by introducing an additional real root, at the cost of slowing down the speed of convergence. One can also in the case of odd degree polynomials first find a real root using Newton's method and/or an interval shrinking method, so that after deflation a better behaved even degree polynomial remains. The third image corresponds to the example above.