Método de gradiente biconjugado

Na matemática , mais especificamente na análise numérica , o método do gradiente biconjugado é um algoritmo para resolver um sistema de equações lineares

{\ displaystyle Ax = b. \,}

Ao contrário do método do gradiente conjugado , este algoritmo não requer que a matriz seja auto-adjunta, por outro lado, o método requer multiplicações pela matriz adjacente . $NO$ $A ^ {*}$

Algoritmo

Escolha , um pré - condicionador regular (usado com frequência ) 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} \,}$ ;
para fazer ${\ 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 são os resíduos); ${\ 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} \ 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} \,}$

Discussão

O método é numericamente instável , mas é remediado pelo método estabilizado do gradiente biconjugado (en) , e continua sendo muito importante do ponto de vista teórico: definimos a iteração por e ( ) usando as seguintes projeções : ${\ 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}

Com e . Podemos iterar as próprias projeções, como ${\ 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}}}

As novas direções de descida e são ortogonais aos resíduos: e , que satisfazem as mesmas 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} = A \ left (1-P_ {k} \ right) A ^ {- 1} r_ {j}}$ ${\ displaystyle s_ {k} = \ left (1-P_ {k} \ right) ^ {*} s_ {j}}$ ${\ displaystyle i, j <k}$

O método do gradiente biconjugado oferece então a seguinte escolha:

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

e .

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

Esta escolha particular torna possível evitar uma avaliação direta de e , e, portanto, aumentar a velocidade de execução do algoritmo. $P_ {k}$ $A ^ {{- 1}}$

Propriedades

Se é auto-adjuntas , e , por conseguinte , e o método de gradiente conjugado produz o mesmo resultado . ${\ 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}}$

Em dimensões finitas , o mais tardar quando : O método do gradiente biconjugado fornece a solução exata após ter percorrido todo o espaço e, portanto, é um método direto. ${\ displaystyle x_ {n} = A ^ {- 1} b}$ ${\ displaystyle P_ {n} = 1}$

A sequência produzida pelo algoritmo é bi - ortogonal (in) : e para . ${\ displaystyle f_ {i} ^ {*} Ad_ {j} = 0}$ ${\ displaystyle s_ {i} ^ {*} M ^ {- 1} r_ {j} = 0}$ ${\ displaystyle i \ neq j}$

IF é um polinômio com , então . O algoritmo é, portanto, composto de projeções em subespaços de Krylov (en) ; ${\ displaystyle p_ {j '}}$ ${\ displaystyle deg \ left (p_ {j '} \ right) + j <k}$ ${\ displaystyle s_ {k} ^ {*} p_ {j '} \ left (M ^ {- 1} A \ right) u_ {j} = 0}$

IF é um polinômio com , então . ${\ displaystyle p_ {i '}}$ ${\ displaystyle i + deg \ left (p_ {i '} \ right) <k}$ ${\ displaystyle v_ {i} ^ {*} p_ {i '} \ left (AM ^ {- 1} \ right) r_ {k} = 0}$

( fr ) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado “ Método de gradiente Biconjugado ” ( veja a lista de autores ) .