《解axb的迭代法》由会员分享，可在线阅读，更多相关《解axb的迭代法（38页珍藏版）》请在金锄头文库上搜索。
1、第四章 解线性代数方程组的迭代法,三种基本的迭代方法及收敛条件 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，即
2、,若aii0, 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、.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
4、）即得证（a）,（b）。 注： 是 收敛的充分条件，但不是必要条件。 因为 收敛，不能推出 。例如,定义4.1 如果A的元素满足,并且至少有一个不等式严格成立，则称A为行对角占优矩阵； 如果A的元素满足 则称A为严格行对角占优矩阵。 同样可以定义列对角占优矩阵和严格列对角占优矩阵。 引理 4.2 （对角优势定理） 若A为严格对角占优矩阵，则A非奇异，且aii0,i=1,2,n.,证明 由线性代数知识知，det(A)0 Ax=0只有零解。,反证法 假定 det(A)=0 ，则Ax=0有非零解，记为,当方程组的系数矩阵为严格对角占优时，关于雅可比迭代我们有下面的定理。,定理 4.3 当系数矩阵为严
5、格对角占优时，雅可比迭代收敛。 证明 方法一：根据严格对角占优矩阵的定义。 雅可比迭代矩阵：,方法二：反证法。,因为A为严格对角占优矩阵，由引理4.2知，aii0.,雅可比迭代算法,算法描述： 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，其中,则高斯-赛德尔迭代可写成
6、矩阵形式 或写成 其中， 为高斯-塞德尔迭代矩阵，,高斯-塞德尔迭代的收敛性,由定理4.1知，高斯-塞德尔迭代收敛的充分必要条件为 也可以利用条件 来判断高斯-塞德尔迭代收敛。 定理 4.4 当系数矩阵为严格对角占优时，高斯-塞德尔迭代收敛。 证明 类似于定理4.3的证明。反证法。,定理 4.5 当系数矩阵A为正定矩阵，高斯-塞德尔迭代收敛。,证明,例4.2 设系数矩阵为,判定高斯-塞德尔迭代格式的收敛性。 解 高斯-塞德尔迭代矩阵为 其中，,4.3 超松弛迭代,高斯-塞德尔迭代为 松弛迭代法是高斯-塞德尔迭代法的一种变化形式。令,其中，参数0称为松弛因子。将(4.9)变形为,(4.9)或(4
7、.10)称为松弛迭代法。迭代矩阵为 当01时，称为低松弛迭代； 当12时，称为超松弛迭代； 当=1时， 即为高斯-塞德尔迭代。,实际用计算机计算时，采用(4.9)的分量形式，即,雅可比迭代、高斯-塞德尔迭代和松弛迭代均为单步线性迭代。,松弛迭代的收敛性,定理 4.6 松弛迭代收敛的必要条件是02。即若松弛迭代收敛，则必有02。 证明 松弛迭代矩阵 其中，,如果松弛迭代收敛，由定理4.1知， 即S的所有特征值的绝对值均小于1。由特征方程的性质得 由（1）和（2）两式得,定理 4.7 如果系数矩阵A为严格对角占优，当松弛因子 时，则松弛迭代收敛。,证明类似于定理4.4。 定理4.8 若A为对称正定矩阵时，则当 时，松弛迭代收敛。,逆矩阵的计算,1. 用初等变换 2. 用伴随矩阵 3. 用逆矩阵的定义：,化为n个线性方程组： 用直接法或迭代法算出： 也就完成了逆矩阵 的计算。,
