线性方程组的误差分析

线性方程组的误差分析第一页，共十二页，编辑于2023年，星期三§2ErrorAnalysisfor.

设精确，A有误差，得到的解为，即

Waitaminute…

Whosaidthat(I+A1A)isinvertible?(只要A充分小，使得是关键的误差放大因子，称为A的条件数，记为cond(A),越则A越病态，难得准确解。大第二页，共十二页，编辑于2023年，星期三§2ErrorAnalysisfor.

注:

cond(A)的具体大小与||·||的取法有关，但相对大小一致。

cond(A)取决于A，与解题方法无关。常用条件数有：cond(A)1cond(A)cond(A)2特别地，若A对称，则条件数的性质：

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。第三页，共十二页，编辑于2023年，星期三§2ErrorAnalysisfor.

精确解为例：计算cond(A)2。A1=解：考察A的特征根39206>>1

测试病态程度：给一个扰动，其相对误差为此时精确解为2.0102>200%第四页，共十二页，编辑于2023年，星期三§2ErrorAnalysisfor.

例：Hilbert阵cond(H2)=27cond(H3)748cond(H6)=2.9106cond(Hn)asn注：一般判断矩阵是否病态，并不计算A1，而由经验得出。行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；主元消去过程中出现小主元；特征值相差大数量级。第五页，共十二页，编辑于2023年，星期三§2ErrorAnalysisfor.

近似解的误差估计及改善：设的近似解为，则一般有cond(A)误差上限改善方法：Step1:近似解Step2:Step3:Step4:若可被精确解出，则有就是精确解了。经验表明：若A不是非常病态（例如：），则如此迭代可达到机器精度；但若A病态，则此算法也不能改进。HW:p.66#2,#4,#5第六页，共十二页，编辑于2023年，星期三§3Jacobi法和Gauss-Seidel法

/*Jacobi&Gauss-SeidelIterativeMethods*/JacobiIterativeMethod写成矩阵形式：A=LUDBJacobi迭代阵第七页，共十二页，编辑于2023年，星期三§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的元素不改变，故可以事先调整好A使得aii

0，否则A不可逆。必须等X(k)完全计算好了才能计算X(k+1)，因此需要两组向量存储。Abitwasteful,isn’tit?第八页，共十二页，编辑于2023年，星期三§3Jacobi&Gauss-SeidelIterativeMethodsGauss-SeidelIterativeMethod…………只存一组向量即可。写成矩阵形式：BGauss-Seidel迭代阵第九页，共十二页，编辑于2023年，星期三Amathematicianabouthiscolleague:"Hemadealotofmistakes,buthemadetheminagooddirection.Itriedtocopythis,butIfoundoutthatitisverydifficulttomakegoodmistakes."§3Jacobi&Gauss-SeidelIterativeMethods注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。p.76#2给出了例子。收敛性分析将在下节课讨论。第十页，共十二页，编辑于2023年，星期三§3Jacobi&Gauss-SeidelIterativeMethodsLab07.Gauss-SeidelMethod UsetheGauss-Seidelmethodtosolveagivenn×nlinearsystemwithaninitialapproximationandagiventoleranceTOL.Input Thereareseveralsetsofinputs.Foreachset: The1stlinecontainsaninteger100

n

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

0whichisthemaximumnumberofiteration.第十一页，共十二页，编辑于2023年，星期三§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.