线性方程组的数值解法省公共课一等奖全国赛课获奖课件.pptx
《线性方程组的数值解法省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《线性方程组的数值解法省公共课一等奖全国赛课获奖课件.pptx(114页珍藏版)》请在咨信网上搜索。
1、数值计算方法第二章 线性方程组数值解法第1页2/114第二章 线性方程组数值解法2.0 引引 言言2.1 Gauss消去法消去法2.2 矩阵三角分解矩阵三角分解2.3 QR分解和奇异值分解分解和奇异值分解第2页3/114 在在自自然然科科学学和和工工程程技技术术中中很很多多问问题题处处理理经经常常归归结结为为解解线线性代数方程组。性代数方程组。比如:电学中网络问题比如:电学中网络问题 用最小二乘法求试验数据曲线拟合问题用最小二乘法求试验数据曲线拟合问题 解非线性方程组问题解非线性方程组问题 用差分法或者有限元方法解常微分方程用差分法或者有限元方法解常微分方程 偏微分方程边值问题等偏微分方程边值
2、问题等都造成求解线性代数方程组。都造成求解线性代数方程组。2.0 引引 言言第3页4/114这些方程组系数矩阵大致分为两种这些方程组系数矩阵大致分为两种一个是低阶稠一个是低阶稠密矩阵密矩阵(比如,阶数大约为比如,阶数大约为150)另一个是大型稀疏矩阵另一个是大型稀疏矩阵(即矩阵阶数高且零元素较多即矩阵阶数高且零元素较多)2.0 引引 言言第4页5/114设有线性方程组设有线性方程组Ax=b,其中,其中 为非奇异阵,为非奇异阵,关于线性方程组数值解法普通有两类:关于线性方程组数值解法普通有两类:直接法与迭代法。直接法与迭代法。2.0 引引 言言第5页6/1141.直接法直接法 就就是是经经过过有
3、有限限步步算算术术运运算算,可可求求得得方方程程组组准准确确解解方方法法(若计算过程中没有舍入误差若计算过程中没有舍入误差)。但但实实际际计计算算中中因因为为舍舍入入误误差差存存在在和和影影响响,这这种种方方法法也也只只能求得线性方程组近似解。能求得线性方程组近似解。本章将阐述这类算法中最基本高斯消去法及其一些变形。本章将阐述这类算法中最基本高斯消去法及其一些变形。这这类类方方法法是是解解低低阶阶稠稠密密矩矩阵阵方方程程组组有有效效方方法法,近近十十几几年年来来直直接接法法在在求求解解含含有有较较大大型型稀稀疏疏矩矩阵阵方方程程组组方方面面取取得得了了较较大进展。大进展。2.0 引引 言言第6
4、页7/1142.迭代法迭代法 就是用某种极限过程去逐步迫近线性方程组准确解方法。就是用某种极限过程去逐步迫近线性方程组准确解方法。迭迭代代法法含含有有需需要要计计算算机机存存贮贮单单元元较较少少、程程序序设设计计简简单单、原原始始系系数数矩矩阵阵在在计计算算过过程程中中一一直直不不变变等等优优点点,但但存存在在收收敛敛性及收敛速度问题。性及收敛速度问题。迭迭代代法法是是解解大大型型稀稀疏疏矩矩阵阵方方程程组组(尤尤其其是是由由微微分分方方程程离离散后得到大型方程组散后得到大型方程组)主要方法。主要方法。第第6 6章介绍迭代法解线性方程组。章介绍迭代法解线性方程组。2.0 引引 言言第7页8/1
5、14 高斯高斯(Gauss)(Gauss)消去法是解线性方程组最惯用方法之一消去法是解线性方程组最惯用方法之一 它它基基本本思思想想是是经经过过逐逐步步消消元元(行行初初等等变变换换),把把方方程程组组化化为为系系数数矩矩阵阵为为三三角角形形矩矩阵阵同同解解方方程程组组,然然后后用用回回代代法法解解此三角形方程组(简单形式)得原方程组解。此三角形方程组(简单形式)得原方程组解。比如:比如:直接法基础直接法基础2.1 Gauss消去法消去法第8页9/114 下面讨论普通解下面讨论普通解n阶方程组高斯消去法。阶方程组高斯消去法。1.消去过程消去过程 将原方程组记为将原方程组记为 A(1)(1)x=
6、b(1)(1)其中其中A(1)(1)=(=(aij(1)(1)n n=(=(aij)n n ,b(1)(1)=b(1)(1)第一次消元。第一次消元。2.1 Gauss消去法消去法第9页10/1141.消去过程消去过程(1)(1)第一次消元。第一次消元。其中其中2.1 Gauss消去法消去法注注:若若a11(1)=0,则则在在第第1列列中中最最少少有有一一个个元元素素不不为为0,可可交交换换行后再消元行后再消元第10页11/114(2)(2)第第k次消元。次消元。2.1 Gauss消去法消去法第11页12/1141.消去过程消去过程(2)(2)第第k次消元。次消元。注:为降低计算量,令注:为降低
7、计算量,令 ,则则2.1 Gauss消去法消去法第12页13/1141.消去过程消去过程(3)(3)当当k=n 1时得时得完成第完成第n 1次消元后得到与原方程组等价三角形方程组次消元后得到与原方程组等价三角形方程组A(n)x=b(n)注:当注:当det(A)0时,显然有时,显然有aii(i)0,(i=1,n)称称aii(i)为主元素。为主元素。2.1 Gauss消去法消去法第13页14/1142.回代过程回代过程求解三角形方程组求解三角形方程组A(n)x=b(n),得到求解公式得到求解公式注:求解过程称为回代过程。注:求解过程称为回代过程。2.1 Gauss消去法消去法第14页15/1143
8、.算法设计算法设计令令 i=k+1,k+2,n2.1 Gauss消去法消去法输输入入A,n,epsFor(k=1 to n-1)for(i=k+1 to n)A(i,k)=A(i,k)/A(k,k)for(j=k+1 to n+1)A(i,j)=A(i,j)-A(i,k)*A(k,j)A(n,n+1)=A(n,n+1)/A(n,n)for(k=n 1 to 1 step-1)w=0for(j=k+1 to n)w=w+A(k,j)*A(j,n+1)A(k,n+1)=A(k,n+1)wA(k,n+1)=A(k,n+1)/A(k,k)第15页16/1143.算法设计算法设计function x=g
9、auss(a)m=size(a);n=m(1);for k=1:n-1 for i=k+1:n a(i,:)=a(i,:)-a(k,:)*a(i,k)/a(k,k);endendfor j=n:-1:1 a(j,n+1)=(a(j,n+1)-a(j,j+1:n)*a(j+1:n,n+1)/a(j,j)endx=a(1:n,n+1);2.1 Gauss消去法消去法输输入入A,n,epsFor(k=1 to n-1)for(i=k+1 to n)A(i,k)=A(i,k)/A(k,k)for(j=k+1 to n+1)A(i,j)=A(i,j)-A(i,k)*A(k,j)A(n,n+1)=A(n,
10、n+1)/A(n,n)for(k=n 1 to 1 step-1)w=0for(j=k+1 to n)w=w+A(k,j)*A(j,n+1)A(k,n+1)=A(k,n+1)wA(k,n+1)=A(k,n+1)/A(k,k)第16页17/1143.算法设计算法设计 i=k+1,k+2,n2.1 Gauss消去法消去法第17页18/1143.算法设计算法设计 在在Excel中中1A1B1C1D1E12A2B2C2D2E23A3B3C3D3E34A4B4C4D4E35=A1=B1=C1=D1=E16=B2-B1*A2/A1=C2-C1*A2/A1=D2-D1*A2/A1=E2-E1*A2/A17=
11、B3-B1*A3/A1=C3-C1*A3/A1=D3-D1*A3/A1=E3-E1*A3/A18=B4-B1*A4/A1=C4-C1*A4/A1=D4-D1*A4/A1=E4-E1*A4/A19=A5=B5=C5=D5=E510=B6=C6=D6=E611=C7-C6*B7/B6=D7-D6*B7/B6=E7-E6*B7/B612=C8-C6*B8/B6=D8-D6*B8/B6=E8-E6*B8/B613=A9=B9=C9=D9=E9=(E13-D13*F16-C13*F15-B13*F14)/A1314=B10=C10=D10=E10=(E14-D14*F16-C14*F15)/B1415=
12、C11=D11=E11=(E15-D15*F16)/C1516=D12-D11*C12/C11=E12-E11*C12/C11=E16/D162.1 Gauss消去法消去法第18页19/1141A1B1C1D1E12A2B2C2D2E23A3B3C3D3E34A4B4C4D4E35=A1=B1=C1=D1=E16=B2-B$1*$A2/$A$1=C2-C$1*$A2/$A$1=D2-D$1*$A2/$A$1=E2-E$1*$A2/$A$17=B3-B$1*$A3/$A$1=C3-C$1*$A3/$A$1=D3-D$1*$A3/$A$1=E3-E$1*$A3/$A$18=B4-B$1*$A4/$
13、A$2=C4-C$1*$A4/$A$1=D4-D$1*$A4/$A$1=E4-E$1*$A4/$A$19=A5=B5=C5=D5=E510=B6=C6=D6=E611=C7-C$6*$B7/$B$6=D7-D$6*$B7/$B$6=E7-E$6*$B7/$B$612=C8-C$6*$B8/$B$6=D8-D$6*$B8/$B$6=E8-E$6*$B8/$B$613=A9=B9=C9=D9=E9=(E13-D13*F16-C13*F15-B13*F14)/A1314=B10=C10=D10=E10=(E14-D14*F16-C14*F15)/B1415=C11=D11=E11=(E15-D15*
14、F16)/C1516=D12-D$11*$C12/$C$11=E12-E$11*$C12/$C$11=E16/D162.1 Gauss消去法消去法3.算法设计算法设计 在在Excel中中第19页20/1144.Gauss消去法计算量消去法计算量以乘除法次数为主以乘除法次数为主(1)消元过程:消元过程:第第k步时步时(n k)+(n k)(n k+1)=(n k)(n k+2)共有共有2.1 Gauss消去法消去法第20页21/1144.Gauss消去法计算量消去法计算量(1)消元过程:消元过程:(2)回代过程:回代过程:求求xi中中,乘乘ni次次,除除1 1次次,共共ni+1+1次次(i=1,
15、n1)共有共有2.1 Gauss消去法消去法第21页22/1144.Gauss消去法计算量消去法计算量(1)消元过程:消元过程:(2)回代过程:回代过程:(3)总次数为总次数为注注:当当n=20时时约约为为26702670次次,比比克克莱莱姆姆法法则则9.7 1020次次大大大降低。大降低。2.1 Gauss消去法消去法第22页23/1145.说明说明(1)若消元过程中出现若消元过程中出现akk(k)=0=0,则无法继续,则无法继续(2)若若akk(k)0 0,但但较较小小,则则小小主主元元做做除除数数将将产产生生大大误误差差(3)每每次次消消元元都都选选择择绝绝对对值值最最大大者者作作主主元
16、元,称称为为高高斯斯主主元元消去法消去法2.1 Gauss消去法消去法第23页24/1145.说明说明(4)通常第通常第k步选择步选择第第k列列主主对对角角元元以以下下元元素素绝绝对对值值最最大大者者作作主主元元(该该行行与第与第k行对调),称为列主元消去法。行对调),称为列主元消去法。2.1 Gauss消去法消去法第24页25/1145.说明说明【例例1】用舍入三位有效数字求解线性方程组】用舍入三位有效数字求解线性方程组(准确解是(准确解是x1=10.0,x2=1.00)解:解:1)不选主元不选主元GaussGauss消去法计算结果:消去法计算结果:x1=-10.0,x2=1.01,此解无效
17、;此解无效;2)按按列列选选主主元元GaussGauss消消去去法法计计算算结结果果:x1=10.0,x2=1.00.2.1 Gauss消去法消去法第25页26/1145.说明说明【例例2】求解线性方程组】求解线性方程组 和和(准确解是(准确解是x1=1.0,x2=1.0)2.1 Gauss消去法消去法第26页27/1145.说明说明(5)行标度化行标度化 当当线线性性方方程程组组系系数数矩矩阵阵元元素素大大小小相相差差很很大大时时,则则可可能能引引进进因因丢丢失失有有效效数数字字而而产产生生误误差差,而而且且舍舍入入误误差差影影响响严严重重,即使用即使用GaussGauss主元消去法得到解也
18、不可靠主元消去法得到解也不可靠 为为防防止止这这一一问问题题,可可将将系系数数矩矩阵阵行行元元素素按按百百分分比比增增减减以以使元素改变减小使元素改变减小2.1 Gauss消去法消去法第27页28/1145.说明说明(5)行标度化行标度化 如如用用每每行行元元素素最最大大模模除除该该行行各各元元素素,使使它它们们模模都都小小于于1 1,这叫行标度化,其目标是要找到真正主元,这叫行标度化,其目标是要找到真正主元 消消元元过过程程仍仍是是对对原原方方程程组组进进行行,只只不不过过在在GaussGauss列列主主元元消去法算法中,按列选主元消去法算法中,按列选主元ck时,应修改为时,应修改为其中其中
19、2.1 Gauss消去法消去法第28页29/1146.列主元消去法算法列主元消去法算法输输入入A,n,epsFor(k=1 to n-1)选选主元主元A(I0,k)确定行号确定行号p=A(I0,k)若若|p|=epsText=1,退出循,退出循环环若若I0 kT换换行(行(I0 k)消元消元若若|A(n,n)|A(I0,k)|TI0=ifor(i=k+1 to n)A(i,k)=A(i,k)/A(k,k)for(j=k+1 to n+1)A(i,j)=A(i,j)-A(i,k)*A(k,j)A(n,n+1)=A(n,n+1)/A(n,n)for(k=n 1 to 1 step-1)w=0for
20、(j=k+1 to n)w=w+A(k,j)*A(j,n+1)A(k,n+1)=A(k,n+1)wA(k,n+1)=A(k,n+1)/A(k,k)for(j=k to n)n=A(k,j),A(k,j)=A(I0,j),A(I0,j)=n2.1 Gauss消去法消去法第29页30/1146.列主元消去法算法列主元消去法算法function x=gaussa(a)m=size(a);n=m(1);x=zeros(n,1);for k=1:n-1 c,i=max(abs(a(k:n,k);q=i+k-1;if q=k d=a(q,:);a(q,:)=a(k,:);a(k,:)=d end for
21、i=k+1:n a(i,:)=a(i,:)-a(k,:)*a(i,k)/a(k,k)endendfor j=n:-1:1 x(j)=(a(j,n+1)-a(j,j+1:n)*x(j+1:n)/a(j,j)end2.1 Gauss消去法消去法输输入入A,n,epsFor(k=1 to n-1)选选主元主元A(I0,k)确定行号确定行号p=A(I0,k)若若|p|=epsText=1,退出循,退出循环环若若I0 kT换换行(行(I0 k)消元消元若若|A(n,n)|行标行标k时时,lkm=0=0 j=k,k+1,.,nk=1,2,.,n2.2 矩阵三角分解矩阵三角分解第35页36/1142.2.1
22、 LU分解和分解和LDU分解分解2.LU分解分解设设A各阶次序主子式不为各阶次序主子式不为0,且,且A=LU,即,即(2)(2)主对角线下边:当行标主对角线下边:当行标m 列标列标k时时,umk=0 i=k+1,k+2,.,nk=1,2,.,n1欲求欲求lik和和ukj2.2 矩阵三角分解矩阵三角分解第36页37/1142.2.1 LU分解和分解和LDU分解分解2.LU分解分解(1)(1)主对角线主对角线(含含)上边上边:当列标当列标m行标行标k时时,lkm=0 j=k,k+1,.,nk=1,2,.,n(2)(2)主对角线下边:当行标主对角线下边:当行标m 列标列标k时,时,umk=0 i=k
23、+1,k+2,.,nk=1,2,.,n1设设k=1,=1,a1 1j=l1111u1 1j u1 1j=a1 1j j=1,2,.,n ai1 1=li1 1u1111 li1 1=ai1 1/u1111 i=2,3,.,n欲求欲求lik和和ukj2.2 矩阵三角分解矩阵三角分解第37页38/1142.2.1 LU分解和分解和LDU分解分解2.LU分解分解普通地,普通地,最终:最终:u11u12.u1n第第1步步l21u22.u2n第第2步步l31l32.ln1ln2unn第第n步步2.2 矩阵三角分解矩阵三角分解第38页39/1142.2.1 LU分解和分解和LDU分解分解3.求解方程组求解
24、方程组下三角下三角 Ly=b:上三角上三角 Ux=y:2.2 矩阵三角分解矩阵三角分解第39页40/1142.2.1 LU分解和分解和LDU分解分解3.求解方程组求解方程组【例【例3】用杜丽特尔法解方程组】用杜丽特尔法解方程组解:解:2.2 矩阵三角分解矩阵三角分解第40页41/1142.2.1 LU分解和分解和LDU分解分解3.求解方程组求解方程组【例【例3】用杜丽特尔法解方程组】用杜丽特尔法解方程组解:解:2.2 矩阵三角分解矩阵三角分解第41页42/1142.2.1 LU分解和分解和LDU分解分解3.求解方程组求解方程组【例【例3】用杜丽特尔法解方程组】用杜丽特尔法解方程组解:解:2.2
25、 矩阵三角分解矩阵三角分解第42页43/1142.2.1 LU分解和分解和LDU分解分解3.求解方程组求解方程组【例【例3】用杜丽特尔法解方程组】用杜丽特尔法解方程组解:解:2.2 矩阵三角分解矩阵三角分解第43页44/1142.2.1 LU分解和分解和LDU分解分解3.求解方程组求解方程组【例【例3】用杜丽特尔法解方程组】用杜丽特尔法解方程组解:解:2.2 矩阵三角分解矩阵三角分解第44页45/1142.2.1 LU分解和分解和LDU分解分解3.求解方程组求解方程组【例【例3】用杜丽特尔法解方程组】用杜丽特尔法解方程组解:解:2.2 矩阵三角分解矩阵三角分解第45页46/1142.2.1 L
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性方程组 数值 解法 公共课 一等奖 全国 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。