線性方程組的誤差分析

線性方程組的誤差分析第1頁，課件共12頁，創(chuàng)作于2023年2月§2ErrorAnalysisfor.

設精確，A有誤差，得到的解為，即

Waitaminute…

Whosaidthat(I+A1A)isinvertible?(只要A充分小，使得是關鍵的誤差放大因子，稱為A的條件數(shù)，記為cond(A),越則A越病態(tài)，難得準確解。大第2頁，課件共12頁，創(chuàng)作于2023年2月§2ErrorAnalysisfor.

注:

cond(A)的具體大小與||·||的取法有關，但相對大小一致。

cond(A)取決于A，與解題方法無關。常用條件數(shù)有：cond(A)1cond(A)cond(A)2特別地，若A對稱，則條件數(shù)的性質(zhì)：

A可逆，則cond(A)p

1；

A可逆，R

則cond(

A)

=cond(A)；

A正交，則cond(A)2=1；

A可逆，R正交，則cond(RA)2

=cond(AR)2

=cond(A)2。第3頁，課件共12頁，創(chuàng)作于2023年2月§2ErrorAnalysisfor.

精確解為例：計算cond(A)2。A1=解：考察A的特征根39206>>1

測試病態(tài)程度：給一個擾動，其相對誤差為此時精確解為2.0102>200%第4頁，課件共12頁，創(chuàng)作于2023年2月§2ErrorAnalysisfor.

例：Hilbert陣cond(H2)=27cond(H3)748cond(H6)=2.9106cond(Hn)asn注：一般判斷矩陣是否病態(tài)，并不計算A1，而由經(jīng)驗得出。行列式很大或很小（如某些行、列近似相關）；元素間相差大數(shù)量級，且無規(guī)則；主元消去過程中出現(xiàn)小主元；特征值相差大數(shù)量級。第5頁，課件共12頁，創(chuàng)作于2023年2月§2ErrorAnalysisfor.

近似解的誤差估計及改善：設的近似解為，則一般有cond(A)誤差上限改善方法：Step1:近似解Step2:Step3:Step4:若可被精確解出，則有就是精確解了。經(jīng)驗表明：若A不是非常病態(tài)（例如：），則如此迭代可達到機器精度；但若A病態(tài)，則此算法也不能改進。HW:p.66#2,#4,#5第6頁，課件共12頁，創(chuàng)作于2023年2月§3Jacobi法和Gauss-Seidel法

/*Jacobi&Gauss-SeidelIterativeMethods*/JacobiIterativeMethod寫成矩陣形式：A=LUDBJacobi迭代陣第7頁，課件共12頁，創(chuàng)作于2023年2月§3Jacobi&Gauss-SeidelIterativeMethodsAlgorithm:JacobiIterativeMethodSolvegivenaninitialapproximation.Input:thenumberofequationsandunknownsn;thematrixentriesa[][];theentriesb[];theinitialapproximationX0[];toleranceTOL;maximumnumberofiterationsNmax.Output:approximatesolutionX[]oramessageoffailure.Step1Setk=1;Step2While(kNmax)dosteps3-6

Step3Fori=1,…,n

Set;/*computexk*/

Step4IfthenOutput(X[]);STOP;/*successful*/

Step5Fori=1,…,nSetX0[]=X[];/*updateX0*/

Step6Setk++;Step7Output(Maximumnumberofiterationsexceeded);STOP./*unsuccessful*/Whatifaii

=0?迭代過程中，A的元素不改變，故可以事先調(diào)整好A使得aii

0，否則A不可逆。必須等X(k)完全計算好了才能計算X(k+1)，因此需要兩組向量存儲。Abitwasteful,isn’tit?第8頁，課件共12頁，創(chuàng)作于2023年2月§3Jacobi&Gauss-SeidelIterativeMethodsGauss-SeidelIterativeMethod…………只存一組向量即可。寫成矩陣形式：BGauss-Seidel迭代陣第9頁，課件共12頁，創(chuàng)作于2023年2月Amathematicianabouthiscolleague:"Hemadealotofmistakes,buthemadetheminagooddirection.Itriedtocopythis,butIfoundoutthatitisverydifficulttomakegoodmistakes."§3Jacobi&Gauss-SeidelIterativeMethods注：二種方法都存在收斂性問題。有例子表明：Gauss-Seidel法收斂時，Jacobi法可能不收斂；而Jacobi法收斂時，Gauss-Seidel法也可能不收斂。p.76#2給出了例子。收斂性分析將在下節(jié)課討論。第10頁，課件共12頁，創(chuàng)作于2023年2月§3Jacobi&Gauss-SeidelIterativeMethodsLab07.Gauss-SeidelMethod UsetheGauss-Seidelmethodtosolveagivenn×nlinearsystemwithaninitialapproximationandagiventoleranceTOL.Input Thereareseveralsetsofinputs.Foreachset: The1stlinecontainsaninteger100

n

0whichisthesizeofamatrix.n=1signalstheendoffile. Thefollowingnlinescontaintheaugmentedmatrixinthefollowingformat:Thenumbersareseparatedbyspacesandnewlines.ThelastlineofeachtestcasecontainsarealnumberTOL,whichisthetolerancefor||·||norm,andanintegerN

0whichisthemaximumnumberofiteration.第11頁，課件共12頁，創(chuàng)作于2023年2月§3Jacobi&Gauss-SeidelIterativeMethodsOutput/*representsaspace*/

EachentryofthesolutionistobeprintedasintheCfprintf:fprintf(outfile,"%12.8f\n",x);

Ifthematrixhasazerocolumn,printthemessage“Matrixhasazerocolumn.Nouniquesolutionexists.\n”.

IfthemethodfailstogiveasolutionafterNiterations,printthemessage“Maximumnumberofiterationsexceeded.\n”.

Ifthereisanentryofthatisoutoftherange,printthemessage“Noconvergence.\n”.Theoutputsoftwotestcasesmustbeseperatedbyablankline.SampleInput

(representsaspace)310–109–110–270–41060