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

第三章 解线性方程组的直接法3.1 引言与矩阵的一些基础知识3.2 Gauss消去法3.3 直接三角分解法3.4 向量和矩阵范数3.5 误差分析与病态方程组1数值分析 主讲教师 3.1 基础知识n3.1.1 引言n3.1.2 矩阵特征值与谱半径n3.1.3 对称正定矩阵n3.1.4 正交矩阵与初等矩阵2数值分析 主讲教师 3.1.1 引言n对于n个变量n个线性方程组求解，其表达式为：n用向量矩阵表示可表示为：3数值分析 主讲教师 其中4数值分析 主讲教师 5数值分析 主讲教师 3.1.2矩阵特征向量与谱半径6数值分析 主讲教师 7数值分析 主讲教师 8数值分析 主讲教师 9数值分析 主讲教师 10数值分析 主讲教师 11数值分析 主讲教师 3.1.3 对称正定矩阵12数值分析 主讲教师 13数值分析 主讲教师 3.1.4 正交矩阵与初等矩阵14数值分析 主讲教师 15数值分析 主讲教师 16数值分析 主讲教师 17数值分析 主讲教师 18数值分析 主讲教师 3.2 Gauss消去法n3.2.1 Gauss顺序消去法 n3.2.2 消去法与矩阵三角分解n3.2.3 列主元消去法19数值分析 主讲教师 3.2.1 Gauss顺序消去法20数值分析 主讲教师 21数值分析 主讲教师 22数值分析 主讲教师 23数值分析 主讲教师 24数值分析 主讲教师 25数值分析 主讲教师 26数值分析 主讲教师 27数值分析 主讲教师 3.2.2消去法与矩阵三角分解定理：28数值分析 主讲教师 3.2.3 列主元消去法29数值分析 主讲教师 选主元素的矩阵表示也称初等置换矩阵30数值分析 主讲教师 3.3 直接三角分解法n3.3.1 Doolittle分解法n3.3.2 Cholesky分解与平方根法 n3.3.3 三对角方程组的追赶法31数值分析 主讲教师 3.3.1 Doolittle分解法32数值分析 主讲教师 33数值分析 主讲教师 34数值分析 主讲教师 35数值分析 主讲教师 36数值分析 主讲教师 3.3.2 Cholesky分解与平方根法37数值分析 主讲教师 38数值分析 主讲教师 利用Cholesky分解将AX=b转化为，令，则原方程等价解以下两个方程39数值分析 主讲教师 例 用平方根法解方程组解 验证A正定，由Cholesky分解求得40数值分析 主讲教师 3.3.3 三对角方程组的追赶法41数值分析 主讲教师 42数值分析 主讲教师 下面举实例用追赶法来解三对角方程组。43数值分析 主讲教师 44数值分析 主讲教师 追赶法计算量：5n-4次乘法，o(n),计算量小；稳定性：普半径小于1，稳定。45数值分析 主讲教师 直接解法的直接解法的atlab求解求解1利用左除运算符的直接解法利用左除运算符的直接解法对于线性方程组对于线性方程组Ax=b，可以利用左除运算符，可以利用左除运算符“”求解：求解：x=Ab46数值分析 主讲教师 例例1 用直接解法求解下列线性方程组。用直接解法求解下列线性方程组。命令如下：命令如下：A=2,1,-5,1;1,-5,0,7;0,2,1,-1;1,6,-1,-4;b=13,-9,6,0;x=Ab47数值分析 主讲教师 2利用矩阵的分解求解线性方程组利用矩阵的分解求解线性方程组矩阵分解是指根据一定的原理用某种算法将一个矩阵分矩阵分解是指根据一定的原理用某种算法将一个矩阵分解成若干个矩阵的乘积。常见的矩阵分解有解成若干个矩阵的乘积。常见的矩阵分解有LU分解、分解、QR分解、分解、Cholesky分解，以及分解，以及Schur分解、分解、Hessenberg分解、奇异分解等。分解、奇异分解等。48数值分析 主讲教师(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)，这样可以大大提高运算速度。，这样可以大大提高运算速度。49数值分析 主讲教师 例例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)50数值分析 主讲教师 (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)。51数值分析 主讲教师 例例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)52数值分析 主讲教师 (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)。53数值分析 主讲教师 例例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=cholMatrix must be positive definite命令执行时，出现错误信息，说明命令执行时，出现错误信息，说明A为非正定矩为非正定矩阵。阵。54数值分析 主讲教师 3.4 向量和矩阵范数n3.4.1 向量内积与范数n3.4.2 矩阵范数（迭代解法数学基础）55数值分析 主讲教师 3.4.1 内积与向量范数56数值分析 主讲教师 3.4.1 内积与向量范数内积定义：设X为一个线性空间，为X上的一个二元泛函,满足：（1）（正定性）0,当且仅当x=0时等号成立；（2）（对第一变元线性）对任意a，bC1,=a+b;(3)(共扼对称性)=*。则称该二元泛函为线性空间X上的一个内积。57数值分析 主讲教师 3.4.1 内积与向量范数58数值分析 主讲教师 3.4.1向量内积与范数59数值分析 主讲教师 3.4.1 内积与向量范数例如：对RN(或CN),有如下的范数：这说明了范数的多样性。60数值分析 主讲教师 3.4.1 内积与向量范数从该定理可知内积可导出范数，61数值分析 主讲教师 3.4.1 内积与向量范数此外，内积还满足下述性质：62数值分析 主讲教师 3.4.1 内积与向量范数63数值分析 主讲教师 3.4.2 矩阵范数64数值分析 主讲教师 3.4.2 矩阵范数65数值分析 主讲教师 3.4.2 矩阵范数66数值分析 主讲教师 3.4.2 矩阵范数注2 通常的范数未必满足上述相容性条件，如：注3 由每种向量范数均可按前述定义构造出一种矩阵的从属范数。67数值分析 主讲教师 3.4.2 矩阵范数(A的行范数)(A的列范数)(A的2范数)68数值分析 主讲教师 3.4.2 矩阵范数69数值分析 主讲教师 3.4.2 矩阵范数70数值分析 主讲教师 3.4.2 矩阵范数证明（1）：（2）参见 关治、陆金甫。71数值分析 主讲教师 问题思考72数值分析 主讲教师 3.4.2 矩阵范数73数值分析 主讲教师 3.4.2 矩阵范数74数值分析 主讲教师 相关的定理*75数值分析 主讲教师 证明：76数值分析 主讲教师 3.5 误差分析与病态方程组n3.5.1矩阵条件数与扰动方程组误差界n3.5.2条件数与剩余误差估计的关系n3.5.3病态方程组的解法77数值分析 主讲教师 3.5.1矩阵条件数与扰动方程组误差界78数值分析 主讲教师 一个并不显然的例子79数值分析 主讲教师 80数值分析 主讲教师 3.5.1矩阵条件数与扰动方程组误差界n病态方程组的定义：81数值分析 主讲教师 3.5.1矩阵条件数与扰动方程组误差界对照条件数观察此式82数值分析 主讲教师 证明：83数值分析 主讲教师 3.5.1矩阵条件数与扰动方程组误差界84数值分析 主讲教师 3.5.2条件数与剩余误差估计的关系对上式比照条件数进行分析从而获得矩阵条件数的定义！85数值分析 主讲教师 86数值分析 主讲教师 3.5.2条件数与剩余误差估计的关系87数值分析 主讲教师 著名的病态矩阵(Hilbert)88数值分析 主讲教师 3.5.2条件数与剩余误差估计的关系89数值分析 主讲教师 3.5.3病态方程组的解法n病态方程组的症状:nCond(A)较大n在列主元素消元法中出现小主元n在计算过程中行或列几乎线性相关n矩阵A的元素数量级相差很大且无规律90数值分析 主讲教师 病态方程组的预处理平衡方法：91数值分析 主讲教师 3.5.3病态方程组的解法92数值分析 主讲教师 93数值分析 主讲教师 谢谢！