Untitled 41

3. Przybliżone rozwiązywanie równań nieliniowych i ich układów 152

+ e ||jc — a || < (J? + 2e) || j — a||. Obierając dostatecznie małe £, mamy /J + 2e < 1 i z podanego powyżej lematu wynika, że przy dowolnym jc⁽⁰⁾eA' ciąg generowany wzorem x⁽ⁱ⁺¹⁾ = G(jr^<0) jest zbieżny do a, cnd.

Twierdzenie 1 pozwala uzasadnić lokalną zbieżność wielu metod iteracyj-nych stosowanych do wyznaczenia rozwiązania a układu równań F(x) = 0. Niech na przykład

jc⁽'⁺d = x⁽⁰ — AF(x^(r>)    (3.56)

gdzie: A: 7?"->-/?" jest odpowiednio przyjętą macierzą⁰. Wzór (3.56) określa stacjonarną metodę iteracyjną z odwzorowaniem G(x) = x — AF(x).

Załóżmy, że Fjest funkcją różniczkowalną w sensie Frecheta w punkcie a. Wówczas G'(a) = 7 — AF'(a). Jeżeli g (7— AF'(a)) < 1, to istnieje takie otoczenie K punktu a, że jeśli x⁽⁰⁾ e K, to ciąg x^(l), jc^<2), ... generowany wzorem (3.56) jest zawarty w K oraz x⁰⁾—>~a. Warunek powyższy jest dostateczny (a także konieczny [45]) dla lokalnej zbieżności metody iteracyjnej (3.56) do punktu a. Istotna trudność polega jednak na tym, że na ogół nie znamy pochodnej F'(a), a więc nie mamy gwarancji, że warunek g(I — AF'(a)) < 1 jest spełniony. Trudność tę rozwiązuje omówiona poniżej metoda Newtona.

3.4.2. Metoda Newtona

Tw. 1. Niech funkcja F(x) będzie różniczkowalna w sensie Frecheta w pewnym otoczeniu K(ct, r) punktu a, w którym F(a) = 0. Załóżmy, że pochodna F'(x) jest ciągła w punkcie a, a pochodna F' (a) jest nieosobliwa. Wówczas punkt a jest punktem przyciągania metody iteracyjnej

x^{(,+ 1)} ₌ j-(0 _ [F'(x⁽ⁱ⁾)]-¹7^:’(x⁽''⁾)    (3.57)

zwanej metodą Newtona.

SZKIC DOWODU. Założenie ciągłości pochodnej w punkcie a i nieosobliwość pochodnej F'(a) gwarantują, że w pewnym otoczeniu tego punktu pochodna F'(a) jest nieosobliwa. Korzystając z definicji pochodnej Frecheta można uzasadnić, że pochodna odwzorowania G(x) = x — [F'(a:)]“' F(x) w punkcie a jest równa zeru. Zatem z twierdzenia Ostrowskiego (patrz p. 3.4.1) wynika lokalna zbieżność metody Newtona.

Zauważmy, że metoda (3.57) jest prostym uogólnieniem na przypadek funkcji n zmiennych metody opisanej w p. 3.1.3. Jak poprzednio, przyjęto tu silne założenia dotyczące funkcji F (ciągła różniczkowalność, nieosobliwość pochodnej w punkcie a), a uzyskano jedynie gwarancję lokalnej zbieżności metody. Dodatkową niedogodnością jest konieczność rozwiązywania w każdej iteracji układu równań F'(x^(l))d⁽ⁱ⁾ = F(x⁽⁰) w celu obliczenia x^(,+1> =

¹¹ W szczególnym przypadku, gdy A =1(1— macierz jednostkowa), metodę nazywamy metodą iteracji prostej. Łatwo sprawdzić, że aby punkt a był punktem przyciągania metody iteracji prostej, potrzeba i wystarcza, by w punkcie tym Jacobian F'(a) miał wartości własne o modułach w przedziale (0; 2).

= x⁽⁰ — d°\ gdzie d^w = [F'(x^(,))]^_I F(x⁽⁰). Przy pewnych dodatkowy założeniach dotyczących funkcji F zbieżność metody Newtona jest jedr bardzo szybka.

Tw. 2. Jeżeli odwzorowanie F spełnia warunki twierdzenia 1, a pona ciągłość pochodnej F'(x) w punkcie a. jest typu Hóldera, tzn.

||f'(*) - r(a)|| <//||jc-<xr dla xeK{<x, r),    pe(0; 1> to

||x^{(,+ 1)} — a|| < C||jc^w —    (3.

gdzie C = 4H\\F\a)-'\\.

Uzasadnienie powyższego twierdzenia można znaleźć np. w [45], Przy spełnieniu założeń tego twierdzenia metoda Newtona jest loka! zbieżna, tzn. ciąg x^(1>, x⁽²⁾,..., uzyskany ze wzoru (3.57) jest zbieżny do a, j tylko początkowy punkt x⁽⁰⁾ jest dostatecznie bliski punktowi a. Za' z nierówności (3.58) wynika, że

< C ||x⁽⁰

otp-*>0

ll*^(,>l>-gll

|| jc^(f> — a ||

tzn. zbieżność jest nadliniowa (szybsza niż w przypadku dowolnego malej; go postępu geometrycznego).

W szczególnym przypadku, gdy p — 1, gdy pochodna F'{x) jest ci< w punkcie a w sensie Lipschitza, uzyskujemy zbieżność kwadratową, tzi

||x^{(,+ 1)} — a || < C||jc⁽⁰- a ||²

Wobec szybkiej lokalnej zbieżności i prostej formule (3.57) obliczania ci przybliżeń rozwiązania x⁽¹⁾, x^{1), ..., metoda Newtona znalazła szeri zastosowanie w obliczeniach prowadzących na maszynach cyfrowych. O cowano wiele modyfikacji tej metody, pozwalającej na osłabienie niektói założeń gwarantujących zbieżność lokalną, a także opracowano spos zwiększania promienia zbieżności metody (czyli powiększania otocz punktu a, z którego można wybierać początkowe przybliżenia jc^<0)). W p padku gdy liczba zmiennych n jest duża, istotną trudnością jest oblicz pochodnych F'(x) odwzorowania F. Wówczas stosuje się dyskretne wari; metody Newtona, w których zastępuje się pochodną F'(x) jej przybliżer różnicowym [45]. Podobnie jak w przypadku funkcji jednej zmiennej, mt jednak od razu zrezygnować z korzystania z pochodnych i zastosować me siecznych.

3.4.3. Metoda siecznych

Idea tej metody polega na przybliżeniu odwzorowania F‘ wzorowaniem afinicznym w ten sposób, by

(!

F(y^U))x Ay^U) + b, j = 0,\,...,n