第三章解线性方程组的直接法

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