img055 (25)

60

.

Ciąg iterowany zdefiniowany formułą rekurencyjną (3.67) algorytmu iteracji prostej jest zbieżny do punktu stałego dla dowolnie ustalonego wektora początkowego jc₍₀₎. Oszacowanie od góry błędu po j iteracjach dane jest wzorem

II    II    ii    ii

Ir ^_*wp]ź7'lrW"*(o)fl-    ⁽³-⁶⁹⁾

Twierdzenie Banacha o punkcie stałym odwzorowania zwężającego posiada uogólnienie dla odwzorowań w przestrzeniach metrycznych zupełnych [15].

Warunek (3.68) jest globalnym warunkiem Lipschitza ze stałą Lipschitza 0<I<1. Nietrudno zauważyć, że dla L bliskiego jedności zbieżność ciągu iterowanego może być bardzo wolna. Niech s_w oznacza błąd po j iteracjach

^e(/) ⁼ |*or*1 •    ^(3J0)

Dla odwzorowania F(-) spełniającego warunek (3.68) otrzymuje się oszacowanie a więc

£0₊i)^-%) •    (3-72)

Algorytm, dla którego ma miejsce oszacowanie błędu w kroku następnym w zależności od błędu w kroku poprzednim takie jak we wzorze (3.72) jest określany jako algorytm o liniowej szybkości zbieżności. A zatem algorytm iteracji prostej jest w przypadku odwzorowania zwężającego F(-) algorytmem o liniowej szybkości zbieżności. Szybkość zbieżności algorytmu iteracji prostej można poprawić, dokonując odpowiedniego przekształcenia odwzorowania F(-). Modyfikacje takie prowadzą do szeregu znanych pod innymi nazwami algorytmów. Otrzymuje się na przykład omawiany w podrozdziale 3.2.2, algorytm Newto-na-Raphsona o kwadratowej szybkości zbieżności.

Powstaje naturalne pytanie, czy dla zadanego odwzorowania F(-), mającego dokładnie jeden punkt stały ar*, można dokonać takiego jego przekształcenia, które zachowywałoby punkt stały x* dla otrzymanego odwzorowania oraz odwzorowanie otrzymane w wyniku przekształcenia spełniałoby globalny warunek Lipschitza w R" ze stałą Lipschitza L< 1. Takie przekształcenie zapewniłoby globalną zbieżność do punktu stałego * danego odwzorowania F(.) ciągów iterowanych otrzymanych dla odwzorowania przekształconego zgodnie z formułą iteracji prostej.

Ogólnie nie jest znane przekształcenie spełniające przedstawione wyżej wymagania, i które posiadałoby jednocześnie wartość praktyczną z punktu widzenia potrzeb związanych z wykonywaniem obliczeń. Wykorzystywane w praktyce obliczeniowej przekształcenia danego odwzorowania F(-) mające na celu zapewnienie zbieżności odpowiednich ciągów iterowanych (3.67) otrzymywane są na ogół w następujący sposób. Równanie jc = F(x) jest przekształcane do postaci równoważnej