Kondisi konvergensi untuk skema iteratif

Aug 18 2020

Membiarkan $A$menjadi matriks tunggal dan simetris, dengan$\lambda_1=0$ dan $\lambda_i >0$ untuk $i=2,\ldots,n$.

Pertimbangkan iterasi

$$x^{*} = b- (A-I)x_k$$ $$x_{k+1} = \alpha x^{*} +(1- \alpha)x_k$$

Dalam kondisi yang mana $x_0$, $\alpha$ dan $b$, apakah itu menyatu dengan solusi sebenarnya dari $Ax =b$?


Saya benar-benar tidak bisa bergerak. Saya mencoba menghitung$e_{k+1}$tetapi saya tidak dapat menemukan hubungan yang berguna. Juga, saya tidak tahu bagaimana menemukan beberapa kendala$x_0$.


EDIT

Saya mencoba mengikuti komentar @uranix dan saya menemukan: $$e_{k+1} = \alpha b + (I - \alpha A) x_k -x $$

yang saya tulis ulang (menggunakan konsistensi) sebagai $$e_{k+1} = (I-\alpha A)(x_k -x)=(I- \alpha A)e_{k}$$

Karena itu $$e_{k+1} = (I-\alpha A)^k e_0$$

Sekarang saya membutuhkan radius spektral kurang dari $1$, tapi sejak $$\lambda(I -\alpha A)= 1-\lambda(A)$$ Saya tahu bahwa nilai eigen pertama adalah $1-\alpha \lambda_1=1-\alpha \cdot 0 = 1$

Jadi saya tidak bisa mengatakan apa-apa tentang konvergensi ... pasti ada cara lain. Memang, saya tidak menggunakan simetri dan juga tidak ada kondisi yang menyala$x_0$, seperti yang tertulis di teks

Jawaban

uranix Aug 18 2020 at 17:42

Sedikit petunjuk.

Seperti yang saya katakan di komentar, pertimbangkan dasar nilai eigen. Vektor basis bersifat ortogonal dan dapat diskalakan untuk membentuk basis ortonormal:$$ A \phi_m = \lambda_m \phi_m, \quad m = 1, \dots, m\\ (\phi_m, \phi_{m'}) = \delta_{mm'}. $$

Memperluas vektor kesalahan atas dasar $e_k = \sum_{m=1}^n c_{k,m} \phi_m$memungkinkan untuk menulis ulang kondisi konvergensi menggunakan koefisien ekspansi. Menggunakan identitas Parseval$$ \|e_k\|_2^2 = \sum_{m} c_{k,m}^2 $$ kami mendapatkannya $e_k \to 0$ terjadi hanya jika untuk semua $m$ setiap koefisien menyatu menjadi nol, yaitu $$ \lim_{k \to \infty} c_{k,m} = 0, \quad m = 1,\dots,n. $$

Berakting dengan $(I - \alpha A)^k$ di $e_0$ bertindak pada setiap nilai eigen secara terpisah: $$ e_k = (I - \alpha A)^k e_0 = (I - \alpha A)^k \sum_{m=1}^n c_{0,m} \phi_m = \\ = \sum_{m=1}^n c_{0,m} (I - \alpha A)^k \phi_m = \sum_{m=1}^n c_{0,m} (1 - \alpha \lambda_m)^k \phi_m. $$

Membandingkan sisi kanan dengan $\sum_{m=1}^n c_{k,m} \phi_m$ kami segera mendapatkan hubungannya $$ c_{k,m} = (1 - \alpha \lambda_m)^k c_{0,m}. $$

Sekarang terserah Anda untuk menemukan kondisi kapan $\lim_{k \to \infty} c_{k,m} = 0$ untuk setiap $m = 1,\dots,n$.