第2章線性方程組的直接解法

第2章線性方程組的直接解法

/*Directmethodsforthesolutionoflinearsystems*/線性方程組：矩陣形式HomogeneoustermCoefficientmatrixorUnknownvariables線性方程組由增廣矩陣唯一確定通過某種迭代系統(tǒng)（公式）求得近似解，優(yōu)點：編程簡單缺點：存在收斂性和收斂速度問題Howtogetthesolution？

CoefficientmatrixA低階稠密陣高階稀疏陣smalldensematrixlargesparsematrixDirectmethodsIteration

methods

Gaussianelimination列/行/完全主元素(pivoting)消去法Gauss-JordaneliminationSquareroot/improvedsquarerootmethods追趕法JaccobiiterationGauss-SideliterationSORExistenceanduniquenessofthesolution？Cramerrule:Computationcost:(n+1)!

上萬階，零元素很多，非零元素很少非零元素較多，零元素較少經(jīng)過有限步算術(shù)運算直接求得精確解（在沒有舍入誤差的情況下），但實際上機器總存在舍入誤差，因此求得的是近似解Gaussianelimination--通過初等變換將原方程組化成三角方程租來求解-2*(1)+(3)

(2)+(3)

回代求解Step1.DenoteAx=bas

Suppose

let-li1*(1)+(i),i=2,…,nGeneralprocedureofGaussianelimimation初等行變換,相當(dāng)于左乘初等行變換矩陣-li1*row1+rowi,i=2,…,nformulaeDirectlyreplacewith0LeavealoneNeedtobeupdatedConvenientinusingMatlab,Mathmatica,Maple第i行第1列Stepk.Afterk-1eliminations,wehaveletSuppose

-lik*(k)+(i),i=k+1,…,n-lik*rowk+rowi,i=k+1,…,n初等行變換,相當(dāng)于左乘初等行變換矩陣LeavealoneNeedtobeupdatedDirectlyreplacewith0第i行第k列formulaek=1,…n-1ConvenientinusingMatlab,Mathmatica,Maplek=1,…n-1消元過程對角線元素全為1，非對角線上除第i行第k列元素為lik外其余元素全為0要使Gauss消去法能夠進行下去，必須有約化后的主對角元素非零，即矩陣A在什么條件下能夠保證此條件成立？Lemma1A的順序主子式(n-k)

×kk×k,det=Dik×k,det=1k×k,det=0k×(n-k)證明要點InferenceTheorem1

可通過Gauss消去法將線性方程組化為三角方程組InGaussianelimination,ifacertaindiagonalelementvanishes,thenyoucan’tcontinueeliminating.Choosecolumn/row/overallmainelement!Right.Evenifitisverysmall,youcan’tdothatbecauseitwillcauseerrorExpandandthescaleincreasedramaticallythenwhatshouldwedo?列主元Gausspletepivoting行主元完全主元-1/2×2行+3行2,3行互換列主元列主元例1用Gauss列主元消去法解方程組Solution:消元回代求解：1,2行互換-2/5×1行+2行-1/5×1行+3行方程的根x對角線下方元素對角線上方元素假設(shè)已是列主元，否則在對角線下方選列主元，做行置換Gauss-Jordan消去法—無回代過程的列主元消去法：Gauss列主元消去法只消去對角線下方的元素，Gauss-Jordan消去法同時消去對角線下方和上方的元素設(shè)已經(jīng)過k-1步G-J消元，得到第k步消元formulaeG-J消元過程k=1,…nGauss-Jordan消去法能夠進行下去的條件和前面一樣！計算量高于Gauss列主元消去法，通常用G-J消去法求矩陣的逆(初等行變換)列主元Example2用Gauss-Jordan消去法解方程組Solution:消元列主元1,2行互換-2/5×1行+2行-1/5×1行+3行2,3行互換-5/14×2行+1行-1/2×2行+3行5×3行+1行-8.4×3行+2行各行/對角線元素example3用Gauss-Jordan消去法求矩陣的逆solution1,2行互換-1/2×1行+2行-1/2×1行+3行2,3行互換-0.4×2行+1行-0.6×2行+3行-4×3行+1行-15×3行+2行各行/對角線元素CramerruleGausselimination(LUfactorization)Gauss-Jordanelimination(n+1)!n3/3n3/239916800n=10430500ComputationcostdetLk=1,Lkinvertible,k=1,2,…,n-1矩陣的直接三角分解(LU分解，不選主元)k=1,2,…,n-1上三角陣單位下三角陣單位下三角陣上三角陣LU分解定理A的各階順序主子式單位下三角陣上三角陣!L,U證明要點存在性不必證,見前面的分析,僅證唯一性(采用反正法)L,U,L1U1都可逆單位下三角上三角陣矩陣的直接三角分解(LU分解)對解線性方程組有什么幫助？三角方程組，易于求解L矩陣直接三角分解(LU分解)中如何求L和U的元素？矩陣乘法A的第一行U的第一行A的第一列L的第一列ULrk=0,k=r+1,…,n;Lrr=1設(shè)已知U的前r-1行，L的前r-1列，求U的第r行，L的第r列A的第r行U的第r行Ukr=0,k=r+1,…,n;A的第r列L的第r列LUfactorizationr=2,…,n---DoolittlefactorizationA24Example4用緊湊格式解線性方程組solution12341112612376246UL平方根法和改進的平方根法—A對稱正定DU0Asymmetricandpositivedefinite單位下三角diagonal單位上三角單位下三角上三角單位下三角上三角LU分解的唯一性Choleskyfactorization用直接分解法確定的元素的遞推公式Obviously,ifj>i,thenlij=0Elsej<iifk>j,thenljk=0

GivenAx=b,whereAissymmetricandpositivedefinite,whatdoesCholeskyfactorizationtodowithsolutionofAx=b三角方程組，易于求解對系數(shù)矩陣為對稱正定的線性方程組，先對A作Chloesky分解，然后將方程組化成兩個三角方程組求解的方法稱為解線性方程組的平方根法，計算量是n3/6,是Gauss法的一半，只要存儲下半個三角即可GivenAx=b,whereAissymmetricandpositivedefinite,whatdoesCholeskyfactorizationtodowithsolutionofAx=bExample5用平方根法解方程組solutionA對稱正定diagonal改進的平方根法—避免平方根法中的開方運算單位下三角Obviously,ifj>i,thenlij=0andljj=1;elsej<i三角方程組，易于求解改進的平方根法計算量與平方根法類似，但不需開方，只需存儲下三角部分三對角方程組追趕法—求解三對角方程組三對角矩陣Theorem4

若三對角矩陣A為弱對角占優(yōu)，即滿足則它可唯一分解成單位下二對角陣L和上二對角陣U的乘積追趕法的代數(shù)基礎(chǔ)三角方程組，易于求解追趕追趕法的求解過程就是將系數(shù)矩陣分解兩個簡單的二對角矩陣，從而歸結(jié)為求解兩個簡單方程組的過程。追趕法的原理和高斯消去法相同，但考慮到方程組的特點，計算時會把大量零元素撇開，從而大大節(jié)省計算量：5n-4次乘除法.用4個一維數(shù)組存放ai,bi,

ci,

di,li

占ai,ui

占bi,yi

占di,xi

占yisummaryCramerruleGausseliminationLUfactorizationGauss-JordaneliminationSquareroot/improvedsquareroot追趕法(n+1)!n3/3n3/3n3/2n3/65n-4pletePivotingOnlyeliminatingelementsinacolumnbelowthediagonaloneNopivotingDirectlyfactorizationcolumnpivotingEliminatingelementsinarowexceptforthediagonalelementAsymmetricandpositivedefiniteNopivotingA三對角，弱對角占優(yōu)reviewSetX:具有一定性質(zhì)的對象的全體，元素?zé)o大小，元素間無代數(shù)結(jié)構(gòu)和拓?fù)浣Y(jié)構(gòu)距離空間(X,p)：元素間有距離量度，可定義點列收斂概念（極限—一切分析的基礎(chǔ)），有了拓?fù)浣Y(jié)構(gòu)集合上定義距離:x,yX,對應(yīng)實數(shù)p(x,y)R,滿足距離公理:p(x,y)0(非負(fù)性),p(x,y)=p(y,x)(對稱性)、p(x,y)

p(x,z)+p(z,y)(三角不等式）數(shù)域K上的線性空間(X,K)：元素間有代數(shù)運算，有了代數(shù)結(jié)構(gòu)；--數(shù)學(xué)的開始集合上定義線性代數(shù)結(jié)構(gòu)(線性運算—最基本的運算):x,yX加法封閉(且滿足交換律、結(jié)合律、存在零元素、逆(負(fù))元素):x+y=y+xX;x+(y+z)=(x+y)+zX;0X,x+0=x;-xX,x+(-x)=0;數(shù)乘封閉(且滿足結(jié)合律、數(shù)的分配律):a,bKa(bx)=(ab)x;1x=x,0x=0;(a+b)x=ax+bx;a(x+y)=ax+ay線性空間上定義范數(shù):xX,對應(yīng)非負(fù)實數(shù)x,滿足范數(shù)公理:x=0x=0(非負(fù)性)；ax=ax(齊性);x+

y

x+y,(三角不等式）數(shù)域K上的賦范線性空間(X,K):元素間有代數(shù)運算(代數(shù)結(jié)構(gòu))；元素本身有大小度量，范數(shù)可導(dǎo)出距離，從而有收斂概念，有拓?fù)浣Y(jié)構(gòu)線性空間上定義內(nèi)積:x,yX,對應(yīng)!數(shù)(x,y)K,滿足內(nèi)積公理:(x,x)0,(x,x)=0x=0(正定性)(ax+by,z)=a(x,z)+b(y,z)(線性)；(x,y)=(共軛對稱性)數(shù)域K上的內(nèi)積空間(X,K):元素間不僅有代數(shù)運算(代數(shù)結(jié)構(gòu))，而且有內(nèi)積運算,從而有正交概念和幾何結(jié)構(gòu)；內(nèi)積可導(dǎo)出范數(shù)和距離，從而元素有大小和距離，有收斂概念，有拓?fù)浣Y(jié)構(gòu)分析的對象賦范線性空間算子數(shù)空間泛函函數(shù)微積分抽象函數(shù)泛函分析研究空間、算子的普遍規(guī)律。以各種學(xué)科為具體背景，把客觀世界中的研究對象抽象為元素和空間，對象間的關(guān)系抽象為算子。從而把表面不相關(guān)的學(xué)科統(tǒng)一在它的普遍規(guī)律和共同框架之下。具有高度的抽象性和廣泛的應(yīng)用性。是數(shù)值分析的基礎(chǔ)。向量范數(shù)與矩陣范數(shù)Vectormatrix常用的向量范數(shù)例向量范數(shù)的性質(zhì)設(shè)為Rn中一向量序列，Def1向量序列收斂Def2向量范數(shù)等價為Rn中任一兩種向量范數(shù)，若const.a,b,s.t.xRn,有具有可傳遞性(任一向量范數(shù))是分量x1,x2,…,xn的連續(xù)函數(shù)Rn中任意兩種向量范數(shù)等價性質(zhì)1三角不等式性質(zhì)2連續(xù)性性質(zhì)3等價性性質(zhì)4收斂等價性TaketheorthogonalbaseofRn:e1,e2,…,en,x,yRn,wehaveTrangularinequalityProofofproperty2TrangularinequalityProofofproperty3Weonlyneedtoprove,orconst.a,b,s.t.xRn,有denoteBoundedclosesetiscontinuousonP,soithasmaximumMandminimummandM,m>0onP0xRn,Forx=0,theequationholdsobviously,soweonlyneedtoprovethecasex0TakeM=b,m=aProofofproperty4Def2矩陣范數(shù)ARn×n,若有非負(fù)實值函數(shù)N(A)滿足A0,A0A=0;(正定性)cA=c·A,cR;(齊次)A+BA+B;(三角不等式)ABA·B則稱N(A)是Rn×n上的矩陣范數(shù)。exampleFrobeniusnormDef4

矩陣范數(shù)與向量范數(shù)相容xRn,ARn×n,若矩陣范數(shù)和向量范數(shù)滿足

AxA·x

---相容性條件則稱矩陣范數(shù)與向量范數(shù)相容。Def5

矩陣的算子范數(shù)xRn,ARn×n,給定一種向量范數(shù)x

p

，例如p=1,2,,相應(yīng)的定義一個矩陣的非負(fù)函數(shù)滿足矩陣范數(shù)條件和相容性條件，稱為A的算子范數(shù)。checkWhat’stherelationbetweenAxandA,x

?Rn

,x

xAxAcheck常用的矩陣算子范數(shù)行范數(shù),p=1列范數(shù),p=22范數(shù),p=3checkxRn,ARn×ncheck1.1IncaseA=0,theequationholdsobviously,soweonlyneedtocheckforthecaseA0.1.2

y,s.t.1.11.2

y,s.t.supposeSimilarly,wecanprovetheresultin21.11.2

y,s.t.1.1

IncaseA=0,theequationholdsobviously,soweonlyneedtocheckforthecaseA0.1.2

y,s.t.Symmetricandpositivedefinite,SocharacteristicvaluesofAtAareallnonnegativerealnumbers:Letthecorrespondingcharacteristicvectorsare

1.1

1.2

y,s.t.例Def6矩陣的譜半徑譜半徑的性質(zhì)1.矩陣A的譜半徑不超過它的任何一種算子范數(shù)，包括F-范數(shù)Letbeanyeigen-alueofA,xthecorrespondingcharacteristiceigen-vector,Letλi

beanyeigen-valueofA,uithecorrespondingeigen-vectorSoisaneigen-valueofAtA,uithecorrespondingeigen-vectorTh1Supposedet(I±B)=0,thenContradictto

perturbationperturbationIt’sfunnythatsuchsmallperturbationsinthecoefficientsleadtosobigchangeinthesolution!That’sright!it’sduetothenatureofAand

Suchasystemissaidtobeill-posed.Erroranalysis由實際問題建立起來的線性方程組Ax=b本身存在模型誤差和觀測誤差，或者是由計算得到的，存在舍入誤差等。總之，A,b都會有一定擾動A

,b,因此實際處理的是A+A或b+b，我們需要分析A或b的擾動對解的影響。

x

—exactsolutionx+x

—exactsolution當(dāng)方程組的系數(shù)矩陣A和齊次項b受到擾動A

,b后，其解x會受到怎樣的擾動？分三種情況討論1.b有擾動b,A無擾動(A=0)解的相對誤差齊次項b的相對誤差當(dāng)b受到擾動b時，引起的解的相對誤差不超過b的相對誤差的A·A-1倍

2.A有擾動A,b無擾動(b=0)解的相對誤差