Algoritm Bairstow

În matematică , în special în analiza numerică , metoda lui Bairstow este un algoritm eficient pentru găsirea rădăcinilor unui polinom real de grad arbitrar. Primul algoritm a apărut ca o apendice la cartea lui Leonard Bairstow, Aerodinamica aplicată , publicată în 1920 . Algoritmul localizează rădăcinile în perechi conjugate complexe folosind doar aritmetică reală.

Descrierea metodei

Abordarea lui Bairstow constă în aplicarea metodei tangente pentru a modifica coeficienții $tu$ ${\ displaystyle u}$ $tu$ Și $v$ ${\ displaystyle v}$ $v$ în ecuația de gradul doi $x^{2}+ux+v=0$ ${\ displaystyle x ^ {2} + ux + v = 0}$ ${\ displaystyle x ^ {2} + ux + v = 0}$ până când rădăcinile acestei ecuații coincid cu rădăcinile polinomului de rezolvat. Rădăcinile ecuației pot fi apoi ușor calculate și polinomul inițial poate fi împărțit la polinomul de gradul doi pentru a elimina acele rădăcini. Acest proces este apoi iterat pentru a găsi toate celelalte rădăcini ale polinomului de pornire.

Prin împărțirea polinomului care trebuie luat în considerare,

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

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

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

pentru $x^{2}+ux+v$ ${\ displaystyle x ^ {2} + ux + v}$ ${\ displaystyle x ^ {2} + ux + v}$ , veți obține un coeficient $Q(x)=\sum _{i=0}^{n-2}b_{i}x^{i}$ ${\ displaystyle Q (x) = \ sum _ {i = 0} ^ {n-2} b_ {i} x ^ {i}}$ ${\ displaystyle Q (x) = \ sum _ {i = 0} ^ {n-2} b_ {i} x ^ {i}}$ și o odihnă $cx+d$ ${\ displaystyle cx + d}$ ${\ displaystyle cx + d}$ astfel încât

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

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

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

Apoi se împarte $Q(x)$ ${\ displaystyle Q (x)}$ $Q (x)$ pentru $x^{2}+ux+v$ ${\ displaystyle x ^ {2} + ux + v}$ ${\ displaystyle x ^ {2} + ux + v}$ , obținerea unui coeficient $R(x)=\sum _{i=0}^{n-4}f_{i}x^{i}$ ${\ displaystyle R (x) = \ sum _ {i = 0} ^ {n-4} f_ {i} x ^ {i}}$ ${\ displaystyle R (x) = \ sum _ {i = 0} ^ {n-4} f_ {i} x ^ {i}}$ și o odihnă $gx+h$ ${\ displaystyle gx + h}$ ${\ displaystyle gx + h}$ cu

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

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

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

Variabilele $c,\,d,\,g,\,h$ ${\ displaystyle c, \, d, \, g, \, h}$ ${\ displaystyle c, \, d, \, g, \, h}$ , si $\{b_{i}\},\;\{f_{i}\}$ ${\ displaystyle \ {b_ {i} \}, \; \ {f_ {i} \}}$ ${\ displaystyle \ {b_ {i} \}, \; \ {f_ {i} \}}$ sunt funcții ale $tu$ ${\ displaystyle u}$ $tu$ Și $v$ ${\ displaystyle v}$ $v$ . Acestea pot fi calculate recursiv după cum urmează:

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

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

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

Polinomul pătratic se divide $P(x)$ ${\ displaystyle P (x)}$ $P (x)$ de sine

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

{\ displaystyle c (u, v) = d (u, v) = 0.}

{\ displaystyle c (u, v) = d (u, v) = 0.}

Puteți găsi valori de $tu$ ${\ displaystyle u}$ $tu$ Și $v$ ${\ displaystyle v}$ $v$ care satisfac aceste condiții luând valori de pornire și iterând metoda lui Newton în două dimensiuni

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

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

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

până când metoda converge.

Această metodă de găsire a zerourilor polinoamelor poate fi ușor implementată cu un limbaj de programare sau cu o foaie de calcul.

Exemplu

Determinați rădăcinile polinomului $f(x)=6\,x^{5}+11\,x^{4}-33\,x^{3}-33\,x^{2}+11\,x+6.$ ${\ displaystyle f (x) = 6 \, x ^ {5} +11 \, x ^ {4} -33 \, x ^ {3} -33 \, x ^ {2} +11 \, x + 6 .}$ ${\ displaystyle f (x) = 6 \, x ^ {5} +11 \, x ^ {4} -33 \, x ^ {3} -33 \, x ^ {2} +11 \, x + 6 .}$ Ca primul polinom pătratic puteți alege polinomul normalizat format din primii trei coeficienți ai $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ .

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

Iterația produce valorile

Etape de iterație ale metodei Bairstow
Nr	tu	v	lungimea pasului	rădăcini
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

După opt iterații, metoda a produs un polinom pătratic cu rădăcini cu care în figurile reprezentate coincid $-1/3$ ${\ displaystyle -1/3}$ $-1/3$ Și $-3$ ${\ displaystyle -3}$ $-3$ . Lungimea pașilor care urmează a patra iterație arată că viteza de convergență este mai mult decât liniară.

Elemente conexe

linkuri externe

Algoritmul lui Bairstow pe Mathworld , la mathworld.wolfram.com .
Rețete numerice în Fortran 77 online , la library.lanl.gov .
Exemplu de rezolvare a rădăcinilor polinomiale (deg (P) ≤10) folosind metoda Bairstow , la polarhome.com:793 . Adus la 27 iulie 2012 (arhivat din original la 3 iulie 2007) .
LinBairstowSolve, o implementare open source C ++ a metodei Lin-Bairstow disponibilă ca metodă a bibliotecii VTK , la vtk.org .
Descoperirea online a rădăcinii unui polinom - metoda lui Bairstow de către Farhad Mazlumi

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică