《9讲:ch4-1消元法.ppt》由会员分享,可在线阅读,更多相关《9讲:ch4-1消元法.ppt(45页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第四章第四章 线性方程组的直接解法线性方程组的直接解法线性方程组的直接解法 消元法的一般理论消元法的一般理论 主元素消去法的理论与程序主元素消去法的理论与程序三角分解法的理论三角分解法的理论平方根与改进的平方根法平方根与改进的平方根法误差估计与余项分析误差估计与余项分析向量和矩阵的定义;向量和矩阵的定义;矩阵的基本运算矩阵的基本运算:矩阵加法,矩阵与标量的乘法,:矩阵加法,矩阵与标量的乘法,矩阵与矩阵的乘法,转置矩阵,矩阵与矩阵的乘法,转置矩阵,单位矩阵,奇异和非奇异矩阵,单位矩阵,奇异和非奇异矩阵,矩阵的行列式(按照行或列展矩阵的行列式(按照行或列展 开),行列式的基本性质。开),行列式的基
2、本性质。预备知识特殊矩阵特殊矩阵:对角矩阵,三对角矩阵,上三角矩阵,:对角矩阵,三对角矩阵,上三角矩阵,对称矩阵(对称矩阵(A的转置的转置A),),Hermite矩阵(矩阵(A的共轭转置的共轭转置=A),),对称正定矩阵(对称正定矩阵(A的转置的转置A,且对任何非零且对任何非零X,有,有X的转置的转置AX 0),),正交矩阵(正交矩阵(A的逆等于的逆等于A的转置),的转置),初等置换阵初等置换阵.预备知识设有线性方程组设有线性方程组:如何求解方程组如何求解方程组?一、问题的提出本章假设:方程组的解存在唯一。即系数行列式:优点:收敛、稳定、结论可靠优点:收敛、稳定、结论可靠缺点:计算量过大缺点:
3、计算量过大二、方程组的解法1Cramer法则MathMath程序程序:A=1,1,1,0,4,-1,2,-2,1;MatrixForm%x=x1,x2,x3;b=6,5,1;LinearSolveA,bSolveA.x=b答案答案:1,2,3x1-1,x2-2,x3-3解线性方程组,给解线性方程组,给出的解为向量形式出的解为向量形式 三、线性方程组的Maths解法 三、线性方程组的Maths解法第1节 高斯高斯(GaussGauss)消元法消元法高斯(Gauss)消元法 高斯消元法是一个古老的直接法高斯消元法是一个古老的直接法,由它由它改进得到的选主元的消元法改进得到的选主元的消元法,是目前计
4、算机是目前计算机上常用于求低阶稠密矩阵方程组的有效方法上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将其特点就是通过消元将一般线性方程组一般线性方程组的求的求解问题转化为解问题转化为三角方程组三角方程组的求解问题的求解问题。高斯(Gauss)消元法举例举例举 例上三角方程组的一般形式是:上三角方程组的一般形式是:目标目标高斯(Gauss)消元法高斯(Gauss)消元法对对n阶线性方程组阶线性方程组转化为等价的转化为等价的(同解同解)的三角方程组的三角方程组.称称消元过程消元过程,逐次计算出,逐次计算出 称称回代过回代过程程。高斯(Gauss)消元法相当于第相当于第i i个方程减第一
5、个方程个方程减第一个方程数数新的第新的第i i方方程程同解!第一方程不动!同解!第一方程不动!Gauss Gauss 消去法计算过程分析消去法计算过程分析Gauss 消去法计算过程分析 上述消元过程除第一个方程不变以外上述消元过程除第一个方程不变以外,第第2 2第第 n n 个方程全消去了变量个方程全消去了变量 ,而系数,而系数 和常数项全得到新值:和常数项全得到新值:高斯(Gauss)消元法高斯(Gauss)消元法高斯(Gauss)消元法高斯(Gauss)消元法高斯(Gauss)消元法第第n-1步消区过程后,得到等价三角方程组。步消区过程后,得到等价三角方程组。高斯(Gauss)消元法高斯(
6、Gauss)消元法消去过程算法消去过程算法高斯(Gauss)消元法回代过程算法回代过程算法请同学们自己推导!高斯(Gauss)消元法例例2.12.1举 例举 例举 例消去第一列的消去第一列的 n-1 n-1 个系数要计算个系数要计算n*(n-1n*(n-1)次乘法。次乘法。远小于用克莱姆法则求解的乘除运算量远小于用克莱姆法则求解的乘除运算量。Gauss消去法乘除法计算量第2节 主元素法主元素法解解:因为因为a a1111=0,=0,故此题不能用故此题不能用GaussGauss消元法求解消元法求解,但但交换方程组的顺序后交换方程组的顺序后,就可就可用用GaussGauss消元法求解了消元法求解了
7、.问题问题1:1:考虑如下线性方程组的考虑如下线性方程组的GaussGauss消元法消元法 2x2=1 2x1+3x2=2问题问题2:2:讨论下面方程组的解法讨论下面方程组的解法0.0001x0.0001x1 1+x+x2 2=1=1 x x1 1+x+x2 2=2=2假设求解是用四位小数计假设求解是用四位小数计算机上进行算机上进行问 题0.1000 10-3 x1+0.1000 101 x2=0.1000 1010.1000 101 x1 +0.1000 101 x2=0.2000 101 解解:本题的计算机机内形式为本题的计算机机内形式为 因为因为a a11 11=0.0001=0.000
8、1 0,0,故可用故可用GaussGauss消元法求解消元法求解,进行进行第一次消元时有第一次消元时有a22(1)=0.1000 101-104 0.1000 101 =0.00001 105-0.1000 105 (对阶对阶计算计算)=0.0000-0.1000 105=-0.1000 105,(m21=a21/a11=1/0.0001=104)得三角方程组得三角方程组 问 题0.1000 10-3 x1+0.1000 101 x2=0.1000 101 -0.1000 105 x2=-0.1000 105 回代解得回代解得x2=1,x1=0 严重失真严重失真!(因为本题的准确解为因为本题的
9、准确解为 x1=10000/9999,x2=9998/9999失真的原因:除数的绝对值远远小于被除数的绝对值问 题 用高斯消去法求解线性方程组时用高斯消去法求解线性方程组时,应避免小的主应避免小的主元元.在实际计算中在实际计算中,进行第进行第k k步消去前步消去前,应该在第应该在第k k列元列元素素 中找出绝大值最大者中找出绝大值最大者,例如例如 再把第再把第p p个方程与第个方程与第k k个方程组进行交换个方程组进行交换,使使 成为主元成为主元.我们称这个过程为我们称这个过程为选主元选主元.由于只在第由于只在第k k列列元素中选主元元素中选主元,通常也称为通常也称为按列选主元按列选主元(或称
10、或称列主元素列主元素法法).).一、列主元的基本思想 如果在第如果在第k k步消去前步消去前,在第在第k k个方程到第个方程到第n n个方程所有的个方程所有的x xk k到到x xn n的系数的系数 中中,找出找出绝对值最大者绝对值最大者,例如例如 再交换第再交换第k,pk,p两个方程和第两个方程和第k,qk,q两个未知量的次序两个未知量的次序,使使 成为主元成为主元.称这个过程为称这个过程为完全选主元或全主完全选主元或全主元素法元素法.不论是哪种方式选出主元不论是哪种方式选出主元,而后再按上面介绍的计算而后再按上面介绍的计算步骤进行消去的计算步骤进行消去的计算,一般都称为一般都称为选主元的高
11、斯消去法选主元的高斯消去法.在实际计算中在实际计算中,常用按列选主元的高斯消去法常用按列选主元的高斯消去法.完全选主元或全主元素法 用列主元消去法用列主元消去法解方程组解方程组解解 第一次消元对第一次消元对 因列主元素为因列主元素为a31(1),故先作行变换故先作行变换r1 r3,然后然后进行消元计算可得进行消元计算可得例例2.22.2举 例 由此回代由此回代,得得x=(1.9272,-0.69841,0.90038)T与精确解与精确解x=(1.9273,-0.69850,0.90042)T相比较是相比较是比较准确的比较准确的.第二次消元对第二次消元对A(2)|b(2),因列主元素为因列主元素
12、为a32(2),故故先作行变换先作行变换r2_r3,然后进行消元计算可得然后进行消元计算可得举 例 用全主元素法求解线性方程组,计算过程保用全主元素法求解线性方程组,计算过程保留三位小数留三位小数解解:例例2.32.3二、全主元素法举例由回代过程得解由回代过程得解注意解的次序注意解的次序二、全主元素法举例 例例2.32.3的计算结果表明,全主元素法的精度略优的计算结果表明,全主元素法的精度略优于列主元素法,这是由于全主元素法是在全体系数中于列主元素法,这是由于全主元素法是在全体系数中选主元,故它对控制舍入误差比较有效。选主元,故它对控制舍入误差比较有效。但全主元素法在计算过程中,需同时作行与列
13、但全主元素法在计算过程中,需同时作行与列的互换,因而程序比较复杂,计算时间较长。列主元的互换,因而程序比较复杂,计算时间较长。列主元素法的精度虽稍低于全主元素法,但其计算简单,工素法的精度虽稍低于全主元素法,但其计算简单,工作量大为减少,且计算经验与理论分析均表明,它与作量大为减少,且计算经验与理论分析均表明,它与全主元素法同样具有良好的数值稳定性,故列主元素全主元素法同样具有良好的数值稳定性,故列主元素法是求解中小型稠密线性方程组的最好方法之一。法是求解中小型稠密线性方程组的最好方法之一。二、全主元素法举例1.1.用高斯消元法解方程组(取用高斯消元法解方程组(取3 3位小数)位小数)2.2.用列主元素法解方程组:用列主元素法解方程组:作 业作 业AX=b直接法直接法迭代法迭代法是是列主元列主元消去法消去法Gauss消去法消去法全主元全主元消去法消去法否否是是LU分解法分解法追赶法追赶法A对称对称且正定且正定平方根法平方根法A三对三对角矩阵角矩阵是是改进平改进平方根法方根法知识结构框图知识结构框图
限制150内