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

第八章 线性方程组的迭代解法
7.1 引言
解线性方程组的直接方法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3数量级，存储量为n2量级，这在系数矩阵A的规模比较小的时候还比较合适（如：矩阵维数n<400）。但是，当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+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迭代公式：

得：
写成矩阵的形式：

若设存在，则：
于是，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.3 迭代法的收敛性定理
设有方程组对于任意初始向量及任意f，解此方程组的迭代法（即）收敛的充要条件是。
（证明见P207-208）
验证迭代过程是否收敛的例子：
例8.5，例8.6
Ø 收敛速度的讨论
可以看出，当越小时，收敛速度越快。