Untitled 41

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

+ e H*. — o || s£ (fi + 2e) ||jc — et ||. Obierając dostatecznie małe e, mamy p + 2e < 1 i z podanego powyżej lematu wynika, że przy dowolnym i^(0|ef ciąg generowany wzorem x^{(,+ ,)} = G(x⁽⁰) 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}(0_ AF(x^w)    (3.56)

gdzie: A: Rⁿ -*■ Rⁿ 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) = / — AF'(a.). Jeżeli g (/— AF'(a)) < 1, to istnieje takie otoczenie A”punktu a, że jeśli x^me K, to ciąg x⁽¹⁾, jc⁽²⁾, ... generowany wzorem (3.56) jest zawarty w K oraz x^(t)-*-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 (/ — AF'(a)) < 1 jest spełniony. Trudność tę rozwiązuje omówiona poniżej metoda Newtona.

3.4.2. Metoda Newtona

Tw. I. Niech funkcja F(x) będzie różniczkowalna w sensie Frecheta w pewnym otoczeniu K(a, 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(n _ [f'(j_t(0)]-i_i?(_j(0)    (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'(;r)]^-1 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^(,))d^(,) = /’(j:⁽'⁾) w celu obliczenia x^(,+1) =

¹¹ W szczególnym przypadku, gdy A = I (/— 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^{i) = [F'(x^(,))]^_1 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'(x) - F'(«)l| *HI* - «r dla xeK(z, r),    pe(0; 1> to

||jc^{(,+ i)} — a || ^ C ||x⁽ⁱ⁾ — a||^1+;>    (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⁰⁾, x^m,..., uzyskany ze wzoru (3.57) jest zbieżny do a, j tylko początkowy punkt x⁽⁰⁾ jest dostatecznie bliski punktowi a. Zai z nierówności (3.58) wynika, że

0

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ą, tzr

||jt^<f+l) — a || < C||x⁽ⁱ⁾-a||²

Wobec szybkiej lokalnej zbieżności i prostej formule (3.57) obliczania ci przybliżeń rozwiązania jc^(I), x⁽²\ ..., metoda Newtona znalazła szen 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, mc 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‘ Rⁿ-+Rⁿ wzorowaniem afmicznym w ten sposób, by

C

F(j>^(/)) * Ay^u) + b, j = 0, 1, ..., n