tovább fel vissza

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.
    tovább fel vissza
    bene@arpad.elte.hu