數(shù)值分析 第三章課件

第三章

線性方程組求解的數(shù)值方法求解1§3.1

消元法思

首先將A化為上三角陣

，路

再回代求解

。=2消元記Step

1：設(shè)

，計(jì)算因子將增廣矩陣第

i

行

?

mi1

×

第1行，得到其中Step

k：設(shè)，計(jì)算因子？且計(jì)算共進(jìn)行n

?1

步3回代如沒果有唯一解.?定理若A的所有順序主子式均不為0，則高斯消元無需換行即可進(jìn)行到底，得到唯一解。注：事實(shí)上，只要A非奇異，即

A?1

存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。4消去法是按照系數(shù)矩陣的主對(duì)角線上的元素（主元）進(jìn)行消元。從而可能出現(xiàn)：某個(gè)主元為零，導(dǎo)致消元過程無法進(jìn)行。當(dāng)某個(gè)主元的絕對(duì)值很小時(shí)，計(jì)算結(jié)果誤差很大。問題?5例：單精度解方程組/*

精確解為和*/8個(gè)8個(gè)用高斯消元法計(jì)算：8個(gè)小主元可能導(dǎo)致計(jì)算失敗。6

全主元消去法每一步選絕對(duì)值最大的元素為主元素，保證。Step

k:

①選取②

If

ik

≠

k

then

交換第

k

行與第

ik

行;If

jk

≠

k

then

交換第

k

列與第

jk

列;③消元注：列交換改變了xi

的順序，須記錄交換次序，解完后再換回來。

列主元消去法省去換列的步驟，每次僅選一列中最大的元。7例：

注：列主元法沒有全主元法穩(wěn)定。例：注意：這兩個(gè)方程組在數(shù)學(xué)上嚴(yán)格等價(jià)。

8用矩陣?yán)碚摲治鱿ǎ?§3.2矩陣三角分解法直接計(jì)算

A

的

LU分解：10直接比對(duì)等式兩端矩陣元素11一般計(jì)算公式：12LU分解求解線性方程組思路13兩步算法：14例：15定義定義一個(gè)矩陣

A

=

(

aij

)n×n

稱為對(duì)稱陣，如果

aij

=

aji

。一個(gè)矩陣

A

稱為正定陣，如果 對(duì)任意非零向量

都成立。

回顧：對(duì)稱正定陣的幾個(gè)重要性質(zhì)

A?1

亦對(duì)稱正定，且aii

>0若不然，則

存在非零解，即存在非零解。

A

的順序主子陣Ak

亦對(duì)稱正定

A

的特征值λi

>0

A的全部順序主子式det(Ak

)>0Cholesky分解：16——對(duì)稱

正定矩陣的分解法將對(duì)稱正定陣A

做LU

分解U=uij=u11u

/

uij

ii111u22unn

記為A對(duì)稱即記

D1/2

=則仍是下三角陣定理設(shè)矩陣A對(duì)稱正定，則存在非奇異下三角陣SWinhcye

ids。eut(i若Ai

>k)限>0?定0使得

L對(duì)角元為正，則分解唯一。注：

對(duì)于對(duì)稱正定陣

A

，從

可知對(duì)任意k

≤

i有

。即

L

的元素不會(huì)增大，誤差可控，不需選主元。17Matlab

中的Cholesky分解函數(shù)chol（）例對(duì)矩陣A=進(jìn)行Cholesky分解。程序18A=[4,1,0;1,4,1;0,1,4];P=chol(A)§

3.3向量和矩陣的范數(shù)為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性，引進(jìn)向量（矩陣）的范數(shù)的概念。19向量范數(shù)定義

Rn空間的向量范數(shù)||·

||

對(duì)任意滿足下列條件：（正定性)對(duì)任意(齊次性)（三角不等式)常用向量范數(shù)：20定義

向量序列收斂于向量是指對(duì)每一個(gè)1

≤i≤n

都有。可以理解為定理Rn

上一切范數(shù)都等價(jià)?？梢岳斫鉃閷?duì)任何向量范數(shù)都成立。21矩陣范數(shù)定義

Rm×n空間的矩陣范數(shù)||·||

對(duì)任意滿足：（正定性)對(duì)任意(齊次性)（三角不等式)(4)*

||

AB||

≤||A

||

·

||B

||

（相容

(當(dāng)m=n時(shí)))22常用矩陣范數(shù)：—向量||

·

||2的直接推廣有可證。Frobenius

范數(shù)對(duì)方陣

以及算子范數(shù)由向量范數(shù)

||

·

||p

導(dǎo)出關(guān)于矩利陣用CAau∈cRhyn×不n

的等p式范數(shù):則特別有：（行和范數(shù)）（列和范數(shù)）（譜范數(shù)）矩陣ATA

的最大特征根23注：我們只關(guān)心有相容性的范數(shù)，算子范數(shù)總是相容的。即使

A中元素全為實(shí)數(shù)，其特征根和相應(yīng)特征向量仍可能是復(fù)數(shù)。將上述定義中絕對(duì)值換成復(fù)數(shù)模均成立。譜半徑定義

矩陣A的譜半徑記為iρ

(A)=

，其中λ

為A

的特征根。ReλλλImλλλλλρ

(A)24定理對(duì)任意算子范數(shù)||

·

||有證明：由算子范數(shù)的相容性，得到將任意一個(gè)特征根

λ

所對(duì)應(yīng)的特征向量

代入定理若A對(duì)稱，則有A對(duì)稱證明：若λ

是A

的一個(gè)特征根，則λ2

必是

A2

的特征根。故得證。對(duì)某個(gè)A

的特征根λ

成立又：對(duì)稱矩陣的特征根為實(shí)數(shù)，即λ2(A)為非負(fù)實(shí)數(shù)，所以2-范數(shù)亦稱為25譜范數(shù)。若矩陣B

對(duì)某個(gè)算子范數(shù)滿足||B||<1，則必有定理①可逆；②有非零解，即存在非零向

證明：①若不然，則量

使得②26例,X=[-3

5]T,分別求A、X的“1-范數(shù)”和“無窮大范數(shù)”Matlab:A=[4,-3;2,1]

,

X=[-3

5]’norm(A,1),

norm(A,inf)norm(X,1),

norm(X,inf)27§3.4解線性方程組的迭代法求解與解

f(x)=0

的不動(dòng)點(diǎn)迭代相似……，將等價(jià)思路改寫為形式，建立迭代。從初值

出發(fā)，得到序列。研究內(nèi)容：28

如何建立迭代格式？

向量序列的收斂條件？

收斂速度？

誤差估計(jì)？迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）直接法：比較適用于中小型方程組。對(duì)高階方程組，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難保持稀疏

性，因而有存儲(chǔ)量大，程序復(fù)雜等不足。稀疏性：迭代法則能保持矩陣的稀疏性，具有計(jì)算簡單，編制程序容易的優(yōu)點(diǎn)，并在許多情況下收斂較快。故能有效地解一些高階方程組。與直接解法的比較29思路30收斂問題3132§3.4.1.雅可比(Jacobi)迭代法333435矩陣簡化記法36收斂與解故如果序列收斂,

則收斂到解.B 稱迭代矩陣.3738Jacobi迭代法的計(jì)算過程如下：39§3.4.2

高斯—塞德爾迭代法4041424344比較：45Gauss-Seidel迭代法的計(jì)算過程：46§3.4.3

松弛法47484950松弛法計(jì)算過程如下：51§3.5迭代法的收斂性52535455565758596061626364656667誤差估計(jì)：68697071一個(gè)例子：§3.7誤差分析72問題的提出：73設(shè)有方程組Ax=b,設(shè)右端項(xiàng)b

有一擾動(dòng)將引起方程組解x的擾動(dòng)設(shè)x是方程組Ax=b

的解,則有方程組1.

b有擾動(dòng)，A無擾動(dòng)74化簡,得由Ax=b

得所以75設(shè)方程組Ax=b,矩陣A

有一擾動(dòng)時(shí),將引起方程組解x的擾動(dòng)設(shè)x是方程組Ax=b

的解,則有方程組2.

A有擾動(dòng)，b無擾動(dòng)76化簡,得取范數(shù)77當(dāng)A和b

均有一擾動(dòng)時(shí),將引起方程組解x的擾動(dòng)。設(shè)x是方程組Ax=b

的解,則有方程組3.

A有擾動(dòng)，b有擾動(dòng)7879條件數(shù):cond(A)=||A–1

||

||A||定義80條件數(shù)的性質(zhì)：