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

第五章解线性方程组的迭代法第五章1实际问题经过简单的分析可以直接归结为线性方程组，或者微分方程，后者可以转换为线性方程组。两种方法：直接法：中小型稠密矩阵迭代法：大型稀疏矩阵实际问题经过简单的分析可以直接归结为线性方程组，或者25.1Jacobi迭代法和Gauss-Seidel迭代法设线性方程组简记AX=b5.1Jacobi迭代法和Gauss-Seidel迭代法设3其中其中4将方程组AX=b，改写成便于迭代的形式建立迭代格式向量X(0)事先给定，称为初始解向量，用公式逐步迭代求解的方法叫做迭代法.如果由产生的序列收敛，则称迭代法是收敛的，否则称为迭代法发散.将方程组AX=b，改写成便于迭代的形式5若将方程组改写为若61．Jacobi迭代法建立迭代格式其中1．Jacobi迭代法7Jacobi迭代法的矩阵表示将方程组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-22;-130;207]A=1-22-130207>>U=triu(A,1)U=0-22000000>>L=tril(A,-1)L=000-100200>>D=diag(diag(A))D=100030007>>A=[1-22;-130;207]>>U15>>-inv(D)*(L+U)ans=02.000000000000000-2.0000000000000000.33333333333333300-0.28571428571428600>>b=[5;-1;2];inv(D)*bans=5.000000000000000-0.3333333333333330.285714285714286>>-inv(D)*(L+U)>>b=[5;-1;2];16>>I=eye(3)I=100010001>>I-inv(D)*Aans=02.000000000000000-2.0000000000000000.33333333333333300-0.28571428571428600>>I=eye(3)17分量形式为:分量形式为:18Gauss-Seidel迭代法方程组改写为：即得迭代格式：Gauss-Seidel迭代法方程组改写为：即得迭代格式：19Gauss-Seidel迭代法迭代格式的分量形式：其中

Gauss-Seidel迭代法迭代格式的分量形式：20的Gauss-Seidel迭代格式（两种）写出方程组写出方程组21例

分别用Jacobi迭代法与Gauss-Seidel迭代法求解方程组精确到小数点后四位，并要求分别写出其迭代法的分量形式和矩阵形式.例分别用Jacobi迭代法与Gauss-Seidel迭代22解（1）用Jacobi迭代法，其迭代法的分量形式为解（1）用Jacobi迭代法，其迭代法的分量形式为23迭代法的矩阵形式为其中迭代法的矩阵形式为24

25取初值X(0)=(0,0,0)′，迭代可得取初值X(0)=(0,0,0)′，迭代可得26迭代7次，得近似值.（2）用Gauss-Seidel迭代法，其迭代法的分量形式为迭代7次，得近似值.27其迭代法的矩阵形式为其中其迭代法的矩阵形式为28

29

30即取初值X(0)=(0,0,0)′，迭代可得即31迭代5次，得近似值第五章方程组的迭代法课件32Question:如何判断迭代出来的值和真实根很接近？Question:33向量和矩阵的模（范数）

为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，——向量和矩阵的范数。向量和矩阵的模（范数） 为了研究线性方程组近似解的误差估计34向量和矩阵的范数

在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。向量和矩阵的范数 在一维数轴上，实轴上任意一点x到原点的距离35向量和矩阵的范数

而在二维平面上，平面上任意一点P(x,y)到原点的距离用表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用表示。推广到n维空间，则称为向量范数。向量和矩阵的范数 而在二维平面上，平面上任意一点P(x,y)36向量范数

向量范数 37常见的向量范数

常见的向量范数 38Question:如何判断迭代出的向量是真实解的精度较高的近似值？Question:39第五章方程组的迭代法课件40向量范数性质向量范数性质41第五章方程组的迭代法课件42例已知例已知43矩阵范数矩阵范数44相容范数相容范数45算子范数（了解）算子范数（了解）46算子范数（了解）算子范数（了解）47算子范数（了解）算子范数（了解）48算子范数（了解）算子范数（了解）49常见的矩阵范数列范数行范数谱范数常见的矩阵范数列范数行范数谱范数50例题例题51Matlab计算过程如下：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.658312395177701i1.500000000000000-1.658312395177701i1.000000000000000例解：A的特征值为：57》norm(lm,inf)ans=2.236067977499790》norm(lm,inf)ans=58》lm1=eig(A*A')lm1=0.9360750171710592.9211249380724389.142800044756498》sqrt(9.142800044756498)ans=3.023706342348162》lm1=eig(A*A')lm1=》sqrt(9.159迭代法的收敛性定理（迭代法的基本收敛定理）迭代过程

X(k+1)

=BX(k)

+g对于任意初始向量X(0)及右端向量g均收敛的充要条件是迭代矩阵B的谱半径(B)<1,并且(B)愈小，收敛速度愈快.

迭代法的收敛性定理（迭代法的基本收敛定理）60第五章方程组的迭代法课件61B表示B的任意一种范数定理（迭代法收敛的充分条件）若迭代法

X(k+1)

=BX(k)

+g的迭代矩阵B满足，B=q<1,则对于任意的初始向量X(0)与右端向量g迭代法收敛.B表示B的任意一种范数定理（迭代法收敛的充分条件）62第五章方程组的迭代法课件63Question:Jacobi迭代法和Gauss-Seidel迭代法如何判断收敛性？Question:64第五章方程组的迭代法课件65收敛的判别条件收敛的判别条件66要清楚掌握如下概念：对角占优矩阵，强对角占优矩阵可约矩阵，不可约矩阵正定矩阵要清楚掌握如下概念：67第五章方程组的迭代法课件68第五章方程组的迭代法课件69定理

若线性代数方程组AX=b的系数方阵A=(aij)nn是按行(或按列)严格对角占优的，则Jacobi迭代法和Gauss-Seidel迭代法都是收敛的.定理70

对方程组通过调整方程的次序，建立收敛的Jacobi迭代格式和Gauss-Seidel迭代格式.解

将第二个方程调到第一行、第三个方程调到第二行、第一个方程调到第三行后有同解方程组对方程组71这是按行严格对角占优方程组，故Jacobi和Gauss-Seidel迭代法都一定收敛.Jacobi迭代格式为

第五章方程组的迭代法课件72Gauss-Seidel迭代格式为

第五章方程组的迭代法课件73第五章方程组的迭代法课件74定理系数矩阵是不可约矩阵且是对角占优矩阵，Jacobi迭代和Gauss-Seidel迭代都收敛。第五章方程组的迭代法课件75第五章方程组的迭代法课件76定理若线性方程组的系数矩阵是对称正定矩阵，则用Jacobi迭代法和Gauss-Seidel迭代法都是收敛的。怎么判断矩阵是对称正定矩阵，直接从定义判断不方便，我们有如下几个结论：定理77对称性很容易判定。下面是如何判断正定性。矩阵的任意特征值都大于零，则是正定矩阵；矩阵的所有顺序主子式都大于零，则是正定矩阵；对角元素为正实数and（强对角占优矩阵or不可约对角占优矩阵），是正定矩阵。对称性很容易判定。下面是如何判断正定性。78顺序主子式：位于矩阵的前k行前k列交叉位置上的元素按照原来的相对位置构成的k阶子式。顺序主子式是行列式。Question:如何编程计算所有的顺序主子式？（让学生黑板练习）顺序主子式：79SOR方法SOR方法为了解决大型稀疏矩阵收敛速度较慢，引入SOR方法。SOR方法SOR方法80回忆Gauss-Seidel迭代松弛迭代法是由Gauss-Seidel迭代演变而来，具体步骤如下：回忆Gauss-Seidel迭代松弛迭代法是由Gauss-S81第五章解线性方程组的迭代法第五章82实际问题经过简单的分析可以直接归结为线性方程组，或者微分方程，后者可以转换为线性方程组。两种方法：直接法：中小型稠密矩阵迭代法：大型稀疏矩阵实际问题经过简单的分析可以直接归结为线性方程组，或者835.1Jacobi迭代法和Gauss-Seidel迭代法设线性方程组简记AX=b5.1Jacobi迭代法和Gauss-Seidel迭代法设84其中其中85将方程组AX=b，改写成便于迭代的形式建立迭代格式向量X(0)事先给定，称为初始解向量，用公式逐步迭代求解的方法叫做迭代法.如果由产生的序列收敛，则称迭代法是收敛的，否则称为迭代法发散.将方程组AX=b，改写成便于迭代的形式86若将方程组改写为若871．Jacobi迭代法建立迭代格式其中1．Jacobi迭代法88Jacobi迭代法的矩阵表示将方程组AX=b的系数A分解成A=L+D+U其中D=diag(a11,a22,,ann)，L和U分别是A的对角线下方元素和上方元素组成的严格下三角阵与严格上三角阵.即Jacobi迭代法的矩阵表示将方程组AX=b的系数A分解成89第五章方程组的迭代法课件90迭代格式为：迭代格式为：91对应的分量表示形式为：另外一种矩阵形式是：对应的分量表示形式为：另外一种矩阵形式是：92的Jacobi迭代格式（三种）写出方程组写出方程组93第五章方程组的迭代法课件94Matlab计算过程如下：Matlab计算过程如下：95>>A=[1-22;-130;207]A=1-22-130207>>U=triu(A,1)U=0-22000000>>L=tril(A,-1)L=000-100200>>D=diag(diag(A))D=100030007>>A=[1-22;-130;207]>>U96>>-inv(D)*(L+U)ans=02.000000000000000-2.0000000000000000.33333333333333300-0.28571428571428600>>b=[5;-1;2];inv(D)*bans=5.000000000000000-0.3333333333333330.285714285714286>>-inv(D)*(L+U)>>b=[5;-1;2];97>>I=eye(3)I=100010001>>I-inv(D)*Aans=02.000000000000000-2.0000000000000000.33333333333333300-0.28571428571428600>>I=eye(3)98分量形式为:分量形式为:99Gauss-Seidel迭代法方程组改写为：即得迭代格式：Gauss-Seidel迭代法方程组改写为：即得迭代格式：100Gauss-Seidel迭代法迭代格式的分量形式：其中

Gauss-Seidel迭代法迭代格式的分量形式：101的Gauss-Seidel迭代格式（两种）写出方程组写出方程组102例

分别用Jacobi迭代法与Gauss-Seidel迭代法求解方程组精确到小数点后四位，并要求分别写出其迭代法的分量形式和矩阵形式.例分别用Jacobi迭代法与Gauss-Seidel迭代103解（1）用Jacobi迭代法，其迭代法的分量形式为解（1）用Jacobi迭代法，其迭代法的分量形式为104迭代法的矩阵形式为其中迭代法的矩阵形式为105

106取初值X(0)=(0,0,0)′，迭代可得取初值X(0)=(0,0,0)′，迭代可得107迭代7次，得近似值.（2）用Gauss-Seidel迭代法，其迭代法的分量形式为迭代7次，得近似值.108其迭代法的矩阵形式为其中其迭代法的矩阵形式为109

110

111即取初值X(0)=(0,0,0)′，迭代可得即112迭代5次，得近似值第五章方程组的迭代法课件113Question:如何判断迭代出来的值和真实根很接近？Question:114向量和矩阵的模（范数）

为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，——向量和矩阵的范数。向量和矩阵的模（范数） 为了研究线性方程组近似解的误差估计115向量和矩阵的范数

在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。向量和矩阵的范数 在一维数轴上，实轴上任意一点x到原点的距离116向量和矩阵的范数

而在二维平面上，平面上任意一点P(x,y)到原点的距离用表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用表示。推广到n维空间，则称为向量范数。向量和矩阵的范数 而在二维平面上，平面上任意一点P(x,y)117向量范数

向量范数 118常见的向量范数

常见的向量范数 119Question:如何判断迭代出的向量是真实解的精度较高的近似值？Question:120第五章方程组的迭代法课件121向量范数性质向量范数性质122第五章方程组的迭代法课件123例已知例已知124矩阵范数矩阵范数125相容范数相容范数126算子范数（了解）算子范数（了解）127算子范数（了解）算子范数（了解）128算子范数（了解）算子范数（了解）129算子范数（了解）算子范数（了解）130常见的矩阵范数列范数行范数谱范数常见的矩阵范数列范数行范数谱范数131例题例题132Matlab计算过程如下：2范数：>>norm(A)1范数：>>norm(A,1)无穷范数：>>norm(A,inf)Matlab计算过程如下：133矩阵的谱半径矩阵的谱半径134例题求特征值命令eig(A)例题求特征值命令135第五章方程组的迭代法课件136第五章方程组的迭代法课件137例解：A的特征值为：》lm=eig(A)lm=1.500000000000000+1.658312395177701i1.500000000000000-1.658312395177701i1.000000000000000例解：A的特征值为：138》norm(lm,inf)ans=2.236067977499790》norm(lm,inf)ans=139》lm1=eig(A*A')lm1=0.9360750171710592.9211249380724389.142800044756498》sqrt(9.142800044756498)ans=3.023706342348162》lm1=eig(A*A')lm1=》sqrt(9.1140迭代法的收敛性定理（迭代法的基本收敛定理）迭代过程

X(k+1)

=BX(k)

+g对于任意初始向量X(0)及右端向量g均收敛的充要条件是迭代矩阵B的谱半径(B)<1,并且(B)愈小，收敛速度愈快.

迭代法的收敛性定理（迭代法的基本收敛定理）141第五章方程组的迭代法课件142B表示B的任意一种范数定理（迭代法收敛的充分条件）若迭代法

X(k+1)

=BX(k)

+g的迭代矩阵B满足，B=q<1,则对于任意的初始向量X(0)与右端向量g迭代法收敛.B表示B的任意一种范数定理（迭代法收敛的充分条件）143第五章方程组的迭代法课件144Question:Jacobi迭代法和Gauss-Seidel迭代法如何判断收敛性？Question:1