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

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

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

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

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

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

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

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

（1）對A進行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)

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

直接三角分解

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

定理4-1

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

證明：反證法。見p67

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

列主元LU分解的矩陣描述

列主元LU分解計算步驟和公式

P73-744.2.2

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

三對角矩陣與三對角方程組

三對角矩陣的克勞特分解的唯一性

直接進行克勞特分解可得到計算公式

追趕法計算步驟及流程圖（P76）

追趕法計算時的存儲結(jié)構(gòu)定理4-2

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

設A為對稱正定矩陣，則存在一個下三角陣L使得A=LLT

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

4.3直接法的誤差分析

4.3.1病態(tài)方程組

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

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

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