线性方程组的直接方法 课件.ppt

线性方程组的直接方法 第1页，此课件共104页哦解线性方程组的直接法解线性方程组的直接法简记为简记为 Ax=b，其中，其中(6.1)常见的线性方程组是方程个数和未知量个数相常见的线性方程组是方程个数和未知量个数相同的同的n阶线性方程组，一般形式为阶线性方程组，一般形式为 第2页，此课件共104页哦线性方程组的数值解法一般有两类：线性方程组的数值解法一般有两类：1.直接法：就是经过有限步算术运算，可求得方程直接法：就是经过有限步算术运算，可求得方程组精确解的方法（组精确解的方法（若计算过程中没有舍入误差若计算过程中没有舍入误差），），如克莱姆法则就是一种直接法，直接法中具有代如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯表性的算法是高斯(Gauss)消去法。消去法。2.迭代法迭代法:就是用某种极限过程去逐步逼近线性就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是方程组的精确解的方法。也就是从解的某个近从解的某个近似值出发，通过构造一个无穷序列去逼近精确解似值出发，通过构造一个无穷序列去逼近精确解的方法。的方法。(一般有限步内得不到精确解一般有限步内得不到精确解)第3页，此课件共104页哦三、特殊矩阵三、特殊矩阵1)对角矩阵2)三对角矩阵3)上三角矩阵4)上海森伯(Hessenberg)阵5)对称矩阵6)埃尔米特矩阵7)对称正定矩阵8)正交矩阵9)酉矩阵10)初等置换阵11)置换阵第4页，此课件共104页哦定理定理1 设ARnn,A非奇异?定理定理2 若ARnn对称正定矩阵，则?定理定理3 若ARnn对称矩阵，则对称正定矩阵0,i=1,2,0,i=1,2,n,n 因此存在惟一的分解因此存在惟一的分解 A=LU A=LU 第58页，此课件共104页哦L是单位下三角阵是单位下三角阵,U是上三角阵是上三角阵,将将U再分解再分解 其中其中D为对角阵为对角阵,U0为单位上三角阵，于是为单位上三角阵，于是 A=L U=L D U0 又又 A=AT=U0TD LT由分解惟一性由分解惟一性,即得即得 U0T=L A=L D LT 第59页，此课件共104页哦记记 又因为又因为det(Ak)0,(k=1,2,n),故故于是对角阵于是对角阵D还可分解还可分解 其中其中 为下三角阵为下三角阵,令令L=LL=L1 1，定理得证。，定理得证。第60页，此课件共104页哦将将A=LLT展开，写成展开，写成 按矩阵乘法展开，可逐行求出分解矩阵按矩阵乘法展开，可逐行求出分解矩阵L L的元素，计算的元素，计算公式是对于公式是对于i=1,2,i=1,2,n,n j=i+1,i+2,n 这一方法称为这一方法称为平方根法平方根法,又称又称乔累斯基乔累斯基(Cholesky)分解分解,它它所需要的乘除次数约所需要的乘除次数约 为数量级为数量级,比比LU分解节省近一般分解节省近一般的工作量。的工作量。第61页，此课件共104页哦例例6.9 6.9 平方根法求解方程组平方根法求解方程组 解解:因方程组系数矩阵对称正定因方程组系数矩阵对称正定,设设A=,A=,即：即：由由Ly=bLy=b解得解得 由由 解得解得 由此例可以看出，平方根法解正定方程组的缺点是由此例可以看出，平方根法解正定方程组的缺点是需要进行开方运算。为避免开方运算，我们改用单位三需要进行开方运算。为避免开方运算，我们改用单位三角阵作为分解阵，即把对称正定矩阵角阵作为分解阵，即把对称正定矩阵A分解成分解成 的形式，其中的形式，其中 第62页，此课件共104页哦为对角阵，而为对角阵，而 是单位下三角阵是单位下三角阵,这里分解这里分解公式为公式为 第63页，此课件共104页哦据此可逐行计算据此可逐行计算 运用这种矩阵分解方法运用这种矩阵分解方法,方程组方程组Ax=bAx=b即即可归结为求解两个上三角方程组可归结为求解两个上三角方程组 和和其计算公式分别为其计算公式分别为 和和 求解方程组的上述算法称为改进的平方根法。这种方法总求解方程组的上述算法称为改进的平方根法。这种方法总的计算量约为的计算量约为 ，即仅为高斯消去法计算量的一半。，即仅为高斯消去法计算量的一半。第64页，此课件共104页哦记笔记记笔记5.7 5.7 向量和矩阵的范数向量和矩阵的范数 为了研究线性方程组近似解的误差估计为了研究线性方程组近似解的误差估计和迭代法的收敛性和迭代法的收敛性,有必要对向量及矩阵的有必要对向量及矩阵的“大小大小”引进某种度量引进某种度量-范数的概念。向量范数的概念。向量范范数是用来度量向量长度的数是用来度量向量长度的,它可以看成是二、它可以看成是二、三维解析几何中向量长度概念的推广。用三维解析几何中向量长度概念的推广。用Rn表示表示n维实向量空间。维实向量空间。第65页，此课件共104页哦记笔记记笔记5.7 5.7 向量和矩阵的范数向量和矩阵的范数定义定义5.2 对任一向量对任一向量X Rn,按照一定规则确定一个实按照一定规则确定一个实数与它对应数与它对应,该实数记为该实数记为|X|,若若|X|满足下面三个满足下面三个性质性质:(1)|X|0；|X|=0当且仅当当且仅当X=0；(2)对任意实数对任意实数，|X|=|X|；(3)对任意向量对任意向量Y Rn，|X+Y|X|+|Y|则称该实数则称该实数|X|为向量为向量X的的范数范数第66页，此课件共104页哦在在R Rn n中，常用的几种范数有：中，常用的几种范数有：记笔记记笔记其中其中其中其中x x x x1 1 1 1,x,x,x,x2 2 2 2,x,x,x,xn n分别是分别是分别是分别是X X X X的的的的n n n n个分量。以上定义的个分量。以上定义的个分量。以上定义的个分量。以上定义的范数分别称为范数分别称为范数分别称为范数分别称为1-1-1-1-范数，范数，2-2-范数和范数和范数和范数和 -范数范数范数范数可以验证它们都是满足范数性质的，其中可以验证它们都是满足范数性质的，其中可以验证它们都是满足范数性质的，其中可以验证它们都是满足范数性质的，其中 是由内积导出的向量范数。是由内积导出的向量范数。5.7 5.7 向量和矩阵的范数向量和矩阵的范数第67页，此课件共104页哦当不需要指明使用哪一种向量范数时，就用记号当不需要指明使用哪一种向量范数时，就用记号|.|泛指任泛指任何一种向量范数。何一种向量范数。有了向量的范数就可以用它来衡量向量的大小和表示向有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。量的误差。设设x*为为Ax=b的精确解，的精确解，x为其近似解，则其绝对误差可为其近似解，则其绝对误差可表示成表示成|x-x*|，其相对误差可表示成，其相对误差可表示成记笔记记笔记5.7 5.7 向量和矩阵的范数向量和矩阵的范数或或第68页，此课件共104页哦第69页，此课件共104页哦例例5.10 证明对任意同维向量证明对任意同维向量x,y 有有 证：证：即即 第70页，此课件共104页哦例例5.11 设设x=(1,0,-1,2)T,计算计算 解解:=1+0+|-1|+2=4第71页，此课件共104页哦定理定理7.1 7.1 对于任意向量对于任意向量x,有有证证:即即 当当 p，第72页，此课件共104页哦定义定义5.4 (向量序列的极限向量序列的极限)设设 为为 中的中的一向量序列，一向量序列，,记记 。如果。如果 (i=1,2,n)，则称则称 收敛于向量收敛于向量 ，记为，记为 定理定理7.2（向量范数的等价性）设（向量范数的等价性）设 为为 上任意两种向量范数上任意两种向量范数,则存在常数则存在常数C1,C20,使得对任意使得对任意 恒有恒有（证（证:略）略）第73页，此课件共104页哦定理定理7 其中其中 为向量中的任一种范数。为向量中的任一种范数。证证 由于由于 而对于而对于 上的任一种上的任一种 范数范数,由定理由定理3.7知存在常数知存在常数C1，C2，使，使 于是可得于是可得 从而定理得证。从而定理得证。第74页，此课件共104页哦定义定义5.5（矩阵的范数矩阵的范数）如果矩阵）如果矩阵 的某个的某个非负的实值函数非负的实值函数 ，满足，满足则称则称 是是 上的一个矩阵范数上的一个矩阵范数(或模或模)第75页，此课件共104页哦矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证。(1)设设A0,x0,使使Ax0,根据向量范数的性根据向量范数的性 质质 Ax 0,所以所以0 x0,使使 Ax =0,则则=0当当A=0时时,第76页，此课件共104页哦矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证(2)根据向量范数的性质根据向量范数的性质第77页，此课件共104页哦矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证(3)第78页，此课件共104页哦矩阵范数定义的另一种方法是矩阵范数定义的另一种方法是这是由于这是由于同样，矩阵范数和向量范数密切相关，向量范数同样，矩阵范数和向量范数密切相关，向量范数有相应的矩阵范数，即有相应的矩阵范数，即第79页，此课件共104页哦第80页，此课件共104页哦定义定义5.7（矩阵的谱半径）设（矩阵的谱半径）设 的特征的特征 值为值为 ,称称 为为A的的谱半径。谱半径。例例 5.12 5.12 计算方阵计算方阵 的三种常用范数的三种常用范数 第81页，此课件共104页哦例例5.12 5.12 计算方阵计算方阵 的三种范数的三种范数 解解 先计算先计算 所以所以 ,从而从而 第82页，此课件共104页哦定理定理5.8.1 设设A为为n阶方阵阶方阵,则对任意则对任意矩阵范数矩阵范数都有都有证证:设设 为为A的特征值，的特征值，x是是 对应于的特征向对应于的特征向 量量,则则 x=Ax。两端取范数并依据其性质。两端取范数并依据其性质 得得由于由于x0，故，故 ，所以，所以第83页，此课件共104页哦第84页，此课件共104页哦5.8 误差分析误差分析5.8.1 方程组的性态方程组的性态 在建立方程组时，其系数往往含有误差在建立方程组时，其系数往往含有误差（如观测误差或计算误差），就是说，所要求（如观测误差或计算误差），就是说，所要求解的运算是有扰动的方程组，因此需要研究扰解的运算是有扰动的方程组，因此需要研究扰动对解的影响。动对解的影响。第85页，此课件共104页哦例例5.13 考察方程组考察方程组 和和 上上述述两两个个方方程程组组尽尽管管只只是是右右端端项项有有微微小小扰扰动动,但解大不相同但解大不相同,第第1个方程组的解是个方程组的解是第第2个方程组的解是个方程组的解是 。这类方程组称为病。这类方程组称为病态的。态的。第86页，此课件共104页哦定义定义5.8 A或或b的微小变化的微小变化(又称扰动或摄动又称扰动或摄动)引起引起方程组方程组Ax=b解的巨大变化，则称方程组为病态方程解的巨大变化，则称方程组为病态方程组，矩阵组，矩阵A称为病态矩阵。否则方程组是良态方程称为病态矩阵。否则方程组是良态方程组，矩阵组，矩阵A也是良态矩阵也是良态矩阵 为了定量地刻画方程组为了定量地刻画方程组“病态病态”的程度，要的程度，要对方程组对方程组Ax=b进行讨论，考察进行讨论，考察A（或（或b）微小误差）微小误差对解的影响。为此先引入矩阵条件数的概念。对解的影响。为此先引入矩阵条件数的概念。定义定义5.9 （矩阵条件数）设（矩阵条件数）设A为非奇异矩阵，称为非奇异矩阵，称 为矩阵为矩阵A条件数。条件数。第87页，此课件共104页哦第88页，此课件共104页哦第89页，此课件共104页哦 我们先来考察常数项我们先来考察常数项b的微小误差对解的影响。的微小误差对解的影响。设设A是精确的是精确的,b有误差有误差(或扰动或扰动)b,显然显然,方程组方程组 的解与的解与x有差别有差别,记为记为即有即有即即 （由设（由设Ax=b0）于是于是 （6.18）又又 Ax=b0，则有，则有 由（由（6.18）式及（）式及（6.19）式即得如下定理）式即得如下定理（6.19）或或第90页，此课件共104页哦定理定理 5.12 (b的扰动对解的影响的扰动对解的影响)设设A非奇异，非奇异，Ax=b0，且，且 则有则有 证证:设设A A精确且非奇异精确且非奇异,b,b有扰动有扰动b,b,使解使解x有扰动有扰动x,则则 消去消去Ax=bAx=b，有，有又又相比较可相比较可得得 第91页，此课件共104页哦定理定理 5.13 (A5.13 (A的扰动对解的影响的扰动对解的影响)设设A A非奇异，非奇异，Ax=b0Ax=b0，且，且若若 ,则则 证证：略：略第92页，此课件共104页哦我们还可证明更为一般的结论：我们还可证明更为一般的结论：当方程组的系数矩阵当方程组的系数矩阵A非奇异和常数项非奇异和常数项b为非为非零向量时，且同时有扰动零向量时，且同时有扰动A，b，满足，满足 ，若，若x和和x+x分别是方程组分别是方程组Ax=b 及及 的解的解则则第93页，此课件共104页哦例例6.13 6.13 线性方程组线性方程组 的系数矩阵带误差，成为如下方程组的系数矩阵带误差，成为如下方程组 求方程组系数矩阵的条件数求方程组系数矩阵的条件数,并说明方程组的性态并说明方程组的性态 解解 因为因为 所以所以 因此方程组是良态的因此方程组是良态的 第94页，此课件共104页哦5.7.2 精度分析精度分析求得方程组求得方程组Ax=b的一个近似解以后的一个近似解以后,希望判断其希望判断其精度，检验精度的一个简单办法是将近似解再精度，检验精度的一个简单办法是将近似解再回代到原方程组去求出回代到原方程组去求出余量余量r.r=b-A 如果如果r r很小，就认为解是相当精确的。很小，就认为解是相当精确的。定理定理6.14 6.14 设设 是方程组是方程组A Ax=b=b的一个近似解的一个近似解,其其精确解记为精确解记为 ,r,r为为 的余量。则有的余量。则有 证明见证明见P P172172第95页，此课件共104页哦例例5.14 设设A为正交矩阵，证明：为正交矩阵，证明：cond2(A)=1分析：由正交矩阵和条件数的定义便可推得分析：由正交矩阵和条件数的定义便可推得解：因为解：因为A是正交矩阵，是正交矩阵，故故ATA=AAT=I，A-1=AT，从而，从而第96页，此课件共104页哦例例5.15 设设A，B为为n阶矩阵，证明：阶矩阵，证明：cond(AB)cond(A)cond(B)分析分析:由矩阵范数性质和条件数定义由矩阵范数性质和条件数定义 便可证明便可证明证：证：cond(AB)=|AB|(AB)-1|A|B|A-1|B-1|=|A|A-1|B|B-1|=cond(A)cond(B)第97页，此课件共104页哦例例5.16 设设A，B为为n阶非奇异矩阵，阶非奇异矩阵，|表示表示 矩阵的任一种范数，证明：矩阵的任一种范数，证明：|A-1-B-1|A-1|B-1|A-B|cond(AB)cond(A)cond(B)分析分析:由矩阵范数的基本性质即可推证由矩阵范数的基本性质即可推证证：证：A-1-B-1=A-1(B-A)B-1,从而从而|A-1-B-1|A-1(B-A)B-1|A-1|B-A|B-1|A-1-B-1|A-1|B-A|B-1|第98页，此课件共104页哦例例9 9 求Hilbert矩阵H3的条件数.第99页，此课件共104页哦如何发现判断矩阵是病态的?如何解决和处理?预处理方法预处理方法.第100页，此课件共104页哦例例10 10 设则化为则第101页，此课件共104页哦二、迭代改善法二、迭代改善法(略去略去)第102页，此课件共104页哦本章小结本章小结 本章介绍了解线性方程组的直接法。直接法是一本章介绍了解线性方程组的直接法。直接法是一种计算量小而精度高的方法。直接法中具有代表性的种计算量小而精度高的方法。直接法中具有代表性的算法是高斯（算法是高斯（Gauss）消去法（在第一章提到的克莱姆算）消去法（在第一章提到的克莱姆算法也是一种直接法，但该算法用于高阶方程组时计算量太法也是一种直接法，但该算法用于高阶方程组时计算量太大而不实用），其它算法大都是它的变型，这类方法是解大而不实用），其它算法大都是它的变型，这类方法是解具有稠密矩阵或非结构矩阵（零元分布无规律）方程组的具有稠密矩阵或非结构矩阵（零元分布无规律）方程组的有效方法。有效方法。第103页，此课件共104页哦 选选主主元元的的算算法法有有很很好好的的数数值值稳稳定定性性。从从计计算算简简单单出出发发实际中多选用列主元法。实际中多选用列主元法。解解三三对对角角矩矩阵阵方方程程组组（A A的的对对角角元元占占优优）的的追追赶赶法法，解解对对称称正正定定矩矩阵阵方方程程组组的的平平方方根根法法都都是是三三角角分分解解法法，且且都都是是数数值值稳稳定定的的方方法法，这这些些方方法法不不选选主主元元素素，也也具具有有较较高高的的精精度。度。向量、矩阵的范数、矩阵的条件数和病态方程组的概念，向量、矩阵的范数、矩阵的条件数和病态方程组的概念，是数值计算中一些基本概念。线性方程组的病态程度是其本身是数值计算中一些基本概念。线性方程组的病态程度是其本身的固有特性，因此即使用数值稳定的方法求解，也难以克服严的固有特性，因此即使用数值稳定的方法求解，也难以克服严重病态导致的解的失真。在病态不十分严重时，用双精度求解重病态导致的解的失真。在病态不十分严重时，用双精度求解可减轻病态的影响可减轻病态的影响 第104页，此课件共104页哦