數(shù)值分析線性代數(shù)方程組的直接法

數(shù)值分析線性代數(shù)方程組的直接法第1頁，課件共51頁，創(chuàng)作于2023年2月問題驅(qū)動：投入產(chǎn)出分析

投入產(chǎn)出分析是20世紀30年代由美國經(jīng)濟學家首先提出的，它是研究整個經(jīng)濟系統(tǒng)各部門之間“投入”與“產(chǎn)出”關(guān)系的線性模型，一般稱為投入產(chǎn)出模型。國民經(jīng)濟各個部門之間存在著相互依存的關(guān)系，每個部門在運轉(zhuǎn)中將其它部門的成品或半成品經(jīng)過加工（稱為投入）變?yōu)樽约旱漠a(chǎn)品（稱為產(chǎn)出），如何根據(jù)各部門之間的投入-產(chǎn)出關(guān)系，確定各部門的產(chǎn)出水平，以滿足社會的需求，是投入產(chǎn)出綜合平衡模型研究的問題，試討論如下簡化問題。

設國民經(jīng)濟僅由農(nóng)業(yè)、制造業(yè)和服務業(yè)三個部門構(gòu)成，已知某年它們之間的投入和產(chǎn)出關(guān)系、外部需求、初始投入等如表6.1.1所示（數(shù)字表示產(chǎn)值，單位為億元）。第2頁，課件共51頁，創(chuàng)作于2023年2月表6.1.1國民經(jīng)濟各個部門間的關(guān)系表中第一行數(shù)字表示農(nóng)業(yè)總產(chǎn)出為100億元，其中15億元農(nóng)產(chǎn)品用于農(nóng)業(yè)生產(chǎn)本身，20億元用于制造業(yè)，30億元用于服務業(yè)，剩下的35億元農(nóng)產(chǎn)品用于滿足外部需求。類似地可以解釋第二、三行數(shù)字。第一列數(shù)字中，15億元如前所述，30億元是制造業(yè)對農(nóng)業(yè)的投入，20億元是服務業(yè)對農(nóng)業(yè)的投入，35億元的初始投入包括工資、稅收、進口等，總投入100億元和總產(chǎn)出相等。假定每個部門的產(chǎn)出和投入是成正比的，由表6.1.1能夠確定這三個部門的投入產(chǎn)出表，如表6.1.2所示。第3頁，課件共51頁，創(chuàng)作于2023年2月表6.1.2投入產(chǎn)出表表中的第一行，第二列的數(shù)字表示生產(chǎn)1個單位產(chǎn)值的制造業(yè)產(chǎn)品需要投入0.10個單位的產(chǎn)值的農(nóng)產(chǎn)品，同樣第三行、第一列的數(shù)字表示，生產(chǎn)1個單位產(chǎn)值的農(nóng)產(chǎn)品需要0.20個單位的服務業(yè)產(chǎn)值。表6.1.2的數(shù)字稱為投入系數(shù)和消耗系數(shù)，如果技術(shù)水平?jīng)]有變化，可以假設投入系數(shù)是常數(shù)。已知投入系數(shù)如表2.1.2所示，若今年對農(nóng)業(yè)、制造業(yè)和服務業(yè)的外部需求分別為50、150、100億元，試計算三個部門的總產(chǎn)出分別為多少？第4頁，課件共51頁，創(chuàng)作于2023年2月若共有n個部門，記一定時期內(nèi)第i個部門的總產(chǎn)出為xi,其中對第j個部門的投入為xij，滿足的外部需求為di，則

(6.1.1)記第j個部門的單位產(chǎn)出需要第i個部門的投入為aij，在每個部門的產(chǎn)出與投入成正比的假定下，有(6.1.2)投入系數(shù)即為aij，將(6.1.2)式代入(6.1.1)）式得方程組

用矩陣表示為或(6.1.3)因此投入產(chǎn)出模型最終可歸結(jié)為求解線性方程組的問題，下面介紹求解線性方程組數(shù)值方法。第5頁，課件共51頁，創(chuàng)作于2023年2月AX=b（3.1）

第6頁，課件共51頁，創(chuàng)作于2023年2月線性方程組數(shù)值解法的分類直接法（適用于中等規(guī)模的n階線性方程組）

◆

Gauss消去法及其變形

◆矩陣的三角分解法迭代法（適用于高階線性方程組）

◆Jacobi迭代法

◆

Gauss-Seidel迭代法

◆逐次超松弛法

◆共軛斜量法第7頁，課件共51頁，創(chuàng)作于2023年2月§1高斯消去法1．三角形方程組的解法---回代法（3.2）（3.3）

第8頁，課件共51頁，創(chuàng)作于2023年2月2．順序高斯消去法

基本思想：通過消元將上述方程組化為三角形方程組進行求解。第9頁，課件共51頁，創(chuàng)作于2023年2月消元公式回代公式第10頁，課件共51頁，創(chuàng)作于2023年2月順序Gauss消去法可執(zhí)行的前提定理1

給定線性方程組，如果n階方陣的所有順序主子式都不為零，即則按順序Gauss消去法所形成的各主元素均不為零，從而Gauss

消去法可順利執(zhí)行。注：當線性方程組的系數(shù)矩陣為對稱正定或嚴格對角占優(yōu)陣時，按Gauss消去法計算是穩(wěn)定的。第11頁，課件共51頁，創(chuàng)作于2023年2月3、列主元Gauss消去法計算步驟：1、輸入矩陣階數(shù)n，增廣矩陣

A(n,n+1);2、對于(1)按列選主元：選取l使

(2)如果，交換A(n,n+1)的第k行與第l

行元素(3)

消元計算：3、回代計算第12頁，課件共51頁，創(chuàng)作于2023年2月4．無回代過程的主元消去法(Gauss-Jordan)第一步：選主元，在第一列中選絕對值最大的元素，設第k行為主元行，將主元行換至第一行，將第一個方程中x1的系數(shù)變?yōu)?，并從其余n–1個方程中消去x1。第二步：在第二列后n–1個元素中選主元，將第二個方程中

x2的系數(shù)變?yōu)?，并從其它n–1個方程中消去x2。第k步：在第k列后n–k個元素中選主元，換行，將第k個方程xk的系數(shù)變?yōu)?，從其它n-1個方程中消去變量xk…………第13頁，課件共51頁，創(chuàng)作于2023年2月消元公式為：對k=1,2,…,按上述步驟進行到第n步后，方程組變?yōu)椋杭礊樗蟮慕獾?4頁，課件共51頁，創(chuàng)作于2023年2月注：無回代的Gauss消元法實際上就是將方程組的系數(shù)矩陣化為行最簡形矩陣。第15頁，課件共51頁，創(chuàng)作于2023年2月5．無回代消去法的應用（1）解線性方程組系設要解的線性方程組系為：AX=b1,AX=b2,…AX=bm上述方程組系可以寫為AX=B=(b1,…,bm)第16頁，課件共51頁，創(chuàng)作于2023年2月因此 X=A-1B即為線性方程組系的解。

在計算機上只需要增加幾組右端常數(shù)項的存貯單元，其結(jié)構(gòu)和解一個方程組時一樣。行系數(shù)右端第17頁，課件共51頁，創(chuàng)作于2023年2月（2）求逆矩陣設A=(aij)nn是非奇矩陣，A

0，且令由于AA-1=AX=I因此，求A-1的問題相當于解下列線性方程組相當于（1）中m=n,

B=I的情形。

第18頁，課件共51頁，創(chuàng)作于2023年2月（3）求行列式的值用高斯消去法將

A化成上三角形第19頁，課件共51頁，創(chuàng)作于2023年2月例

用Gauss-Jordan消去法解方程組

，并求出

其中解：把系數(shù)矩陣、單位矩陣和右端項組成增廣矩陣，對增廣矩陣實行Gauss-Jordan消元過程。第20頁，課件共51頁，創(chuàng)作于2023年2月故，系數(shù)矩陣的逆為第21頁，課件共51頁，創(chuàng)作于2023年2月§2解三對角方程組的追趕法第22頁，課件共51頁，創(chuàng)作于2023年2月第23頁，課件共51頁，創(chuàng)作于2023年2月§3矩陣的三角分解法

高斯消元法的矩陣形式

每一步消去過程相當于左乘初等下三角矩陣Lk第24頁，課件共51頁，創(chuàng)作于2023年2月記第25頁，課件共51頁，創(chuàng)作于2023年2月A

的

LU

分解(LUfactorization)第26頁，課件共51頁，創(chuàng)作于2023年2月定理2：（矩陣的三角分解）設A為nn實矩陣，如果求解AX=b用順序高斯消去法能夠完成（即），則矩陣A可分解為單位下三角矩陣L與上三角矩陣U的乘積。

A=LU且這種分解是唯一的。第27頁，課件共51頁，創(chuàng)作于2023年2月注：（1）L為單位下三角陣而U為一般上三角陣的分解稱為Doolittle

分解（2）L為一般下三角陣而U為單位上三角陣的分解稱為Crout分解。

第28頁，課件共51頁，創(chuàng)作于2023年2月Doolittle分解法：通過比較法直接導出L和U的計算公式。思路第29頁，課件共51頁，創(chuàng)作于2023年2月LU分解求解線性方程組第30頁，課件共51頁，創(chuàng)作于2023年2月直接三角分解法解AX=b的計算公式對于r=2,3,…,n計算（2）計算U的第r行元素

（3）計算L的第r列元素(r

n)(1)第31頁，課件共51頁，創(chuàng)作于2023年2月(4)(5)第32頁，課件共51頁，創(chuàng)作于2023年2月例用矩陣的三角分解法解方程組第33頁，課件共51頁，創(chuàng)作于2023年2月Doolittle分解法的變形緊湊格式的Doolittle分解法例所以第34頁，課件共51頁，創(chuàng)作于2023年2月緊湊格式的列主元Doolittle分解法例第35頁，課件共51頁，創(chuàng)作于2023年2月§4平方根法1．矩陣的LDR分解定理3：如果n階矩陣A的所有順序主子式均不等于零，則矩陣A存在唯一的分解式A=LDR，其中L和R分別是n階單位下三角陣和單位上三角陣，D是對角元素不為零的n階對角陣，上述分解稱為A的LDR分解。第36頁，課件共51頁，創(chuàng)作于2023年2月2．平方根法

如果A為對稱正定矩陣，則存在一個實的非奇異下三

角矩陣，使A=LLT，且當限定的對角元素為正時，這種分解是唯一的，稱為矩陣A的cholesky分解。定理4：（對稱正定矩陣的三角分解）第37頁，課件共51頁，創(chuàng)作于2023年2月將對稱

正定陣

A做LU

分解U=uij=u11uij/uii111u22unn記為

A對稱即記D1/2=則仍是下三角陣，且有對稱正定陣cholesky分解的實現(xiàn)第38頁，課件共51頁，創(chuàng)作于2023年2月用平方根法解對稱正定線性代數(shù)方程組的算法（1）對矩陣A進行Cholesky分解，即A=LLT，由矩陣乘法：對于i=1,2,…,n計算第39頁，課件共51頁，創(chuàng)作于2023年2月（2）求解下三角形方程組

（3）求解LTX=y第40頁，課件共51頁，創(chuàng)作于2023年2月3．改進平方根法

其中第41頁，課件共51頁，創(chuàng)作于2023年2月改進平方根法解對稱正定方程組的算法第42頁，課件共51頁，創(chuàng)作于2023年2月令LTX=y，先解下三角形方程組LDY=b得解上三角形方程組LTX=Y得第43頁，課件共51頁，創(chuàng)作于2023年2月求解時，A和的誤差對解有何影響？設A精確，有誤差，得到的解為，即絕對誤差放大因子又相對誤差放大因子§5線性方程組的性態(tài)和解的誤差分析第44頁，課件共51頁，創(chuàng)作于2023年2月§6ErrorAnalysisfor.

設精確，A有誤差，得到的解為，即

Waitaminute…

Whosaidthat(I+A1A)isinvertible?(只要A充分小，使得是關(guān)鍵的誤差放大因子，稱為A的條件數(shù)，記為cond(A),越則A越病態(tài)，難得準確解。大第45頁，課件共51頁，創(chuàng)作于2023年2月例：Hilbert陣cond(H2)=27cond(H3)748cond(H6)=2.9106cond(Hn)asn注：現(xiàn)在用Matlab數(shù)學軟件可以很方便求矩陣的狀態(tài)數(shù)!定義2:設線性方程組的系數(shù)矩陣是非奇異的,如果cond(A)越大,就稱這個方程組越病態(tài).反之,cond(A)越小,就稱這個方程組越良態(tài).第46頁，課件共51頁，創(chuàng)作于2023年2月一般判斷矩陣是否病態(tài)，并不計算A1，而由經(jīng)驗得出。行列式很大或很小（如某些行、列近似相關(guān)）；元素間相差大數(shù)量級，且無規(guī)則；主元消去過程中出現(xiàn)小主元；特征值相差大數(shù)量級。第47頁，課件共51頁，創(chuàng)作于2023年2月近似解的誤差估計及改善：設的近似解為，則一般有cond(A)誤差上限改善方法(1)：Step1:近似解Step2:Step3:Step4:若可被精確解出，則有就是精確解了。經(jīng)驗表明：若A不是非常病態(tài)（例如：），則如此迭代可達到機器精度；但若A病態(tài)，則此算法也不能改進。第48頁，課件共51頁，創(chuàng)作于2023年2月改善方法(2)對方程組進行預處理，即適當選擇非奇異對角陣D，C,使求解Ax=b的問題轉(zhuǎn)化為求解等價方程組DAC[C-1x]=Db,且使DAC的條件數(shù)得到改善。（P88，例3.10）用雙精度進行計算，以便改善和減輕病態(tài)矩陣的影響。第49頁，課件共51頁，創(chuàng)作于2023年2月歷史與注記

高斯(CarlFriedrichGauss,1777-1855)高斯是德國數(shù)學家、物理學家、天文學家。1777年生于德國布倫瑞克，1855年在哥廷根逝世。高斯是近代數(shù)學奠基者之一，在歷史上影響之大，可以和阿基米德、牛頓、歐拉并列，有“數(shù)學王子”之稱。1795年進入格丁根大學學習。1798年轉(zhuǎn)入黑爾姆施泰特大學，1799年獲博士學位。1807年以后一直在格丁根大學任教授和哥廷根天文臺臺長，一直到逝世。1833年和物理學家W.E.韋伯共同建立地磁觀測臺，組織磁學學會以聯(lián)系全世界的地磁臺站網(wǎng)。