成都市中考满分作文线性方程组的迭代解法.docVIP

第八章 线性方程组的迭代解法 7.1 引言 解线性方程组的直接方法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在系数矩阵A的规模比较小的时候还比较合适（如：矩阵维数n400）。但是，当A为大型稀疏矩阵时，再利用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法：迭代法。 从第六章方程求根的迭代方法可以推测： 迭代法：从线性方程组一个初始的近似解（向量）出发，反复套用同一个迭代公式，构造一个无穷序列，逐步逼近方程组精确解的方法（一般有限步内得不到精确解）。 特点：该方法具有存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点，但是存在收敛性及收敛速度方面的问题。 例8.1（P201） 如何设计方程组的迭代公式 线性方程组： 等价的迭代方程组： 迭代过程： 可以写成多种等价的迭代方程组，例如 ： ， （例8.1） ， Jacobi迭代 注：的形式如下 问题： 1、是否任意一个等价的迭代方程组，按迭代法做出的向量序列都一定逐步逼近方程组的解呢？ 2、如何保证收敛性？ 定义8.1 对于给定的方程组，用式子 逐步代入求近似解的方法称为迭代法（或称为一阶定常迭代法，这里B与迭代次数k无关）。 如果存在（记作），称此迭代法收敛，显然就是方程组的解；否则称此迭代法发散。 收敛性讨论 从误差的角度分析，引入误差向量： 则： ， 将的各个方程减去得： ，为初始误差 如果矩阵B满足（零矩阵），那么就成立，即，迭代过程收敛。 8.2 Jacobi迭代法与Gauss-Seidel迭代法 8.2.1 Jacobi（雅可比）迭代法 迭代公式 线性方程组： 矩阵形式描述： 等价的迭代方程组： B=？ f=？ 即： 因此，Jacobi迭代法的迭代公式为 迭代矩阵 令 ，其中： 则，等价的迭代方程组为： 迭代公式的矩阵形式为： 称B为Jacobi方法迭代矩阵。 特点： Jacobi迭代法公式简单，每迭代一次只需要计算一次矩阵和向量乘法！ 在用计算机计算时，计算x(k+1)时需要x(k)的所有分量，因此需开两组存储单元分别存放x(k)和x(k+1)。 由Jacobi方法迭代公式可知，迭代的每一步计算过程，都是用x(k)的全部分量来计算x(k+1)的所有分量。 x(k+1)的时，利用x(k+1)已经计算出的前i-1个分量的信息？ 这样做有两方面的优势： 从直观上看，必威体育精装版计算出的分量可能比旧的分量要好些（更精确逼近线性方程组的真实解向量）。 计算时只需要x(k)的i+1~n个分量，因此x(k+1)的前i个分量可存储在x(k)的前i个分量所占的存储单元，无需开两组存储单元。 因此，对这些必威体育精装版计算出来的第k+1次近似x(k+1)的加以利用，就得到解方程组的Gauss-Seidel迭代法（G-S方法）。 迭代公式 Gauss-Seidel迭代法的迭代公式： 注：对比Jacobi迭代公式： Gauss-Seidel迭代公式也可以写为： （注意第二项求和，j=i） 得： 写成矩阵的形式： 若设存在，则： 于是，Gauss-Seidel迭代公式的矩阵形式为： 其中：， 称G为Gauss-Seidel迭代方法的迭代矩阵。 特点： 在用计算机计算时，需组存储单元Gauss-Seidel迭代法的计算过程中只需用一个一维数组存放迭代向量。 Gauss-Seidel迭代不一定比Jacobi迭代收敛快。 8.3 迭代法的收敛性 前面已经从误差的角度分析了迭代过程收敛的条件： 如果迭代矩阵B满足（零矩阵），那么就成立，即，迭代过程收敛。 矩阵序列的极限 定义8.2 设有矩阵序列（）及，如果 （） 成立，则称收敛于A，记作。 例8.4 矩阵序列的例子 矩阵序列极限的概念可以用任何矩阵范数来描述。 范数的定义 如果矩阵的某个非负实函数，记作，满足条件： 　　（1）当且仅当时，（非负性） 　　（2） （齐次性） 　　（3）对任意两个阶数相同的矩阵A,B有（三角不等式性） 　　（4）A,B矩阵为同阶矩阵, （相容性） 　则称为矩阵范数。 矩阵范数的例子： A的行范数： A的列范数： A的2范数： （是最大特征值） 的充要条件是 （） （证明略。） 定理8.2 设迭代矩阵，则（）的充要条件是。 （证明见P206） 注： 是矩阵B的普半径。 设A是n