Biconjugate gradientní metoda - Biconjugate gradient method

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (září 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, konkrétněji v numerická lineární algebra, biconjugate gradientní metoda je algoritmus vyřešit soustavy lineárních rovnic

${displaystyle Ax = b.,}$

Na rozdíl od metoda konjugovaného gradientu, tento algoritmus nevyžaduje matice ${displaystyle A}$ být sebe-adjunkt, ale místo toho je třeba provést násobení pomocí konjugovat transponovat A^*.

Algoritmus

1. Zvolte počáteční odhad ${displaystyle x_ {0},}$, dva další vektory ${displaystyle x_ {0} ^ {*}}$ a ${displaystyle b ^ {*},}$ a a kondicionér ${displaystyle M,}$
2. ${displaystyle r_ {0} leftarrow b-A, x_ {0},}$
3. ${displaystyle r_ {0} ^ {*} leftarrow b ^ {*} - x_ {0} ^ {*}, A}$
4. ${displaystyle p_ {0} leftarrow M ^ {- 1} r_ {0},}$
5. ${displaystyle p_ {0} ^ {*} leftarrow r_ {0} ^ {*} M ^ {- 1},}$
6. pro ${displaystyle k = 0,1, ldots}$ dělat
   1. ${displaystyle alpha _ {k} leftarrow {r_ {k} ^ {*} M ^ {- 1} r_ {k} nad p_ {k} ^ {*} Ap_ {k}},}$
   2. ${displaystyle x_ {k + 1} leftarrow x_ {k} + alpha _ {k} cdot p_ {k},}$
   3. ${displaystyle x_ {k + 1} ^ {*} leftarrow x_ {k} ^ {*} + {overline {alpha _ {k}}} cdot p_ {k} ^ {*},}$
   4. ${displaystyle r_ {k + 1} leftarrow r_ {k} -alpha _ {k} cdot Ap_ {k},}$
   5. ${displaystyle r_ {k + 1} ^ {*} leftarrow r_ {k} ^ {*} - {overline {alpha _ {k}}} cdot p_ {k} ^ {*}, A}$
   6. ${displaystyle eta _ {k} leftarrow {r_ {k + 1} ^ {*} M ^ {- 1} r_ {k + 1} nad r_ {k} ^ {*} M ^ {- 1} r_ {k} },}$
   7. ${displaystyle p_ {k + 1} leftarrow M ^ {- 1} r_ {k + 1} + eta _ {k} cdot p_ {k},}$
   8. ${displaystyle p_ {k + 1} ^ {*} leftarrow r_ {k + 1} ^ {*} M ^ {- 1} + {overline {eta _ {k}}} cdot p_ {k} ^ {*}, }$

Ve výše uvedené formulaci se počítá ${displaystyle r_ {k},}$ a ${displaystyle r_ {k} ^ {*}}$ uspokojit

${displaystyle r_ {k} = b-Ax_ {k} ,,}$

${displaystyle r_ {k} ^ {*} = b ^ {*} - x_ {k} ^ {*}, A}$

a tedy jsou příslušné zbytky souhlasí s ${displaystyle x_ {k},}$ a ${displaystyle x_ {k} ^ {*}}$, jako přibližné řešení systémů

${displaystyle Ax = b ,,}$

${displaystyle x ^ {*}, A = b ^ {*} ,;}$

${displaystyle x ^ {*}}$ je adjoint, a ${displaystyle {overline {alpha}}}$ je komplexní konjugát.

Nepodmíněná verze algoritmu

1. Zvolte počáteční odhad ${displaystyle x_ {0},}$,
2. ${displaystyle r_ {0} leftarrow b-A, x_ {0},}$
3. ${displaystyle {hat {r}} _ {0} leftarrow {hat {b}} - {hat {x}} _ {0} A}$
4. ${displaystyle p_ {0} leftarrow r_ {0},}$
5. ${displaystyle {hat {p}} _ {0} leftarrow {hat {r}} _ {0},}$
6. pro ${displaystyle k = 0,1, ldots}$ dělat
   1. ${displaystyle alpha _ {k} leftarrow {{hat {r}} _ {k} r_ {k} over {hat {p}} _ {k} Ap_ {k}},}$
   2. ${displaystyle x_ {k + 1} leftarrow x_ {k} + alpha _ {k} cdot p_ {k},}$
   3. ${displaystyle {hat {x}} _ {k + 1} leftarrow {hat {x}} _ {k} + alpha _ {k} cdot {hat {p}} _ {k},}$
   4. ${displaystyle r_ {k + 1} leftarrow r_ {k} -alpha _ {k} cdot Ap_ {k},}$
   5. ${displaystyle {hat {r}} _ {k + 1} leftarrow {hat {r}} _ {k} -alpha _ {k} cdot {hat {p}} _ {k} A}$
   6. ${displaystyle eta _ {k} leftarrow {{hat {r}} _ {k + 1} r_ {k + 1} over {hat {r}} _ {k} r_ {k}},}$
   7. ${displaystyle p_ {k + 1} leftarrow r_ {k + 1} + eta _ {k} cdot p_ {k},}$
   8. ${displaystyle {hat {p}} _ {k + 1} leftarrow {hat {r}} _ {k + 1} + eta _ {k} cdot {hat {p}} _ {k},}$

Diskuse

Metoda biconjugate gradientu je numericky nestabilní^{[Citace je zapotřebí ]} (v porovnání s metoda stabilizovaná bikonjugovaným gradientem ), ale z teoretického hlediska velmi důležité. Definujte iterační kroky

${displaystyle x_ {k}: = x_ {j} + P_ {k} A ^ {- 1} vlevo (b-Ax_ {j} vpravo),}$

${displaystyle x_ {k} ^ {*}: = x_ {j} ^ {*} + vlevo (b ^ {*} - x_ {j} ^ {*} Aight) P_ {k} A ^ {- 1}, }$

kde ${displaystyle j$ pomocí související projekce

${displaystyle P_ {k}: = mathbf {u} _ {k} vlevo (mathbf {v} _ {k} ^ {*} Amathbf {u} _ {k} ight) ^ {- 1} mathbf {v} _ {k} ^ {*} A,}$

s

${displaystyle mathbf {u} _ {k} = left [u_ {0}, u_ {1}, dots, u_ {k-1} ight],}$

${displaystyle mathbf {v} _ {k} = left [v_ {0}, v_ {1}, dots, v_ {k-1} ight].}$

Tyto související projekce mohou být iterovány jako

${displaystyle P_ {k + 1} = P_ {k} + vlevo (1-P_ {k} noc) u_ {k} častěji {v_ {k} ^ {*} Aleft (1-P_ {k} noc) nad v_ {k} ^ {*} Aleft (1-P_ {k} ight) u_ {k}}.}$

Vztah k Kvazi-Newtonovy metody je dána ${displaystyle P_ {k} = A_ {k} ^ {- 1} A}$ a ${displaystyle x_ {k + 1} = x_ {k} -A_ {k + 1} ^ {- 1} vlevo (Ax_ {k} -bight)}$, kde

${displaystyle A_ {k + 1} ^ {- 1} = A_ {k} ^ {- 1} + vlevo (1-A_ {k} ^ {- 1} Aight) u_ {k} často {v_ {k} ^ {*} doleva (1-AA_ {k} ^ {- 1} ight) nad v_ {k} ^ {*} Aleft (1-A_ {k} ^ {- 1} Aight) u_ {k}}.}$

Nové směry

${displaystyle p_ {k} = left (1-P_ {k} ight) u_ {k},}$

${displaystyle p_ {k} ^ {*} = v_ {k} ^ {*} Aleft (1-P_ {k} ight) A ^ {- 1}}$

jsou pak kolmé na zbytky:

${displaystyle v_ {i} ^ {*} r_ {k} = p_ {i} ^ {*} r_ {k} = 0,}$

${displaystyle r_ {k} ^ {*} u_ {j} = r_ {k} ^ {*} p_ {j} = 0,}$

které samy uspokojují

${displaystyle r_ {k} = Aleft (1-P_ {k} ight) A ^ {- 1} r_ {j},}$

${displaystyle r_ {k} ^ {*} = r_ {j} ^ {*} vlevo (1-P_ {k} ight)}$

kde ${displaystyle i, j$.

Metoda gradientu biconjugate nyní dělá speciální volbu a používá nastavení

${displaystyle u_ {k} = M ^ {- 1} r_ {k} ,,}$

${displaystyle v_ {k} ^ {*} = r_ {k} ^ {*}, M ^ {- 1}.,}$

S touto konkrétní volbou, explicitní hodnocení ${displaystyle P_ {k}}$ a A⁻¹ jsou vyloučeny a algoritmus má formu uvedenou výše.

Vlastnosti

• Li ${displaystyle A = A ^ {*},}$ je sebe-adjunkt, ${displaystyle x_ {0} ^ {*} = x_ {0}}$ a ${displaystyle b ^ {*} = b}$, pak ${displaystyle r_ {k} = r_ {k} ^ {*}}$, ${displaystyle p_ {k} = p_ {k} ^ {*}}$a metoda konjugovaného gradientu produkuje stejnou sekvenci ${displaystyle x_ {k} = x_ {k} ^ {*}}$ za poloviční výpočetní cenu.
• Sekvence produkované algoritmem jsou biortogonální, tj., ${displaystyle p_ {i} ^ {*} Ap_ {j} = r_ {i} ^ {*} M ^ {- 1} r_ {j} = 0}$ pro ${displaystyle ieq j}$.
• -li ${displaystyle P_ {j '},}$ je polynom s ${displaystyle mathrm {deg} left (P_ {j '} ight) + j$, pak ${displaystyle r_ {k} ^ {*} P_ {j '} vlevo (M ^ {- 1} Aight) u_ {j} = 0}$. Algoritmus tak vytváří projekce na Krylovský podprostor.
• -li ${displaystyle P_ {i '},}$ je polynom s ${displaystyle i + mathrm {deg} left (P_ {i '} ight)$, pak ${displaystyle v_ {i} ^ {*} P_ {i '} vlevo (AM ^ {- 1} vpravo) r_ {k} = 0}$.

Viz také

• Metoda stabilizovaná pomocí dvojitého konjugátu
• Konjugovaná metoda přechodu

Reference

• Fletcher, R. (1976). Watson, G. Alistair (ed.). "Konjugované gradientní metody pro neurčité systémy". Numerická analýza. Přednášky z matematiky. Springer Berlin / Heidelberg. 506: 73–89. doi:10.1007 / BFb0080109. ISBN  978-3-540-07610-0. ISSN  1617-9692.
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Oddíl 2.7.6“. Numerické recepty: Umění vědecké práce na počítači (3. vyd.). New York: Cambridge University Press. ISBN  978-0-521-88068-8.