Metoda gospodarza

W matematyce , a dokładniej w analizie numerycznej , metody Householdera to klasa algorytmów wyszukiwania pierwiastków , które są używane do funkcji jednej zmiennej rzeczywistej z ciągłymi pochodnymi do pewnego rzędu d + 1 . Każda z tych metod charakteryzuje się liczbą d , która jest znana jako kolejność metody. Algorytm jest iteracyjny i ma współczynnik + 1 zbieżności d .

Metody te zostały nazwane na cześć amerykańskiego matematyka Alstona Scotta Householdera .

metoda

Metoda Householdera to numeryczny algorytm rozwiązywania równania nieliniowego f ( x ) = 0 . W tym przypadku funkcja f musi być funkcją jednej zmiennej rzeczywistej. Metoda składa się z sekwencji iteracji

${\ Displaystyle x_ {n + 1} = x_ {n} + d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{ N})}}}$

zaczynając od początkowego przypuszczenia x ₀ .

Jeśli f jest funkcją d + 1 razy różniczkowalną w sposób ciągły i a jest zerem f, ale nie jego pochodną, ​​to w sąsiedztwie a , iteracje x _n spełniają:

${\ Displaystyle | x_ {n + 1} -a | \ równoważnik K \ cdot {| x_ {n} -a |} ^ {d + 1}} dla pewnego K > 0.$ { $> 0.\!}$

Oznacza to, że iteracje zbiegają się do zera, jeśli początkowe przypuszczenie jest wystarczająco bliskie, oraz że zbieżność ma rząd d + 1 .

Pomimo ich rzędu zbieżności, metody te nie są szeroko stosowane, ponieważ wzrost precyzji nie jest współmierny do wzrostu wysiłku dla dużych d . Indeks Ostrowskiego wyraża redukcję błędów w liczbie ocen funkcji zamiast liczby iteracji.

• W przypadku wielomianów ocena pierwszych d pochodnych f przy x _n przy użyciu metody Hornera wymaga wysiłku d + 1 ocen wielomianów. Ponieważ n ( d + 1) ocen po n iteracjach daje wykładnik błędu równy ( d + 1) ⁿ , wykładnik dla jednej oceny funkcji wynosi ${\ displaystyle {\ sqrt [{d + 1}] { d+1}}}$ , numerycznie 1,4142 , 1,4422 , 1,4142 , 1,3797 dla d = 1, 2, 3, 4 i spadające po tym. Według tego kryterium d = 2 ( metoda Halleya ) jest optymalną wartością d .
• Dla funkcji ogólnych obliczenie pochodnej za pomocą arytmetyki Taylora różniczkowania automatycznego wymaga równowartości ( d + 1) ( d + 2)/2 ocen funkcji. re $(d + 1) (d + 2)} {2} }]{d+1}}}$ , czyli ${\ Displaystyle {\ sqrt [{3}] {2}} \ około 1,2599}$ dla metody Newtona, ${\ Displaystyle {\ sqrt [{6}] {3}} \ około 1,2009}$ dla metody Halleya i spada w kierunku 1 lub zbieżności liniowej dla metod wyższego rzędu.

Motywacja

Załóżmy, że f jest analityczne w sąsiedztwie a i f ( a ) = 0 . Wtedy f ma szereg Taylora w punkcie a , a jego stały wyraz wynosi zero. Ponieważ ten stały wyraz wynosi zero, funkcja f ( x ) / ( x - a ) będzie miała szereg Taylora w a i gdy f ′ ( a ) ≠ 0 , jego stały wyraz nie będzie równy zeru. Ponieważ ten stały wyraz nie jest zerem, wynika z tego, że odwrotność ( x − a ) / f ( x ) ma szereg Taylora w a , który zapiszemy jako ${\ Displaystyle \ suma _ {k = 0} ^ {+ \ infty} {\ Frac {c_ {k} (xa) ^ {k}} {k!}}} i jego stały$ wyraz c ₀ nie będzie zerowy. Korzystając z tego szeregu Taylora, możemy napisać

$${\ Displaystyle {\ Frac {1} {f}} = {\ Frac {c_ {0}} {xa}} + \ suma _ {k = 1} ^ {+ \ infty} {\ Frac {c_ {k} (xa)^{k-1}}{k~(k-1)!}}\,.}$$

Możemy obliczyć jego d -tą pochodną:

$${\ Displaystyle \ lewo ({\ Frac {1} {f}} \ prawo) ^ {(d)} = {\ Frac {(-1) ^ {d} d! ~ c_ {0}} {(xa) ^{d+1}}}+\suma _{k=d+1}^{+\infty}{\frac {c_{k}(xa)^{kd-1}}{k~(kd-1 )!}}}$$

$${\ Displaystyle = {\ Frac {(-1) ^ {d} d! ~ c_ {0}} {(xa) ^ {d + 1}}} \ lewo (1 + {\ Frac {1} {(( -1)^{d}d!~c_{0}}}\sum _{k=d+1}^{+\infty}{\frac {c_{k}(xa)^{k}}{k ~(kd-1)!}}\right)}$$

$${\ Displaystyle = {\ Frac {(-1) ^ {d} d! ~ c_ {0}} {(xa) ^ {d + 1}}} \ lewo (1 + {\ mathcal {O}} \ lewo ((xa)^{d+1}\prawo)\prawo)\,.}$$

Dogodnie, terminy dla k = 1, ..., d zniknęły. Otrzymujemy w ten sposób ten stosunek

$${\ Displaystyle d ~ {\ Frac {(1/f) ^ {(d-1)}} {(1/f) ^{(d)}}}=d~{\frac {(-1)^{d-1}(d-1)!~c_{0}}{(-1)^{d}d!~c_ {0}}}(xa)\left({\frac {1+{\mathcal {O}}\left((xa)^{d}\right)}{1+{\mathcal {O}}\left ((xa)^{d+1}\prawo)}}\prawo)}$$

$${\ Displaystyle = - (xa) \ lewo (1 + {\ mathcal {O}} \ lewo ((xa) ^ {d} \ prawo) \ prawo) \,.}$$

Jeśli a jest zerem f , które jest najbliższe x , to drugi czynnik dąży do 1, gdy d dąży do nieskończoności i ${\ Displaystyle x +d~{\frac {(1/f)^{(d-1)}}{(1/f)^{(d)}}}}$ idzie do .

Sugeruje to, że iteracja Householdera może być dobrą iteracją zbieżną. Rzeczywisty dowód zbieżności również opiera się na tym pomyśle.

Metody niższego rzędu

Metoda Householdera rzędu 1 jest po prostu metodą Newtona , ponieważ:

${\ Displaystyle {\ rozpocząć {tablica} {rl} x_ {n + 1} = & x_ {n} + 1 \, {\ Frac {\ lewo (1/f \ prawo) (x_ {n})} {\ lewo (1/f\right)^{(1)}(x_{n})}}\\[.7em]=&x_{n}+{\frac {1}{f(x_{n})}}\ cdot \left({\frac {-f'(x_{n})}{f(x_{n})^{2}}}\right)^{-1}\\[.7em]=&x_{n }-{\frac {f(x_{n})}{f'(x_{n})}}.\end{tablica}}}$

Dla metody Householdera rzędu 2 otrzymujemy metodę Halleya , ponieważ tożsamości

${\ Displaystyle \ textstyle (1/f) '(x) = - {\ Frac {f' (x)} {f ( x)^{2}}}\ }$

I

${\ Displaystyle \ textstyle \ (1/f) '' (x) =-{\frac {f''(x)}{f(x)^{2}}}+2{\frac {f'(x)^{2}}{f(x)^{3}} }}$

skutkować w

${\ Displaystyle {\ rozpocząć {tablica} {rl} x_ {n + 1} = & x_ {n} + 2 \, {\ Frac {\ lewo (1/f \ prawo) '(x_ {n})}} left(1/f\right)''(x_{n})}}\\[1em]=&x_{n}+{\frac {-2f(x_{n})\,f'(x_{n} )}{-f(x_{n})f''(x_{n})+2f'(x_{n})^{2}}}\\[1em]=&x_{n}-{\frac { f(x_{n})f'(x_{n})}{f'(x_{n})^{2}-{\tfrac {1}{2}}f(x_{n})f'' (x_{n})}}\\[1em]=&x_{n}+h_{n}\;{\frac {1}{1+{\frac {1}{2}}(f''/f ')(x_{n})\,h_{n}}}.\end{tablica}}}$

w ostatnim wierszu ${\ Displaystyle h_ {n} = - {\ tfrac {f (x_ {n})} {f' (x_ {n}) }}}$ jest aktualizacją iteracji Newtona w punkcie ${\ displaystyle x_ {n}}$ . Ta linia została dodana, aby pokazać, gdzie leży różnica w stosunku do prostej metody Newtona.

Metodę trzeciego rzędu uzyskuje się z tożsamości pochodnej trzeciego rzędu 1/ f

${\ Displaystyle \ textstyle (1/f) ''' (x) = - {\ Frac {f''' (x)} {f (x) ^ {2}}} + 6 {\ Frac {f' ( x)\,f''(x)}{f(x)^{3}}}-6{\frac {f'(x)^{3}}{f(x)^{4}}}}$

i ma formułę

${\ Displaystyle {\ rozpocząć {tablica} {rl} x_ {n + 1} = & x_ {n} + 3 \, {\ Frac {\ lewo (1/f \ prawo) '' (x_ {n})} \left(1/f\right)'''(x_{n})}}\\[1em]=&x_{n}-{\frac {6f(x_{n})\,f'(x_{n })^{2}-3f(x_{n})^{2}f''(x_{n})}{6f'(x_{n})^{3}-6f(x_{n})f '(x_{n})\,f''(x_{n})+f(x_{n})^{2}\,f'''(x_{n})}}\\[1em]= &x_{n}+h_{n}{\frac {1+{\frac {1}{2}}(f''/f')(x_{n})\,h_{n}}{1+( f''/f')(x_{n})\,h_{n}+{\frac {1}{6}}(f'''/f')(x_{n})\,h_{n }^{2}}}\end{tablica}}}$

i tak dalej.

Przykład

Pierwszym problemem rozwiązanym przez Newtona metodą Newtona-Raphsona-Simpsona było równanie wielomianowe ${\ Displaystyle y ^ {3} -2y-5 = 0}$ . Zauważył, że rozwiązanie powinno być bliskie 2. Zastąpienie y = x + 2 przekształca równanie w

${\ Displaystyle 0 = f (x) = -1 + 10x + 6x ^ {2} + x ^ {3}}$ .

Szereg Taylora funkcji odwrotności zaczyna się od

${\ Displaystyle {\ rozpocząć {tablica} {rl} 1/f (x) = & -1-10 \, x-106 \, x ^ {2} -1121 \, x ^ {3} -11856\,x^{4}-125392\,x^{5}\\&-1326177\,x^{6}-14025978\,x^{7}-148342234\,x^{8}-1568904385 \,x^{9}\\&-16593123232\,x^{10}+O(x^{11})\end{tablica}}}$

Wynik zastosowania metod Householdera różnych rzędów przy x = 0 otrzymujemy również dzieląc sąsiednie współczynniki tego ostatniego szeregu potęgowego. Dla pierwszych rzędów otrzymuje się następujące wartości już po jednym kroku iteracji: Na przykład w przypadku 3. rzędu ${\ displaystyle x_ {1} = 0,0 + 106/1121 =0,09455842997324}$ .

D	x 1
1	0,1 0000000000000000000000000000000000
2	0,094 339622641509433962264150943396
3	0,09455 8429973238180196253345227475
4	0,094551 282051282051282051282051282
5	0,09455148 6538216154140615031261962
6	0,094551481 438752142436492263099118
7	0,09455148154 3746895938379484125812
8	0,0945514815423 36756233561913325371
9	0,09455148154232 4837086869382419375
10	0,094551481542326 678478801765822985

Jak widać, jest trochę więcej niż d poprawnych miejsc po przecinku dla każdego zamówienia d. Pierwsze sto cyfr poprawnego rozwiązania to 0,09455 14815 42326 59148 23865 40579 30296 38573 06105 62823 91803 04128 52904 53121 89983 48366 71462 67281 77715 77578 .

Obliczmy wartości dla jakiegoś najniższego rzędu, ${\ Displaystyle x_ {2}, x_ {3}, x_ {4}}$

${\ Displaystyle f = -1 + 10x + 6x ^ {2} + x ^ {3}}$

${\ Displaystyle fa ^ {\ pierwsza} = 10 + 12x + 3x ^ {2}}$

${\ Displaystyle f ^ {\ pierwsza \ pierwsza} = 12 + 6x}$

${\ displaystyle f ^ {\ pierwsza \ pierwsza \ pierwsza} = 6}$

I korzystając z następujących zależności,

pierwsze zamówienie; ${\ Displaystyle x_ {i + 1} = x_ {i} -f (x_ {i}) / f ^ {\ pierwsza} ( x_{i})}$

drugiego rzędu; ${\ Displaystyle x_ {i + 1} = x_ {i} -2ff ^ {\ pierwsza} / (2 {f ^ {\ pierwsza}} ^ {2} -ff ^ {\ pierwsza \ pierwsza})} Trzecie zamówienie$

; ${\ Displaystyle x_ {i + 1} = x_ {i} - (6f {f ^ {\ pierwsza}} ^ {2} -3f ^ {2} f ^ {\ pierwsza \ pierwsza}) / (6 {f ^ {\prime}}^{3}-6ff^{\prime }f^{\prime \prime }+f^{2}f^{\prime \prime \prime })}$

X	1 miejsce (Newton)	2 miejsce (Halley)	3. zamówienie	4. zamówienie
x 1	0. 10000000000000000000000000000000000	0,094 339622641509433962264150943395	0,09455 8429973238180196253345227475	0,094551 28205128
x2 _	0,0945 68121104185218165627782724844	0,09455148154 0164214717107966227500	0,094551481542326591482 567319958483
x 3	0,094551481 698199302883823703544266	0,094551481542326591482386540579303	0,094551481542326591482386540579303
x 4	0,0945514815423265914 96064847153714	0,094551481542326591482386540579303	0,094551481542326591482386540579303
x 5	0,094551481542326591482386540579303
x6 _	0,094551481542326591482386540579303

Pochodzenie

Dokładne wyprowadzenie metod Householdera zaczyna się od aproksymacji Padé rzędu d + 1 funkcji, gdzie wybiera się przybliżenie z licznikiem liniowym. Gdy to zostanie osiągnięte, aktualizacja dla kolejnego przybliżenia wynika z obliczenia unikalnego zera licznika.

Przybliżenie Padé ma postać

${\ Displaystyle f (x + h) = {\ Frac {a_ {0} + h} {b_ {0} + b_ {1} h + \ cdots + b_ {d-1} h ^ {d-1}}} +O(h^{d+1}).}$

Funkcja wymierna ma zero w ${\ displaystyle h = -a_ {0}}$ .

Tak jak wielomian Taylora stopnia d ma współczynniki d + 1 , które zależą od funkcji f , przybliżenie Padé ma również współczynniki d + 1 zależne od f i jego pochodnych. Dokładniej, w każdym przybliżeniu Padé stopnie wielomianów licznika i mianownika muszą sumować się do rzędu przybliżenia. Dlatego ${\ displaystyle b_ {d} = 0}$ musi się utrzymać.

Można by określić przybliżenie Padé, wychodząc z wielomianu Taylora f, używając algorytmu Euklidesa . Jednak wyjście z wielomianu Taylora 1/ f jest krótsze i prowadzi bezpośrednio do podanego wzoru. Od

${\ Displaystyle (1/f) (x + h) = (1/f) (x) + (1/f) '(x) h + \ cdots + (1/f) ^ {(d-1)}(x){\frac {h^{d-1}}{(d-1)!}}+(1/f)^{(d)}(x){\frac { h^{d}}{d!}}+O(h^{d+1})}$

musi być równe odwrotności pożądanej funkcji wymiernej, otrzymujemy po pomnożeniu przez równanie za $\ displaystyle a_ {0} + h}$ w potędze $displaystyle h ^ {d}}$ \

${\ Displaystyle 0 = b_ {d} = a_ {0} (1/f) ^ {(d)} (x) {\ Frac {1} {d!}} + (1/f) ^ {(d- 1)}(x){\frac {1}{(d-1)!}}}$ .

Teraz rozwiązanie ostatniego równania dla zera licznika skutkuje ${\ displaystyle h = -a_ {0}}$

${\ Displaystyle {\ rozpocząć {wyrównane} h & = -a_ {0} = {\ Frac {{\ Frac {1} {(d-1)!}} (1 /f)^{(d-1)}(x)}{{\frac {1}{d!}}(1/f)^{(d)}(x)}}\\&=d\, {\frac {(1/f)^{(d-1)}(x)}{(1/f)^{(d)}(x)}}\end{wyrównane}}}$ .

Oznacza to formułę iteracji

${\ Displaystyle x_ {n + 1} = x_ {n} + d\;{\frac {\left(1/f\right)^{(d-1)}(x_{n})}{\left(1/f\right)^{(d)}(x_{ n})}}}$ .

Związek z metodą Newtona

f ( x ) o wartościach rzeczywistych jest taka sama jak metoda Newtona zastosowana do funkcji g ( x ) :

${\ Displaystyle x_ {n + 1} = x_ {n} - {\ Frac {g (x_ {n})} {g '( x_{n})}}}$

z

${\ Displaystyle g (x) = \ lewo | (1 / f) ^ {(d-1)} \ prawo | ^ {- 1 / d} \,.}$

W szczególności d = 1 daje niezmodyfikowaną metodę Newtona, a d = 2 daje metodę Halleya.

Linki zewnętrzne

• Pascal Sebah i Xavier Gourdon (2001). „Metoda Newtona i iteracja wysokiego rzędu” . Uwaga : Użyj wersji postscriptowej tego łącza; wersja serwisu nie jest poprawnie skompilowana.