《第六章解线性方程组的迭代法.doc》由会员分享，可在线阅读，更多相关《第六章解线性方程组的迭代法.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品文档，仅供学习与交流，如有侵权请联系网站删除第五章 解线性方程组的迭代法本章主要内容：迭代法收敛定义，矩阵序列收敛定义，迭代法基本定理，雅可比迭代法，高斯-塞德尔迭代法，系数矩阵为严格对角占优阵的采用雅可比迭代、高斯-塞德尔迭代的收敛性。教学目的及要求：使学生了解迭代法收敛定义，迭代法基本定理，掌握雅可比迭代法、高斯-塞德尔迭代法。教学重点：雅可比迭代法，高斯-塞德尔迭代法。教学难点：迭代法基本定理的证明以及作用。教学方法及手段：应用严格的高等代数、数学分析知识，完整地证明迭代法基本定理，讲清雅可比迭代法与高斯-塞德尔迭代法的关系，介绍雅可比迭代法与高斯-塞德尔迭代法在编程中的具体实现方法
2、。在实验教学中，通过一个具体实例，让学生掌握雅可比迭代法与高斯-塞德尔迭代法的具体实现，并能通过数值计算实验，揭示高斯-塞德尔迭代法是对雅可比迭代法的一种改进这一事实。教学时间：本章的教学的讲授时间为6学时，实验学时4学时。教学内容：一 迭代法定义对于给定的线性方程组，设它有唯一解，则 (6.1)又设为任取的初始向量，按下述公式构造向量序列 (6.2)这种逐步代入求近似解的方法称为迭代法（这里B与f与k无关）。如果存在（记为），称此迭代法收敛，显然就是方程组的解，否则称此迭代法发散。迭代法求方程近似解的关键是是讨论由(6.1)式所构造出来的向量序列是否收敛。为此，我们引入误差向量将(6.2)式
3、与(6.1)式相减，我们可得递推下去，得要考察的收敛性，就要研究在什么条件下有也就是要研究在什么条件下有二 迭代法收敛性定理矩阵的收敛性定义设有矩阵序列及，如果个数列极限均存在且有则称收敛于，记为。注：矩阵序列的收敛性是根据矩阵的每个分量序列的收敛性来定义的。【例题1】讨论约当块矩阵的幂次所构成的矩阵序列的收敛性。形如的矩阵称之为n阶的约当块。它可以分解成为下面，我们分几步来研究矩阵序列的收敛性。1 矩阵的幂阵的性质我们不妨以4阶阵来看看这种性质。的性质可归纳为以下两点：（1） 如时，；（2） m=1时，的第2条对角线元素为1，其余为零；m=2时，的第3条对角线元素为1，其余为零；m=3时，的
4、第4条对角线元素为1，其余为零。 简言之，的第m+1条对角线元素为1，其余为零（当没有第m+1条对角线时，应理解为零矩阵）。2 计算约当块的幂次。当时，3 一个极限性质因为，得到这里，注意事实4 约当块幂阵的收敛性结论当时，收敛于零矩阵；当，发散。矩阵序列极限的概念可以用矩阵范数来描述。【定理1】，其中为矩阵的任意一种范数。证明 显然有再利用矩阵范数的等价性，可证明定理对其他矩阵范数也成立。【定理2】的充要条件是，有。证明 必要性 记，据，可知。设，对于，有由可知，。类似地，可证明 。这里，是中的基本单位向量组。，则即 ，亦即 。充分性 据，有 ，由的任意性，如果取，则亦即 类似地，可分别让，
5、可得故 从而 。【定理3】设，则的充要条件是。证明 由高等代数知识，存在非奇奇异矩阵P使其中约当块且，显然有其中于是 据例题1的结论，的充要条件是故的充要条件是。【定理4】（迭代法基本定理）设有方程组以及迭代法对任意选取初始向量，迭代法收敛的充要条件是矩阵的谱半径。证明 充分性 设则矩阵的特征值均大于零，故非奇异。有唯一解，且 ，即 。误差向量由设，应用定理3，有。于是，对任意，有，即 。必要性 设对任意有其中，显然，极限是方程组的解，且对任意有由定理2知 。再由定理3，即得。判断迭代收敛时，需要计算，一般情况下，这不太方便。由于，在实际应用中，常常利用矩阵B的范数来判别迭代法的收敛性。【定理
6、5】（迭代法收敛的充分条件）设有方程组以及迭代法如果有B的某种范数，则（1）迭代法收敛，即对任取有 且 。（2）。（3）。（4）。证明 （1）由基本定理4，结论（1）是显然的。（2）由关系式，有（3）即显然亦成立。（4）。注：该定理中的第3款可作为误差的事后估计式。三 几种常见的迭代法及收敛性下面，我们讨论线性方程组如何用迭代法求近似解的问题。这里，为非奇异矩阵，。（一） 雅可比迭代法。设，将A分解成以下三部分记，那么 形成迭代式对于任意初值，（）这就是雅可比迭代法。注：1 形成雅可比迭代式的条件是A的主对角线元素均非零。2 雅可比迭代收敛的条件是。【例题2】对于线性方程组利用雅可比迭代法求其
7、近似解（允许的最大迭代次数N，近似解的精度eps，由用户设定）。（二） 高斯-塞德尔迭代法。从雅可比迭代的分量形式可以发现，在进行第k次迭代时，利用，生成向量，其分量产生的次序是，。我们对雅可比方法进行以下改变设计：步1 应用信息，据雅可比迭代分量式，生成分量；步2 应用信息，据雅可比迭代分量式，生成分量；步3 应用信息，据雅可比迭代分量式，生成分量；步n 应用信息，据雅可比迭代分量式，生成分量。如此生成的设计方案，是想更好地利用已有的最新有用信息。有理由相信，如此所获得的迭代式，其计算效果应该会更好一些。下面，我们具体给出这种迭代法的表达形式。即左边可改写为右边可改写为亦即注意到： ，于是有
8、迭代矩阵为迭代向量为故高斯-塞德尔迭代式为故高斯-塞德尔迭代式的分量计算公式为实现高斯-塞德尔迭代法的分量计算公式的算法步1 ，输入允许的最大迭代次数N，用户精度eps，k=0。步2 对于i=1,2,n， 步3 对于i=1,2,n步4 k=k+1步5 若，输出近似解，停止计算。否则，执行步6。步6 若k=N，输出达到迭代次数信息，程序中止。否则，执行步7。步7 对于i=1,2,n，返回步2。注：1 形成高斯-塞德尔迭代式的条件是存在，而，故只要A的主对角线元素均非零，该逆阵存在。2 高斯-塞德尔迭代收敛的条件是。【例题3】对于线性方程组1 高斯塞德尔迭代法求其近似解（允许的最大迭代次数N，近似
9、解的精度eps，由用户设定）。2 通过数值实验说明，求该线性方程组的近似解时，高斯塞德尔迭代法的收敛速度较雅可比迭代法要快一些。3 采用分量计算公式编程求该线性方程组的近似解，验证用矩阵迭代形式求解所得的结果。四 关于解某些特殊方程组迭代法的收敛性在科学及工程计算中，要求方程组，其矩阵常常具有某些特性。例如，具有对角占优性质或为不可约阵，或是对称正定阵等，下面讨论用基本迭代法解这些方程组的收敛性。【定义1】设1 如果A的元素满足称A为严格对角占优阵。2 如果A的元素满足且上式至少有一个不等式严格成立，称A为弱对角占优阵。【定义2】设()，如果存在置换阵P，使其中，为r阶方阵，为n-r阶方阵()
10、，则称A为可约矩阵。否则，则称A为不可约矩阵。【定理6】（对角占优定理）如果为严格对角占优矩阵或A为不可约弱对角占优矩阵，则A为非奇异矩阵。证明 只就A为严格对角占优矩阵证明此定理。采用反证法，如果，则有非零解，记为，则。由齐次方程组第k个方程则有即 与假设矛盾，故，A为非奇异矩阵。【定理7】设，如果1 A为严格对角占优矩阵，则解的雅可比迭代法，高斯-塞德尔迭代法均收敛。2 A为弱对有占优阵，且A为不可约矩阵，则解的雅可比迭代法，高斯-塞德尔迭代法均收敛。证明 只证明1A为严格对角占优矩阵，故故A的主对角元素均为非零的，可以生成雅可比迭代式其中，。从而 ，雅可比迭代法收敛。同样，也可以生成高斯-塞德尔迭代其中，。下面考察B的特征值情况。设为B的任一特征值，于是有由于，于是记 下面来证明，当时，则，于是便证明了B的任一特征值均满足，从而，高斯-塞德尔迭代法收敛。事实上，当时，由A为严格对角占优矩阵，则有即C矩阵为严格对角占优，故。小结：本章主要介绍了解大型稀疏线性方程组的一些基本迭代方法，如雅可比迭代法、G-S迭代法，SOR法等，建立了迭代法收敛的基本理论。 迭代法是一种逐次逼近的方法，在使用迭代法解方程组时，其系数矩阵在计算过程中始终不变。迭代法具有循环的计算公式，方法简单，适宜解大型稀疏矩阵方程组，不过在使用迭代法时候要注意收敛性和收敛速度问题。【精品文档】第 8 页