第三章解线性方程组的迭代法.pptx
1 迭代法概述等价线性方程组取初始向量 x(0)Rn,构造如下单步定常线性迭代公式以此来产生近似向量序列 x(1),x(2),.当k充分大时，基本思想等价变形如何做收敛性条件M:迭代矩阵第1页/共50页2定义 对于Rn中的向量序列 x(k),如果则称向量序列x(k)收敛于 Rn中的向量 x.定义对于n阶方阵序列 A(k),如果则称方阵序列A(k)收敛于n阶方阵A.上面两式通常表示成 向量序列与矩阵序列的收敛概念第2页/共50页3定理 Rn中的向量序列x(k)收敛于Rn中的向量x的充分必要条件是其中xj(k)和 xj分别表示 x(k)和 x中的第 j个分量.定理 n阶方阵序列A(k)收敛于n阶方阵A的充分必要条件是 向量序列与矩阵序列收敛的充分必要条件 向量序列和矩阵序列的收敛可归结为对应分量或对应元素序列的收敛性.第3页/共50页4 若由迭代公式产生的向量序列 x(k)收敛于向量 x，则即向量 x 是 方程 Ax=b 的解.单步定常线性迭代法产生的向量序列若收敛则必收敛到原线性方程组的解.第4页/共50页5 n=4的Jacobi迭代法把方程组改写成如下等价形式第5页/共50页6 n=4的Jacobi迭代法计算公式已知 用上述迭代公式可算得 第6页/共50页7 n=4的Jacobi迭代法矩阵表示第7页/共50页8 Jacobi迭代法(k)(k)(k)(k)(k+1)第8页/共50页9从上式中分离出变量 xi,将它改写成即得到解方程组的雅可比迭代公式:Jacobi迭代法第9页/共50页10 设D为由A的对角线元素构成的对角矩阵Jacobi迭代公式 Jacobi迭代法的矩阵表示 迭代矩阵第10页/共50页11例 用Jacobi迭代法求解线性方程组解 将方程组改写成如下等价形式第11页/共50页12Jacobi迭代法计算公式为假设初始向量取 x(0)=(0,0,0)T.第一次迭代第二次迭代第12页/共50页13 实际计算时，迭代法中止条件其中 为给定的要求精度.第13页/共50页14 n=4的Gauss-Seidel迭代法把方程组改写成如下等价形式第14页/共50页15 n=4的Gauss-Seidel迭代法第15页/共50页16 Gauss-Seidel迭代法(k)(k)(k+1)(k+1)(k+1)第16页/共50页17在迭代的每一步设定计算顺序并且，在计算迭代值 充分利用它前面的新信息这样设计出来的迭代公式称为高斯塞德尔迭代公式.Gauss-Seidel迭代法第17页/共50页18 Gauss-Seidel迭代法的矩阵表示 设将系数矩阵A 分裂为其中D为对角阵,L 和U分别为严格下三角和严格上三角阵.迭代矩阵GaussSeidel迭代公式第18页/共50页19例 用Gauss-Seidel迭代法求解线性方程组解 将方程组改写成如下等价形式第19页/共50页20Gauss-Seidel迭代法计算公式为假设初始向量取 x(0)=(0,0,0)T.第一次迭代第20页/共50页21第二次迭代Gauss-Seidel迭代法计算公式为假设初始向量取 x(0)=(0,0,0)T.第21页/共50页22 Jacobi迭代法：x(k+1)分量的计算可以同时进行，无先后次序 Gauss-Seidel迭代法：x(k+1)分量的计算有先后次序，必须先计算x(k+1)前面的分量然后再计算下一分量.第22页/共50页23 Jacobi迭代法与Gauss-Seidel迭代法的计算效果哪一种更好？前例计算结果表明,用Gauss-Seidel迭代法比用Jacobi迭代法效果好.但对一般情形,有些问题Gauss-Seidel迭代法确实比Jacobi迭代法收敛得快,但也有Gauss-Seidel迭代法比Jacobi迭代法收敛得慢,甚至还有Jacobi迭代法收敛,但Gauss-Seidel迭代法发散的情形.第23页/共50页24 迭代法的收敛条件定义(谱半径)设n阶方阵A的特征值为i(i=1,2,n)，则称为矩阵A的谱半径.Ak 的特征值为故第24页/共50页25 矩阵范数和谱半径有如下关系设A的任一特征值为i,对应的特征向量为ui,则由的任意性可知结论成立.矩阵A的谱半径不超过它的任何一种由向量范数诱导出的范数，即|A|是A的特征值的上界.证故从而第25页/共50页26 设A为n阶方阵，则 由于2-范数具有上面的关系式，所以称|A|2 为谱范数.第26页/共50页27定理 设A是任意n阶方阵，由A的各次幂所组成的矩阵序列收敛于零矩阵，即的充分必要条件是第27页/共50页28定理 对任何初始向量 x(0)和右端项g，由迭代公式 x(k+1)=Mx(k)+g (k=0,1,2,)产生的向量序列x(k)收敛的充分必要条件是(M)1其中(M)是矩阵M的谱半径.迭代法收敛的充分必要条件 迭代法的收敛性只与迭代矩阵的谱半径有关,而迭代矩阵是由A演变来的,因此迭代法是否收敛只与系数矩阵A以及演变的方式有关,与常数项和初始向量的选择无关.第28页/共50页29证明 必要性.设序列x(k)收敛于 x*，则有 迭代法收敛的充分必要条件任意收敛故由于x(0)为任意n维向量,即第29页/共50页30 迭代法收敛的充分必要条件任意收敛充分性.若(M)1,则=1不是M的特征值,故方程(IM)x=g有唯一解,记为x*,即又且故对任意初始向量x(0),均有证明第30页/共50页31推论1 若迭代矩阵M满足|M|1,则下列迭代公式对任意初始向量x(0)收敛 第31页/共50页32例 解方程组讨论Jacobi迭代法与Gauss-Seidel迭代法的收敛性.解迭代法是否收敛等价于迭代矩阵的谱半径是否小于1，故先求迭代矩阵第32页/共50页33 Jacobi迭代法的迭代矩阵为其特征方程为特征值谱半径故Jacobi迭代法收敛.第33页/共50页34 Gauss-Seidel迭代法的迭代矩阵为第34页/共50页35其特征方程为特征值谱半径故Gauss-Seidel迭代法发散.第35页/共50页36 一般来说,计算矩阵的谱半径比较困难,故用迭代法收敛的充分必要条件来判断迭代法是否收敛往往不太容易,以下介绍用其他方法判别迭代法收敛的充分条件.第36页/共50页37定义(严格对角占优阵)称n 阶方阵 是严格对角占优的，如果其主对角线元素的绝对值大于同行其它元素绝对值之和：若线性方程组的系数矩阵为严格对角占优阵，则称这个线性方程组为严格对角占优方程组.第37页/共50页38 迭代法收敛的充分条件定理 若A为严格对角占优阵,则求解Ax=b 的Jacobi迭代法和Gauss-Seidel迭代法均收敛.定理 若A为对称正定阵,则求解Ax=b的Gauss-Seidel迭代法收敛.第38页/共50页39例 方程组Ax=b的系数矩阵为严格对角占优阵.故Jacobi迭代法与Gauss-Sidel迭代法均收敛.第39页/共50页40例 方程组Ax=b的系数矩阵为非对角占优阵交换两个方程的次序，得原方程组的同解方程组 它是一个严格对角占优方程组，对此方程组Jacobi迭代法和Gauss-Seidel迭代法均收敛.当所给的方程组不满足迭代法的收敛条件时,适当调整方程组中方程的次序,有时可得到满足迭代法收敛条件的同解方程组.第40页/共50页41例 方程组Ax=b的系数矩阵为但A为对称正定矩阵，Gauss-Seidel迭代法收敛.非严格对角占优第41页/共50页42例 设有方程组Ax=b,其中讨论用两种迭代法求解的收敛性.解 A是对称正定阵故Gauss-Seidel迭代法收敛.A不是严格对角占优阵第42页/共50页43Jacobi迭代法的迭代矩阵为其特征方程为特征值为故迭代矩阵的谱半径为 由迭代法收敛的充分必要条件知Jacobi迭代法发散.第43页/共50页44 误差估计定理 设由迭代格式 x(k+1)=M x(k)+g,若|M|1,则 x(k)收敛于 x*,且有误差估计式第44页/共50页45证明由以上两式得故第45页/共50页46证明第46页/共50页47由此可知，为使 只要实际计算时，当|M|不太接近1时，可用作为停机准则,x(k)即为满足精度要求之近似解.停机准则第47页/共50页48 根据事先给定的精度，可以估算出迭代的次数k第48页/共50页49上机作业第89页第1题(1)(2).第49页/共50页50感谢您的观看！第50页/共50页
