Kaksikonjugaattigradienttimenetelmä

On matematiikka , tarkemmin sanoen numeerinen analyysi , biconjugate kaltevuus menetelmä on algoritmi , jonka avulla voidaan ratkaista lineaarisen yhtälöryhmän

{\ displaystyle Ax = b. \,}

Toisin kuin konjugaattigradienttimenetelmä , tämä algoritmi ei vaadi matriisin olevan itsestään liitetty, toisaalta menetelmä vaatii kertomuksia viereisen matriisin kanssa . $AT$ $A ^ {*}$

Algoritmi

Valitse , esikostuttimeen säännöllisesti (usein käytetty ) ja ; $x_ {0}$ $y_ {0}$ $M$ ${\ displaystyle M ^ {- 1} = 1}$ $vs.$
${\ displaystyle r_ {0} \ vasen nuoli b-Axe {0}, s_ {0} \ vasen nuoli cA ^ {*} y_ {0} \,}$ ;
${\ displaystyle d_ {0} \ vasen nuoli M ^ {- 1} r_ {0}, f_ {0} \ vasen nuoli M ^ {- *} s_ {0} \,}$ ;
for Do ${\ displaystyle k = 0,1, \ pistettä \,}$
${\ displaystyle \ alpha _ {k} \ vasen nuoli {s_ {k} ^ {*} M ^ {- 1} r_ {k} \ yli f_ {k} ^ {*} Ad_ {k}} \,}$ ;
${\ displaystyle x_ {k + 1} \ vasen nuoli x_ {k} + \ alpha _ {k} d_ {k} \,}$ ${\ displaystyle \ left (y_ {k + 1} \ leftarrow y_ {k} + {\ overline {\ alpha _ {k}}} f_ {k} \ right) \,}$ ;
${\ displaystyle r_ {k + 1} \ vasen nuoli r_ {k} - \ alpha _ {k} Ad_ {k} \,}$ , ( Ja ovat tähteet); ${\ displaystyle s_ {k + 1} \ vasen nuoli s_ {k} - {\ yliviiva {\ alpha _ {k}}} A ^ {*} f_ {k} \,}$ ${\ displaystyle r_ {k} = b-Ax_ {k}}$ ${\ displaystyle s_ {k} = cA ^ {*} y_ {k}}$
${\ displaystyle \ beta _ {k} \ vasen nuoli {s_ {k + 1} ^ {*} M ^ {- 1} r_ {k + 1} \ yli s_ {k} ^ {*} M ^ {- 1} r_ {k}} \,}$ ;
${\ displaystyle d_ {k + 1} \ vasen nuoli M ^ {- 1} r_ {k + 1} + \ beta _ {k} d_ {k} \,}$ , . ${\ displaystyle f_ {k + 1} \ vasen nuoli M ^ {- *} s_ {k + 1} + {\ overline {\ beta _ {k}}} f_ {k} \,}$

Keskustelu

Menetelmä on numeerisesti epävakaa , mutta se korjataan kaksikonjugaattigradientin (en) stabiloidulla menetelmällä , ja se on teoreettisesta näkökulmasta edelleen erittäin tärkeä: määritämme iteraation ja ( ) seuraavilla ennusteilla : ${\ displaystyle x_ {k}: = x_ {j} + P_ {k} A ^ {- 1} \ vasen (b-Ax_ {j} \ oikea)}$ ${\ displaystyle y_ {k}: = y_ {j} + A ^ {- *} P_ {k} ^ {*} \ vasen (cA ^ {*} y_ {j} \ oikea)}$ $j <k$

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

Kanssa ja . Voimme toistaa ennusteet itse, kuten ${\ displaystyle \ mathbf {u_ {k}} = \ vasen (u_ {0}, u_ {1}, \ pisteitä u_ {k-1} \ oikea)}$ ${\ displaystyle \ mathbf {v_ {k}} = \ vasen (v_ {0}, v_ {1}, \ piste v_ {k-1} \ oikea)}$

{\ displaystyle P_ {k + 1} = P_ {k} + \ vasen (1-P_ {k} \ oikea) u_ {k} \ otimes {v_ {k} ^ {*} A \ vasen (1-P_ { k} \ oikea) \ yli v_ {k} ^ {*} A \ vasen (1-P_ {k} \ oikea) u_ {k}}}

Uudet laskeutumissuunnat ja ovat sitten kohtisuorassa jäännösten kanssa: ja , jotka tyydyttävät saman ja ( ). ${\ displaystyle d_ {k}: = \ vasen (1-P_ {k} \ oikea) u_ {k}}$ ${\ displaystyle f_ {k}: = \ vasen (A \ vasen (1-P_ {k} \ oikea) A ^ {- 1} \ oikea) ^ {*} 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 \ vasen (1-P_ {k} \ oikea) A ^ {- 1} r_ {j}}$ ${\ displaystyle s_ {k} = \ vasen (1-P_ {k} \ oikea) ^ {*} s_ {j}}$ ${\ displaystyle i, j <k}$

Bikonjugaattigradienttimenetelmä tarjoaa sitten seuraavan valinnan:

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

ja .

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

Tämä erityisesti valinta sitten tekee mahdolliseksi välttää suoran arvioinnin ja , ja siten nopeuttaa algoritmin suorituksen. $P_ {k}$ $A ^ {{- 1}}$

Ominaisuudet

If on itsekytkentä , ja siten , ja konjugaattigradienttimenetelmä tuottaa saman tuloksen . ${\ 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}}$

Lopullisissa mitoissa viimeistään, kun : Kaksikonjugaattigradienttimenetelmä antaa ratkaisulle tarkan koko tilan peittämisen jälkeen ja on siten suora menetelmä. ${\ displaystyle x_ {n} = A ^ {- 1} b}$ ${\ displaystyle P_ {n} = 1}$

Algoritmin tuottama sekvenssi on biortogonaalinen (in) : ja for . ${\ displaystyle f_ {i} ^ {*} Ad_ {j} = 0}$ ${\ displaystyle s_ {i} ^ {*} M ^ {- 1} r_ {j} = 0}$ ${\ displaystyle i \ neq j}$

IF on polynomi , jossa on , sen jälkeen . Siksi algoritmi koostuu projektioista Krylovin alatiloissa (en) ; ${\ displaystyle p_ {j '}}$ ${\ displaystyle deg \ vasen (p_ {j '} \ oikea) + j <k}$ ${\ displaystyle s_ {k} ^ {*} p_ {j '} \ vasen (M ^ {- 1} A \ oikea) u_ {j} = 0}$

IF on polynomi , jonka kanssa . ${\ displaystyle p_ {i '}}$ ${\ displaystyle i + deg \ vasen (p_ {i '} \ oikea) <k}$ ${\ displaystyle v_ {i} ^ {*} p_ {i '} \ vasen (AM ^ {- 1} \ oikea) r_ {k} = 0}$

( fr ) Tämä artikkeli on osittain tai kokonaan peräisin englanninkielisestä Wikipedia- artikkelista " Biconjugate gradient method " ( katso luettelo kirjoittajista ) .