metoda Bairstowa

W analizie numerycznej metoda Bairstowa jest skutecznym algorytmem znajdowania pierwiastków wielomianu rzeczywistego dowolnego stopnia. Algorytm pojawił się po raz pierwszy w dodatku do książki Applied Aerodynamics z 1920 roku autorstwa Leonarda Bairstowa . Algorytm znajduje pierwiastki w zespolonych parach koniugatów, używając tylko arytmetyki rzeczywistej.

Zobacz algorytm wyszukiwania korzeni dla innych algorytmów.

Opis metody

$aż jego$ Bairstow polega na użyciu Newtona do dostosowania współczynników u i v w kwadracie , rozwiązywanego wielomianu. Następnie można określić pierwiastki kwadratu, a wielomian można podzielić przez kwadrat, aby wyeliminować te pierwiastki. Proces ten jest następnie powtarzany, aż wielomian stanie się kwadratowy lub liniowy, a wszystkie pierwiastki zostaną określone.

Długie dzielenie wielomianu do rozwiązania

${\ Displaystyle P (x) = \ suma _ {i = 0} ^ {n} a_ {i} x ^ {i}}$

przez ${\ Displaystyle x ^ {2} + ux + v}$ daje iloraz ${\ Displaystyle Q (x) = \ suma _ {i = 0} ^ {n-2} b_ {i} x ^ {i}}$ i reszta taka, że ${\ displaystyle cx + d}$

${\ Displaystyle P (x) = (x ^ {2} + ux + v) \ lewo (\ suma _ {i = 0} ^ {n-2} b_ {i} x ^ {i} \ prawo) + ( cx+d).}$

Drugi podział przez ${\ Displaystyle Q (x)}$ przez ${\ Displaystyle x ^ {2} + ux + v}$ jest wykonywany w celu uzyskania ilorazu ${\ Displaystyle R (x) = \ suma _ {i = 0} ^ {n-4} f_ {i} x ^ {i}} i reszta sol x$ + $gx +h}$ z

${\ Displaystyle Q (x) = (x ^ {2} + ux + v) \ lewo (\ suma _ {i = 0} ^ {n-4} f_ {i} x ^ {i} \ prawo) + ( gx+h).}$

Zmienne ${\ Displaystyle c, \, d, \, g, \, h} i {$$\}, \;\ {f_ {i}\}}$ { są funkcjami ${\ displaystyle u}$ i ${\ displaystyle v}$ . Można je znaleźć rekurencyjnie w następujący sposób.

${\ Displaystyle {\ rozpocząć {wyrównane} 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{wyrównane}}}$

Kwadrat równomiernie dzieli wielomian kiedy

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

Wartości i , dla których to występuje $u}$$displaystyle$ wartości początkowe i iterując metodę Newtona w dwóch wymiarach u {\

${\ Displaystyle {\ rozpocząć {bmatrix} u \\ v \ koniec {bmatrix}}: = {\ rozpocząć {bmatrix} u \\ v\end{bmatrix}}-{\begin{bmatrix}{\frac {\częściowe c}{\częściowe u}}&{\frac {\częściowe c}{\częściowe v}}\\[3pt]{\ frac {\częściowe d}{\częściowe u}}&{\frac {\częściowe d}{\częściowe 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}}}$

aż nastąpi zbieżność. Ta metoda znajdowania zer wielomianów może być zatem łatwo zaimplementowana za pomocą języka programowania, a nawet arkusza kalkulacyjnego.

Przykład

Zadanie polega na wyznaczeniu pary pierwiastków wielomianu

${\ Displaystyle f (x) = 6 \, x ^ {5} + 11 \, x ^ {4 }-33\,x^{3}-33\,x^{2}+11\,x+6.}$

Jako pierwszy wielomian kwadratowy można wybrać wielomian znormalizowany utworzony z trzech wiodących współczynników f ( x ),

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

Następnie iteracja tworzy tabelę

Kroki iteracyjne metody Bairstowa

Nr	u	w	długość kroku	korzenie
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,3333333333330
8	3.333333333333	1.0000000000000	0,0000000000000	−1,666666666667±1,3333333333333

Po ośmiu iteracjach metoda dała współczynnik kwadratowy, który zawiera pierwiastki -1/3 i -3 w ramach reprezentowanej precyzji. Długość kroku od czwartej iteracji pokazuje nadliniową prędkość konwergencji.

Wydajność

Algorytm Bairstowa dziedziczy lokalną zbieżność kwadratową metody Newtona, z wyjątkiem przypadków czynników kwadratowych o krotności większej niż 1, gdy zbieżność do tego czynnika jest liniowa. Szczególny rodzaj niestabilności obserwuje się, gdy wielomian ma nieparzysty stopień i tylko jeden pierwiastek rzeczywisty. Czynniki kwadratowe, które mają małą wartość przy tym pierwiastku rzeczywistym, mają tendencję do rozchodzenia się do nieskończoności.

${\ Displaystyle f (x) = x ^ {5} -1}$	${\ Displaystyle f (x) = x ^ {6} -x}$	${\ Displaystyle {\ rozpocząć {wyrównane} f (x) = & 6x ^ {5} + 11x ^ {4} -33x^{3}\\&-33x^{2}+11x+6\end{wyrównane}}}$

Obrazy przedstawiają pary ${\ Displaystyle (s, t) \ w [-3,3] ^ {2}}$ . Punkty w górnej połowie płaszczyzny ${$ > 0 $odpowiadają$ czynnikowi liniowemu z czyli . Punkty w dolnej połowie płaszczyzny t <0 odpowiadają czynnikom kwadratowym z $+$ x $\$ , więc ogólnie ${\ Displaystyle (u,\,v)=(-2s,\,s^{2}+t\,|t|)}$ . Punkty są kolorowe zgodnie z końcowym punktem iteracji Bairstow, czarne punkty wskazują rozbieżne zachowanie.

Pierwszy obraz jest demonstracją pojedynczego rzeczywistego przypadku głównego. Drugi wskazuje, że można zaradzić rozbieżnemu zachowaniu, wprowadzając dodatkowy pierwiastek rzeczywisty, kosztem spowolnienia szybkości zbieżności. Można również w przypadku wielomianów nieparzystych stopni najpierw znaleźć pierwiastek rzeczywisty za pomocą metody Newtona i/lub metody zmniejszania przedziałów, tak aby po deflacji pozostał lepiej zachowujący się wielomian parzystych stopni. Trzeci obraz odpowiada powyższemu przykładowi.

Linki zewnętrzne

• Algorytm Bairstowa w Mathworld
• Przepisy numeryczne w Fortran 77 Online
• Przykład rozwiązania pierwiastka wielomianowego (deg ( P ) ≤ 10) przy użyciu metody Bairstowa
• LinBairstowSolve , implementacja metody Lin-Bairstow typu open source w języku C ++ dostępna jako metoda biblioteki VTK
• Znajdowanie pierwiastków online wielomianu - metoda Bairstowa autorstwa Farhada Mazlumi