Metoda gradientu biconjugate

W matematyce , a dokładniej w analizie numerycznej , metoda gradientu dwukoniugatowego jest algorytmem rozwiązywania układu równań liniowych

{\ Displaystyle Ax = b. \,}

W przeciwieństwie do metody gradientu sprzężonego , algorytm ten nie wymaga, aby macierz była samosprzężona, z drugiej strony metoda wymaga mnożenia przez sąsiednią macierz . $W$ $A ^ {*}$

Algorytm

Wybierz , a przygotowujący regularnych (często używany ) oraz ; $x_ {0}$ $y_ {0}$ $M$ ${\ Displaystyle M ^ {- 1} = 1}$ $vs$
${\ Displaystyle r_ {0} \ leftarrow b-Ax_ {0}, s_ {0} \ leftarrow cA ^ {*} y_ {0} \,}$ ;
${\ Displaystyle d_ {0} \ leftarrow M ^ {- 1} r_ {0}, f_ {0} \ leftarrow M ^ {- *} s_ {0} \,}$ ;
do zrobienia ${\ Displaystyle k = 0,1, \ kropki \,}$
${\ Displaystyle \ alpha _ {k} \ leftarrow {s_ {k} ^ {*} M ^ {- 1} r_ {k} \ ponad f_ {k} ^ {*} Ad_ {k}} \,}$ ;
${\ Displaystyle x_ {k + 1} \ leftarrow x_ {k} + \ alpha _ {k} d_ {k} \,}$ ${\ displaystyle \ left (y_ {k + 1} \ leftarrow y_ {k} + {\ overline {\ alpha _ {k}}} f_ {k} \ right) \,}$ ;
${\ displaystyle r_ {k + 1} \ leftarrow r_ {k} - \ alpha _ {k} Ad_ {k} \,}$ , ( i są pozostałościami); ${\ Displaystyle s_ {k + 1} \ leftarrow s_ {k} - {\ overline {\ alpha _ {k}}} A ^ {*} f_ {k} \,}$ ${\ displaystyle r_ {k} = b-Ax_ {k}}$ ${\ Displaystyle s_ {k} = CA ^ {*} y_ {k}}$
${\ Displaystyle \ beta _ {k} \ leftarrow {s_ {k + 1} ^ {*} M ^ {- 1} r_ {k + 1} \ ponad s_ {k} ^ {*} M ^ {- 1} r_ {k}} \,}$ ;
${\ Displaystyle d_ {k + 1} \ leftarrow M ^ {- 1} r_ {k + 1} + \ beta _ {k} d_ {k} \,}$ , . ${\ displaystyle f_ {k + 1} \ leftarrow M ^ {- *} s_ {k + 1} + {\ overline {\ beta _ {k}}} f_ {k} \,}$

Dyskusja

Metoda jest niestabilna numerycznie , ale można ją naprawić za pomocą ustabilizowanej metody gradientu biconiugatu (en) i pozostaje bardzo ważna z teoretycznego punktu widzenia: iterację definiujemy za pomocą i ( ) za pomocą następujących rzutów : ${\ Displaystyle x_ {k}: = x_ {j} + P_ {k} A ^ {- 1} \ lewo (b-Ax_ {j} \ prawo)}$ ${\ Displaystyle y_ {k}: = y_ {j} + A ^ {- *} P_ {k} ^ {*} \ lewo (CA ^ {*} y_ {j} \ prawej)}$ $j <k$

{\ Displaystyle P_ {k}: = \ mathbf {u_ {k}} \ lewo (\ mathbf {v_ {k}} ^ {*} A \ mathbf {u_ {k}} \ prawo) ^ {- 1} \ mathbf {v_ {k}} ^ {*} A}

Z i . Możemy powtórzyć same prognozy, na przykład ${\ Displaystyle \ mathbf {u_ {k}} = \ lewo (u_ {0}, u_ {1}, \ kropki u_ {k-1} \ po prawej)}$ ${\ displaystyle \ mathbf {v_ {k}} = \ lewo (v_ {0}, v_ {1}, \ kropki v_ {k-1} \ po prawej)}$

{\ Displaystyle P_ {k + 1} = P_ {k} + \ lewo (1-P_ {k} \ prawo) u_ {k} \ otimes {v_ {k} ^ {*} A \ lewo (1-P_ { k} \ right) \ over v_ {k} ^ {*} A \ left (1-P_ {k} \ right) u_ {k}}}

Nowe kierunki opadania i są wówczas ortogonalne do reszt: i , które spełniają to samo i ( ). ${\ Displaystyle d_ {k}: = \ lewo (1-P_ {k} \ prawo) u_ {k}}$ ${\ Displaystyle f_ {k}: = \ lewo (A \ lewo (1-P_ {k} \ prawo) A ^ {- 1} \ prawo) ^ {*} v_ {k}}$ ${\ Displaystyle V_ {i} ^ {*} r_ {k} = f_ {i} ^ {*} r_ {k} = 0}$ ${\ Displaystyle s_ {k} ^ {*} u_ {j} = s_ {k} ^ {*} d_ {j} = 0}$ ${\ Displaystyle r_ {k} = A \ lewo (1-P_ {k} \ prawej) A ^ {- 1} r_ {j}}$ ${\ Displaystyle s_ {k} = \ lewo (1-P_ {k} \ prawej) ^ {*} s_ {j}}$ ${\ displaystyle i, j <k}$

Metoda gradientu dwukoniugatowego oferuje wtedy następujący wybór:

{\ Displaystyle u_ {k}: = M ^ {- 1} r_ {k}}

i .

{\ Displaystyle v_ {k}: = M ^ {- *} s_ {k}}

Ten szczególny wybór następnie pozwala uniknąć bezpośredniej oceny i , a tym samym zwiększyć szybkość wykonania algorytmu. $P_ {k}$ $A ^ {{- 1}}$

Nieruchomości

Jeśli jest samosprzężone , i w związku z tym , a koniugat gradient metoda daje taki sam wynik . ${\ Displaystyle A = A ^ {*}}$ ${\ displaystyle y_ {0} = x_ {0}}$ ${\ displaystyle c = b}$ ${\ displaystyle r_ {k} = s_ {k}}$ ${\ displaystyle d_ {k} = f_ {k}}$ ${\ displaystyle x_ {k} = y_ {k}}$

W skończonych wymiarach , najpóźniej wtedy, gdy : Metoda gradientu dwukoniugatowego daje dokładne rozwiązanie po pokryciu całej przestrzeni i dlatego jest metodą bezpośrednią. ${\ Displaystyle x_ {n} = A ^ {- 1} b}$ ${\ displaystyle P_ {n} = 1}$

Sekwencja generowana przez algorytm jest biortogonalna (in) : i dla . ${\ displaystyle f_ {i} ^ {*} Ad_ {j} = 0}$ ${\ Displaystyle s_ {i} ^ {*} M ^ {- 1} r_ {j} = 0}$ ${\ displaystyle i \ neq j}$

JEŻELI jest wielomianem z , to . Algorytm składa się zatem z rzutów na podprzestrzenie Kryłowa (en) ; ${\ displaystyle p_ {j '}}$ ${\ Displaystyle deg \ lewo (p_ {j '} \ prawo) + j <k}$ ${\ Displaystyle s_ {k} ^ {*} p_ {j '} \ lewo (M ^ {- 1} A \ prawo) u_ {j} = 0}$

JEŻELI jest wielomianem z , to . ${\ displaystyle p_ {i '}}$ ${\ Displaystyle i + deg \ lewo (p_ {i '} \ prawo) <k}$ ${\ Displaystyle V_ {i} ^ {*} p_ {i '} \ lewo (AM ^ {- 1} \ prawej) r_ {k} = 0}$

( fr ) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu z angielskiej Wikipedii zatytułowanego „ Biconjugate gradient method ” ( patrz lista autorów ) .