第五章方程组的迭代法课件

第五章解线性方程组的迭代法第五章1 实际问题经过简单的分析可以直接归结 为线性方程组，或者微分方程，后者可以转换为线性方程组。两种方法：直接法：中小型稠密矩阵 迭代法：大型稀疏矩阵 实际问题经过简单的分析可以直接归结 为线性方程组，或者25.1 Jacobi迭代法和Gauss-Seidel迭代法设线性方程组简记 AX=b5.1 Jacobi迭代法和Gauss-Seidel迭代法设3n其中其中4n将方程组AX=b，改写成便于迭代的形式 建立迭代格式 向量X(0)事先给定，称为初始解向量，用公式逐步迭代求解的方法叫做迭代法.如果由产生的序列 收敛，则称迭代法是收敛的，否则称为迭代法发散.将方程组AX=b，改写成便于迭代的形式5n若将方程组改写为若61Jacobi迭代法n建立迭代格式其中1Jacobi迭代法7Jacobi迭代法的矩阵表示n将方程组AX=b的系数A分解成 A=L+D+U其中D=diag(a11,a22,ann)，L和U分别是A的对角线下方元素和上方元素组成的严格下三角阵与严格上三角阵.即Jacobi迭代法的矩阵表示将方程组AX=b的系数A分解成8第五章方程组的迭代法课件9迭代格式为：迭代格式为：10对应的分量表示形式为：另外一种矩阵形式是：对应的分量表示形式为：另外一种矩阵形式是：11的Jacobi迭代格式（三种）写出方程组写出方程组12第五章方程组的迭代法课件13Matlab计算过程如下：Matlab计算过程如下：14 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 A=1-2 2;-1 3 0;2 0 7 U15-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-inv(D)*(L+U)b=5;-1;2;16 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 I=eye(3)17分量形式为:分量形式为:18Gauss-Seidel迭代法方程组改写为：即得迭代格式：Gauss-Seidel迭代法方程组改写为：即得迭代格式：19Gauss-Seidel迭代法n迭代格式的分量形式：其中 Gauss-Seidel迭代法迭代格式的分量形式：20的Gauss-Seidel迭代格式（两种）写出方程组写出方程组21例n 分别用Jacobi迭代法与Gauss-Seidel迭代法求解方程组精确到小数点后四位，并要求分别写出其迭代法的分量形式和矩阵形式.例 分别用Jacobi迭代法与Gauss-Seidel迭代22解n（1）用Jacobi迭代法，其迭代法的分量形式为解（1）用Jacobi迭代法，其迭代法的分量形式为23迭代法的矩阵形式为其中 迭代法的矩阵形式为24 25 取初值X(0)=(0,0,0)，迭代可得 取初值X(0)=(0,0,0)，迭代可得26迭代7次，得近似值.n（2）用Gauss-Seidel迭代法，其迭代法的分量形式为迭代7次，得近似值.27其迭代法的矩阵形式为其中其迭代法的矩阵形式为28 29 30即 取初值X(0)=(0,0,0)，迭代可得即 31迭代5次，得近似值第五章方程组的迭代法课件32nQuestion:如何判断迭代出来的值和真实根很接近？Question:33 向量和矩阵的模（范数）n为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。向量和矩阵的模（范数）为了研究线性方程组近似解的误差估计34向量和矩阵的范数n在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。向量和矩阵的范数在一维数轴上，实轴上任意一点x到原点的距离35向量和矩阵的范数n而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。推广到n维空间，则称为向量范数。向量和矩阵的范数而在二维平面上，平面上任意一点P(x,y)36向量范数向量范数37常见的向量范数常见的向量范数38nQuestion:如何判断迭代出的向量是真实解的精度较高的近似值？Question:39第五章方程组的迭代法课件40向量范数性质向量范数性质41第五章方程组的迭代法课件42例已知例已知43 矩阵范数 矩阵范数44相容范数相容范数45算子范数（了解）算子范数（了解）46算子范数（了解）算子范数（了解）47算子范数（了解）算子范数（了解）48算子范数（了解）算子范数（了解）49常见的矩阵范数列范数行范数谱范数常见的矩阵范数列范数行范数谱范数50例题例题51nMatlab计算过程如下：2范数：norm(A)1范数：norm(A,1)无穷范数：norm(A,inf)Matlab计算过程如下：52 矩阵的谱半径 矩阵的谱半径53例题求特征值命令eig(A)例题求特征值命令54第五章方程组的迭代法课件55第五章方程组的迭代法课件56例解：A的特征值为：lm=eig(A)lm=1.500000000000000+1.658312395177701i 1.500000000000000-1.658312395177701i 1.000000000000000 例解：A的特征值为：57norm(lm,inf)ans=2.236067977499790norm(lm,inf)ans=58 lm1=eig(A*A)lm1=0.936075017171059 2.921124938072438 9.142800044756498sqrt(9.142800044756498)ans=3.023706342348162 lm1=eig(A*A)lm1=sqrt(9.159迭代法的收敛性n定理（迭代法的基本收敛定理）迭代过程 X(k+1)=BX(k)+g对于任意任意初始向量X(0)及右端向量g均收敛的充要条件是迭代矩阵B的谱半径(B)1,并且(B)愈小，收敛速度愈快.迭代法的收敛性定理（迭代法的基本收敛定理）60第五章方程组的迭代法课件61B表示B的任意一种范数定理（迭代法收敛的充分条件）若迭代法 X(k+1)=BX(k)+g的迭代矩阵B满足，B=q1,则对于任意的初始向量X(0)与右端向量g迭代法收敛.B表示B的任意一种范数定理（迭代法收敛的充分条件）62第五章方程组的迭代法课件63nQuestion:nJacobi迭代法和Gauss-Seidel迭代法如何判断收敛性？Question:64第五章方程组的迭代法课件65收敛的判别条件收敛的判别条件66要清楚掌握如下概念：对角占优矩阵，强对角占优矩阵可约矩阵，不可约矩阵正定矩阵要清楚掌握如下概念：67第五章方程组的迭代法课件68第五章方程组的迭代法课件69n定理 若线性代数方程组AX=b的系数方阵A=(aij)nn是按行(或按列)严格对角占优的，则Jacobi迭代法和Gauss-Seidel迭代 法都是收敛的.定理70n 对方程组通过调整方程的次序，建立收敛的Jacobi迭代格式和Gauss-Seidel迭代格式.n解 将第二个方程调到第一行、第三个方程调到第二行、第一个方程调到第三行后有同解方程组 对方程组71这是按行严格对角占优方程组，故Jacobi和Gauss-Seidel迭代法都一定收敛.nJacobi迭代格式为 第五章方程组的迭代法课件72nGauss-Seidel迭代格式为 第五章方程组的迭代法课件73第五章方程组的迭代法课件74n定理n系数矩阵是不可约矩阵且是对角占优矩阵，Jacobi迭代和Gauss-Seidel迭代都收敛。第五章方程组的迭代法课件75第五章方程组的迭代法课件76n定理 若线性方程组的系数矩阵是对称正定矩阵，则用Jacobi迭代法和Gauss-Seidel迭代法都是收敛的。怎么判断矩阵是对称正定矩阵，直接从定义判断不方便，我们有如下几个结论：定理77 对称性很容易判定。下面是如何判断正定性。n矩阵的任意特征值都大于零，则是正定矩阵；n矩阵的所有顺序主子式都大于零，则是正定矩阵；n对角元素为正实数and（强对角占优矩阵or不可约对角占优矩阵），是正定矩阵。对称性很容易判定。下面是如何判断正定性。78n顺序主子式：位于矩阵的前k行前k列交叉位置上的元素按照原来的相对位置构成的k阶子式。顺序主子式是行列式。Question:如何编程计算所有的顺序主子式？（让学生黑板练习）顺序主子式：79SOR方法nSOR方法n为了解决大型稀疏矩阵收敛速度较慢，引入SOR方法。SOR方法SOR方法80回忆回忆Gauss-Seidel迭代迭代松弛迭代法是由Gauss-Seidel迭代演变而来，具体步骤如下：回忆Gauss-Seidel迭代松弛迭代法是由Gauss-S81