MN02

Równania nieliniowe

<<< Powrót do strony głównej przedmiotu Metody numeryczne

W wielu zadaniach, m.in. matematyki stosowanej, spotykamy się z problemem rozwiązania skalarnego równania nieliniowego postaci $\displaystyle f(x)=0$. Oto kilka przykładów:

Przykład

Równanie Keplera

$\displaystyle f(x)\equiv x-\epsilon \sin(x)-M=0$

jest bardzo ważne w astronomii, jego rozwiązanie pozwala wyznaczyć przyszłe położenie planety. Parametr $\displaystyle \epsilon$ odpowiada ekscentryczności orbity i przyjmuje wartości z przedziału $\displaystyle [0,1]$. Poza paru prostymi przypadkami, w ogólności równanie Keplera nie daje się rozwiązać w terminach funkcji elementarnych.

Johann Kepler
Zobacz biografię

Przykład

Znajdowanie miejsc zerowych wielomianu

$\displaystyle f(x)\equiv a_{n}x^{n}+\ldots +a_{1}x+a_{0}=0.$

Bardzo wiele modeli matematycznych wymaga rozwiązania równania z wielomianową nieliniowością. Piękne kwadratury (Gaussa) opierają się na węzłach będących zerami pewnego wielomianu. Wielomiany są bardzo szczególnymi funkcjami i dla nich istnieje szereg wyspecjalizowanych metod znajdowania ich pierwiastków, m.in. metoda Laguerre'a, metoda Bairstow'a (o nich tu nie będziemy mówić), a także zaskakujące metody sprowadzające zadanie poszukiwania miejsc zerowych wielomianu do zupełnie innego zadania matematycznego --- o nich jednak będzie mowa dopiero w wykładzie dotyczącym znajdowania wartości własnych macierzy.

Przykład

Obliczanie pierwiastka kwadratowego z zadanej liczby $\displaystyle a$, czyli sposób na implementację funkcji "sqrt()". Można to zadanie wyrazić, jako rozwiązywanie równania

$\displaystyle f(x)\equiv x^{2}-a=0.$

Szybkie algorytmy wyznaczania pierwiastka kwadratowego były znane już starożytnym. W wykładzie zrozumiemy, dlaczego metoda Herona,

$\displaystyle x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {a}{x_{k}}}\right)$

daje bardzo dobre przybliżenie $\displaystyle {\sqrt {a}}$ już po kilku iteracjach.

Przykład

Implementacja wyznaczania odwrotności liczby $\displaystyle a$ (bez dzielenia!) jest możliwa, gdy odpowiednią metodą będziemy poszukiwać rozwiązania równania

$\displaystyle f(x)\equiv {\frac {1}{x}}-a=0.$

To zadanie jest ważne praktycznie, np. tak można poprawić precyzję funkcji wektorowych stosowanych w niektórych procesorach AMD. Okazuje się, że instrukcja procesora służąca do równoległego obliczania odwrotności sekwencji liczb umieszczonych w 128-bitowym rejestrze wektorowym daje wynik z małą precyzją (oczywiście po to, by wykonywała się szybciej!). Jeśli taka dokładność wyniku nie odpowiada nam, możemy ją --- zgodnie z manualem procesora --- poprawić, rozwiązując właśnie takie równanie jak powyżej, metodą korzystającą wyłącznie z (wektorowych) operacji mnożenia i dodawania.

Bisekcja

Metoda bisekcji, czyli połowienia, często stosowana w innych działach informatyki, jest dość naturalną metodą obliczania zer skalarnych funkcji ciągłych określonych na danym przedziale $\displaystyle [a,b]$ i zmieniających znak. Dokładniej, rozpatrzmy klasę funkcji

$\displaystyle F\,=\,\{\,f\in C([a,b])\,:\;f(a)\cdot f(b)<0\,\},$

to znaczy $\displaystyle f\in F$ przyjmują w krańcach przedziału wartości przeciwnego znaku. Oczywiście, każda funkcja $\displaystyle f\in F$ ma, na mocy twierdzenia Darboux, co najmniej jedno zero w $\displaystyle [a,b]$. Startując z przedziału $\displaystyle [a,b]$, w kolejnych krokach metody bisekcji obliczamy informację o wartości $\displaystyle f$ w środku przedziału, co pozwala nam w następnym kroku zmniejszyć o połowę przedział, w którym na pewno znajduje się zero funkcji.

Bisekcję realizuje następujący ciąg poleceń, po wykonaniu którego $\displaystyle x$ jest przybliżeniem zera funkcji $\displaystyle f$ z zadaną dokładnością $\displaystyle \epsilon$.

Algorytm Metoda bisekcji

---

lewy = a; prawy = b;
flewy = f(lewy); fprawy = f(prawy);
x = (a+b)/2; 	/* przybliżenie rozwiązania */
e = (b-a)/2; 	/* przedział lokalizujący rozwiązanie dokładne */
while (e > <math>\displaystyle \epsilon</math>) 
{
	fx = f(x);   	/* reszta */
	if ( abs(fx) == 0 ) /* trafiliśmy dokładnie w miejsce zerowe */
		return(x); 
	if ( sign(fx) != sign(flewy) ) /* tzn. f(lewy)*f(x) < 0 */
	{
		prawy = x;
		fprawy = fx;
	}
	else
	{
		lewy = x;
		flewy = fx;
	}
	x = (lewy+prawy)/2; /* najlepsze przybliżenie rozwiązania przy danym przedziale */
	e = e/2;
}
return(x);

Z konstrukcji metody łatwo wynika, że po wykonaniu $\displaystyle k$ obrotów pętli while (czyli po obliczeniu $\displaystyle k+2$ wartości funkcji) otrzymujemy $\displaystyle x$, które odległe jest od pewnego rozwiązania $\displaystyle x^{*}$ o co najwyżej

$\displaystyle |x-x^{*}|\,\leq \,{\Big (}{\frac {1}{2}}{\Big )}^{k}{\Big (}{\frac {b-a}{2}}{\Big )}.$

Metoda bisekcji jest więc zbieżna liniowo z ilorazem $\displaystyle 1/2$. Choć ta zbieżność nie jest imponująca, bisekcja ma kilka istotnych zalet. Oprócz jej prostoty, należy podkreślić fakt, że bisekcja jest w pewnym sensie uniwersalna. Jeśli tylko dysponujemy dwoma punktami $\displaystyle a$ i $\displaystyle b$ takimi, że $\displaystyle f$ przyjmuje w nich wartości przeciwnych znaków, to metoda bisekcji z pewnością znajdzie miejsce zerowe funkcji, choćby początkowa długość przedziału $\displaystyle |b-a|$ była bardzo duża: zbieżność metody bisekcji jest globalna. Co ważniejsze, dla zbieżności metody bisekcji wystarcza jedynie ciągłość funkcji. Poza tym możemy łatwo kontrolować błąd bezwzględny aproksymacji miejsca zerowego. Konsekwencją powyższego oszacowania błędu jest bowiem następujący wniosek.

Wniosek

Dla znalezienia zera $\displaystyle x^{*}$ z dokładnością $\displaystyle \epsilon >0$, wystarczy obliczyć w metodzie bisekcji

$\displaystyle k\,=\,k(\epsilon )\,=\,{\Big \lceil }{\log _{2}{\frac {(b-a)}{\epsilon }}}{\Big \rceil }-1$

wartości funkcji.

Iteracja prosta Banacha

Zupełnie inne, i jak się okaże --- przy odrobinie sprytu bardzo skuteczne --- podejście do wyznaczania miejsca zerowego jest oparte na metodzie Banacha. Dla większej ogólności, będziemy zakładać teraz, że $\displaystyle f:D\rightarrow R^{N}$ i $\displaystyle D$ jest otwartym, niepustym podzbiorem $\displaystyle R^{N}$.

Najpierw nasze równanie nieliniowe

$\displaystyle f(x)=0$

przekształcamy (dobierając odpowiednią funkcję $\displaystyle \phi$) do równania równoważnego (tzn. mającego te same rozwiązania)

$\displaystyle x\,=\,\phi (x).$

Taki $\displaystyle x$, dla którego zachodzi powyższa równość, nazywamy punktem stałym odwzorowania $\displaystyle \phi$.

Następnie, startując z pewnego przybliżenia początkowego $\displaystyle x_{0}\in D$, konstruujemy ciąg kolejnych przybliżeń $\displaystyle x_{k}$ według wzoru

$\displaystyle x_{k}\,=\,\phi (x_{k-1}),\qquad k\geq 1.$

Stefan Banach
Zobacz biografię

Twierdzenie Banacha, o kontrakcji

Niech $\displaystyle D_{0}$ będzie domkniętym podzbiorem dziedziny $\displaystyle D$,

$\displaystyle {\overline {D}}_{0}\,=\,D_{0}\subset D,$

w którym $\displaystyle \phi$ jest odwzorowaniem zwężającym. To znaczy, $\displaystyle \phi (D_{0})\subset D_{0}$, oraz istnieje stała $\displaystyle 0\leq L<1$ taka, że

$\displaystyle \|\phi (x)-\phi (y)\|\,\leq \,L\,\|x-y\|,\qquad \forall x,y\in D_{0}.$

Wtedy równanie

$\displaystyle x\,=\,\phi (x).$

ma dokładnie jedno rozwiązanie $\displaystyle x^{*}$, oraz

$\displaystyle x^{*}\,=\,\lim _{k\to \infty }x_{k},$

dla dowolnego przybliżenia początkowego $\displaystyle x_{0}\in D_{0}$.

Dowód

Wobec

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \| x_k- x_{k-1}\| &= \|\phi( x_{k-1})-\phi( x_{k-2})\| \,\le\,L\,\| x_{k-1}- x_{k-2}\| \\ &\le &\cdots\;\le\;L^{k-1}\| x_1- x_0\|, \endaligned}

dla $\displaystyle k\geq s$ mamy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \| x_k- x_s\| &&\le \sum_{j=s+1}^k\| x_j- x_{j-1}\| \,\le\,\sum_{j=s+1}^k L^{j-1}\| x_1- x_0\| \\ &&= L^s(1+L+\cdots+L^{k-s-1})\| x_1- x_0\| \,\le\,\frac{L^s}{1-L}\| x_1- x_0\|. \endaligned}

Ciąg $\displaystyle \{x_{k}\}_{k}$ jest więc ciągiem Cauchy'ego. Stąd istnieje granica $\displaystyle \alpha =\lim _{k\to \infty }x_{k}$, która należy do $\displaystyle D_{0}$, wobec domkniętości tego zbioru. Ponieważ lipschitzowskość $\displaystyle \phi$ implikuje jej ciągłość, mamy też

$\displaystyle \phi (\alpha )\,=\,\phi {\Big (}\lim _{k\to \infty }x_{k}{\Big )}\,=\,\lim _{k\to \infty }\phi (x_{k})\,=\,\lim _{k\to \infty }x_{k}\,=\,\alpha ,$

tzn. $\displaystyle \alpha$ jest punktem stałym odwzorowania $\displaystyle \phi$. Dla jednoznaczności zauważmy, że jeśliby istniał drugi, różny od $\displaystyle \alpha$, punkt stały $\displaystyle \beta$, to mielibyśmy

$\displaystyle \|\alpha -\beta \|\,=\,\|\phi (\alpha )-\phi (\beta )\|\,\leq \,L\,\|\alpha -\beta \|.$

Stąd $\displaystyle 1<L$, co jest sprzeczne z założeniem, że

$\displaystyle \phi$ jest zwężająca.

Z powyższych rozważań otrzymujemy natychmiastowy wniosek dotyczący zbieżności iteracji prostych.

Wniosek

Przy założeniach twierdzenia Banacha, metoda iteracji prostych jest zbieżna co najmniej liniowo z ilorazem $\displaystyle L$, tzn.

$\displaystyle \|x_{k}-x^{*}\|\,\leq \,L^{k}\,\|x_{0}-x^{*}\|.$

Przykład

Dla ilustracji, rozpatrzmy równanie Keplera, gdy $\displaystyle 0<\epsilon <1$:

$\displaystyle x\,=\,M+\epsilon \sin(x),\qquad {\mbox{dla}}\qquad x\in R.$

Graficzna ilustracja równania Keplera dla $\displaystyle M=1$ i $\displaystyle \epsilon ={\frac {1}{4}}$.

W tym przypadku $\displaystyle \phi (x)=M+\epsilon \,\sin(x)$. Zauważmy, że w funkcja $\displaystyle \phi$ jest zwężająca ze stałą

$\displaystyle L\leq \max _{x}|\phi '(x)|\leq \epsilon <1.$

Ponieważ obrazem prostej przy przekształceniu $\displaystyle \phi$ jest odcinek $\displaystyle D=[M-\epsilon ,M+\epsilon ]$, to znaczy, że $\displaystyle \phi$ --- ograniczona do $\displaystyle D$ --- spełnia założenia twierdzenia Banacha o kontrakcji. Stąd istnieje dokładnie jedno rozwiązanie naszego równania w przedziale $\displaystyle D$. Rozwiązanie to może być aproksymowane z dowolnie małym błędem przy pomocy iteracji prostych, startując z dowolnego przybliżenia początkowego $\displaystyle x_{0}\in D$. Jednak, gdy $\displaystyle \epsilon \approx 1$, zbieżność może być bardzo powolna... (Wkrótce przekonasz się, że są szybsze metody).

Zaletą iteracji prostych jest fakt, że zbieżność nie zależy od wymiaru $\displaystyle n$ zadania, ale tylko od stałej Lipschitza $\displaystyle L$ (jednak w praktyce czasem sama stała Lipschitza może zależeć od wymiaru zadania...). Metoda Banacha ma szczególne zastosowanie w przypadku, gdy funkcja $\displaystyle \phi$ jest zwężająca na całym zbiorze $\displaystyle D$, tzn. $\displaystyle D_{0}=D$. Jeśli ponadto $\displaystyle D$ ma skończoną średnicę, $\displaystyle {\mbox{diam}}(D)<+\infty$, to dla osiągnięcia $\displaystyle \epsilon$-aproksymacji zera funkcji $\displaystyle f$ wystarczy wykonać

$\displaystyle k\,=\,k(\epsilon )\,=\,{\Big \lceil }{\frac {\log(\|x_{0}-x^{*}\|/\epsilon )}{\log(1/L)}}{\Big \rceil }\,=\,{\Big \lceil }{\frac {\log({\mbox{diam}}(D)/\epsilon )}{\log(1/L)}}{\Big \rceil }$

iteracji, niezależnie od $\displaystyle x_{0}$. Metody zbieżne dla dowolnego przybliżenia początkowego nazywamy zbieżnymi globalnie. Obie przedstawione dotychczas metody: bisekcji i Banacha, przy rozsądnych założeniach, są zbieżne globalnie.

Okazuje się, że metoda iteracji prostej może być --- w bardzo szczególnych przypadkach --- zbieżna szybciej niż liniowo. Z taką sytuacją będziemy mieli do czynienia, gdy rozpatrzymy metodę Newtona.

Metoda Newtona

Zarówno metoda Banacha, jak i bisekcja, są zbieżnie liniowo, co w praktyce może okazać się zbieżnością dość powolną (np. dla metody zbieżnej liniowo z ilorazem $\displaystyle 1/2$ dopiero po piątej iteracji dostajemy kolejną dokładną cyfrę wyniku). Wykorzystując więcej informacji o funkcji $\displaystyle f$, której miejsca zerowego poszukujemy, możemy istotnie przyspieszyć zbieżność metody. Ceną, jaką przyjdzie nam zapłacić, będzie utrata globalnej zbieżności.

Plik:Newton.jpg

Isaac Newton
Zobacz biografię

W dalszych rozważaniach będziemy zakładać dla uproszczenia, że dziedzina $\displaystyle D=R$.

Idea metody Newtona opiera się na popularnym wśród inżynierów pomyśle linearyzacji: zamiast szukać miejsca zerowego skomplikowanej $\displaystyle f$, przybliżmy ją linią prostą, a dla niej już umiemy znaleźć miejsce zerowe!

Startując z pewnego przybliżenia początkowego $\displaystyle x_{0}$, w kolejnych krokach metody, $\displaystyle k$-te przybliżenie $\displaystyle x_{k}$ jest punktem przecięcia stycznej do wykresu $\displaystyle f$ w punkcie $\displaystyle x_{k-1}$. Ponieważ równanie stycznej wynosi $\displaystyle y(x)=f(x_{k-1})+f'(x_{k-1})(x-x_{k-1})$, otrzymujemy wzór

Algorytm Metoda Newtona (stycznych)

---

for k = 1,2,...
	<math>\displaystyle x_k\,=\,x_{k-1}\,-\,\frac{f(x_{k-1})}{f'(x_{k-1})}</math>;

Oczywiście, aby metoda Newtona była dobrze zdefiniowana, musimy założyć, że $\displaystyle f'(x_{k-1})$ istnieje i nie jest zerem.

<flash>file=Newtononestep.swf|width=550|height=300</flash>

Postęp iteracji Newtona

Zauważmy, że metodę Newtona można traktować jako szczególny przypadek iteracji prostych, gdzie

$\displaystyle \phi (x)\,=\,x-{\frac {f(x)}{f'(x)}}.$

Widać też, że nie jest ona zbieżna globalnie.

Metoda Newtona i jej podobne należą do grupy metod zbieżnych lokalnie. Znaczy to, że zbieżność ciągu $\displaystyle \{x_{k}\}_{k}$ do zera danej funkcji $\displaystyle f$ jest zapewniona jedynie wtedy, gdy przybliżenia początkowe zostały wybrane dostatecznie blisko $\displaystyle x^{*}$.

Nawet jeśli pochodna w $\displaystyle x_{k-1}$ się nie zeruje, ciąg $\displaystyle \{x_{k}\}_{k}$ może nie zbiegać do zera funkcji $\displaystyle f$. Okazuje się jednak, że jeśli wystartujemy dostatecznie blisko rozwiązania $\displaystyle x^{*}$, to metoda Newtona jest zbieżna. Dokładniej, załóżmy najpierw, że

$\displaystyle f(x^{*})=0\quad {\mbox{ oraz }}\quad f'(x^{*})\,\neq \,0.$

Ponadto załóżmy, że $\displaystyle f$ jest dwukrotnie różniczkowalna w sposób ciągły, $\displaystyle f\in C^{2}(D)$. Rozwijając $\displaystyle \phi$ w szereg Taylora w punkcie $\displaystyle x^{*}$, otrzymujemy

$\displaystyle x_{k}-x^{*}\,=\,\phi (x_{k-1})-\phi (x^{*})\,=\,(x_{k-1}-x^{*})\phi '(x^{*})+(x_{k-1}-x^{*})^{2}\phi ''(\xi _{k})/2,$

gdzie $\displaystyle \min(x^{*},x_{k-1})\leq \xi _{k}\leq \max(x^{*},x_{k-1})$. Wobec tego, że $\displaystyle \phi '(x^{*})=f(x)f''(x)/(f'(x))^{2}=0$ i $\displaystyle \phi ''(\xi _{k})=f''(\xi _{k})/f'(\xi _{k})$, mamy

$\displaystyle x_{k}-x^{*}\,=\,(x_{k-1}-x^{*})^{2}{\frac {f''(\xi _{k})}{2f'(\xi _{k})}}.$

Zdefiniujmy liczbę

$\displaystyle R_{f}\,=\,\sup _{r\geq 0}\sup _{\{x:|x-x^{*}|\leq r\}}{\Big |}{\frac {2(x-x^{*})f''(x)}{f'(x)}}{\Big |}\,<\,1.$

Oczywiście $\displaystyle R_{f}>0$. Dla $\displaystyle x_{k-1}$ spełniającego $\displaystyle |x_{k-1}-x^{*}|\leq R<R_{f}$, mamy z poprzedniej równości

$\displaystyle |x_{k}-x^{*}|\,\leq \,q\,|x_{k-1}-x^{*}|,$

gdzie $\displaystyle q<1$ i $\displaystyle q$ zależy tylko od $\displaystyle R$.

Niech teraz $\displaystyle x^{*}$ będzie zerem $\displaystyle m$-krotnym,

$\displaystyle f(x^{*})=f'(x^{*})=\cdots =f^{(m-1)}(x^{*})=0\neq f^{(m)}(x^{*}),$

gdzie $\displaystyle m\geq 2$, oraz niech $\displaystyle f$ będzie $\displaystyle m$-krotnie różniczkowalna w sposób ciągły. Wtedy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x_k-x^* &= (x_{k-1}-x^*)\,-\,\frac{(x_{k-1}-x^*)^m \frac{f^{(m)} (\eta_k^{(1)})}{m!}}{(x_{k-1}-x^*)^{m-1} \frac{f^{(m-1)}(\eta_k^{(2)})}{(m-1)!}} \nonumber \\ &= (x_{k-1}-x^*)\left(1-\frac 1m\frac {f^{(m)}(\eta_k^{(1)})}{f^{(m)}(\eta_k^{(2)})}\right) \nonumber \\ &\approx & (x_{k-1}-x^*)\Big( 1-\frac 1m\Big), \endaligned}

o ile $\displaystyle x_{k-1}$ jest "blisko" $\displaystyle x^{*}$.

Metoda Newtona jest więc zbieżna lokalnie. Gdy $\displaystyle x_{0}$ jest zbyt daleko od rozwiązania może zdarzyć się, że iteracja Newtona zacznie nas oddalać od miejsca zerowego, co ilustruje poniższy przykład:

<flash>file=Newtononestepdiv.swf|width=550|height=300</flash>

Metoda Newtona: jeśli startujemy zbyt daleko od miejsca zerowego $\displaystyle f$, zamiast przybliżać się do niego, zaczynamy się oddalać! (gdzie będzie $\displaystyle x_{3}$?...)

Z powyższego można też wywnioskować, jaki jest charakter zbieżności metody Newtona. Dla zera jednokrotnego $\displaystyle x^{*}$ oraz $\displaystyle f''(x^{*})\neq 0$ mamy bowiem

$\displaystyle |x_{k}-x^{*}|\,\approx \,|x-x_{k-1}|^{2}{\frac {|f''(x^{*})|}{2|f'(x^{*})|}}.$

Mówimy, że zbieżność metody Newtona, gdy $\displaystyle f'(x^{*})\neq 0$ jest kwadratowa.

Stwierdzenie

Jeśli $\displaystyle f'(x^{*})\neq 0$ oraz $\displaystyle f''(x^{*})=0$ to zbieżność jest nawet szybsza. Z kolei dla zera $\displaystyle m$-krotnego (tzn. $\displaystyle f(x^{*})=f'(x^{*})=\ldots f^{(m)}(x^{*})=0$, $\displaystyle m>1$) zbieżność jest liniowa z ilorazem $\displaystyle (1-{\frac {1}{m}})$.

Metoda Newtona jest pierwszą poznaną tutaj metodą iteracyjną, która jest (dla zer jednokrotnych) zbieżna szybciej niż liniowo. Dla takich metod wprowadza się pojęcie wykładnika zbieżności, który jest zdefiniowany następująco.

Porównanie zbieżności metody bisekcji i stycznych dla równania $\displaystyle e^{x}-1=0$. Błąd kolejnych przybliżeń wyświetlany jest w skali logarytmicznej, dzięki czemu lepiej widać różnicę między zbieżnością liniową a kwadratową.

Powiemy, że metoda iteracyjna $\displaystyle \phi$ jest w klasie funkcji $\displaystyle F$ rzędu co najmniej $\displaystyle p\geq 1$, gdy spełniony jest następujący warunek. Niech $\displaystyle f\in F$ i $\displaystyle f(x^{*})=0$. Wtedy istnieje stała $\displaystyle C<\infty$ taka, że dla dowolnych przybliżeń początkowych $\displaystyle x_{0},\ldots ,x_{s-1}$ dostatecznie bliskich $\displaystyle x^{*}$, kolejne przybliżenia $\displaystyle x_{k}=\phi (x_{k-1},\ldots ,x_{k-s})$ generowane tą metodą spełniają

$\displaystyle |x_{k}-x^{*}|\,\leq \,C\,|x_{k-1}-x^{*}|^{p}.$

Ponadto, jeśli $\displaystyle p=1$ to dodatkowo żąda się, aby $\displaystyle C<1$.

Definicja

Wykładnikiem zbieżności metody iteracyjnej $\displaystyle \phi$ w klasie $\displaystyle F$ nazywamy liczbę $\displaystyle p^{*}$ zdefiniowaną równością

$\displaystyle p^{*}\,=\,\sup \,\{\,p\geq 1:\,\phi {\mbox{ jest rzędu co najmniej }}p\,\}.$

Możemy teraz sformułować następujące twierdzenie, które natychmiast wynika z poprzednich rozważań.

Twierdzenie O rzędzie zbieżności metody Newtona

Wykładnik zbieżności metody Newtona (stycznych) wynosi $\displaystyle p^{*}=2$ w klasie funkcji o zerach jednokrotnych, oraz $\displaystyle p^{*}=1$ w klasie funkcji o zerach wielokrotnych.

Zbieżność metody Newtona dla zer wielokrotnych $\displaystyle f(x)=(x-1)^{5}$ jest liniowa z ilorazem $\displaystyle {\frac {4}{5}}$ (końcowe załamanie wykresu spowodowane jest przypadkowym trafieniem w dokładne miejsce zerowe). Metoda bisekcji nie jest na to czuła i dalej zbiega z ilorazem $\displaystyle {\frac {1}{2}}$.

Metoda siecznych

Inną znaną i często używaną metodą iteracyjną, opartą na podobnym pomyśle linearyzacyjnym co metoda Newtona, jest metoda siecznych, w której zamiast przybliżenia wykresu $\displaystyle f$ przez styczną, stosuje się przybliżenie sieczną.

Metoda ta wykorzystuje więc do konstrukcji $\displaystyle x_{k}$ przybliżenia $\displaystyle x_{k-1}$ i $\displaystyle x_{k-2}$. Musimy również wybrać dwa różne punkty startowe $\displaystyle x_{0}$ i $\displaystyle x_{1}$. Ponieważ sieczna dla $\displaystyle f$ w punktach $\displaystyle x_{k-1}$ i $\displaystyle x_{k-2}$ ma wzór

$\displaystyle y(x)\,=\,{\frac {x-x_{k-2}}{x_{k-1}-x_{k-2}}}f(x_{k-1})+{\frac {x-x_{k-1}}{x_{k-2}-x_{k-1}}}f(x_{k-2}),$

otrzymujemy

Algorytm Metoda siecznych

---

for k = 1,2,...
	<math>\displaystyle x_k\,=\,x_{k-1}\,-\,\frac{x_{k-1}-x_{k-2}} {f(x_{k-1})-f(x_{k-2})}\,f(x_{k-1})</math>;
end

Zauważmy, że jeśli $\displaystyle x_{k-1}$ i $\displaystyle x_{k-2}$ są blisko siebie, to $\displaystyle x_{k}$ jest podobny do tego z metody Newtona, bowiem wtedy iloraz różnicowy przybliża pochodną $\displaystyle f$,

$\displaystyle {\frac {f(x_{k-1})-f(x_{k-2})}{x_{k-1}-x_{k-2}}}\approx f'(x_{k-1}).$

Nie wystarcza to jednak, aby osiągnąć zbieżność z wykładnikiem $\displaystyle 2$. Można pokazać, że przy podobnych założeniach o funkcji, wykładnik zbieżności metody siecznych dla zer jednokrotnych i dostatecznie gładkich funkcji wynosi $\displaystyle p^{*}={\frac {1+{\sqrt {5}}}{2}}=1.618\ldots$. Jako wariant metody Newtona, metoda siecznych jest również zbieżna lokalnie.

Porównanie zbieżności metody bisekcji, stycznych i siecznych dla równania $\displaystyle e^{x}-1=0$. Błąd kolejnych przybliżeń wyświetlany jest w skali logarytmicznej.

Niewątpliwą zaletą metody siecznych jest jednak to, że nie wymaga obliczania pochodnej funkcji (bywa, że dokładne wyznaczenie pochodnej jest niemożliwe, gdy np. funkcja jest zadana zewnętrzną procedurą, do której kodu źródłowego nie mamy dostępu; zwykle też koszt obliczenia wartości pochodnej jest wyższy od kosztu obliczenia wartości funkcji). Jest to również istotne w pakietach numerycznych, gdzie czasem nie chcemy wymagać od użytkownika czegokolwiek, oprócz podania wzoru na funkcję i przybliżonej lokalizacji miejsca zerowego.

Ponadto, często zdarza się, że wyznaczenie wartości pochodnej, $\displaystyle f'(x_{k})$, jest tak samo, albo i bardziej kosztowne od wyznaczenia wartości $\displaystyle f(x_{k})$. W takim wypadku okazuje się, że metoda siecznych --- choć wolniej zbieżna niż metoda Newtona --- dzięki temu, że jej iteracja wymaga jedynie wyznaczenia jednej wartości $\displaystyle f$, jest bardziej efektywna od metody Newtona: koszt osiągnięcia zadanej dokładności jest w takim przypadku mniejszy od analogicznego kosztu dla metody Newtona.

Jednak gdy żądane przez użytkownika dokładności są bardzo wielkie, a sama funkcja "złośliwa", metoda siecznych może cierpieć z powodu redukcji cyfr przy odejmowaniu.

Metoda Brenta

Naturalnie, uważny student zaczyna zadawać sobie pytanie, czy nie można w jakiś sposób połączyć globalnej zbieżności metody bisekcji z szybką zbieżnością metody siecznych tak, by uzyskać metodę zbieżną globalnie, a jednocześnie istotnie szybciej niż liniowo.

Okazuje się, że można to zrobić, wprowadzając metodę opartą na trzech punktach lokalizujących miejsce zerowe: dwóch odcinających zero tak jak w metodzie bisekcji i trzecim, konstruowanym np. jak w metodzie stycznych. W kolejnej iteracji wymieniamy jeden z punktów albo wedle metody siecznych (i wtedy zapewne szybciej zbliżamy się do zera), albo wykonując bisekcję (aby zagwarantować sobie, że w wiadomym przedziale miejsce zerowe rzeczywiście się znajduje).

Ten prosty pomysł metody hybrydowej wymaga jednak subtelnego dopracowania. Zostało to zrobione w 1973 roku przez Richarda Brenta. Funkcja MATLABa (i Octave'a) fzero implementują właśnie metodę Brenta. Autorem implementacji w Octave jest ówczesny student matematyki na Uniwersytecie Warszawskim, Łukasz Bodzon. Fortranowski kod metody Brenta można znaleźć także w Netlibie. Inną funkcją Octave'a służącą rozwiązywaniu równań nieliniowych jest fsolve:

octave:1> [X, MSG, INFO] = fsolve ('cos', 1) X = 1.5708 MSG = 1 INFO = solution converged within specified tolerance octave:2> cos(X) ans = 6.1230e-17

Metody dla układów równań nieliniowych

Niektóre z poznanych metod można łatwo rozszerzyć na przypadek układu $\displaystyle N$ równań z $\displaystyle N$ niewiadomymi, to znaczy

$\displaystyle F(x)=0,$

gdzie $\displaystyle F:R^{N}\rightarrow R^{N}$.

Metoda Banacha

Jak pamiętamy, metodę Banacha sformułowaliśmy od razu dla zagadnienia wielowymiarowego. Analiza i własności metody są zatem już omówione.

Wielowymiarowa metoda Newtona

Okazuje się, że metodę Newtona można uogólnić na przypadek układu $\displaystyle N$ równań nieliniowych z $\displaystyle N$ niewiadomymi. Zapiszmy wzór na skalarną metodę Newtona odrobinę inaczej:

$\displaystyle x_{k+1}=x_{k}-[F'(x_{k})]^{-1}\,F(x_{k}).$

Niezwykłe jest, że taki wzór nie tylko ma sens w przypadku, gdy $\displaystyle F:R^{N}\rightarrow R^{N}$ (wtedy $\displaystyle F'(x_{k})$ jest macierzą Jakobianu $\displaystyle F$ w punkcie $\displaystyle x_{k}$), ale dodatkowo ta metoda zachowuje wszystkie własności metody stycznych dla przypadku skalarnego:

Twierdzenie O zbieżności wielowymiarowej metody Newtona

Załóżmy, że $\displaystyle F:R^{N}\rightarrow R^{N}$ i istnieje $\displaystyle x^{*}\in R^{N}$ taki, że

$\displaystyle F(x^{*})=0.$

Załóżmy ponadto, że $\displaystyle F$ jest różniczkowalna, a jej pochodna $\displaystyle F':R^{N}\rightarrow R^{N\times N}$ jest lipschitzowska i dodatkowo

$\displaystyle F'(x^{*}){\mbox{ jest nieosobliwa}}.$

Wówczas, jeśli tylko $\displaystyle x_{0}$ jest dostatecznie blisko rozwiązania $\displaystyle x^{*}$, to ciąg kolejnych przybliżeń $\displaystyle x_{k}$, generowany wielowymiarową metodą Newtona, jest zbieżny do $\displaystyle x^{*}$. Co więcej, szybkość zbieżności jest kwadratowa.

Implementacja wielowymiarowej metody Newtona

Implementując wielowymiarową metodę Newtona, musimy dysponować nie tylko funkcją obliczającą $\displaystyle N$ współrzędnych wektora wartości $\displaystyle F$, ale także funkcją wyznaczającą $\displaystyle N^{2}$ elementów macierzy pochodnej $\displaystyle F$ w zadanym punkcie $\displaystyle x\in R^{N}$. Zwróćmy uwagę na to, że w implementacji metody nie trzeba wyznaczać $\displaystyle F'(x_{k})^{-1}$, tylko rozwiązać układ równań:

Algorytm Wielowymiarowa metoda Newtona

---

while (!stop)
{
	rozwiąż (względem <math>\displaystyle s</math>) układ równań liniowych <math>\displaystyle F'(x_k)\, s = -F(x_k)</math>;
	<math>\displaystyle x_{k+1}</math> = <math>\displaystyle x_k</math> + <math>\displaystyle s</math>;
}

O tym, jak skutecznie rozwiązywać układy równań liniowych, dowiesz się z kolejnych wykładów. Dowiesz się także, dlaczego nie należy w implementacji korzystać z wyznaczonej explicite macierzy odwrotnej do macierzy Jakobianu.

Literatura

W celu dogłębnego zapoznania się z omawianym na wykładzie materiałem, przeczytaj rozdział 3 w

• D. Kincaid, W. Cheney Analiza numeryczna, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 83-204-3078-X.

Rozdziały 3.5 i 3.6 nie są obowiązkowe.

Wiele wariantów metod rozwiązywania układów równań nieliniowych jest przedstawionych w znakomitej monografii

• C.T.Kelley, Iterative Solution of Systems of Linear and Nonlinear Equations, SIAM, 1995.

Opis metody Brenta znajdziesz w książce

• R. Brent, Algorithms for Minimization Without Derivatives, Prentice-Hall, 1973.