Zagadnienia

11.1 Realizacja metody Broydena
11.2 Zbieżność metody Broydena

11. Metoda Broydena

W przypadku jednowymiarowym, metoda siecznych:

xk+1=xk-f⁢xk-f⁢xk-1xk-xk-1-1⁢f⁢xk

jest interesującą alternatywą dla metody Newtona: jej zbieżność jest superliniowa (dokładniej: wykładnicza z wykładnikiem p=1+52≈1.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-1⁢F⁢xk,

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

	Ak+1	=Ak+1skT⁢sk⁢F⁢xk+1⁢skT,
	sk	=xk+1-xk.

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

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+uk⁢vkT, jest zadaniem wyznaczenia rozkładu dla modyfikacji macierzy rzędu 1 — a na to są znane (tanie!) algorytmy [7], [10], działające kosztem O⁢N2 flopów¹⁴W 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+1skT⁢sk⁢F⁢xk+1⁢skT,

to co prawda wyznaczenie Ak kosztowałoby nas tylko O⁢N2 flopów, ale za to rozkład macierzy Ak musiałby nas kosztować O⁢N3. 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 O⁢N2+k⁢N.

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+u⁢vT, gdzie A jest macierzą nieosobliwą N×N oraz u,v∈RN. B jest nieosobliwa wtedy i tylko wtedy, gdy 1+vT⁢A-1⁢u≠0 i wówczas

B-1=I-A-1⁢u⁢vT1+vT⁢A-1⁢u⁢A-1.

U nas

Ak+1=Ak+uk⁢vkT,

gdzie uk=F⁢xk+1/sk2, vk=sk/sk2. Oznaczając dodatkowo

zk=Ak-1⁢uk=Ak-1⁢F⁢xk+1/sk2,⁢wk=zk1+vkT⁢zk,

ze wzoru Shermana–Morrisona mamy więc

Ak+1-1=I-wk⁢vkT⁢Ak-1=…=I-wk⁢vkT⁢⋯⁢I-w0⁢v0T⁢A0-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-1⁢F⁢xk+1. Tymczasem, korzystając z definicji zk i vk,

	-sk+1	=Ak+1-1F(xk+1)=(I-wkvkT)Ak-1⁢F⁢xk+1︸=sk2⁢zk=∥sk∥2(I-zk1+vkT⁢zkvkT)zk
		=∥sk∥2zk(1-vkT⁢zk1+vkT⁢zk)=∥sk∥2zk11+vkT⁢zk=∥sk∥2wk.

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-1⁢F⁢xk+1=I+sk+1⁢skTsk22⁢Ak-1⁢F⁢xk+1.

(11.2)

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

-sk+1=Ak-1⁢F⁢xk+1/1+skT⁢Ak-1⁢F⁢xk+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 skT⁢Ak-1⁢F⁢xk+1sk22=vkT⁢Ak-1⁢uk 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-1⁢F⁢xk+1,

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

Ak-1=∏j=0k-1I+sj+1⁢sjTsj22⁢A0-1,

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

p+u⁢vT⁢p,

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

Bazowa implementacja metody Broydena

x=x0; k = 0;

A0=F′⁢x;

wyznacz rozkład LU lub QR macierzy A0;

rozwiąż, korzystając z gotowego rozkładu, A0⁢s0=-F⁢x;

while not stop do

begin

x=x+s;

oblicz F⁢x;

k = k+1;

rozwiąż, korzystając z gotowego rozkładu, A0⁢s=-F⁢x;

for j = 0 to k-1

begin

s=s+sj+1⁢sjT⁢s/sj22;

end

s=s/1+sk-1T⁢s/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 A0≈F′⁢x0.

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

Przy standardowych założeniach, istnieją δ oraz δ0 (dostatecznie małe) takie, że jeśli x0∈K⁢x*,δ oraz A0-F′⁢x*<δ0, to metoda Broydena startująca z x0 i A0 jest dobrze określona oraz xk→x* superliniowo.

Dowód

Zobacz np. [9].

∎

Ćwiczenie 11.3

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

Rozwiązanie:

To oczywiste, gdyż

A0-F′⁢x*=F′⁢x0-F′⁢x*≤L⁢x0-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-F′⁢x*≤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+1⁢xk+1-xk=F⁢xk+1-F⁢xk.

Rozwiązanie:

Z definicji

Ak+1=Ak+1skT⁢sk⁢F⁢xk+1⁢skT,

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

Ak+1⁢sk=Ak⁢sk+F⁢xk+1=-F⁢xk+F⁢xk+1.

Ćwiczenie 11.6

Niech A∈RN×N oraz s,y∈RN przy czym s≠0. Wtedy

minB∈RN×N:⁢B⁢s=y⁡A-B2

jest osiągane dla

B*=A+y-A⁢s⁢sTsT⁢s.

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

Ak⁢xk-xk-1=F⁢xk-F⁢xk-1.

Rozwiązanie:

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

B*-A=y-A⁢s⁢sTsT⁢s=B⁢s-A⁢s⁢sTsT⁢s=B-A⁢s⁢sTsT⁢s,

skąd

B*-A2≤B-A2⁢s⁢sT/s22=B-A2.

Ostatnia równość wynika z faktu, że x⁢yT2=x2⁢⁢y2.

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.

Matematyka obliczeniowa II

Zagadnienia

11. Metoda Broydena

11.1. Realizacja metody Broydena

Stwierdzenie 11.1 (wzór Shermana–Morrisona)

Ćwiczenie 11.1

Ćwiczenie 11.2

Bazowa implementacja metody Broydena

11.2. Zbieżność metody Broydena

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

Dowód

Ćwiczenie 11.3

Ćwiczenie 11.5

Ćwiczenie 11.6