Algoritmo di Bairstow

In matematica, in particolare in analisi numerica, il metodo di Bairstow è un algoritmo efficiente per trovare le radici di un polinomio reale di grado arbitrario. Il primo algoritmo è apparso in appendice al libro Aerodinamica Applicata di Leonard Bairstow, pubblicato nel 1920. L'algoritmo individua le radici in coppie complesse coniugate utilizzando solo l'aritmetica reale.

Descrizione del metodo

L'approccio di Bairstow consiste nell'applicare il metodo delle tangenti per modificare i coefficienti $u$ e $v$ nell'equazione di secondo grado $x^{2}+ux+v=0$ fino a quando le radici di quest'equazione coincidano con le radici del polinomio da risolvere. Le radici dell'equazione possono quindi essere facilmente calcolate e il polinomio di partenza può essere diviso per il polinomio di secondo grado per eliminare quelle radici. Questo processo viene quindi iterato per trovare tutte le altre radici del polinomio di partenza.

Dividendo il polinomio da fattorizzare,

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

per $x^{2}+ux+v$, si ottiene un quoziente $Q(x)=\sum _{i=0}^{n-2}b_{i}x^{i}$ e un resto $cx+d$ tali che

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

Si divide poi $Q(x)$ per $x^{2}+ux+v$, ottenendo un quoziente $R(x)=\sum _{i=0}^{n-4}f_{i}x^{i}$ e un resto $gx+h$ con

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

Le variabili $c,\,d,\,g,\,h$, e le $\{b_{i}\},\;\{f_{i}\}$ sono funzioni di $u$ e $v$. Si possono calcolare ricorsivamente nel modo seguente:

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

Il polinomio quadratico divide $P(x)$ se

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

Si possono trovare valori di $u$ e $v$ che soddisfano queste condizioni prendendo dei valori di partenza e iterando il metodo di Newton in due dimensioni

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

fino a quando il metodo converge.

Questo metodo per trovare gli zeri dei polinomi può essere facilmente implementato con un linguaggio di programmazione o con un foglio di calcolo.

Esempio

Determinare le radici del polinomio $f(x)=6\,x^{5}+11\,x^{4}-33\,x^{3}-33\,x^{2}+11\,x+6.$ Come primo polinomio quadratico si può scegliere il polinomio normalizzato formato dai primi tre coefficienti di $f(x)$.

$u={\frac {a_{n-1}}{a_{n}}}={\frac {11}{6}};\quad v={\frac {a_{n-2}}{a_{n}}}=-{\frac {33}{6}}.$

L'iterazione produce i valori

Iteration steps of Bairstow's method

Nr	u	v	step length	roots
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

Dopo otto iterazioni il metodo ha prodotto un polinomio quadratico con radici che nelle cifre rappresentate coincidono con $-1/3$ e $-3$. La lunghezza dei passi successivi alla quarta iterazione mostra che la velocità di convergenza è più che lineare.

Voci correlate

• Leonard Bairstow
• Metodo delle tangenti

Collegamenti esterni

• (EN) Eric W. Weisstein, Algoritmo di Bairstow, su MathWorld, Wolfram Research.
• Numerical Recipes in Fortran 77 Online, su library.lanl.gov.
• Example polynomial root solver (deg(P)≤10) using Bairstow's Method, su polarhome.com:793. URL consultato il 27 luglio 2012 (archiviato dall'url originale il 3 luglio 2007).
• LinBairstowSolve, an open-source C++ implementation of the Lin-Bairstow method available as a method of the VTK library, su vtk.org.
• Online root finding of a polynomial-Bairstow's method by Farhad Mazlumi