第3章 线性代数方程组数值解法.ppt
- 文档编号:18768018
- 上传时间:2023-11-04
- 格式:PPT
- 页数:120
- 大小:1.49MB
第3章 线性代数方程组数值解法.ppt
《第3章 线性代数方程组数值解法.ppt》由会员分享,可在线阅读,更多相关《第3章 线性代数方程组数值解法.ppt(120页珍藏版)》请在冰点文库上搜索。
3.1引言在这一章,我们将建立解线性方程组的一般方法,然后分析与计算机解题有关的误差并研究控制和降低这些误差的方法,最后介绍解线性方程组的迭代法。
本章讨论形如式(3.1.1)的线性方程组的数值解法。
第3章线性代数方程组的数值解法,(3.1.1),这是一个有n个方程,n个未知数x1,x2,xn的系统,元素aij和bi是实数。
可表示为矩阵形式记x=(x1,x2,xn)Tb=(b1,b2,bn)T,第3章线性代数方程组的数值解法,为n阶方阵方程成为简单形式Ax=b(3.1.2)解线性方程组的方法,在线性代数中有根据Gram法则的方法。
若A为非奇异矩阵,即|A|0,则xi=i/,方程组有唯一解。
其中,为A的行列式,i为中第i列元素被b替代的行列式。
第3章线性代数方程组的数值解法,根据行列式的定义计算一个n阶行列式需要n!
(n1)次乘法,因此,就目前而言,当n稍大一些,在电脑上用Gram法则解线性方程组是不可行的。
回顾中学课本中解一次方程组的方法:
加减消元法。
例3.2.1r32r1:
-3x1=-3x1=1;r2r3:
x2=1行初等变换x1=1,x2=1代入r1:
x3=421=1这里由于人可以方便的判断出r32r1和r2r3可以同时消去2个未知数,很容易的得到了解。
第3章线性代数方程组的数值解法,3.2Gauss消去法计算机不能这样灵活的加减消元,但能按照既定的规则按部就班地进行加减消元。
首先,分别以第1行乘以适当的数加到2n行消去第1列除a11之外的所有元素,然后,第2行分别乘以适当的数加到3n行消去第2列a22以下的所有元素,。
这就是顺序Gauss消去法的消元过程。
本节重点讨论Gauss消去法的基本原理、与矩阵三角分解的关系、计算量和可行性、稳定性。
第3章线性代数方程组的数值解法,3.2.1顺序消去过程和LU三角分解将变换之前的A、b记为A
(1)、b
(1),则方程组(3.1.2)可写为A
(1)x=b
(1),增广矩阵为A,b=A
(1),b
(1)。
第1步消元:
丛r2,r3,rn中消去x1项,条件a11
(1)0,使得A
(2)x=b
(2)A
(1)x=b
(1)其中,第3章线性代数方程组的数值解法Gauss消去法,具体方法:
-(r1
(1)/a11
(1)a21
(1)加到第2行,-(r1
(1)/a11
(1)a31
(1)加到第3行,-(r1
(1)/a11
(1)ai1
(1)加到第i行,-(r1
(1)/a11
(1)an1
(1)加到第n行。
这就使第1列a11
(1)以下元素皆为0。
记l21=a21
(1)/a11
(1);li1=ai1
(1)/a11
(1),i=2,3,n则上述过程可描述为:
以矩阵A
(1),b
(1)中的第1行分别乘以-li1加到2n行,即ri
(1)li1r1
(1)ri
(2),i=2,3,n其中第i行aij
(2)=aij
(1)li1a1j
(1),i,j=2,3,nbi
(2)=bi
(1)li1b1
(1),i=2,3,n,第3章线性代数方程组的数值解法Gauss消去法,第2步消元:
丛r3,r4,rn中消去x2项,条件a22
(2)0,使得A(3)x=b(3)A
(2)x=b
(2)具体方法:
li2=ai2
(2)/a22
(2),ri
(2)li2r2
(2)ri(3),i=3,4,n第k步消元:
丛rk+1,rk+2,rn中消去xk项,条件akk(k)0,使得A(k+1)x=b(k+1)A(k)x=b(k)其中,第3章线性代数方程组的数值解法Gauss消去法,(3.2.1),第3章线性代数方程组的数值解法Gauss消去法,具体方法:
记lik=aik(k)/akk(k),i=k+1,k+2,n(3.2.2)以矩阵A(k),b(k)中的第k行乘以-lik加到i行,即ri(k)likrk(k)ri(k+1),i=k+1,k+2,n其中第i行aij(k+1)=aij(k)likakj(k),i,j=k+1,k+2,n(3.2.3)bi(k+1)=bi(k)likbk(k),i=k+1,k+2,n当完成第k=n1步时,A
(1)变为上三角阵A(n),Gauss消元过程结束,得到与原方程组等价的方程组A(n)x=b(n)(3.2.4),第3章线性代数方程组的数值解法Gauss消去法,其中(3.2.5),第3章线性代数方程组的数值解法Gauss消去法,由(3.2.4)式按倒序可方便的求出解向量x:
这个过程称为Gauss消去法的回代过程。
写成简洁的形式(3.2.6),第3章线性代数方程组的数值解法Gauss消去法,消元过程和回代过程合在一起称为Gauss消去法。
由于消元过程未改变顺序,故称为顺序Gauss消去法。
消元过程的矩阵描述分别以-li1乘以矩阵A
(1),b
(1)中的第1行加到2n行,即ri
(1)li1r1
(1)ri
(2),i=2,3,n其中第i行aij
(2)=aij
(1)li1a1j
(1),i,j=2,3,nbi
(2)=bi
(1)li1b1
(1),i=2,3,n即,第3章线性代数方程组的数值解法Gauss消去法,或A
(1)和,第3章线性代数方程组的数值解法Gauss消去法,相当于用一个初等矩阵L1=Il1e1T左乘A
(1)和b
(1),其中l1=(0,l21,l31,ln1)T,li1=ai1
(1)/a11
(1),i=2,3,n,即L1A
(1)=A
(2),L1b
(1)=b
(2)。
第3章线性代数方程组的数值解法Gauss消去法,其中单位列向量e1=(1,0,0,0,0)T,e2=(0,1,0,0,0)T,en=(0,0,0,0,1)T,,第k步分别以-lik乘以矩阵A(k),b(k)中的第k行加到k+1n行,即ri(k)likrk(k)ri(k+1),i=k+1,k+2,n其中第i行aij(k+1)=aij(k)likakj(k),i,j=k+1,k+2,nbi(k+1)=bi(k)likbk(k),i=k+1,k+2,n相当于用一个初等矩阵Lk=IlkekT左乘A(k)和b(k),其中lk=(0,0,lk+1,k,lk+2,k,ln,k)T,lik=aik(k)/akk(k),i=k+1,k+2,n即LkA(k)=A(k+1),Lkb(k)=b(k+1)。
第3章线性代数方程组的数值解法Gauss消去法,第3章线性代数方程组的数值解法Gauss消去法,第3章线性代数方程组的数值解法Gauss消去法,以上n-1步消元过程用矩阵相乘表示:
A
(1)L1A
(1)=A
(2)L2L1A
(1)=L2A
(2)=A(3)Ln-1Ln-2L2L1A
(1)=Ln-1Ln-2A(n-2)=Ln-1A(n-1)=A(n)和b
(1)L1b
(1)=b
(2)L2L1b
(1)=L2b
(2)=b(3)Ln-1Ln-2L2L1b
(1)=Ln-1Ln-2b(n-2)=Ln-1b(n-1)=b(n),第3章线性代数方程组的数值解法Gauss消去法,矩阵A变换部分A
(1)=(Ln-1Ln-2L2L1)-1A(n)=A(n)令,得到A
(1)=LA(n),即A=LA(n),同理,由向量b变换部分得到b=Lb(n),由初等三角矩阵的性质:
第3章线性代数方程组的数值解法Gauss消去法,对于初等矩阵Li(mi)=ImieiT(2.3.3),第3章线性代数方程组的数值解法Gauss消去法,有如下性质(P.3031)
(1)Li-1(mi)=Li(-mi),|Li|=1,(3)任何一个单位下三角阵LRn都可分裂成L=Im1e1Tm2e2Tmn-1en-1T(4)Li左乘A的结果是从A的各行中减去第i行乘1个因子。
由性质
(1)得,由性质
(2)知,L为单位下三角阵:
(),第3章线性代数方程组的数值解法Gauss消去法,
(2)L=L1(l1)L2(l2)L3(l3)Ln-1(ln-1)为单位下三角阵,令U=A(n),即(3.2.7),第3章线性代数方程组的数值解法Gauss消去法,消元过程最终得到A=LU(3.2.8)上述过程说明,只要主元素,k=1,2,n,Gauss顺序消元过程就可以将A分解为一个单位下三角阵L和一个上三角阵U的乘积,称为A的LU分解,也称为Doolittle分解。
如果分解成上三角阵是单位阵,则称为Crout分解。
利用A的LU分解可以计算A的行列式(determinant)值:
第3章线性代数方程组的数值解法Gauss消去法,综上所述,Gauss顺序消元过程实际上是对A作了LU分解,n1步消元过程将原方程组Ax=b(3.1.2)变为LUx=b令Ux=y,原方程组分解为2个容易求解的三角形方程组Ly=b(3.1.5)Ux=y(3.1.6),求解顺序为先(3.1.5)式,后(3.1.6)式。
对于(3.1.5)式,由于L为下三角阵,故按正序求解(3.2.9),第3章线性代数方程组的数值解法Gauss消去法,对(3.1.6)式仍用(3.2.6)式。
即按倒序可方便的求出解向量x。
事实上,对比式(3.2.4)A(n)x=b(n),并注意到式(3.2.7)A(n)=U,及y=b(n),式(3.1.6)就是式(3.2.4)。
例3.2.1,3.2.2可行性和计算量顺序Gauss消去法的可行性Gauss消去法的的消元过程和回代过程都要求k=1,2,n,否则过程进行不下去。
但是是否等于0,在消元过程中才知道。
如何事先判断,下面的三个定理给出了答案。
定理3.2.1若矩阵A的各阶顺序主子式均不为0,即Dk=detAk0,则。
第3章线性代数方程组的数值解法Gauss消去法,矩阵A的各阶顺序主子式:
D1=|a11|,第3章线性代数方程组的数值解法Gauss消去法,证用归纳法。
k=1时,D1=|a11|0,于是=a110。
设Di0对i=2,3,k-1成立,则只需证明Dk0即可。
由于i=1,2,3,k-1,因此可对A进行k-1次顺序Gauss消元,A变为A(k),A的k阶主子式Ak变为上三角阵Ak(k)。
由于Ak等于单位下三角阵左乘Ak(k),故有detAk=detAk(k),第3章线性代数方程组的数值解法Gauss消去法,即变换前后矩阵行列式的值不变(3.2.11),第3章线性代数方程组的数值解法Gauss消去法,由上式得到Dk0,定理得证。
直接用定理3.2.1判别是不方便的,因为须计算各阶顺序主子式。
以该定理为基础可得到下面两个有实用价值的判别定理。
根据定理3.2.1和定理2.3.8实对称矩阵A正定的充要条件是A的所有顺序主子式一定是正的得到定理3.2.2。
定理3.2.2A对称正定根据定理3.2.1和严格对角占优阵的性质,可以证明定理3.2.3。
定理3.2.3A严格对角占优顺序Gauss消去法的计算量由第k次消元的消元过程计算式(3.2.3)和回代过程的计算式(3.2.6)统计乘除法和加减法的计算量。
第3章线性代数方程组的数值解法Gauss消去法,消元过程的计算量:
aij(k+1)=aij(k)likakj(k),i,j=k+1,k+2,n(3.2.3a)bi(k+1)=bi(k)likbk(k),i=k+1,k+2,n(3.2.3b)a式共有(nk)2个计算式,b式共有(nk)个计算式,每式1次乘法1次减法;lik,i=k+1,k+2,n是两式共用的,须计算(nk)个lik。
每计算1个lik,1次除法。
共有(n1)步消元,即k=1(n1)。
所以消元过程共有乘除法(次):
加减法(次):
第3章线性代数方程组的数值解法Gauss消去法,回代过程的计算量:
(3.2.6),第3章线性代数方程组的数值解法Gauss消去法,式(3.2.6)有n次除法;乘法、减法:
k=n-1,各1次;k=n-2,各2次;k=1=n-(n-1),各n-1次所以回代过程共有乘除法(次)加减法(次),所以顺序Gauss消元的计算量为乘除法(次):
加减法(次):
对比用Gram法则解线性方程组,按定义计算n阶行列式,需n!
(n-1)次乘法(P.61),第3章线性代数方程组的数值解法Gauss消去法,3.2.3数值稳定性:
选主元(Pivoting)1选主元的必要性因为作为除数,主元小误差大。
(每一步消元之前都选)还可解决主元为零的问题。
2选主元:
列选主元,比例列选主元,完全选主元。
例3.2.23Gauss选主元法实现矩阵的三角分解与顺序Gauss消去法的不同之处是,列主元消去法在每一步行变换左乘Lk之前,先要左乘一个排列阵(PermutationMatrix)Pk。
Pk由单位阵的第k行与第ik行交换得到,也就是2.3.3节中的初等置换阵,有性质PkPk=I,Pk-1=Pk,det(Pk)=1,当k=ik时,Pk=I。
第3章线性代数方程组的数值解法Gauss消去法,因此,列主元消去法的消元过程是:
A
(1)L1P1A
(1)=A
(2)L2P2L1P1A
(1)=L2P2A
(2)=A(3)Ln-1Pn-1Ln-2Pn-2L2P2L1P1A
(1)=Ln-1Pn-1A(n-1)=A(n)和b
(1)L1P1b
(1)=b
(2)L2P2L1P1b
(1)=L2P2b
(2)=b(3)Ln-1Pn-1Ln-2Pn-2L2P2L1P1b
(1)=Ln-1Pn-1b(n-1)=b(n),第3章线性代数方程组的数值解法Gauss消去法,即Ln-1Pn-1Ln-2Pn-2Ln-3Pn-3L2P2L1P1A=A(n)=Ln-1Pn-1Ln-2Pn-2L2P2L1P1b=b(n)上式中插入则有Ln-1(Pn-1Ln-2Pn-1)(Pn-1Pn-2Ln-3Pn-2Pn-1)(Pn-1Pn-2P2L1P2Pn-2Pn-1)(Pn-1Pn-2P2P1)A=,第3章线性代数方程组的数值解法Gauss消去法,令上式成为即,第3章线性代数方程组的数值解法Gauss消去法,(3.2.12),用排列阵对单位下三角阵Li进行合同变换,结果i=1,2,n-1,仍是单位下三角阵,因而也是单位下三角阵。
在每次消元时,可以把每次的消元因子放在矩阵A主对角线下方刚被消成0元素的位置上,这样可以节省存储空间,同时,在以后的消元中,这些消元因子随着A一起作行交换,直到消元完成,在A的主对角线下方就形成了单位下三角阵主对角线下方的非0元素部分,即形成,+I就得到。
第3章线性代数方程组的数值解法Gauss消去法,上述过程说明,列主元消去法的消元过程实际上是对增广矩阵作一系列的行交换后,得到与原方程组等价的方程组PAx=Pb再对PA作LU分解,得到与原方程组等价的方程组和是在列主元消元过程中得到的。
令解原方程组等价于解2个三角形方程组:
第3章线性代数方程组的数值解法Gauss消去法,(3.2.13),完全选主元Gauss消去法比列主元消去法多出列交换过程,即右乘排列阵qT,第3章线性代数方程组的数值解法Gauss消去法,即系数矩阵A先左乘P右乘qT,再由消元过程作PAqT的三角分解,得到与原方程组等价的方程组PAqT(qx)=Pb,令,解原方程组等价于解2个三角形方程组:
扩展讨论1如果同时解若干个系数矩阵相同的方程组,如:
Ax=b1,Ax=b2,Ax=b3,Ax=b4,只需对A作一次三角分解,4次利用式(3.2.13)即可。
如果记对应于右端相量bi的解向量为xi,i=1,2,3,4,X=(x1,x2,x3,x4),B=(b1,b2,b3,b4),则解上述4各方程组相当于解方程:
AX=B
(1),第3章线性代数方程组的数值解法Gauss消去法,其中,A=(aij)nRnn,X=(xij)Rn4,B=(bij)Rn4。
2如果对Gauss消去法作一点小修改,每一步消元不仅把该步主对角线元素以下的元素消为0,也把该步主对角线元素以上的元素消为0,即以矩阵A(k),b(k)中的第k行乘以-lik加到除第k行之外的所有行:
ri(k)likrk(k)ri(k+1),i=1,2,k-1,k+1,nk=1(n-1),其中第i行aij(k+1)=aij(k)likakj(k),i=1,2,k-1,k+1,nj=k+1,k+2,nbi(k+1)=bi(k)likbk(k),i=1,2,k-1,k+1,n,第3章线性代数方程组的数值解法Gauss消去法,其中lik=aik(k)/akk(k),i=1,2,k-1,k+1,n最后每一行除以该行对角线元素,实际上仅是同时令全部主对角元素为1。
如此这般,A变为单位阵,b成为解向量,没有回代过程。
这就是Gauss消去法一种变形GaussJordan消去法。
第3章线性代数方程组的数值解法Gauss消去法,3将GaussJordan消去法用于方程组
(1),即对增广矩阵A,B施行讨论2描述的行初等变换使增广矩阵中A部分成为单位矩阵,则B部分就是方程组的解。
若bi的个数等于bi的维数,即B是n阶方阵,则方程组
(1)中的A也是n阶方阵,若B是单位阵,即AX=I
(2)则X=A-1,将GaussJordan消去法用于方程组
(2)的增广矩阵A,I,原A部分成为单位阵的同时,原I部分成为A-1求逆矩阵。
第3章线性代数方程组的数值解法Gauss消去法,3.3矩阵的直接三角分解法对于非奇异矩阵A,可利用Gauss消去法的消元过程对其作LU三角分解。
是否可以利用矩阵相乘及两矩阵相等则其所有元素相等,直接进行三角分解?
答案是肯定的。
但是对于一般的矩阵无便利可图。
而对于一些特殊的矩阵,如本节涉及的三对角阵和对称正定阵,则计算比用Gauss消去法简单。
本节讨论三对角阵和对称正定阵的直接三角分解法。
第3章线性代数方程组的数值解法,3.3.1三对角形方程组的追赶法三对角形方程组Ax=f的系数矩阵除三条对角线外,皆为0元素。
(3.3.1)如果A满足定理3.2.1的条件,则可用Gauss消去法将A分解为(3.3.2)式的LU的乘积,第3章线性代数方程组的数值解法直接三角分解法,(3.3.2)两矩阵相乘
(1),第3章线性代数方程组的数值解法直接三角分解法,比较式(3.3.1)和式
(1),得到ci=di,i=1,2,n-1di=ci,i=1,2,n-1b1=u1u1=b1bi=lidi-1+ui,i=2,3,nli=ai/ui-1,i=2,3,nai=liui-1,i=2,3,nui=bilici-1,i=2,3,n(3.3.3)分解后,Ax=fLUx=f,解原三对角线方程组等效为解两个具有两条对角线的方程组Ly=f和Ux=y,第3章线性代数方程组的数值解法直接三角分解法,计算过程是y1=f1yi=filifi1,i=2,3,n(3.3.4)xn=yn/unxi=(yicixi+1)/ui,i=n1,n2,2,1(3.3.5)式(3.3.3),(3.3.4)和(3.3.5)称为解三对角形方程组的追赶法。
只要三对角线矩阵A满足定理3.2.1,3.2.2和3.2.3的条件,就可以用追赶法。
也可分解成:
L是下三角阵,U是单位上三角阵。
第3章线性代数方程组的数值解法直接三角分解法,条件还可比定理3.2.3宽松。
定理3.3.1设三对角线矩阵A满足
(1)|b1|c1|0
(2)|bn|an|0(3)|bi|ai|+|ci|,aici0,i=2,3,n-1则方程组的解存在唯一,且追赶法通常是数值稳定的解读、证明(略)算账:
分解第3式(n-1)次除法,第4式(n-1)次乘法、减法;(3.3.4)式(n-1)次乘法、减法,(3.3.5b)式(n-1)次乘法、减法、除法,(3.3.5a)式1次除法。
共5(n-1)+1次乘法、除法,3(n-1)次减法,第3章线性代数方程组的数值解法直接三角分解法,实际上,对于满足定理3.3.1的三对角形方程组
(2),可直接用顺序Gauss消去法,也是相当方便的。
(2),第3章线性代数方程组的数值解法直接三角分解法,计算过程是第1步:
第2行减去第1行乘以一个数使a2的位置为0,b2和f2同时改变,但c2不变:
l1a2/b1b2b2l1c1f2f2l1f1第i步:
第i+1行减去第i行乘以一个数使ai+1的位置为0,bi+1和fi+1同时改变,但ci+1不变,即剩余的步骤与第1步完全相同,可以统一表示为:
第3章线性代数方程组的数值解法直接三角分解法,liai+1/bibi+1bi+1licii=1,2,n1(3)fi+1fi+1lifi回代过程xnfn/bn下一步xn-1(fn-1cn-1xn)/bn-1接下来完全一样xi(ficixi+1)/bi,i=n2,2,1(4),第3章线性代数方程组的数值解法直接三角分解法,伪代码程序inputn,(ai),(bi),(ci),(fi)fori=2tondoli-1ai/bi-1bibili-1ci-1fifili-1fi-1enddo(li-1占ai的存储单元)(n-1)次除法+2(n-1)次乘法、减法;,第3章线性代数方程组的数值解法直接三角分解法,xnfn/bnfori=n-1to1step-1doxi(ficixi+1)/bienddo(xi占fi的存储单元)output(xi)(n-1)次乘法、减法、除法+1次除法,3.3.2对称正定阵的Cholesky分解法若矩阵A为对称正定阵,则根据定理3.2.2,0
(1)A可以直接作LU分解,为与Doolittle分解区别,记为L1U1,其中U1=DU0,D=diag(u11,u22,ukk)
(2)根据Gauss消元过程,ukk就是,对ukk开平方,规定取正,即令,则A=L1U1=L1DU0=L1D1/2D1/2U0(3.3.6),第3章线性代数方程组的数值解法直接三角分解法,由于A对称,即A=AT,于是L1DU0=(L1DU0)T=U0TDL1T该分解是唯一的,因此L1=U0T,于是A=L1DL1T=L1D1/2D1/2L1T=LLT其中L=L1D1/2,是对角线元素为正的下三角阵,这种分解方法称为Cholesky分解法。
定理3.2.2设ARnn,A对称正定,则存在一个实的下三角阵L,使A=LLT。
若限定L的对角线元素为正,则这种分解是唯一的。
第3章线性代数方程组的数值解法直接三角分解法,由A=LLT和矩阵乘法规则,有a11=(l11)2l11=(a11)1/2,a21=l21l11l21=a21/l11ai1=li1l11li1=ai1/l11i=2,3,n(Column1),第3章线性代数方程组的数值解法直接三角分解法,a22=(l21)2+(l22)2l22=(a22(l21)2)1/2ai2=li1l21+li2l22li2=(ai2li1l21)/l22i=3,4,n(Column2)(3.3.8)m=i+1,i+2,n(3.3.9)(Columnii=1,2,n),第3章线性代数方程组的数值解法直接三角分解法,Cholesky分解法伪代码程序inputn,(aij)fori=1tondoform=i+1tondoenddoenddooutput(lij),第3章线性代数方程组的数值解法直接三角分解法,利用Cholesky分解法分解后,解原方程组Ax=b等效为解两个三角形方程组Ly=b和LTx=y如果用分解A=LDLT,其中L为单位下三角阵,则无开平方根运算,称为改进的平方根法。
第3章线性代数方程组的数值解法直接三角分解法,3.4范数和误差分析为了讨论线性方程组近似解的误差,这类误差涉及向量和矩阵,需要对Rn中的向量和Rnn中的矩阵的大小引入某种度量向量和矩阵的范数。
在实数域中,数的大小和两个数之差,用绝对值度量;在解析几何中,向量的大小和两个向量之差,用长度或距离度量;向量范数的概念是三维欧氏空间中向量长度或距离概念的推广。
首先将向量长度的概念推广到n维实空间Rn。
第3章线性代数方程组的数值解法,定义2.3.19
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第3章 线性代数方程组数值解法 线性代数 方程组 数值 解法