线性方程组的迭代式求解方法
- 格式：docx
- 大小：9.96 KB
- 文档页数：5
线性方程组的迭代式求解方法
迭代法解方程的基本原理
1.概述
把 Ax=b 改写成 x=Bx+f ，如果这一迭代格式收敛，对这个式子不断迭代计算就可以得到方程组的解。
道理很简单：对 x^{(k+1)}=bx^{(k)}+f 两边取极限，显然如果收敛，则最终得到的解满足 \lim_{k\rightarrow\infty }
x^{(k)}=x^*=Bx^*+f ，从而必然满足原方程 Ax^*=b 。
迭代方法的本质在于这一次的输出可以当作下一次的输入，从而能够实现循环往复的求解，方法收敛时，计算次数越多越接近真实值。
2.收敛条件
充要条件：迭代格式 x=Bx+f 收敛的充要条件是 \rho (B)<1
充分条件： \Vert B\Vert <1
即 \Vert B\Vert <1 \Rightarrow \rho
(B)<1\Leftrightarrow 迭代收敛
一、Jacobi迭代法
怎样改写Ax=b ，从而进行迭代求解呢？一种最简单的迭代方法就是把第i行的 x_i 分离出来(假定 a_{ii} \ne 0 )：
\sum_{j=1}^{n}a_{ij}x_j=b_i\Rightarrow x_i=\frac{b_i-\sum_{j=1,j\ne i}^{n}a_{ij}x_j}{a_{ii}}\quad \\
这就是Jacobi(雅可比)迭代法。 迭代格式
给定
x^{(0)}=\left[x_1^{(0)},x_2^{(0)},\cdots,x_n^{(0)}\right]^T ，则Jacobi法的迭代格式（也称分量形式）为
x_i^{(k+1)}=\frac{1}{a_{ii}}\left ( {b_i-\sum_{j=1,j\ne i}^{n}a_{ij}x_j^{(k)}}\right),\quad
i=1,2,\cdots,n\\
矩阵形式
设 A=D-L-U。
Jacobi法的矩阵形式（也称向量形式）为
x^{(k+1)}=B_Jx^{(k)}+D^{-1}b\\
其中迭代矩阵 B_J=D^{-1}(L+U)
收敛条件
\begin{eqnarray} \left. \begin{array}{lll} \Vert
B_J\Vert <1 \\ A 严格对角占优\\ A, 2D-A对称正定
\end{array} \right \} \end{eqnarray} \Rightarrow \rho
(B_J)<1\Leftrightarrow 迭代收敛
特别地，若 A 对称正定且为三对角，则 \rho^2(B_J)=\rho
(B_G)<1 。
误差
先验误差： \Vert x^*-x^{(k)} \Vert \le \frac{\Vert
B_J\Vert ^k}{1-\Vert B_J\Vert}\Vert x^{(1)}-x^{(0)}\Vert 后验误差： \Vert x^*-x^{(k)} \Vert \le \frac{\Vert
B_J\Vert }{1-\Vert B_J\Vert}\Vert x^{(k)}-x^{(k-1)}\Vert
收敛速度
平均收敛速度： R_k(B_J)=-\ln\Vert {B_J}^k \Vert
^{\frac 1k}
渐进收敛速度： R(B_J)=-\ln\rho (B_J)
一般采用渐进收敛速度来近似地衡量迭代的快慢。
二、Gauss-Seidel迭代法
如何改进 Jacobi 迭代法呢？一种自然的想法是把 j
j>i 的部分分开(假定 a_{ii} \ne 0 )：
\sum_{j=1}^{n}a_{ij}x_j=b_i\Rightarrow x_i=\frac{b_i-\sum_{j=1}^{i-1}a_{ij}x_j-\sum_{j=i+1}^{n}a_{ij}x_j}{a_{ii}}\quad \\
由于在计算 x_i^{(k+1)} 时， x_j^{(k+1)}(j\le i-1) 已经算出来了，所以可以把这些新鲜出炉的量拿来代替老旧的迭代变量。这就是 Gauss-Seidel (高斯-塞德尔) 迭代法。
迭代格式
给定
x^{(0)}=\left[x_1^{(0)},x_2^{(0)},\cdots,x_n^{(0)}\right]^T ，则Gauss-Seidel法的迭代格式（也称分量形式）为
x_i^{(k+1)}=\frac{1}{a_{ii}}\left ( {b_i-\sum_{j=1}^{i-1}a_{ij}x_j^{(k+1)}}-\sum_{j=i+1}^{n}a_{ij}x_j^{(k)}\right),\quad
i=1,2,\cdots,n\\
矩阵形式
设 A=D-L-U。
Gauss-Seidel法的矩阵形式（也称向量形式）为
x^{(k+1)}=B_Gx^{(k)}+(D-L)^{-1}b\\
其中迭代矩阵 B_G=(D-L)^{-1}U
收敛条件
\begin{eqnarray} \left. \begin{array}{lll} \Vert
B_G\Vert <1 \\ A 严格对角占优\\ A对称正定 \end{array}
\right \} \end{eqnarray} \Rightarrow \rho
(B_G)<1\Leftrightarrow 迭代收敛
特别地，若 A 对称正定且为三对角，则 \rho^2(B_J)=\rho
(B_G)<1 。
误差
先验误差： \Vert x^*-x^{(k)} \Vert \le \frac{\Vert
B_G\Vert ^k}{1-\Vert B_G\Vert}\Vert x^{(1)}-x^{(0)}\Vert
后验误差： \Vert x^*-x^{(k)} \Vert \le \frac{\Vert
B_G\Vert }{1-\Vert B_G\Vert}\Vert x^{(k)}-x^{(k-1)}\Vert
收敛速度 平均收敛速度： R_k(B_G)=-\ln\Vert {B_G}^k \Vert
^{\frac 1k}
渐进收敛速度： R(B_G)=-\ln\rho (B_G)
