病態(tài)線性方程組

1、數(shù)值分析數(shù)值分析朱立永朱立永北京航空航天大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院Email: numerical_Password:beihang答疑時(shí)間：星期三下午2:005:00答疑地點(diǎn)：主216數(shù)值分析數(shù)值分析第四講病態(tài)線性方程組求解第二章 線性方程組的解法數(shù)值分析數(shù)值分析In Scientific ComputingLarge Linear SystemsAx=bas sub-problems/as intermediate stepsGauss-Seidel methodJacobi methodSOR methodConjugate Gradient methodfor symmetric sys

2、temsGaussian eliminationLU factorizationCholesky factorizationGMRESGCRBi-CGCGSBi-CGSTABBi-CGSTAB2GPBi-CGBi-CGSTAB(L)數(shù)值分析數(shù)值分析perturbation1122238123.000 018.000 022xxxx 11222388.522.999998.000033xxxxperturbationIts funny that such small perturbations in the coefficients lead to so big change in the so

3、lution!數(shù)值算例數(shù)值算例數(shù)值分析數(shù)值分析由實(shí)際問(wèn)題建立起來(lái)的線性方程組Ax=b本身存在模型誤差和觀測(cè)誤差，或者是由計(jì)算得到的，存在舍入誤差等?？傊珹,b都會(huì)有一定擾動(dòng)A, b, 因此實(shí)際處理的是A+ A或b+ b ，我們需要分析A或b的擾動(dòng)對(duì)解的影響。數(shù)值分析數(shù)值分析bbxxA)(bAx1|1bAx|1bbAAxxbAx 數(shù)值分析數(shù)值分析bxxAA)(|1|11AAAAAAAAxx數(shù)值分析數(shù)值分析bbxxAA)()|(|1|11AAbbAAAAAAxx解的相對(duì)誤差A(yù)的相對(duì)誤差b的相對(duì)誤差當(dāng)方程組的系數(shù)矩陣A或右端項(xiàng)b受到擾動(dòng)A, b時(shí)，引起的解的相對(duì)誤差完全由AA-1來(lái)決定，它刻畫(huà)了方

4、程組的解對(duì)原始數(shù)據(jù)的敏感程度。數(shù)值分析數(shù)值分析：對(duì)非奇異矩陣：對(duì)非奇異矩陣A，稱乘積，稱乘積|A| |A-1|為矩陣為矩陣A的條件數(shù)，的條件數(shù)，記為記為 cond（A） |A| |A-1|數(shù)值分析數(shù)值分析|)(1AAAcond1111|)(AAAcond2122|)(AAAcond數(shù)值分析數(shù)值分析例：例：Hilbert 陣陣1211111131211211nnnnnnHcond (H2) = 27cond (H3) 748cond (H6) = 2.9 106注：注：現(xiàn)在用現(xiàn)在用MatlabMatlab數(shù)學(xué)軟件可以很方便數(shù)學(xué)軟件可以很方便求矩陣的條件數(shù)求矩陣的條件數(shù)! !數(shù)值分析數(shù)值分析數(shù)值分

5、析數(shù)值分析：對(duì)線性方程組：對(duì)線性方程組Axb，若，若cond(A)相對(duì)很大，則稱相對(duì)很大，則稱Axb是病態(tài)的線性方程組；若是病態(tài)的線性方程組；若cond(A)相對(duì)很小，則稱相對(duì)很小，則稱Axb是良態(tài)的線性方程組。是良態(tài)的線性方程組。一個(gè)病態(tài)線性方程組的例子（見(jiàn)書(shū)上）一個(gè)病態(tài)線性方程組的例子（見(jiàn)書(shū)上）對(duì)于嚴(yán)重的病態(tài)線性方程組，即使原始數(shù)據(jù)對(duì)于嚴(yán)重的病態(tài)線性方程組，即使原始數(shù)據(jù)A和和b都沒(méi)有都沒(méi)有誤差，但如果在求解過(guò)程中有舍入誤差，所得到的解也誤差，但如果在求解過(guò)程中有舍入誤差，所得到的解也會(huì)有很大的相對(duì)誤差。會(huì)有很大的相對(duì)誤差。數(shù)值分析數(shù)值分析注：注：一般判斷矩陣是否病態(tài)，并不計(jì)算一般判斷矩陣是

6、否病態(tài)，并不計(jì)算A 1，而由經(jīng)驗(yàn)得出。，而由經(jīng)驗(yàn)得出。 行列式很大或很?。ㄈ缒承┬?、列行列式很大或很小（如某些行、列近似相關(guān)）；近似相關(guān)）； 元素間相差大數(shù)量級(jí)，且無(wú)規(guī)則；元素間相差大數(shù)量級(jí)，且無(wú)規(guī)則； 主元消去過(guò)程中出現(xiàn)小主元；主元消去過(guò)程中出現(xiàn)小主元； 特征值相差大數(shù)量級(jí)。特征值相差大數(shù)量級(jí)。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1. 求解求解Axb，得到，得到x的近似解的近似解x1；2. 校正校正x1，令，令r1bAx1，解，解A x1 r1；3. x2x1 x1 ；4. 令令r2bAx2，解，解A x2 r2；5. x3x2 x2 ；6. 。7. 令令rkbAxk，解，解A xk rk；8. Xk1xk xk ；。；。數(shù)值分析數(shù)值分析預(yù)條件技術(shù) 80年代提出，純代數(shù)觀點(diǎn) M 近似 A, 求解(左預(yù)條件) M y = c 易解 相當(dāng)于化學(xué)反應(yīng)中尋找高效、廉價(jià)的催化劑高效、廉價(jià)的催化劑，能極大地提高迭代方法的速度。11M AxM b1()( )MAA數(shù)值分析數(shù)值分析預(yù)條件技術(shù)(續(xù)) 代數(shù)預(yù)條件技術(shù)代數(shù)預(yù)條件技術(shù) ILU、SPAI、SOR、多項(xiàng)式 幾何預(yù)條件技術(shù)幾何預(yù)條件技術(shù) 某方向壓縮粗化、網(wǎng)格均勻化、區(qū)域規(guī)則化近似 分析預(yù)條件技術(shù)分析預(yù)條件技術(shù)變系數(shù)常數(shù)化、Green函數(shù)稀疏近似、強(qiáng)化橢圓型 物