Metodo del gradiente biconiugato

In matematica , più specificamente nell'analisi numerica , il metodo del gradiente biconiugato è un algoritmo per la risoluzione di un sistema di equazioni lineari

{\ displaystyle Ax = b. \,}

A differenza del metodo del gradiente coniugato , questo algoritmo non richiede che la matrice sia autoaggiunta, d'altra parte, il metodo richiede moltiplicazioni per la matrice adiacente . $A$ $A ^ {*}$

Algoritmo

Scegli , un precondizionatore regolare (spesso usato ) e ; $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} \,}$ ;
per fare ${\ displaystyle k = 0,1, \ dots \,}$
${\ displaystyle \ alpha _ {k} \ leftarrow {s_ {k} ^ {*} M ^ {- 1} r_ {k} \ over 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} \,}$ , ( e sono i residui); ${\ displaystyle s_ {k + 1} \ leftarrow s_ {k} - {\ overline {\ alpha _ {k}}} LA ^ {*} 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} \ over 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} \,}$

Discussione

Il metodo è numericamente instabile , ma viene risolto con il metodo stabilizzato del gradiente biconiugato (en) , e rimane molto importante da un punto di vista teorico: definiamo l'iterazione con e ( ) utilizzando le seguenti proiezioni : ${\ 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}

Con e . Possiamo iterare le proiezioni stesse, come ${\ Displaystyle \ mathbf {u_ {k}} = \ left (u_ {0}, u_ {1}, \ dots u_ {k-1} \ right)}$ ${\ displaystyle \ mathbf {v_ {k}} = \ left (v_ {0}, v_ {1}, \ dots v_ {k-1} \ right)}$

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

Le nuove direzioni di discesa e sono quindi ortogonali ai residui: e , che soddisfano la stessa e ( ). ${\ 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} = LA \ sinistra (1-P_ {k} \ destra) LA ^ {- 1} r_ {j}}$ ${\ displaystyle s_ {k} = \ sinistra (1-P_ {k} \ destra) ^ {*} s_ {j}}$ ${\ displaystyle i, j <k}$

Il metodo del gradiente biconiugato offre quindi la seguente scelta:

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

e .

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

Questa particolare scelta permette poi di evitare una valutazione diretta di e , e quindi di aumentare la velocità di esecuzione dell'algoritmo. $P_ {k}$ $A ^ {{- 1}}$

Proprietà

Se è autoaggiunto , e , quindi , e il metodo del gradiente coniugato produce lo stesso risultato . ${\ 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}}$

In dimensioni finite , al più tardi quando : Il metodo del gradiente biconiugato fornisce la soluzione esatta dopo aver coperto tutto lo spazio ed è quindi un metodo diretto. ${\ displaystyle x_ {n} = A ^ {- 1} b}$ ${\ displaystyle P_ {n} = 1}$

La sequenza prodotta dall'algoritmo è biortogonale (in) : e per . ${\ displaystyle f_ {i} ^ {*} Ad_ {j} = 0}$ ${\ displaystyle s_ {i} ^ {*} M ^ {- 1} r_ {j} = 0}$ ${\ displaystyle i \ neq j}$

IF è un polinomio con , allora . L'algoritmo è quindi composto da proiezioni su sottospazi di Krylov (en) ; ${\ displaystyle p_ {j '}}$ ${\ Displaystyle deg \ left (p_ {j '} \ right) + j <k}$ ${\ displaystyle s_ {k} ^ {*} p_ {j '} \ sinistra (M ^ {- 1} A \ destra) u_ {j} = 0}$

IF è un polinomio con , allora . ${\ displaystyle p_ {i '}}$ ${\ Displaystyle i + deg \ left (p_ {i '} \ right) <k}$ ${\ displaystyle v_ {i} ^ {*} p_ {i '} \ left (AM ^ {- 1} \ right) r_ {k} = 0}$

( fr ) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Metodo del gradiente biconiugato " ( vedere l'elenco degli autori ) .