研究生翻译第2讲.ppt

算法见教材第27页： （1）消元过程.对k=1,2，…n-1进行如下运算： 对i=k+1.k+2,…,n; 对j=k+1,…,n+1, (2) 回代过程.按下述公式 算法见教材第27页： （1）消元过程.对k=1,2，…n-1进行如下运算： ① 选主元：找行号ik∈{k,…,n} 使 若为零，终止. ②交换[A(k),b(k)]中的第k,ik两行; ③对i=k+1.k+2,…,n;令 对j=k+1,…,n+1, (2) 回代过程.按下述公式 例求解 三角分解法的运算量与高斯消去法大体相当，但对于系数矩阵A不变而常数列b变化的的一类方程组来说，节省运算量 因为A=LU不用再分解，对于不同的b 直接解LY=b和UX=Y即可 列主元三角分解法主要思想 先解 先解 例如，AX=B两边都加X得 X+AX=X+b即X=X-AX+b=IX-AX+b 合并右边前两项得X=(I-A)X+b 这里 则当X(0)=X(1)时, X(1)就是原方程的解. 若X(0)≠X(1) ，但当二者差别非常小时，例如当 可认为X(0)≈X(1)可将X(1)作为近似解.否则… 定义2 （矩阵范数）若对任意n×n矩阵A，按一定规则对应一实数||A|| ，并满足以下条件： ①对任意n×n矩阵A， ||A||≥0，只有当A=0时， ||A||=0 ②对任意实数k， ||kA||= |k| ||A|| ③对任意n×n矩阵A，B, ||A+B||≤ ||A||+ ||B|| ④对任意n×n矩阵A，B, ||AB||≤ ||A|| ||B|| 则称||·|| 为矩阵范数. 定义3(P59) 若有向量范数||·||u和矩阵范数||·||v,使得对任意n×n矩阵A和n维向量X都有 ||AX||u ≤ ||A||v ||X||u 则称向量范数||·||u与矩阵范数||·||v是相容的.注意特别当u=v=1,2,∞，向量范数||·||u与矩阵范数||·||v是相容的. 二、迭代法的收敛性 雅可比、高斯-塞德尔迭代法举例： P76：第9,10题 定理3（P63） 若n×n矩阵A=[aij] n×n是严格对角占优矩阵，则A为非奇异矩阵. 证：用反正法.若|A|=0，则齐次线性方程组AX=0有非零解，设有一非零解为X 定理4（P64）若线性方程组AX=b的系数矩阵是严格对角占优矩阵，则①解此线性方程组的雅可比迭代法收敛.②解此线性方程组的高斯-塞德尔迭代法收敛. 定理5（P65）若线性方程组AX=b的系数矩阵A为正定矩阵，则解此线性方程组的高斯-塞德尔迭代法收敛 （证明从略） 则当X(2)=X(1)时, X(2)就是原方程的解. 若X(2)≠X(1) ，但当二者差别非常小时，例如当 可认为X(2)≈X(1)可将X(2)作为近似.否则… 则X*正是方程组X=MX+d的精确解 称X(k+1)=MX(k)+d为迭代公式， 称M为迭代矩阵.对应的方法为一种迭代法. 一.雅可比（Jacobi）迭代法 (1)迭代格式 设有n 阶方程组 其中系数矩阵非奇异，且 ，i=1,2，……，n 将上式变形为 建立迭代格式 上面的迭代式称为雅可比（Jacobi）迭代格式。 用矩阵形式来表示方程组的迭代格式 设det(A) ，且 则 记A=D+L+U 雅可比迭代式成为： 令 则得 举例…用矩阵形式和分量形式！ 称B为雅可比迭代矩阵 雅可比 高斯-塞德尔 迭代格式 二、高斯-塞德尔（Gauss-Seidel）迭代法 G-S迭代式成为： 则 令 则得 记A=D+L+U 举例…用矩阵形式和分量形式！ 称G为高斯-赛德尔迭代矩阵 三、逐次超松弛迭代法 （SOR法-Successive Over Relaxation） 1.迭代公式 将G-S迭代格式 改写为： 并记 一般地，残量(余量) 。 这就是逐次超松驰迭代法（SOR方法)， 称为松驰 因子。 SOR方法的计算公式也常写为： Remark：可见，SOR方法的得到的 可以看成是G-S方法的结果与 的加权平均。 将残量乘以一个修正量加到 上，作为新的结果 P56例1 §2.3迭代法的收敛性 一、向量的范数和矩阵的范数 定义1 （向量范数）对任意n维向量X∈Rn,若按一定规则对应一实数||X|| ，并满足以下条件： ①正定条件.即对任意X∈Rn, ||X||≥0，只有当X=0时， ||X||=0 ②齐次性.对任意