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

$$P_n(z)=a_0+a_1z+\ldots+a_nz^n$$с комплексными коэффициентами, основанный на интерполяции многочленами $2$–й степени. Метод парабол позволяет найти все корни многочлена без предварительной информации о начальном приближении. Сходимость метода парабол установлена лишь эмпирически. Вблизи простого корня скорость сходимости близка к квадратичной.

Вычислительная схема метода парабол состоит в следующем. По произвольным комплексным числам $z_0$, $z_1$, $z_2$ как узлам интерполяции строится интерполяционный многочлен Лагранжа для $P_n(z)$. Это будет некоторый многочлен $2$–й степени. Находятся оба его корня и за $z_3$ берётся ближайший к $z_2$. После этого вместо точек $z_0$, $z_1$, $z_2$ берутся точки $z_1$, $z_2$, $z_3$ и процесс повторяется. Эмпирически установлено, что последовательность $z_0,z_1,z_2,z_3,\ldots$, построенная таким образом, сходится к корню многочлена. Вычисленный корень выделяется, и далее метод применяется к многочлену меньшей степени.

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

$$\begin{gathered}h=z-z_i, \quad h_i=z_i-z_{i-1}, \quad h_{i-1}=z_{i-1}-z_{i-2},\\ \lambda=h/h_i, \quad \lambda_i=h_i/h_{i-1}, \quad \delta_i=1+\lambda_i \end{gathered}$$интерполяционный многочлен Лагранжа имеет вид

$$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).$$Корни $L^{(i)}(\lambda)$ находятся по формуле

$$\lambda=\frac{-2P_n(z_i)\delta_i}{g_i\pm\sqrt{g_i^2-4 P_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)]}},$$где

$$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).$$Из двух возможных значений $\lambda$ берётся наименьшее по модулю и далее вычисляется

$$\lambda_{i+1}=\lambda;\quad h_{i+1}=\lambda_{i+1}h_i;\quad z_{i+1}=z_i+h_{i+1}.$$При реализации описанного процесса на ЭВМ возможно переполнение сверху и снизу при вычислении значения многочлена в точке. Появление больших чисел возможно также при вычислении корней многочлена $2$–й степени. Существует ряд приёмов, имеющих целью избежать этого явления (Воеводин. 1966; Бахвалов. 2021).