《数学计算方法线性方程组解法学习教案.pptx》由会员分享，可在线阅读，更多相关《数学计算方法线性方程组解法学习教案.pptx（122页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学计算方法数学计算方法(fngf)线性方程组解法线性方程组解法第一页，共122页。3.1 问题(wnt)的提出 第三章 线性方程组解法(ji f)第1页/共122页第二页，共122页。n阶线性方程组3.1 问题(wnt)的提出第2页/共122页第三页，共122页。3.1 问题(wnt)的提出线性方程组Ax=b，其中A是n维方阵，x是n维未知数向量(xingling)，b是n维常数向量(xingling)。第3页/共122页第四页，共122页。3.1 问题(wnt)的提出如果(rgu)A是非奇异阵时，方程组有唯一解，且可以用克莱姆(Grammer)法则表示:其中xi是解向量x*的第i个分量(f
2、n ling)，D=detA,Di是用b代替A的第i列后得到矩阵的行列式。第4页/共122页第五页，共122页。3.1 问题(wnt)的提出克莱姆方法求解(qi ji)计算量太大，需要计算(n+1)个n阶行列式，共需要(n+1)!次乘法运算。第5页/共122页第六页，共122页。3.1 问题(wnt)的提出 求解(qi ji)线性方程组的数值方法有两大类：1)直接法(direct methods)。经过有限次算术运算可求方程组精确解的方法(实际上，由于舍入误差不可避免，一般得不到精确解)。适合(shh)于求解低阶稠密阵方程组。第6页/共122页第七页，共122页。3.1 问题(wnt)的提出2
3、)迭代法(iterative methods)。采用极限过程去逐步逼近线性方程组精确解的方法。迭代法需要计算机存储单元较少，对计算机要求不高，程序设计简单(jindn)，但有收敛性和收敛速度方面的问题。迭代法是求解大型稀疏矩阵方程的重要方法。第7页/共122页第八页，共122页。3.1 问题(wnt)的提出 我们(w men)在本章将要学习迭代法有：雅可比(Jacobi)迭代法高斯(o s)塞德尔(Gauss-Seidel)迭代法超松弛迭代法(Successive overrelaxation method,SOR)。第8页/共122页第九页，共122页。3.1 问题(wnt)的提出追赶(zh
4、ugn)法(Forward elimination and backward substitution)。我们在本章将要学习(xux)直接解法有：高斯消去法(Gauss Elimination)，高斯主元素消去法(Gauss Elemination with pivoting),三角分解法(LU decomposition)，第9页/共122页第十页，共122页。3.1 问题(wnt)的提出第10页/共122页第十一页，共122页。【历史注记】线性代数方程组数值解法有着悠久的历史。我国古代(gdi)数学著作九章算术(公元1世纪)的“方程”章中就有了较好的线性方程组数值解法相当于现代对方程组的增
5、广矩阵进行初等变换、消去未知数的方法。中世纪的印度数学家也可以求解线性方程组。例如12世纪的婆什迦罗的著作中，也有求解线性方程组的内容。3.1 问题(wnt)的提出第11页/共122页第十二页，共122页。在欧洲，16世纪的比特奥在其算术（1559）中采用了与九章算术类似的消元法。日本数学家关孝和在其解伏题之法一书(1683)中首先采用了类似于现代行列式法求解了三元(sn yun)线性方程组。稍后，莱布尼茨提出关于行列式解线性方程组的思想(1693)。1721年马可劳林用行列式展开式的方法给出了二元、三元(sn yun)、四元线性方程组的解法，3.1 问题(wnt)的提出第12页/共122页第
6、十三页，共122页。但他的符号记法不完善。1750年，克莱姆给出了现在比较通用的线性方程组行列式解法，即克莱姆法则。1764年，贝祖用行列式建立(jinl)了线性方程组的一般理论。但由于当时计算的效率很低，这一理论几乎只有理论的意义，实际上只能求出未知数很少的线性代数方程组的解。只是在20世纪中叶电子计算机问世并投入应用之后，大型线性代数方程组的数值求解才成为可能。3.1 问题(wnt)的提出第13页/共122页第十四页，共122页。如何利用计算机更精确、更有效地求解大型线性方程组，是计算数学中最重要的课题之一。现代计算实践中，常用的线性代数方程组数值解法有直接法和迭代法两大类。直接法是在没有
7、舍入误差的假设下，经过有限次运算就可得出方程组的精确解的方法，如各种消元法。迭代法则采用(ciyng)逐次逼近的方法,即从一个初始值出发，按照一定的计算格式(迭代公式)，构造一个向量的无穷序列，其极限才3.1 问题(wnt)的提出第14页/共122页第十五页，共122页。是方程组的精确解，用有限次运算得不到精确解。迭代法是牛顿最先提出(t ch)来的，1940年经司威尔提出(t ch)的松弛法也是一种迭代法，共轭梯度法则是另一种迭代法，是弗莱彻等人于20世纪60年代提出(t ch)来的。3.1 问题(wnt)的提出第15页/共122页第十六页，共122页。例3.13.1 问题(wnt)的提出精
8、确解为将方程(fngchng)写为取第16页/共122页第十七页，共122页。3.1 问题(wnt)的提出重复(chngf)以上过程得k0123456x(k)01.62.122.0241.99281.998562.000432y(k)0-1.3-1.06-0.982-0.9964-1.00108-1.000216第17页/共122页第十八页，共122页。3.1 问题(wnt)的提出如果(rgu)把原方程写为构造(guzo)k0123x(k)08.66735.335-109.126y(k)04.0-17.668-84.358第18页/共122页第十九页，共122页。3.1 问题(wnt)的提出例
9、3.2 构造(guzo)第19页/共122页第二十页，共122页。3.1 问题(wnt)的提出得 第20页/共122页第二十一页，共122页。3.1 问题(wnt)的提出构造(guzo)由原方程(fngchng)第21页/共122页第二十二页，共122页。3.1 问题(wnt)的提出得第22页/共122页第二十三页，共122页。3.1 问题(wnt)的提出 如果A非奇异(qy)，则线性方程组Ax=b有唯一解x*，将上式化为x=Bx+f，给出初始向量x0，则有：！xk+1=Bxk+f,k=0,1,2可以构成一向量(xingling)序列xk，若向量(xingling)序列xk收敛于x*，则x*=
10、Bx*+f,即x*是方程组的解。这种方法称为迭代法,B称为迭代矩阵。第23页/共122页第二十四页，共122页。3.1 问题(wnt)的提出 构造迭代法的中心问题是建立一个由本次近似值计算下一次近似值的规则(guz)。用迭代法求解线性方程组时要解决的问题有：1)构造(guzo)一种迭代格式，由xk计算xk+1 3)证明向量序列xk的收敛性 2)给出初始向量x04)如果序列收敛，证明是原方程组的解 5)给出估计误差和迭代停止判据。第24页/共122页第二十五页，共122页。3.1 问题(wnt)的提出v 定义：在n维空间中给定一个向量序列(xli)，如果对每一个分量 ,当 时都有极限xi,即 ,
11、则称向量序列(xli)有极限 ,或称 收敛于x。第25页/共122页第二十六页，共122页。3.2 雅可比迭代(di di)(Jacobi iteration)第五章 线性方程组解法(ji f)第26页/共122页第二十七页，共122页。3.2 雅可比迭代(di di)最简单(jindn)的迭代方法是从第i个方程解出未知数xi，i=1,2,n 于是(ysh)雅可比迭代式为 第27页/共122页第二十八页，共122页。把系数矩阵(j zhn)分解为A=U+D+L，其中U为由A上三角部分构成的上三角阵，L为由A下三角元素构成的下三角阵，D为由A对角线元素构成的对角阵。3.2 雅可比迭代(di di
12、)显然，所有aii,i=1,2,n不为零上式才有意义，从线性代数知，对于任何系数方阵非奇异的方程组，通过适当交换方程的顺序总可以使所有方程的第28页/共122页第二十九页，共122页。3.2 雅可比迭代(di di)第29页/共122页第三十页，共122页。于是(ysh)原方程组为(U+D+L)x=b3.2 雅可比迭代(di di)上式两边(lingbin)左乘D-1得 x=D-1 b-D-1(U+L)x=Bx+f其中 B=-D-1(U+L),f=D-1b于是有迭代格式 xk+1=Bxk+f第30页/共122页第三十一页，共122页。例3.3 用Jacobi迭代格式(g shi)解下面方程组。
13、3.2 雅可比迭代(di di)解：Jacobi迭代(di di)格式为 第31页/共122页第三十二页，共122页。3.2 雅可比迭代(di di)取初始(ch sh)向量x(0)=(0,0,0)T，各次迭代结果k0123456x1(k)0.00000.12500.25000.22630.22350.22510.2250 x2(k)0.00000.40000.31500.30050.30600.30580.3056x3(k)0.0000-0.6000-0.4950-0.4870-0.4946-0.4941-0.4948第32页/共122页第三十三页，共122页。3.3 高斯(o s)塞德尔迭
14、代(Gauss-Seidel iteration)第五章 线性方程组解法(ji f)第33页/共122页第三十四页，共122页。在雅可比迭代(di di)中,计算第k+1次迭代(di di)近似值时用的是上一次即第k次的近似值，从式 3.3 高斯(o s)塞德尔迭代可以看出，在计算第i个xik+1分量时，前面(qin mian)i-1个分量x1k+1,x2k+1 xi-1k+1已经从上式中计算出来了，于是很自然会想到如果把它们代入用来计算xik+1可能会改进迭代,于是就得到Gauss-Seidel迭代格式：第34页/共122页第三十五页，共122页。写成矩阵(j zhn)形式为：3.3 高斯(
15、o s)塞德尔迭代或如果(rgu)(D+L)-1存在，则 第35页/共122页第三十六页，共122页。其中(qzhng)3.3 高斯(o s)塞德尔迭代【注记】通常高斯塞得尔方法比雅可比方法有更快的收敛速度，但不是总这样，对于某些方程组，雅可比迭代收敛，而高斯塞得尔方法发散(fsn)。即，并不是任何时候高斯塞得尔方法都比雅可比方法好。第36页/共122页第三十七页，共122页。例3.4 用Gauss-Seidel迭代格式解下面方程组，精确(jngqu)到3位有效数。3.3 高斯(o s)塞德尔迭代解：Gauss-Seidel迭代格式(g shi)如下第37页/共122页第三十八页，共122页。
16、3.3 高斯(o s)塞德尔迭代取初始(ch sh)近似值x0=(0,0,0)T，各次迭代结果k01234xk10.00000.12500.23440.22450.2250 xk20.00000.37500.30310.30590.3056xk30.0000-0.5000-0.4925-0.4939-0.4936第38页/共122页第三十九页，共122页。3.4 逐次(zh c)超松弛迭代法(SOR)(Successive Overrelaxation Method)第五章 线性方程组解法(ji f)第39页/共122页第四十页，共122页。逐次超松弛迭代简称(jinchng)SOR方法，是高
17、斯塞得尔法的一种加速方法。3.4 逐次(zh c)超松弛迭代法高斯塞得尔法迭代(di di)格式得到 把xik+1改进为xik与 的加权平均，即 第40页/共122页第四十一页，共122页。3.4 逐次(zh c)超松弛迭代法 上式中 时,就是高斯塞得尔方法，为保证迭代过程收敛,要求 当 时叫低阶松弛法；当 时叫超松弛法。SOR方法收敛时，希望选择一个最佳的使收敛速度最快。目前还没有最佳松弛因子 的一般算法理论，实际大都由计算经验通过试算确定 的近似值 第41页/共122页第四十二页，共122页。超松弛(sn ch)迭代式的矩阵形式 3.4 逐次(zh c)超松弛迭代法1)直接(zhji)由分
18、量形式公式写 由有所以第42页/共122页第四十三页，共122页。(证明(zhngmng)3.4 逐次(zh c)超松弛迭代法第43页/共122页第四十四页，共122页。2)由高斯(o s)塞德尔公式推导。3.4 逐次(zh c)超松弛迭代法高斯塞德尔迭代公式(gngsh)的矩阵形式是 加权平均第44页/共122页第四十五页，共122页。(证明(zhngmng)3.4 逐次(zh c)超松弛迭代法第45页/共122页第四十六页，共122页。3.5 迭代法的收敛性(convergence)第五章 线性方程组解法(ji f)第46页/共122页第四十七页，共122页。v 矩阵(j zhn)的特征值
19、 的绝对值最大值称为矩阵(j zhn)A的谱半径，即 3.5 迭代法的收敛性 定理(迭代法基本定理)：设有方程组x=Bx+f，对于任意初始向量x0及任意f，迭代公式xk+1=Bxk+f收敛的充要条件是 第47页/共122页第四十八页，共122页。3.5 迭代法的收敛性 定理(迭代收敛的充分条件)：设有迭代式xk+1=Bxk+f，如果 ，则对于任意初始向量x0，这个迭代过程收敛于方程组x=Bx+f的唯一解x*，并且有事后估计 以及事前(shqin)估计 第48页/共122页第四十九页，共122页。3.5 迭代法的收敛性v定义：如果对于方阵 ，有 则称方阵(fn zhn)对角占优。第49页/共12
20、2页第五十页，共122页。定理：如果方程组Ax=b的系数(xsh)阵对角占优，则方程组有唯一解且对任意初始向量x0雅可比迭代和高斯塞德尔迭代都收敛于真解。？、3.5 迭代法的收敛性【思考题3.1】如何对方程组进行调整，使用(shyng)Gauss-Seidel迭代格式求解时收敛？第50页/共122页第五十一页，共122页。定理：如果方程组Ax=b的系数阵对称(duchn)正定，则方程组有唯一解且对任意初始向量x0高斯塞德尔迭代收敛于真解。3.5 迭代法的收敛性第51页/共122页第五十二页，共122页。Jacobi迭代(di di)格式的收敛性3.5 迭代法的收敛性 Jacobi迭代(di d
21、i)矩阵 特征方程第52页/共122页第五十三页，共122页。3.5 迭代法的收敛性由于所以注意到所以，将A的对角线元素乘以 后取行列式，令其等于零，就是Jacobi迭代矩阵的特征方程。第53页/共122页第五十四页，共122页。例3.5 讨论用Jacobi迭代(di di)格式解方程组的收敛性。3.5 迭代法的收敛性解：Jacobi迭代(di di)矩阵的特征方程为第54页/共122页第五十五页，共122页。展开(zhn ki)得3.5 迭代法的收敛性Jacobi迭代(di di)格式收敛。解得第55页/共122页第五十六页，共122页。Gauss-Seidel迭代(di di)格式的收敛性
22、3.5 迭代法的收敛性 Gauss-Seidel迭代(di di)矩阵 特征方程第56页/共122页第五十七页，共122页。3.5 迭代法的收敛性由于所以注意到所以，将将A的对角线以下元素乘以的对角线以下元素乘以 后取后取行列式，令其等于零，就是行列式，令其等于零，就是Gauss-Seidel迭代矩阵的特征方程迭代矩阵的特征方程。第57页/共122页第五十八页，共122页。3.5 迭代法的收敛性【思考题3.2】Gauss-Seidel迭代(di di)矩阵至少(zhsho)有1个特征值为零，为什么？第58页/共122页第五十九页，共122页。例3.6 讨论(toln)用Gauss-Seidel
23、迭代格式解方程组的收敛性。3.5 迭代法的收敛性解：Gauss-Seidel迭代(di di)矩阵特征方程为第59页/共122页第六十页，共122页。展开(zhn ki)得3.5 迭代法的收敛性Gauss-Seidel迭代格式(g shi)收敛。解得第60页/共122页第六十一页，共122页。3.5 迭代法的收敛性!作业：(1)写出下面方程组的Jacobi迭代格式(g shi)和Gauss-Seidel迭代格式(g shi)的算法!(2)讨论它们的收敛性。第61页/共122页第六十二页，共122页。3.6高斯(o s)消去法(Gauss Elimination)第三章 线性方程组解法(ji f
24、)第62页/共122页第六十三页，共122页。高斯(o s)消去法是最古老的数值方法之一，现在仍然是一个很有用的方法，它在计算机上容易实现。3.6 高斯(o s)消去法 其基本思想是在各个方程之间进行乘法和加减(ji jin)运算，逐步消去方程中的未知数。它分为消去和回代两个过程。给定线性方程组第63页/共122页第六十四页，共122页。3.6 高斯(o s)消去法第一步消元，令 ，用 乘第一个方程再加到第i个方程上作为第i个新方程，消去x1的项，变为第64页/共122页第六十五页，共122页。逐次(zh c)进行同样过程，最后，经过n-1次消元，得到：3.6 高斯(o s)消去法第65页/共
25、122页第六十六页，共122页。以上(yshng)这些步骤叫消元过程。3.6 高斯(o s)消去法第66页/共122页第六十七页，共122页。然后(rnhu)，从第n个方程开始，依次解出 xn,xn-1,x1 3.6 高斯(o s)消去法第67页/共122页第六十八页，共122页。高斯(o s)消去法的计算量3.6 高斯(o s)消去法 消去过程的计算量。第一步计算乘数mi1,(i=2,3,n)需要i-1次除法运算，计算aij(2)(i,j=2,3,n)需要(i-1)2次乘法(chngf)运算以及(i-1)2次加减法运算。利用求和公式 得到第68页/共122页第六十九页，共122页。3.6 高
26、斯(o s)消去法第k步加减法次数乘法次数除法次数1(n-1)2(n-1)2n-12(n-2)2(n-2)2n-2N-1111合计n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2 于是消去过程乘除法次数为消去过程加减法次数为第69页/共122页第七十页，共122页。3.6 高斯(o s)消去法计算(j sun)b(n-1)的计算(j sun)量 乘除(chngch)法次数为 加减法次数为第70页/共122页第七十一页，共122页。3.6 高斯(o s)消去法回代计算(j sun)量 乘除(chngch)法次数为 加减法次数为第71页/共122页第七十二页，共122页。3
27、.6 高斯(o s)消去法总的计算(j sun)量 乘除(chngch)法次数为 加减法次数为第72页/共122页第七十三页，共122页。高斯(o s)消去法还有没有办法进行，为什么？3.6 高斯(o s)消去法【思考题3.3】如果(rgu)遇到!作业：写出高斯消去法的Fortran程序。第73页/共122页第七十四页，共122页。3.7高斯(o s)主元消去法(Gauss Elimination with pivoting)第三章 线性方程组解法(ji f)第74页/共122页第七十五页，共122页。3.7 高斯(o s)主元消去法 从高斯消去法我们已经看出，为使高斯消去法能顺利进行，必须在
28、每一步消去步都满足条件 ，但若相应的系数 计算可能引起(ynq)很大的舍入误差。第75页/共122页第七十六页，共122页。为此，需要(xyo)改进高斯消去法。有两种改进方法：列选主元，完全选主元。3.7 高斯(o s)主元消去法u列选主元u通过交换方程而使得(sh de)aki(i-1),k=i,i+1,n,中绝对值最大的一个换到(i,i)位置而成为第i步的消去主元。第76页/共122页第七十七页，共122页。u完全选主元法就是(jish)在系数矩阵的子块 中找出绝对值最大的元素，作为(zuwi)第k+1次消去过程的主元。3.7 高斯(o s)主元消去法第77页/共122页第七十八页，共12
29、2页。假设(jish)则k+1行与p行交换，第k+1列与第q列交换，右端也同时(tngsh)交换，在做列交换时，要注意未知量也作交换，即把xk+1与xp交换。3.7 高斯(o s)主元消去法第78页/共122页第七十九页，共122页。列选主元算法(sun f)：1.for k=1,2,n-1 2.找出满足 元素(yun s)的行位置p 3.if ,error,无唯一(wi y)解，stop error4.if()换行 5.for j=k,k+1,n 6.ak,j与ap,j交换 3.7 高斯主元消去法第79页/共122页第八十页，共122页。7.bk与bp交换(jiohun)8.Endfor9.
30、Endif 消去计算(j sun)：10.Endfor3.7 高斯(o s)主元消去法第80页/共122页第八十一页，共122页。回代计算(j sun)：11.for i=n-1,n-2,2,1 12.Endfor 3.7 高斯(o s)主元消去法第81页/共122页第八十二页，共122页。3.8 三角(snjio)分解法(LU decomposition)第三章 线性方程组解法(ji f)第82页/共122页第八十三页，共122页。高斯(o s)消去法 3.7 三角(snjio)分解法第一次消元过程(guchng)为 用-mi1乘上面第一个方程再加到第i个方程，即可消去第i个方程中的未知量x
31、1。这个过程实际上是给系数矩阵A左乘这样一个下三角阵L1：第83页/共122页第八十四页，共122页。作第二次消元相当于给系数矩阵A(1)左乘了一个(y)下三角阵L2：3.7 三角(snjio)分解法第84页/共122页第八十五页，共122页。作第k次消元相当于系数矩阵(j zhn)A(k-1)左乘一个下三角阵Lk3.7 三角(snjio)分解法第85页/共122页第八十六页，共122页。3.7 三角(snjio)分解法第86页/共122页第八十七页，共122页。于是(ysh)第n-1次消元过程可表示为：于是(ysh)下三角(snjio)阵乘积也是一个下三角(snjio)阵。记3.7 三角分解
32、法第87页/共122页第八十八页，共122页。L是单位下三角阵(即对角(du jio)元素全为1的下三角阵)。3.7 三角(snjio)分解法第88页/共122页第八十九页，共122页。叫矩阵(j zhn)A的三角分解，或LU分解。如果L为单位下三角阵，则叫Doolittle分解，若U为单位上三角阵，则叫Crout分解。只要A的各顺序(shnx)主子式不为零，则A可唯一分解成一个单位下三角阵L与一个上三角阵U的乘积。3.7 三角(snjio)分解法第89页/共122页第九十页，共122页。设Ax=b，A=LU，则Ax=LUx=b于是(ysh)令Ux=y，则Ly=b3.7 三角(snjio)分解
33、法第90页/共122页第九十一页，共122页。这样原来(yunli)方程能化为两个简单方程组由 求y然后由 求x3.7 三角(snjio)分解法第91页/共122页第九十二页，共122页。现在(xinzi)显式地给出lij和uij的表达式 从第一行可以(ky)看出，u1j=a1j,j=1,2,n3.7 三角(snjio)分解法从第一列可以看出 ai1=li1u11,i=2,3,n,即li1=ai1/u11,i=2,3,n。第92页/共122页第九十三页，共122页。从第二行可以(ky)看出，a2j=l21u1j+u2j,j=2,3,n，则u2j=a2j-l21u1j,j=2,3,n 从第二列可
34、以(ky)看出，ai2=li1u12+li2u22,i=2,3,n，则li2=(ai2-li1u12)/u22,i=2,3,n3.7 三角(snjio)分解法第93页/共122页第九十四页，共122页。一般(ybn)地，如果U的前k-1行，L的前k-1行已经求出，则第k(k=2,3,n)步(行)3.7 三角(snjio)分解法第94页/共122页第九十五页，共122页。(列)直到(zhdo)第n步，A全部分解成LU。3.7 三角(snjio)分解法第95页/共122页第九十六页，共122页。3.9 追赶(zhugn)法(Forward elimination and backward subs
35、titution)第三章 线性方程组解法(ji f)第96页/共122页第九十七页，共122页。在很多实际问题中，方程组Ax=b的系数(xsh)矩阵A是一个稀疏矩阵。3.6 追赶(zhugn)法第97页/共122页第九十八页，共122页。假设(jish)非零元素集中分布在对角线及其相邻两个次对角线上，且系数阵为对角占优阵，即有：3.6 追赶(zhugn)法第98页/共122页第九十九页，共122页。把系数矩阵(j zhn)三角分解有3.6 追赶(zhugn)法第99页/共122页第一百页，共122页。利用(lyng)LU分解公式，写出3.6 追赶(zhugn)法第100页/共122页第一百零一
36、页，共122页。得到 于是 得到(d do)3.6 追赶(zhugn)法第101页/共122页第一百零二页，共122页。3.6 追赶(zhugn)法第102页/共122页第一百零三页，共122页。3.10 其它(qt)应用第三章 线性方程组解法(ji f)第103页/共122页第一百零四页，共122页。计算(j sun)行列式值3.6 其他(qt)应用 求矩阵(j zhn)逆第104页/共122页第一百零五页，共122页。分别(fnbi)由 解出 xij,ij=1,2,n 于是3.6 其他(qt)应用第105页/共122页第一百零六页，共122页。3.11 误差(wch)分析(Error an
37、alysis)第三章 线性方程组解法(ji f)第106页/共122页第一百零七页，共122页。3.6 误差(wch)分析v 定义：设 为方程组Ax=b的精确解，近似解与精确解之间的误差向量定义为 第107页/共122页第一百零八页，共122页。一种衡量(hng ling)近似解精确度的方法是把近似解 代入方程组，看残差向量的大小。于是3.6 误差(wch)分析第108页/共122页第一百零九页，共122页。由范数性质(xngzh)有 而上面两个(lin)式子相乘得3.6 误差(wch)分析第109页/共122页第一百一十页，共122页。这个式子左端计算的是近似解x的相对误差，而 是相对残差。
38、近似解的相对误差小于相对残差的一个倍数：。这个倍数对于近似解的误差估计很重要，定义为矩阵A的条件数 3.6 误差(wch)分析第110页/共122页第一百一十一页，共122页。线性方程组Ax=b的解x*是由系数矩阵A和向量b决定的，那么如果A和b有微小的变化(binhu)(扰动)时，解会如何变化(binhu)呢？(1)假设b有微小变化 ，此时解有变化 ，即注意(zh y)到3.6 误差(wch)分析第111页/共122页第一百一十二页，共122页。于是(ysh)即两边(lingbin)取范数得利用(lyng)得3.6 误差分析第112页/共122页第一百一十三页，共122页。(2)假设A有微小
39、变化 ，此时解有变化 ，即整理并注意到 得即两边(lingbin)取范数得3.6 误差(wch)分析第113页/共122页第一百一十四页，共122页。即于是从(1),(2)两种情况可以看出，如果b或者A有误差，则解的相对误差不超过它们相对误差的 倍。3.6 误差(wch)分析第114页/共122页第一百一十五页，共122页。Remark:条件数刻画了线性方程组的解对于初始数据(b,A)误差的灵敏度，条件数是方程组的固有属性，与求解该方程组的方法无关。对于病态方程组，一般不能得到令人满意(ln rn mn y)的结果。3.6 误差(wch)分析定义 为线性方程组的条件数 第115页/共122页第
40、一百一十六页，共122页。当 时，方程“病态”。通常使用(shyng)的条件数有 其中 是ATA的绝对值最大、最小的特征值。3.6 误差(wch)分析第116页/共122页第一百一十七页，共122页。当A对称(duchn)时 是A的最大特征值，是 A的最小特征值。3.6 误差(wch)分析第117页/共122页第一百一十八页，共122页。Remark:为了计算(j sun)方程组的条件数，需要计算(j sun)矩阵A的逆阵，求逆阵的工作量很大，而且，如果A是病态时，其逆阵的计算(j sun)也不准确。(2)系数(xsh)阵某些行(列)近似线性相关3.6 误差(wch)分析 判断方程组病态的参考：(1)用选主元消去法求解时出现小主元 (3)系数阵元素量级相差很大,且无规则第118页/共122页第一百一十九页，共122页。本章(bn zhn)小结第三章 线性方程组解法(ji f)第119页/共122页第一百二十页，共122页。3.6 小结(xioji)迭代法：雅克比迭代法高斯(o s)塞德尔迭代法超松弛(sn ch)迭代法SOR。第120页/共122页第一百二十一页，共122页。追赶(zhugn)法。直接(zhji)解法：高斯(o s)消去法高斯主元素消去法三角分解法LU 其它应用条件数3.6 小结第121页/共122页第一百二十二页，共122页。