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

数值计算_第4章解线性方程组的迭代法————————————————————————————————作者：————————————————————————————————日期：个人收集整理勿做商业用途个人收集整理勿做商业用途个人收集整理勿做商业用途第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．FORi：=1,2,…，n｛//假定，形成常数项向量FORj:=1，2,…，n｝//形成迭代矩阵元素3．//赋初始值，x1和x2分别表示和4．WHILEx1：=x2x2：=B＊x1+g//FORu：=1，2，…,n//s:=g［u］；//FORv:=1，2,…，ns：=s+b[u]［v]＊x1［v］；//x2［u］:=s；ENDWHILE5．输出方程组的解例4.1用雅可比方法解下列方程组:解：方程的迭代格式：或雅可比迭代收敛.取初始值,计算结果由表4。1所示。表4.1计算结果01111—1。51。60.90.252—1.252。081.090.483-0。9152.0681。0170。3354—0.95751.98640.98470。08165—1。014451。988440.997110.056956-1。007222。002311.00260.013877—0.9975432.001971。000490。009687方程组的准确解是4。1.2雅可比迭代收敛条件对于方程组，构造雅可比迭代格式其中，。当迭代矩阵的谱半径时，迭代收敛，这是收敛的充分必要条件。迭代矩阵的某范数时，迭代收敛。要注意的是范数小于1只是判断迭代矩阵收敛的充分条件，当迭代矩阵的一种范数||B|｜〉1，并不能确定迭代矩阵是收敛还是发散。例如，，则，但它的特征值是0.9和0.8。是收敛矩阵。当方程组的系数矩阵具有某些性质时，可直接判定由它生成的雅可比迭代矩阵是收敛的.定理4。3若方程组的系数矩阵，满足下列条件之一，则其雅可比迭代法是收敛的.（1）为行对角占优阵，即（2)为列对角占优阵，即证明：(1)雅可比迭代矩阵其中（2）为列对角优阵，故为行对角占优阵，由系数矩阵构造的迭代矩阵为行对角占优阵，则有又得到而,得由系数矩阵构造的雅可比迭代矩阵收敛。（如矩阵既是行对角占优阵，也是列对角占优阵)定理4.4若方程组系数矩阵为对称正定阵，并且也为对称正定，则雅可比迭代收敛。4.2高斯-塞德尔（Gauss—S