《地球物理计算方法第一章ppt课件.ppt》由会员分享，可在线阅读，更多相关《地球物理计算方法第一章ppt课件.ppt（151页珍藏版）》请在三一办公上搜索。
1、第一章线性方程组的数值解法,2/47,本章内容,1.1 引言1.2 高斯消去法1.3 选主元素的高斯消去法1.4 矩阵的三角分解1.5 解三对角线方程组的追赶法1.6 解对称正定矩阵方程组的平方根法1.7 向量和矩阵的范数1.8 解线性方程组的迭代法1.9 病态方程组和迭代改善法,3/47,本章要求,1. 理解高斯消去法的基本原理，熟练掌握高斯主元消去法；2. 理解矩阵的三角分解；3. 掌握解三对角线方程组的追赶法，掌握平方根法；4. 了解矩阵范数、条件数。5. 熟悉简单迭代法及其收敛条件的使用;6. 熟悉Jacobi迭代法及其相应的Seidel迭代法的计算公式以及它们的收敛条件;7. 熟悉S
2、OR方法的计算公式及其收敛条件。,4/47,1.1 引言,本节内容一. 线性方程组解法二. 直接法与迭代法比较,5/47,1.1 引言,一. 线性方程组解法工程中几乎有一半的问题涉及到线性方程组的求解设 n 阶线性方程组,6/47,1.1 引言,A 称为方程组的系数矩阵，当是 n 阶非奇异矩阵时，既 A 0，此时方程组有唯一解。 X 阵是解向量，B 阵是常向量。 在线性代数中学过用克莱姆法则求解，它是一种直接法(属于解析法)，但随着n计算工作量,7/47,1.1 引言,自学并理解,8/47,1.1 引言,二. 直接法与迭代法比较各有优缺点解方程组的数值解法：直接法与迭代法优缺点比较直接法：经有
3、限次计算得准确解(在无舍入误差下),实际上舍入误差客观存在, 得到的依然还是近似解。由于受到计算机存储容量的限制，一般来说，仅适于系数矩阵阶数不太高的问题，其工作量(计算量)较小、精度较高，但程序设计复杂。迭代法将问题构成一个无穷序列，逼近准确解。主要用于某些系数矩阵阶数较高的问题，一般来说，程序较为简单、易于编程，但存在收敛性及收敛速度的问题，只对具有某些性质的系数矩阵的方程组才适用。工作量有时较大。,9/47,1.1 引言,实际计算时，应根据问题的特点和要求来决定方法的取舍。本章介绍的求解线性代数方程组的直接法有Gauss(高斯) 消元法和LU分解等；迭代法有Jacobi(雅可比)迭代和G
4、auss-Seidel(高斯-赛德尔)迭代。,10/47,1.2 高斯消去法,本节内容一. 引言二. 例子三. 顺序Gauss消去法四. Gauss消去法计算量返回章节目录,顺序高斯消去法,11/47,一. 引言是一个古老的求解线性方程组的方法。改进和变形得到高斯选主元素消去法（第3节）、三角分解法（第4节）n 元线性方程组 的直接解法。,1.2 高斯消去法,（式1）,12/47,方程组(1)的矩阵形式为 Ax=b 其中,1.2 高斯消去法,13/47,线性代数：方法不好时工作量非常大， 工作量小的方法是 Gauss 消去法。,Cramer法则是一种不实用的直接法，本章介绍几种实用的直接法。
5、Gauss消去法是一种规则化的加减消元法，其基本思想是通过逐次消元计算，把一般线性方程组的求解转化为等价的上三角形方程组的求解。,1.2 高斯消去法,14/47,二. 例子为清楚起见，先看一简单 例子。考虑线性方程组,1.消去后两个方程中的x1得：,2.再消去最后一个方程的x2得：,3.消元结束,经过回代得解:,1.2 高斯消去法,15/47,上述求解的消元过程可用矩阵表示为: 这是高斯消去法的计算形式,新的增广矩阵对应的线性方程组就是上三角形方程组,可进行回代求解,1.2 高斯消去法,16/47,三. 求解线性方程组(1)的顺序Gauss消去法 记 则,线性方程组(1)的增广矩阵为,1.2
6、高斯消去法,17/47,1.2 高斯消去法,18/47,1.2 高斯消去法,19/47,1.2 高斯消去法,20/47,（式2）,1.2 高斯消去法,（式3）,21/47,1.2 高斯消去法,22/47,结论： （1）高斯消去法分消元、回代两过程。 （2）从矩阵分解角度看： 消去是解一个下三角方程组， 回代是解一个上三角方程组。 （3）消去法顺利进行必须满足 akk (k) 0,(k=1,2,n)， 若出现akk (k) =0，则 可交换行列后再进行消元。,1.2 高斯消去法,23/47,1.2 高斯消去法,四. Gauss消去法计算量,(n-k),(n-k)2,24/47,1.2 高斯消去法
7、,25/47,1.2 高斯消去法,乘除法耗时大大多于加减法耗时，故高斯消元法的计算量为O(n3)。n=20时,顺序Gauss消去法只需3060次乘除法运算。顺序Gauss消去法通常也简称为Gauss消去法。,26/47,1.2 高斯消去法,27/47,1.3 选主元素的高斯消去法,本节内容一. 问题提出二. 选主元素消去法三. 高斯列主元消去法N-S图四. 高斯-约当消去法返回章节目录,28/47,一. 问题提出,1.3 选主元素的高斯消去法,29/47,1.3 选主元素的高斯消去法,例1：单精度解方程组,精确解为 和,8个,8个,用Gauss消去法计算：,8个,小主元 /* Small pi
8、vot element */ 可能导致计算失败。,30/47,1.3 选主元素的高斯消去法,例2： 解线性方程组（用4位十进制浮点计算）,用Cramer法则可得精度较高的解（精确解） x1* = 1.00010，x2* = 0.99990,31/47,解 用顺序Gauss消去法, 消元得,回代得解：x1=0.00，x2=1.00与精确解相比，该结果相当糟糕原因是：在求行乘数时用了很小的数0.0001作除数,主元,9999,1.3 选主元素的高斯消去法,32/47,用顺序Gauss消去法, 消元得,回代得解：x1=1.00，x2=1.00,若将方程组改写成（将1,2行交换）:,这是一个相当不错的
9、结果,0.9999,1.3 选主元素的高斯消去法,33/47,例3：解线性方程组(用8位十进制尾数的浮点数计算),解：这个方程组和例2一样，若用Gauss消去法计算会有小数作除数的现象，若采用换行的技巧，则可避免,1.3 选主元素的高斯消去法,34/47,绝对值最大,不需换行,1.3 选主元素的高斯消去法,35/47,1.3 选主元素的高斯消去法,36/47,1.3 选主元素的高斯消去法,二. 选主元素消去法,37/47,1.3 选主元素的高斯消去法,38/47,给定线性方程组Ax=b，记A(1)=A，b(1)=b，列主元Gauss消去法的具体过程如下： 首先在增广矩阵B(1)=(A(1),b
10、(1)的第一列元素中，取 然后进行第一步消元得增广矩阵B(2)=(A(2),b(2)。 再在矩阵B(2)=(A(2),b(2)的第二列元素中，取 然后进行第二步消元得增广矩阵B(3)=(A(3),b(3)。按此方法继续进行下去, 经过n-1步选主元和消元运算,得到增广矩阵B(n)=(A(n),b(n).则方程组A(n)x=b(n)是与原方程组等价的上三角形方程组,可进行回代求解. 易证，只要|A|0,列主元Gauss消去法就可顺利进行。,1.3 选主元素的高斯消去法,39/47,方程组具有四位有效数字的精确解为 x1*=17.46，x2*=-45.76，x3*=5.546,例4 采用4位十进制
11、浮点计算,分别用顺序Gauss消去法和列主元Gauss消去法求解线性方程组:,1.3 选主元素的高斯消去法,40/47,解 1. 用顺序Gauss消去法求解，消元过程为,回代得： x3=5.546，x2=100.0，x1=-104.0,1.3 选主元素的高斯消去法,41/47,2. 用列主元Gauss消去法求解，消元过程为,1.3 选主元素的高斯消去法,42/47,回代得：x3=5.545，x2=-45.77，x1=17.46,1.3 选主元素的高斯消去法,43/47,列主元Gauss消去法是在每一步消元前，在主元所在的一列选取绝对值最大的元素作为主元素。而全主元Gauss消去法是在每一步消元
12、前，在所有元素中选取绝对值最大的元素作为主元素。但由于运算量大增，实际应用中并不经常使用。,1.3 选主元素的高斯消去法,44/47,三. 高斯列主元消去法N-S图,消元次数 K=1,k=n ?,选列主元 amk,|amk| eps,N,rm rk,进行第k步消元,输出方程组的解X,建立增广矩阵A(n,n+1),m=k,Y,N,Y,k=k+1,回代求解,停止,1.3 选主元素的高斯消去法,45/47,四. 高斯-约当消去法（Gauss-Jordan）这是一种无回代的方法，使计算工作量减小，在第k次消元时不仅把akk(k) 化成1，不仅将aik（i=k+1，n）化成0，而且也将aik（i=1，2
13、，k-1）也化为0，最后消元过程结束时的系数矩阵为,得消元公式 akj (k)=akj(k-1)/akk(k-1) （j=1,2,n+1） aij (k)= aij (k)- aik(k-1)akj(k) （i k,i=1,2,n，j=1,2,n+1）,自学了解,1.3 选主元素的高斯消去法,46/47,1.4 矩阵的三角分解,本节内容一. Gauss消去法的矩阵表示二. Doolittle分解法返回章节目录,47/47,1.4 矩阵的三角分解,一. Gauss消去法的矩阵表示对矩阵,48/47,1.4 矩阵的三角分解,49/47,1.4 矩阵的三角分解,50/47,1.4 矩阵的三角分解,5
14、1/47,也就是： A(n)=Ln-1A(n-1) =Ln-1Ln-2A(n-2) = Ln-1Ln-2L2L1A(1) 其中：,所以有： A=A(1) = L1-1L2-1Ln-1-1A(n) = LU 其中： L=L1-1L2-1Ln-1-1, U=A(n),1.4 矩阵的三角分解,52/47,L称为单位下三角矩阵;U是上三角矩阵.,式 A=LU称为矩阵A的三角分解。,1.4 矩阵的三角分解,53/47,二、Doolittle分解法,定理2： 设n阶方阵A的各阶顺序主子式不为零,则存在唯 一单位下三角矩阵L和上三角矩阵U使A=LU。 证明 只证唯一性, 设有两种分解 则有 所以得 于是 A
15、x=b LUx=b 令 Ux=y 得,1.4 矩阵的三角分解,54/47,K=1,1.4 矩阵的三角分解,55/47,对K=2,3,n 计算（1）,求U的第i行元素,1.4 矩阵的三角分解,56/47,对K=2,3,n 计算（2）,求L的第i列元素,1.4 矩阵的三角分解,57/47,1.4 矩阵的三角分解,58/47,1.4 矩阵的三角分解,59/47,这就是求解方程组Ax=b的Doolittle三角分解方法。,1.4 矩阵的三角分解,60/47,例 利用三角分解方法解线性方程组,解 因为,1.4 矩阵的三角分解,61/47,1.4 矩阵的三角分解,先解,得,再解,得,62/47,解线性方程
16、组 Ax=b 的 Doolittle 三角分解法的计算量约为 1/3n3, 与 Gauss 消去法基本相同。其优点在于求一系列同系数的线性方程组 Ax=bk , (k=1,2,m) 时, 可大大节省运算量。,例如, 求上例中矩阵A的逆矩阵。可分别取常向量 b1=(1,0,0)T, b2=(0,1,0)T, b3=(0,0,1)T,1.4 矩阵的三角分解,63/47,1.4 矩阵的三角分解,64/47,为了提高数值稳定性, 可考虑列主元三角分解法, 设已完成A=LU的k-1步分解计算, 矩阵分解成,1.4 矩阵的三角分解,65/47,1.4 矩阵的三角分解,66/47,6.4 矩阵的三角分解,例
17、如，用列主元三角分解解上例中方程组。则有,67/47,1.5 解三对角线方程组的追赶法,本节内容一. 三对角线矩阵二. Crount分解三. 例返回章节目录,68/47,一. 有一类方程组，在插值问题和边值问题中有着重要的作用，即三对角线方程组，其形式为：,1.5 解三对角线方程组的追赶法,对角元,前次对角线,后次对角线,69/47,1.5 解三对角线方程组的追赶法,70/47,1.5 解三对角线方程组的追赶法,前面已经讲过,71/47,1.5 解三对角线方程组的追赶法,注意：和教材上字母不同,72/47,1.5 解三对角线方程组的追赶法,73/47,1.5 解三对角线方程组的追赶法,74/4
18、7,追，相当于消元过程,1.5 解三对角线方程组的追赶法,75/47,式1 式3 叫追赶法，也称Thomas法。工作量小，非常有效。,赶，相当于回代过程,1.5 解三对角线方程组的追赶法,76/47,5.7 解三对角线方程组的追赶法,77/47,5.7 解三对角线方程组的追赶法,78/47,当满足条件 |a1|c1|0； |an|dn|0； |ai|ci|+|di|，cidi 0，i=2,3,n-1。时，追赶法是数值稳定的追赶法具有： 计算程序简单， 存贮量少， 计算量小的优点。,1.5 解三对角线方程组的追赶法,79/47,1.6 解对称正定矩阵方程组的平方根法,本节内容一. 对称正定矩阵二
19、. 平方根法乔来斯金分解三. LDLT分解返回章节目录,80/47,1.6 解对称正定矩阵方程组的平方根法,81/47,1.6 解对称正定矩阵方程组的平方根法,对称正定阵的几个重要性质,(2)A 的顺序主子阵 Ak 亦对称正定,(3)A 的特征值 i 0,(1)A1 亦对称正定，且 aii 0,(4)A 的全部顺序主子式 det ( Ak ) 0,82/47,1.6 解对称正定矩阵方程组的平方根法,83/47,1.6 解对称正定矩阵方程组的平方根法,84/47,1.6 解对称正定矩阵方程组的平方根法,85/47,1.6 解对称正定矩阵方程组的平方根法,86/47,1.6 解对称正定矩阵方程组的
20、平方根法,87/47,1.6 解对称正定矩阵方程组的平方根法,88/47,6.6 解对称正定矩阵方程组的平方根法,4/2=2,89/47,6.6 解对称正定矩阵方程组的平方根法,平方根法是求对称正定系数线性方程组的三角分解法，对称正定矩阵的 Cholesky 分解的计算量和存贮量均约为一般矩阵的 LU 分解的一半。且Cholesky 分解具有数值稳定性。,90/47,1.6 解对称正定矩阵方程组的平方根法,91/47,1.6 解对称正定矩阵方程组的平方根法,92/47,1.7 向量和矩阵的范数,本节内容一. 向量范数二. 矩阵范数三. 矩阵A的谱半径返回章节目录,93/47,1.7 向量和矩阵
21、的范数,94/47,1.7 向量和矩阵的范数,95/47,1.7 向量和矩阵的范数,96/47,1.7 向量和矩阵的范数,97/47,1.7 向量和矩阵的范数,98/47,1.7 向量和矩阵的范数,99/47,1.7 向量和矩阵的范数,100/47,1.7 向量和矩阵的范数,101/47,1.7 向量和矩阵的范数,102/47,6.7 向量和矩阵的范数,103/47,1.7 向量和矩阵的范数,104/47,1.7 向量和矩阵的范数,105/47,1.8 解线性方程组的迭代法,本节内容一. 简单迭代法二. 雅可比(Jacobi)迭代法三. 塞德尔(Seidel)迭代法四. 逐次超松弛(SOR)迭
22、代法五. 例子返回章节目录,解大型稀疏线性方程组,106/47,1.8 解线性方程组的迭代法,一. 简单迭代法,107/47,1.8 解线性方程组的迭代法,一阶定常迭代法,108/47,特征值,谱半径,1.8 解线性方程组的迭代法,109/47,6.8 解线性方程组的迭代法,有兴趣同学自学,110/47,二. 雅可比(Jacobi)迭代法1. 迭代法,1.8 解线性方程组的迭代法,111/47,1.8 解线性方程组的迭代法,112/47,1.8 解线性方程组的迭代法,113/47,1.8 解线性方程组的迭代法,114/47,1.8 解线性方程组的迭代法,115/47,1.8 解线性方程组的迭代
23、法,2. 收敛性,范数,116/47,1.8 解线性方程组的迭代法,117/47,1.8 解线性方程组的迭代法,三. 塞德尔(Seidel)迭代法1. 迭代法1,118/47,1.8 解线性方程组的迭代法,119/47,1.8 解线性方程组的迭代法,2. 收敛性1,120/47,1.8 解线性方程组的迭代法,3. 迭代法2,121/47,1.8 解线性方程组的迭代法,122/47,1.8 解线性方程组的迭代法,4. 收敛性2,123/47,四. 逐次超松弛(SOR)迭代法1. 迭代法,1.8 解线性方程组的迭代法,124/47,1.8 解线性方程组的迭代法,2. 收敛性,125/47,1.8
24、解线性方程组的迭代法,五. 例子例1,126/47,1.8 解线性方程组的迭代法,127/47,6.8 解线性方程组的迭代法,可见，迭代序列逐次收敛于方程组的解，而且迭代7次得到精确到小数点后两位的近似解。,计算结果列表如下:,128/47,G-S迭代法的计算公式为:,1.8 解线性方程组的迭代法,129/47,同样取初始向量x(0)=(0,0,0)T，计算结果为：,由计算结果可见，G-S迭代法收敛较快.取精确到小数点后两位的近似解，G-S迭代法只需迭代 3 次，而J迭代法需要迭代 7 次。,1.8 解线性方程组的迭代法,130/47,1.8 解线性方程组的迭代法,131/47,例2 用J迭代
25、法求例1中方程组的解，取x(0)=(0,0,0)T，若使误差x(k)-x*10-5，问需要迭代多少次？,1.8 解线性方程组的迭代法,132/47,6.8 解线性方程组的迭代法,试建立一个收敛的迭代格式，并说明收敛性。,解 按如下方法建立迭代格式,由于迭代矩阵的行范数小于1，故此迭代法收敛。,例3 已知解线性方程组,133/47,6.8 解线性方程组的迭代法,例4 用SOR方法解线性方程组,解 SOR方法迭代公式为,方程组的精确解是 x*=(2,1,-1)T。,134/47,6.8 解线性方程组的迭代法,从结果可见，迭代 20 次时已获得精确到小数点后五位的近似解。如果取 =1.25，则需要迭
26、代 56 次才能得到具有同样精度的近似解；如果取 =1，则需迭代 110 次以上。,取x(0)=(0,0,0)T，=1.46,计算结果如下:,135/47,6.8 解线性方程组的迭代法,136/47,6.8 解线性方程组的迭代法,注意：未必Seidel方法一定比Jacobi方法好。,137/47,1.9 病态方程组和迭代改善法,本节内容一. 矩阵的条件数二. 误差分析返回章节目录,138/47,1.9 病态方程组和迭代改善法,一.矩阵的条件数,139/47,6.10 病态方程组和迭代改善法,140/47,6.10 病态方程组和迭代改善法,右端项b的扰动对解的影响,141/47,6.10 病态方程组和迭代改善法,系数矩阵A的扰动对解的影响,142/47,6.10 病态方程组和迭代改善法,条件数的定义,143/47,6.10 病态方程组和迭代改善法,条件数的性质,144/47,1.9 病态方程组和迭代改善法,145/47,1.9 病态方程组和迭代改善法,146/47,6.10 病态方程组和迭代改善法,147/47,1.9 病态方程组和迭代改善法,148/47,“病态”方程的经验判断,149/47,1.9 病态方程组和迭代改善法,150/47,1.9 病态方程组和迭代改善法,二. 误差分析,151/47,6.10 病态方程组和迭代改善法,
