四川大学数值分析期末总复习(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,四川大学水利水电学院,数值分析,程复习,课,1,Gauss,消元法,解线性代数方程组的直接法,列主元素消去法,全主元素消去法,矩阵三角分解法,范数、条件数,平方根法,LU,分解法,追赶法,列主元素三角分解法,2,第四章 解线性代数方程组的直接法,（适用于中等规模的,n,阶线性方程组）,范数、条件数,Gauss,消去法,LU,分解法,平方根法,3,了解几个,基本概念,：,顺序主子式,D,i,：方阵前,i,行、前,i,列元素矩阵的行列式；,非奇异矩阵：对方阵,A,而言，即可证明,A,非奇异，涉及特征值时，全部,特征值均不等于,0,可证明,A,非奇异,.,对称正定矩阵：,充要条件：,A,的全部特征值大于,0,；顺序主子式全大于,0,；,性质：,行列式为正；,严格对角占优矩阵：详见书,P173.,4,Gauss,消去法,线性代数方程组：,用矩阵及向量形式表示：,AX,=,b,（,PS:,A,为非奇异矩阵，即 ）,5,消元过程：,实质上是用,去乘以第一个方程，得到一个新的方程，然后用,第二个方程减去这个新的方程，,使其,第一项,为,0,，最终变成：,同样取,乘以第一个方程,，得到一个新的方程，然后用第三个,方程减去这个新的方程，使其第一项为,0,，最终变成：,上标,(2),实际上表示经过消去法一步，以此类推,(3),表示经过消去法两,步。,6,重复此步骤,n-1,次最终得到等价方程组：,经过消元法,n-1,步后，可以得到一个等价的上三角形方程组：,（,PS,：,经过初等变换得到的矩阵与原矩阵等价）,即：,已为,0,0,7,经过回代可得到方程组的解：,此时必须满足条件：,n,阶线性方程组消元过程所需要的总运算量为：,消元乘法运算量：,消元除法运算量：,回代乘除法运算量：,8,消元公式,（,4.1.1,）,回代公式,（,4.1.2,）,9,消元法能够运用的,充要条件,为：,定理,1.1,：,矩阵,A,的顺序主子式,推论：,若矩阵,A,的顺序主子式 则有：,10,注意：,若某个主元,很小，会引起很大的误差。,因此可以采用,全主元素消去法,或,列主元素消去法,。,全主元素消去法：,实质上是在消元法进行了,k,（,k=0,1,2,.,n-1,）步之后，选取系数矩阵,A,第,k+1,行到第,n,行中绝对值最大的元作为主元，并利用初等行变换和列变换交换其位置，使其置于对角线上，成为对角元，以减小误差。,列主元素消去法：,实质上是在消元法进行了,k,（,k=0,1,2,.,n-1,）,步之后，选取系数矩阵,A,第,k+1,列中绝对值最大的元作为主元，并利用初等行变换使主元其置于对角线上，成为对角元，以减小误差。,11,典型题目,1,、概念题、消元及回代公式；,2,、用全主元素消去法或列主元素消去法解方程组；,3,、相关定理、定义或变形证明题,(,详见书本证明过程,).,例,1,：,分别用全主元素消去法和列主元素消去法解方程组，并由此计算系数行列式的值,.,第一步,：消元法进行了,0,步后，选出前三行的主元素,4,，经交换得：,全主元素消去法,：,经,Gauss,消元得,12,第二步：,消元法进行了,1,步后，选出前两行的主元素,2,，经交换得：,经,Gauss,消元得,回代求解得：,13,列主元素消去法：,第一步,：选出第一列的主元素,2,，经交换得：,经,Gauss,消元得,14,第二步,：选出第二列的主元素,3,，经交换得：,经,Gauss,消元得,回代求解得,：,结果相同！,15,例,2,：,矩阵,A,的元素 ，经过,Gauss,消去法,1,步后，,A,变为,证明若,A,对称，,A,2,也对称,.,证明,：,Guass,消元法第一步,16,即 故,A,2,也是对称矩阵,.,已知,A,为对称矩阵,故,因此：,其中：,得证,.,17,矩阵三角分解法,原理,：,对矩阵进行一次初等变换，相当于用相应的初等矩阵去左乘原来的矩阵。从这个观点来考察,Gauss,消去法，用矩阵乘法表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。,矩阵分解：,A,LU,18,第一步为：,LU,分解法,19,第,k,步为：,相当于左乘矩阵,L,k,第,k,行,第,i,行，,20,总体有：,易证：,21,其中,L,为单位下三角阵，,U,为上三角阵。,所以有：,22,注：分解理论由,Gauss,消去法得出，因此能够进行分解的条件与,Gauss,消去法结果一样。,*（实际使用时也需要选主元，即列主元素三角分解法）,由此，解线性方程组,Ax=b,等价于解两个三角形方程组：,关键在于,能否对矩阵,A,直接进行,LU,分解,23,定理,3.1,：,A,的所有顺序主子式均不为零，则,A,存在唯一的分解式,A=L,U,.,元素求解公式,定理,3.2,：对非奇异矩阵,A,，存在排列阵,P,，以及元素值全不大于,1,的单位下三角阵,L,和上三角阵,U,，使,24,平方根法,定理,3.3,：设,A,为对称正定矩阵，则存在唯一分解 其中,L,为,单位下三角阵，,D,为对角阵且对角元全大于,0.,定理,3.4,：,n,阶矩阵,A,对称正定时，则有如下分解：,则,A,存在唯一分解,(,即平方根分解,),：,其中,G,为下三角阵，规定,G,的对角元,全为正时，分解式是唯一的,.,25,元素求解公式,定理,3.5,：若线性代数方程组 的系数矩阵,A,对称正定，则用平方,根法进行求解是稳定的,.,（证明过程详见,P172,）,PS,：平方根法约需 次乘法，大约为直接,LU,分解计算量的一半,.,26,定理：,A,为三对角矩阵，且满足,则,A,非奇异，且追赶法可实现。,三对角方程组的,追赶法,27,如果,A,存在,LU,分解，则有：,其中,28,则：求解,Ax=f,29,再由,解得,以上称为解三对角方程组的追赶法。,30,典型题目,1,、利用,LU,方法、平方根法或追赶法对矩阵进行求解；,2,、判断,LU,分解是否存在且唯一,.,例,1,：判断,下述矩阵的,LU,分解是否存在？若存在，是否唯一？,已知,A,有唯一的,LU,分解（,LU,存在且唯一）,可从这两方面对问题进行考虑,31,？,以从判断矩阵的顺序主子式为例,对于,A,1,所以不存在,LU,分解,对于,A,2,所以不存在,LU,分解,对于,A,2,所以存在唯一的,LU,分解,32,范数、条件数,为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对,(n,维向量空间,),中的向量或 中矩阵的“大小”引入一种度量,向量和矩阵的范数。,向量范数,定义,4.1,：,如果向量 的某个,实值函数,满足条件：,1,）正定性：当且仅当,x=0,时,2,）齐次性：,3,）三角不等式：,则称,N,(,x,),是 上的一个,向量范数,.,33,常用的几种范数：,向量的,2-,范数：,向量的,1-,范数：,向量的,-,范数：,绝对值之和,模,最大值,34,定理,4.1,（范数等价性）,：对 上定义的任意两种范数 必存在两正常数,m,，,M,，使得：,定义,4.2,：设 中一向量序列,其中,若,满足,则称向量序列,(,依分量,),收敛到 ，记作：,定理,4.2,：,（,PS,：,必须为向量任一范数,.,）,35,矩阵范数,定义,4.3,：,如果矩阵 的某个,实值函数,满足条件：,1,）正定性：当且仅当,x=0,时,2,）齐次性：,3,）三角不等式：,则称,N,(,A,),是 上的一个矩阵,范数,.,4,）相容性：,36,定义,4.4,：,算子范数：,且,常见的矩阵范数：,谱范数,列范数,行范数,F-,范数,算子范数,37,定义,4.5,：设 中一矩阵序列,其中,若,则称矩阵序列 收敛到矩阵 ，记作：,定理,4.3,：,PS,：,必须为任一种矩阵范数,.,定义,4.6,：设 为矩阵,A,的特征值，称 为矩阵,A,的,谱半径,。,谱半径和范数的关系：,38,定理,4.4,：设任意,n,阶矩阵,F,满足 ，则 非奇异，且：,定理,4.5,：,条件数,（非奇异）：,矩阵条件数的,性质,：,为任意非,0,常数。,若 则,4,）若,A,是正交矩阵，则,A,的谱条件数等于,1,（相应的谱范数也为,1,），为最小值,.,39,典型题目,1,、范数的证明与判断,(,较难,),，求常见范数,(,易,),；,2,、相关定理、定义证明,(,详见书本证明过程,),；,3,、基于定理、定义证明的变形证明题,.,例,1,：设 为对称正定阵，定义,试证 为 上向量的一种范数,.,证：,正定性：,(,正定矩阵的定义,).,当 时,等号,成立,齐次性：,40,三角不等式：,对于,因为,A,正定，则对任意数,t,有：,41,即 对任意,t,成立,.,二次曲线开口向上，与,X,轴有一个或没有交点,.,则判别式,即,代入上面的表达式可得：,42,例,2,：若矩阵,的谱半径,为单位矩阵,证明矩阵,非奇异,.,证：,已知 故,设 为,B,的特征值,则,I,-,B,的特征值为1-,故,11-2,I-B,的所有特征值均不为零,故,|,I-,B,|=,得证,.,设,x,0,为,B,的特征向量，则有：,43,谢谢聆听,44,