數(shù)值分析 -lec5--病態(tài)線性方程組的解法

《數(shù)值分析 -lec5--病態(tài)線性方程組的解法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、朱立永北京航空航天大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院數(shù)值分析Email:numerical_analysis@buaa.edu.cnPassword:beihang答疑時(shí)間：星期四下午2:30－5:30答疑地點(diǎn)：主216第四講病態(tài)線性方程組求解第二章線性方程組的解法InScientificComputing↓LargeLinearSystemsAx=bassub-problems/asintermediatestepsGauss-SeidelmethodJacobimethodSORmethodConjugateGradientmethodforsy

2、mmetricsystemsGaussianeliminationLUfactorizationCholeskyfactorizationGMRESGCRBi-CGCGSBi-CGSTABBi-CGSTAB2GPBi-CGBi-CGSTAB(L)perturbationperturbationIt’sfunnythatsuchsmallperturbationsinthecoefficientsleadtosobigchangeinthesolution!數(shù)值算例提問(wèn)：求解Ax＝b時(shí)，A和b的誤差對(duì)x有何影響？由實(shí)際問(wèn)題建立起來(lái)的線性方程

3、組Ax=b本身存在模型誤差和觀測(cè)誤差，或者是由計(jì)算得到的，存在舍入誤差等?？傊珹,b都會(huì)有一定擾動(dòng)ΔA,Δb,因此實(shí)際處理的是A+ΔA或b+Δb，我們需要分析A或b的擾動(dòng)對(duì)解的影響。矩陣的條件數(shù)與病態(tài)線性方程組提問(wèn)：求解Ax＝b時(shí)，A和b的誤差對(duì)x有何影響？1：A非奇異，設(shè)精確，b有誤差Δb，導(dǎo)致解x有多大誤差？2：設(shè)b精確，A有誤差ΔA，導(dǎo)致解x有多大誤差？設(shè)A非奇異，

4、

5、ΔA

6、

7、

8、

9、A-1

10、

11、<13：設(shè)b，A分別有誤差Δb和ΔA，導(dǎo)致解x有多大誤差？設(shè)A非奇異，

12、

13、ΔA

14、

15、

16、

17、A-1

18、

19、<1解的相對(duì)誤差A(yù)的相對(duì)誤差b的相對(duì)誤差當(dāng)方程

20、組的系數(shù)矩陣A或右端項(xiàng)b受到擾動(dòng)ΔA,Δb時(shí)，引起的解的相對(duì)誤差完全由??A??·??A-1??來(lái)決定，它刻畫了方程組的解對(duì)原始數(shù)據(jù)的敏感程度。矩陣的條件數(shù)（Conditionnumber）定義：對(duì)非奇異矩陣A，稱乘積

21、

22、A

23、

24、

25、

26、A-1

27、

28、為矩陣A的條件數(shù)，記為cond（A）＝

29、

30、A

31、

32、

33、

34、A^-1

35、

36、

37、

38、A

39、

40、

41、

42、A^-1

43、

44、是我們遇到的第二個(gè)放大因子；cond（A）的具體大小與

45、

46、?

47、

48、有關(guān)，但相對(duì)大小一致；cond（A）的大小本質(zhì)取決于A，與解題的方法無(wú)關(guān)；cond（A）＝∞，如果A是奇異的。常用的矩陣條件數(shù)例：Hilbert陣c

49、ond(H2)?=27cond(H3)??748cond(H6)?=2.9?106注：現(xiàn)在用Matlab數(shù)學(xué)軟件可以很方便求矩陣的條件數(shù)!矩陣條件數(shù)的一些性質(zhì)cond（A）≥1；A非奇異，k≠0，則cond（kA）＝cond（A）；A非奇異對(duì)稱矩陣，則cond（A）2＝

50、λ1/λn

51、；A是正交矩陣，則cond（A）2＝1；A可逆，R正交，則cond(RA)2＝cond(AR)2＝cond(A)2病態(tài)、良態(tài)線性方程組定義：對(duì)線性方程組Ax＝b，若cond(A)相對(duì)很大，則稱Ax＝b是病態(tài)的線性方程組；若cond(A)相對(duì)很小，則稱Ax＝b是

52、良態(tài)的線性方程組。一個(gè)病態(tài)線性方程組的例子（見(jiàn)書(shū)上P31例5）對(duì)于嚴(yán)重的病態(tài)線性方程組，即使原始數(shù)據(jù)A和b都沒(méi)有誤差，但如果在求解過(guò)程中有舍入誤差，所得到的解也會(huì)有很大的相對(duì)誤差。什么樣的線性方程組可能是病態(tài)的？注：一般判斷矩陣是否病態(tài)，并不計(jì)算A?1，而由經(jīng)驗(yàn)得出。?行列式很大或很?。ㄈ缒承┬?、列近似相關(guān)）；?元素間相差大數(shù)量級(jí)，且無(wú)規(guī)則；?主元消去過(guò)程中出現(xiàn)小主元；?特征值相差大數(shù)量級(jí)。緩和甚至解決線性方程組病態(tài)的手段采用高精度的算法（不是總有效）；通過(guò)行或列的平衡來(lái)降低矩陣的條件數(shù)（平衡法）；殘差校正法；通過(guò)矩陣的預(yù)條件處理來(lái)降低矩

53、陣的條件數(shù)。殘差校正法步驟：求解Ax＝b，得到x的近似解x1；校正x1，令r1＝b－Ax1，解AΔx1＝r1；x2＝x1＋Δx1；令r2＝b－Ax2，解AΔx2＝r2；x3＝x2＋Δx2；。。。令rk＝b－Axk，解AΔxk＝rk；Xk＋1＝xk＋Δxk；。。。預(yù)條件技術(shù)80年代提出，純代數(shù)觀點(diǎn)M近似A,求解(左預(yù)條件)My=c易解相當(dāng)于化學(xué)反應(yīng)中尋找高效、廉價(jià)的催化劑，能極大地提高迭代方法的速度。預(yù)條件技術(shù)(續(xù))代數(shù)預(yù)條件技術(shù)ILU、SPAI、SOR、多項(xiàng)式幾何預(yù)條件技術(shù)某方向壓縮粗化、網(wǎng)格均勻化、區(qū)域規(guī)則化近似分析預(yù)條件技術(shù)變系數(shù)常數(shù)

54、化、Green函數(shù)稀疏近似、強(qiáng)化橢圓型物理預(yù)條件量綱平衡、物理參數(shù)逼近、狀態(tài)方程近似、某些物理項(xiàng)簡(jiǎn)化、算子分裂高級(jí)預(yù)條件MG、DDM、快速變換（FFT）、基底變換法作業(yè)教材第46頁(yè)習(xí)題11、1