基本迭代方法优秀PPT.ppt
基本迭代方法第1页，本讲稿共12页第五章第五章 线性方程组的迭代解法线性方程组的迭代解法教学目的教学目的 1.掌握掌握Jacobi迭代法，迭代法，G-S迭代法解大型线性方程组的方法及其收迭代法解大型线性方程组的方法及其收敛性的判别方法；敛性的判别方法；2.掌握掌握SOR迭代法及收敛的必要条件迭代法及收敛的必要条件(02)；3.了解三种迭代法之间的改进关系从而掌握该思想方法；了解三种迭代法之间的改进关系从而掌握该思想方法；4.理解迭代法基本定理。理解迭代法基本定理。教学重点及难点教学重点及难点 重点是重点是三种迭代法及收敛性的判别方法；三种迭代法及收敛性的判别方法；难点是难点是迭代法基本定理及三种迭代法收敛定理的证明。迭代法基本定理及三种迭代法收敛定理的证明。第2页，本讲稿共12页第第5章章 线性方程组的迭代解法线性方程组的迭代解法 首先看一个形成大型方程组的例子。考虑下面的首先看一个形成大型方程组的例子。考虑下面的Poisson方程方程的离散逼近，其边界条件为：的离散逼近，其边界条件为：取取 进行网格剖分进行网格剖分,用二阶导数用二阶导数,按逐行自左至右和自下而按逐行自左至右和自下而上的自然次序离散华可得下列线性方程组上的自然次序离散华可得下列线性方程组第3页，本讲稿共12页其中是的近似值。这是一其中是的近似值。这是一种特殊形状的稀疏矩阵。随着和的减少，所得到的方程组的阶种特殊形状的稀疏矩阵。随着和的减少，所得到的方程组的阶数将增大。数将增大。对于大型线形代数方程组，常用迭代解法。它是从某些初始向量出对于大型线形代数方程组，常用迭代解法。它是从某些初始向量出第4页，本讲稿共12页发，用设计好的步骤逐次算出近似解向量，从而得到向量序发，用设计好的步骤逐次算出近似解向量，从而得到向量序 列列 。一般的计算公式是一般的计算公式是称之为称之为多步迭代法多步迭代法若只与有关，且是线性的，即若只与有关，且是线性的，即其中其中 ，称为，称为单步线性迭代法单步线性迭代法，称为称为迭代距阵迭代距阵。若。若 和和 都与都与k 无关，即无关，即 称为称为单步定常线性迭代法单步定常线性迭代法。本章主要讨论具有这种形式的各种迭代方法。本章主要讨论具有这种形式的各种迭代方法。第5页，本讲稿共12页5.1 基本迭代方法基本迭代方法5.1.1 迭代公式的构造迭代公式的构造 设设 ，A非奇异，非奇异，满足方程组满足方程组 Ax=b。（5.1.1）如果能找到距阵如果能找到距阵 ，向量，向量 ，使，使 可逆，而且方程组可逆，而且方程组 x=Bx+f (5.1.2)的唯一解就是方程组（的唯一解就是方程组（5.1.1）的解，则可从（）的解，则可从（5.1.2）式构造一个定常的线）式构造一个定常的线性迭代公式性迭代公式 （5.1.3）给定初始向量给定初始向量 ,由由(5.1.3)可以产生序列可以产生序列 ,若它有极限若它有极限 ,显然显然 就是就是(5.1.1)和和(5.1.2)的解。的解。第6页，本讲稿共12页 定义定义 5.1 若对任意初始向量若对任意初始向量 ，迭代公式（，迭代公式（5.1.3）产生的）产生的序列序列 都有都有则称迭代法（则称迭代法（5.1.3）是收敛的。）是收敛的。从（从（5.1.1）出发，可以由不同的途径得到各种不同的等价方程组）出发，可以由不同的途径得到各种不同的等价方程组（5.1.2），从而得到不同的迭代法（），从而得到不同的迭代法（5.1.3）。例如，设）。例如，设A可以分解为可以分解为 ，其中，其中M非奇异，则由（非奇异，则由（5.1.1）可得）可得令令 就可以得到（就可以得到（5.1.2）的形式。不同的分解方式）的形式。不同的分解方式 ，可的不同的，可的不同的 B 和和 f,下面给出对应不同分解方式的常用迭代下面给出对应不同分解方式的常用迭代 计算公式。计算公式。第7页，本讲稿共12页5.1.2 Jacobi 迭代法和迭代法和 Gauss-Seidel迭代法迭代法 1.Jacobi 迭代法迭代法 记记 ，可以把可以把 A 分解为分解为 （5.1.4）其中其中现设现设D非奇异，即非奇异，即 。方程组（。方程组（5.1.1）等价于）等价于第8页，本讲稿共12页 用用 J 法计算向量序列法计算向量序列 ，要用两组单元存放向量，要用两组单元存放向量 和和 。迭代法可以写成分量形式迭代法可以写成分量形式（5.1.8）由此构造迭代公式：由此构造迭代公式：（5.1.5）其中迭代距阵其中迭代距阵 和向量和向量 为为 （5.1.6）（5.1.7）称（称（5.1.5）为解（）为解（5.1.1）的）的Jacobi 迭代法迭代法，简称，简称 J 法法。2.Gauss-Seidel 迭代法迭代法 在在J 法中，计算法中，计算 时，分量时，分量 已经算出，所以可考虑已经算出，所以可考虑第9页，本讲稿共12页对对J 法进行修改。在每个分量计算出来之后，下一个分量的计算就利用最法进行修改。在每个分量计算出来之后，下一个分量的计算就利用最 新的计算结果。这样，在整个迭代过程中只要使用一组单元存放迭代向新的计算结果。这样，在整个迭代过程中只要使用一组单元存放迭代向量，其分量形式的计算结果为量，其分量形式的计算结果为（5.1.9）这就是这就是Gauss-Seidel 迭代法迭代法，简称，简称 GS 法法 将（将（5.1.9）写成距阵形式）写成距阵形式经整理有经整理有（5.1.10）其中迭代距阵其中迭代距阵 和向量和向量 为为(5.1.11)第10页，本讲稿共12页(5.1.12)Jacobi 迭代法和迭代法和 Gauss-Seidel 迭代法的分量形式供计算编程用，它们迭代法的分量形式供计算编程用，它们的距阵形式供研究迭代序列是否收敛等理论分析用。的距阵形式供研究迭代序列是否收敛等理论分析用。例例.用法和法分别求解方程组用法和法分别求解方程组其准确解为其准确解为。解解 用用 J 法计算，按（法计算，按（5.1.8）有）有第11页，本讲稿共12页用用 GS 法计算，按（法计算，按（5.1.9）有）有 取取 ，J 法迭代法迭代4次的计算结果是次的计算结果是GS 法迭代法迭代4次的计算结果是次的计算结果是从计算结果看，本例用从计算结果看，本例用 GS 法显然比用法显然比用 J 法收敛快。法收敛快。第12页，本讲稿共12页
