Konjugovaná reziduální metoda - Conjugate residual method

The konjugovaná reziduální metoda je iterativní numerická metoda slouží k řešení soustavy lineárních rovnic. To je Krylovova podprostorová metoda velmi podobné mnohem populárnějším metoda sdruženého gradientu, s podobnými konstrukčními a konvergenčními vlastnostmi.

Tato metoda se používá k řešení lineárních rovnic formy

${ displaystyle mathbf {A} mathbf {x} = mathbf {b}}$

kde A je invertibilní a Hermitova matice, a b je nenulová.

Metoda zbytkového konjugátu se liší od úzce související metoda sdruženého gradientu primárně v tom, že zahrnuje více numerických operací a vyžaduje více úložného prostoru, ale systémová matice musí být pouze hermitská, nikoli symetrická pozitivní konečná.

Vzhledem k (libovolnému) počátečnímu odhadu řešení ${ displaystyle mathbf {x} _ {0}}$, metoda je uvedena níže:

${ displaystyle { begin {aligned} & mathbf {x} _ {0}: = { text {Nějaký počáteční odhad}} & mathbf {r} _ {0}: = mathbf {b} - mathbf {Ax} _ {0} & mathbf {p} _ {0}: = mathbf {r} _ {0} & { text {Iterate, s}} k { text {začíná zavináč}} 0: & qquad alpha _ {k}: = { frac { mathbf {r} _ {k} ^ { mathrm {T}} mathbf {Ar} _ {k}} { ( mathbf {Ap} _ {k}) ^ { mathrm {T}} mathbf {Ap} _ {k}}} & qquad mathbf {x} _ {k + 1}: = mathbf {x} _ {k} + alpha _ {k} mathbf {p} _ {k} & qquad mathbf {r} _ {k + 1}: = mathbf {r} _ {k} - alpha _ {k} mathbf {Ap} _ {k} & qquad beta _ {k}: = { frac { mathbf {r} _ {k + 1} ^ { mathrm {T }} mathbf {Ar} _ {k + 1}} { mathbf {r} _ {k} ^ { mathrm {T}} mathbf {Ar} _ {k}}} & qquad mathbf {p} _ {k + 1}: = mathbf {r} _ {k + 1} + beta _ {k} mathbf {p} _ {k} & qquad mathbf {Ap} _ { k + 1}: = mathbf {Ar} _ {k + 1} + beta _ {k} mathbf {Ap} _ {k} & qquad k: = k + 1 end {zarovnáno}} }$

iteraci lze zastavit jednou ${ displaystyle mathbf {x} _ {k}}$ bylo považováno za konvergované. Jediným rozdílem mezi touto metodou a metodou konjugovaného gradientu je výpočet ${ displaystyle alpha _ {k}}$ a ${ displaystyle beta _ {k}}$ (plus volitelný přírůstkový výpočet ${ displaystyle mathbf {Ap} _ {k}}$ na konci).

Poznámka: výše uvedený algoritmus lze transformovat tak, aby se v každé iteraci vytvořilo pouze jedno násobení symetrické matice-vektor.

Předběžná úprava

Provedením několika substitucí a proměnných změn lze předem připravenou reziduální metodu konjugátu odvodit stejným způsobem, jaký se provádí pro metodu konjugovaného gradientu:

${ displaystyle { begin {aligned} & mathbf {x} _ {0}: = { text {Nějaký počáteční odhad}} & mathbf {r} _ {0}: = mathbf {M} ^ {-1} ( mathbf {b} - mathbf {Ax} _ {0}) & mathbf {p} _ {0}: = mathbf {r} _ {0} & { text {Iterovat, s}} k { text {od}} 0: & qquad alpha _ {k}: = { frac { mathbf {r} _ {k} ^ { mathrm {T} } mathbf {A} mathbf {r} _ {k}} {( mathbf {Ap} _ {k}) ^ { mathrm {T}} mathbf {M} ^ {- 1} mathbf {Ap } _ {k}}} & qquad mathbf {x} _ {k + 1}: = mathbf {x} _ {k} + alpha _ {k} mathbf {p} _ {k} & qquad mathbf {r} _ {k + 1}: = mathbf {r} _ {k} - alpha _ {k} mathbf {M} ^ {- 1} mathbf {Ap} _ {k} & qquad beta _ {k}: = { frac { mathbf {r} _ {k + 1} ^ { mathrm {T}} mathbf {A} mathbf {r} _ {k + 1}} { mathbf {r} _ {k} ^ { mathrm {T}} mathbf {A} mathbf {r} _ {k}}} & qquad mathbf {p} _ {k + 1}: = mathbf {r} _ {k + 1} + beta _ {k} mathbf {p} _ {k} & qquad mathbf {Ap} _ {k + 1 }: = mathbf {A} mathbf {r} _ {k + 1} + beta _ {k} mathbf {Ap} _ {k} & qquad k: = k + 1 konec {zarovnaný}}}$

The kondicionér ${ displaystyle mathbf {M} ^ {- 1}}$ musí být symetrický pozitivní určitý. Všimněte si, že zbytkový vektor se zde liší od zbytkového vektoru bez předběžné úpravy.

Reference

• Yousef Saad, Iterační metody pro řídké lineární systémy (2. vyd.), Strana 194, SIAM. ISBN  978-0-89871-534-7.