数值计算方法与算法精选课件.ppt

关于数值计算方法与算法第一页，本课件共有47页 求解线性方程组 Ax=y，可用直接法。当 A 为稀疏矩阵时，直接法将破坏矩阵 A 的稀疏性。我们可以对线性方程组进行等价变换，构造出等价方程组 x=Mx+g,由此构造迭代关系式例如，分解A=N-P，则第二页，本课件共有47页迭代法：构造一个向量序列 x(k)，使其收敛到某个极限向 量 x*，即 则x*就是线性方程组的解。常用迭代方法：雅可比迭代，高斯-赛德尔迭代，松弛迭代等。第三页，本课件共有47页6.1 6.1 雅可比迭代6.1.1 雅可比迭代格式迭代格式 线性方程组 Ax=y，即 第四页，本课件共有47页若aii0,i=1,2,n,（6.1）可变为记 则第五页，本课件共有47页写成矩阵形式或简记为 对任意初始向量 构造迭代格式：(6.2)是称为简单迭代或雅可比迭代。第六页，本课件共有47页 雅可比迭代矩阵 记所以 称为雅可比迭代矩阵，是常数项向量。第七页，本课件共有47页如果通过(6.2)构造的迭代序列x(k)收敛，即则 x*为 Ax=y的解，即 Ax*=y。事实上，对(6.2)取极限得第八页，本课件共有47页迭代格式的收敛性引理6.1(线性代数定理)设矩阵序列 则 （证明见关治和陈景良编数值计算方法P410412）定理6.1 设迭代格式为 由初始向量x(0)产生的向量序列x(k)收敛的充分必 要条件是证明 必要性（）设 则由（6.3）得第九页，本课件共有47页(6.3)-(6.4)得设第k次迭代的误差记为充分性（）设(M)1,证x(k)收敛。如果(M)1，则I-M为非奇异矩阵。事实上，因为(M)1，i0称为松弛因子。将(6.9)变形为(6.9)或(6.10)称为松弛迭代法。迭代矩阵为 当01时，称为低松弛迭代；当12时，称为超松弛迭代；当=1时，即为高斯-塞德尔迭代。第三十六页，本课件共有47页 实际用计算机计算时，采用(6.9)的分量形式，即雅可比迭代、高斯-塞德尔迭代和松弛迭代均为单步线性迭代。第三十七页，本课件共有47页 松弛迭代的收敛性定理定理 6.6 6.6 松弛迭代收敛的必要条件是02。即若松弛迭 代收敛，则必有02。证明证明 松弛迭代矩阵 其中，第三十八页，本课件共有47页 如果松弛迭代收敛，由定理6.1知，即S的所有特征值的绝对值均小于1。由特征方程的性质得 由（1）和（2）两式得第三十九页，本课件共有47页定理定理 6.7 6.7 如果系数矩阵A为严格对角占优，当松弛因子 时，则松弛迭代收敛。证明类似于定理6.4。定理定理6.86.8 若A为对称正定矩阵时，则当 时，松弛迭代收敛。第四十页，本课件共有47页 松弛迭代算法 基本上与高斯-塞德尔迭代算法相同。第四十一页，本课件共有47页6.4 逆矩阵的计算1.用初等变换2.用伴随矩阵3.用逆矩阵的定义：第四十二页，本课件共有47页化为n个线性方程组：用直接法或迭代法算出：也就完成了逆矩阵 的计算。第四十三页，本课件共有47页2005.12.9第四十四页，本课件共有47页第四十五页，本课件共有47页6.5 程序示例第四十六页，本课件共有47页感感谢谢大大家家观观看看第四十七页，本课件共有47页