Algoritmo di Bairstow

Da Wikipedia, l'enciclopedia libera.

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

Descrizione del metodo[modifica | modifica sorgente]

L'approccio di Bairstow consiste nell'utilizzare il metodo delle tangenti per modificare i coefficienti u ev 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 della 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 variabilic,\,d,\,g,\,h, e le  \{b_i\},\;\{f_i\} sono funzioni di u e v. Si possono calcolare ricorsivamente nel modo seguente:

\begin{align}
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{align}

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[modifica | modifica sorgente]

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.

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]