第四章-解AXb的迭代法.ppt

第四章 解线性代数方程组的迭代法 三种基本的迭代方法及收敛条件 4.1 雅可比迭代 4.2 高斯-赛德尔(Gauss-Seidel)迭代 4.3 超松弛迭代 求解线性方程组 Ax = y，可用直接法。当 A 为稀疏矩阵时，直接法将破坏矩阵 A 的稀疏性。 我们可以对线性方程组进行等价变换，构造出等价方程 组 x = Mx+g,由此构造迭代关系式 例如，分解A=N-P，则 迭代法： 构造一个向量序列 {x(k)} ，使其收敛到某个极限向量 x*，即 则 x* 就是线性方程组的解。 常用迭代方法： 雅可比迭代，高斯-赛德尔迭代，松弛迭代等。 4.1 雅可比迭代 迭代格式 线性方程组 Ax = y，即 若aii≠0, i = 1,2,…,n ,（6.1）可变为 记 则 写成矩阵形式 或简记为 对任意初始向量 构造迭代格式： (4.2)是称为简单迭代或雅可比迭代。 雅可比迭代矩阵 记 所以 称为雅可比迭代矩阵， 是常数项向量。 如果通过(4.2)构造的迭代序列{x(k)}收敛，即 则 x*为 Ax = y的解，即 Ax*= y。事实上，对(4.2)取极限得 迭代格式的收敛性 引理4.1 (线性代数定理) 设矩阵序列 则 （证明见关治和陈景良编《数值计算方法》P410-412） 定理4.1 设迭代格式为 由初始向量x(0)产生的向量序列{x(k)}收敛的充分必要条件是 证明 必要性（?）设 则由（4.3）得 (4.3)-(4.4)得 设第k次迭代的误差记为 充分性（?）设ρ(M)1,证{x(k)}收敛。 如果ρ(M)1 ，则I-M为非奇异矩阵。事实上，因 为ρ(M)1，λi1，因此λ=1不是M的特征值，即 所以方程组 (I-M)x = f 有惟一解x*,满足(I-M)x* = f ，即 x*=Mx* + f 。于是 由引理4.1知， 例4.1 设系数矩阵为 判定雅可比迭代格式的收敛性。 解 雅可比迭代矩阵为 特征方程为 实际计算中，M的特征值难于计算，因此 也难于判断。由于 可用 作为判断收敛的条件。 定理4.2 若 则由迭代格式 确定的迭代序列{x(k)}收敛，且有误差估计式 证明 又因为 分别把（c）和（d）代入（e）即得证（a）,（b）。 注： 是 收敛的充分条件，但不是必要条件。 因为 收敛，不能推出 。例如 定义4.1 如果A的元素满足 并且至少有一个不等式严格成立，则称A为行对角占优矩阵； 如果A的元素满足 则称A为严格行对角占优矩阵。 同样可以定义列对角占优矩阵和严格列对角占优矩阵。 引理 4.2 （对角优势定理） 若A为严格对角占优矩阵，则A非奇异，且aii≠0,i=1,2,…,n. 证明 由线性代数知识知，det(A)≠0 ? Ax=0只有零解。 反证法 假定 det(A)=0 ，则Ax=0有非零解，记为 当方程组的系数矩阵为严格对角占优时，关于雅可比迭代我们有下面的定理。 定理 4.3 当系数矩阵为严格对角占优时，雅可比迭代收敛。 证明 方法一：根据严格对角占优矩阵的定义。 雅可比迭代矩阵： 方法二：反证法。 因为A为严格对角占优矩阵，由引理4.2知，aii≠0. 雅可比迭代算法 算法描述： 1. 输入系数矩阵A和常数项向量y； 2. 形成雅可比迭代矩阵B和向量g 4.2 高斯-塞德尔(Gauss-Seidel)迭代 高斯-塞德尔迭代的计算 在雅可比迭代(4.4)的迭代过程中，可用新求出的x(k+1)的分量来代替x(k)的分量参与计算，直到用x(k+1)的前n-1分量代