解线性方程组的直接法.ppt

数值分析 主讲教师,1,第三章 解线性方程组的直接法,3.1 引言与矩阵的一些基础知识 3.2 Gauss消去法 3.3 直接三角分解法 3.4 向量和矩阵范数 3.5 误差分析与病态方程组,数值分析 主讲教师,2,3.1 基础知识,3.1.1 引言 3.1.2 矩阵特征值与谱半径 3.1.3 对称正定矩阵 3.1.4 正交矩阵与初等矩阵,数值分析 主讲教师,3,3.1.1 引言,对于n个变量n个线性方程组求解，其表达式为：,用向量矩阵表示可表示为：,数值分析 主讲教师,4,其中,数值分析 主讲教师,5,数值分析 主讲教师,6,3.1.2矩阵特征向量与谱半径,数值分析 主讲教师,7,数值分析 主讲教师,8,数值分析 主讲教师,9,数值分析 主讲教师,10,数值分析 主讲教师,11,数值分析 主讲教师,12,3.1.3 对称正定矩阵,数值分析 主讲教师,13,数值分析 主讲教师,14,3.1.4 正交矩阵与初等矩阵,数值分析 主讲教师,15,数值分析 主讲教师,16,数值分析 主讲教师,17,数值分析 主讲教师,18,数值分析 主讲教师,19,3.2 Gauss消去法,3.2.1 Gauss顺序消去法 3.2.2 消去法与矩阵三角分解 3.2.3 列主元消去法,数值分析 主讲教师,20,3.2.1 Gauss顺序消去法,数值分析 主讲教师,21,数值分析 主讲教师,22,数值分析 主讲教师,23,数值分析 主讲教师,24,数值分析 主讲教师,25,数值分析 主讲教师,26,数值分析 主讲教师,27,数值分析 主讲教师,28,3.2.2消去法与矩阵三角分解,定理：,数值分析 主讲教师,29,3.2.3 列主元消去法,数值分析 主讲教师,30,选主元素的矩阵表示也称初等置换矩阵,数值分析 主讲教师,31,3.3 直接三角分解法,3.3.1 Doolittle分解法 3.3.2 Cholesky分解与平方根法 3.3.3 三对角方程组的追赶法,数值分析 主讲教师,32,3.3.1 Doolittle分解法,数值分析 主讲教师,33,数值分析 主讲教师,34,数值分析 主讲教师,35,数值分析 主讲教师,36,数值分析 主讲教师,37,3.3.2 Cholesky分解与平方根法,数值分析 主讲教师,38,数值分析 主讲教师,39,利用Cholesky分解将AX=b转化为,，,令,，则原方程等价解以下两个方程,数值分析 主讲教师,40,例 用平方根法解方程组,解 验证A正定，由Cholesky分解求得,数值分析 主讲教师,41,3.3.3 三对角方程组的追赶法,数值分析 主讲教师,42,数值分析 主讲教师,43,下面举实例用追赶法来解三对角方程组。,数值分析 主讲教师,44,数值分析 主讲教师,45,追赶法计算量：5n-4次乘法，o(n),计算量小； 稳定性：普半径小于1，稳定。,数值分析 主讲教师,46,直接解法的atlab求解,1利用左除运算符的直接解法 对于线性方程组Ax=b，可以利用左除运算符“”求解： x=Ab,数值分析 主讲教师,47,例1 用直接解法求解下列线性方程组。 命令如下： A=2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4; b=13,-9,6,0; x=Ab,数值分析 主讲教师,48,2利用矩阵的分解求解线性方程组 矩阵分解是指根据一定的原理用某种算法将一个矩阵分解成若干个矩阵的乘积。常见的矩阵分解有LU分解、QR分解、Cholesky分解，以及Schur分解、Hessenberg分解、奇异分解等。,数值分析 主讲教师,49,(1) LU分解 矩阵的LU分解就是将一个矩阵表示为一个交换下三角矩阵和一个上三角矩阵的乘积形式。线性代数中已经证明，只要方阵A是非奇异的，LU分解总是可以进行的。 MATLAB提供的lu函数用于对矩阵进行LU分解，其调用格式为： L,U=lu(X)：产生一个上三角阵U和一个变换形式的下三角阵L(行交换)，使之满足X=LU。注意，这里的矩阵X必须是方阵。 L,U,P=lu(X)：产生一个上三角阵U和一个下三角阵L以及一个置换矩阵P，使之满足PX=LU。当然矩阵X同样必须是方阵。 实现LU分解后，线性方程组Ax=b的解x=U(Lb)或x=U(LPb)，这样可以大大提高运算速度。,数值分析 主讲教师,50,例2 用LU分解求解例题中的线性方程组。 命令如下： A=2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4; b=13,-9,6,0; L,U=lu(A); x=U(Lb) 或采用LU分解的第2种格式，命令如下： L,U ,P=lu(A); x=U(LP*b),数值分析 主讲教师,51,(2) QR分解 对矩阵X进行QR分解，就是把X分解为一个正交矩阵Q和一个上三角矩阵R的乘积形式。QR分解只能对方阵进行。MATLAB的函数qr可用于对矩阵进行QR分解，其调用格式为： Q,R=qr(X)：产生一个一个正交矩阵Q和一个上三角矩阵R，使之满足X=QR。 Q,R,E=qr(X)：产生一个一个正交矩阵Q、一个上三角矩阵R以及一个置换矩阵E，使之满足XE=QR。 实现QR分解后，线性方程组Ax=b的解x=R(Qb)或x=E(R(Qb)。,数值分析 主讲教师,52,例3 用QR分解求解例题中的线性方程组。 命令如下： A=2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4; b=13,-9,6,0; Q,R=qr(A); x=R(Qb) 或采用QR分解的第2种格式，命令如下： Q,R,E=qr(A); x=E*(R(Qb),数值分析 主讲教师,53,(3) Cholesky分解 如果矩阵X是对称正定的，则Cholesky分解将矩阵X分解成一个下三角矩阵和上三角矩阵的乘积。设上三角矩阵为R，则下三角矩阵为其转置，即X=RR。MATLAB函数chol(X)用于对矩阵X进行Cholesky分解，其调用格式为： R=chol(X)：产生一个上三角阵R，使RR=X。若X为非对称正定，则输出一个出错信息。 R,p=chol(X)：这个命令格式将不输出出错信息。当X为对称正定的，则p=0，R与上述格式得到的结果相同；否则p为一个正整数。如果X为满秩矩阵，则R为一个阶数为q=p-1的上三角阵，且满足RR=X(1:q,1:q)。 实现Cholesky分解后，线性方程组Ax=b变成RRx=b，所以x=R(Rb)。,数值分析 主讲教师,54,例4 用Cholesky分解求解例1中的线性方程组。 命令如下： A=2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4; b=13,-9,6,0; R=chol(A) ? Error using = chol Matrix must be positive definite 命令执行时，出现错误信息，说明A为非正定矩阵。,数值分析 主讲教师,55,3.4 向量和矩阵范数,3.4.1 向量内积与范数 3.4.2 矩阵范数 （迭代解法数学基础）,数值分析 主讲教师,56,3.4.1 内积与向量范数,数值分析 主讲教师,57,3.4.1 内积与向量范数,内积定义：设X为一个线性空间，为X上的一个二元泛函,满足： （1）（正定性）0,当且仅当x=0时等号成立； （2）（对第一变元线性）对任意a，bC1, = a+ b; (3)(共扼对称性)= *。 则称该二元泛函为线性空间X上的一个内积。,数值分析 主讲教师,58,3.4.1 内积与向量范数,数值分析 主讲教师,59,3.4.1向量内积与范数,数值分析 主讲教师,60,3.4.1 内积与向量范数,例如：对RN(或CN),有如下的范数：,这说明了范数的多样性。,数值分析 主讲教师,61,3.4.1 内积与向量范数,从该定理可知内积可导出范数，,数值分析 主讲教师,62,3.4.1 内积与向量范数,此外，内积还满足下述性质：,数值分析 主讲教师,63,3.4.1 内积与向量范数,数值分析 主讲教师,64,3.4.2 矩阵范数,数值分析 主讲教师,65,3.4.2 矩阵范数,数值分析 主讲教师,66,3.4.2 矩阵范数,数值分析 主讲教师,67,3.4.2 矩阵范数,注2 通常的范数未必满足上述相容性条件，如：,注3 由每种向量范数均可按前述定义构造出一种矩阵的从属范数。,数值分析 主讲教师,68,3.4.2 矩阵范数,(A的行范数),(A的列范数),(A的2范数),数值分析 主讲教师,69,3.4.2 矩阵范数,数值分析 主讲教师,70,3.4.2 矩阵范数,数值分析 主讲教师,71,3.4.2 矩阵范数,证明（1）：,（2）参见 关治、陆金甫。,数值分析 主讲教师,72,问题思考,数值分析 主讲教师,73,3.4.2 矩阵范数,数值分析 主讲教师,74,3.4.2 矩阵范数,数值分析 主讲教师,75,相关的定理*,数值分析 主讲教师,76,证明：,数值分析 主讲教师,77,3.5 误差分析与病态方程组,3.5.1矩阵条件数与扰动方程组误差界 3.5.2条件数与剩余误差估计的关系 3.5.3病态方程组的解法,数值分析 主讲教师,78,3.5.1矩阵条件数与扰动方程组误差界,数值分析 主讲教师,79,一个并不显然的例子,数值分析 主讲教师,80,数值分析 主讲教师,81,3.5.1矩阵条件数与扰动方程组误差界,病态方程组的定义：,数值分析 主讲教师,82,3.5.1矩阵条件数与扰动方程组误差界,对照条件数观察此式,数值分析 主讲教师,83,证明：,数值分析 主讲教师,84,3.5.1矩阵条件数与扰动方程组误差界,数值分析 主讲教师,85,3.5.2条件数与剩余误差估计的关系,对上式比照条件数进行分析从而获得矩阵条件数的定义！,数值分析 主讲教师,86,数值分析 主讲教师,87,3.5.2条件数与剩余误差估计的关系,数值分析 主讲教师,