1、Ch3 線性方程組求解的數(shù)值方法,Numerical Solutions of Systems of Linear Equations,3.0 Introduction,線性方程組,工程問題（電子網(wǎng)絡(luò)，船體放樣等）,自然科學(xué)（實(shí)驗(yàn)數(shù)據(jù)的最小二乘法曲線擬合）,解非線性方程組,解常/偏微分方程組（差分法，有限元法）,3.0 Introduction,線性方程組的系數(shù)矩陣：,（1）低價(jià)稠密矩陣（階數(shù)150）；,（2）大型稀疏矩陣（階數(shù)高且零元素較多）。,求解線性方程組的方法：,（1）直接法: 經(jīng)過有限步算術(shù)運(yùn)算，求得精確解（假設(shè)計(jì)算過程沒有舍入誤差）。 如Gauss消去法，三角分解法。,（2）間接法

2、(迭代法)： 通過迭代序列，逐步逼近方程組的解。如Jacobi迭代法，Gauss-Seidel迭代法。,3.0 Introduction,【最簡(jiǎn)單的情形】三角形線性方程組：,簡(jiǎn)記為,，A為上三角矩陣。,若所有aii0，可用“回代”過程得到方程組的解。,function X=backsub(U,b) % 解上三角方程組-回代過程%Backsubstitution in Gauss elimination % Input-U is a n x n upper-trianglular matrix % -b is a n x 1 constant vctor % Output-X is the so

3、lution vector of UX=b % Usage: X=backsub(U,b) %Find the dimension of b and initialize X n=length(b); X=zeros(n,1); X(n)=b(n)/U(n,n); for p=n-1:-1:1 X(p)=(b(p)-U(p,p+1:n)*X(p+1:n)/U(p,p); end,Backsub.m,3.0 Introduction,3.0 Introduction,【作業(yè)】（1）編寫Matlab程序解下列上三角形方程組：,（2）編寫Matlab程序解下列下三角形方程組：,3.1 Gauss消去

4、法與LU分解法,直接法的基本思想：,將線性方程組化成與之等價(jià)的上三角形或下三角形，再用回代法求解。它的核心是矩陣分解。,核心：矩陣分解。,Gauss消去法（Gaussian elimination）：,（對(duì)方程組的三種變換）,（1）交換兩個(gè)方程的次序；,（2）用一個(gè)非零常數(shù)乘一個(gè)方程；,（3）將一個(gè)方程的非零倍數(shù)加到另一個(gè)方程上去。,這等價(jià)與對(duì)增廣矩陣進(jìn)行三種行初等變換，將它化為行階梯形。,【例3.1】解下列線性方程組：,解：用行初等變換將方程組的增廣矩陣化為行階梯形：,解得 x=(0, -1, 1).,3.1 Gaussian Elimination and LU Decomposition

5、,【注】上述過程可用矩陣表示為：,LU=PA,其中,3.1 Gaussian Elimination and LU Decomposition,【高斯消元法思路】,(1) 用消元法將A化為上三角陣 upper-triangular matrix ;,(2) 回代求解 backward substitution 。,3.1 Gaussian Elimination and LU Decomposition,3.1 Gaussian Elimination and LU Decomposition,消元,記,其中,Step k：設(shè) ，計(jì)算因子 且計(jì)算,共進(jìn)行 ？ 步,n 1,回代,No uniqu

6、e solution exists.,What if we cant find such k ?,No unique solution exists.,定理,若A的所有順序主子式 /* determinant of leading principal submatrices */ 均不為0，則高斯消元無需換行即可進(jìn)行到底，得到唯一解。,注：事實(shí)上，只要 A 非奇異，即 A1 存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解。,3.1 Gaussian Elimination and LU Decomposition,高斯消元法的矩陣表達(dá)-矩陣分解,課本P40-42,3.1

7、Gaussian Elimination and LU Decomposition,3.1.2 矩陣的LU分解（LU Decomposition）,若在Gauss消去法過程中，沒有進(jìn)行交換行的變換，即P=I, 則分解結(jié)果為,3.1 Gaussian Elimination and LU Decomposition,這樣的分解式稱為矩陣的LU分解。,【Matlab】, L,U,P=lu(A),其中,【作業(yè)】P.67 題1, 2,3.1.3 選主元消去法 /* Pivoting Strategies */,例：?jiǎn)尉冉夥匠探M,用Gaussian Elimination計(jì)算：,8個(gè),小主元 /* S

8、mall pivot element */ 可能導(dǎo)致計(jì)算失敗。,3.1 Gaussian Elimination and LU Decomposition, 全主元消去法 /* Complete Pivoting */,每一步選絕對(duì)值最大的元素為主元素，保證 。,Step k: 選取, If ik k then 交換第 k 行與第 ik 行; If jk k then 交換第 k 列與第 jk 列;, 消元,注：列交換改變了 xi 的順序，須記錄交換次序，解完后再換回來。, 列主元消去法 /* Partial Pivoting, or maximal column pivoting */,省去

9、換列的步驟，每次僅選一列中最大的元。,3.1 Gaussian Elimination and LU Decomposition,例：,注：列主元法沒有全主元法穩(wěn)定。,例：, 標(biāo)度化列主元消去法 /* Scaled Partial Pivoting */,對(duì)每一行計(jì)算 。為省時(shí)間，si 只在初始時(shí)計(jì)算一次。以后每一步考慮子列 中 最大的 aik 為主元。,注：穩(wěn)定性介于列主元法和全主元法之間。,3.1 Gaussian Elimination and LU Decomposition,實(shí)際應(yīng)用中直接調(diào)用Gauss Elimination 解3階線性方程組的結(jié)果：,結(jié)合全主元消去后的結(jié)果：,3.

10、1 Gaussian Elimination and LU Decomposition,3.2 Cholesky分解,【Matlab】,設(shè)A是對(duì)稱正定矩陣，則A有以下形式的LU分解：,A=PTP （3.2.1）,其中P是一個(gè)上三角矩陣, 上式稱為A的Cholesky分解(Choleskian decomposition)., P=chol(A),定理,【作業(yè)】P.68 題4,3.3 向量范數(shù)與矩陣范數(shù), 誤差的度量,3.3.1 向量范數(shù) (vector norms),常用向量范數(shù)：,這些范數(shù)滿足：,一般范數(shù)：,如，設(shè)向量 x=(2, -4, -1)T, 則,3.3 向量范數(shù)與矩陣范數(shù),【Mat

11、lab】,x=(1:4)/5 N1=norm(x,1) N2=norm(x) N7=norm(x,7) Ninf=norm(x,inf),x = 0.2000 0.4000 0.6000 0.8000 N1 = 2 N2 = 1.0954 N7 = 0.8153 Ninf = 0.8000,定義 矩陣A的范數(shù)定義為,3.3 向量范數(shù)與矩陣范數(shù),3.3.2 矩陣范數(shù) (matrix norms),命題：矩陣的常用范數(shù)：,其中，1, n是,的特征值，,稱為 的譜半徑。,例 設(shè)矩陣,3.3 向量范數(shù)與矩陣范數(shù),則,可以證明，矩陣范數(shù)滿足：,3.4 經(jīng)典迭代法,Jacobi迭代法與Gauss-Seid

12、el迭代法,3.4.1Jacobi迭代法,設(shè)有n階方程組,(3.4.1),若系數(shù)矩陣非奇異，且 (i = 1, 2, n)，將方程組,（4.1）改寫成,3.4 經(jīng)典迭代法,然后寫成迭代格式,（3.4.2）,（3.4.2）式也可以簡(jiǎn)單地寫為,（3.4.3）,3.4 經(jīng)典迭代法,寫成矩陣形式：,L,U,D,Jacobi 迭代陣,3.4 經(jīng)典迭代法, ,只存一組向量即可。,寫成矩陣形式：,Gauss-Seidel 迭代陣,3.4.2 Gauss-Seidel迭代法,(3.4.7),3.4 經(jīng)典迭代法,定理3.1 對(duì)任意初始向量X(0)及常向量F，迭代格式(3.5.1),(3.5.1),推論：若迭代矩

13、陣的某種范數(shù) ，則（3.5.1）,收斂的充分必要條件是迭代矩陣B的譜半徑(B) 1。,確定的迭代法對(duì)任意初值X(0)均收斂于方程組,X = BX + F,3.5 迭代法的分析,迭代法的收斂性、收斂速度與數(shù)值穩(wěn)定性,3.5.1 收斂性,的唯一解x*。,定義1：如果矩陣的每一行中，不在主對(duì)角線上的所有元素絕對(duì)值之和小于主對(duì)角線上元素的絕對(duì)值，即,則稱矩陣A (按行) 嚴(yán)格對(duì)角占優(yōu)。,定理3.2：若A是嚴(yán)格對(duì)角占優(yōu)，則A是非奇異的。,3.5 迭代法的分析,定理3：若線性方程組AX = b的系數(shù)矩陣A按行嚴(yán)格對(duì)角占優(yōu)，則Jacobi迭代法和Gauss-Seidel迭代法對(duì)任意給定初值均收斂。,3.5.

14、2 迭代法的誤差估計(jì)與收斂速度,定理3.4 設(shè)X*是方程組AX = b的同解方程X = BX + F的準(zhǔn)確解，若迭代公式中迭代矩陣B的某種范數(shù)，,(1),(2),則有,3.5 迭代法的分析,迭代,加速,（3.6.2）,3.6 超松馳法(SOR)及分塊迭代法,定理3. SOR方法收斂的必要條件是,其中稱為松弛因子,（3.6.1）,3.7 條件數(shù)、病態(tài)方程組與算法的穩(wěn)定性,3.7.1 病態(tài)方程組與數(shù)值穩(wěn)定的算法,定義 對(duì)線性方程組Ax=b, 如果解x關(guān)于問題（矩陣A和b）的“微小”變化（即舍入誤差）不敏感，則稱此方程組是“好的”，或稱為“良態(tài)的”，否則，稱之為“壞的”，或稱為“病態(tài)的”。,定義 對(duì)

15、求解線性方程組Ax=b的一個(gè)(迭代)算法 ，如果關(guān)于初始值的誤差，不隨計(jì)算逐步放大，則稱算法是數(shù)值穩(wěn)定的，否則，稱之為是數(shù)值不穩(wěn)定的。,數(shù)值不穩(wěn)定的算法是不可用的！,例 （病態(tài)方程組）考慮線性方程組,3.7條件數(shù)、病態(tài)方程組與算法的穩(wěn)定性,已知其精確解是 u =(1,1,1,1)T.,(1)對(duì)右邊常數(shù)向量b作“微小”擾動(dòng)，得方程,(2)對(duì)系數(shù)矩陣A作“微小”擾動(dòng)，得方程組,它的解是 v = (9.2, -12.6, 4.5, -1.1)T.,它的解是 w = (-81, 137, -34, 22)T.,注意：上述兩種情況的解都是精確解！,一般地，對(duì)線性方程組 Au=b （1）,兩方程相減得,于

16、是,(2),由此得到,設(shè)其解為v=u+u,即設(shè),(1) 考慮對(duì)此線性方程組的第一類擾動(dòng)方程組,（2）式右端給出了解的相對(duì)誤差界。,3.7條件數(shù)、病態(tài)方程組與算法的穩(wěn)定性,兩方程相減得,于是,(3),由此得到,設(shè)其解為v=u+u,即設(shè),(2) 考慮對(duì)線性方程組（1）的第二類擾動(dòng)方程組,（4）式右端給出了解的相對(duì)誤差界。,進(jìn)一步得到,(4),3.7條件數(shù)、病態(tài)方程組與算法的穩(wěn)定性,3.7.2 條件數(shù)與方程組病態(tài)性,定義 設(shè)A 是一個(gè)非奇異矩陣，|.|是與某種向量范數(shù)相容的矩陣范數(shù)，正數(shù) cond(A):=|A-1| |A| 稱為矩陣A的 條件數(shù)（conditional number）。,Remar

17、k: 由上面分析可知，系數(shù)矩陣的條件數(shù)很大(1)（此時(shí)矩陣也稱為“病態(tài)矩陣”）的線性方程組Ax=b是病態(tài)的；反之，系數(shù)矩陣的條件數(shù)很小的線性方程組Ax=b是良態(tài)的。, A=hilb(n); c=cond(A),Example: 著名的Hilbert 矩陣是病態(tài)的。,【Matlab】,3.7條件數(shù)、病態(tài)方程組與算法的穩(wěn)定性,定理3.6 (條件數(shù)的性質(zhì)) 設(shè)A 是一個(gè)非奇異矩陣. (1) cond(A)1, cond(A)=cond(A-1), con(aA)=cond(A), a 0. (2) 如果 Q是正交矩陣，則 cond2(Q)=1, cond2(A)= cond2(QA)= cond2(AQ), 其中cond2(A)=|A-1|2 |A|2.,3.7條件數(shù)、病態(tài)方程組與算法的穩(wěn)定性,3.8 稀疏矩