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

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

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

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

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

k

then交換第k行與第ik

行;Ifjk

k

then交換第k列與第jk

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

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

A1

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

A

的順序主子陣Ak

亦對稱正定

A

的特征值i

>0

A

的全部順序主子式

det(Ak

)>0Cholesky分解：

——對稱

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

正定陣

A做LU

分解U=uij=u11uij/uii111u22unn記為

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

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

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

Rn空間的向量范數(shù)||·||對任意滿足下列條件：（正定性)對任意(齊次性)（三角不等式)常用向量范數(shù)：向量范數(shù)定義Rn空間的向量范數(shù)||·||對20定義向量序列收斂于向量是指對每一個1in都有?？梢岳斫鉃槎ɡ鞷n上一切范數(shù)都等價?？梢岳斫鉃閷θ魏蜗蛄糠稊?shù)都成立。定義向量序列收斂于向量是21矩陣范數(shù)定義

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

（相容(當(dāng)

m=n

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

對方陣以及有利用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ù)，其特征根和相應(yīng)特征向量仍可能是復(fù)數(shù)。將上述定義中絕對值換成復(fù)數(shù)模均成立。譜半徑定義矩陣A的譜半徑記為(A)=，其中i

為

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

A的特征根成立所以2-范數(shù)亦稱為譜范數(shù)。定理對任意算子范數(shù)||·||有證明：由算子范數(shù)的相容25若矩陣B對某個算子范數(shù)滿足||B||<1，則必有定理①可逆；②證明：①若不然，則有非零解，即存在非零向量使得②若矩陣B對某個算子范數(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的不動點迭代相似……，將等價改寫為形式，建立迭代。從初值出發(fā)，得到序列。研究內(nèi)容：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計？§3.4解線性方程組的迭代法求解思路與解f(x28迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確解的方法。（一般有限步內(nèi)得不到精確解）稀疏性：迭代法則能保持矩陣的稀疏性，具有計算簡單，編制程序容易的優(yōu)點，并在許多情況下收斂較快。故能有效地解一些高階方程組。直接法：比較適用于中小型方程組。對高階方程組，既使系數(shù)矩陣是稀疏的，但在運算中很難保持稀疏性，因而有存儲量大，程序復(fù)雜等不足。與直接解法的比較迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確29思路思路30收斂問題收斂問題31數(shù)值分析_第三章課件32§3.4.1.雅可比(Jacobi)迭代法§3.4.1.雅可比(Jacobi)迭代法33數(shù)值分析_第三章課件34數(shù)值分析_第三章課件35矩陣簡化記法矩陣簡化記法36收斂與解故如果序列收斂,則收斂到解.B稱迭代矩陣.收斂與解故如果序列收斂,則收斂到解.B稱迭代矩陣.37數(shù)值分析_第三章課件38Jacobi迭代法的計算過程如下：Jacobi迭代法的計算過程如下：39§3.4.2高斯—塞德爾迭代法§3.4.2高斯—塞德爾迭代法40數(shù)值分析_第三章課件41數(shù)值分析_第三章課件42數(shù)值分析_第三章課件43數(shù)值分析_第三章課件44比較：比較：45Gauss-Seidel迭代法的計算過程：Gauss-Seidel迭代法的計算過程：46§3.4.3松弛法§3.4.3松弛法47數(shù)值分析_第三章課件48數(shù)值分析_第三章課件49數(shù)值分析_第三章課件50松弛法計算過程如下：松弛法計算過程如下：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誤差估計：誤差估計：68數(shù)值分析_第三章課件69數(shù)值分析_第三章課件70數(shù)值分析_第三章課件71一個例子：§3.7誤差分析一個例子：§3.7誤差分析72問題的提出：問題的提出：73設(shè)有方程組Ax=b,設(shè)右端項b有一擾動將引起方程組解x的擾動設(shè)x是方程組Ax=b的解,則有方程組1.b有擾動，A無擾動設(shè)有方程組Ax=b,設(shè)右端項b有一擾動74化簡,得由Ax=b得所以化簡,得由Ax=b得所以75設(shè)方程組Ax=b,矩陣A有一擾動時,將引起方程組解x的擾動設(shè)x是方程組Ax=b的解,則有方程組2.A有擾動，b無擾動設(shè)方程組Ax=b,矩陣A有一擾動76化簡,得取范數(shù)化簡,得取范數(shù)77當(dāng)A和b均有一擾動時,將引起方程組解x的擾動。設(shè)x是方程組Ax=b的解,則有方程組3.A有擾動，b有擾動當(dāng)A和b均有一擾動時,將引起方程組解x的擾動。設(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ù)很大時,方程組Ax=b是病態(tài)問題;當(dāng)條件數(shù)較小時,方程組Ax=b是良態(tài)問題結(jié)論當(dāng)條件數(shù)很大時,方程組Ax=b是病態(tài)問題;當(dāng)條件數(shù)較小82病態(tài)矩陣的例子：病態(tài)矩陣的例子：83在消元過程中，出現(xiàn)小主元。矩陣行列式的值很小，或有某些行（列）近似線性相關(guān)。矩陣元素間的數(shù)量級相差太大。實際計算中，病態(tài)矩陣的判斷：在消元過程中，出現(xiàn)小主元。實際計算中，病態(tài)矩陣的判斷：84作業(yè)：P.66~70思考題：1，2，4，8習(xí)題：4，6，7實驗題：4作業(yè)：P.66~7085第三章線性方程組求解的數(shù)值方法求解第三章線性方程組求解的數(shù)值方法求解86§3.1消元法思路首先將A化為上三角陣，再回代求解。=§3.1消元法思路首先將A化為上三角陣，=87消元記Step1：設(shè)，計算因子將增廣矩陣第i行mi1

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

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

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

k

then交換第k行與第ik

行;Ifjk

k

then交換第k列與第jk

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

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

A1

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

A

的順序主子陣Ak

亦對稱正定

A

的特征值i

>0

A

的全部順序主子式

det(Ak

)>0Cholesky分解：

——對稱

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

正定陣

A做LU

分解U=uij=u11uij/uii111u22unn記為

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

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

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

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

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

（相容(當(dāng)

m=n

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

對方陣以及有利用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ù)，其特征根和相應(yīng)特征向量仍可能是復(fù)數(shù)。將上述定義中絕對值換成復(fù)數(shù)模均成立。譜半徑定義矩陣A的譜半徑記為(A)=，其中i

為

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

A的特征根成立所以2-范數(shù)亦稱為譜范數(shù)。定理對任意算子范數(shù)||·||有證明：由算子范數(shù)的相容110若矩陣B對某個算子范數(shù)滿足||B||<1，則必有定理①可逆；②證明：①若不然，則有非零解，即存在非零向量使得②若矩陣B對某個算子范數(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的不動點迭代相似……，將等價改寫為形式，建立迭代。從初值出發(fā)，得到序列。研究內(nèi)容：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

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