Метод парабол

Ме́тод пара́бол, метод вычисления корней многочлена

${\displaystyle P_{n}(z)=a_{0}+a_{1}z+\ldots +a_{n}z^{n}}$

с комплексными коэффициентами, основанный на интерполяции многочленами ${\displaystyle 2}$–й степени. Метод парабол позволяет найти все корни многочлена без предварительной информации о начальном приближении. Сходимость метода парабол установлена лишь эмпирически. Вблизи простого корня скорость сходимости близка к квадратичной.

Вычислительная схема метода парабол состоит в следующем. По произвольным комплексным числам ${\displaystyle z_{0}}$, ${\displaystyle z_{1}}$, ${\displaystyle z_{2}}$ как узлам интерполяции строится интерполяционный многочлен Лагранжа для ${\displaystyle P_{n}(z)}$. Это будет некоторый многочлен ${\displaystyle 2}$–й степени. Находятся оба его корня и за ${\displaystyle z_{3}}$ берётся ближайший к ${\displaystyle z_{2}}$. После этого вместо точек ${\displaystyle z_{0}}$, ${\displaystyle z_{1}}$, ${\displaystyle z_{2}}$ берутся точки ${\displaystyle z_{1}}$, ${\displaystyle z_{2}}$, ${\displaystyle z_{3}}$ и процесс повторяется. Эмпирически установлено, что последовательность ${\displaystyle z_{0},z_{1},z_{2},z_{3},\ldots }$, построенная таким образом, сходится к корню многочлена. Вычисленный корень выделяется, и далее метод применяется к многочлену меньшей степени.

Расчётные формулы метода парабол: если ${\displaystyle z_{i-2}}$, ${\displaystyle z_{i-1}}$, ${\displaystyle z_{i}}$ – исходная тройка чисел ${\displaystyle i}$–гo шага, то в обозначениях

${\displaystyle h=z-z_{i},\quad h_{i}=z_{i}-z_{i-1},\quad h_{i-1}=z_{i-1}-z_{i-2},}$
${\displaystyle lambda=h/h_{i},\quad \lambda _{i}=h_{i}/h_{i-1},\quad \delta _{i}=1+\lambda _{i}}$

интерполяционный многочлен Лагранжа имеет вид

${\displaystyle L^{(i)}(\lambda )=\lambda ^{2}\delta _{i}^{-1}[P_{n}(z_{i-2})\lambda _{i}^{2}-P_{n}(z_{i-1})\lambda _{i}\delta _{i}+P_{n}(z_{i})\lambda _{i}]+\ +\lambda \delta _{i}^{-1}[P_{n}(z_{i-2})\lambda _{i}^{2}-P_{n}(z_{i-1})\delta _{i}^{2}+\ +P_{n}(z_{i})(\lambda _{i}+\delta _{i})]+P_{n}(z_{i})}$.

Корни ${\displaystyle L^{(i)}(\lambda )}$ находятся по формуле

${\displaystyle \lambda ={\frac {-2P_{n}(z_{i})\delta _{i}}{g_{i}\pm {\sqrt {g_{i}^{2}-4P_{n}(z_{i})\delta _{i}\lambda _{i}[P_{n}(z_{i-2})\lambda _{i}-P_{n}(z_{i-1})\delta _{i}+P_{n}(z_{i})]}}}}}$,

где

${\displaystyle g_{i}=P_{n}(z_{i-2})\lambda _{i}^{2}-P_{n}(z_{i-1})\delta _{i}^{2}+P_{n}(z_{i})(\lambda _{i}+\delta _{i})}$.

Из двух возможных значений ${\displaystyle \lambda }$ берётся наименьшее по модулю и далее вычисляется

${\displaystyle \lambda _{i+1}=\lambda ;\quad h_{i+1}=\lambda _{i+1}h_{i};\quad z_{i+1}=z_{i}+h_{i+1}}$.

При реализации описанного процесса на ЭВМ возможно переполнение сверху и снизу при вычислении значения многочлена в точке. Появление больших чисел возможно также при вычислении корней многочлена ${\displaystyle 2}$–й степени. Существует ряд приёмов, имеющих целью избежать этого явления (Воеводин. 1966^[1]; Бахвалов. 2021^[2]).