Bairstowsova metoda - Bairstows method - Wikipedia

tento článek příliš spoléhá na Reference na primární zdroje. Vylepšete to přidáním sekundární nebo terciární zdroje. (Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v numerická analýza, Bairstowova metoda je efektivní algoritmus pro nalezení kořeny skutečné polynomiální libovolného stupně. Algoritmus se poprvé objevil v příloze knihy z roku 1920 Aplikovaná aerodynamika podle Leonard Bairstow.^{[1][není nutný primární zdroj ]} Algoritmus najde kořeny komplexní konjugát páry využívající pouze skutečnou aritmetiku.

Vidět algoritmus hledání kořenů pro další algoritmy.

Popis metody

Přístup společnosti Bairstow je použít Newtonova metoda upravit koeficienty u a proti v kvadratický ${ displaystyle x ^ {2} + ux + v}$ dokud jeho kořeny nejsou také kořeny řešeného polynomu. Poté lze určit kořeny kvadratu a polynom lze rozdělit kvadratem, aby se tyto kořeny vyloučily. Tento proces je poté iterován, dokud se polynom nestane kvadratickým nebo lineárním, a nebyly stanoveny všechny kořeny.

Dlouhé dělení polynomu, který má být vyřešen

${ displaystyle P (x) = součet _ {i = 0} ^ {n} a_ {i} x ^ {i}}$

podle ${ displaystyle x ^ {2} + ux + v}$ získá kvocient ${ displaystyle Q (x) = součet _ {i = 0} ^ {n-2} b_ {i} x ^ {i}}$ a zbytek ${ displaystyle cx + d}$ takhle

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

Druhá divize ${ displaystyle Q (x)}$ podle ${ displaystyle x ^ {2} + ux + v}$ se provádí, aby se získal kvocient ${ displaystyle R (x) = součet _ {i = 0} ^ {n-4} f_ {i} x ^ {i}}$ a zbytek ${ displaystyle gx + h}$ s

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

Proměnné ${ displaystyle c, , d, , g, , h}$a ${ displaystyle {b_ {i} }, ; {f_ {i} }}$ jsou funkce ${ displaystyle u}$ a ${ displaystyle v}$. Lze je najít rekurzivně následujícím způsobem.

${ displaystyle { 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 {zarovnáno}}}$

Kvadratik rovnoměrně rozděluje polynom, když

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

Hodnoty ${ displaystyle u}$ a ${ displaystyle v}$ pro které k tomu dojde, lze zjistit výběrem počátečních hodnot a iterací Newtonovy metody ve dvou dimenzích

${ displaystyle { begin {bmatrix} u v end {bmatrix}}: = { begin {bmatrix} u v end {bmatrix}} - { begin {bmatrix} { frac { částečné c} { částečné u}} & { frac { částečné c} { částečné v}} [3pt] { frac { částečné d} { částečné u}} & { frac { částečné d } { částečné 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}}}$

dokud nedojde ke konvergenci. Tuto metodu pro nalezení nul polynomů lze tedy snadno implementovat pomocí programovacího jazyka nebo dokonce tabulky.

Příklad

Úkolem je určit dvojici kořenů polynomu

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

Jako první kvadratický polynom lze zvolit normalizovaný polynom vytvořený z předních tří koeficientů F(X),

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

Iterace pak vytvoří tabulku

Po osmi iteracích způsobila metoda kvadratický faktor, který obsahuje kořeny −1/3 a −3 v rámci zobrazené přesnosti. Délka kroku od čtvrté iterace ukazuje superlineární rychlost konvergence.

Výkon

Bairstowův algoritmus zdědí lokální kvadratickou konvergenci Newtonovy metody, s výjimkou případu kvadratických faktorů multiplicity vyšších než 1, kdy je konvergence k tomuto faktoru lineární. Zvláštní druh nestability lze pozorovat, když má polynom lichý stupeň a pouze jeden skutečný kořen. Kvadratické faktory, které mají v tomto skutečném kořenu malou hodnotu, se obvykle rozcházejí do nekonečna.

${ displaystyle f (x) = x ^ {5} -1}$	${ displaystyle f (x) = x ^ {6} -x}$	${ displaystyle { begin {aligned} f (x) = & 6x ^ {5} + 11x ^ {4} -33x ^ {3} & - 33x ^ {2} + 11x + 6 end {zarovnáno}} }$

Obrázky představují dvojice ${ displaystyle (s, t) v [-3,3] ^ {2}}$. Body v horní polovině roviny t > 0 odpovídá lineárnímu faktoru s kořeny ${ displaystyle s pm it}$, to je ${ displaystyle x ^ {2} + ux + v = (x-s) ^ {2} + t ^ {2}}$. Body v dolní polovině roviny t <0 odpovídá kvadratickým faktorům s kořeny ${ displaystyle s pm t}$, to znamená, ${ displaystyle x ^ {2} + ux + v = (x-s) ^ {2} -t ^ {2}}$, tedy obecně ${ displaystyle (u, , v) = (- 2 s, , s ^ ​​{2} + t , | t |)}$. Body jsou vybarveny podle posledního bodu iterace Bairstowa, černé body označují odlišné chování.

První obrázek je ukázkou jediného skutečného kořenového případu. Druhý naznačuje, že lze napravit odlišné chování zavedením dalšího skutečného kořene za cenu zpomalení rychlosti konvergence. Lze také v případě lichých stupňů polynomů nejprve najít skutečný kořen pomocí Newtonovy metody a / nebo metody zmenšování intervalů, takže po deflaci zůstane lépe vychovaný sudý polynom. Třetí obrázek odpovídá výše uvedenému příkladu.

Odkaz

externí odkazy

• Bairstowův algoritmus na Mathworld
• Numerické recepty ve Fortranu 77 online
• Příklad řešení kořene polynomu (deg (P) ≤ 10) pomocí Bairstowovy metody
• LinBairstowSolve, open-source implementace metody Lin-Bairstow v C ++ dostupná jako metoda knihovny VTK
• Online kořenový nález polynomu - Bairstowova metoda autor: Farhad Mazlumi