数值计算解线性方程组的迭代法.docVIP

第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； 　　? ENDWHILE 　　5．输出方程组的解 　　例4.1 用雅可比方法解下列方程组： 　　解：方程的迭代格式： ? 　　或 ? 　　雅可比迭代收敛。 　　取初始值，计算结果由表4.1所示。 表4.1 计算结果 0 　　1 　　1 　　1 ? 1 　　-1.5 　　1.6 　　0.9 　　0.25 2 　　-1.25 　　2.08 　　1.09 　　0.48 3 　　-0.915 　　2.068 　　1.017 　　0.335 4 　　-0.9575 　　1.9864 　　0.9847 　　0.0816 5 　　-1.01445 　　1.98844 　　0.99711 　　0.05695 6 　　-1.00722 　　2.00231 　　1.0026 　　0.01387 7 　　-0.997543 　　2.00197 　　1.00049 　　0.0096