线性代数计算方法.ppt

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

1、第3章 线性代数计算方法 计算方法第第3章章线性代数计算方法线性代数计算方法1高斯消去法高斯消去法3解实三对角线性方程组的追赶法解实三对角线性方程组的追赶法4矩阵的三角分解矩阵的三角分解5行列式和逆矩阵的计算行列式和逆矩阵的计算7迭代法的收敛性迭代法的收敛性8矩阵的特征值与特征向量的计算矩阵的特征值与特征向量的计算2高斯高斯约当消去法约当消去法6迭代法迭代法第3章 线性代数计算方法 计算方法在自然科学和工程技术中很多问题的解决在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。常常归结为解线性代数方程组。例如例如:电学中的网络问题，电学中的网络问题，船体数学放样中建立三次样条函数问

2、题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题等用最小二乘法求实验数据的曲线拟合问题等第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法直接法直接法:经过有限次运算后可求得方程组精确解的方法经过有限次运算后可求得方程组精确解的方法(不计舍入误差不计舍入误差!)!)迭代法：迭代法：从解的某个近似值出发，通过构造一个无穷序列从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法去逼近精确解的方法(一般有限步内得不到精确一般有限步内得不到精确解解)解线性方程组的两类方法解线性方程组的两类方法:第3章 线性代数计算方法 计算方法1高斯消去法高斯消去

3、法一、高斯消去法一、高斯消去法第3章 线性代数计算方法 计算方法且aii0,i=1,2,nAXB第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法高斯消去法高斯消去法思思路路首先将方程组首先将方程组Ax=b 化为上三角方程组化为上三角方程组，此过程称为此过程称为消去过程消去过程，再求解上三角方程，再求解上三角方程组，此过程称为组，此过程称为回代过程回代过程.第3章 线性代数计算方法 计算方法-2-3-2例：例：第3章 线性代数计算方法 计算方法第第2 2行：计算比例因子行：计算比例因子（1）消去过程：）消去过程：第一步第一步：消消，设设第第2

4、 行行 -l21 第第1 1行行，得到：，得到：消去法的数值计算过程：消去法的数值计算过程：消去消去第3章 线性代数计算方法 计算方法-1-1第3章 线性代数计算方法 计算方法第第 i 行行 -li1 第第1 1行行，得到：，得到：第第i 行行：计算因子计算因子第第2 2行：行：第第 n 行：消去行：消去第3章 线性代数计算方法 计算方法第第k步：步：消去消去共进行共进行 n 1步，得到步，得到设设 ，计算因子，计算因子且计算且计算第3章 线性代数计算方法 计算方法消元过程总体流程：消元过程总体流程：对于对于对于对于做做做做对于对于做做第3章 线性代数计算方法 计算方法（2）回代过程：）回代过

5、程：第3章 线性代数计算方法 计算方法二、二、选主元消去法选主元消去法为避免这种情况的发生，可通过交换方程的次序，为避免这种情况的发生，可通过交换方程的次序，选取绝对值大的元素作主元。选取绝对值大的元素作主元。基于这种思想导出了主元素法基于这种思想导出了主元素法u 在高斯消去法消去过程中可能出现 的情 况，这时高斯消去法将无法进行；u 即使主因素 但很小，其作除数，也会导 致其它元素数量级的严重增长和舍误差的扩散。第3章 线性代数计算方法 计算方法例如：用高斯消去法求解下列方程组(用四位有效数字计算):-105x2=0.5999959999第3章 线性代数计算方法 计算方法化简可得 x2=0.

6、6000回代求得 x1=105(0.6-0.6000)=0而方程组的解应为 x1=0.4000 x2=0.6000 第3章 线性代数计算方法 计算方法 显然用上述方法求出的解x1与方程组的实际解相差很大。若改变两个方程的顺序,即 x1+x2=1 10-5 x1+x2=0.6 -10-5得 (1.000-1.00010-5)x2=0.6-1.00010-5 0.99999x2=0.59999 化简得 x2=0.6000 回代求得 x1=(1-0.6000)=0.4000 x2=0.5999959999第3章 线性代数计算方法 计算方法 高斯主元素消去法是顺序消去法的一种改进。它的基本思想是在逐次

7、消元时总是选绝对值最大的元素(称之为主元)做除数，按顺序消去法的步骤消元。这里主要介绍求解线性方程组最常用的列主元素消去法和全主元素消去法。第3章 线性代数计算方法 计算方法所所谓谓列列主主元元素素消消去去法法就就是是在在每每一一步步消消元元过过程程中中取取系系数数子子矩矩阵阵的的第第一一列列元元素素中中绝绝对对值值最最大大者者作作主主元元。对对线性方程组进行线性方程组进行n-1次消元后，可得到上三角形方程组次消元后，可得到上三角形方程组v列主元消去法列主元消去法这种方法称为这种方法称为列主元列主元GaussGauss消去法消去法。第3章 线性代数计算方法 计算方法 取四位有效数字计算。解 中

8、-18为主元,交换和得 例1 用列主元素消去法解方程组 第3章 线性代数计算方法 计算方法 +12/18,+1/18得 第二列消元时,主元为1.167,交换方程和得 第3章 线性代数计算方法 计算方法 +1/1167得 回代求得 x1=1.000,x2=2.000,x3=3.001方程组的实际解 x1=1,x2=2,x3=3第3章 线性代数计算方法 计算方法开始开始输入输入FT结束结束输出输出FT找找列列最大值最大值当前当前列列换行换行消元消元回代、求解回代、求解第3章 线性代数计算方法 计算方法找找列列最大值最大值换行换行对于对于对于对于做做做做对于对于做做第3章 线性代数计算方法 计算方法

9、/*本算法用高斯列主元素消去法求解矩阵方程本算法用高斯列主元素消去法求解矩阵方程AX=B。其中：其中：A是是NN矩阵；矩阵；B是是N1矩阵。矩阵。输入：输入：nA的行数；的行数；a二维矩阵二维矩阵Ab矩阵矩阵B算法结束后，函数返回值为算法结束后，函数返回值为ERROR_CODE时，表示时，表示A是奇异的或病态的；否则，是奇异的或病态的；否则，A代表行列式的值。代表行列式的值。aA消元后的上三角矩阵消元后的上三角矩阵b矩阵方程的解矩阵方程的解X*/第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法double Gaussian_elimination(int n,double

10、ann，double bn)int i,j,k,mk;double mm,f;for(k=0;kn-1;k+)mm=akk;mk=k;for(i=k+1;in;i+)if(fabs(mm)fabs(aik)mm=aik;mk=i;if(fabs(mm)=0)return(ERROR_CODE);当前列当前列找找列列最大值最大值第3章 线性代数计算方法 计算方法 if(mk!=k)for(j=k;jn;j+)f=akj;akj=amkj;amkj=f;f=bk;bk=bmk;bmk=f;for(i=k+1;in;i+)mm=aik/akk;aik=0.0;for(j=k+1;j=0;j-)for

11、(k=j+1;keps)x1=x2;for(i=0;in;i+)x2i=0;for(j=0;ji;j+)x2i+=Mij*x1j for(j=i+1;jeps)for(i=0;in;i+)for(j=0;ji;j+)x2i+=Mij*x2j for(j=i+1;jn;j+)x2i+=Mij*x2j x2i=(bi-x2i)/Mii 4、输出解x2第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法 Siedel迭代收敛条件迭代收敛条件定理：若A满足下列条件之一，则Seidel迭代收敛。A为行或列对角占优阵 A对称正定阵注：注：注：注：二种方法都存在二种方法都存在收敛性问题收敛性

12、问题。有例子表明：有例子表明：Seidel法收敛时，法收敛时，Jacobi法可能不收敛；法可能不收敛；而而Jacobi法收敛时，法收敛时，Seidel法也可能不收敛。法也可能不收敛。第3章 线性代数计算方法 计算方法 7.1 向量范数 在三维空间中,常用三种方法来衡量一个向量r=(x,y,z)T的“长度”,即7迭代法的收敛性迭代法的收敛性这种衡量的方法可推广到n维空间的向量：x=(x1,x2,xn)也即我们下面介绍的向量范数。T第3章 线性代数计算方法 计算方法定定义义1：设设n维维向向量量xR，记记对对应应向向量量x的的一一个个实实数数为为x,若若x满足下面三个性质满足下面三个性质:(1)非

13、负性，即非负性，即x0，当且仅当，当且仅当x=0时，时，x=0(2)齐次性，齐次性，x=x,为任意实数为任意实数(3)三角不等式性，三角不等式性，x+yx+y，yRn。则称该实数则称该实数x为向量为向量x的范数。的范数。可验证，对于不小于可验证，对于不小于1的正数的正数pn具有向量范数的三条基本性质。具有向量范数的三条基本性质。第3章 线性代数计算方法 计算方法称上式为向量称上式为向量x的的p范数范数,记为记为xp，即，即在在Rn中，常用的几种向量范数有中，常用的几种向量范数有:第3章 线性代数计算方法 计算方法定义定义2设设A为为nn阶矩阵，定义阶矩阵，定义为矩阵为矩阵A的范数。的范数。可以

14、证明，矩阵范数满足下列的几个性质可以证明，矩阵范数满足下列的几个性质:(1)非负性，非负性，A0,当且仅当当且仅当A=0时时,A=0(2)齐次性，齐次性，A=A,为任意实数为任意实数(3)三角不等式性三角不等式性,A+BA+B,B与与A为同阶矩阵为同阶矩阵(4)AxAx(5)ABAB第3章 线性代数计算方法 计算方法常见的矩阵范数常见的矩阵范数是是的最大特征值的最大特征值第3章 线性代数计算方法 计算方法谱谱半半径径：设设nn阶阶矩矩阵阵A的的特特征征值值为为i(i=1,2,n),则则称称为矩阵为矩阵A的谱半径。的谱半径。定定理理3设设(A)是是矩矩阵阵A的的谱谱半半径径，则则对对于于A的的任

15、任何何一一种种范数范数A,都有都有(A)A第3章 线性代数计算方法 计算方法定理定理5对于任意初始向量对于任意初始向量x(0)和常数项和常数项f,由迭代公式由迭代公式x(k+1)=Ax(k)+f,k=0,1,2,收敛的充要条件是收敛的充要条件是(A)1通常通常(A)1很难证明，一般用很难证明，一般用A1来判断迭代是否来判断迭代是否收敛收敛第3章 线性代数计算方法 计算方法8矩阵的特征值与特征向量的计算矩阵的特征值与特征向量的计算求求矩矩阵阵的的特特征征值值与与特特征征向向量量是是自自然然科科学学许许多多分分支支中中一一个个重重要要的的问问题题。nn阶阶矩矩阵阵A的的特特征征值值是是其其特特征征

16、方方程程det(A-I)=0的根的根,而属于特征值而属于特征值的特征向量是线性方程组的特征向量是线性方程组(A-I)x=0的非零解。的非零解。第3章 线性代数计算方法 计算方法8.1乘幂法乘幂法在在实实际际问问题题中中,往往往往不不需需要要求求矩矩阵阵A的的全全部部特特征征值值,而而只只要要计计算算其其按按模模最最大大或或最最小小的的特特征征值值,也也即即只只需需求求矩矩阵阵A的部分特征值。乘幂法便是一种行之有效的方法。的部分特征值。乘幂法便是一种行之有效的方法。设设n阶阶实实矩矩阵阵A有有n个个线线性性无无关关的的特特征征向向量量,其其特特征征值按模排列如下值按模排列如下:12n其相应的特征

17、向量分别记为其相应的特征向量分别记为x1,x2,xn现求按模最大的特征值现求按模最大的特征值1及其相应的特征向量及其相应的特征向量x1。第3章 线性代数计算方法 计算方法取非零初始向量取非零初始向量v0,作迭代构成一向量序列作迭代构成一向量序列因因为为特特征征向向量量x1,x2,xn线线性性无无关关,故故v0可可以以表表示示成这成这n个线性无关的向量的线性组合个线性无关的向量的线性组合,即即v0=1x1+2x2+nxn第3章 线性代数计算方法 计算方法于是于是vk=Ak(1x1+2x2+nxn)=11kx1+22kx2+nnkxn设设1为实数为实数,将上式改写成将上式改写成若若12,由上式有：

18、由上式有：第3章 线性代数计算方法 计算方法因此，当因此，当k充分大时，只要充分大时，只要10,就有就有vk1k1x1(1)(A-1I)vk11k(A-1I)x1=0这说明这说明vk是相应于特征值是相应于特征值1的特征向量的近似向量。的特征向量的近似向量。由式由式(1)，当，当k充分大时：充分大时：vk+11k+11x1=1k1x11vk第3章 线性代数计算方法 计算方法 例10 求矩阵 的按模最大的特征值与相应的特征向量。第3章 线性代数计算方法 计算方法(A6v0)1/(A5v0)13.4(A6v0)2/(A5v0)23.4(A6v0)3/(A5v0)33.4(A7v0)1/(A6v0)1

19、3.4(A7v0)2/(A6v0)23.4(A7v0)3/(A6v0)33.4于是有 13.4相应的特征向量为 x1(792,-1120,792)第3章 线性代数计算方法 计算方法 若把x1的第一个分量化为1,则有 x1(1,-1.4,1)事实上,矩阵A的特征值与相应的特征向量为第3章 线性代数计算方法 计算方法习题：习题：要求:习题三 1.2 ，6请尽力试着编写程序第3章 线性代数计算方法 计算方法非线性方程组的迭代法非线性方程组的迭代法第3章 线性代数计算方法 计算方法例例解下列非线性方程组解下列非线性方程组k0121819x0.00.80.92800.9999999720.9999999

20、89y0.00.80.93120.9999999720.999999989kk第3章 线性代数计算方法 计算方法直接推广直接推广Newton迭代为：迭代为：单个方程的牛顿迭代形式单个方程的牛顿迭代形式:雅可比矩阵雅可比矩阵(Jacobi)第3章 线性代数计算方法 计算方法NewtonNewton方法的迭代格式的推导方法的迭代格式的推导第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法解非线性方程组的主要步骤：解非线性方程组的主要步骤：(1)(1)选定初值选定初值X X0(4)(4)按公式计算按公式计算X1 1

21、(2)(2)计算计算F(X0),J(X0)(3)(3)计算计算X0(5)(5)误差判断误差判断第3章 线性代数计算方法 计算方法例：例：第3章 线性代数计算方法 计算方法例例用牛顿法解下列非线性方程组用牛顿法解下列非线性方程组k01234x0.00.80.9917872210.9999752291.000000000y0.00.880.9917117370.9999685241.000000000kk第3章 线性代数计算方法 计算方法SolveNonlinear程序框架程序框架GetFunagaus GetDeltaXGetJacobiUpdateXMain函数。第3章 线性代数计算方法 计算

22、方法#include stdlib.h#include math.h#include stdio.h#define N 3void SolveNonlinear(double xN,double eps,int k);void GetFun(double xN,double bN);void GetJacobi(double xN,double JNN);double GetDeltaX(double JNN,double bN,double deltaX N);int agaus(double a NN,double bN,int n);void UpdateX(double xN,doub

23、le deltaX N);计算计算F(X0)计算计算F (X0)解非线性方程组主程序解非线性方程组主程序计算计算X0主程序主程序更新计算结果（相当于计算更新计算结果（相当于计算X1）非线性方程组求解程序（牛顿法）非线性方程组求解程序（牛顿法）第3章 线性代数计算方法 计算方法/主函数主函数main()inti,k;doubleeps;doublexN=1.0,1.0,1.0;doublebN;eps=0.0000001;k=100;SolveNonlinear(x,eps,k);GetFun(x,b);printf(n);printf(n);for(i=0;ik)|(NormDeltaXeps

24、)break;计算计算F(X0)计算计算F(X0)计算计算X0更新计算结果更新计算结果循环截止条件循环截止条件第3章 线性代数计算方法 计算方法/计算计算F(X)，结果放在，结果放在b里里voidGetFun(x,y)doublex,y;y0=x0*x0+x1*x1+x2*x2-1.0;y1=2.0*x0*x0+x1*x1-4.0*x2;y2=3.0*x0*x0-4.0*x1+x2*x2;return;/计算计算F(X)，结果放在，结果放在J里里voidGetJacobi(x,J)doublexN,JNN;J00=2*x0;J01=2*x1;J02=2*x2;J10=4*x0;J11=2*x1

25、;J12=-4;J20=6*x0;J21=-4;J22=2*x2;return;第3章 线性代数计算方法 计算方法/计算计算X0主程序主程序doubleGetDeltaX(doubleJNN,doublebN,doubledeltaXN)intnResultFlag,i;doubleNormDeltaX;nResultFlag=agaus(J,b,N);if(nResultFlag)NormDeltaX=0;for(i=0;iN;i+)NormDeltaX=NormDeltaX+fabs(bi);deltaXi=bi;returnNormDeltaX;解线性方程组求解线性方程组求X0，存于存于

26、b中中第3章 线性代数计算方法 计算方法/高斯全主元法解方程，结果放在高斯全主元法解方程，结果放在b里里intagaus(a,b,n)intn;doubleaNN,bN;int*js,l,k,i,j,is;doubled,t;js=malloc(n*sizeof(int);/记载列交换标号记载列交换标号l=1;for(k=0;k=n-2;k+)d=0.0;for(i=k;i=n-1;i+)/求全主元求全主元for(j=k;jd)d=t;jsk=j;/记住列记住列is=i;/记住行记住行求全主元求全主元第3章 线性代数计算方法 计算方法if(d+1.0=1.0)l=0;elseif(jsk!=k

27、)/列交换列交换for(i=0;i=n-1;i+)t=aik;aik=aijsk;aijsk=t;if(is!=k)for(j=k;j=n-1;j+)/行交换行交换t=akj;akj=aisj;aisj=t;t=bk;bk=bis;bis=t;/b交换交换列交换列交换行交换行交换判断主元是否为零判断主元是否为零第3章 线性代数计算方法 计算方法/最大主元为零不能计算出正确结果最大主元为零不能计算出正确结果if(l=0)free(js);printf(failn);return(0);/以下为消元过程以下为消元过程d=akk;akk=1;for(j=k+1;j=n-1;j+)/当前行除以当前行除

28、以akkakj=akj/d;bk=bk/d;for(i=k+1;i=n-1;i+)/消元消元for(j=k+1;j=0;i-)t=0.0;for(j=i+1;j=0;k-)if(jsk!=k)t=bk;bk=bjsk;bjsk=t;free(js);return(1);恢复解的顺序恢复解的顺序第3章 线性代数计算方法 计算方法voidUpdateX(doublex0N,doubledeltaXN)inti;for(i=0;iN;i+)x0i=x0i-deltaXi;/更新计算结果更新计算结果（相当于计算（相当于计算X1）第3章 线性代数计算方法 计算方法计算雅可比矩阵的方法计算雅可比矩阵的方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法第3章 线性代数计算方法 计算方法拟牛顿法第3章 线性代数计算方法 计算方法数值法数值法解非线性方程组的主要步骤：解非线性方程组的主要步骤：(1)(1)选定初值选定初值X X0、h0(5)(5)按公式计算按公式计算X1 1(2)(2)计算计算F(X0),F (X0)(4)(4)计算计算X0(6)(6)误差判断误差判断h(3)(3)计算计算z0