数值计算第章解线性方程组的迭代法.doc

第 4 章 解线性方程组的迭代法用迭代法求解线性方程组 与第 4 章非线性方程求根的方法相似，对方程组进行等价变换，构造同解方程组 (对 可构造各种等价方程组，如分解 ， 可逆，则由 得到 )，以此构造迭代关系式（4.1）任取初始向量 ，代入迭代式中，经计算得到迭代序列若迭代序列 收敛，设 的极限为 ，对迭代式两边取极限即 是方程组 的解，此时称迭代法收敛，否则称迭代法发散我们将看到，不同于非线性方程的迭代方法，解线性方程组的迭代收敛与否完全决定于迭代矩阵的性质，与迭代初始值的选取无关迭代法的优点是占有存储空间少，程序实现简单，尤其适用于大型稀疏矩阵；不尽人意之处是要面对判断迭代是否收敛和收敛速度的问题可以证明迭代矩阵的与谱半径 是迭代收敛的充分必要条件，其中 是矩阵 的特征根事实上，若 为方程组 的解，则有再由迭代式 可得到　　由线性代数定理， 的充分必要条件 因此对迭代法(4.1)的收敛性有以下两个定理成立定理 4.1 迭代法 收敛的充要条件是 定理 4.2 迭代法 收敛的充要条件是迭代矩阵 的谱半径因此，称谱半径小于 1 的矩阵为收敛矩阵计算矩阵的谱半径，需要求解矩阵的特征值才能得到，通常这是较为繁重的工作。

但是可以通过计算矩阵的范数等方法简化判断收敛的工作前面已经提到过，若||A|| p 矩阵 的范数，则总有 因此，若，则 必为收敛矩阵计算矩阵的 1 范数和 范数的方法比较简单，其中于是，只要迭代矩阵 满足 或 ，就可以判断迭代序列是收敛的要注意的是，当 或 时，可以有 ，因此不能判断迭代序列发散　　在计算中当相邻两次的向量误差的某种范数 小于给定精度时，则停止迭代计算，视 为方程组 的近似解（有关范数的详细定义请看 3.3 节4.1　雅可比（Jacobi ）迭代法4.1.1 雅可比迭代格式雅可比迭代计算元线性方程组（4.2）写成矩阵形式为 若 将式（ 4.2）中每个方程的 留在方程左边，其余各项移到方程右边；方程两边除以 则得到下列同解方程组：记 ，构造迭代形式　　或（4.3）迭代计算式（4.3）称为简单迭代或雅可比迭代任取初始向量 ，由式（4.3）可得到迭代向量序列雅可比迭代矩阵设由 ，得到等价方程：记不难看出， 正是迭代式（4.3）的迭代矩阵， 是常数项向量于是式（4.3）可写成矩阵形式：（4.4）其中：　　雅可比迭代算法下面描述解线性方程组 的雅可比迭代算法，为了简单起见，在算法中假定矩阵 满足雅可比迭代要求，即 ，并设由系数矩阵 构造迭代矩阵 是收敛的。

1．定义和输入系数矩阵 与常数项向量 的元素2．FOR i：=1，2，…，n{ //假定 ，形成常数项向量FOR j:=1,2,…,n} //形成迭代矩阵元素3．// 赋初始值，x1 和 x2 分别表示 和4．WHILE x1:=x2　　 x2:=B *x1+g // FOR u:=1,2,…,n// s:= g[u];// FOR v:=1,2,…,n s:=s+b[u][v]*x1[v];// x2[ u]:=s；ENDWHILE5．输出方程组的解例 4.1 用雅可比方法解下列方程组：解：方程的迭代格式：或雅可比迭代收敛取初始值 ，计算结果由表 4.1 所示表 4.1 计算结果0 　　1 　　1 　　1 1 　　-1.5 　　1.6 　　0.9 　　0.252 　　-1.25 　　2.08 　　1.09 　　0.483 　　-0.915 　　2.068 　　1.017 　　0.3354 　　-0.9575 　　1.9864 　　0.9847 　　0.08165 　　-1.01445 　　1.98844 　　0.99711 　　0.056956 　　-1.00722 　　2.00231 　　1.0026 　　0.013877 　　-0.997543 　　2.00197 　　1.00049 　　0.009687方程组的准确解是4.1.2 雅可比迭代收敛条件对于方程组 ，构造雅可比迭代格式 其中 ，。

当迭代矩阵的谱半径 时，迭代收敛，这是收敛的充分必要条件迭代矩阵的某范数 时，迭代收敛要注意的是范数小于 1 只是判断迭代矩阵收敛的充分条件，当迭代矩阵的一种范数||B||>1，并不能确定迭代矩阵是收敛还是发散例如， ，则 ，但它的特征值是 0.9 和 0.8是收敛矩阵当方程组的系数矩阵 具有某些性质时，可直接判定由它生成的雅可比迭代矩阵是收敛的定理 4.3 若方程组 的系数矩阵 ，满足下列条件之一，则其雅可比迭代法是收敛的1） 为行对角占优阵，即（2） 为列对角占优阵，即证明：（1）雅可比迭代矩阵 其中　　 （2） 为列对角优阵，故 为行对角占优阵，由系数矩阵 构造的迭代矩阵为行对角占优阵，则有又得到而 ，得由系数矩阵 构造的雅可比迭代矩阵收敛如矩阵 既是行对角占优阵，也是列对角占优阵）定理 4.4　若方程组系数矩阵 为对称正定阵，并且 也为对称正定，则雅可比迭代收敛4.2 高斯 -塞德尔（Gauss-Seidel）迭代法高斯- 赛德尔迭代计算　　在雅可比迭代中，用 的值代入方程（4.2）中计算出的值， 的计算公式是事实上，在计算 前，已经得到 的值，不妨将已算出的分量直接代入迭代式中，及时使用最新计算出的分量值。

因此 的计算公式可改为：即用向量 计算出 的值，用向量 计算出的值 ，用向量 计算出 的值，这种迭代格式称为高斯—塞德尔迭代对于方程组 AX=y ，如果由它构造高斯- 塞德尔迭代和雅可比迭代都收敛，那么，多数情况下高斯—塞德尔迭代比雅可比迭代的收敛效果要好，但是情况并非总是如此构造方程组 的高斯-塞德尔迭代格式的步骤与雅可比类似，设将式（4.1）中每个方程的 留在方程的左边，其余各项都移到方程的右边；方程两边除以 ，得到下列同解方程组：　　记 ，对方程组对角线以上的 取第 步迭代的数值，对角线以下的 取第 步迭代的数值，构造高斯—塞德尔迭代形式：（4.5）例 4.2 用高斯-塞德尔方法解方程组：解：方程的迭代格式：取初始值 有时，时，　　计算结果如表 4.2 所示表 4.2 计算结果012340　　　　　0　　　　　0－2.5　　　2.1　　　　1.14　　　　　2.5－0.88　　 2.004　　　0.9876　　　　1.62－1.0042　 1.9984　　 1.0006　　　　0.1242－1.0005　 2.0002　　 1.0000　　　　0.0037高斯—塞德尔迭代矩阵设写成等价矩阵表达式：构造迭代形式：有 　　　　（4.6）则高斯-塞德尔迭代式（ 4.4）为（4.7）　　 称为高斯-塞德尔迭代矩阵。

高斯- 塞德尔迭代算法高斯—塞德尔迭代的程序实现与雅可比迭代步骤大致相同，对于方程组 ，在前面的雅可比算法中，假定雅可比迭代矩阵为 表示 表示 ,其迭代核心部分是 下面的算法给出由 和 计算 的过程，省略了形成迭代矩阵和对 初始化的部分雅可比迭代的核心部分：WHILEfor(u:=1;u#include#define MAX-N 20 // 方程的最大维数#define MAXREPT 100#define epsilon 0.00001 //求解精度　　int main( ){ int n;int I, j, k;double err;static double a [MAX-N] [MAX-N],b[MAX-N] [MAX-N],c[MAX-N],g [MAX-N];static double x[MAX-N],nx[MAX-N];printf( 〃 \nInput n value(dim of Ax=c):〃); //输入方程的维数scanf(〃%d〃,&n);if(n>MAX-N){printf( 〃The input n is larger then MAX-N,please redefine the MAX-N.\n〃);}if(n# include# define MAX_N 20 / /方程的最大维数# define MAXREPT 100# define epsilon 0.00001 / /求解精度int main( ){ int n;int i, j, k ;double err, w;static double a[MAX_N][MAX_N], b[MAX_N][MAX_N],c[MAX_N],c[MAX_N],g[MAX_N] ;static double a[MAX_N] , nx[MAX_N];PRINTF(“\nlnput n value(dim of Ax=c ):”); //输入方程的维数Scanf(“% d”, &n);If (n>MAX_N)　　{ printf(“The input n-is larger then MAX_N, please redefine the MAX_N.\n”);return 1;}if (n=2)}printf(“w must between 1and 2. \ n”);return 1;{for(i=0; i