数值分析方程组迭代法.pptVIP

Jacobi 和Gauss-Seidel的收敛性 * 第二十九页，共五十四页，2022年，8月28日 注 * 第三十页，共五十四页，2022年，8月28日 对于前面的例子 由迭代矩阵的特征方程 因而雅可比迭代公式是收敛的。 * 第三十一页，共五十四页，2022年，8月28日 注 * 第三十二页，共五十四页，2022年，8月28日 直接用矩阵A判定敛散性 收敛性定理虽然给出了判别迭代法收敛的充要条件， 但实际使用时很不方便，因为求逆矩阵和特征值的 难度并不亚于用直接法求解线性方程组。 下面对一些特殊的方程组，从方程组本身出发给出几个常用 的判别条件，而不必求迭代阵的特征值或范数。 定义 如果矩阵A满足条件 则称A是严格对角占优阵(strictly diagonally dominant matrix)； * 第三十三页，共五十四页，2022年，8月28日 A为按行按列严格对角占优阵；B为按行对角占优阵。 实例(Example) * 第三十四页，共五十四页，2022年，8月28日 定理1 若A为严格对角占优阵，则Jacobi 迭代法和 G-S迭代法收敛。 定理2 若A为对称正定阵，则G-S迭代法收敛。 相关定理 可以总结，讨论迭代法的收敛性，应首先从A出发讨 论其是否具有主对角占优或对称正定性；其次对迭代 法的迭代阵讨论其是否有范数小于1；最后利用迭代 阵的谱半径讨论（这是充分必要条件）。 * 第三十五页，共五十四页，2022年，8月28日 定理1的证明 证 首先证明Jacobi 迭代的收敛性。由 易求 由严格对角占优定义，得 ?? BJ ??∞1,所以, Jacobi 迭代法收敛。 * 第三十六页，共五十四页，2022年，8月28日 下面证明G-S迭代法的收敛性。对于严格对角占优阵A，其对角元素 aii ≠ 0 ， i=1,2,??????,n，故 考虑BG的特征值λ，其特征方程为 det(?I-BG) = det(?I-(D-L)-1U) = det(D-L)-1det(?(D-L)-U)=０ = det(?(D-L)-U)=0 * 第三十七页，共五十四页，2022年，8月28日 我们通过A的严格对角占优性质去证明det(?(D-L)-U)=0的根?有性质 | ? |1。用反证法：假设| ? |≥1，且由于A的严格对角占优性质，有 * 第三十八页，共五十四页，2022年，8月28日 * 第一页，共五十四页，2022年，8月28日 直接法得到的解是理论上准确的，但是计算量都是 n3数量级，存储量为n2量级，这在n比较小的时候 还比较合适（n400） 实际问题中，往往方程组的阶数很高，而且这些矩 阵(系数矩阵)往往是含有大量的0元素（稀疏矩阵 方程组）。直接法运算量将会很大并且大量占用计 算机资源。 因此有必要引入一类新的方法：迭代法。 引言 * 第二页，共五十四页，2022年，8月28日 迭代法的基本思想 迭代法是解线性方程组的一种重要的实用方 法，特别适用于求解在实际中大量出现的，系 数矩阵为稀疏阵的大型线性方程组。 迭代法的基本思想是去构成一个向量序列 {x(k)}， 使其收敛至某个极限向量x* ，并且x*就是要求解 的方程组：Ax = b 的准确解。 * 第三页，共五十四页，2022年，8月28日 迭代法的主要步骤The process of iterative method 解线性方程组迭代法的主要步骤是: 把线性方程组Ax=b化成如下形式的同解方程组 x=Bx+f 给出初始向量 ,按迭 代公式 x(k+1)=Bx(k)+f (k=0,1,2,…) 进行计算,其中k 表迭代次数。 * 第四页，共五十四页，2022年，8月28日 如果按上述迭代公式所得到的向量序列{ x(k)}收敛于某个向量x* ,则x* 就是方程组 Ax =b 的解，并称此迭代法收敛。否则，就叫不收敛或发散。 迭代公式中的矩阵B ，称为迭代矩阵。 问题 迭代公式的建立 迭代公式的收敛性 收敛速度 误差估计 * 第五页，共五十