Zagadnienia

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=Fxk-1Fxk 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ć Fx 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=Fxk-1Fxk; {zaczynamy od standardowej poprawki z metody Newtona}
TEST: x=xk-s;  {wypróbowujemy poprawkę}
if Fx<Fxk 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 Fx<Fxk może być zbyt łagodne i dlatego raczej stosuje się tzw. regułę Armijo:

Metoda nawrotów z regułą Armijo
s=Fxk-1Fxk;
λ=1 ;     {mnożnik poprawki}
TEST: x=xk-λs;  {wypróbowujemy poprawkę}
if Fx<1-αλFxk 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 Fxk 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 Fx0 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λ=Fxk-λ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λ=Fxk-λs22,

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

g0=Fxk22 (z poprzedniego kroku),
g0=g(λ)|λ=0=-2F(xk)TF(xk)s,
g1=Fxk-s22.

Zauważmy, że jeśli s było wyznaczone metodą Newtona, to wtedy faktycznie g0<0, a więc Fxk 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=-12g0g1-g0-g0.
Ćwiczenie 12.1

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

Wskazówka: 

Wspominany wielomian interpolacyjny Hermite'a dla g to

wλ=g0+g0λ+g1-g0-g0λ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 t0,1,

Hx,t=0,(12.1)

gdzie H:D×0,1RN, 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ę txt taką, że

Hxt,t=0.

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

Hx*,t*=0.

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

Hxt,t=0.

Ponadto, xC1U oraz

xt=-Hxxt,t-1Htxt,t dla tU.(12.2)

Mówimy w takim przypadku, że xt 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*=xt*. Naszym zadaniem jest wyznaczenie xt*+h, gdzie h>0 jest małe15W szczególności, t*+hU.. Odpowiada to wziętej z życia sytuacji, gdy chcemy prześledzić przebieg gałęzi xt, próbkując jej wartości dla kolejnych (zapewne gęsto rozmieszczonych w U) wartości parametru t.

Naturalnie, do wyznaczenia xt*+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 xt*+h tak, by metoda Newtona od razu startowała z dobrego przybliżenia początkowego? Ze względu na regularny charakter gałęzi xt nietrudno zgadnąć, że niezłym przybliżeniem dla xt*+h mogłoby być x0=x*. Rzeczywiście, niech

l=maxtt*,t*+hxt.

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

xt*+h-x*lh,

więc jeśli h jest dostatecznie małe względem l, to x0 będzie dostatecznie blisko xt*+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 xt*=x*, to przybliżoną wartość xt*+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 x0xt*+h położymy

x0=xt*+hxt*=x*-hHxx*,t*-1Htx*,t*.

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

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

xt*+h-x0=xt*+h-xt*-hxt*=01hxt*+τh-xt*dτ,

skąd, oznaczając l~=maxtt*,t*+hx′′t, dostajemy na mocy lematu o wartości średniej oszacowanie

xt*+h-x001hxt*+τh-xt*dτl~2h2.
Ć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 xt dla tU. 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

Fx=0,

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

Hx,1=Fx

oraz

Hx,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 Hx,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ć

Hx,t=tFx+1-tF~x,

albo położyć jeszcze prostszą

Hx,t=tFx0+Fx-Fx0 dla zadanego x0,

zbyt proste, aby były skuteczne.

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

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.