数值分析解线性代数方程组的直接解法.ppt

《数值分析解线性代数方程组的直接解法.ppt》由会员分享，可在线阅读，更多相关《数值分析解线性代数方程组的直接解法.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值分析数值分析数值分析数值分析第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现第三节第三节 用矩阵分解法求解线性方程组用矩阵分解法求解线性方程组第四节第四节 误差分析和解的精度改进误差分析和解的精度改进第五节第五节 大型稀疏方程组的迭代法大型稀疏方程组的迭代法第三章第三章 线性代数方程组的数值解法线性代数方程组的数值解法第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理第六节第六节 极小化方法极小化方法数值分析数值分析数值分析数值分析线性代数方程组的一般形式线性代数方程组的一般形式第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理数值分析

2、数值分析数值分析数值分析数值分析数值分析数值分析数值分析MATLAB实现实现:x=Ab数值分析数值分析数值分析数值分析 数值求解方法有以下三条途径（三种框架）数值求解方法有以下三条途径（三种框架）迭代法：构造迭代格式，产生迭代序列，通过无限迭代法：构造迭代格式，产生迭代序列，通过无限 次迭代过程求解。有限次截断得近似解。次迭代过程求解。有限次截断得近似解。极小化方法：构造二次模函数，用迭代过程求二次极小化方法：构造二次模函数，用迭代过程求二次 模函数的极小化问题，即变分法（经模函数的极小化问题，即变分法（经 n次运算，理论上得精确解）要求次运算，理论上得精确解）要求A 对称正定对称正定(S.P

3、.D)直接法：利用直接法：利用GaussGauss消元或矩阵分解，通过有限次运消元或矩阵分解，通过有限次运 算可求出精确解。算可求出精确解。数值分析数值分析数值分析数值分析 第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现数值分析数值分析数值分析数值分析 A b U g数值分析数值分析数值分析数值分析三三角角形形方方程程组组包包括括上上三三角角形形方方程程组组和和下下三三角角形形方方程程组组，是是最最简简单单的的线线性性方方程程组组之之一一。上上三角方程组的一般形式是三角方程组的一般形式是：一、三角形方程组的解法一、三角形方程组的解法数值分析数值分析数值分析数值分析数值分析数值分

4、析数值分析数值分析 为求解上三角方程组，从最后一个方程入手，先为求解上三角方程组，从最后一个方程入手，先解出解出 xn=bn/ann,然后按方程由后向前的顺序，从方然后按方程由后向前的顺序，从方程中依次解出程中依次解出xn-1,xn-2,x1。这样就完成了上三角方这样就完成了上三角方程组的求解过程。这个过程被称为回代过程其计算步程组的求解过程。这个过程被称为回代过程其计算步骤如下：骤如下：数值分析数值分析数值分析数值分析 function X=backsub(A,b)%InputA is an nn upper-triangular nonsingullar matrix%-b is an n

5、1 matrix%OutputX is the solution to the system AX=b函数名函数名返回变量返回变量参数表参数表n=length(b);X=zeros(n,1);X(n)=b(n)/A(n,n);for i=n-1:-1:1 X(i)=(b(i)-A(i,i+1:n)*X(i+1:n)/A(i,i);endA的第的第i行、第行、第i+1到到n列元素列元素构成的行向量构成的行向量数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析 高斯消元法是一个古老的直接法高斯消元法是一个古老的直接法,由它改进得到由它改进得到的选主元法

6、的选主元法,是目前计算机上常用于求低阶稠密矩阵是目前计算机上常用于求低阶稠密矩阵方程组的有效方法方程组的有效方法,其特点就是通过消元将其特点就是通过消元将一般线性一般线性方程组方程组的求解问题转化为的求解问题转化为三角方程组三角方程组的求解问题。的求解问题。高斯消元法的求解过程高斯消元法的求解过程,可大致分为两个阶段可大致分为两个阶段:首先首先,把原方程组化为上三角形方程组把原方程组化为上三角形方程组,称之为称之为“消消元元”过程过程;然后然后,用逆次序逐一求出上三角方程组用逆次序逐一求出上三角方程组(原原方程组的等价方程组方程组的等价方程组)的解的解,称之为称之为“回代回代”过程过程.高斯高

7、斯“消消元元”过程过程可通过矩阵运算来实现。具可通过矩阵运算来实现。具体过程如下：体过程如下：二、高斯消元法二、高斯消元法数值分析数值分析数值分析数值分析解：解：数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析将方程组将方程组Ax=b的系数矩阵与右端项合并为的系数矩阵与右端项合并为数值分析数值分析数值分析数值分析 数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析进行到第进行到第k步消元时步消元时数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析 用回代过程求解上三角方程组，即可得解向量用回代过程求解上三角方程组，即可

8、得解向量(x1*,x2*,xn*)T.数值分析数值分析数值分析数值分析求解的全过程包括两个步骤：消元和回代求解的全过程包括两个步骤：消元和回代2.2.回代求解回代求解1.1.顺序消元顺序消元数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析 消元过程全部完成后，原来的二维数组中存放的消元过程全部完成后，原来的二维数组中存放的元素实际上是一个新的矩阵，记为元素实际上是一个新的矩阵，记为数值分析数值分析数值分析数值分析function X=gauss(A,b)%InputA is an nn nonsingullar matrix%-b is an n1 matrix%OutputX

9、 is the solution to the system AX=bMATLAB For Gaussian Eliminationn n=size(A);%确定确定A的维数的维数X=zeros(n,1);for k=1:n-1 for i=k+1:n%消元过程消元过程 m=A(i,k)/A(k,k);%A(k,k)0 A(i,k+1:n)=A(i,k+1:n)-m*A(k,k+1:n);b(i)=b(i)-m*b(k);endendX=backsub(A,b);%回代求解回代求解数值分析数值分析数值分析数值分析function X=gauss(A,b)%InputA is an nn non

10、singullar matrix%-b is an n1 matrix%OutputX is the solution to the system AX=bMATLAB For Gaussian Eliminationn n=size(A);%确定确定A的维数的维数X=zeros(n,1);for k=1:n-1 for i=k+1:n%消元过程消元过程 A(i,k)=A(i,k)/A(k,k);%A(k,k)0 A(i,k+1:n)=A(i,k+1:n)-A(i,k)*A(k,k+1:n);b(i)=b(i)-A(i,k)*b(k);endendX=backsub(A,b);%回代求解回代求

11、解数值分析数值分析数值分析数值分析 高斯消元法的计算量分析高斯消元法的乘除总运算分析为分析为消元次数消元次数k k 消元乘法次数消元乘法次数 消元除法次数消元除法次数 回代乘除法次数回代乘除法次数 1 n(n-1)n-1 1 n(n-1)n-1 2 (n-1)(n-2)n-2 2 (n-1)(n-2)n-2 .k (n-k+1)(n-k)n-k k (n-k+1)(n-k)n-k .n-1 2*1 1 n-1 2*1 1 n(n+1)/2n(n+1)/2高斯消元法的计算量为高斯消元法的计算量为 乘乘 除除 回代回代 当当 n n 充分大时为充分大时为 N Nn n3 3/3/3数值分析数值分析

12、数值分析数值分析 消元法是解线性方程组的基本方法，具有消元法是解线性方程组的基本方法，具有计算简单的优点，但有时由于主元过小，使得计算简单的优点，但有时由于主元过小，使得计算结果严重失真计算结果严重失真,实际中常采用选主元高斯消实际中常采用选主元高斯消元法。元法。数值分析数值分析数值分析数值分析例例4:讨论下面方程组的解法讨论下面方程组的解法0.0001x1+x2=1 x1+x2=2假设求解是在四位浮点十进制数假设求解是在四位浮点十进制数的计算机上进行的计算机上进行0.1000 10-3 x1+0.1000 101 x2=0.1000 1010.1000 101 x1 +0.1000 101

13、x2=0.2000 101 解解:本题用机器数系表示为本题用机器数系表示为 a11=0.0001,m21=a21/a11=1/0.0001=104,消元消元得得 回代解得回代解得 x2=1=1 ,x1=0=0 严重失真严重失真!(本题的准确解为本题的准确解为 x1=10000/9999,x2=9998/9999）a22(2)=0.1000 101-104 0.1000 101 =0.00001 105-0.1000 105 (对阶计算对阶计算)=-0.1000 105 0.1000 10-3 x1+0.1000 101 x2=0.1000 101 -0.1000 105 x2=-0.1000

14、105 主元主元a11过小过小数值分析数值分析数值分析数值分析 选主元基本思想选主元基本思想 用高斯消元法求解线性方程组时用高斯消元法求解线性方程组时,为避免小的主元为避免小的主元.在进在进行第行第k k步消元前步消元前,应该在第应该在第k k列元素列元素 (i=k,ni=k,n)中找出第中找出第一个出现的绝对值最大者一个出现的绝对值最大者,例如例如 ，再把第再把第i ik k个方程与第个方程与第k k个方程组进行交换个方程组进行交换,使使 成为主元成为主元.我们我们称这个过程为选主元称这个过程为选主元.由于只在第由于只在第k k列元素中选主元列元素中选主元,通常通常也称为也称为按列选主元按列

15、选主元.如果在第如果在第k k步消元前步消元前,在第在第k k个方程到第个方程到第n n个方程所有个方程所有的的x xk k到到x xn n的系数的系数 (i=k,n;j=k,ni=k,n;j=k,n)中中,找出绝对值找出绝对值最大者最大者,例如例如 三、选主元三、选主元高斯消元法高斯消元法数值分析数值分析数值分析数值分析再交换第再交换第k k,ikik两个方程和第两个方程和第k k,jkjk列列,使使 成为主元成为主元.称这个过程为称这个过程为完全选主元完全选主元.不论是哪种方式选出主元不论是哪种方式选出主元,而后再按上面介绍的计算步而后再按上面介绍的计算步骤进行消元的计算骤进行消元的计算,

16、一般都称为选主元的高斯消元法一般都称为选主元的高斯消元法.在在实际计算中实际计算中,常用按列选主元的高斯消元法常用按列选主元的高斯消元法.数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析算法算法 列主元高斯消元法解线性方程组列主元高斯消元法解线性方程组 Ax=bAx=b具体执行行交换要通过工作单元具体执行行交换要通过工作单元 T。数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析假设求解是在四假设求解是在四位浮点十进制数位浮点十进制数的计算机上进行的计算机上进行0.0001x1+x2=1 x1+x2=2将两个方程对调，得将两个方程对调，得 x1+x2=2 0.00

17、01x1+x2=1在四位浮点十进制数的计算机上在四位浮点十进制数的计算机上,上式为上式为 x1+x2=2 即即 x1+x2=2 (0.1000101-0.00001 101)x2=1 x2=1（1-0.0001)x2=1x1+x2=2消元，得消元，得解得：解得：x1=1，x2=1现在我们再用列主元法解例现在我们再用列主元法解例4数值分析数值分析数值分析数值分析例例5 5 用列主元消去法解方程组用列主元消去法解方程组解解 第一次消元对第一次消元对 因列主元素为因列主元素为a31(1),故先作行交换故先作行交换E E1 1 E E3 3,然后进行然后进行消元计算可得消元计算可得-0.002x1+2

18、x2+2x3 =0.4 x1+0.78125x2 =1.38163.996x1+5.5625x2+4x3=7.4178 -0.002 2 2 0.4 A(1)|b(1)=1 0.78125 0 1.3816 3.996 5.5625 4 7.4178 3.996 5.5625 4 7.4178 A(2)|b(2)=0 -0.61077 -1.0010 -0.47471 0 2.0029 2.0020 0.40371数值分析数值分析数值分析数值分析 由此回代由此回代,得得 x=(1.9272,-0.69841,0.90038)=(1.9272,-0.69841,0.90038)T T与精确与精确

19、解解 x=(1.9273,-0.69850,0.90042)=(1.9273,-0.69850,0.90042)T T相比较是比较准确相比较是比较准确的的.3.996 5.5625 4 7.4178A(3)|b(3)=0 2.0029 2.0020 0.40371 0 0 -0.39050 -0.35160 第二次消元对第二次消元对 A A(2)(2)|b b(2)(2),因列主元素为因列主元素为a32(2)(2),故先故先作行交换作行交换E E2 2 E E3 3,然后进行消元计算可得然后进行消元计算可得数值分析数值分析数值分析数值分析二版习题二版习题 P113-6（1）三三版版习题习题 P137-3（1）