Modern numerikus módszerek
Bene Gyula
Eötvös Loránd Tudományegyetem, Elméleti Fizikai Tanszék
1117 Budapest, Pázmány Péter sétány 1/A
Konjugált gradiens módszer: bizonyítások
Szimmetrikus, pozitív definit eset
Iteráció:
$${\bf r}_{j+1}={\bf r}_{j}-\alpha_j\;{\bf A}\cdot{\bf p}_{j}\;,\quad\quad (1)$$
$${\bf p}_{j+1}={\bf r}_{j+1}+\beta_{j}{\bf p}_{j}\;,\quad\quad (2)$$
$$\alpha_j=\frac{{\bf r}_j^T{\bf r}_{j}}{{\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_{j}}\;,\quad\quad (3)$$
$$\beta_j=\frac{{\bf r}_{j+1}^T{\bf r}_{j+1}}{{\bf r}_{j}^T{\bf r}_{j}}\;,\quad\quad (4)$$
$${\bf p}_0={\bf r}_0={\bf b}\quad\quad (5)$$
Állítás:
$${\bf p}_i^T\cdot{\bf A}\cdot{\bf p}_{k}=0\quad k< i\le j+1\;,\quad\quad (6)$$
$${\bf r}_i^T{\bf r}_{k}=0\quad k< i\le j+1\;,\quad\quad (7)$$
$${\bf r}_i^T{\bf p}_{k}=0\quad k< i\le j+1\;,\quad\quad (8)$$
$${\bf r}_i^T\cdot{\bf A}\cdot{\bf p}_{k-1}=0\quad k< i\le j+1\quad\quad (9)$$
Bizonyítás:
Előzetes megjegyzések:
(2)-ből és (5)-ből következik, hogy ${\bf p}_k$ az ${\bf r}_0$, ${\bf
r}_1$... ${\bf r}_k$ vektorok lineárkombinációja. Emiatt (7)-ből (8) azonnal
következik.
(6)-ból (2) alapján (9) következik. Elég tehát (6)-ot és (7)-et bizonyítani.
A $j=0$ eset:
Az ${\bf r}_1^T\cdot{\bf r}_{0}=0$ egyenlőség bizonyítása: (1) és
(3) szerint
$${\bf r}_1^T\cdot{\bf r}_{0}={\bf r}_0^T\cdot{\bf r}_{1}={\bf r}_0^T\cdot{\bf r}_{0}-\frac{{\bf r}_0^T{\bf r}_{0}}{{\bf p}_0^T\cdot{\bf A}\cdot{\bf p}_{0}}{\bf r}_0^T\cdot{\bf A}\cdot{\bf p}_{0}\;,$$
ami (5)-ből következően eltűnik.
Az ${\bf p}_1^T\cdot{\bf A}\cdot{\bf p}_{0}=0$ egyenlőség bizonyítása: (2) és
(4) szerint
$${\bf p}_1^T\cdot{\bf A}\cdot{\bf p}_{0}={\bf p}_0^T\cdot{\bf A}\cdot{\bf
p}_{1}={\bf p}_0^T\cdot{\bf A}\cdot{\bf r}_{1}+\frac{{\bf r}_{1}^T{\bf
r}_{1}}{{\bf r}_{0}^T{\bf r}_{0}}{\bf p}_0^T\cdot{\bf A}{\bf p}_0$$
Az első tagot (1) és (3) segítségével átalakítjuk:
$${\bf p}_0^T\cdot{\bf A}\cdot{\bf r}_{1}={\bf r}_1^T\cdot{\bf A}\cdot{\bf
p}_{0}=-\frac{{\bf p}_0^T\cdot{\bf A}\cdot{\bf p}_{0}}{{\bf r}_0^T{\bf
r}_{0}}{\bf r}_{1}^T\cdot\left({\bf r}_{1}-{\bf r}_{0}\right)=-\frac{{\bf
p}_0^T\cdot{\bf A}\cdot{\bf p}_{0}}{{\bf r}_0^T{\bf r}_{0}}{\bf
r}_{1}^T\cdot{\bf r}_{1}$$
Felhasználtuk a már bebizonyított ${\bf r}_1^T\cdot{\bf r}_{0}=0$
egyenlőséget. Ezt a kifejezést az előző egyenletbe visszaírva megkapjuk a
bizonyítandó állítást.
A $j>0$ eset:
Teljes indukcióval bizonyítunk. Feltételezzük, hogy (6) és (7) teljesül
$j\rightarrow j-1$-re, és ezt felhasználva bizonyítunk.
(7) bizonyítása:
Ha $i\le j$ és $k < i $, akkor az állítás az indukciós feltevés miatt igaz.
Ha $i= j+1$ és $k < j$, akkor (1) és (3) alapján
$${\bf r}_{j+1}^T{\bf r}_{k}
={\bf r}_{k}^T{\bf r}_{j+1}
={\bf r}_{k}^T{\bf r}_{j}
-\frac{{\bf r}_j^T{\bf r}_{j}}{{\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_{j}}{\bf r}_{k}^T\cdot{\bf A}\cdot{\bf p}_{j}$$
Az első tag az indukciós feltevés következtében eltűnik. A második tagban
${\bf r}_{k} $-t kifejezzük (2) segítségével, ekkor
$${\bf r}_{k}^T\cdot{\bf A}\cdot{\bf p}_{j}={\bf p}_{j}^T\cdot{\bf A}\cdot{\bf r}_{k}={\bf p}_{j}^T\cdot{\bf A}{\bf p}_{k}-\frac{1}{\beta_{k-1}}{\bf p}_{j}^T\cdot{\bf A}{\bf p}_{k-1}$$
Az indukciós feltevések miatt mindkét tag eltűnik.
Ha $i= j+1$ és $k = j$, akkor (1) és (3) alapján
$${\bf r}_{j+1}^T{\bf r}_{j}
={\bf r}_{j}^T{\bf r}_{j+1}
={\bf r}_{j}^T{\bf r}_{j}
-\frac{{\bf r}_j^T{\bf r}_{j}}{{\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_{j}}{\bf
r}_{j}^T\cdot{\bf A}\cdot{\bf p}_{j}$$
A második tagban
${\bf r}_{j} $-t kifejezzük (2) segítségével:
$${\bf r}_{j+1}^T{\bf r}_{j}
={\bf r}_{j}^T{\bf r}_{j}
-\frac{{\bf r}_j^T{\bf r}_{j}}{{\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_{j}}{\bf
p}_{j}^T\cdot{\bf A}\cdot{\bf p}_{j}+\frac{{\bf r}_j^T{\bf r}_{j}}{{\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_{j}}\frac{1}{\beta_{j-1}}{\bf
p}_{j-1}^T\cdot{\bf A}\cdot{\bf p}_{j}$$
Az utolsó tag az indukciós feltevés miatt eltűnik, a másik két tag pedig
kiejti egymást.
(6) bizonyítása:
Ha $i\le j$ és $k < i $, akkor az állítás az indukciós feltevés miatt igaz.
Ha $i= j+1$ és $k < j$, akkor (2) és (4) alapján
$${\bf p}_{j+1}^T\cdot{\bf A}{\bf p}_{k}
={\bf p}_{k}^T\cdot{\bf A}{\bf p}_{j+1}
={\bf p}_{k}^T\cdot{\bf A}{\bf r}_{j+1}
+\frac{{\bf r}_{j+1}^T{\bf r}_{j+1}}{{\bf r}_{j}^T{\bf r}_{j}}{\bf p}_{k}^T\cdot{\bf A}\cdot{\bf p}_{j}$$
A második tag az indukciós feltevés következtében eltűnik, az első tagban
pedig ${\bf A}\cdot{\bf p}_{k}$-t kifejezzük (1)
segítségével:
$${\bf p}_{k}^T\cdot{\bf A}{\bf r}_{j+1}={\bf r}_{j+1}^T\cdot{\bf A}{\bf
p}_{k}=-\frac{1}{\alpha_{k}}{\bf r}_{j+1}^T\left({\bf
r}_{k}-{\bf r}_{jk-1}\right)$$
Ez pedig a már bizonyított (7) egyenlőség miatt eltűnik.
Ha $i= j+1$ és $k = j$, akkor (2), (4), majd (1) és (3) alapján (mint fent)
$${\bf p}_{j+1}^T\cdot{\bf A}{\bf p}_{j}
={\bf p}_{j}^T\cdot{\bf A}{\bf p}_{j+1}
={\bf p}_{j}^T\cdot{\bf A}{\bf r}_{j+1}
+\frac{{\bf r}_{j+1}^T{\bf r}_{j+1}}{{\bf r}_{j}^T{\bf r}_{j}}{\bf
p}_{j}^T\cdot{\bf A}\cdot{\bf p}_{j}
=-\frac{{\bf p}_j^T\cdot{\bf A}\cdot{\bf p}_{j}}{{\bf r}_j^T{\bf r}_{j}}{\bf r}_{j+1}^T\left({\bf
r}_{j+1}-{\bf r}_{j}\right)+\frac{{\bf r}_{j+1}^T{\bf r}_{j+1}}{{\bf r}_{j}^T{\bf r}_{j}}{\bf
p}_{j}^T\cdot{\bf A}\cdot{\bf p}_{j}
$$
A már bebizonyított ${\bf r}_{j+1}^T{\bf r}_{j}=0$ összefüggés miatt a fenti
kifejezés azonosan eltűnik.
QED.
bene@arpad.elte.hu