《數(shù)值計(jì)算方法》課件4線性方程組的直接解法

直接法（第4章）思想：對(duì)系數(shù)矩陣進(jìn)行分解、變換，經(jīng)有限次算術(shù)運(yùn)算，求出精確解特點(diǎn)：準(zhǔn)確、可靠、無方法誤差適用：中、小規(guī)模問題，尤其是稠密系數(shù)矩陣問題：舍入誤差對(duì)病態(tài)方程組的影響，算法可能不穩(wěn)定

常見的線性方程組數(shù)值方法分類4.1消去法

4.1.1高斯消去法用高斯消去法求解線性方程組，分為消元過程和回代過程。

消元過程將原始方程組記作。經(jīng)過n-1步消元后，得到記作其中注意：必須確保

回代過程對(duì)于上三角方程組，容易得到

可行性與計(jì)算量1、系數(shù)矩陣A的各階順序階主子式均不為零。2、系數(shù)矩陣A對(duì)稱正定。3、系數(shù)矩陣A嚴(yán)格對(duì)角占優(yōu)。消元和回代的乘除及加減法總次數(shù)如下：高斯消元法的消去過程和回代過程均要求，否則溢出停機(jī)。但在如下情況下，對(duì)原方程組不作任何處理，確保上述條件成立，使高斯消去法在計(jì)算機(jī)上順利執(zhí)行。由于在此不予證明，僅列出一下三個(gè)條件：相比克萊姆法則的乘除法次數(shù)不在一個(gè)數(shù)量級(jí)上，減少了很多。4.1.2高斯列主元消去法為擬制舍入誤差的傳播，在消元過程中希望主元的絕對(duì)值最大，就要在每步消元過程前選主元。通常有列主元和全主元兩種方法。列主元消去法是第k步消元時(shí)，選取作為主元素，進(jìn)行消元。全主元消去法是選取作為第k步的主元素進(jìn)行消元。列主元往往需要行的交換，而全主元不僅需要行的交換，而且可能需要列的交換。列的交換實(shí)質(zhì)上是未知量的交換。列主元素消去法步驟及流程框圖（p63-65）選主元的思想是消除零主元和小主元，策略是對(duì)方稱組進(jìn)行行或列的交換。4.2三角分解法

矩陣的初等（行）變換與初等方陣矩陣的初等變換：三種形式初等方陣：三種形式類型，p(I,j),p(i(k)),p(i(k),j)，與初等變換一一對(duì)應(yīng)初等變換與初等方陣的關(guān)系：初等方陣的逆陣、行列式、乘法此處主要使用第三種形式的初等方陣4.2.1LU分解法高斯消去法的消元過程是通過對(duì)增廣矩陣的初等行變換來完成的。例4-2P67用LU分解法求解線性方程組的步驟

（1）對(duì)A進(jìn)行LU分解，即A=LU；公式見p69（4-5）-（4-8）

（2）求解Ly=b；公式見p69（4-9）

（3）求解Ux=y；公式見p70（4-10）例4-3

p70用LU分解法求解線性方程組的數(shù)據(jù)結(jié)構(gòu)

存儲(chǔ)空間僅需一個(gè)n階的二維數(shù)組和一個(gè)n階的一維數(shù)組（向量）公式思考：如何利用矩陣的LU分解求解矩陣方程Ax=B。4.2.1LU分解法

直接三角分解

可以不經(jīng)過高斯消去過程，直接利用公式得到矩陣的LU分解。令如上的LU分解成為杜利特爾（Doolittle）分解。還有另一種分解法稱為克勞特（Crout）分解，它是將A分解為一個(gè)下三角陣L與一個(gè)單位上三角陣U的乘積的形式。可以自己推導(dǎo)L和U的計(jì)算公式。LU分解的唯一性定理

定理4-1

設(shè)A為n階方陣，若A的各階順序主子式不為零，則A可分解為單位下三角陣L與一個(gè)上三角陣U的乘積，且這種分解是唯一的。

證明：反證法。見p67

LDU分解將LU分解中上三角陣U的對(duì)角線元素提出來，令D=diag（u11,u22,...unn）,則有A=LDU’，其中U’=D-1U是單位上三角陣。這種分解成為L(zhǎng)DU分解。

列主元LU分解的矩陣描述

列主元LU分解計(jì)算步驟和公式

P73-744.2.2

列主元LU分解法4.2.3三對(duì)角方程組的追趕法

三對(duì)角矩陣與三對(duì)角方程組

三對(duì)角矩陣的克勞特分解的唯一性

直接進(jìn)行克勞特分解可得到計(jì)算公式

追趕法計(jì)算步驟及流程圖（P76）

追趕法計(jì)算時(shí)的存儲(chǔ)結(jié)構(gòu)定理4-2

設(shè)A為三對(duì)角矩陣，且對(duì)角占優(yōu)，則對(duì)A可以進(jìn)行克勞特分解，且分解是唯一的。例用追趕法求解三對(duì)角方程組4.2.4對(duì)稱正定矩陣的平方根法定理4-3

設(shè)A為對(duì)稱正定矩陣，則存在一個(gè)下三角陣L使得A=LLT

若限定L的主對(duì)角線元素取正值，則這種分解是唯一的。例P84習(xí)題7

4.3直接法的誤差分析

4.3.1病態(tài)方程組

對(duì)于線性方程組Ax=b，如果A或者b有很小的擾動(dòng)（誤差），但其解會(huì)有很大的擾動(dòng)（誤差），則稱該方程組為病態(tài)方程組。原問題4.3.2矩陣的條件數(shù)

通常用條件數(shù)的大小來度量方程組病態(tài)的程度。

矩陣A的條件數(shù)定義為計(jì)算3階希爾伯特矩陣的條件數(shù)（例4-6）4.4近似解的精度改善基本思想：對(duì)右端項(xiàng)b的誤差反復(fù)迭代，直至誤差滿足要求；用直接法求解方程組。算法步驟：（1）對(duì)A進(jìn)行LU分解，A=LU;令k=1，求解Ly=b及Ux(k)=y得x(k)；（2）計(jì)算r(k)=b-Ax(k)，求解L