4线性方程组的直接解法课件

北京科技大学数理学院卫宏儒weihr@计算方法北京科技大学数理学院计算方法第4章:线性方程组的直接解法第4章:线性方程组的直接解法关键词：高斯消元法主元消元法高斯消元法与主元消元法

高斯消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题关键词：高斯消元法与主元消元法

(一)引言

为便于以下讨论,把涉及到的有关名词及问题的引出暂介绍如下:

如果未知量的个数为n,而且关于这些未知量x1,x2,…,xn

的幂次都是一次的(线性的),那么,n个方程

a11x1+a12x2+…+a1nxn=b1

┆┆

┆(1)an1x1+an2x2+…+annxn=bn

构成一个含n个未知量的线性方程组,称为n阶线性方程组。其中,系数a11,…,a1n,a21,…,a2n,…,an1,…,ann

是给定的常数;b1,…,bn

也是给定的常数,通常称为常数项,或称为方程组的右端.

方程组(1)也常用矩阵的形式表示,写为

Ax=b(一)引言为便于以下讨论,把涉及到的有关名词及问题的其中,A是由系数按次序排列构成的一个n阶矩阵，称为方程组的系数矩阵，x和b都是n维向量，称为方程组的右端向量。.

使方程组(1)中每一个方程都成立的一组数x1*,x2*,…,xn*

称为式(1)的解，把它记为向量的形式，称为解向量。其中,A是由系数按次序排列构成的一个n阶矩阵，称为方程组的系

我们总是希望方程组有解,且有唯一解.由线性代数的克莱姆(cramer)规则可知,如果方程组(1)的系数矩阵A的行列式(一般记为D=ⅠAⅠ)不等于零,那么,这个方程组有唯一解,而且它们可以表示为

xi=Di/D(i=1,…,n)

这里,Di是指D中第i列元素用右端b1,…bn代替构成的行列式.

如果方程组(1)有唯一解,我们按上面的等式求解,就必须计算n+1个n阶行列式.由行列式的定义,n阶行列式包含有n!项,每一项含有n个因子,计算一个n阶行列式就需要做(n-1)n!次乘法.而我们一共要计算n+1个n阶行列式,共需做(n2-1)n!次乘法.此外,还要做n次除法才能算出xi(i=1,…n).也就是说,用这个办法求解就要做

N=(n2-1)n!+n次乘除法运算,这个计算量是大得惊人的.例如,当n=10(即求解一个含10个未知量的方程组),乘除法的运算次数共为32659210次;我们总是希望方程组有解,且有唯一解.由线性代数的克莱当n=40，乘除法运算次数可达3.181049次。对于上百个未知量的方程组，次数运算量就更大了。因此可莱姆规则在理论上尽管是完善的，但在实际计算中却没有什么实用价值。我们将重点讨论求解线性方程组的一种有效的数值方法。

(二)求解线性方程组的消元法

消(元)去法是求解线性方程组

Ax=b(2)和满秩矩阵的逆阵A-1的一种直接方法.尽管它比较古老,但它具有演算步骤,推算公式都系统化的特点(对其中选主元消去法,还可以证明是稳定的).因此,它至今仍然是求解方程组的一种有效的方法.

消去法可以引出几种计算方法,下面按三角形方程组和一般线性方程组的顺序来讨论。当n=40，乘除法运算次数可达3.181049次。对于上1.三角形方程组的解法

三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一，实际上消元法就是通过简化一般线性方程组为三角形方程组后再求解的。上三角方程组的一般形式是：

1.三角形方程组的解法4线性方程组的直接解法课件4线性方程组的直接解法课件4线性方程组的直接解法课件2.Gauss消元法

(一)高斯消去法的求解过程：分为两个阶段:首先，把原方程组化为上三角形方程组，称之为“消去”过程；然后，用逆次序逐一求出三角方程组(原方程组的等价方程组)的解，并称之为“回代”过程。下面分别写出“消去”和“回代”

两个过程的计算步骤。

消去过程:第一步:设a110,取

做(消去第i个方程组的x1)mi1第一个方程+第i个方程

i=2,3,…n则第i个方程变为：2.Gauss消元法(一)高斯消去法的求解过程：分为两个因为可得第一步消元后的方程组为：i,j=2,3,…,ni,j=2,3,…,n因为i,j=2,3,…,ni,j=2,3,…,n第二步:设,取

做(消去第i个方程组的x2,i=3,4,…n)mi2第二个方程+第i个方程

i=3,4,…n类似可得第二步消元后的方程组为：第二步:设,取第k步:设,取

做(消去第i个方程组的xk,i=k+1,k+2,…,n)mik第k个方程+第i个方程

i=k+1,k+2,…n类似可得第k步消元后的方程组为：第k步:设,取继续下去到第n-1步消元，可将线性方程组化为如下上三角方程组:继续下去到第n-1步消元，可将线性方程组化为如下上三角方程组4线性方程组的直接解法课件4线性方程组的直接解法课件4线性方程组的直接解法课件3.主元消元法例1:考虑如下线性方程组的Gauss消元法

求解性

2x2=12x1+3x2=2解:因为a11=0,故此题不能用Gauss消元法求解,但交换方程组的顺序后,就可用Gauss消元法求解了.3.主元消元法例1:考虑如下线性方程组的Gauss消元法例题2:讨论下面方程组的解法0.0001x1+x2=1x1+x2=2

假设求解是在四位浮点十进制数的计算机上进行。0.100010-3x1+0.1000101x2=0.10001010.1000101x1

+0.1000101x2=0.2000101解:本题的计算机机内形式为

因为a11=0.00010,故可用Gauss消元法求解,进行第一次消元时有a22(1)=0.1000101-1040.1000101

(m21=a21/a11=1/0.0001=104)=0.00001105-0.1000105

(对阶计算)=0.0000-0.1000105=

-0.1000105,得三角方程组

0.100010-3x1+0.1000101x2=0.1000101-0.1000105x2=-0.1000105

回代解得x2=1,x1=0

严重失真!

(因为本题的准确解为x1=10000/9999,x2=9998/9999）例题2:讨论下面方程组的解法0.0001x1+x2=1

列主元基本思想及程序框图

用高斯消去法求解线性方程组时,应避免小的主元.在实际计算中,进行第k步消去前,应该在第k列元素aik

(i=k,…,n)中找出绝大值最大者,例如∣a∣=max∣a∣再把第p个方程与第k个方程组进行交换,使apk(k-1)成为主元.我们称这个过程为选主元.由于只在第k列元素中选主元,通常也称为按列选主元(或称部分选主元).

如果在第k步消去前,在第k个方程到第n个方程所有的xk到xn的系数a(i=k,…,n;j=k,…,n)中,找出绝对值最大者,例如 ∣a∣=max∣a∣再交换第k,p两个方程和第k,q两个未知量的次序,使a成为主元.称这个过程为完全选主元。不论是哪种方式选出主元,而后再按上面介绍的计算步骤进行消去的计算,一般都称为选主元的高斯消去法。在实际计算中,常用按列选主元的高斯消去法。

(k-1)(k-1)pk(k-1)ikk≦i≦n(k-1)pq(k-1)ijk≦i,j≦n(k-1)ij(k-1)pq列主元基本思想及程序框图(k-1)(k-1)pk(k-1

用列主元消去法解线性方程组AX=b的程序框图见右图.图中w作控制常数,通常为比较小的正实数,当某个选出的主元或完成消元后的系数ann的绝对值小于w时,就认为detA≈0,从而终止计算.为了节省工作单元图中还用A(k)

冲掉A,b(k)冲掉b,并注意A到的下三角部分都应变为零,而且在第k次消元计算式算出乘数mik后aik不再起作用,故用mik冲掉aik,回代后所得到的解放在数组b内。k<n-1输入n,A,b,wk=1,2,…,n-1选主元,确定ik使|aik,k(k)|=max|ai,k(k)|(k≤i≤n)ik=k|aik,k(k)|<w交换行aik,kakj(j=1,2,…n)bikbk

消元计算aikaik/akkaijaij-aikakjbibi-aikbk(i=k+1,…n)(j=k+1,..n)|ann|<wStop输出detA=0输出结果bi(i=1,2,…n)回代求解bnbn/annbi(bi-∑aijxj)/aii(i=n-1,..,2,1)是否是是否用列主元消去法解线性方程组AX=b的程序框图例三用列主元消去法解方程组解

第一次消元对

因列主元素为a31(1),故先作行变换r1__r3,然后进行消元计算可得

第二次消元对[A(2)|b(2)],因列主元素为a32(2),故先作行变换r2__r3,然后进行消元计算可得

由此回代,得x=(1.9272,-0.69841,0.90038)T与精确解

x=(1.9273,-0.69850,0.90042)T相比较是比较准确的.-0.002x1+2x2+2x3=0.4x1+0.78125x2=1.38163.996x1+5.5625x2+4x3=7.4178-0.002220.4[A(1)|b(1)]=10.7812501.38163.9965.562547.41783.9965.562547.4178[A(2)|b(2)]=0-0.61077-1.0010-0.4747102.00292.00200.40371

3.9965.562547.4178[A(3)|b(3)]=02.00292.00200.4037100-0.39050-0.35160例三用列主元消去法解方程组解第一次消元对

4、高斯消去法的计算量分析

高斯消去法的乘除总运算分析如下：消元次数k消元乘法次数消元除法次数回代乘除法总次数

1n(n-1)n-12(n-1)(n-2)n-2...k(n-k+1)(n-k)n-k..n-12*11n(n+1)/2

故高斯消去法的计算量为N=n(n2-1)/3+n(n-1)/2+n(n+1)/2=n3/3+n2-n/3当N充分大时为n3/34、高斯消去法的计算量分析4线性方程组的直接解法课件

5、方法的特点

由具体计算结果可知,全主元素法的精度优于主元素法,这是由于全主元素是在全体系数中选主元,故它对控制舍入误差十分有效.但全主元素法在计算过程中,需同时作行与列的互换,因而程序比较复杂,计算时间较长.列主元素法的精度虽稍低于全主元素法,但其计算简单工作量大为减少,且计算经验与理论分析均表明,它与全主元素法同样具有良好的数值稳定性,列主元素法是求解中小型稠密性方程组的最好方法之一。

选主元消去法(包括解线性方程组的所有直接的方法)比较适用于中小型方程组.对高阶方程组,即使奇数矩阵是稀疏的,但在计算中很难保持稀疏性,因而有存储量大，程序复杂等不足,所幸的是这一缺点可用迭代法解决.

另外,高斯选主元消去法还可技巧性的解决一些特殊线性方程组。

由于误差的影响,计算过程中可能出现一些坏现象,要尽可能防止,表现在求解线性方程组的消元法比较上,则应该注意要简化运算,减小运算次数,提高效率;提高数值稳定性等.

5、方法的特点（三）线性方程组解对系数的敏感性

在计算过程中，由于计算机字长的有限性，不可避免地产生所谓的舍入误差。同时，由于所求问题的初始数据（例如线形方程组的系数矩阵和右端项系数）往往是带有一定误差的。因此计算结果总是不可避免地带有误差，或者说，如果初始数据有扰动，势必将带来具有一定误差的计算结果。就拿Ax=b来说，由于观测或计算等原因，线性方程组两端的系数A和b都带有误差A和b，这样实际建立的方程组是近似方程组(A+A)(x+x)=b+b。对近似方程组求出的解是原问题的真解x加上误差x,即x+x。而

x是由A及b引起的，它的大小将直接影响所求解的可靠性。这种解依赖于方程组系数的误差A及b的问题，称为线性方程组解对系数的敏感性。（三）线性方程组解对系数的敏感性在计算过程中

方程组的系数矩阵发生微小扰动，就有可能引起方程组性质上的变化，这是方程组本身的“条件问题”。相对误差关系式：设原线形方程组Ax=b

和近似方程组(A+A)(x+x)=b+b在1、A=0,b0

2、A0,b=0方程组的系数矩阵发生微小扰动，就有可能引起方程组性一般情形

由这些关系式可看到，带有扰动的近似方程组中，扰动的大小直接影响着所求解的相对误差，故可作如下定义：定义：设A非奇异，称||A-1||||A||为矩阵A的条件数，记为Cond(A)，即Cond(A)=||A-1||||A||.Cond(A)可反映出方程组解对系数的敏感性。对此，可通过下面的例子加以理解。一般情形由这些关系式可看到，带有扰动的近似方方程组

此方程组的准确解为x1=0,x2=-1。现将其右端加以微小的扰动使之变为：

经计算可得准确解为x1=2,x2=-3.

这两个方程组的解相差很大，说明方程组的解对常数项b的扰动很敏感。同时注意到||A||=4.0001,||A-1||=3.0001104,故有Cond(A)=1.23105,可见条件数很大。方程组一般来说，方程组的条件数越小，求得的解就越可靠；反之，解的可靠性就越差。通常当从方程组Ax=b求出计算解x**后，有时用残向量

r=b-Ax**

的大小来检验x**的精度，认为如果对某种范数||r||很小，就说明是好的。不过要记住这种处理在某些情况下是不准确的。例如，对上述举例的方程组，当用某种方法求得计算解后，则有，显然||r||是很小的，但与其真实解相差很大。为说明这方面的原因，我们可以把残向量r看成是Ax=b的右端有扰动的b，由相对误差关系式，有：不可轻易用残向量||r||的大小来判断计算解的精度。一般来说，方程组的条件数越小，求得的解就越可靠；反之，解的可（四）病态方程组：如果方程组AX=b由于A或b的小扰动而导致解严重失真，则此方程组称为病态方程组，否则称为良态方程组。判定一个病态方程组的简单方法；病态方程组一般不能用解方程组的常有方法求解，而采用“迭代求精法”来计算。（列主元消元法的应用）（四）病态方程组：如果方程组AX=b由于A或b的小扰动而导致(五)、LU分解法

1、LU分解法的基本思想假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU其中L为下三角矩阵，U为上三角矩阵。这样我们可以把线性方程组Ax=b写成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y，则原线性方程组Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,从而求解线性方程组Ax=b的目的。(五)、LU分解法

定义：

1.LU分解:将系数矩阵A转变成等价两个矩阵L和U的乘积，其中L和U分别是下三角和上三角矩阵，而且要求U的对角元素都是1。2.紧凑格式:由于可以把L和U两个矩阵压缩到一个数组中，而且还可以存储在原来的系数矩阵A的数组中。这种LU分解常被称为紧凑格式.

由LU=A及对L和U的要求可以得到分解的计算公式。根据下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及对L和U的要求可以得到分解的计算公式。根据下式(第j个分量第i个分量第j个分量第i个分量根据矩阵乘法及相等的定义,有

得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n根据矩阵乘法及相等的定义,有得公式u1j=a1j4线性方程组的直接解法课件

在计算机程序中常常用这种方法解线性代数方程组。它的优点是存储量很省。L和U中的三角零元素都不必存储，就是U的对角元素也因为都是1没有必要再记录在程序中，这样只用一个n阶方阵就可以把L和U贮存起来。即：下三角（包括对角元）存储L各元素而上三角存储U的元素。再考察公式S会发现A中任一元素只在计算（j<=i）和（j>i)中用到一次以后就不再出现了，因而完全可以利用原始数组A的单元，一个个逐次贮存L或U中的相应元素，即：

a11

a12a13…a1nu11u12u13…u1na21a22a23…a2nl21u22u23…u2na31a32a33…a3nl31l32u33…u3n

an1an2an3…annln1ln2ln3…unn………...…………......(1)(3)(5)(2n-1)(2)(4)(6)(2n)在计算机程序中常常用这种方法解线性代数方程组。………...采用LU分解有如下特点：（1）LU分解与右端向量无关。先分解，后回代。一般说来，分解的运算次数正比于n回代求解正比与n。求解遇到多次回代时，分解的工作不必重新做。这样节省计算时间。（2）分解按步进行，前边分解得到的信息为后边所用。（3）[A]阵的存储空间可利用，节省存储。32采用LU分解有如下特点：322、特殊方程组的解法（1）追赶法（2）分解法---平方根法2、特殊方程组的解法（1）追赶法（1）追赶法---追赶法与稀疏线性方程组

追赶法仍然保持LU分解特性，它是一种特殊的LU分解。充分利用了系数矩阵的特点，而且使之分解更简单，得到对三对角线性方程组的快速解法。因三对角矩阵的非零元素呈“带状”，我们也因此将它叫做带状矩阵。

（1）追赶法---追赶法与稀疏线性方程组三对角线性方程组：三对角线性方程组：设有方程组Ax=d，其中A为三对角矩阵。假设系数矩阵A满足条件：对A作Crout分解形式为：设有方程组Ax=d，其中A为三对角矩阵。第i个分量第j个分量第i个分量第j个分量追赶法计算公式追赶法计算公式4线性方程组的直接解法课件定理

如果上带宽为q，下带宽为p的n阶带状矩阵A有Doolittle分解。A=LU，则L是下带宽为p的单位下三角矩阵，U是上带宽为q的上三角矩阵。

定理如果上带宽为q，下带宽为p的n阶带状矩阵A有Dooli4线性方程组的直接解法课件下面举实例用追赶法来解三对角方程组。下面举实例用追赶法来解三对角方程组。4线性方程组的直接解法课件

实际问题中，当求解方程组的系数矩阵是对称矩阵时，则用下面介绍的分解法可以简化程序设计并减少计算量。从定理可知，当矩阵A的各阶顺序主子式不为零时，A有唯一的Doolittle分解A=LU。此时，当然有矩阵U的对角线元素uii

0,(i=1,2,,n),将矩阵U的每行依此提出uii，（2）.分解法实际问题中，当求解方程组的系数矩阵是对称矩阵时，由A=AT，得由分解的唯一性有，即：于是可得下面的结论。

由A=AT，得定理3：若对称矩阵A各阶顺序主子式不为零时,

则

A可以唯一分解为A=LDLT

，这里LT为L的转置矩阵。当A有LDLT分解时，利用矩阵运算法则及相等原理易得计算ljk及dk的公式为：定理3：若对称矩阵A各阶顺序主子式不为零时,则

A可以唯一

k=1,2,,n;j=k+1,k+2,,n为减少乘法次数，引入辅助量ujk=ljkdk,则上面公式可写成k=1,2,,n;j=k+1,k+2,,n为减少乘法4线性方程组的直接解法课件4线性方程组的直接解法课件平方根法

设A为正定矩阵，则它的各阶顺序主子式均为正。由前面的定理知，A必有唯一的LDLT分解式

A=LDLT

在解对称正定线性方程组时，系数矩阵A的LDLT分解中D又可分解为D=D1/2D1/2，这里D1/2也是对角矩阵。平方根法应用实例与Matlab应用实例与Matlab4线性方程组的直接解法课件见例4-12；4-13，应用实例4-14见例4-12；4-13，应用实例4-144线性方程组的直接解法课件北京科技大学数理学院卫宏儒weihr@计算方法北京科技大学数理学院计算方法第4章:线性方程组的直接解法第4章:线性方程组的直接解法关键词：高斯消元法主元消元法高斯消元法与主元消元法

高斯消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题关键词：高斯消元法与主元消元法

(一)引言

为便于以下讨论,把涉及到的有关名词及问题的引出暂介绍如下:

如果未知量的个数为n,而且关于这些未知量x1,x2,…,xn

的幂次都是一次的(线性的),那么,n个方程

a11x1+a12x2+…+a1nxn=b1

┆┆

┆(1)an1x1+an2x2+…+annxn=bn

构成一个含n个未知量的线性方程组,称为n阶线性方程组。其中,系数a11,…,a1n,a21,…,a2n,…,an1,…,ann

是给定的常数;b1,…,bn

也是给定的常数,通常称为常数项,或称为方程组的右端.

方程组(1)也常用矩阵的形式表示,写为

Ax=b(一)引言为便于以下讨论,把涉及到的有关名词及问题的其中,A是由系数按次序排列构成的一个n阶矩阵，称为方程组的系数矩阵，x和b都是n维向量，称为方程组的右端向量。.

使方程组(1)中每一个方程都成立的一组数x1*,x2*,…,xn*

称为式(1)的解，把它记为向量的形式，称为解向量。其中,A是由系数按次序排列构成的一个n阶矩阵，称为方程组的系

我们总是希望方程组有解,且有唯一解.由线性代数的克莱姆(cramer)规则可知,如果方程组(1)的系数矩阵A的行列式(一般记为D=ⅠAⅠ)不等于零,那么,这个方程组有唯一解,而且它们可以表示为

xi=Di/D(i=1,…,n)

这里,Di是指D中第i列元素用右端b1,…bn代替构成的行列式.

如果方程组(1)有唯一解,我们按上面的等式求解,就必须计算n+1个n阶行列式.由行列式的定义,n阶行列式包含有n!项,每一项含有n个因子,计算一个n阶行列式就需要做(n-1)n!次乘法.而我们一共要计算n+1个n阶行列式,共需做(n2-1)n!次乘法.此外,还要做n次除法才能算出xi(i=1,…n).也就是说,用这个办法求解就要做

N=(n2-1)n!+n次乘除法运算,这个计算量是大得惊人的.例如,当n=10(即求解一个含10个未知量的方程组),乘除法的运算次数共为32659210次;我们总是希望方程组有解,且有唯一解.由线性代数的克莱当n=40，乘除法运算次数可达3.181049次。对于上百个未知量的方程组，次数运算量就更大了。因此可莱姆规则在理论上尽管是完善的，但在实际计算中却没有什么实用价值。我们将重点讨论求解线性方程组的一种有效的数值方法。

(二)求解线性方程组的消元法

消(元)去法是求解线性方程组

Ax=b(2)和满秩矩阵的逆阵A-1的一种直接方法.尽管它比较古老,但它具有演算步骤,推算公式都系统化的特点(对其中选主元消去法,还可以证明是稳定的).因此,它至今仍然是求解方程组的一种有效的方法.

消去法可以引出几种计算方法,下面按三角形方程组和一般线性方程组的顺序来讨论。当n=40，乘除法运算次数可达3.181049次。对于上1.三角形方程组的解法

三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一，实际上消元法就是通过简化一般线性方程组为三角形方程组后再求解的。上三角方程组的一般形式是：

1.三角形方程组的解法4线性方程组的直接解法课件4线性方程组的直接解法课件4线性方程组的直接解法课件2.Gauss消元法

(一)高斯消去法的求解过程：分为两个阶段:首先，把原方程组化为上三角形方程组，称之为“消去”过程；然后，用逆次序逐一求出三角方程组(原方程组的等价方程组)的解，并称之为“回代”过程。下面分别写出“消去”和“回代”

两个过程的计算步骤。

消去过程:第一步:设a110,取

做(消去第i个方程组的x1)mi1第一个方程+第i个方程

i=2,3,…n则第i个方程变为：2.Gauss消元法(一)高斯消去法的求解过程：分为两个因为可得第一步消元后的方程组为：i,j=2,3,…,ni,j=2,3,…,n因为i,j=2,3,…,ni,j=2,3,…,n第二步:设,取

做(消去第i个方程组的x2,i=3,4,…n)mi2第二个方程+第i个方程

i=3,4,…n类似可得第二步消元后的方程组为：第二步:设,取第k步:设,取

做(消去第i个方程组的xk,i=k+1,k+2,…,n)mik第k个方程+第i个方程

i=k+1,k+2,…n类似可得第k步消元后的方程组为：第k步:设,取继续下去到第n-1步消元，可将线性方程组化为如下上三角方程组:继续下去到第n-1步消元，可将线性方程组化为如下上三角方程组4线性方程组的直接解法课件4线性方程组的直接解法课件4线性方程组的直接解法课件3.主元消元法例1:考虑如下线性方程组的Gauss消元法

求解性

2x2=12x1+3x2=2解:因为a11=0,故此题不能用Gauss消元法求解,但交换方程组的顺序后,就可用Gauss消元法求解了.3.主元消元法例1:考虑如下线性方程组的Gauss消元法例题2:讨论下面方程组的解法0.0001x1+x2=1x1+x2=2

假设求解是在四位浮点十进制数的计算机上进行。0.100010-3x1+0.1000101x2=0.10001010.1000101x1

+0.1000101x2=0.2000101解:本题的计算机机内形式为

因为a11=0.00010,故可用Gauss消元法求解,进行第一次消元时有a22(1)=0.1000101-1040.1000101

(m21=a21/a11=1/0.0001=104)=0.00001105-0.1000105

(对阶计算)=0.0000-0.1000105=

-0.1000105,得三角方程组

0.100010-3x1+0.1000101x2=0.1000101-0.1000105x2=-0.1000105

回代解得x2=1,x1=0

严重失真!

(因为本题的准确解为x1=10000/9999,x2=9998/9999）例题2:讨论下面方程组的解法0.0001x1+x2=1

列主元基本思想及程序框图

用高斯消去法求解线性方程组时,应避免小的主元.在实际计算中,进行第k步消去前,应该在第k列元素aik

(i=k,…,n)中找出绝大值最大者,例如∣a∣=max∣a∣再把第p个方程与第k个方程组进行交换,使apk(k-1)成为主元.我们称这个过程为选主元.由于只在第k列元素中选主元,通常也称为按列选主元(或称部分选主元).

如果在第k步消去前,在第k个方程到第n个方程所有的xk到xn的系数a(i=k,…,n;j=k,…,n)中,找出绝对值最大者,例如 ∣a∣=max∣a∣再交换第k,p两个方程和第k,q两个未知量的次序,使a成为主元.称这个过程为完全选主元。不论是哪种方式选出主元,而后再按上面介绍的计算步骤进行消去的计算,一般都称为选主元的高斯消去法。在实际计算中,常用按列选主元的高斯消去法。

(k-1)(k-1)pk(k-1)ikk≦i≦n(k-1)pq(k-1)ijk≦i,j≦n(k-1)ij(k-1)pq列主元基本思想及程序框图(k-1)(k-1)pk(k-1

用列主元消去法解线性方程组AX=b的程序框图见右图.图中w作控制常数,通常为比较小的正实数,当某个选出的主元或完成消元后的系数ann的绝对值小于w时,就认为detA≈0,从而终止计算.为了节省工作单元图中还用A(k)

冲掉A,b(k)冲掉b,并注意A到的下三角部分都应变为零,而且在第k次消元计算式算出乘数mik后aik不再起作用,故用mik冲掉aik,回代后所得到的解放在数组b内。k<n-1输入n,A,b,wk=1,2,…,n-1选主元,确定ik使|aik,k(k)|=max|ai,k(k)|(k≤i≤n)ik=k|aik,k(k)|<w交换行aik,kakj(j=1,2,…n)bikbk

消元计算aikaik/akkaijaij-aikakjbibi-aikbk(i=k+1,…n)(j=k+1,..n)|ann|<wStop输出detA=0输出结果bi(i=1,2,…n)回代求解bnbn/annbi(bi-∑aijxj)/aii(i=n-1,..,2,1)是否是是否用列主元消去法解线性方程组AX=b的程序框图例三用列主元消去法解方程组解

第一次消元对

因列主元素为a31(1),故先作行变换r1__r3,然后进行消元计算可得

第二次消元对[A(2)|b(2)],因列主元素为a32(2),故先作行变换r2__r3,然后进行消元计算可得

由此回代,得x=(1.9272,-0.69841,0.90038)T与精确解

x=(1.9273,-0.69850,0.90042)T相比较是比较准确的.-0.002x1+2x2+2x3=0.4x1+0.78125x2=1.38163.996x1+5.5625x2+4x3=7.4178-0.002220.4[A(1)|b(1)]=10.7812501.38163.9965.562547.41783.9965.562547.4178[A(2)|b(2)]=0-0.61077-1.0010-0.4747102.00292.00200.40371

3.9965.562547.4178[A(3)|b(3)]=02.00292.00200.4037100-0.39050-0.35160例三用列主元消去法解方程组解第一次消元对

4、高斯消去法的计算量分析

高斯消去法的乘除总运算分析如下：消元次数k消元乘法次数消元除法次数回代乘除法总次数

1n(n-1)n-12(n-1)(n-2)n-2...k(n-k+1)(n-k)n-k..n-12*11n(n+1)/2

故高斯消去法的计算量为N=n(n2-1)/3+n(n-1)/2+n(n+1)/2=n3/3+n2-n/3当N充分大时为n3/34、高斯消去法的计算量分析4线性方程组的直接解法课件

5、方法的特点

由具体计算结果可知,全主元素法的精度优于主元素法,这是由于全主元素是在全体系数中选主元,故它对控制舍入误差十分有效.但全主元素法在计算过程中,需同时作行与列的互换,因而程序比较复杂,计算时间较长.列主元素法的精度虽稍低于全主元素法,但其计算简单工作量大为减少,且计算经验与理论分析均表明,它与全主元素法同样具有良好的数值稳定性,列主元素法是求解中小型稠密性方程组的最好方法之一。

选主元消去法(包括解线性方程组的所有直接的方法)比较适用于中小型方程组.对高阶方程组,即使奇数矩阵是稀疏的,但在计算中很难保持稀疏性,因而有存储量大，程序复杂等不足,所幸的是这一缺点可用迭代法解决.

另外,高斯选主元消去法还可技巧性的解决一些特殊线性方程组。

由于误差的影响,计算过程中可能出现一些坏现象,要尽可能防止,表现在求解线性方程组的消元法比较上,则应该注意要简化运算,减小运算次数,提高效率;提高数值稳定性等.

5、方法的特点（三）线性方程组解对系数的敏感性

在计算过程中，由于计算机字长的有限性，不可避免地产生所谓的舍入误差。同时，由于所求问题的初始数据（例如线形方程组的系数矩阵和右端项系数）往往是带有一定误差的。因此计算结果总是不可避免地带有误差，或者说，如果初始数据有扰动，势必将带来具有一定误差的计算结果。就拿Ax=b来说，由于观测或计算等原因，线性方程组两端的系数A和b都带有误差A和b，这样实际建立的方程组是近似方程组(A+A)(x+x)=b+b。对近似方程组求出的解是原问题的真解x加上误差x,即x+x。而

x是由A及b引起的，它的大小将直接影响所求解的可靠性。这种解依赖于方程组系数的误差A及b的问题，称为线性方程组解对系数的敏感性。（三）线性方程组解对系数的敏感性在计算过程中

方程组的系数矩阵发生微小扰动，就有可能引起方程组性质上的变化，这是方程组本身的“条件问题”。相对误差关系式：设原线形方程组Ax=b

和近似方程组(A+A)(x+x)=b+b在1、A=0,b0

2、A0,b=0方程组的系数矩阵发生微小扰动，就有可能引起方程组性一般情形

由这些关系式可看到，带有扰动的近似方程组中，扰动的大小直接影响着所求解的相对误差，故可作如下定义：定义：设A非奇异，称||A-1||||A||为矩阵A的条件数，记为Cond(A)，即Cond(A)=||A-1||||A||.Cond(A)可反映出方程组解对系数的敏感性。对此，可通过下面的例子加以理解。一般情形由这些关系式可看到，带有扰动的近似方方程组

此方程组的准确解为x1=0,x2=-1。现将其右端加以微小的扰动使之变为：

经计算可得准确解为x1=2,x2=-3.

这两个方程组的解相差很大，说明方程组的解对常数项b的扰动很敏感。同时注意到||A||=4.0001,||A-1||=3.0001104,故有Cond(A)=1.23105,可见条件数很大。方程组一般来说，方程组的条件数越小，求得的解就越可靠；反之，解的可靠性就越差。通常当从方程组Ax=b求出计算解x**后，有时用残向量

r=b-Ax**

的大小来检验x**的精度，认为如果对某种范数||r||很小，就说明是好的。不过要记住这种处理在某些情况下是不准确的。例如，对上述举例的方程组，当用某种方法求得计算解后，则有，显然||r||是很小的，但与其真实解相差很大。为说明这方面的原因，我们可以把残向量r看成是Ax=b的右端有扰动的b，由相对误差关系式，有：不可轻易用残向量||r||的大小来判断计算解的精度。一般来说，方程组的条件数越小，求得的解就越可靠；反之，解的可（四）病态方程组：如果方程组AX=b由于A或b的小扰动而导致解严重失真，则此方程组称为病态方程组，否则称为良态方程组。判定一个病态方程组的简单方法；病态方程组一般不能用解方程组的常有方法求解，而采用“迭代求精法”来计算。（列主元消元法的应用）（四）病态方程组：如果方程组AX=b由于A或b的小扰动而导致(五)、LU分解法

1、LU分解法的基本思想假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU其中L为下三角矩阵，U为上三角矩阵。这样我们可以把线性方程组Ax=b写成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y，则原线性方程组Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,从而求解线性方程组Ax=b的目的。(五)、LU分解法

定义：

1.LU分解:将系数矩阵A转变成等价两个矩阵L和U的乘积，其中L和U分别是下三角和上三角矩阵，而且要求U的对角元素都是1。2.紧凑格式:由于可以把L和U两个矩阵压缩到一个数组中，而且还可以存储在原来的系数矩阵A的数组中。这种LU分解常被称为紧凑格式.

由LU=A及对L和U的要求可以得到分解的计算公式。根据下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及对L和U的要求可以得到分解的计算公式。根据下式(第j个分量第i个分量第j个分量第i个分量根据矩阵乘法及相等的定义,有

得公式