高斯消元法及其计算机实现.ppt

《高斯消元法及其计算机实现.ppt》由会员分享，可在线阅读，更多相关《高斯消元法及其计算机实现.ppt（40页珍藏版）》请在三一办公上搜索。

1、第二节 高斯消元法及其计算机实现,第三节 用矩阵分解法求解线性方程组,第四节 误差分析和解的精度改进,第五节 大型稀疏方程组的迭代法,第三章 线性代数方程组的数值解法,第一节 求解线性代数方程组的基本定理,第六节 极小化方法,线性代数方程组的一般形式,第一节 求解线性代数方程组的基本定理,MATLAB实现:x=Ab,数值求解方法有以下三条途径（三种框架）直接法：利用Gauss消元或矩阵分解，通过有限次运算 可求出精确解。,迭代法：构造迭代格式，产生迭代序列，通过无限 次迭代过程求解。有限次截断得近似解。,极小化方法：构造二次模函数，用迭代过程求二次 模函数的极小化问题，即变分法（经n 次运算，

2、理论上得精确解）要求A 对称正定(S.P.D),第二节 高斯消元法及其计算机实现,A b,U g,三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一。上三角方程组的一般形式是：,一、三角形方程组的解法,为求解上三角方程组，从最后一个方程入手，先解出 xn=bn/ann,然后按方程由后向前的顺序，从方程中依次解出xn-1,xn-2,x1。这样就完成了上三角方程组的求解过程。这个过程被称为回代过程其计算步骤如下：,function X=backsub(A,b)%InputA is an nn upper-triangular nonsingullar matrix%-b is

3、 an n1 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);end,A的第i行、第i+1到n列元素构成的行向量,高斯消元法是一个古老的直接法,由它改进得到的选主元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题。,高斯消元法的求解过程,可大致分为两个阶

4、段:首先,把原方程组化为上三角形方程组,称之为“消元”过程;然后,用逆次序逐一求出上三角方程组(原方程组的等价方程组)的解,称之为“回代”过程.,高斯“消元”过程可通过矩阵运算来实现。具体过程如下：,二、高斯消元法,解：,将方程组Ax=b的系数矩阵与右端项合并为,进行到第k步消元时,用回代过程求解上三角方程组，即可得解向量(x1*,x2*,xn*)T.,求解的全过程包括两个步骤：消元和回代1.顺序消元,2.回代求解,消元过程全部完成后，原来的二维数组中存放的元素实际上是一个新的矩阵，记为,function X=gauss(A,b)%InputA is an nn nonsingullar ma

5、trix%-b is an n1 matrix%OutputX is the solution to the system AX=b,MATLAB For Gaussian Elimination,n 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);endend,X=backsub(A,b);%回代求解,function X=gauss(A,b)%InputA is an

6、 nn nonsingullar matrix%-b is an n1 matrix%OutputX is the solution to the system AX=b,MATLAB For Gaussian Elimination,n 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);endend,X=backsub(A,b);%回代求解,

7、高斯消元法的计算量分析高斯消元法的乘除总运算分析为消元次数k 消元乘法次数 消元除法次数 回代乘除法次数 1 n(n-1)n-1 2(n-1)(n-2)n-2.k(n-k+1)(n-k)n-k.n-1 2*1 1 n(n+1)/2高斯消元法的计算量为,乘 除 回代,当 n 充分大时为 Nn3/3,消元法是解线性方程组的基本方法，具有计算简单的优点，但有时由于主元过小，使得计算结果严重失真,实际中常采用选主元高斯消元法。,例4:讨论下面方程组的解法,0.0001x1+x2=1 x1+x2=2,假设求解是在四位浮点十进制数的计算机上进行,0.100010-3 x1+0.1000 101 x2=0.

8、1000 1010.1000 101 x1+0.1000 101 x2=0.2000 101,解:本题用机器数系表示为,a11=0.0001,m21=a21/a11=1/0.0001=104,消元得,回代解得 x2=1,x1=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.100010-3 x1+0.1000 101 x2=0.1000 101-0.1000 105 x2=-0.1000 105,主元a1

9、1过小,选主元基本思想 用高斯消元法求解线性方程组时,为避免小的主元.在进行第k步消元前,应该在第k列元素(i=k,n)中找出第一个出现的绝对值最大者,例如，再把第ik个方程与第k个方程组进行交换,使 成为主元.我们称这个过程为选主元.由于只在第k列元素中选主元,通常也称为按列选主元.,如果在第k步消元前,在第k个方程到第n个方程所有的xk到xn的系数(i=k,n;j=k,n)中,找出绝对值最大者,例如,三、选主元高斯消元法,再交换第k,ik两个方程和第k,jk列,使 成为主元.称这个过程为完全选主元.,不论是哪种方式选出主元,而后再按上面介绍的计 算步骤进行消元的计算,一般都称为选主元的高斯

10、消元法.在实际计算中,常用按列选主元的高斯消元法.,算法 列主元高斯消元法解线性方程组 Ax=b,具体执行行交换要通过工作单元 T。,假设求解是在四位浮点十进制数的计算机上进行,0.0001x1+x2=1 x1+x2=2,将两个方程对调，得 x1+x2=2 0.0001x1+x2=1,在四位浮点十进制数的计算机上,上式为 x1+x2=2 即 x1+x2=2(0.1000101-0.00001 101x2=1 x2=1,（1-0.0001)x2=1,x1+x2=2,消元，得,解得：x1=1，x2=1,现在我们再用列主元法解例4,例5 用列主元消去法解方程组,解 第一次消元对,因列主元素为a31(1),故先作行交换E1 E3,然后进行消元计算可得,由此回代,得x=(1.9272,-0.69841,0.90038)T与精确解 x=(1.9273,-0.69850,0.90042)T相比较是比较准确的.,第二次消元对A(2)|b(2),因列主元素为a32(2),故先作行交换E2 E3,然后进行消元计算可得,二版习题 P113-6（1），8（1）,三版习题 P137-3（1），5（1）,