计算方法第六章解线性方程组的直接法.ppt
《计算方法第六章解线性方程组的直接法.ppt》由会员分享,可在线阅读,更多相关《计算方法第六章解线性方程组的直接法.ppt(74页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、AXAX=b b(3.1)第三章第三章 解线性方程组的直接法解线性方程组的直接法1 1 1 1 高斯消去法高斯消去法高斯消去法高斯消去法1 1三角形方程组的解法三角形方程组的解法(3.2)(3.3)首先将首先将A化为上三角阵化为上三角阵,再回代求解,再回代求解。=(一一)高斯消去法的求解过程高斯消去法的求解过程,可分为两个阶段可分为两个阶段:首先首先,把原方程组化为上三角形方程组把原方程组化为上三角形方程组,称之为称之为 “消元消元”过程过程;然后然后,用逆次序逐一求出三角方程组用逆次序逐一求出三角方程组(原方程组的原方程组的等价方程组等价方程组)的解的解,并称之为并称之为“回代回代”过程过程
2、.下面分别写出下面分别写出“消元消元”和和“回代回代”两个过程的两个过程的计算步骤计算步骤.记记Step 1:设设 ,计算因子,计算因子将增广矩阵第将增广矩阵第 i 行行 mi1 第第1 1行,得到行,得到其中其中Step k:设设 ,计算因子,计算因子共进行共进行?步步n 1且计算且计算 若若A的所有的所有顺序主子式顺序主子式 均不为均不为0,则高斯消元,则高斯消元无需换行即可进行到底,得到惟一解。无需换行即可进行到底,得到惟一解。利用高斯消元法求解方程组利用高斯消元法求解方程组:解:解:1.2 1.2 高斯消元法高斯消元法_ _例题分析例题分析利用利用得得利用利用得得利用利用得得显然,方程
3、组显然,方程组(4)(4)与与(1)(1)是等价的,其系数矩阵为上三角状是等价的,其系数矩阵为上三角状的,易于求解的,易于求解.称以上过程为高斯消去法的称以上过程为高斯消去法的消去过程消去过程.通过通过方程组方程组(4)(4)的回代求解,可以得到准确解为的回代求解,可以得到准确解为这一过程为高斯消去法的这一过程为高斯消去法的回代过程回代过程。消元公式消元公式消元公式消元公式回代公式回代公式回代公式回代公式1.3 1.3 高斯消元法高斯消元法_ _选主元消去法选主元消去法Gauss消元法第消元法第 k 次消元是用第次消元是用第 k 个方程个方程主元素及其选取问题主元素及其选取问题来消去第来消去第
4、 k+1,n 个方程中的个方程中的 xk,条件是条件是 .是实现第是实现第 k 次消元的关键元素,称为第次消元的关键元素,称为第k次消去的主元次消去的主元.Gauss消元法存在的问题是消元法存在的问题是:例:例:单精度解方程组单精度解方程组/*精确解为精确解为 和和 */8个个8个个用用Gaussian Elimination计算:计算:8个个用小主元用小主元10-9作作除数,致使其它除数,致使其它元素的数量级大元素的数量级大大增加,舍入误大增加,舍入误差的扩散将准确差的扩散将准确解淹没了。解淹没了。1.3 1.3 高斯消元法高斯消元法_ _选主元消去法选主元消去法全主元消去法全主元消去法每一
5、步选绝对值最大的元素为主元素,保证每一步选绝对值最大的元素为主元素,保证 。Step k:选取选取 If ik k then 交换第交换第 k 行与第行与第 ik 行行;If jk k then 交换第交换第 k 列与第列与第 jk 列列;消元消元注注注注:列交换改变了列交换改变了 xi 的顺序,须记录的顺序,须记录交换次序交换次序,解完后再,解完后再换回来。换回来。算法:算法:1.1.消元过程,对消元过程,对 (1)(1)选主元,找选主元,找 使得使得 (2)(2)若若 ,则停止,推出,则停止,推出 (3)(3)若若 ,则换行,则换行,(4)(4)消元,对消元,对 有有 考虑在整个矩阵范围选
6、主元,这就是所谓的全主元考虑在整个矩阵范围选主元,这就是所谓的全主元消去法,此时要注意的是,在做列的变换时,要同消去法,此时要注意的是,在做列的变换时,要同时记录当前变量的次序,以免自变量的含义不清。时记录当前变量的次序,以免自变量的含义不清。有有回代过程:回代过程:(1)(1)若若 ,则停止,则停止(2)(2)对对例:例:注注注注:列主元法没有全主元法稳定。列主元法没有全主元法稳定。例:例:列主元消去法列主元消去法 在计算机上实现全主元素消去法意味着进行数的比较操作,在计算机上实现全主元素消去法意味着进行数的比较操作,选全主元素法需要相当多的计算时间,因此常采用选全主元素法需要相当多的计算时
7、间,因此常采用局部局部选主选主元素的方法元素的方法.省去换列的步骤,每次仅选一列中最大的元。省去换列的步骤,每次仅选一列中最大的元。例题分析(例题分析(GuassGuass全选主元法全选主元法)精确解为:精确解为:x1=1.9273,x2=-0.698496,x3=0.9004233例题分析(例题分析(GuassGuass列选主元法列选主元法)精确解为:精确解为:x x1 1=1.9273,=1.9273,x x2 2=-0.698496,x=-0.698496,x3 3=0.9004233=0.9004233列主元消去法计算步骤:列主元消去法计算步骤:1、输入矩阵阶数输入矩阵阶数n,增广矩阵
8、增广矩阵 A(n,n+1);2、对于对于(1)按列选主元:选取按列选主元:选取 l 使使(2)如果如果 ,交换,交换 A(n,n+1)的第的第k行与底行与底l 行元素行元素(3)消元计算消元计算 :3、回代计算回代计算4 4无回代过程的主元消去法无回代过程的主元消去法算法:算法:第一步:选主元,在第一列中选绝对值最大的元素,设第第一步:选主元,在第一列中选绝对值最大的元素,设第k行为主元行,行为主元行,将主元行换至第一行,将第一个方程中将主元行换至第一行,将第一个方程中x1的系数变为的系数变为1,并从,并从 其余其余n 1n 1个方程中消去个方程中消去x1。第二步:在第二列后第二步:在第二列后
9、n 1个元素中选主元,将第二个方程中个元素中选主元,将第二个方程中x2的的 系数变为系数变为1,并从其它,并从其它n n 1 1个方程中消去个方程中消去x2。第第k步:在第步:在第k列后列后n k个元素中选主元,换行,将第个元素中选主元,换行,将第k个方程个方程xk的系数的系数 变为变为1,从其它,从其它n-1n-1个方程中消去变量个方程中消去变量xk,消元公式为:消元公式为:对对k=1,2,按上述步骤进行到第按上述步骤进行到第n步后,方程组变为:步后,方程组变为:即为所求的解即为所求的解5无回代消去法的应用无回代消去法的应用(1)解线性方程组系解线性方程组系设要解的线性方程组系为:设要解的线
10、性方程组系为:AX=b1,AX=b2,AX=bm上述方程组系可以写为上述方程组系可以写为AX=B=(b1,bm)因此因此X=A-1B 即为线性方程组系的解。即为线性方程组系的解。在计算机上只需要增加几组右端常数项的存贮单元,在计算机上只需要增加几组右端常数项的存贮单元,其结构和解一个方程组时一样。其结构和解一个方程组时一样。行行系数系数右端右端(2)求逆矩阵求逆矩阵设设A=(aij)n n是非奇矩阵是非奇矩阵,A 0,且令且令由于由于 AA-1=AX=I因此,求因此,求A-1的问题相当于解下列线性方程组的问题相当于解下列线性方程组相当于相当于(1)中中m=n,B=I 的情形。的情形。(3)求行
11、列式的值求行列式的值用高斯消去法将用高斯消去法将 A化成化成2 2 解三对角方程组的追赶法解三对角方程组的追赶法 高斯消元法的矩阵形式高斯消元法的矩阵形式:Step 1:3 矩阵的三角分解及其在解方程组中的应用矩阵的三角分解及其在解方程组中的应用记记 L1=L11=记记 于是于是Step n 1:Lk=其中其中记为记为L记记 U=由上述讨论可知,高斯消去法实质上产生了一个将系数由上述讨论可知,高斯消去法实质上产生了一个将系数矩阵矩阵A分解为上三角分解为上三角阵与下三角阵相乘的因式分解。阵与下三角阵相乘的因式分解。若若A的所有顺序主子式的所有顺序主子式 均不为均不为0,则,则 A 的的 LU 分
12、解唯一分解唯一(其中(其中 L 为为单位单位下三角阵)。下三角阵)。设有方程组设有方程组AX=b,并设并设A=LU,于是于是 AX=LUX=b令令UX=Y,则则 LY=b.于是求解于是求解AX=b的的问题等价于求解两个问题等价于求解两个方程组方程组UX=Y和和LY=b(1)利用顺推过程解)利用顺推过程解LY=b,其计算公式为其计算公式为:(2)利用回代过程解)利用回代过程解UX=Y,其计算公式为其计算公式为:定理定理1:(矩阵的三角分解)设:(矩阵的三角分解)设A为为n n实矩阵,如果实矩阵,如果解解AX=b用高斯消去法能够完成(限制不进行行的交用高斯消去法能够完成(限制不进行行的交换,即换,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算方法 第六 线性方程组 直接
限制150内