计算物理课件 Chapter6.ppt

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