第三章 线性方程组的迭代解法ppt课件.ppt

《第三章 线性方程组的迭代解法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性方程组的解法思路与解f(x)=0的不动点迭代相似……，将等价改写为形式，建立迭代　。从初值出发，得到序列。求解，有迭代法和直接法先介绍迭代法§3.1雅可比(Jacobi)迭代法其中是迭代初值。写成矩阵形式：A=LUD写成迭代法形式B称为Jacobi迭代阵即其中…………写成矩阵形式：BGauss-Seidel迭代阵§3.2高斯-赛德尔(Gauss-Seidel)迭代法例3.2.1用Gauss-Seidel迭代法求解方程组取初始向量,要求时迭代终止。解：Gauss-Seidel迭代格式为:计算结果可列表如下注：1.未必Seidel方法一定比Jacobi方法好。2.二种方法都存在收敛性问

2、题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。残余误差§3.3超松弛迭代法ri(k+1)=下面令，希望通过选取合适的来加速收敛，这就是松弛法（或SOR法）。称作松弛因子。iikikikiarxx)1()()1(+++=w0<<1低松弛法=1Gauss-Seidel法1<<2(渐次)超松弛法写成矩阵形式：松弛迭代阵（Kahan必要条件）设A可逆，且aii0，则松弛法从任意出发都收敛0<<2。定理3.3.1证明：省略§3.4迭代法的收敛性的收敛条件设存在唯一解，则从任意出发，迭代收敛

3、(B)<1定理3.4.1(迭代法基本定理)①②（充分条件）若存在一个矩阵范数使得

4、

5、B

6、

7、=q<1,则迭代收敛，且有下列误差估计：定理3.4.2证明：省略。（充分条件）若A为严格对角占优阵,则解的Jacobi和Gauss-Seidel迭代均收敛。定理3.4.3定义3.4.1设A=(aij)nn,如果即主对角线上的元素绝对值大于同行其它元素的绝对值之和，那么称矩阵A是严格对角占优阵。§3.5高斯消去法或叫高斯消元法，是一个古老的求解线性方程组的直接法。思路首先通过消元将A化为上三角阵，再回代求解。=消元记第一步：设，计算因子将增广矩阵第i行mi1第1行，得到其中第k步：设，计算因子且计算

8、共进行？步n1回代注：事实上，只要A非奇异，即A1存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。如果出现某个akk(k)=0或其绝对值很小,则消元过程无法进行下去，或者将严重影响计算精度。这个问题通常可通过与以下的某行交换来克服。§3.6高斯列主元消去法例3.6.1：单精度解方程组/*精确解为和*/8个8个用高斯消去法计算：8个小主元可能导致计算失败。到此原方程组化为列主元素消去法到此原方程组化为：(n)回代求解公式(n-1)原方程组化为以上为消元过程。这是回代过程。§3.7三角分解法高斯消去法的矩阵形式:步骤1:记L1=，则步骤n1:其中Lk=单位下三角阵记为

9、L记U=称为A的LU分解若A的所有顺序主子式均不为0，则A的LU分解唯一（其中L为单位下三角阵，这种分接称为道立特(Doolittle)分解法）。定理3.7.1为什么要讨论三角分解？若在消元法进行前能实现三角分解A=LU,则容易回代求解回代求解很容易，如＝通过比较法直接导出L和U的计算公式。思路因为L的第i行只有前i个元素不为0，而U的第j列只有前j个元素不为0，故由矩阵乘法………………………分别固定i＝1,…,n:对j=i,i+1,…,n有lii=1将i，j对换，对j=i,i+1,…,n有DooLittle分解公式：§3.8追赶法（解三对角方程组）利用高斯消去法，经过n-1次消元，可将它化

10、为同解方程组易知求这些值的过程(即消元过程)称为追。再利用回代过程求出方程组的各变量。这一逆序求变量的过程(即回代过程)称为赶。§3.10(线性方程组的)误差分析求解时，A和的误差对解有何影响？设A精确，有误差　，得到的解为，即绝对误差放大因子又相对误差放大因子(只要A充分小，使得(I+A1A)一定可逆吗?设精确，A有误差　，得到的解为，即是关键的误差放大因子，称为A的条件数，记为cond(A),此数越则A越病态，越难得准确解。大注:cond(A)的具体大小与

11、

12、·

13、

14、的取法有关，但相对大小一致。cond(A)取决于A，与解题方法无关。常用条件数有：cond(A)1cond(

15、A)cond(A)2特别地，若A对称，则条件数的性质：A可逆，则cond(A)p1；A可逆，R则cond(A)=cond(A)；A正交，则cond(A)2=1；A可逆，R正交，则cond(RA)2=cond(AR)2=cond(A)2。精确解为例3.10.1：计算cond(A)2。A1=解：考察A的特征值39206>>1测试病态程度：给　一个扰动，其相对误差为此时精确解为2.0102>2