第三章线性方程组的迭代解法省公共课一等奖全国赛课获奖课件

第三章线性方程组解法

思绪与解f(x)=0不动点迭代相同……，将等价改写为形式，建立迭代。从初值出发，得到序列。求解，有迭代法和直接法先介绍迭代法第1页§3.1雅可比(Jacobi)迭代法其中是迭代初值。第2页写成矩阵形式：A=LUD写成迭代法形式B称为Jacobi迭代阵即其中第3页…………写成矩阵形式：BGauss-Seidel迭代阵§3.2高斯-赛德尔(Gauss-Seidel)迭代法第4页例3.2.1用Gauss-Seidel迭代法求解方程组取初始向量,要求时迭代终止。解：Gauss-Seidel迭代格式为:第5页计算结果可列表以下第6页注：1.未必Seidel方法一定比Jacobi方法好。2.二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。第7页残余误差§3.3超松弛迭代法ri(k+1)=下面令，希望经过选取适当

来加速收敛，这就是松弛法（或SOR法）。

称作松弛因子。iikikikiarxx)1()()1(+++=w0<

<1低松弛法

=1Gauss-Seidel法1<<2(渐次)超松弛法第8页写成矩阵形式：松弛迭代阵

（Kahan必要条件）设A可逆，且aii0，则松弛法从任意出发都收敛

0<

<2。定理3.3.1证实：省略第9页§3.4迭代法收敛性收敛条件设存在唯一解，则从任意出发，迭代收敛

(B)<1定理3.4.1(迭代法基本定理)第10页①②

（充分条件）若存在一个矩阵范数使得||B||=q<1,则迭代收敛，且有以下误差预计：定理3.4.2第11页证实：省略。

（充分条件）若A为严格对角占优阵,则解Jacobi和Gauss-Seidel迭代均收敛。定理3.4.3定义3.4.1设A=(aij)n

n,

假如即主对角线上元素绝对值大于同行其它元素绝对值之和，那么称矩阵A是严格对角占优阵。第12页§3.5高斯消去法或叫高斯消元法，是一个古老求解线性方程组直接法。思绪首先经过消元将A化为上三角阵，再回代求解。=消元记第13页第一步：设，计算因子将增广矩阵第i行

mi1

第1行，得到其中第k步：设，计算因子且计算共进行？步n

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

1:其中Lk=第20页单位下三角阵记为L记

U=称为A

LU

分解第21页若A全部次序主子式均不为0，则A

LU

分解唯一（其中L为单位下三角阵，这种分接称为道立特(Doolittle)分解法）。定理3.7.1

为何要讨论三角分解？若在消元法进行前能实现三角分解A=LU,则轻易回代求解第22页回代求解很轻易，如

第23页＝经过比较法直接导出L和U计算公式。思绪因为L第i行只有前i个元素不为0，而U第j列只有前j个元素不为0，故第24页由矩阵乘法………第25页分别固定i＝1,…,n:对j=i,i+1,…,n有lii=1将i，j对换，对j=i,i+1,…,n有DooLittle分解公式：第26页§3.8追赶法（解三对角方程组）利用高斯消去法，经过n-1次消元，可将它化为同解方程组第27页易知求这些值过程(即消元过程)称为追。再利用回代过程求出方程组各变量。这一逆序求变量过程(即回代过程)称为赶。第28页§3.10(线性方程组)误差分析

求解时，A和误差对解有何影响？

设A准确，有误差，得到解为，即绝对误差放大因子又相对误差放大因子第29页(只要A充分小，使得(I+A

1A)一定可逆吗?

设准确，A有误差，得到解为，即是关键误差放大因子，称为A条件数，记为cond(A),此数越则A越病态，越难得准确解。大第30页注:

cond(A)详细大小与||·||取法相关，但相对大小一致。

cond(A)取决于A，与解题方法无关。

惯用条件数有：cond(A)1cond(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。第31页准确解为例3.10.1：计算cond(A)2。A1=解：考查A特征值39206>>1

测试病态程度：给一个扰动，其相对误差为此时准确解为2.0102>200%第32页注：普通判断矩阵是否病态，并不计算A1，而由经验得出。

行列式很大或很小（如一些行、列近似相关）；

元素间相差大数量级，且无规则；

主元消去过程中出现小主元；

特征值相差大数量级。