Metoda gradientu dwukoniugatowego

W matematyce , a dokładniej w numerycznej algebrze liniowej , metoda gradientu dwusprzężonego jest algorytmem rozwiązywania układów równań liniowych

${\ Displaystyle Ax = b. \,}$

W przeciwieństwie do metody gradientu sprzężonego , ten algorytm nie wymaga, $aby$ macierz była samosprzężona , ale zamiast tego należy wykonać mnożenie przez transpozycję koniugatu A ^*

Algorytm

1. Wybierz początkowe przypuszczenie , dwa inne wektory $\$$Displaystyle x_ {0} ^ {*}}$ b $\ Displaystyle b ^ {*} \,}$ i warunek wstępny ${\ Displaystyle M \,}$
2. ${\ Displaystyle r_ {0} \ strzałka w lewo bA \, x_ {0} \,}$
3. ${\ Displaystyle r_ {0} ^ {*} \ strzałka w lewo b ^ {*} -x_ {0} ^ {*} \, A}$
4. ${\ Displaystyle p_ {0} \ strzałka w lewo M ^ {-1} r_ {0} \,}$
5. ${\ Displaystyle p_ {0} ^ {*} \ strzałka w lewo r_ {0} ^ {*} M ^ {- 1} \,}$
6. dla ${\ Displaystyle k = 0,1, \ ldots}$ zrobić
   1. ${\ Displaystyle \ alfa _ {k} \ leftarrow {r_ {k} ^ {*} M ^ {- 1} r_ {k} \ ponad p_ {k}^{*}Ap_{k}}\,}$
   2. ${\ Displaystyle x_ {k + 1} \ strzałka w lewo x_ {k} + \ alfa _ {k} \ cdot p_ {k} \,}$
   3. ${\ Displaystyle x_ {k + 1} ^ {*} \ strzałka w lewo x_ {k} ^ {*} + {\ overline {\ alfa _ {k }}}\cdot p_{k}^{*}\,}$
   4. ${\ Displaystyle r_ {k + 1} \ strzałka w lewo r_ {k} - \ alfa _ {k} \ cdot Ap_ {k} \,}$
   5. ${\ Displaystyle r_ {k + 1} ^ {*} \ strzałka w lewo r_ {k} ^ {*} - {\ overline {\ alfa _ { k}}}\cdot p_{k}^{*}\,A}$
   6. ${\ Displaystyle \ beta _ {k} \ leftarrow {r_ {k + 1} ^ {*} M ^ {-1 }r_{k+1} \ponad r_{k}^{*}M^{-1}r_{k}}\,}$
   7. ${\ Displaystyle p_ {k + 1} \ lewa strzałka M ^ {-1} r_ {k + 1} + \ beta _ {k} \ cdot p_{k}\,}$
   8. ${\ Displaystyle p_ {k + 1} ^ {*} \ leftarrow r_ {k + 1} ^ {*} M ^ { -1}+{\overline {\beta _{k}}}\cdot p_{k}^{*}\,}$

W powyższym sformułowaniu obliczone i ${\ Displaystyle r_ {k}$$^ {*}} spełniają r k {\ displaystyle r_ {k$ } }

${\ Displaystyle r_ {k} = b-Ax_ {k}, \,}$

${\ Displaystyle r_ {k} ^ {*} = b^{*}-x_{k}^{*}\,A}$

$x_ {k} ^ {*}}$ zatem odpowiednie reszty odpowiadają i jako przybliżonym systemów $Displaystyle$

${\ Displaystyle Ax = b, \,}$

${\ Displaystyle x ^ {*} \, A = b ^ {*} \,;}$

$x ^ {*}}$ { \ $jest$ jest sprzężeniem i złożonym .

Nieuwarunkowana wersja algorytmu

1. Wybierz początkowe przypuszczenie ${\ displaystyle x_ {0} \,}$ ,
2. ${\ Displaystyle r_ {0} \ strzałka w lewo bA \, x_ {0} \,}$
3. ${\ Displaystyle {\ kapelusz {r}} _ {0} \ strzałka w lewo {\ kapelusz {b}} - {\ kapelusz {x}} _ {0} A}$
4. ${\ displaystyle p_ {0} \ strzałka w lewo r_ {0} \,}$
5. ${\ Displaystyle {\ kapelusz {p}} _ {0} \ strzałka w lewo {\ kapelusz {r}} _ {0} \,}$
6. dla ${\ Displaystyle k = 0,1, \ ldots}$ zrobić
   1. ${\ Displaystyle \ alfa _ {k} \ strzałka w lewo {{\ kapelusz {r}} _ {k} r_ {k} \ ponad {\ kapelusz {p}} _{k}Ap_{k}}\,}$
   2. ${\ Displaystyle x_ {k + 1} \ strzałka w lewo x_ {k} + \ alfa _ {k} \ cdot p_ {k} \,}$
   3. ${\ Displaystyle {\ kapelusz {x}} _ {k + 1} \ strzałka w lewo {\ kapelusz {x}} _ {k} + \ alfa _ { k}\cdot {\kapelusz {p}}_{k}\,}$
   4. ${\ Displaystyle r_ {k + 1} \ strzałka w lewo r_ {k} - \ alfa _ {k} \ cdot Ap_ {k} \,}$
   5. ${\ Displaystyle {\ kapelusz {r}} _ {k + 1} \ strzałka w lewo {\ kapelusz {r}} _ {k} - \ alfa _ {k}\cdot {\kapelusz {p}}_{k}A}$
   6. ${\ Displaystyle \ beta _ {k} \ strzałka w lewo {{\ kapelusz {r}} _ {k + 1} r_ {k + 1} \ ponad {\kapelusz {r}}_{k}r_{k}}\,}$
   7. ${\ Displaystyle p_ {k + 1} \ strzałka w lewo r_ {k + 1} + \ beta _ {k} \ cdot p_ {k} \,}$
   8. ${\ Displaystyle {\ kapelusz {p}} _ {k + 1} \ strzałka w lewo {\ kapelusz {r}} _ {k + 1} + \beta _{k}\cdot {\kapelusz {p}}_{k}\,}$

Dyskusja

Metoda gradientu dwukoniugatu jest numerycznie niestabilna (porównaj z metodą stabilizowanego gradientu dwukoniugatu ), ale bardzo ważna z teoretycznego punktu widzenia. Zdefiniuj kroki iteracji wg

${\ Displaystyle x_ {k}: = x_ {j} + P_ {k} A ^ {- 1} \ lewo (b-Ax_ {j} \ prawo),}$

$\ Displaystyle x_ {k} ^ {*}: = x_ {j} ^ {*}+\left(b^{*}-x_{j}^{*}A\right)P_{k}A^{-1},}$

gdzie ${\ displaystyle j <k}$ przy użyciu powiązanej projekcji

${\ Displaystyle P_ {k}: = \ mathbf {u} _ {k} \ lewo (\ mathbf {v} _ {k }^{*}A\mathbf {u} _{k}\right)^{-1}\mathbf {v} _{k}^{*}A,}$

z

${\ Displaystyle \ mathbf {u} _ {k} = \ lewo [u_ {0}, u_ {1}, \ kropki, u_ {k- 1}\right],}$

${\ Displaystyle \ mathbf {v} _ {k} = \ lewo [v_ {0}, v_ {1}, \ kropki, v_ {k-1} \ prawo].}$

Te powiązane projekcje mogą być powtarzane same jako

${\ Displaystyle P_ {k + 1} = P_ {k} + \ lewo (1-P_ {k} \ prawej) u_ {k} \ czasami {v_ {k} ^ {*} A \ lewo (1-P_ { k}\right) \over v_{k}^{*}A\left(1-P_{k}\right)u_{k}}.}$

Związek z metodami quasi-newtonowskimi jest podany przez ${\ Displaystyle P_ {k} = A_ {k} ^ {-1} A}$ i $_$ _

${\ Displaystyle A_ {k + 1} ^ {-1} = A_ {k} ^ {- 1} + \ lewo (1-A_ {k} ^ {-1} A \ prawo) u_ {k} \ czasami { v_{k}^{*}\left(1-AA_{k}^{-1}\right) \over v_{k}^{*}A\left(1-A_{k}^{-1} A\right)u_{k}}.}$

Nowe kierunki

${\ Displaystyle p_ {k} = \ lewo (1-P_ {k} \ prawej) u_ {k},}$

${\ Displaystyle p_ {k} ^ {*} = v_ {k} ^ {*} A \ lewo (1-P_ {k} \ prawo) A ^ {- 1}}$

są wtedy prostopadłe do reszt:

${\ Displaystyle v_ {i} ^ {*} r_ {k} = p_ {i} ^ {*} r_ {k} = 0,}$

${\ Displaystyle r_ {k} ^ {*} u_ {j} = r_ {k} ^ {*} p_ {j} = 0,}$

które same zaspokajają

${\ Displaystyle r_ {k} = A \ lewo (1-P_ {k} \ prawej) A ^ {- 1} r_ {j},}$

${\ Displaystyle r_ {k} ^ {*} = r_ {j} ^ {*} \ lewo (1-P_ {k} \ prawo)}$

gdzie ${\ Displaystyle i, j <k}$ .

Metoda gradientu biconjugate dokonuje teraz specjalnego wyboru i wykorzystuje ustawienie

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

${\ Displaystyle v_ {k} ^ {*} = r_ {k} ^ {*} \, M ^ {-1}. \,}$

$.$ ocen i A ^{-1 , a algorytm przyjmuje} postać

Nieruchomości

• Jeśli $x$ samosprzężony , ${\ Displaystyle x_ {0} ^ {*$$\ Displaystyle b ^ {*} = b}$$x_$ {0} i , wtedy ${\ Displaystyle r_ {k} = r_ {k} ^ {*}}$ , $} ^ {*}}$${\ Displaystyle p_ {k} = p_ {$$k$ a metoda gradientu sprzężonego samą sekwencję kosztów obliczeniowych
• Sekwencje $_ } M ^ {- 1} r_ {j} = 0}$ biorthogonalne tj dla ${\ Displaystyle i \ neq j}$ .
• ${\ Displaystyle P_ {j'} \,}$ jot jest wielomianem z $\ prawej) + j <k }$ , wtedy ${\ Displaystyle r_ {k} ^ {*} P_ {j'} \ lewo (M ^ {- 1} A \ prawej) u_ {j }=0}$ . Algorytm tworzy zatem projekcje na podprzestrzeń Kryłowa .
• P ${\ Displaystyle P_ {i'} \,}$ jest wielomianem z $\ Displaystyle i+ \ stopień \ lewo (P_ {i'} \ prawo) <k}$ , wtedy ${\ Displaystyle v_ {i} ^ {*} P_ {i'} \ lewo (AM ^ {-1} \ prawej) r_ {k} = 0}$ .

Zobacz też

• Metoda stabilizowana gradientem dwukoniugatu
• Metoda gradientu sprzężonego

•    Fletcher, R. (1976). Watson, G. Alistair (red.). „Metody gradientu sprzężonego dla systemów nieokreślonych” . Analiza numeryczna . Notatki z wykładów z matematyki. Springer Berlin/Heidelberg. 506 : 73–89 . doi : 10.1007/BFb0080109 . ISBN 978-3-540-07610-0 . ISSN 1617-9692 .
•   Prasa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Sekcja 2.7.6” . Przepisy numeryczne: sztuka obliczeń naukowych (wyd. 3). Nowy Jork: Cambridge University Press. ISBN 978-0-521-88068-8 .