成都市中考满分作文-第八章 线性方程组的迭代解法.doc

第八章 线性方程组的迭代解法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)。8.2.2 Gauss-Seidel（高斯-赛德尔）迭代法由Jacobi方法迭代公式可知，迭代的每一步计算过程，都是用x(k)的全部分量来计算x(k+1)的所有分量。能否在计算x(k+1)的第i个分量时，利用x(k+1)已经计算出的前i-1个分量的信息？这样做有两方面的优势：1、 从直观上看，最新计算出的分量可能比旧的分量要好些（更精确逼近线性方程组的真实解向量）。2、 计算时只需要x(k)的i+1n个分量，因此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迭代公式：得： 写成矩阵的形式： 若设存在，则：于是，Gauss-Seidel迭代公式的矩阵形式为： 其中：， 称G为Gauss-Seidel迭代方法的迭代矩阵。特点：在用计算机计算时，只需一组存储单元，以便存放近似解。每迭代一步只需计算一次矩阵与向量的乘法。 例8.2此例题中Gauss-Seidel迭代法比Jacobi迭代法收敛快，但这个结论在一定条件下才是对的。（当Jacobi迭代法和Gauss-Seidel迭代法都收敛时，Gauss-Seidel迭代法比Jacobi迭代法收敛快） 例8.3此例题说明，存在某些线性方程组，用Jacobi迭代法收敛而Gauss-Seidel迭代法发散。注意：1) Gauss-Seidel迭代法的计算过程中只需用一个一维数组存放迭代向量。2) Gauss-Seidel迭代不一定比Jacobi迭代收敛快。8.3 迭代法的收敛性前面已经从误差的角度分析了迭代过程收敛的条件：如果迭代矩阵B满足（零矩阵），那么就成立，即，迭代过程收敛。 矩阵序列的极限定义8.2 设有矩阵序列（）及，如果（）成立，则称收敛于A，记作。例8.4 矩阵序列的例子矩阵序列极限的概念可以用任何矩阵范数来描述。 范数的定义如果矩阵的某个非负实函数，记作，满足条件：（1）当且仅当时，（非负性）（2） （齐次性）（3）对任意两个阶数相同的矩阵A,B有（三角不等式性）（4）A,B矩阵为同阶矩阵, （相容性）则称为矩阵范数。矩阵范数的例子：A的行范数： A的列范数：A的2范数： （是最大特征值） 定理8.1 的充要条件是 （）（证明略。） 定理8.2设迭代矩阵，则（）的充要条件是。（证明见P206）注：是矩阵B的普半径。设A是n n矩阵，i (i=1,2,n)是其特征值。称为A的谱半径。即矩阵A的特征值中绝对值最大的那一个特征值的绝对值。矩阵A的特征值和特征向量：的根，为矩阵A的特征值。满足的向量v为矩阵A的对于特征值的特征向量。 定理8.