數(shù)值分析-北交大-王兵團(tuán)-3 線性方程組解法

講授：

大型線性方程組計(jì)算機(jī)求解的常用方法的構(gòu)造和原理；

重點(diǎn)論述:

Jacobi迭代法、Seidel迭代法、Guass消元法及LU分解法的原理、構(gòu)造、收斂性等。第三章線性方程組解法§3.2基本概念第3章線性方程組解法*線性方程組的行列式解法對于n

個(gè)方程的n元線性方程組其系數(shù)矩陣則方程組Ax=b

有唯一解如果|A|≠0，*線性方程組的解對于n

個(gè)方程的n元線性方程組直接法

用計(jì)算公式直接計(jì)算出線性方程組的解的方法。在數(shù)值計(jì)算中，迭代法

用迭代公式來求滿足精度要求的近似解的方法。

迭代法是一種逐次逼近線性方程組解的方法。解線性方程組的方法有直接法和迭代法兩大類?！?.3線性方程組的迭代解法第3章線性方程組解法一、基本思想

將線性方程組Ax=b等價(jià)變形為x=Bx+g,然后構(gòu)造向量迭代公式二、構(gòu)造原理1、Jacobi方法的構(gòu)造模式2、Seidel方法的構(gòu)造模式3、Sor方法的構(gòu)造模式方法：

1）將

Jacobi

迭代法：等價(jià)變形不動(dòng)點(diǎn)方程組2）寫成迭代格式Jacobi迭代格式3）取定初始向量可逐次算出向量序列

Seldel迭代法Seidel迭代格式Seidel迭代并不能取代Jacobi迭代!

Sor法得到Sor法迭代格式Sor法是Seidel迭代法的推廣!例：寫出如下程組的3種迭代格式解：先寫出不動(dòng)點(diǎn)方程組：Jacobi迭代格式：Seidel迭代格式：Sor迭代格式：三、迭代分析及向量收斂1、三種迭代法的向量迭格式則有

解出向量x得不動(dòng)點(diǎn)方程組由此得Jacobi迭代的向量迭代格式：記：（*）式可以寫為：同理，有Seidel向量迭代格式：Sor法向量迭代格式：上面三種向量迭代格式可以寫成一種：2、向量收斂定義3、范數(shù)定義及常用范數(shù)定義3.2設(shè)L是數(shù)域K上的一個(gè)線性空間，如果定義在L上的實(shí)值函數(shù)

P(x)滿足:則稱P(.)是L上的一個(gè)范數(shù)，稱

P(x)為x的一個(gè)范數(shù)。比較線性運(yùn)算定義：

數(shù)值分析中常用的線性空間

式中向量

數(shù)值分析中常用的范數(shù)

例如

數(shù)值分析中常用的范數(shù)

矩陣范數(shù)要滿足如上四條！

對比一下向量范數(shù)。定義3.3矩陣A的算子范數(shù)為：例：證明范數(shù)不等式證明：（反證法）假設(shè)I+B不可逆，易知對應(yīng)齊次方程組兩邊取范數(shù)，并利用范數(shù)定義矛盾！故I+B可逆。兩邊取范數(shù)，并利用算子范數(shù)定義

數(shù)值分析中常用的范數(shù)

F范數(shù)不是算子范數(shù)，其他3個(gè)是算子范數(shù)。例如

3、范數(shù)等價(jià)與向量極限

4、譜半徑及其與范數(shù)的關(guān)系矩陣A的譜半徑：定理3.3證明四、迭代法的收斂條件與誤差估計(jì)1、收斂條件定理證明：必要性定理證明：充分性2、收斂的判別條件（充分條件）判別條件I判別條件II判別條件III定理3.7

Sor法收斂的必要條件是松弛因子

滿足0<

<2證明定理3.8設(shè)矩陣B的某種矩陣范數(shù)

2、誤差估計(jì)證明參照非線性方程求根定理的證明，將：絕對值換成范數(shù)、函數(shù)換成矩陣，注意范數(shù)關(guān)系的使用，例3.1用Jacobi迭代法解線性方程組解Jacobi迭代收斂！故所求近似解為準(zhǔn)確解：例3.2：已知方程組1、寫出Jacobi和Seidel迭代格式；2、判別兩種迭代格式的收斂性。解：1、2、得特征值得特征值§3.4線性方程組的直接解法第3章線性方程組解法

直接方法描述

解線性方程組的直接法有Gauss消元法，LU分解法及一些特殊線性方程組的解法等，其中Gauss消元法是直接法的基礎(chǔ)。本章的重點(diǎn)是在一般公式推導(dǎo)上，要注意學(xué)習(xí)和體會(huì)。一、Gauss消元法

1、基本思想

先將線性方程組通過消元方法化為同解的上三角方程組，然后從該三角方程組中按第n個(gè)方程、第n-1個(gè)方程、…、第1個(gè)方程的順序，逐步回代求出線性方程組的解。

2、構(gòu)造原理

Gauss消元法的求解過程分為兩個(gè):“消元”：把原方程組化為上三角方程組；“回代”：求上三角方程組的解。1）記原方程組為

Gauss消元法構(gòu)造過程：消元：第i個(gè)方程變?yōu)榉匠探M（1）變?yōu)橛?jì)算公式：完成了第一步消元！對方程組（2）的后n-1元線性方程組做同樣的處理：

Gauss消元法構(gòu)造過程：方程組（2）變?yōu)椋旱诙较?）Gauss消元公式系數(shù)計(jì)算公式：

順序做了n-1次消元后，方程組（1）變?yōu)槿缦律先欠匠探M：3）回代

Gauss消元法構(gòu)造過程：再從后向前依次解出：,計(jì)算公式為4）Gauss消元公式系數(shù)計(jì)算公式：5）

Gauss消元法計(jì)算公式3、分析1）Gauss消元法的計(jì)算量計(jì)算量3、分析2）Gauss消元法矩陣解釋2）Gauss消元法矩陣解釋第1步消元第n-1步消元后，有L是下三角陣，U是上三角陣。A=D-L-U?3）Gauss消元法可使用的條件4）Gauss消元法的改進(jìn)缺點(diǎn)2：在使用Gauss消元法進(jìn)行計(jì)算機(jī)求解時(shí)，人們發(fā)現(xiàn)有時(shí)求出的解是錯(cuò)誤的。例：研究線性方程組的Gauss消元法求解結(jié)果，假設(shè)計(jì)算在4位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上求解。解：用Gauss消元法得用Gauss消元法求解得其準(zhǔn)確解為可以接受。主元:消元法中用作分母的數(shù);主方程:主元所在的方程。列主元消元法、全主元消元法例：用列主元與全主元方法解方程組解：1）列主元法解：2）全主元法回代得到解Gauss消元法例見書

1、基本思想二、LU分解法

2、構(gòu)造原理

1）

Doolittle分解2）Grout分解3）

LDU分解都稱為三角分解！1）由A=LU及矩陣乘積和相等概念，有

Doolittle分解法的構(gòu)造過程：得出L的第一列和U的第一行元素！2）同理，有

Doolittle分解法的構(gòu)造過程：Doolittle分解計(jì)算公式：

Doolittle分解算法

計(jì)算出Doolittle分解的L和U矩陣上述過程求解

的方法稱為Doolittle分解方法或三角分解法。1)A可以進(jìn)行Doolittle分解的條件定理1、

非奇異矩陣A的Doolittle分解是唯一的。定理2、

若A的各階順序主子式不為零

，則A有唯一的Doolittle分解。易知：能進(jìn)行Gauss消元法就能做Doolittle分解。？3、分析3、分析2）Doolittle分解的緊湊格式例：用LU分解法求解線性方程組解：因?yàn)闆]有指定用哪種LU分解，這里使用Doolittle分解法做之。用緊湊格式計(jì)算。

1、基本思想三、特殊線性方程組解法

利用系數(shù)矩陣的特殊性消除無效的零元計(jì)算來構(gòu)造求解公式以提高效率。

1）追趕法

三對角方程組

三對角矩陣帶狀矩陣帶狀矩陣的三角分解三對角矩陣的LU分解仿照Doolittle方法，有2）追趕法構(gòu)造過程：2）追趕法構(gòu)造過程：

追趕法求解公式為：用追趕法來求解三對角線性方程組，計(jì)算量只是5n-4，這比Gauss消元法的計(jì)算量要小很多。

追趕法算法用上述過程求解

的方法稱為追趕法解法。§3.5線性方程組解對系數(shù)的敏感性第3章線性方程組解法

概念描述解對系數(shù)的敏感性是指方程中由于系數(shù)的變化（擾動(dòng)）導(dǎo)致所求解的變化