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

第三章線性方程組求解的數(shù)值方法求解第三章線性方程組求解的數(shù)值方法求解1§3.1消元法思路首先將A化為上三角陣，再回代求解。=§3.1消元法思路首先將A化為上三角陣，=2消元記Step1：設(shè)，計(jì)算因子將增廣矩陣第i行mi1

第1行，得到其中Stepk：設(shè)，計(jì)算因子且計(jì)算共進(jìn)行？步n

1消元記Step1：設(shè)，計(jì)算因子將增廣矩陣第i3回代如果?沒有唯一解.如果?定理若A的所有順序主子式均不為0，則高斯消元無需換行即可進(jìn)行到底，得到唯一解。注：事實(shí)上，只要A非奇異，即A1存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解?；卮绻?沒有唯一解4消去法是按照系數(shù)矩陣的主對(duì)角線上的元素（主元）進(jìn)行消元。從而可能出現(xiàn)：（1）某個(gè)主元為零，導(dǎo)致消元過程無法進(jìn)行。（2）當(dāng)某個(gè)主元的絕對(duì)值很小時(shí)，計(jì)算結(jié)果誤差很大。問題?消去法是按照系數(shù)矩陣的主對(duì)角線上的元素（主元）進(jìn)行消元。從而5例：?jiǎn)尉冉夥匠探M/*精確解為和*/8個(gè)8個(gè)用高斯消元法計(jì)算：8個(gè)小主元可能導(dǎo)致計(jì)算失敗。例：?jiǎn)尉冉夥匠探M/*精確解為6

全主元消去法每一步選絕對(duì)值最大的元素為主元素，保證。Stepk:①選?、贗fik

k

then交換第k行與第ik

行;Ifjk

k

then交換第k列與第jk

列;③消元注：列交換改變了xi的順序，須記錄交換次序，解完后再換回來。列主元消去法省去換列的步驟，每次僅選一列中最大的元。全主元消去法每一步選絕對(duì)值最大的元素為主元素，保證7例：注：列主元法沒有全主元法穩(wěn)定。例：注意：這兩個(gè)方程組在數(shù)學(xué)上嚴(yán)格等價(jià)。例：注：列主元法沒有全主元法穩(wěn)定。例：注意：這兩個(gè)方程組在8

用矩陣?yán)碚摲治鱿ǎ骸?.2矩陣三角分解法用矩陣?yán)碚摲治鱿ǎ骸?.2矩陣三角分解法9直接計(jì)算A的LU分解：直接計(jì)算A的LU分解：10直接比對(duì)等式兩端矩陣元素直接比對(duì)等式兩端矩陣元素11一般計(jì)算公式：一般計(jì)算公式：12LU分解求解線性方程組思路LU分解求解線性方程組思路13兩步算法：兩步算法：14例：例：15定義一個(gè)矩陣A=(aij)nn稱為對(duì)稱陣，如果aij=aji。定義一個(gè)矩陣A稱為正定陣，如果對(duì)任意非零向量都成立。回顧：對(duì)稱正定陣的幾個(gè)重要性質(zhì)

A1

亦對(duì)稱正定，且aii>0若不然，則存在非零解，即存在非零解。

A

的順序主子陣Ak

亦對(duì)稱正定

A

的特征值i

>0

A

的全部順序主子式

det(Ak

)>0Cholesky分解：

——對(duì)稱

正定矩陣的分解法定義一個(gè)矩陣A=(aij)nn稱為對(duì)稱陣，如果16將對(duì)稱

正定陣

A做LU

分解U=uij=u11uij/uii111u22unn記為

A對(duì)稱即記D1/2=Whyisuii>0?Sincedet(Ak)>0則仍是下三角陣定理設(shè)矩陣A對(duì)稱正定，則存在非奇異下三角陣使得。若限定L對(duì)角元為正，則分解唯一。注：對(duì)于對(duì)稱正定陣A，從可知對(duì)任意ki有。即L

的元素不會(huì)增大，誤差可控，不需選主元。將對(duì)稱正定陣A做LU分解U=uij=u11uij17Matlab中的Cholesky分解函數(shù)chol（）例對(duì)矩陣A=進(jìn)行Cholesky分解。程序A=[4,1,0;1,4,1;0,1,4];P=chol(A)Matlab中的Cholesky分解函數(shù)chol（）例對(duì)矩18§

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

Rn空間的向量范數(shù)||·||對(duì)任意滿足下列條件：（正定性)對(duì)任意(齊次性)（三角不等式)常用向量范數(shù)：向量范數(shù)定義Rn空間的向量范數(shù)||·||對(duì)20定義向量序列收斂于向量是指對(duì)每一個(gè)1in都有。可以理解為定理Rn上一切范數(shù)都等價(jià)。可以理解為對(duì)任何向量范數(shù)都成立。定義向量序列收斂于向量是21矩陣范數(shù)定義

Rmn空間的矩陣范數(shù)||·||對(duì)任意滿足：（正定性)對(duì)任意(齊次性)（三角不等式)(4)*||AB||||A||·||B||

（相容(當(dāng)

m=n

時(shí)))矩陣范數(shù)定義Rmn空間的矩陣范數(shù)||·||22常用矩陣范數(shù)：Frobenius范數(shù)—向量||·||2的直接推廣

對(duì)方陣以及有利用Cauchy不等式可證。算子范數(shù)

由向量范數(shù)||·||p導(dǎo)出關(guān)于矩陣A

Rnn

的p范數(shù):則特別有：（行和范數(shù)）（列和范數(shù)）（譜范數(shù)）矩陣ATA的最大特征根常用矩陣范數(shù)：Frobenius范數(shù)—向量||·||23注：

我們只關(guān)心有相容性的范數(shù)，算子范數(shù)總是相容的。

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

為

A的特征根。ReIm(A)注：我們只關(guān)心有相容性的范數(shù)，算子范數(shù)總是相容的。即24定理對(duì)任意算子范數(shù)||·||有證明：由算子范數(shù)的相容性，得到將任意一個(gè)特征根所對(duì)應(yīng)的特征向量代入定理若A對(duì)稱，則有證明：A對(duì)稱若是A的一個(gè)特征根，則2必是A2的特征根。又：對(duì)稱矩陣的特征根為實(shí)數(shù)，即2(A)為非負(fù)實(shí)數(shù)，故得證。對(duì)某個(gè)

A的特征根成立所以2-范數(shù)亦稱為譜范數(shù)。定理對(duì)任意算子范數(shù)||·||有證明：由算子范數(shù)的相容25若矩陣B對(duì)某個(gè)算子范數(shù)滿足||B||<1，則必有定理①可逆；②證明：①若不然，則有非零解，即存在非零向量使得②若矩陣B對(duì)某個(gè)算子范數(shù)滿足||B||<1，則必有定26例,X=[-35]T,分別求A、X的“1-范數(shù)”和“無窮大范數(shù)”Matlab:A=[4,-3;2,1],X=[-35]’norm(A,1),norm(A,inf)norm(X,1),norm(X,inf)例,X=[27§3.4解線性方程組的迭代法

求解思路與解f(x)=0的不動(dòng)點(diǎn)迭代相似……，將等價(jià)改寫為形式，建立迭代。從初值出發(fā)，得到序列。研究?jī)?nèi)容：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？§3.4解線性方程組的迭代法求解思路與解f(x28迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）稀疏性：迭代法則能保持矩陣的稀疏性，具有計(jì)算簡(jiǎn)單，編制程序容易的優(yōu)點(diǎn)，并在許多情況下收斂較快。故能有效地解一些高階方程組。直接法：比較適用于中小型方程組。對(duì)高階方程組，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難保持稀疏性，因而有存儲(chǔ)量大，程序復(fù)雜等不足。與直接解法的比較迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確29思路思路30收斂問題收斂問題31數(shù)值分析_第三章課件32§3.4.1.雅可比(Jacobi)迭代法§3.4.1.雅可比(Jacobi)迭代法33數(shù)值分析_第三章課件34數(shù)值分析_第三章課件35矩陣簡(jiǎn)化記法矩陣簡(jiǎn)化記法36收斂與解故如果序列收斂,則收斂到解.B稱迭代矩陣.收斂與解故如果序列收斂,則收斂到解.B稱迭代矩陣.37數(shù)值分析_第三章課件38Jacobi迭代法的計(jì)算過程如下：Jacobi迭代法的計(jì)算過程如下：39§3.4.2高斯—塞德爾迭代法§3.4.2高斯—塞德爾迭代法40數(shù)值分析_第三章課件41數(shù)值分析_第三章課件42數(shù)值分析_第三章課件43數(shù)值分析_第三章課件44比較：比較：45Gauss-Seidel迭代法的計(jì)算過程：Gauss-Seidel迭代法的計(jì)算過程：46§3.4.3松弛法§3.4.3松弛法47數(shù)值分析_第三章課件48數(shù)值分析_第三章課件49數(shù)值分析_第三章課件50松弛法計(jì)算過程如下：松弛法計(jì)算過程如下：51§3.5迭代法的收斂性§3.5迭代法的收斂性52數(shù)值分析_第三章課件53數(shù)值分析_第三章課件54數(shù)值分析_第三章課件55數(shù)值分析_第三章課件56數(shù)值分析_第三章課件57數(shù)值分析_第三章課件58數(shù)值分析_第三章課件59數(shù)值分析_第三章課件60數(shù)值分析_第三章課件61數(shù)值分析_第三章課件62數(shù)值分析_第三章課件63數(shù)值分析_第三章課件64數(shù)值分析_第三章課件65數(shù)值分析_第三章課件66數(shù)值分析_第三章課件67誤差估計(jì)：誤差估計(jì)：68數(shù)值分析_第三章課件69數(shù)值分析_第三章課件70數(shù)值分析_第三章課件71一個(gè)例子：§3.7誤差分析一個(gè)例子：§3.7誤差分析72問題的提出：?jiǎn)栴}的提出：73設(shè)有方程組Ax=b,設(shè)右端項(xiàng)b有一擾動(dòng)將引起方程組解x的擾動(dòng)設(shè)x是方程組Ax=b的解,則有方程組1.b有擾動(dòng)，A無擾動(dòng)設(shè)有方程組Ax=b,設(shè)右端項(xiàng)b有一擾動(dòng)74化簡(jiǎn),得由Ax=b得所以化簡(jiǎn),得由Ax=b得所以75設(shè)方程組Ax=b,矩陣A有一擾動(dòng)時(shí),將引起方程組解x的擾動(dòng)設(shè)x是方程組Ax=b的解,則有方程組2.A有擾動(dòng)，b無擾動(dòng)設(shè)方程組Ax=b,矩陣A有一擾動(dòng)76化簡(jiǎn),得取范數(shù)化簡(jiǎn),得取范數(shù)77當(dāng)A和b均有一擾動(dòng)時(shí),將引起方程組解x的擾動(dòng)。設(shè)x是方程組Ax=b的解,則有方程組3.A有擾動(dòng)，b有擾動(dòng)當(dāng)A和b均有一擾動(dòng)時(shí),將引起方程組解x的擾動(dòng)。設(shè)x是方78數(shù)值分析_第三章課件79條件數(shù):cond(A)=||A–1||||A||

定義條件數(shù):cond(A)=||A–1||||A||定80條件數(shù)的性質(zhì)：條件數(shù)的性質(zhì)：81當(dāng)條件數(shù)很大時(shí),方程組Ax=b是病態(tài)問題;當(dāng)條件數(shù)較小時(shí),方程組Ax=b是良態(tài)問題結(jié)論當(dāng)條件數(shù)很大時(shí),方程組Ax=b是病態(tài)問題;當(dāng)條件數(shù)較小82病態(tài)矩陣的例子：病態(tài)矩陣的例子：83在消元過程中，出現(xiàn)小主元。矩陣行列式的值很小，或有某些行（列）近似線性相關(guān)。矩陣元素間的數(shù)量級(jí)相差太大。實(shí)際計(jì)算中，病態(tài)矩陣的判斷：在消元過程中，出現(xiàn)小主元。實(shí)際計(jì)算中，病態(tài)矩陣的判斷：84作業(yè)：P.66~70思考題：1，2，4，8習(xí)題：4，6，7實(shí)驗(yàn)題：4作業(yè)：P.66~7085第三章線性方程組求解的數(shù)值方法求解第三章線性方程組求解的數(shù)值方法求解86§3.1消元法思路首先將A化為上三角陣，再回代求解。=§3.1消元法思路首先將A化為上三角陣，=87消元記Step1：設(shè)，計(jì)算因子將增廣矩陣第i行mi1

第1行，得到其中Stepk：設(shè)，計(jì)算因子且計(jì)算共進(jìn)行？步n

1消元記Step1：設(shè)，計(jì)算因子將增廣矩陣第i88回代如果?沒有唯一解.如果?定理若A的所有順序主子式均不為0，則高斯消元無需換行即可進(jìn)行到底，得到唯一解。注：事實(shí)上，只要A非奇異，即A1存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解?；卮绻?沒有唯一解89消去法是按照系數(shù)矩陣的主對(duì)角線上的元素（主元）進(jìn)行消元。從而可能出現(xiàn)：（1）某個(gè)主元為零，導(dǎo)致消元過程無法進(jìn)行。（2）當(dāng)某個(gè)主元的絕對(duì)值很小時(shí)，計(jì)算結(jié)果誤差很大。問題?消去法是按照系數(shù)矩陣的主對(duì)角線上的元素（主元）進(jìn)行消元。從而90例：?jiǎn)尉冉夥匠探M/*精確解為和*/8個(gè)8個(gè)用高斯消元法計(jì)算：8個(gè)小主元可能導(dǎo)致計(jì)算失敗。例：?jiǎn)尉冉夥匠探M/*精確解為91

全主元消去法每一步選絕對(duì)值最大的元素為主元素，保證。Stepk:①選取②Ifik

k

then交換第k行與第ik

行;Ifjk

k

then交換第k列與第jk

列;③消元注：列交換改變了xi的順序，須記錄交換次序，解完后再換回來。列主元消去法省去換列的步驟，每次僅選一列中最大的元。全主元消去法每一步選絕對(duì)值最大的元素為主元素，保證92例：注：列主元法沒有全主元法穩(wěn)定。例：注意：這兩個(gè)方程組在數(shù)學(xué)上嚴(yán)格等價(jià)。例：注：列主元法沒有全主元法穩(wěn)定。例：注意：這兩個(gè)方程組在93

用矩陣?yán)碚摲治鱿ǎ骸?.2矩陣三角分解法用矩陣?yán)碚摲治鱿ǎ骸?.2矩陣三角分解法94直接計(jì)算A的LU分解：直接計(jì)算A的LU分解：95直接比對(duì)等式兩端矩陣元素直接比對(duì)等式兩端矩陣元素96一般計(jì)算公式：一般計(jì)算公式：97LU分解求解線性方程組思路LU分解求解線性方程組思路98兩步算法：兩步算法：99例：例：100定義一個(gè)矩陣A=(aij)nn稱為對(duì)稱陣，如果aij=aji。定義一個(gè)矩陣A稱為正定陣，如果對(duì)任意非零向量都成立?；仡櫍簩?duì)稱正定陣的幾個(gè)重要性質(zhì)

A1

亦對(duì)稱正定，且aii>0若不然，則存在非零解，即存在非零解。

A

的順序主子陣Ak

亦對(duì)稱正定

A

的特征值i

>0

A

的全部順序主子式

det(Ak

)>0Cholesky分解：

——對(duì)稱

正定矩陣的分解法定義一個(gè)矩陣A=(aij)nn稱為對(duì)稱陣，如果101將對(duì)稱

正定陣

A做LU

分解U=uij=u11uij/uii111u22unn記為

A對(duì)稱即記D1/2=Whyisuii>0?Sincedet(Ak)>0則仍是下三角陣定理設(shè)矩陣A對(duì)稱正定，則存在非奇異下三角陣使得。若限定L對(duì)角元為正，則分解唯一。注：對(duì)于對(duì)稱正定陣A，從可知對(duì)任意ki有。即L

的元素不會(huì)增大，誤差可控，不需選主元。將對(duì)稱正定陣A做LU分解U=uij=u11uij102Matlab中的Cholesky分解函數(shù)chol（）例對(duì)矩陣A=進(jìn)行Cholesky分解。程序A=[4,1,0;1,4,1;0,1,4];P=chol(A)Matlab中的Cholesky分解函數(shù)chol（）例對(duì)矩103§

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

Rn空間的向量范數(shù)||·||對(duì)任意滿足下列條件：（正定性)對(duì)任意(齊次性)（三角不等式)常用向量范數(shù)：向量范數(shù)定義Rn空間的向量范數(shù)||·||對(duì)105定義向量序列收斂于向量是指對(duì)每一個(gè)1in都有。可以理解為定理Rn上一切范數(shù)都等價(jià)?？梢岳斫鉃閷?duì)任何向量范數(shù)都成立。定義向量序列收斂于向量是106矩陣范數(shù)定義

Rmn空間的矩陣范數(shù)||·||對(duì)任意滿足：（正定性)對(duì)任意(齊次性)（三角不等式)(4)*||AB||||A||·||B||

（相容(當(dāng)

m=n

時(shí)))矩陣范數(shù)定義Rmn空間的矩陣范數(shù)||·||107常用矩陣范數(shù)：Frobenius范數(shù)—向量||·||2的直接推廣

對(duì)方陣以及有利用Cauchy不等式可證。算子范數(shù)

由向量范數(shù)||·||p導(dǎo)出關(guān)于矩陣A

Rnn

的p范數(shù):則特別有：（行和范數(shù)）（列和范數(shù)）（譜范數(shù)）矩陣ATA的最大特征根常用矩陣范數(shù)：Frobenius范數(shù)—向量||·||108注：

我們只關(guān)心有相容性的范數(shù)，算子范數(shù)總是相容的。

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

為

A的特征根。ReIm(A)注：我們只關(guān)心有相容性的范數(shù)，算子范數(shù)總是相容的。即109定理對(duì)任意算子范數(shù)||·||有證明：由算子范數(shù)的相容性，得到將任意一個(gè)特征根所對(duì)應(yīng)的特征向量代入定理若A對(duì)稱，則有證明：A對(duì)稱若是A的一個(gè)特征根，則2必是A2的特征根。又：對(duì)稱矩陣的特征根為實(shí)數(shù)，即2(A)為非負(fù)實(shí)數(shù)，故得證。對(duì)某個(gè)

A的特征根成立所以2-范數(shù)亦稱為譜范數(shù)。定理對(duì)任意算子范數(shù)||·||有證明：由算子范數(shù)的相容110若矩陣B對(duì)某個(gè)算子范數(shù)滿足||B||<1，則必有定理①可逆；②證明：①若不然，則有非零解，即存在非零向量使得②若矩陣B對(duì)某個(gè)算子范數(shù)滿足||B||<1，則必有定111例,X=[-35]T,分別求A、X的“1-范數(shù)”和“無窮大范數(shù)”Matlab:A=[4,-3;2,1],X=[-35]’norm(A,1),norm(A,inf)norm(X,1),norm(X,inf)例,X=[112§3.4解線性方程組的迭代法

求解思路與解f(x)=0的不動(dòng)點(diǎn)迭代相似……，將等價(jià)改寫為形式，建立迭代。從初值出發(fā)，得到序列。研究?jī)?nèi)容：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？§3.4解線性方程組的迭代法求解思路與解f(x113迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）稀疏性：迭代法則能保持矩陣的稀疏性，具有計(jì)算簡(jiǎn)單，編制程序容易的優(yōu)點(diǎn)，并在許多情況下收斂較快。故能有效地解一些高階方程組。直接法：比較適用于中小型方程組。對(duì)高階方程組，既使系數(shù)矩陣是稀疏的，但在運(yùn)算中很難保持稀疏性，因而有存儲(chǔ)量大，程序復(fù)雜等不足。與直接解法的比較迭代法：從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確114思路思路115收斂問題收斂問題116數(shù)值分析_第三章課件117§3.4.1.雅可比(Jacobi)迭代法§3.4.1.雅可比(Jacobi)迭代法118數(shù)值分析_第三章課件119數(shù)值分析_第三章課件120矩陣簡(jiǎn)化記法矩陣簡(jiǎn)化記法121收斂與解故如果序列收斂,則收斂到解.B稱迭代矩陣.收斂與解故如果序列收斂,則收斂到解.B稱迭代矩陣.122數(shù)值分析_第三章課件123Jacobi迭代法的計(jì)算過程如下：Jacobi迭代法的計(jì)算過程如下：124§3.4.2高斯—塞德爾迭代法§3.4.2高斯—塞德爾迭代法125數(shù)值分析_第三章課件126數(shù)值分析_第三章課件127數(shù)值分析_第三章課件128數(shù)值分析_第三章課件129比較：比較：130Gauss-Seidel迭代法的計(jì)算過程：Gauss-Seidel迭代法的計(jì)算過程：131§3.4.3松弛法§3.4.3松弛法132數(shù)值分析_第三章課件133數(shù)值分析_第三章課件134數(shù)值分析_第三章課件135松弛法計(jì)算過程如下：松弛法計(jì)