Untitled 40

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

wyznaczania przybliżeń pierwiastków nie ma specjalnego wpływu przy sklejanej deflacji).

W podobny sposób można znaleźć sklejany algorytm deflacyjny dla deflacji rzeczywistego wielomianu /(z) z rzeczywistym czynnikiem kwadratowym (jest to ważne ze względu na stosowanie metody Bairstowa [47]). Problem deflacji — oczywisty w przypadku poszukiwania zer wielomianów — w przypadku równań przestępczych można sprowadzić np. dla metody Newtona do tzw. pozornej deflacji. Polega ona na formalnym podzieleniu lewej strony równania przez iloczyn czynników liniowych odpowiadających już znalezionym pierwiastkom i ponownego zastosowania metody Newtona do tak otrzymanej funkcji [68, s. 112]. W przypadku metody Newtona wzór na deflację pozorną ma postać

r — liczba już znalezionych zer funkcji f(x).

3.4. UKŁADY RÓWNAŃ NIELINIOWYCH

Istota rozwiązywania układu równań sprowadza się do znalezienia takiego rozwiązania a e /?”, w którym odwzorowanie F: Rⁿ -*■ R" przyjmuje wartość zero, tzn. F{a) = 0°. W szczególnym przypadku gdy odwzorowanie F jest afiniczne, np. F(x) = Ax — b, uzyskujemy układ równań liniowych Ax = b, w którym A jest macierzą utworzoną ze współczynników układu, x — wektorem szukanych wartości, a b — wektorem wyrazów wolnych. Metody rozwiązywania układów równań liniowych są omówione w rozdziale 5: podano tam przegląd tzw. metod dokładnych i metod iteracyjnych poszukiwania rozwiązania a, przyjmując założenie o istnieniu i jednoznaczności rozwiązywania układu Ax = b, które sprowadza się do warunku det A =£ 0. W przypadku gdy odwzorowanie Fjest nieliniowe warunki istnienia rozwiązania układu równań F(x) = 0 są znacznie trudniejsze do sprawdzenia, a nawet nie można sformułować jednolitego kryterium istnienia rozwiązania bez założenia szczególnych własności odwzorowania F, takich jak różniczko-

'* Zwracamy uwagę Czytelnika, że metody poszukiwania rozwiązań układów równań są znacznie trudniejsze niż dla jednego równania. W celu krótkiego przedstawienia własności tych metod, wprowadza się zazwyczaj zapis wektorowy. Ponadto pojawia się tu potrzeba odróżnienia indeksów współrzędnych wektora od numerów nadawanych wektorom w kolejnych iteracjach. Przyjęto umowę, że numery iteracji są oznaczone indeksami u góry, a współrzędne wektora — indeksami u dołu. Zatem x, oznacza pierwszą współrzędną wektora x, a x^(l) wektor obliczony w pierwszej iteracji.

walność, monotoniczność itp. W naszych rozważaniach będziemy zakładać a priori istnienie rozwiązania a układu równań F(x) = 0 i ograniczymy się jedynie do omówienia wybranych metod poszukiwania punktu a. Czytelnika zainteresowanego dalszymi szczegółami odsyłamy do prac [45], [69] i [23],

3.4.1. Ogólne metody iteracyjne

W obliczeniach numerycznych konstruujemy na ogół ciąg punktów x⁽⁰⁾, x^M), ..., zbieżny do rozwiązania a układu równań F(x) = 0. Jeżeli można wskazać takie odwzorowanie G, że x^(,) = G(x^(,-1), x^(,_2), ..., x^(,_/,)), to taką metodę iteracyjną nazywamy metodą stacjonarną p-punktową. W szczególnym przypadku, gdy x^(,) = G(x^(i_1)), metodę nazywamy stacjonarną, opuszczając dodatkowe określenie „1-punktową”. W pewnych przypadkach operator G może ulec modyfikacjom podczas iteracji — metodę nazywamy wówczas niestacjonarną (p-punktową) lub metodą zmiennego operatora.

Def. (Ostrowskiego). Niech G: D cz R" x Rⁿ x ... x R"-+ Rⁿ. Punkt a. nazywamy punktem przyciągania metody iteracyjnej, jeżeli istnieje takie otoczenie U_x tego punktu, że obierając punkty x^(_/,+1}, x⁽~^p+2),..., jc⁽⁰⁾ z tego otoczenia uzyskamy ciąg punktów x⁽¹⁾, x⁽²⁾, ..., cfl, zbieżny do a.

Największe z tych otoczeń nazywamy obszarem przyciągania punktu x.

Lemat. Niech G: D c Rⁿ -*■ Rⁿ i niech istnieją kula K(a, r) a D i stała c < 1 takie, że

II Gx — a || < c ||x — a ||, A^xeK

Wówczas dla dowolnego x^<0)e K, ciągx^{]), x⁽²⁾,... generowany wzorem x^{(,+ l)} = = G(x⁽ⁱ⁾) jest zawarty w K i jest zbieżny do a. Zbieżność ta jest co najmniej liniowa, tzn. ||x⁽ⁱ⁺¹⁾ — <z|| < c||x^(,) — a||, i = 0, 1,____

Def. Odwzorowanie G: Rⁿ-+R" nazywamy różniczkowalnym w sensie

Frecheta w punkcie x, jeżeli istnieje taka macierz A\ R"-+Rⁿ, że

<    ||G(x + h) — G(x) — Ah\\    ,    ,

hm-—- = 0 przy dowolnym sposobie wyboru wek-

*-o    ||Ml

torów /i —► 0. Macierz A nazywamy pochodną Frecheta odwzorowania G (lub F-pochodną) w punkcie x i oznaczamy ją G'(x).

Tw. 1. (Ostrowskiego). Jeżeli F-pochodna odwzorowania G: w punkcie a ma promień spektralny^ q> (G'(<*)) = /? < 1 oraz G (a) = a, to a jest punktem przyciągania metody iteracyjnej x^{(,+ l)} = G(x^<,)).

DOWÓD. Można wykazać [45, s. 47], że dla dowolnego e >0 istnieje taka norma w R", że ||G'(a)|| ^ p + e. Z określenia F-pochodnej wynika, że istnieje taka kula AT (a, r), że ||G(x) — -G(a)-G'(«)(x-a)||    dla xeK. Zatem ||G(x) - a|| < ||G'(a)(x - a)||+

¹¹ Promieniem spektralnym macierzy kwadratowej nazywamy największy spośród modułów wartości własnych tej macierzy.