ch06 数值分析.ppt

第六章
线性方程组的数值解法
-------迭代法
1
直接法得到的解是理论上准确的,但是计算量都是
n3数量级,存储量为n2量级,这在n比较小的时候
还比较合适(n<400)
实际问题中,往往方程组的阶数很高,而且这些矩
阵(系数矩阵)往往是含有大量的0元素(稀疏矩阵
方程组)。直接法运算量将会很大并且大量占用计
算机资源。
因此有必要引入一类新的方法:迭代法。
引言
2
迭代法的基本思想
迭代法是解线性方程组的一种重要的实用方
法,特别适用于求解在实际中大量出现的,系
数矩阵为稀疏阵的大型线性方程组。
迭代法的基本思想是去构成一个向量序列{x(k)},
使其收敛至某个极限向量x* ,并且x*就是要求解
的方程组:Ax = b 的准确解。
3
迭代法的主要步骤The process of iterative method
解线性方程组迭代法的主要步骤是:
把线性方程组Ax=b化成如下形式的同解方程组
x=Bx+f
给出初始向量,按迭
代公式
x(k+1)=Bx(k)+f (k=0,1,2,…)
进行计算,其中k 表迭代次数。
4
如果按上述迭代公式所得到的向量序列{ x(k)}收敛于某个向量x* ,则x* 就是方程组 Ax =b 的解,并称此迭代法收敛。否则,就叫不收敛或发散。
迭代公式中的矩阵B ,称为迭代矩阵。
问题
迭代公式的建立
迭代公式的收敛性
收敛速度
误差估计
5
基本迭代公式
把矩阵 A 分裂为
则
记 B = M-1N, f = M-1b, 则
注:选取M阵,就得到解 Ax=b 的各种迭代法.
6
本章重点介绍三个迭代法,即:
Jacobi迭代法
Gauss-Seidel 迭代法
超松弛迭代法(SOR法)
7
Jacobi迭代法
由方程组AX=b的第i个方程解出
得到一个同解方程组
8
获得相应的迭代公式
Jacobi迭代法
取初始向量
称上式为雅可比迭Jacobi迭代公式。
9
Jacobi迭代法的矩阵形式
若记
则有 A=D-L-U 成立,矩阵形式为
Dx =(L+U)x +b
等式两边乘以D-1,得
x= D-1(L+U)x+ D-1b
由此得到迭代公式( The iterative scheme is :)
x(k+1)= D-1(L+U)x(k)+ D-1b
10