W przypadku jednowymiarowym, metoda siecznych:
![]() |
jest interesującą alternatywą dla metody Newtona: jej zbieżność jest superliniowa (dokładniej: wykładnicza z wykładnikiem — 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
![]() |
gdzie (lub jest jej przybliżeniem wyznaczonym za pomocą ilorazów różnicowych), a kolejne macierze
wyznaczamy według wzoru
![]() |
![]() |
||
![]() |
![]() |
(Zauważmy, że jest jawnie wyznaczane w trakcie algorytmu, gdyż
jest rozwiązaniem równania poprawki,
.)
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 , to wyznaczenie rozkładu
, która jest postaci
, jest zadaniem wyznaczenia rozkładu dla modyfikacji macierzy rzędu 1 — a na to są znane (tanie!) algorytmy [7], [10], działające kosztem
flopów14W metodzie Broydena nie ma więc — wbrew pozorom — potrzeby jawnego wyznaczania macierzy
!, o czym szerzej mówimy w poniższym rozdziale.
Oczywiście, gdybyśmy tylko skorzystali wprost ze wzoru
![]() |
to co prawda wyznaczenie kosztowałoby nas tylko
flopów, ale za to rozkład macierzy
musiałby nas kosztować
. Jednak, jako że macierz
różni się od
tylko o macierz rzędu jeden, będziemy mogli od razu przykładać odwrotność macierzy
do wektora na podstawie rozkładu macierzy
, kosztem jedynie
.
Algorytm działający w oparciu o aktualizację macierzy odwrotnej do może być mniej stabilny numerycznie od algorytmu używającego aktualizacji rozkładu QR (zob. [10, 10.3.1, Algorytm 2]) macierzy
i dlatego wskazuje się sposoby kontrolowania przebiegu pracy tej metody [5], którymi tutaj nie będziemy się zajmować.
Aby tanio odwracać kolejne macierze , wykorzystamy wzór Shermana–Morrisona, którego wyprowadzeniu było poświęcone ćwiczenie 5.24.
Niech , gdzie
jest macierzą nieosobliwą
oraz
.
jest nieosobliwa wtedy i tylko wtedy, gdy
i wówczas
![]() |
U nas
![]() |
gdzie ,
.
Oznaczając dodatkowo
![]() |
ze wzoru Shermana–Morrisona mamy więc
![]() |
(11.1) |
Wydawałoby się więc, że by skorzystać z powyższego wzoru, należałoby pamiętać dodatkowe wektory dla
. 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
.
Rzeczywiście, w metodzie Broydena interesuje nas przecież nie sama macierz , tylko nowa wartość poprawki,
.
Tymczasem, korzystając z definicji
i
,
![]() |
![]() |
||
![]() |
Stąd dostajemy elegancką zależność , którą możemy podstawić z powrotem do (11.1) i otrzymać
![]() |
(11.2) |
Na tej podstawie ( występuje po obu stronach tej równości!) konkludujemy, że
![]() |
(11.3) |
Wykaż, że jeśli jest nieosobliwa, to wyrażenie pojawiające się w mianowniku wzoru na
jest różne od zera.
Zauważ, że i skorzystaj ze wzoru Shermana–Morrisona.
Zaimplementuj metodę Broydena z zastosowaniem wzoru Shermana–Morrisona.
Aby sensownie wyznaczać , musimy zastanowić się chwilę, jak wyznaczać wektor
![]() |
występujący we wzorze (11.3). Zauważmy, że na mocy (11.1),
![]() |
a więc wyznaczenie daje się zrealizować w pętli polegającej na kolejnym mnożeniu przez macierze postaci
. Pamiętajmy, by macierzy postaci
nigdy nie formować explicite, a w zamian wyznaczać iloczyn
zgodnie z wzorem
![]() |
co będzie kosztowało tylko flopów. Szkielet algorytmu mógłby więc wyglądać następująco:
![]() |
![]() |
wyznacz rozkład LU lub QR macierzy ![]() |
rozwiąż, korzystając z gotowego rozkładu, ![]() |
while not stop do |
begin |
![]() |
oblicz ![]() |
k = k+1; |
rozwiąż, korzystając z gotowego rozkładu, ![]() |
for j = 0 to k-1 |
begin |
![]() |
end |
![]() |
![]() |
end |
Jak widać, musimy pamiętać czynniki rozkładu (samego
już nie) oraz wszystkie pośrednie poprawki
.
Poniższe twierdzenie gwarantuje superliniową zbieżność metody Broydena nawet w przypadku, gdy .
Przy standardowych założeniach, istnieją oraz
(dostatecznie małe) takie, że jeśli
oraz
, to metoda Broydena startująca z
i
jest dobrze określona oraz
superliniowo.
Zobacz np. [9].
∎Wykaż, że jeśli oraz
jest dostatecznie blisko
, to powyższe twierdzenie zachodzi.
To oczywiste, gdyż
![]() |
Biorąc ,
z twierdzenia o zbieżności metody Broydena i ewentualnie dodatkowo zmniejszając
tak, by jednocześnie
, dostajemy
![]() |
co gwarantuje spełnienie wszystkich założeń twierdzenia 11.1.
Wykaż, że macierze generowane w metodzie Broydena spełniają równanie siecznych,
![]() |
Z definicji
![]() |
więc mnożąc przez mamy
![]() |
Niech oraz
przy czym
. Wtedy
![]() |
jest osiągane dla
![]() |
Znaczy to, że metoda Broydena generuje ciąg macierzy taki, że
jest najbliższe
w normie spektralnej wśród wszystkich macierzy spełniających równanie siecznych
![]() |
Wystarczy pokazać, że dla dowolnej innej macierzy spełniającej
, norma różnicy
nie jest mniejsza niż dla
. Mamy
![]() |
skąd
![]() |
Ostatnia równość wynika z faktu, że .
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.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.