Biconjugate gradientní metoda

V matematiky , konkrétně v numerické analýze je metoda biconjugate stoupání je algoritmus umožňuje řešit systém lineárních rovnic

{\ displaystyle Ax = b. \,}

Na rozdíl od metody s konjugovaným gradientem tento algoritmus nevyžaduje, aby matice byla samoadjungovaná, na druhou stranu metoda vyžaduje násobení sousední maticí . $NA$ $A ^ {*}$

Algoritmus

Zvolit , se preconditioner pravidelnost (často používaný ) a ; $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} \,}$ ;
pro práci ${\ displaystyle k = 0,1, \ tečky \,}$
${\ displaystyle \ alpha _ {k} \ leftarrow {s_ {k} ^ {*} M ^ {- 1} r_ {k} \ přes 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} \,}$ , (( a jsou zbytky); ${\ 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} \ přes 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} \,}$

Diskuse

Metoda je numericky nestabilní , ale je napravena stabilizovanou metodou biconjugate gradientu (en) a z teoretického hlediska zůstává velmi důležitá: iteraci definujeme pomocí a ( ) pomocí následujících projekcí : ${\ displaystyle x_ {k}: = x_ {j} + P_ {k} A ^ {- 1} \ left (b-Ax_ {j} \ right)}$ ${\ displaystyle y_ {k}: = y_ {j} + A ^ {- *} P_ {k} ^ {*} \ left (cA ^ {*} y_ {j} \ right)}$ $j <k$

{\ displaystyle P_ {k}: = \ mathbf {u_ {k}} \ left (\ mathbf {v_ {k}} ^ {*} A \ mathbf {u_ {k}} \ right) ^ {- 1} \ mathbf {v_ {k}} ^ {*} A}

S a . Můžeme iterovat projekce samotné, jako ${\ displaystyle \ mathbf {u_ {k}} = \ left (u_ {0}, u_ {1}, \ dots u_ {k-1} \ right)}$ ${\ displaystyle \ mathbf {v_ {k}} = \ vlevo (v_ {0}, v_ {1}, \ tečky v_ {k-1} \ vpravo)}$

{\ displaystyle P_ {k + 1} = P_ {k} + \ left (1-P_ {k} \ right) u_ {k} \ other {v_ {k} ^ {*} A \ left (1-P_ { k} \ right) \ over v_ {k} ^ {*} A \ left (1-P_ {k} \ right) u_ {k}}}

Nové směry sestupu a poté jsou kolmé na zbytky: a , které splňují stejné a ( ). ${\ displaystyle d_ {k}: = \ left (1-P_ {k} \ right) u_ {k}}$ ${\ displaystyle f_ {k}: = \ left (A \ left (1-P_ {k} \ right) A ^ {- 1} \ right) ^ {*} 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 \ left (1-P_ {k} \ right) A ^ {- 1} r_ {j}}$ ${\ displaystyle s_ {k} = \ vlevo (1-P_ {k} \ vpravo) ^ {*} s_ {j}}$ ${\ displaystyle i, j <k}$

Metoda biconjugate gradient pak nabízí následující výběr:

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

a .

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

Tato konkrétní volba pak umožňuje vyhnout se přímému vyhodnocení a , a tedy zvýšit rychlost provádění algoritmu. $P_ {k}$ $A ^ {{- 1}}$

Vlastnosti

If je self-adjoint , a , proto , a metoda konjugovaného přechodu produkuje stejný výsledek . ${\ 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}}$

V konečných rozměrech nejpozději, když : Metoda biconjugate gradient poskytuje řešení přesné poté, co prošla celým prostorem, a je tedy přímou metodou. ${\ displaystyle x_ {n} = A ^ {- 1} b}$ ${\ displaystyle P_ {n} = 1}$

Sekvence produkovaná algoritmem je biortogonální (in) : a for . ${\ displaystyle f_ {i} ^ {*} Ad_ {j} = 0}$ ${\ displaystyle s_ {i} ^ {*} M ^ {- 1} r_ {j} = 0}$ ${\ Displaystyle i \ neq j}$

IF je polynom s , poté . Algoritmus se proto skládá z projekcí na krylovské podprostory (en) ; ${\ displaystyle p_ {j '}}$ ${\ displaystyle deg \ left (p_ {j '} \ right) + j <k}$ ${\ displaystyle s_ {k} ^ {*} p_ {j '} \ vlevo (M ^ {- 1} A \ vpravo) u_ {j} = 0}$

IF je polynom , pak . ${\ displaystyle p_ {i '}}$ ${\ displaystyle i + deg \ left (p_ {i '} \ right) <k}$ ${\ displaystyle v_ {i} ^ {*} p_ {i '} \ vlevo (AM ^ {- 1} \ vpravo) r_ {k} = 0}$

( fr ) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „ Biconjugate gradient method “ ( viz seznam autorů ) .