解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分量代替x(k) 的前n-1个分量求出 为止，即可由（4.5）得到高斯-塞德尔迭代：,令B=L+U，其中,则高斯-赛德尔迭代可写成矩阵形式 或写成 其中， 为高斯-塞德尔迭代矩阵，,高斯-塞德尔迭代的收敛性,由定理4.1知，高斯-塞德尔迭代收敛的充分必要条件为 也可以利用条件 来判断高斯-塞德尔迭代收敛。

定理 4.4 当系数矩阵为严格对角占优时，高斯-塞德尔迭代收敛 证明 类似于定理4.3的证明定理 4.5 当系数矩阵A为正定矩阵，高斯-塞德尔迭代收敛证明,例4.2 设系数矩阵为,判定高斯-塞德尔迭代格式的收敛性 解 高斯-塞德尔迭代矩阵为 其中，,4.3 超松弛迭代,高斯-塞德尔迭代为 松弛迭代法是高斯-塞德尔迭代法的一种变化形式令,其中，参数ω0称为松弛因子将(4.9)变形为,(4.9)或(4.10)称为松弛迭代法迭代矩阵为 当0ω1时，称为低松弛迭代； 当1ω2时，称为超松弛迭代； 当ω=1时， 即为高斯-塞德尔迭代实际用计算机计算时，采用(4.9)的分量形式，即,雅可比迭代、高斯-塞德尔迭代和松弛迭代均为单步线性迭代松弛迭代的收敛性,定理 4.6 松弛迭代收敛的必要条件是0ω2即若松弛迭代收敛，则必有0ω2 证明 松弛迭代矩阵 其中，,如果松弛迭代收敛，由定理4.1知， 即Sω的所有特征值的绝对值均小于1由特征方程的性质得 由（1）和（2）两式得,定理 4.7 如果系数矩阵A为严格对角占优，当松弛因子 时，则松弛迭代收敛。

证明类似于定理4.4 定理4.8 若A为对称正定矩阵时，则当 时，松弛迭代收敛逆矩阵的计算,1. 用初等变换 2. 用伴随矩阵 3. 用逆矩阵的定义：,化为n个线性方程组： 用直接法或迭代法算出： 也就完成了逆矩阵 的计算。