Zagadnienia

12.1 Metoda nawrotów
- 12.1.1 Prosta metoda nawrotów
- 12.1.2 Wielomianowe nawroty
12.2 Metody kontynuacji
- 12.2.1 Wyznaczanie dobrego przybliżenia początkowego dla metody typu Newtona
- 12.2.2 Metoda homotopii

12. Globalizacja zbieżności

Zarówno metoda Newtona, jak i omawiane przez nas jej modyfikacje, mogą zawieść (to znaczy: mogą nie być zbieżne lub dobrze określone), gdy początkowe przybliżenie x0 będzie zbyt daleko od rozwiązania i założenia standardowe nie będą spełnione w x0. Ponieważ zwykle trudno wiedzieć a priori, czy jesteśmy dostatecznie blisko rozwiązania, opracowano szereg mniej lub bardziej heurystycznych technik globalizacji zbieżności metod typu Newtona, pozwalających w końcu dotrzeć w takie pobliże rozwiązania, w którym już nastąpi szybka zbieżność.

Podobny charakter ma inny — jakże często spotykany w zastosowaniach — problem: równanie nieliniowe z parametrem, w którym celem jest wyznaczenie nie jednego, jak dotychczas, ale całej rodziny rozwiązań (w zależności od parametru). Przykładowo, mogłaby nas interesować charakterystyka prądowo–napięciowa pewnego układu elektronicznego o nieliniowych własnościach: wtedy dla zadanych wartości napięcia musielibyśmy rozwiązać równanie nieliniowe, określające prąd w obwodzie. Ponieważ aby narysować dokładny wykres takiej charakterystyki, należałoby próbkować wartości natężenia w bardzo wielu (powiedzmy, kilkuset) podanych napięciach — dobrze byłoby te kilkaset układów równań rozwiązać możliwie efektywnie. Pokażemy więc pożyteczną metodę wyznaczania bardzo dobrych punktów startowych x0 w przypadku, gdy zależność rozwiązania od parametru jest dostatecznie regularna.

Co ciekawe, tę technikę można wykorzystać także w celu globalizacji zbieżności metody typu Newtona dla pojedynczego równania nieliniowego!

12.1. Metoda nawrotów

Przypomnijmy, że rozważane przez nas metody iteracyjne są postaci

xk+1=xk-s.

Zacznijmy od prostej obserwacji, że — gdy xk jest daleko od rozwiązania — poprawka s=F′⁢xk-1⁢F⁢xk jest co prawda słuszna co do kierunku (idziemy wszak w stronę, w którą funkcja lokalnie maleje), ale być może przesadna co do wielkości i spowodować, że w następnej iteracji wartość residuum wzrośnie, a nie zmaleje…

Metoda nawrotów (ang. backtracking) reprezentuje prostą strategię, polegającą na zachowaniu kierunku poprawki i następnie na ewentualnym jej skróceniu tak, by residuum w xk+1 było mniejsze od residuum w xk: dzięki temu zawsze będziemy redukować F⁢x w nadziei, że tym samym będziemy zbliżać się do rozwiązania.

12.1.1. Prosta metoda nawrotów

W swojej najbardziej podstawowej (raczej nie stosowanej) postaci, metoda nawrotów wyznacza poprawkę s następująco:

Metoda nawrotów, wersja bazowa

s=F′⁢xk-1⁢F⁢xk; {zaczynamy od standardowej poprawki z metody Newtona}

TEST: x=xk-s; {wypróbowujemy poprawkę}

if F⁢x<F⁢xk then

xk+1=x; {akceptujemy poprawkę}

else begin

s=s/2; {skracamy poprawkę i ponownie sprawdzamy}

goto TEST;

end

W praktyce powyższe kryterium akceptacji poprawki F⁢x<F⁢xk może być zbyt łagodne i dlatego raczej stosuje się tzw. regułę Armijo:

Metoda nawrotów z regułą Armijo

s=F′⁢xk-1⁢F⁢xk;

λ=1 ; {mnożnik poprawki}

TEST: x=xk-λ⁢s; {wypróbowujemy poprawkę}

if F⁢x<1-α⁢λ⁢F⁢xk then

xk+1=x; {akceptujemy poprawkę}

else begin

λ=λ/2; {zmniejszamy mnożnik i ponownie sprawdzamy}

goto TEST;

end

Parametr relaksacyjny α dobiera się na wyczucie, zwykle trochę poniżej jedności. Oczywiście, nie można dać się zwariować i stosować zbyt małych mnożników λ, bo prowadziłoby to do stagnacji metody (lepiej potraktować to jako informację o kłopotach ze zbieżnością i następnie restartować metodę z zupełnie innym x0).

Metoda nawrotów, jakkolwiek często istotnie poprawia charakter zbieżności metody Newtona, może także załamać się, gdy F′⁢xk stanie się osobliwa. Nie musi także gwarantować zbieżności do prawdziwego rozwiązania, gdyż może zdarzyć się, że na przykład

iteracje xk dążą do lokalnego ekstremum F, a nie do miejsca zerowego;
xk→∞ (bo na przykład F⁢x→0 dla x→∞).

12.1.2. Wielomianowe nawroty

Zamiast stosować dość prymitywną regułę wyznaczania nowego mnożnika poprawki: λ=λ/2, można wybierać nowe λ jako argument minimalizujący wartość wielomianu interpolacyjnego dla funkcji g⁢λ=F⁢xk-λ⁢s, opartego na węzłach będących poprzednio wybieranymi wartościami λ. Taką strategię nazywa się strategią nawrotów wielomianowych. Inna metoda — obszaru ufności (ang. trust region) — pozwala dobrać nie tylko mnożnik poprawki, ale dodatkowo nieco zmienić jej kierunek; jest więc nieco bardziej elastyczna, ale za cenę wyższego kosztu.

Przykład 12.1 (Metoda wielomianowych nawrotów oparta na dwóch punktach)

Wybierając

g⁢λ=F⁢xk-λ⁢s22,

po teście λ=1, dysponujemy następującymi trzema(!) wartościami g:

	g⁢0	=F⁢xk22⁢ (z poprzedniego kroku),
	g′⁢0	=g′(λ)\|λ=0=-2F(xk)TF′(xk)s,
	g⁢1	=F⁢xk-s22.

Zauważmy, że jeśli s było wyznaczone metodą Newtona, to wtedy faktycznie g′⁢0<0, a więc F⁢xk maleje w kierunku s. Na podstawie tych trzech wartości możemy skonstruować wielomian interpolacyjny (Hermite'a) drugiego stopnia oraz wyznaczyć λnowe, minimalizujące ten wielomian:

λnowe=-12⁢g′⁢0g⁢1-g⁢0-g′⁢0.

Ćwiczenie 12.1

Wyprowadź powyższy wzór na λnowe.

Wskazówka:

Wspominany wielomian interpolacyjny Hermite'a dla g to

w⁢λ=g⁢0+g′⁢0⁢λ+g⁢1-g⁢0-g′⁢0⁢λ2.

Dla metody Broydena także można sformułować regułę podobną do reguły Armijo dla metody Newtona, [9].

Jeszcze innym sposobem globalizacji zbieżności metody Newtona może być wykorzystanie metody kontynuacji — o czym w następnym rozdziale.

12.2. Metody kontynuacji

W wielu praktycznych zastosowaniach mamy do czynienia nie z jednym równaniem nieliniowym, ale z całą rodziną równań, indeksowaną pewnym parametrem (lub zestawem parametrów). Dla ustalenia uwagi, rozważmy więc rodzinę równań indeksowaną parametrem t∈0,1,

H⁢x,t=0,

(12.1)

gdzie H:D×0,1→RN, gdzie D jest otwartym niepustym podzbiorem RN.

W ogólności zbiór wszystkich rozwiązań (12.1) może być dziwaczny, ale my zajmiemy się regularnym — spotykanym w niektórych zastosowaniach — przypadkiem, kiedy możemy lokalnie jednoznacznie określić funkcję t↦x⁢t taką, że

H⁢x⁢t,t=0.

Dokładniej, załóżmy, że H∈C1⁢D×0,1 i dla pewnego parametru t*∈0,1 i dla pewnego x*∈D zachodzi

H⁢x*,t*=0.

Jeśli dodatkowo założymy, że pochodna cząstkowa Hx⁢x*,t* jest nieosobliwa, to na mocy twierdzenia o funkcji uwikłanej istnieje U=t*-ϵ,t*+ϵ, gdzie ϵ>0, takie, że dla t∈U jest jednoznacznie wyznaczone rozwiązanie x⁢t,

H⁢x⁢t,t=0.

Ponadto, x∈C1⁢U oraz

x′⁢t=-Hx⁢x⁢t,t-1⁢Ht⁢x⁢t,t⁢⁢ dla ⁢t∈U.

(12.2)

Mówimy w takim przypadku, że x⁢t jest regularną gałęzią rozwiązań (12.1), przechodzącą przez x*,t*. W dalszym ciągu zajmiemy się właśnie metodami wyznaczania takiej regularnej gałęzi rozwiązań.

12.2.1. Wyznaczanie dobrego przybliżenia początkowego dla metody typu Newtona

Przypuśćmy, że dla parametru t* wyznaczyliśmy już rozwiązanie x*=x⁢t*. Naszym zadaniem jest wyznaczenie x⁢t*+h, gdzie h>0 jest małe¹⁵W szczególności, t*+h∈U.. Odpowiada to wziętej z życia sytuacji, gdy chcemy prześledzić przebieg gałęzi x⁢t, próbkując jej wartości dla kolejnych (zapewne gęsto rozmieszczonych w U) wartości parametru t.

Naturalnie, do wyznaczenia x⁢t*+h możemy użyć dowolnej z wcześniej opisywanych metod — ale czy nie udałoby się wykorzystać informacji uzyskanej dla t* w celu wyznaczenia przybliżenia x0 dla x⁢t*+h tak, by metoda Newtona od razu startowała z dobrego przybliżenia początkowego? Ze względu na regularny charakter gałęzi x⁢t nietrudno zgadnąć, że niezłym przybliżeniem dla x⁢t*+h mogłoby być x0=x*. Rzeczywiście, niech

l=maxt∈t*,t*+h⁡x′⁢t.

Wtedy (na mocy lematu o wartości średniej 9.1)

x⁢t*+h-x*≤l⁢h,

więc jeśli h jest dostatecznie małe względem l, to x0 będzie dostatecznie blisko x⁢t*+h, by zagwarantować szybką (kwadratową) zbieżność metody Newtona (pod oczywistym warunkiem, że spełnione są założenia standardowe, por. rozdział 9.3.1). Ten sposób wyboru x0, zaproponowany przez Poincaré'go, nazywa się klasyczną metodą kontynuacji.

Można jednak, niewiele większym kosztem, uzyskać jeszcze lepsze przybliżenie początkowe dla metody Newtona (lub podobnej).

Ponieważ zachodzi (12.2) z warunkiem początkowym x⁢t*=x*, to przybliżoną wartość x⁢t*+h możnaby uzyskać, stosując jakiś schemat różnicowy dla (12.2). Na przykład, korzystając dla (12.2) z jawnego schematu Eulera z krokiem h, jako x0≈x⁢t*+h położymy

x0=x⁢t*+h⁢⁢x′⁢t*=x*-h⋅Hx⁢x*,t*-1⁢Ht⁢x*,t*.

Ten sposób wyznaczania początkowego przybliżenia x⁢t*+h nazywa się kontynuacją wzdłuż stycznej. Aby więc wyznaczyć x0, musimy rozwiązać układ równań z macierzą pochodnej Hx⁢x*,t* (wyznaczoną dla poprzednio znalezionego rozwiązania — to przecież macierz występująca w iteracji Newtona!) no i wyznaczyć wartość Ht⁢x*,t* — co zwykle nie jest zbyt trudne analitycznie (w przeciwnym przypadku, możemy zadowolić się, jak zwykle, różnicową aproksymacją).

Jeśli x∈C2⁢U, to jakość tak uzyskanego przybliżenia jest znacznie wyższa niż w przypadku klasycznej metody kontynuacji. Rzeczywiście,

x⁢t*+h-x0=x⁢t*+h-x⁢t*-h⁢⁢x′⁢t*=∫01h⁢⁢x′⁢t*+τ⁢h-x′⁢t*⁢⁢d⁢τ,

skąd, oznaczając l~=maxt∈t*,t*+h⁡x′′⁢t, dostajemy na mocy lematu o wartości średniej oszacowanie

x⁢t*+h-x0≤∫01h⁢⁢x′⁢t*+τ⁢h-x′⁢t*⁢⁢d⁢τ≤l~2⁢h2.

Ćwiczenie 12.2

Dlaczego w metodzie kontynuacji wzdłuż stycznej, zastosowanie schematu niejawnego do rozwiązywania (12.2) nie miałoby większego sensu?

Rozwiązanie:

Bo, po pierwsze, wymagałoby rozwiązania podobnego równania nieliniowego, a po drugie — byłoby niepotrzebnie kosztowne. Przecież nas i tak interesuje tylko wykonanie jednego kroku takiego schematu!

W świetle powyższego, nabiera znaczenia kwestia doboru właściwej wielkości kroku kontynuacji h. Na razie dysponujemy jedynie informacją jakościową, że ,,dla h dostatecznie małego”, dostaniemy zbieżność. Jednak w praktyce chcielibyśmy używać rozsądnie małych (czytaj: nie za małych) h — bo obniża to koszt wyznaczenia aproksymacji x⁢t dla t∈U. Istnieją na szczęście strategie kontroli kroku kontynuacji h [5], analogiczne jak w przypadku równań różniczkowych, ale dostosowane do tej konkretnej sytuacji: zagwarantowania (kwadratowej) zbieżności metody Newtona startującej z x0.

Warto także wiedzieć, że istnieją bardziej wyrafinowane techniki kontynuacji, które pozwalają przejść przez punkty krytyczne gałęzi (w których pochodna po t jest nieokreślona)

12.2.2. Metoda homotopii

Jeśli trudno znaleźć dobry punkt startowy dla metody Newtona dla równania

F⁢x=0,

możemy spróbować sztucznie wprowadzić parametr t∈0,1 i określić równanie (12.1) tak, by

H⁢x,1=F⁢x

oraz

H⁢x,0=F~⁢x,

przy czym dla F~ jesteśmy w stanie łatwo wygenerować dobry punkt startowy. Jeśli tak, to postępując zgodnie z metodą kontynuacji — rozwiązując H⁢x,ti=0 dla kolejnych wartości ti, poczynając od zera — dojdziemy w końcu do ti=1, i tym samym wygenerujemy dlań dobre przybliżenie startowe.

Taka metoda globalizacji zbieżności metody Newtona — przez wykorzystanie kontynuacji dla odpowiednio spreparowanej rodziny zadań z parametrem — nosi nazwę metody homotopii, gdyż w sposób ciągły przeprowadzamy zadanie ,,łatwe” na zadanie ,,trudne”. Należy jednak pamiętać, że w praktyce ta metoda może, ale nie musi się sprawdzić, gdyż znalezienie dobrej homotopii H może być sprawą znacznie trudniejszą niż znalezienie dobrego x0! Zazwyczaj ,,naturalne” pomysły na H, np. wziąć ,,bardzo łatwą” F~⁢x i określić

H⁢x,t=t⁢F⁢x+1-t⁢F~⁢x,

albo położyć jeszcze prostszą

H⁢x,t=t⁢F⁢x0+F⁢x-F⁢x0⁢⁢ dla zadanego ⁢x0,

są zbyt proste, aby były skuteczne.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.