数值计算方法与算法.ppt

文档介绍：数值计算方法与算法
求解线性方程组 Ax = y，可用直接法。当 A 为稀疏矩阵时，直接法将破坏矩阵 A 的稀疏性。
我们可以对线性方程组进行等价变换，构造出等价方程
组 x = Mx+g,由此构造迭代关系式
例如，分解A=N-P，则
迭代法：构造一个向量序列 {x(k)} ，使其收敛到某个极限向 量 x*，即 则x*就是线性方程组的解。
常用迭代方法：
雅可比迭代，高斯-赛德尔迭代，松弛迭代等。
雅可比迭代
雅可比迭代格式
迭代格式
线性方程组 Ax = y，即
若aii≠0, i = 1,2,…,n ,（）可变为
记 则
写成矩阵形式
或简记为
对任意初始向量 构造迭代格式：
()是称为简单迭代或雅可比迭代。
雅可比迭代矩阵 记
所以 称为雅可比迭代矩阵，
是常数项向量。
如果通过()构造的迭代序列{x(k)}收敛，即
则 x*为 Ax = y的解，即 Ax*= y。事实上，对()取极限得
迭代格式的收敛性
(线性代数定理) 设矩阵序列
则
（证明见关治和陈景良编《数值计算方法》P410~412）
设迭代格式为
由初始向量x(0)产生的向量序列{x(k)}收敛的充分必
要条件是
证明 必要性（）设 则由（）得
()-()得
设第k次迭代的误差记为
充分性（）设ρ(M)<1,证{x(k)}收敛。
如果ρ(M)<1 ，则I-M为非奇异矩阵。事实上，因为
ρ(M)<1，λi<1，因此λ=1不是M的特征值，即