线性方程组迭代解法公开课一等奖优质课大赛微课获奖课件.pptx

第四章线性方程组迭代解法第1页第1页返回前进第四章目录1 向量序列与矩阵序列极限向量序列与矩阵序列极限2 Jacobi迭代法迭代法3 GaussSeidel迭代法迭代法4 松驰法松驰法5 迭代法收敛条件及误差预计迭代法收敛条件及误差预计 5.1 矩阵谱半径矩阵谱半径 5.2 迭代法收敛条件迭代法收敛条件 5.3 误差预计误差预计第2页第2页返回前进第四章 方程组迭代解法概述 这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法迭代法，由于迭代法，由于迭代法，由于迭代法，由于迭代法能充足避免系数矩阵中零元存贮与计算，因此尤其迭代法能充足避免系数矩阵中零元存贮与计算，因此尤其迭代法能充足避免系数矩阵中零元存贮与计算，因此尤其迭代法能充足避免系数矩阵中零元存贮与计算，因此尤其适合用于求解系数矩阵阶数很高而零元素又诸多（即大型稀疏）适合用于求解系数矩阵阶数很高而零元素又诸多（即大型稀疏）适合用于求解系数矩阵阶数很高而零元素又诸多（即大型稀疏）适合用于求解系数矩阵阶数很高而零元素又诸多（即大型稀疏）线性方程组。线性方程组。线性方程组。线性方程组。解线性方程组迭代法基本思想与解方程迭代法相解线性方程组迭代法基本思想与解方程迭代法相解线性方程组迭代法基本思想与解方程迭代法相解线性方程组迭代法基本思想与解方程迭代法相似，首先将方程组似，首先将方程组似，首先将方程组似，首先将方程组AxAx=b b化为等价方程组化为等价方程组化为等价方程组化为等价方程组x x=MxMx+g g，其中，其中，其中，其中MM为为为为n n阶方阵，阶方阵，阶方阵，阶方阵，b b=(=(b b1 1,b b2 2,b bn n)T T，g g R Rn n，任取初始向量，任取初始向量，任取初始向量，任取初始向量x x(0)(0)R Rn n，代入迭代公式：代入迭代公式：代入迭代公式：代入迭代公式：产生向量序列产生向量序列产生向量序列产生向量序列 x x(k k)，若此序列收敛于，若此序列收敛于，若此序列收敛于，若此序列收敛于x x*，则有，则有，则有，则有x x*=*=MxMx*+g+g，即，即，即，即x x*为原方程组解。因此，可依据精度要求选择一个适当为原方程组解。因此，可依据精度要求选择一个适当为原方程组解。因此，可依据精度要求选择一个适当为原方程组解。因此，可依据精度要求选择一个适当x x(k k)（k k充足大时）作为近似解，这就是解线性方程组迭代法，充足大时）作为近似解，这就是解线性方程组迭代法，充足大时）作为近似解，这就是解线性方程组迭代法，充足大时）作为近似解，这就是解线性方程组迭代法，上式称为迭代格式，上式称为迭代格式，上式称为迭代格式，上式称为迭代格式，MM称为迭代矩阵，若序列称为迭代矩阵，若序列称为迭代矩阵，若序列称为迭代矩阵，若序列 x x(k k)极限存极限存极限存极限存在，称此迭代过程收敛，不然称为发散。在，称此迭代过程收敛，不然称为发散。在，称此迭代过程收敛，不然称为发散。在，称此迭代过程收敛，不然称为发散。第3页第3页返回前进1 向量与矩阵范数 与求解方程类似，需要讨论问题是：如何建与求解方程类似，需要讨论问题是：如何建与求解方程类似，需要讨论问题是：如何建与求解方程类似，需要讨论问题是：如何建立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量序列序列序列序列 x x(k k)收敛，如何进行误差预计？收敛，如何进行误差预计？收敛，如何进行误差预计？收敛，如何进行误差预计？第4页第4页返回前进4.1 向量与矩阵范数 这三个性质刻画了向量长度基本特性，并能够用其将平面这三个性质刻画了向量长度基本特性，并能够用其将平面这三个性质刻画了向量长度基本特性，并能够用其将平面这三个性质刻画了向量长度基本特性，并能够用其将平面向量长度概念推广到普通向量长度概念推广到普通向量长度概念推广到普通向量长度概念推广到普通n n维向量，于是有下列定义：维向量，于是有下列定义：维向量，于是有下列定义：维向量，于是有下列定义：定义定义定义定义1 1下屏将给出范数种类：下屏将给出范数种类：下屏将给出范数种类：下屏将给出范数种类：第5页第5页返回前进惯用向量范数 容易证实它们都满足上述三条性质。能够看出，2范数是平面向量长度计算公式在形式上推广，也是线性代数中内积定义。此处引入各种范数来刻画向量大小，是为了在不同情况下用不同范数研究问题。向量范数证实：（只对第三条）对对对对 范数：前面范数：前面范数：前面范数：前面2 2条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数条显然，对第三条，由于对任意实数x x,y y，绝对值不等式：，绝对值不等式：，绝对值不等式：，绝对值不等式：|x x+y|y|x|+|y|x|+|y|成立，因而有成立，因而有成立，因而有成立，因而有:分别称为向量分别称为向量x2范数，范数，1范数，无穷范数。范数，无穷范数。第6页第6页返回前进对2范数利用实数柯西不等式利用实数柯西不等式：于是，有：于是，有：惯用向量范数（续）惯用向量范数（续）第7页第7页返回前进Rn中范数等价性 比如可证实下列等价性：比如可证实下列等价性：比如可证实下列等价性：比如可证实下列等价性：因此，因此，因此，因此，2 2范范范范数与数与数与数与 范数范数范数范数是等价。是等价。是等价。是等价。不难证实：不难证实：不难证实：不难证实：亦即亦即1范数与范数与 范数是等价范数是等价。事实上事实上事实上事实上:Rn 中任意中任意两种范数两种范数都是等价都是等价。第8页第8页返回前进矩阵范数 定义定义2对任意对任意对任意对任意n n阶方阵阶方阵阶方阵阶方阵A A=(=(a aij ij)n n n n，若相应一个非负实，若相应一个非负实，若相应一个非负实，若相应一个非负实数数数数|A A|，满足：，满足：，满足：，满足：则称则称|A|为矩阵为矩阵A范数。范数。与向量范数定义比较，前三条性质只是向量范与向量范数定义比较，前三条性质只是向量范数定义推广，而第四条性质则是矩阵乘法性质数定义推广，而第四条性质则是矩阵乘法性质要求，它使矩阵范数在数值计算中使用更以便。要求，它使矩阵范数在数值计算中使用更以便。第9页第9页返回前进惯用矩阵范数惯用矩阵范数有：惯用矩阵范数有：惯用矩阵范数有：惯用矩阵范数有：它们分别叫做矩阵它们分别叫做矩阵它们分别叫做矩阵它们分别叫做矩阵 范数，范数，范数，范数，1 1范数，范数，范数，范数，2 2范数，范数，范数，范数，F F范数，范数，范数，范数，矩阵矩阵矩阵矩阵F F范数是向量范数是向量范数是向量范数是向量2 2范数推广，矩阵范数推广，矩阵范数推广，矩阵范数推广，矩阵 范数，范数，范数，范数，1 1范数计算范数计算范数计算范数计算容易，而矩阵容易，而矩阵容易，而矩阵容易，而矩阵2 2范数与范数与范数与范数与A AT TA A特性值相关，因此又称为谱特性值相关，因此又称为谱特性值相关，因此又称为谱特性值相关，因此又称为谱范数，它计算较困难，但由于它有一些好性质，所范数，它计算较困难，但由于它有一些好性质，所范数，它计算较困难，但由于它有一些好性质，所范数，它计算较困难，但由于它有一些好性质，所以也是惯用范数。以也是惯用范数。以也是惯用范数。以也是惯用范数。第10页第10页返回前进惯用矩阵范数（续）能够证实，这些范数都满足定义能够证实，这些范数都满足定义2。以以以以|A A|为例，前为例，前为例，前为例，前2 2条性质显然成立，而对：条性质显然成立，而对：条性质显然成立，而对：条性质显然成立，而对：第11页第11页返回前进最大行和矩阵范数证实第12页第12页返回前进最大行和矩阵范数证实第13页第13页返回前进范数相容性 在误差预计中，由于矩阵与向量会同时用到，我们总在误差预计中，由于矩阵与向量会同时用到，我们总在误差预计中，由于矩阵与向量会同时用到，我们总在误差预计中，由于矩阵与向量会同时用到，我们总希望有上面不等式成立，希望有上面不等式成立，希望有上面不等式成立，希望有上面不等式成立，但对任意向量范数与矩阵范数但对任意向量范数与矩阵范数但对任意向量范数与矩阵范数但对任意向量范数与矩阵范数却未必如此，因而尤其地把满足此不等式范数称为相容，却未必如此，因而尤其地把满足此不等式范数称为相容，却未必如此，因而尤其地把满足此不等式范数称为相容，却未必如此，因而尤其地把满足此不等式范数称为相容，能够证实，上述惯用范数是相容，即有：能够证实，上述惯用范数是相容，即有：能够证实，上述惯用范数是相容，即有：能够证实，上述惯用范数是相容，即有：在使用范数时，应选取相容矩阵范数与向量范数。在使用范数时，应选取相容矩阵范数与向量范数。在使用范数时，应选取相容矩阵范数与向量范数。在使用范数时，应选取相容矩阵范数与向量范数。分别称为分别称为分别称为分别称为 关于关于关于关于P P范数范数范数范数绝对误差与相对误差。绝对误差与相对误差。绝对误差与相对误差。绝对误差与相对误差。有了矩阵范数，就能够用它描述矩阵误差，设有了矩阵范数，就能够用它描述矩阵误差，设有了矩阵范数，就能够用它描述矩阵误差，设有了矩阵范数，就能够用它描述矩阵误差，设 是是是是A A近似近似近似近似矩阵，矩阵，矩阵，矩阵，称为称为称为称为 残差阵残差阵，则：，则：，则：，则：第14页第14页返回前进求范数举例例例10第15页第15页返回前进 向量序列与矩阵序列极限 与求解方程类似，需要讨论问题是：如何建与求解方程类似，需要讨论问题是：如何建与求解方程类似，需要讨论问题是：如何建与求解方程类似，需要讨论问题是：如何建立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量序列序列序列序列 x x(k k)收敛，如何进行误差预计？收敛，如何进行误差预计？收敛，如何进行误差预计？收敛，如何进行误差预计？1 向量序列与矩阵序列极限向量序列与矩阵序列极限 由于由于由于由于R Rn n中向量可与中向量可与中向量可与中向量可与R Rn n点建立一一相应关系，点建立一一相应关系，点建立一一相应关系，点建立一一相应关系，因此由点列收敛概念及向量范数等价性，可得因此由点列收敛概念及向量范数等价性，可得因此由点列收敛概念及向量范数等价性，可得因此由点列收敛概念及向量范数等价性，可得到向量序列收敛概念。到向量序列收敛概念。到向量序列收敛概念。到向量序列收敛概念。定义定义定义定义3 3第16页第16页返回前进 向量序列与矩阵序列极限（续）n n维点列收敛一个等价描述是其相应坐标序列均维点列收敛一个等价描述是其相应坐标序列均维点列收敛一个等价描述是其相应坐标序列均维点列收敛一个等价描述是其相应坐标序列均收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。定理定理定理定理1 1 第17页第17页返回前进矩阵序列收敛概念及定理定义定义定义定义3 3完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵序列收敛：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：定理定理定理定理2 2 第18页第18页返回前进4.3 矩阵谱半径矩阵谱半径 迭代法收敛性与迭代矩阵特性值相关：迭代法收敛性与迭代矩阵特性值相关：迭代法收敛性与迭代矩阵特性值相关：迭代法收敛性与迭代矩阵特性值相关：设设设设A A为为为为n n阶方阵，阶方阵，阶方阵，阶方阵，i i(i i=1,2,=1,2,，n n)为为为为A A特性值，特性值，特性值，特性值，称特性值模最大值为矩阵称特性值模最大值为矩阵称特性值模最大值为矩阵称特性值模最大值为矩阵A A谱半径，记为：谱半径，记为：谱半径，记为：谱半径，记为：定义定义定义定义5 5第19页第19页返回前进矩阵谱半径（续）矩阵谱半径与范数之间有下列关系：矩阵谱半径与范数之间有下列关系：矩阵谱半径与范数之间有下列关系：矩阵谱半径与范数之间有下列关系：设设设设x x为相应于特性值为相应于特性值为相应于特性值为相应于特性值 A A特性向量，则由：特性向量，则由：特性向量，则由：特性向量，则由：这个不等式对这个不等式对这个不等式对这个不等式对A A任何范数、任意特性值都成立，任何范数、任意特性值都成立，任何范数、任意特性值都成立，任何范数、任意特性值都成立，因此，可得矩阵因此，可得矩阵因此，可得矩阵因此，可得矩阵A A谱半径与谱半径与谱半径与谱半径与A A范数之间一个主要范数之间一个主要范数之间一个主要范数之间一个主要关系：关系：关系：关系：A A谱半径不超出谱半径不超出谱半径不超出谱半径不超出A A任一个范数。即：任一个范数。即：任一个范数。即：任一个范数。即：第20页第20页返回前进公式 主要性阐明 它之因此主要是由于：它之因此主要是由于：它之因此主要是由于：它之因此主要是由于：(A A)难计算，而难计算，而难计算，而难计算，而|A A|、|A A|1 1计算容易，并且对于任意正数计算容易，并且对于任意正数计算容易，并且对于任意正数计算容易，并且对于任意正数 ，存在一个矩阵范数，存在一个矩阵范数，存在一个矩阵范数，存在一个矩阵范数很靠近很靠近很靠近很靠近 (A A)，使得成立：，使得成立：，使得成立：，使得成立：对任意对任意对任意对任意n n阶方阵阶方阵阶方阵阶方阵A A，普通不存在矩阵范数使，普通不存在矩阵范数使，普通不存在矩阵范数使，普通不存在矩阵范数使 (A A)=|)=|A|A|，但若，但若，但若，但若A A为对称矩阵，则有：为对称矩阵，则有：为对称矩阵，则有：为对称矩阵，则有：下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要 ：定理定理定理定理3 3第21页第21页返回前进定理3（续）证实：证实：证实：证实：第22页第22页返回前进由由由由5.1 5.1 结果，能够得到下列收敛定理结果，能够得到下列收敛定理结果，能够得到下列收敛定理结果，能够得到下列收敛定理 ：定理定理定理定理4 4对任意初始向量对任意初始向量对任意初始向量对任意初始向量x x(0)(0)和右端项和右端项和右端项和右端项g g，由迭代格式：，由迭代格式：，由迭代格式：，由迭代格式：证实：证实：证实：证实：第23页第23页返回前进推论推论推论推论1 1第24页第24页返回前进 能够看出，后两个方程组与第一个方程组相能够看出，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有比，系数矩阵或右端向量仅有0.0005下列误差，下列误差，但准确解却相差很大。但准确解却相差很大。4.2 方程组误差分析 数值稳定算法是否一定能求得精度比较高数值稳定算法是否一定能求得精度比较高解呢？回答是不一定，解精度还与方程组本解呢？回答是不一定，解精度还与方程组本身性态相关，下面来考察几种例：身性态相关，下面来考察几种例：例例11第25页第25页返回前进例例12若其系数，常数项改用三位有效数字小数表示，若其系数，常数项改用三位有效数字小数表示，则方程组为则方程组为：第26页第26页返回前进右端项右端项b产生产生0.1%改变改变引起解改变引起解改变最大改变最大改变184%。初始数据误差（相对）初始数据误差（相对）0.3%=0.003，而解相对误差却超出而解相对误差却超出50%。例例13第27页第27页返回前进方程组性态讨论 病态、良态 在许多实际问题中，线性方程组系数矩阵和在许多实际问题中，线性方程组系数矩阵和右端项元素大多为前面计算结果，因此上述右端项元素大多为前面计算结果，因此上述例中微小误差是避免不了。而对上述例中方例中微小误差是避免不了。而对上述例中方程组，无论用多么稳定算法求解，计算中产生程组，无论用多么稳定算法求解，计算中产生微小误差就使解面目全非，因此这些方程组微小误差就使解面目全非，因此这些方程组性态是很差。性态是很差。当方程组当方程组Ax=b系数矩阵与右端向量系数矩阵与右端向量b微微小变动（小扰动）而引起解严重失真时，称此方小变动（小扰动）而引起解严重失真时，称此方程组为病态方程组，其系数矩阵程组为病态方程组，其系数矩阵A称为病态矩阵，称为病态矩阵，不然称为良态方程组，不然称为良态方程组，A称为良态矩阵，为了定量称为良态矩阵，为了定量刻画方程组刻画方程组“病态病态”程度，下面对方程组程度，下面对方程组Ax=b在在系数矩阵系数矩阵A及右端项及右端项b有扰动几种情形进行讨论。有扰动几种情形进行讨论。第28页第28页返回前进 此不等式表明，当右端项有扰动时，解相对误差不超此不等式表明，当右端项有扰动时，解相对误差不超此不等式表明，当右端项有扰动时，解相对误差不超此不等式表明，当右端项有扰动时，解相对误差不超出出出出b b相对误差相对误差相对误差相对误差 倍。倍。倍。倍。首先考察右端项首先考察右端项b扰动对解影响，设扰动对解影响，设b有扰有扰动动 b，A为准确为准确,记引起解记引起解x扰动为扰动为 x,即：即：第29页第29页返回前进方程组性态讨论（续2）当当b为准确而为准确而A有微小扰动有微小扰动 A时，在时，在 A充足小时充足小时也同样可推得：也同样可推得：紧接下屏讨论：紧接下屏讨论：第30页第30页返回前进第31页第31页返回前进方程组性态讨论续（3）而当而当而当而当A A,b b同时有微小扰动同时有微小扰动同时有微小扰动同时有微小扰动 A A，b b时，则可进一步导出更时，则可进一步导出更时，则可进一步导出更时，则可进一步导出更普通误差预计式：普通误差预计式：普通误差预计式：普通误差预计式：注意到：注意到：第32页第32页返回前进在在 b充足小时，充足小时，此式右端事实上此式右端事实上即为：即为：方程组性态讨论续（4）第33页第33页返回前进矩阵条件数 在三种情况下得到这三个不等式反应理解相对误在三种情况下得到这三个不等式反应理解相对误在三种情况下得到这三个不等式反应理解相对误在三种情况下得到这三个不等式反应理解相对误差与差与差与差与A A及及及及b b相对误差关系；数相对误差关系；数相对误差关系；数相对误差关系；数|A|AA|A-1-1|越小，解相对越小，解相对越小，解相对越小，解相对误差也越小；反之数误差也越小；反之数误差也越小；反之数误差也越小；反之数|A|AA|A-1-1|越大，解相对误差也越大，越大，解相对误差也越大，越大，解相对误差也越大，越大，解相对误差也越大，事实上这个数反应理解对方程组原始数据敏感程度，揭示事实上这个数反应理解对方程组原始数据敏感程度，揭示事实上这个数反应理解对方程组原始数据敏感程度，揭示事实上这个数反应理解对方程组原始数据敏感程度，揭示了矩阵了矩阵了矩阵了矩阵A A和方程组本身性态，称之为方程组或矩阵和方程组本身性态，称之为方程组或矩阵和方程组本身性态，称之为方程组或矩阵和方程组本身性态，称之为方程组或矩阵A A条件条件数数，记作：，记作：，记作：，记作：condcond(A A)越大，越大，越大，越大，A A病态程度越严重。至于病态程度越严重。至于病态程度越严重。至于病态程度越严重。至于condcond(A A)多大才多大才多大才多大才算病态，这是一个相对概念，没有一个严格数量界线。算病态，这是一个相对概念，没有一个严格数量界线。算病态，这是一个相对概念，没有一个严格数量界线。算病态，这是一个相对概念，没有一个严格数量界线。第34页第34页返回前进判断病态矩阵几点参考 求条件数要计算逆阵范数，很不以便，下列一求条件数要计算逆阵范数，很不以便，下列一些现象可作为判断病态矩阵参考。些现象可作为判断病态矩阵参考。（1 1）在用主元消去法时消元过程出现小主元（如例）在用主元消去法时消元过程出现小主元（如例）在用主元消去法时消元过程出现小主元（如例）在用主元消去法时消元过程出现小主元（如例1212）（2 2）矩阵）矩阵）矩阵）矩阵A A中元素间数量级相差很大；中元素间数量级相差很大；中元素间数量级相差很大；中元素间数量级相差很大；（3 3）A A行列式行列式行列式行列式det(det(A A)满足（行列式值相对很大）满足（行列式值相对很大）满足（行列式值相对很大）满足（行列式值相对很大）：（4 4）矩阵一些行（或列）近似相关（如例）矩阵一些行（或列）近似相关（如例）矩阵一些行（或列）近似相关（如例）矩阵一些行（或列）近似相关（如例1111）。）。）。）。第35页第35页返回前进利用条件数判断矩阵性态举例A A条件数很大，因此方程组是病态。条件数很大，因此方程组是病态。条件数很大，因此方程组是病态。条件数很大，因此方程组是病态。特例，它是典型特例，它是典型特例，它是典型特例，它是典型“病态病态病态病态”阵，阵，阵，阵，n n越大，越大，越大，越大，“病态病态病态病态”越严重，越严重，越严重，越严重，如如如如n n=6=6时，时，时，时，condcond(A A)=2910)=29106 6，对严重，对严重，对严重，对严重“病态病态病态病态”方程组，即方程组，即方程组，即方程组，即使用主元素法求解也难以确保数值稳定性。使用主元素法求解也难以确保数值稳定性。使用主元素法求解也难以确保数值稳定性。使用主元素法求解也难以确保数值稳定性。第36页第36页返回前进3 雅可比（Jacobi）迭代法 设有设有设有设有n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：简记为：简记为：简记为：简记为：其系数矩阵其系数矩阵其系数矩阵其系数矩阵A A非奇异，不妨设非奇异，不妨设非奇异，不妨设非奇异，不妨设a aii ii 0(1,2,0(1,2,n n)可将上式可将上式可将上式可将上式改写为等价方程组：改写为等价方程组：改写为等价方程组：改写为等价方程组：第37页第37页返回前进雅可比（Jacobi）迭代法（续）也可写作为：也可写作为：也可写作为：也可写作为：可简记为：可简记为：可简记为：可简记为：由此可建立迭代格式：由此可建立迭代格式：由此可建立迭代格式：由此可建立迭代格式：第38页第38页返回前进Jacobi迭代法定义 选取初始向量选取初始向量选取初始向量选取初始向量x x(0)(0)代入（代入（代入（代入（4-44-4）右端，可得）右端，可得）右端，可得）右端，可得x x(1)(1)=BxBx(0)(0)+g g，再将再将再将再将x x(1)(1)代入（代入（代入（代入（3-43-4）右端，可得）右端，可得）右端，可得）右端，可得x x(2)(2)=BxBx(1)(1)+g g，如此继续下去，如此继续下去，如此继续下去，如此继续下去，就产生一个向量序列就产生一个向量序列就产生一个向量序列就产生一个向量序列 x x(k k)，按（，按（，按（，按（3-23-2）或（）或（）或（）或（3-33-3）格式迭代求解）格式迭代求解）格式迭代求解）格式迭代求解办法称为办法称为办法称为办法称为雅可比（雅可比（雅可比（雅可比（JacobiJacobiJacobiJacobi）迭代法）迭代法）迭代法）迭代法，又叫，又叫，又叫，又叫简朴迭代法简朴迭代法简朴迭代法简朴迭代法。迭代式（迭代式（迭代式（迭代式（3-43-4）中）中）中）中B B 称为迭代矩阵，它可直接由（称为迭代矩阵，它可直接由（称为迭代矩阵，它可直接由（称为迭代矩阵，它可直接由（3-23-2）或（或（或（或（3-33-3）得到，也可用系数矩阵）得到，也可用系数矩阵）得到，也可用系数矩阵）得到，也可用系数矩阵A A来表示：来表示：来表示：来表示：若将系数矩阵若将系数矩阵若将系数矩阵若将系数矩阵A A分解为分解为分解为分解为A A=D D L L U U，其中：其中：其中：其中：第39页第39页返回前进Jacobi迭代法定义（续）式（式（式（式（3-53-5）为简朴迭代法矩阵形式）为简朴迭代法矩阵形式）为简朴迭代法矩阵形式）为简朴迭代法矩阵形式。第40页第40页返回前进Jacobi迭代法举例用用用用JacobiJacobi迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：例例例例1 1解解解解：由第一个方程解：由第一个方程解：由第一个方程解：由第一个方程解x x1 1，第二个方程解，第二个方程解，第二个方程解，第二个方程解x x2 2，第三，第三，第三，第三个方程解个方程解个方程解个方程解x x3 3得得得得JoacbiJoacbi迭代格式为：迭代格式为：迭代格式为：迭代格式为：继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表3-13-1：取取取取x x(0)(0)=(0,0,0)=(0,0,0)T T代入迭代式代入迭代式代入迭代式代入迭代式（3-63-6）或（）或（）或（）或（3-73-7）得：）得：）得：）得：第41页第41页返回前进Jacobi迭代法举例 0 00.00000.00000.00000.00000.00000.00001 17.7.8.30008.30008.40008.40002 29.71009.710010.700010.700011.500011.50003 310.570010.570011.570011.570012.482012.48204 410.853510.853511.853411.853412.828212.82825 510.951010.951011.951011.951012.941412.94146 610.983410.983411.983411.983412.950412.95047 710.994410.994411.998111.998112.993412.99348 810.998110.998111.994111.994112.997812.99789 910.999410.999411.999411.999412.999212.9992表表表表3-13-1k k x x1 1(k k)x x2 2(k k)x x3 3(k k)迭代迭代迭代迭代9 9次，得近似解次，得近似解次，得近似解次，得近似解x x(9)(9)=(10.9994,11.9994,12,9992)=(10.9994,11.9994,12,9992)T T，此方，此方，此方，此方程组准确解为程组准确解为程组准确解为程组准确解为x x=(11,12,13)=(11,12,13)T T，从表，从表，从表，从表3-13-1能够看出，伴随迭能够看出，伴随迭能够看出，伴随迭能够看出，伴随迭代次数增长，迭代结果越来越靠近准确解。代次数增长，迭代结果越来越靠近准确解。代次数增长，迭代结果越来越靠近准确解。代次数增长，迭代结果越来越靠近准确解。第42页第42页返回前进 收敛条件收敛条件 迭代格式收敛充要条件是G谱半径1。对于Jacobi迭代，我们有一些确保收敛充足条件定理：若A满足下列条件之一，则Jacobi迭代收敛。A为行对角占优阵 A为列对角占优阵第43页第43页返回前进证实：证毕第44页第44页返回前进例例例例4 4 讨论讨论讨论讨论JacobiJacobi迭代法收敛性。迭代法收敛性。迭代法收敛性。迭代法收敛性。解：首先要求出迭代矩阵，解：首先要求出迭代矩阵，解：首先要求出迭代矩阵，解：首先要求出迭代矩阵，对对对对JacobiJacobi迭代法：迭代法：迭代法：迭代法：第45页第45页返回前进第46页第46页返回前进3 高斯塞德尔(Gauss-Seidel)迭代法 JacobiJacobi迭代法长处是公式简朴，迭代矩阵容易得到，迭代法长处是公式简朴，迭代矩阵容易得到，迭代法长处是公式简朴，迭代矩阵容易得到，迭代法长处是公式简朴，迭代矩阵容易得到，它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算x x(k k+1)+1)时是用时是用时是用时是用x x(k k)所有分量代入求所有分量代入求所有分量代入求所有分量代入求x x (k+1)(k+1)所有分量。因此所有分量。因此所有分量。因此所有分量。因此需同时保留两个近似解向量需同时保留两个近似解向量需同时保留两个近似解向量需同时保留两个近似解向量x x(k k)和和和和x x(k k+1)+1)。第47页第47页返回前进第48页第48页返回前进Gauss-Seidel迭代法求解 例例2 用用用用Gauss-SeidelGauss-Seidel迭代法求解例迭代法求解例迭代法求解例迭代法求解例1 1 解：解：解：解：Gauss-SeidelGauss-Seidel迭代格式为：迭代格式为：迭代格式为：迭代格式为：仍取仍取仍取仍取x x (0)(0)=(0,0,0)=(0,0,0)T T，计算结果见下表：计算结果见下表：计算结果见下表：计算结果见下表：0 00.00000.00000.00000.00000.00000.00001 17.7.9.02009.020011.644011.64402 210.430810.430811.671911.671912.820512.82053 310.931310.931311.957211.957212.977812.97784 410.991310.991311.994711.994712.997212.99725 510.998910.998911.999311.999312.999612.99966 610.999910.999911.999911.999913.000013.0000k xk x1 1(k k)x x2 2(k k)x x3 3(k k)表表表表3-23-2 显然，用显然，用显然，用显然，用Gauss-SeidelGauss-Seidel迭代法比迭代法比迭代法比迭代法比JacobiJacobi迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论在多数情况下是成立，但也有在多数情况下是成立，但也有在多数情况下是成立，但也有在多数情况下是成立，但也有Gauss-SeidelGauss-Seidel迭代比迭代比迭代比迭代比JacuobiJacuobi迭代收迭代收迭代收迭代收敛慢，甚至尚有敛慢，甚至尚有敛慢，甚至尚有敛慢，甚至尚有JacobiJacobi迭代收敛，迭代收敛，迭代收敛，迭代收敛，Gauss-SeidelGauss-Seidel迭代发散情形。迭代发散情形。迭代发散情形。迭代发散情形。第49页第49页返回前进求例2中Gauss-Seidel法迭代阵M两种办法第50页第50页返回前进求例2中Gauss-Seidel法迭代阵M两种办法续1办法办法2：可按代入法求可按代入法求可按代入法求可按代入法求MM，以避免计算逆矩阵，在，以避免计算逆矩阵，在，以避免计算逆矩阵，在，以避免计算逆矩阵，在Gauss-Gauss-SeidelSeidel迭代式（迭代式（迭代式（迭代式（3-103-10）中，第）中，第）中，第）中，第 二个式子中以第一个式子二个式子中以第一个式子二个式子中以第一个式子二个式子中以第一个式子代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为k k（能够无论常数）：（能够无论常数）：（能够无论常数）：（能够无论常数）：第51页第51页返回前进求例2中Gauss-Seidel法迭代阵M两种办法续2由于（由于（由于（由于（3-103-10）第一式及（）第一式及（）第一式及（）第一式及（3-113-11），），），），（3-123-12）右端上标均为）右端上标均为）右端上标均为）右端上标均为k k，即，即，即，即为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类似于JacobiJacobi迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得迭代阵为：迭代阵为：迭代阵为：迭代阵为：第52页第52页返回前进 收敛条件收敛条件 迭代格式收敛充要条件是G谱半径1。我们看一些充足条件定理：若A满足下列条件之一，则Gauss-Seidel 迭代收敛。A为行或列对角占优阵 A对称正定阵第53页第53页返回前进证实：设G特性多项式为，则为对角占优阵，则时为对角占优阵即即证毕注：注：注：注：二种办法都存在二种办法都存在收敛性问题收敛性问题。有例子表明：有例子表明：Gauss-Seidel法收敛时，法收敛时，Jacobi法也许法也许不收敛；而不收敛；而Jacobi法收敛时，法收敛时，Gauss-Seidel法也也许法也也许不收敛。不收敛。第54页第54页返回前进两种迭代法举例例例例例4 4 讨论讨论讨论讨论JacobiJacobi迭代法与迭代法与迭代法与迭代法与Gauss-SeidelGauss-Seidel迭代法收敛性。迭代法收敛性。迭代法收敛性。迭代法收敛性。解：首先要求出迭代矩阵，然后利用推论解：首先要求出迭代矩阵，然后利用推论解：首先要求出迭代矩阵，然后利用推论解：首先要求出迭代矩阵，然后利用推论1 1（充足条（充足条（充足条（充足条件）及定理件）及定理件）及定理件）及定理4 4（充足必要条件）进行讨论。（充足必要条件）进行讨论。（充足必要条件）进行讨论。（充足必要条件）进行讨论。对对对对JacobiJacobi迭代法：迭代法：迭代法：迭代法：第55页第55页返回前进例4（Jacobi迭代法续）第56页第56页返回前进例4（G-S迭代法续）对对对对G-SG-S迭代法：迭代法：迭代法：迭代法：第57页第57页返回前进两种迭代法阐明注注1：对：对：对：对G-SG-S法，为避免求逆阵可按下面两个办法：法，为避免求逆阵可按下面两个办法：法，为避免求逆阵可按下面两个办法：法，为避免求逆阵可按下面两个办法：第58页第58页返回前进两种迭代法阐明（续）第59页第59页返回前进4 松驰法 通过引入参数，在通过引入参数，在通过引入参数，在通过引入参数，在Gauss-SeidelGauss-Seidel法基础上作适当修改，法基础上作适当修改，法基础上作适当修改，法基础上作适当修改，在不增长过多计算量条件下，可得到一个新，收敛在不增长过多计算量条件下，可得到一个新，收敛在不增长过多计算量条件下，可得到一个新，收敛在不增长过多计算量条件下，可得到一个新，收敛更快迭代法。更快迭代法。更快迭代法。更快迭代法。将将将将Gauss-SeidelGauss-Seidel迭代格式（迭代格式（迭代格式（迭代格式（3-93-9）改写为：）改写为：）改写为：）改写为：第60页第60页返回前进松驰法（续）通过选择适当参数通过选择适当参数 使此迭代格式收敛更快。使此迭代格式收敛更快。称为称为松驰因子松驰因子，1时称时称为为超松驰法超松驰法，=1是是Gauss-Seidel迭代迭代，简称为，简称为SOR法法（Successive Over-Relaxation）。）。第61页第61页返回前进将（将（将（将（3-133-13）代入（）代入（）代入（）代入（3-143-14）可得：）可得：）可得：）可得：其矩阵其矩阵其矩阵其矩阵形式为：形式为：形式为：形式为：因此因此因此因此SORSOR法迭代矩阵为：法迭代矩阵为：法迭代矩阵为：法迭代矩阵为：第62页第62页返回前进用SOR法解线性方程组（例3）例例3 取取取取 =1.4,=1.4,x x (0)(0)=(1,1,1)=(1,1,1)T T，用用用用SORSOR法解线性方程组法解线性方程组法解线性方程组法解线性方程