计算方法3课件

1、第3章 线性方程组的数值解法三、 矩阵的三角分解及其应用四、 线性代数方程组的性态与误差分析五、 迭代法一、 线性方程组二、 高斯(Gauss)消元法求解上一页 下一页 返回 一、线性方程组 实际问题中的线性方程组分类：按系数矩阵中零元素的个数：稠密线性方程组稀疏线性方程组按未知量的个数：高阶线性方程组低阶线性方程组(如1000)(80%)按系数矩阵的形状对称正定方程组三角形方程组三对角占优方程组 实际中，存在大量的解线性方程组的问题。很多数值方法到最后也会涉及到线性方程组的求解问题：如样条插值的M和m关系式，曲线拟合的法方程，方程组的Newton迭代等问题。解线性方程组的两类数值方法：直接法

2、: 经过有限次四则运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）特点：准确，可靠，理论上得到的解是精确的。适合于中小规模的方程组。特点：速度快，但有误差。适合于大规模的方程组。Cramer法则是一种直接法，但无法实用 直接法概述直接法是将原方程组化为一个或若干个三角形方程组的方法对于线性方程组根据Cramer(克莱姆)法则,若则都是三角形方程组上述方法称为直接三角形分解法不论是Gauss消元法还是直接三角形分解法,最终都归结为解三角形方程组一、三角形线性代数方程组的直接法若记下三角形线性方程组上

3、三角形线性方程组 Gauss消去法二、直接法 其解为其解为:按回代过程求解对方程组，作如下的变换，解不变：交换两个方程的次序一个方程的两边同时乘以一个非0的数一个方程的两边同时乘以一个非0数，加到另一个方程二、Gauss消元法因此，对增广矩阵(A，b )作如下的变换，解不变：交换矩阵的两行某一行乘以一个非0的数某一行乘以一个非0数，加到另一行消元法就是对增广矩阵作上述行的变换，变为三角形线性方程组，而后求根。用矩阵表示：=首先将A化为上三角阵，再回代求解。例3.1.1解化为同解方程组化为上三角方程组按回代过程求解上述求解三元线性代数方程组的方法即为Gauss消元法。(1) 定义行乘数相当于第i

4、个方程-第一个方程行乘数新的第i方程同解！第一个方程不动！ 且(1) 定义行乘数相当于第i个方程-第二个方程行乘数新的第i方程同解！第一、二个方程不动！ 系数矩阵与常数项： Gauss消元法的运算量乘法次数：除法次数：全部回代过程需作乘除法的总次数为于是Gauss消元法的乘除法运算总的次数为数级类似地，可得Gauss消元法的加减法运算总的次数为由于计算机完成一次乘除运算所耗时间要远远多于完成一次加减运算的时间，而且按统计规律，在一个算法中，加减运算和乘除运算次数大体相当，故在衡量一个算法的运算量时只需统计乘除的运算次数。Gauss消元法乘除法约为2700次而如果用Cramer法则的乘除法运算次

5、数约为用行列式定义回代求解 从Gauss消元法的过程自然想到：如果在消元过程中把对角线上方未知量的系数也化为零，使方程组化成每个方程只含一个未知量的方程组，则无须回代就可得到解。这种消元法称为GaussJordan消元法。但经计算，它需要的乘除法次数为 显然，其运算量超过Gauss消元法。所以用GaussJordan消元法求解线性代数方程组是不可取的。不过，用它来求逆矩阵却有方便之处。三、选主元Gauss消元法例3.1.3用Gauss消元法解线性方程组(用3位十进制浮点数计算）解本方程组的精度较高的解为用Gauss消元法求解(用3位十进制浮点数计算)回代后得到主元9999与精确解相比,该结果相

6、当糟糕！究其原因,在求行乘数时用了很小的数0.0001作除数! 上述例题表明：Gauss消元法是不稳定的算法，其中小主元是不稳定的根源。因而在Gauss消元法中要避免小主元的出现。这就需要采用“选主元”的技术。所谓选主元，简单地说就是选取绝对值最大的元素作主元。 全选主元Gauss消元法在此范围内选主元需进行元素比较 列选主元Gauss消元法在此范围内选主元不必选主元的情况： 当系数矩阵A对称正定或严格对角占优或不可约对角占优时，可不必选主元。现用列选主元消元法重解例3.1.3：将方程组的1,2行交换，即得回代后得到这是一个相当不错的结果！0.9999例3.1.4解线性方程组(用8位十进制尾数

7、的浮点数计算)解这个方程组和例3.1.3一样，若用Gauss消元法计算会有小数作除数的现象，若采用换行的技巧（即列选主元消元法） ，则可避免。绝对值最大不需换行经过回代后可得事实上,方程组的准确解为 列选主元Gauss消元法的计算步骤? 列选主元Gauss消元法的流程图开始输出无解信息消元换行停机回代求解本算法主要由四个模块组成 一些特殊情况, 主元就在对角线上,不需选主元. 元素满足如下条件的矩阵 即对角线上每一元素的绝对值均大于同行其他各元素绝对值之和,这样的矩阵称为按行严格对角占优矩阵,简称严格对角占优矩阵.例：性质：严格对角占优矩阵必定非奇异.上一页 下一页 返回 补充一、 LU分解法

8、 /* LU Factorization. */就 n=3的情况分析顺序消去法的消元过程.上一页 下一页 返回 矩阵的三角(LU)分解法三、直接法 可见, 消元过程相当于下述矩阵乘法运算：由分块乘法可得：直接计算可得由(*)式可得上一页 下一页 返回 Step 1:记M(1) =，则Step n 1: 其中 M (k)= 以上分析推广到n阶线性方程组可得上一页 下一页 返回 记为L单位下三角阵/* unitary lower-triangular matrix */记 U =A 的 LU 分解/* LU factorization */也称 A 的Doolittle分解上一页 下一页 返回 道

9、立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式 /* compact form */根据矩阵乘法法则,先比较等式两边第1行和第1列元素有：上一页 下一页 返回 设已定出U 的第1行到第k-1行的元素 L 的第1列到第k-1列的元素上一页 下一页 返回 (1),(2)两式就是 LU分解的一般计算公式, 其结果与高斯消去法所得结果完全一样. 避免了中间过程的计算,故称为A的直接分解公式.上一页 下一页 返回 按上图逐框求出矩阵A的LU分解,这种计算方法称为紧凑格式法。上一页 下一页 返回 定理 若矩阵A非奇异, 则A能分解为LU 的充分必要条件是A的

10、所有顺序主子式 均不为0.定理 若非奇异矩阵A有LU 分解,则此分解是唯一的.上一页 下一页 返回 矩阵的Doolittle分解法的Matlab程序function 1,u=lu_Doolittle1(A)%A为可逆方阵，l为返回下三角矩阵，u为上三角阵n=length(A);u=zeros(n);l=eye(n);u(1,:)=A(1,:);l(2:n,1)=A(2:n,1)/u(1,1);for k=2:n u(k,k:n)=A(k,k:n)-l(k,1:k-1)*u(1:k-1,k:n); l(k+1:n,k)=(A(k+1:n,k)-l(k+1:n,1:k-1)*u(1:k-1,k)/

11、u(k,k);end例：利用系数矩阵的LU分解, 求解方程组解：LU分解的紧凑格式为上一页 下一页 返回 在Matlab命令窗口执行A=1 1 1 1;1 2 1 3;4 3 2 1;6 11 3 7;l,u=lu_Doolittle1(A)则求解原方程组等价于求解下面两个方程组Ly=b及Ux=y上一页 下一页 返回 在Matlab命令窗口执行A=1 1 1 1;1 2 1 3;4 3 2 1;6 11 3 7;b=6 12 14 45;y,x=LU_s(A,b)A=LU若U为单位上三角矩阵，则称为Crout分解.Crout分解相应的求解公式可类似得到。上一页 下一页 返回 二、平方根法 对称

12、 正定矩阵的分解法将对称 正定阵 A 做 LU 分解记为定理 设n阶对称正定矩阵A，则存在唯一的单位下三角阵L及对角阵D 使得 。 称为矩阵A 的乔累斯基分解上一页 下一页 返回 定理 设矩阵A对称正定，则存在唯一的对角元为正的下三角阵 L，使得 。 称为对称正定矩阵A 的乔累斯基分解 利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法三、三对角方程组追赶法若A满足Gauss消去法可行的条件，则可用LU分解法求解其中：上一页 下一页 返回 解方程组Ax=d分为两步，即求解Ly=d和Ux=y，计算公式如下：上述方法为求解三对角方程组的追赶法，也称Thom

13、as算法.上一页 下一页 返回 追赶法公式简单，计算量和存储量都小，整个求解过程只需要5n-4次乘除运算。 在分析方程组的解的误差及下章中迭代法的收敛性时，常产生一个问题,即如何判断向量 x 的“大小”，对矩阵也有类似的问题. 本节介绍n维向量范数和nn矩阵的范数. 向量范数是三维欧氏空间中向量长度概念的推广，在数值分析中起着重要作用.四、线性代数方程组的性态与误差分析定义3.3.1(一)向量和矩阵的范数按某种规则(或映射)1. 向量的范数由(3)可推出不等式：-(1)-(2)-(3)-(4)显然并且由于例3.3.1 求下列向量的各种常用范数解向量范数是其分量的连续函数，即有下述定理：定理3.

14、3.1（向量范数连续性定理）证明 向量序列的收敛性定义3.3.2 如果向量序列x(k)Rn和向量 xRn满足则称向量序列x(k)收敛于向量 x，记为显然，Rn 中向量序列x(k)收敛于 x 的充分必要条件是由下面向量范数的等价性定理可得到结论：如果在一种范数意义下向量序列收敛时，则在任何一种范数意义下向量序列亦收敛，即 有限维向量空间的范数等价性定理定理3.3.2注： 上述结论不能推广到无限维空间。容易验证： （1） x2x1 n1/2x2； （2）xx2 n1/2x； （3）xx1 nx。3种范数相互等价证明 由 x12+ x22+ + xn2(|x1|+ |x2|+ +| xn|) 2，两

15、边开方得第一式成立； 由 (|x1|+ |x2|+ +| xn|) 2 n( |x1|2+ |x2|2+ + |xn|2)，两边开方得第二式成立。定义3.3.32. 矩阵的范数例3.3.2不难验证其满足定义3.3.3的4个条件称为Frobenius范数，简称F-范数而且可以验证tr为矩阵的迹-(5)-(6)类似向量的 2-范数定义3.3.4-(7)简称为从属范数或导出范数或算子p-范数由此可知，给出一种向量范数，就有一种相应的矩阵范数显然，由定义不难推出定义3.3.5由(8)式,可知算子范数和其对应的向量范数是相容的-(8)-(9)根据向量的常用范数可以得到常用的矩阵算子范数-(10)-(11

16、)-(12)证明见书P70例3.3.3 解类似于向量的2-范数不过例3.3.4求矩阵A的各种常用范数解由于特征方程为容易计算计算较复杂对矩阵元素的变化比较敏感不是从属范数较少使用(理论上)使用最广泛性质较好 矩阵范数的等价性定理定理3.3.3可以验证： （1）A2AF n1/2A2； （2） n-1/2 AA2 n1/2A； （3） n-1/2 A1A2 nA14种范数相互等价定义3.3.5-(13) 矩阵的谱半径显然，由定义可知定理3.3.4而证明实特征值为绝对值，复特征值为模即所以因此定理3.3.5 补充 矩阵序列的收敛性定义3.3.6 如果n阶矩阵序列A(k) Rnn和矩阵ARnn 满足

17、 （ 其中A(k)=(aij(k)nn , A=(aij)nn）则称矩阵序列A(k)收敛于矩阵 A，记为显然，Rnn 中矩阵序列A(k) 收敛于矩阵A 的充分必要条件是定理3.3.6 证明定理3.3.7-(14)证明补充练习 设则求相应的各种范数.解因为令得ATA的特征值故可见求A1, A2 , A , (A).作业：设 ,解: 显然A1 =4,A=4 这里, 我们指出, 对于实对称矩阵A, 有(A)=|A|2.(二) 线性代数方程组的性态与误差分析1. 线性代数方程组的性态 判断一个计算方法的好坏，可用方法是否稳定、解的精确度高低以及计算量、存储量大小等来衡量。然而，对于不同的问题，同一方法

18、却可以产生完全不同的效果，这就涉及到所提供问题的性态，即“好、坏”。例3.3.5 可见，在上述方程组中，系数误差的小扰动对解的影响不大。可见，在上述方程组中，系数误差的小扰动对解的影响很大。-(1)-(2)-(3)定义3.3.7定理3.3.8推论1推论2 常数项 b 的扰动对解的影响 系数矩阵A 的扰动对解的影响定义3.3.8矩阵A的条件数与所取范数有关。通常记显然，当A对称时，例3.3.6 试求例3.3.5中两个线性代数方程组的条件数解 因而，第二个方程组的性态远比第一个方程组坏， 从而对系数的敏感程度要高得多。值得强调的是，线性代数方程组的性质是问题本身的固有性质。用一个稳定的方法去解一个

19、良态的方程组，必然得到较准确的结果。同样用一个稳定的方法去解一个病态的方程组，结果就可能很差。例3.3.7 解线性代数方程组的精确解为用列选主元消元法计算：回代后得到计算结果完全不可靠，实际上，此时因此，方程组病态！如把方程组的系数舍入成两位有效数字例3.3.8设有线性代数方程组试分析其性态。试分别计算两组方程组的精确解。它的精确解为x1 = -6.222. x2= 38.25 x3= -33.65.它的精确解为x1=x2=x3=1.条件数不是很好。两个解相差大，说明解对系数矩阵敏感程度高事实上，上例中矩阵A是三阶Hilbert矩阵n阶Hilbert矩阵是有名的病态矩阵，它随着矩阵阶数的增大，

20、条件数迅速增大。解 “病态”方程的经验判断 “病态”问题的处理方法例3.3.9 解回代后得到用列选主元消元法计算：计算解很精确例3.3.10 解等价的方程组解回代后得到用列选主元消元法计算：与例3.3.7的计算结果相比，这是一个很好的近似解定理3.3.92. 误差分析证明注: cond (A) 的具体大小与 | | 的取法有关，但相对大小一致。 cond (A) 取决于A，与解题方法无关。常用条件数有：cond 1(A)cond (A)cond2 (A)条件数的性质： A可逆，则 cond p (A) 1； A可逆， R 则 cond ( A) = cond (A) ； A正交，则 cond

21、2 (A) =1； A可逆，R正交，则 cond 2 (RA) = cond 2 (AR) = cond (A)2 。上一页 下一页 返回 注：一般判断矩阵是否病态，并不计算A1，而由经验得出。 行列式的值很大或很小（如某些行、列近似相关）； 元素间的数量级相差大，且无规则； 主元消去过程中出现小主元； 特征值相差大数量级。 直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!) 直接法比较适用于中小型方程组。直接法得到的解理论上是准确的，但它们的计算量都是n3数量级，存储量为n2数量级，这在n比较小的时候还比较合适（n400）。对于现在的很多实际问题，往往要我们求解n很大的高阶方程组