第五章解线性方程组的迭代法 实际问题经过简单的分析可以直接归结 为线性方程组，或者微分方程，后者可以转换为线性方程组。 两种方法： 直接法：中小型稠密矩阵 迭代法：大型稀疏矩阵5.1 Jacobi迭代法和Gauss-Seidel迭代法设线性方程组简记 AX=bn其中n将方程组AX=b，改写成便于迭代的形式 建立迭代格式 向量X(0)事先给定，称为初始解向量，用公式逐步迭代求解的方法叫做迭代法. 如果由产生的序列 收敛，则称迭代法是收敛的，否则称为迭代法发散. n若将方程组改写为1Jacobi迭代法n建立迭代格式其中Jacobi迭代法的矩阵表示n将方程组AX=b的系数A分解成 A=L +D+U其中D=diag(a11,a22,ann) ，L和U分别是A的对角线下方元素和上方元素组成的严格下三角阵与严格上三角阵. 即迭代格式为：对应的分量表示形式为：另外一种矩阵形式是：的Jacobi迭代格式（三种）写出方程组Matlab计算过程如下： A=1 -2 2;-1 3 0;2 0 7A = 1 -2 2 -1 3 0 2 0 7 U=triu(A,1)U = 0 -2 2 0 0 0 0 0 0 L=tril(A,-1)L = 0 0 0 -1 0 0 2 0 0 D=diag(diag(A)D = 1 0 0 0 3 0 0 0 7 -inv(D)*(L+U)ans = 0 2.000000000000000 -2.000000000000000 0.333333333333333 0 0 -0.285714285714286 0 0 b=5;-1;2;inv(D)*bans = 5.000000000000000 -0.333333333333333 0.285714285714286 I=eye(3)I = 1 0 0 0 1 0 0 0 1 I-inv(D)*Aans = 0 2.000000000000000 -2.000000000000000 0.333333333333333 0 0 -0.285714285714286 0 0分量形式为:Gauss-Seidel迭代法方程组改写为：即得迭代格式：Gauss-Seidel迭代法n迭代格式的分量形式：其中 的Gauss-Seidel迭代格式（两种）写出方程组例n 分别用Jacobi迭代法与Gauss-Seidel迭代法求解方程组精确到小数点后四位，并要求分别写出其迭代法的分量形式和矩阵形式. 解n（1）用Jacobi迭代法，其迭代法的分量形式为迭代法的矩阵形式为其中 取初值X(0) =(0,0,0)，迭代可得迭代7次，得近似值. n（2）用Gauss-Seidel迭代法，其迭代法的分量形式为其迭代法的矩阵形式为其中 即 取初值X(0) =(0,0,0)，迭代可得迭代5次，得近似值nQuestion:如何判断迭代出来的值和真实根很接近？ 向量和矩阵的模（范数）n为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。向量和矩阵的范数n在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用| x1-x2 |表示。向量和矩阵的范数n而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。 推广到n维空间，则称为向量范数。向量范数常见的向量范数nQuestion:如何判断迭代出的向量是真实解的精度较高的近似值？向量范数性质例已知 矩阵范数相容范数算子范数（了解）算子范数（了解）算子范数（了解）算子范数（了解）常见的矩阵范数列范数行范数谱范数例题nMatlab计算过程如下：2范数： norm(A)1范数： norm(A,1)无穷范数： norm(A,inf) 矩阵的谱半径例题求特征值命令eig(A)例解：A的特征值为：lm=eig(A)lm = 1.500000000000000 + 1.658312395177701i 1.500000000000000 - 1.658312395177701i 1.000000000000000 norm(lm,inf)ans = 2.236067977499790 lm1=eig(A*A)lm1 = 0.936075017171059 2.921124938072438 9.142800044756498sqrt( 9.142800044756498)ans = 3.023706342348162迭代法的收敛性n定理（迭代法的基本收敛定理） 迭代过程 X(k+1) =BX(k) +g对于任意任意初始向量X(0)及右端向量g均收敛的充要条件是迭代矩阵B的谱半径(B)1, 并且(B) 愈小，收敛速度愈快. B表示B的任意一种范数定理（迭代法收敛的充分条件） 若迭代法 X(k+1) =BX(k) +g的迭代矩阵B满足，B=q1,则对于任意的初始向量X(0)与右端向量g迭代法收敛.nQuestion:nJacobi迭代法和Gauss-Seidel迭代法如何判断收敛性？收敛的判别条件要清楚掌握如下概念：对角占优矩阵，强对角占优矩阵可约矩阵，不可约矩阵正定矩阵n定理 若线性代数方程组AX=b的系数方阵A=(aij)nn是按行(或按列)严格对角占优的，则Jacobi迭代法和Gauss-Seidel迭代 法都是收敛的. n 对方程组通过调整方程的次序，建立收敛的Jacobi迭代格式和Gauss-Seidel迭代格式. n解 将第二个方程调到第一行、第三个方程调到第二行、第一个方程调到第三行后有同解方程组这是按行严格对角占优方程组，故Jacobi和Gauss-Seidel迭代法都一定收敛. nJacobi迭代格式为 nGauss-Seidel迭代格式为 n定理n系数矩阵是不可约矩阵且是对角占优矩阵，Jacobi迭代和Gauss-Seidel迭代都收敛。n定理 若线性方程组的系数矩阵是对称正定矩阵，则用Jacobi迭代法和Gauss-Seidel迭代法都是收敛的。 怎么判断矩阵是对称正定矩阵，直接从定义判断不方便，我们有如下几个结论： 对称性很容易判定。下面是如何判断正定性。n矩阵的任意特征值都大于零，则是正定矩阵；n矩阵的所有顺序主子式都大于零，则是正定矩阵；n对角元素为正实数and（强对角占优矩阵or不可约对角占优矩阵），是正定矩阵。n顺序主子式： 位于矩阵的前k行前k列交叉位置上的元素按照原来的相对位置构成的k阶子式。顺序主子式是行列式。Question: 如何编程计算所有的顺序主子式？（让学生黑板练习）SOR方法nSOR方法n为了解决大型稀疏矩阵收敛速度较慢，引入SOR方法。回忆回忆Gauss-Seidel迭代迭代松弛迭代法是由Gauss-Seidel迭代演变而来，具体步骤如下：