Zagadnienia

11. Metoda Broydena

W przypadku jednowymiarowym, metoda siecznych:

xk+1=xk-fxk-fxk-1xk-xk-1-1fxk

jest interesującą alternatywą dla metody Newtona: jej zbieżność jest superliniowa (dokładniej: wykładnicza z wykładnikiem p=1+521.61 — a więc tylko trochę gorsza niż metody stycznych), a za to istotny koszt jednej iteracji ogranicza się do wyznaczenia tylko jednej nowej wartości funkcji! (Pochodna jest niepotrzebna).

Uogólnienie pomysłu metody siecznych na przypadek wielowymiarowy tak, by zachować jej dwie główne cechy: superliniową zbieżność oraz niski koszt iteracji (nie wymagający w szczególności wyznaczania pochodnej ani obliczania dodatkowych wartości funkcji) nie jest trywialne i zostało zrealizowane w metodzie Broydena. Iterację Broydena określimy wzorem

xk+1=xk-Ak-1Fxk,

gdzie A0=Fx0 (lub jest jej przybliżeniem wyznaczonym za pomocą ilorazów różnicowych), a kolejne macierze Ak wyznaczamy według wzoru

Ak+1=Ak+1skTskFxk+1skT,
sk=xk+1-xk.

(Zauważmy, że sk jest jawnie wyznaczane w trakcie algorytmu, gdyż sk jest rozwiązaniem równania poprawki, Aksk=-Fxk.)

Jak widzimy z powyższej definicji, koszt jednej iteracji metody Broydena jest niewygórowany. Rzeczywiście, jeśli z poprzedniego kroku znamy rozkład LU lub QR macierzy Ak-1, to wyznaczenie rozkładu Ak, która jest postaci Ak+1=Ak+ukvkT, jest zadaniem wyznaczenia rozkładu dla modyfikacji macierzy rzędu 1 — a na to są znane (tanie!) algorytmy [7], [10], działające kosztem ON2 flopów14W metodzie Broydena nie ma więc — wbrew pozorom — potrzeby jawnego wyznaczania macierzy Ak!, o czym szerzej mówimy w poniższym rozdziale.

11.1. Realizacja metody Broydena

Oczywiście, gdybyśmy tylko skorzystali wprost ze wzoru

Ak+1=Ak+1skTskFxk+1skT,

to co prawda wyznaczenie Ak kosztowałoby nas tylko ON2 flopów, ale za to rozkład macierzy Ak musiałby nas kosztować ON3. Jednak, jako że macierz Ak+1 różni się od Ak tylko o macierz rzędu jeden, będziemy mogli od razu przykładać odwrotność macierzy Ak do wektora na podstawie rozkładu macierzy A0, kosztem jedynie ON2+kN.

Algorytm działający w oparciu o aktualizację macierzy odwrotnej do Ak może być mniej stabilny numerycznie od algorytmu używającego aktualizacji rozkładu QR (zob. [10, 10.3.1, Algorytm 2]) macierzy Ak i dlatego wskazuje się sposoby kontrolowania przebiegu pracy tej metody [5], którymi tutaj nie będziemy się zajmować.

Aby tanio odwracać kolejne macierze Ak, wykorzystamy wzór Shermana–Morrisona, którego wyprowadzeniu było poświęcone ćwiczenie 5.24.

Stwierdzenie 11.1 (wzór Shermana–Morrisona)

Niech B=A+uvT, gdzie A jest macierzą nieosobliwą N×N oraz u,vRN. B jest nieosobliwa wtedy i tylko wtedy, gdy 1+vTA-1u0 i wówczas

B-1=I-A-1uvT1+vTA-1uA-1.

U nas

Ak+1=Ak+ukvkT,

gdzie uk=Fxk+1/sk2, vk=sk/sk2. Oznaczając dodatkowo

zk=Ak-1uk=Ak-1Fxk+1/sk2,wk=zk1+vkTzk,

ze wzoru Shermana–Morrisona mamy więc

Ak+1-1=I-wkvkTAk-1==I-wkvkTI-w0v0TA0-1,(11.1)

Wydawałoby się więc, że by skorzystać z powyższego wzoru, należałoby pamiętać dodatkowe wektory uj,wj,vj dla j=0,,k. W rzeczywistości jednak możemy dalej wymasować powyższe zależności i wyeliminować te wektory, ograniczając się jedynie do pamiętania sekwencji poprawek s0,,sk.

Rzeczywiście, w metodzie Broydena interesuje nas przecież nie sama macierz Ak+1-1, tylko nowa wartość poprawki, sk+1=-Ak+1-1Fxk+1. Tymczasem, korzystając z definicji zk i vk,

-sk+1=Ak+1-1F(xk+1)=(I-wkvkT)Ak-1Fxk+1=sk2zk=sk2(I-zk1+vkTzkvkT)zk
=sk2zk(1-vkTzk1+vkTzk)=sk2zk11+vkTzk=sk2wk.

Stąd dostajemy elegancką zależność wk=-sk+1/sk2, którą możemy podstawić z powrotem do (11.1) i otrzymać

-sk+1=Ak+1-1Fxk+1=I+sk+1skTsk22Ak-1Fxk+1.(11.2)

Na tej podstawie (sk+1 występuje po obu stronach tej równości!) konkludujemy, że

-sk+1=Ak-1Fxk+1/1+skTAk-1Fxk+1sk22.(11.3)
Ćwiczenie 11.1

Wykaż, że jeśli Ak+1 jest nieosobliwa, to wyrażenie pojawiające się w mianowniku wzoru na sk+1 jest różne od zera.

Wskazówka: 

Zauważ, że skTAk-1Fxk+1sk22=vkTAk-1uk i skorzystaj ze wzoru Shermana–Morrisona.

Ćwiczenie 11.2

Zaimplementuj metodę Broydena z zastosowaniem wzoru Shermana–Morrisona.

Rozwiązanie: 

Aby sensownie wyznaczać sk+1, musimy zastanowić się chwilę, jak wyznaczać wektor

pk=Ak-1Fxk+1,

występujący we wzorze (11.3). Zauważmy, że na mocy (11.1),

Ak-1=j=0k-1I+sj+1sjTsj22A0-1,

a więc wyznaczenie pk daje się zrealizować w pętli polegającej na kolejnym mnożeniu przez macierze postaci I+sj+1sjTsj22. Pamiętajmy, by macierzy postaci I+uvT nigdy nie formować explicite, a w zamian wyznaczać iloczyn I+uvTp zgodnie z wzorem

p+uvTp,

co będzie kosztowało tylko ON flopów. Szkielet algorytmu mógłby więc wyglądać następująco:

Bazowa implementacja metody Broydena
x=x0; k = 0;
A0=Fx;
wyznacz rozkład LU lub QR macierzy A0;
rozwiąż, korzystając z gotowego rozkładu, A0s0=-Fx;
while not stop do
begin
  x=x+s;
  oblicz Fx;
  k = k+1;
  rozwiąż, korzystając z gotowego rozkładu, A0s=-Fx;
  for j = 0 to k-1
  begin
    s=s+sj+1sjTs/sj22;
  end
  s=s/1+sk-1Ts/sk-122;
  sk=s;
end

Jak widać, musimy pamiętać czynniki rozkładu A0 (samego A0 już nie) oraz wszystkie pośrednie poprawki s0,s1,.

11.2. Zbieżność metody Broydena

Poniższe twierdzenie gwarantuje superliniową zbieżność metody Broydena nawet w przypadku, gdy A0Fx0.

Twierdzenie 11.1 (o zbieżności metody Broydena)

Przy standardowych założeniach, istnieją δ oraz δ0 (dostatecznie małe) takie, że jeśli x0Kx*,δ oraz A0-Fx*<δ0, to metoda Broydena startująca z x0 i A0 jest dobrze określona oraz xkx* superliniowo.

Dowód

Zobacz np. [9].

Ćwiczenie 11.3

Wykaż, że jeśli A0=Fx0 oraz x0 jest dostatecznie blisko x*, to powyższe twierdzenie zachodzi.

Rozwiązanie: 

To oczywiste, gdyż

A0-Fx*=Fx0-Fx*Lx0-x*Lδ.

Biorąc δ, δ0 z twierdzenia o zbieżności metody Broydena i ewentualnie dodatkowo zmniejszając δ tak, by jednocześnie Lδ<δ0, dostajemy

A0-Fx*Lδ<δ0,

co gwarantuje spełnienie wszystkich założeń twierdzenia 11.1.

Ćwiczenie 11.5

Wykaż, że macierze Ak generowane w metodzie Broydena spełniają równanie siecznych,

Ak+1xk+1-xk=Fxk+1-Fxk.
Rozwiązanie: 

Z definicji

Ak+1=Ak+1skTskFxk+1skT,

więc mnożąc przez xk+1-xk=sk mamy

Ak+1sk=Aksk+Fxk+1=-Fxk+Fxk+1.
Ćwiczenie 11.6

Niech ARN×N oraz s,yRN przy czym s0. Wtedy

minBRN×N:Bs=yA-B2

jest osiągane dla

B*=A+y-AssTsTs.

Znaczy to, że metoda Broydena generuje ciąg macierzy Ak taki, że Ak+1 jest najbliższe Ak w normie spektralnej wśród wszystkich macierzy spełniających równanie siecznych

Akxk-xk-1=Fxk-Fxk-1.
Rozwiązanie: 

Wystarczy pokazać, że dla dowolnej innej macierzy B spełniającej Bs=y, norma różnicy B-A nie jest mniejsza niż dla B*-A. Mamy

B*-A=y-AssTsTs=Bs-AssTsTs=B-AssTsTs,

skąd

B*-A2B-A2ssT/s22=B-A2.

Ostatnia równość wynika z faktu, że xyT2=x2y2.

Na zakończenie wspomnijmy, że — podobnie jak w przypadku modyfikacji metody Newtona — rozsądne jest wykonać co pewną liczbę iteracji restart metody Broydena, to znaczy: uruchomić procedurę na nowo, biorąc za punkt początkowy ostatnio wyznaczone przybliżenie. W ten sposóby spowodujemy aktualizację macierzy pochodnej (tej z ,,zerowego” kroku) oraz zmniejszymy liczbę czynników iloczynu macierzy rzędu jeden koniecznych do obliczenia poprawki.

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.