《《线性代数方程组》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《线性代数方程组》PPT课件.ppt（80页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章线性方程组的数值解法线性方程组的数值解法确定小行星轨道确定小行星轨道以太阳为原点在轨道平面以太阳为原点在轨道平面内建立直角坐标系内建立直角坐标系, ,取天文测量单位取天文测量单位, ,在五个不同时间在五个不同时间观察小行星观察小行星, ,测得坐标数据：测得坐标数据：x 4.5596 5.08165.55465.96366.2756y 0.8145 1.36851.98952.69253.5265通过计算确定椭圆方程通过计算确定椭圆方程a1x2+2a2xy + a3y2+2a4 x + 2a5 y +1=0a1xj2+2a2xjyj + a3yj2+2a4 xj + 2a5 yj +
2、1=0将五个点的坐标将五个点的坐标(xj,yj)(j= 1,2,3,4,5)代入二次曲线代入二次曲线方程方程,得关于得关于a1,a2,a3,a4,a5的方程组的方程组 在在 科科 学学 计计 算算 中中 ， 经经 常常 需需 要要 求求 解解 含含 有有 n n个个 未未 知知 量量 的的n n个方程构成的线性方程组个方程构成的线性方程组方程组还可以用矩阵形式表示为方程组还可以用矩阵形式表示为: : Ax=b (2.1)(2.1)克莱姆法则需克莱姆法则需(n+1)(n-1)n!+n次乘除法运次乘除法运算算(1)输入系数矩阵输入系数矩阵A和右端向量和右端向量b;(4)计算并输出计算并输出x1=D
3、1/D;,xn=Dn/D,结束。结束。(3)对对k=1,2,n用用b替换替换A的第的第k列数据列数据,并计算并计算替换后矩阵的行列式值替换后矩阵的行列式值Dk;(2)计算系数矩阵计算系数矩阵A的行列式值的行列式值D,如果如果D=0,则输则输出错误信息结束出错误信息结束,否则进行第否则进行第(3)步步;线性方程组数值解法的分类：线性方程组数值解法的分类：线性方程组数值解法的分类：线性方程组数值解法的分类： 直接法直接法 GaussGauss消去法及其变形消去法及其变形 矩阵的三角分解法矩阵的三角分解法 迭代法迭代法 JacobiJacobi迭代法迭代法Gauss-SeidelGauss-Seid
4、el迭代法迭代法松弛松弛迭代迭代2.1 2.1 高斯消元法高斯消元法1 1三角形方程组的解法三角形方程组的解法-回代法回代法2.2.顺序顺序Gauss（高斯）消元法高斯）消元法是一种规则化的加减消是一种规则化的加减消元法。元法。 基基本本思思想想通通过过逐逐次次消消元元计计算算把把需需要要求求解解的的线线性性方方程程组组转转化化成成上上三三角角形形方方程程组组，也也就就是是把把线线性性方方程程组组的的系系数数矩矩阵阵转转化化为为上上三三角角矩矩阵阵，从从而而使使一一般般线线性性方方程程组组的的求求解解转转化为等价（同解）的上三角形方程组的求解。化为等价（同解）的上三角形方程组的求解。 Gaus
5、s消元法由消元法由消元消元和和回代回代两个过程组成，先讨论两个过程组成，先讨论一个具体的线性方程组的一个具体的线性方程组的求解。求解。例例1用用Gauss消元法解方程组消元法解方程组 用增广矩阵进行进算用增广矩阵进行进算这样，对于方程组这样，对于方程组(2.1)用增广矩阵表示，并给出用增广矩阵表示，并给出Gauss消元法的具体步骤：消元法的具体步骤：或者或者 Ax=b 顺序顺序Gauss消元法的消元过程可表述如下：消元法的消元过程可表述如下：第一步：设第一步：设a11(1)0，将第一列将第一列a11(1)以下各元素消成零以下各元素消成零乘以矩阵乘以矩阵A（1），b（1）的第的第一行再加到第一行
6、再加到第i 行，得到矩阵行，得到矩阵 (i2，3，n)即依次用即依次用其中其中第二步第二步：设设a22(2)0，将第二列将第二列a22(2)以下各元素消成零以下各元素消成零（i3，4，n） 即依次用即依次用乘以矩阵乘以矩阵A（2），b（2）的第二行再加到第的第二行再加到第i行，得到矩阵行，得到矩阵其中其中如此继续消元下去第如此继续消元下去第n1步结束后，得到矩阵步结束后，得到矩阵增广矩阵增广矩阵A（n），b（n）对应如下上三角形方程组对应如下上三角形方程组这是与原线性方程组（这是与原线性方程组（2.1）等价的方程组）等价的方程组.对于等价方程组对于等价方程组进行回代求解，可以得到：进行回代求解
7、，可以得到：首先写出增广矩阵首先写出增广矩阵于是，采用于是，采用Gauss消元法求解方程组消元法求解方程组(2.1)(2.1)然后进行消元，采用公式然后进行消元，采用公式最后进行回代得到方程组的解最后进行回代得到方程组的解得到相似增广矩阵得到相似增广矩阵（ik+1，k+2，n） 在编程计算时，最后的增广矩阵存放的元素是：在编程计算时，最后的增广矩阵存放的元素是：算法算法.顺序顺序GaussGauss消元法可执行的消元法可执行的前提前提定理定理 1 1 给定线性方程组给定线性方程组 ，如果，如果n n阶方阵阶方阵 的所有顺序主子式都不为零，即的所有顺序主子式都不为零，即 则按顺序则按顺序Gaus
8、sGauss消去法所形成的各主元素消去法所形成的各主元素 均不为零，从而均不为零，从而Gauss消元法可顺利执行。消元法可顺利执行。注：注：当线性方程组的系数矩阵为当线性方程组的系数矩阵为对称正定对称正定或或严格对角严格对角占优阵占优阵时，按时，按GaussGauss消元法计算是稳定的。消元法计算是稳定的。例例2 2 用用Gauss消元法消元法求解方程组：求解方程组：例例3用用Gauss消元法求解线性方程组消元法求解线性方程组a=121-2;253-2;-2-235;1323;b=47-10;(ab)fork=1:3d=a(k,k);c=a(k,:);c0=b(k);fori=k+1:4l=a
9、(i,k)/d;a(i,:)=a(i,:)-l*c;b(i)=b(i)-l*c0;endendb(4)=b(4)/a(4,4);fork=3:-1:1b(k)=(b(k)-a(k,k+1:4)*b(k+1:4)/a(k,k);endb=bMATLAB程序程序ans=2-12-1 b=2-12-1 3 3、列主元、列主元GaussGauss消元消元法法顺序顺序Gauss消元法计算过程中的消元法计算过程中的akk(k) 称为主元素，在称为主元素，在第第k步消元时要用它作除数步消元时要用它作除数,则可能会出现以下几种情况则可能会出现以下几种情况若出现若出现akk(k)0，消元过程就不能进行下去。消元
10、过程就不能进行下去。 akk(k)0，消元过程能够进行，但若消元过程能够进行，但若|akk(k)|过小，也会过小，也会造成舍入误差积累很大导致计算解的精度下降。造成舍入误差积累很大导致计算解的精度下降。 例例4:在四位十进制的限制下，试用顺序在四位十进制的限制下，试用顺序Gauss消元法求消元法求解如下方程组解如下方程组此方程组具有四位有效数字的精确解为此方程组具有四位有效数字的精确解为x117.46，x245.76，x35.546 解解用顺序用顺序Gauss消元法求解，消元过程如下消元法求解，消元过程如下经回代求解得经回代求解得 x35.546，x2100.0，x1104.0和此方程组的精确
11、解相比和此方程组的精确解相比x35.546 ，x245.76，x117.46有较大的误差。有较大的误差。对对于于此此例例，由由于于顺顺序序Gauss消消元元法法中中的的主主元元素素绝绝对对值值非非常常小小，使使消消元元乘乘数数绝绝对对值值非非常常大大，计计算算过过程程中中出出现现大大数数吃吃掉掉小小数数现现象象，产产生生较较大大的的舍舍入入误误差差，最最终终导导致致计计算算解解x1104.0和和x2100.0已完全失真。已完全失真。为为避避免免这这种种现现象象发发生生，可可以以对对原原方方程程组组作作等等价价变变换换，再再利用顺序利用顺序Gauss消元法求解消元法求解。写出原方程组的增广矩阵：
12、写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行等价变换：针对第一列找出绝对值最大的元素，进行等价变换：求得方程的解为：求得方程的解为：x35.546，x245.76，x117.46精确解为：精确解为：x35.546 ，x245.76，x117.46列主元列主元Gauss消元法与顺序消元法与顺序Gauss消元法的不同之处在于：消元法的不同之处在于： 后者是按自然顺序取主元素进行消元后者是按自然顺序取主元素进行消元前者在每步消元之前先选取主元素然后再进行消元前者在每步消元之前先选取主元素然后再进行消元 下面将列主元下面将列主元Gauss消元法的计算步骤叙述如下：消元法的计算步骤叙述如
13、下： 给给定定线线性性方方程程组组Axb,记记A（1）,b（1）A,b，列列主主元元Gauss消去法的具体过程如下：消去法的具体过程如下： 1.首首先先在在增增广广矩矩阵阵A（1）,b（1）第第一一列列的的n个个元元素素中中选选取取绝绝对对值值最最大大的的一一个个作作为为主主元元素素，并并把把此此主主元元素素所所在在的的行行与与第一行交换，即第一行交换，即2.其其次次进进行行第第一一步步消消元元得得到到增增广广矩矩阵阵A（2）,b（2），在在矩矩阵阵A（2）,b（2）第第二二列列的的后后n1个个元元素素中中选选取取绝绝对对值值最最大大的的一个作为主元素，并把此主元素所在的行与第二行交换，即一个
14、作为主元素，并把此主元素所在的行与第二行交换，即 3.再再进进行行第第二二步步消消元元得得到到增增广广矩矩阵阵A（3），b（3）。按按此此方方法法继继续续进进行行下下去去，经经过过n1步步选选主主元元和和消消元元运运算算，得得到到增增广矩阵广矩阵A（n），b（n），它对应的方程组它对应的方程组A（n）xb（n）是一个与原方程组等价的上三角形方程组，可进行回代求是一个与原方程组等价的上三角形方程组，可进行回代求解。解。 容容易易证证明明，只只要要det（A）0，列列主主元元Gauss消消去去法法就就可可以以顺顺利利完完成成，即即不不会会出出现现主主元元素素为为零零或或者者绝绝对对值值太太小小的的
15、情情形出现。形出现。选列主元过程：选列主元过程：一、求主元一、求主元alk 使得使得|alk|=max|akk|,|ak+1,k|, ,|ank|;二、判断：若二、判断：若|alk| 1时时当当j 1 时时下面，我们对具体矩阵进行下面，我们对具体矩阵进行Doolittle Doolittle 三角分解。三角分解。为了表示和存储方便，可以将分解后的两个矩阵用为了表示和存储方便，可以将分解后的两个矩阵用一个矩阵表示一个矩阵表示例例7 7 利用利用DoolittleDoolittle三角分解法分解矩阵三角分解法分解矩阵解：分解时用到如下公式解：分解时用到如下公式1234111261237624624
16、1234111261237624624可以写成：可以写成：这时，矩阵的三角分解这时，矩阵的三角分解如果我们要求解方程组如果我们要求解方程组则由则由得到得到例例8 8：利用：利用DoolittleDoolittle三角分解方法解线性三角分解方法解线性方程组方程组解解:进行三角分解进行三角分解ALU，可以对增广矩阵可以对增广矩阵A,b作作三角分解三角分解:123-2-322 -3-13317得到得到123-2-322 -3-13317这时，相应的方程组为：这时，相应的方程组为：x135x28，例例9：用矩阵分解方法解用矩阵分解方法解AX = bLY = bUx = Yy1=6y2=-4y3=-4x
17、1=-13x2=8x3=2A=LU不选主元的不选主元的LU分解分解A=2，3，4；3，5，2；4，3，30n=max(size(A);fork=1:n-1d=A(k,k);fori=k+1:nm=A(i,k)/d;forj=k+1:nA(i,j)=A(i,j)-m*A(k,j);endA(i,k)=m;endendA=2.003.004.001.500.50-4.002.00-6.00-2.00 平方根平方根法法 ： 在实际应用中，常见一类非常重要的线性方程组在实际应用中，常见一类非常重要的线性方程组Axb，其中其中A为为对称正定矩阵对称正定矩阵，即，即A是对称的且对任是对称的且对任何非零向量
18、何非零向量 x都有都有xTAx0。本节将对这类方程组导本节将对这类方程组导出更有效地三角分解求解方法，称之为出更有效地三角分解求解方法，称之为平方根法平方根法。 设设A A为为对对称称正正定定矩矩阵阵，那那么么A A的的所所有有顺顺序序主主子子式式均均大大于于零零，根根据据定定理理2.22.2，存存在在惟惟一一三三角角分分解解 ALU，即即 记记Ak（1kn）为）为A的的k 阶顺序主子阵，则阶顺序主子阵，则det（Ak）为）为A的的k阶顺序主子式。由上式，利用矩阵分阶顺序主子式。由上式，利用矩阵分块运算规则，容易验证块运算规则，容易验证det（Ak）u11u22ukk那么由那么由det（Ak）
19、0，可知可知ukk0，k1，2，n这时，将上面的矩阵表示为：这时，将上面的矩阵表示为：即：即：A=LDM ，其中其中DM=U， M=D-1U。当当AAT为对称矩阵时，根据为对称矩阵时，根据ALDM, 得到得到ATMT D LT再根据矩阵三角分解的唯一性再根据矩阵三角分解的唯一性,可知可知MLT。于是于是ALDLT则有则有令令如果对称正定矩阵如果对称正定矩阵A具有如下分解具有如下分解AGGT，其中其中G为为下三角矩阵，则称其为下三角矩阵，则称其为对称正定矩阵的对称正定矩阵的Cholesky（乔（乔列斯列斯基）分解。基）分解。为表示方便，可以记为表示方便，可以记给定对称正定方程组给定对称正定方程组
20、Axb，对对A 进行进行Cholesky分解分解ALLT，则原方程组等价于则原方程组等价于 LLTxbLyb LTx y解此方程组即可得到原方程组的解解此方程组即可得到原方程组的解x ，这就是求解方程组这就是求解方程组的平方根法。的平方根法。 下下面面，我我们们通通过过比比较较矩矩阵阵的的对对应应元元素素给给出出对对称称正正定定矩矩阵阵的的平方根分解法。已知平方根分解法。已知即：即： LLTxb，等价于等价于比较对应元素：比较对应元素：当当i= j 时时当当 ji 时时解得解得于是，根据计算公式于是，根据计算公式可以对对称正定矩阵进行平方根分解可以对对称正定矩阵进行平方根分解l11 l21 l
21、22 l31 l32 l33 ln1 ln2 ln3 lnn 关关于于方方程程组组Ax=b , 如如果果对对系系数数矩矩阵阵进进行行了了平平方方根根分分解解ALLT，则将方程组化为：则将方程组化为：Lyb , LTxy解得解得于是，关于系数矩阵是对称正定矩阵的线性方程组于是，关于系数矩阵是对称正定矩阵的线性方程组Ax=b的求解，分两步进行：的求解，分两步进行：第一步：系数矩阵的平方根分解第一步：系数矩阵的平方根分解第二步：解等价方程组第二步：解等价方程组例例10 用平方根法求解对称正定方程组用平方根法求解对称正定方程组 解解:首先进行首先进行A 的的Cholesky分解分解 ALLT2-0.5
22、0.521.512-0.50.521.51得得y12，y23.5，y31得得x11，x21，x31求解求解Lyb:再求解再求解LTxy: 解三对角方程组的追赶法解三对角方程组的追赶法考虑如下形式的三对角方程组问题考虑如下形式的三对角方程组问题其中，系数矩阵满足条件其中，系数矩阵满足条件:该三对角方程组的增广矩阵该三对角方程组的增广矩阵为为:第一步：第一行元素除以第一步：第一行元素除以b1，取，取 1 = c1 / b1，y1 = f1 / b1，可，可得得增广矩阵增广矩阵：第二步：从出发，用初等变换作第二步：从出发，用初等变换作 n-1 轮消元。作第轮消元。作第 k 轮消元时，将矩阵中第轮消元
23、时，将矩阵中第 k 行元素乘以行元素乘以 - ak+1 加到第加到第 k+1 行元素上，然后将第行元素上，然后将第 k+1 行主元单位化行主元单位化( k = 1 , 2, , n-1 )。最后的增广矩阵。最后的增广矩阵 ：其中， i = ci / (bi - ai i-1 ) (i = 2,3, , n-1 )yi = ( fi aiyi-1) / ( bi - ai i-1 )(i = 2, 3, , n)在在消元过程消元过程中所用除法次数为中所用除法次数为2n - 1，所用乘法次数为，所用乘法次数为2(n - 1)。根据矩阵初等变换的性质知，原三对角方程组根据矩阵初等变换的性质知，原三对
24、角方程组等价于如下方程组等价于如下方程组 对这一特殊的上三角方程组，在对这一特殊的上三角方程组，在回代过程回代过程中只需用到中只需用到n 1 次乘法就可以求出方程组的解。次乘法就可以求出方程组的解。xn=ynk 从从(n-1)到到1 循循环环输出输出x1，x2，xn；结束结束输入已知数据输入已知数据ai，bi，ci，fii 从从2到到n 循环循环y1=f1/b1，d=b1 i-1=ci-1/d;d=bi-ai i-1;yi=(fi-aiyi-1)/d. xi=yi- ixi+1追赶法算法框图追赶法算法框图例例11用追赶法求解方程组用追赶法求解方程组最后得增广矩阵最后得增广矩阵所以，方程组的解为
25、所以，方程组的解为k12345 k0.25000.26670.26790.2679yk0.50000.13330.23210.20570.4808xk0.48080.07690.21150.07690.4808a=01111;b=44444;c=11110;f=21112;d=b(1);f(1)=f(1)/d;fork=2:5,c(k-1)=c(k-1)/d;d=b(k)-a(k)*c(k-1);f(k)=(f(k)-a(k)*f(k-1)/d;endcleardabfork=4:-1:1,f(k)=f(k)-c(k)*f(k+1);endff=0.48080.07690.21150.07690.4808MATLAB程序程序
