第四章解线性方程组的迭代法2.ppt
2线性方程组的误差分析线性方程组的误差分析/*Error Analysis for Linear system of Equations*/求解求解时，时，A和和的误差对解的误差对解有何影响？有何影响？设设A精确，精确，有误差有误差，得到的解为，得到的解为，即，即绝对误差放大因子绝对误差放大因子又又相对误差放大因子相对误差放大因子2ErrorAnalysisfor.设设精确，精确，A有误差有误差，得到的解为，得到的解为，即，即 Wait a minute Who said that(I+A 1 A)is invertible?(只要只要 A充分小，使得充分小，使得是关键是关键的误差放大因子，称为的误差放大因子，称为A的的条件数条件数，记为，记为cond(A),越越则则A 越病态，越病态，难得准确解。难得准确解。大大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。2ErrorAnalysisfor.精确解精确解为为例：例：计算计算cond(A)2。A 1=解：解：考察考察A的特征根的特征根392061测试病态程度：测试病态程度：给一个扰动给一个扰动，其相对误差为，其相对误差为此时此时精确解精确解为为2.0102200%2ErrorAnalysisfor.例：例：Hilbert阵阵cond(H2)=27cond(H3)748cond(H6)=2.9 106cond(Hn)asn 注：注：一般判断矩阵是否病态，并不计算一般判断矩阵是否病态，并不计算A 1，而由经验而由经验得出。得出。行列式很大或很小（如某些行、列近似相关）；行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；元素间相差大数量级，且无规则；主元消去过程中出现小主元；主元消去过程中出现小主元；特征值相差大数量级。特征值相差大数量级。2ErrorAnalysisfor.近似解的误差估计及改善：近似解的误差估计及改善：设设的近似解为的近似解为，则一般有，则一般有cond(A)误差上限误差上限改善方法：改善方法：Step 1:近似解近似解Step 2:Step 3:Step 4:若若可被精确解出，则有可被精确解出，则有就是精确解了。就是精确解了。经验表明经验表明：若：若A 不是非常病态（例如：不是非常病态（例如：），则如），则如此迭代可达到机器精度；但若此迭代可达到机器精度；但若A 病态，则此算法也不能改病态，则此算法也不能改进。进。HW:p.66#2,#4,#53Jacobi法和法和Gauss-Seidel法法/*Jacobi&Gauss-Seidel Iterative Methods*/JacobiIterativeMethod写成写成矩阵形式矩阵形式：A=LUDBJacobi迭代阵迭代阵3Jacobi&Gauss-SeidelIterativeMethods Algorithm:Jacobi Iterative MethodSolvegivenaninitialapproximation.Input:thenumberofequationsandunknownsn;thematrixentriesa;theentriesb;theinitialapproximationX0;toleranceTOL;maximumnumberofiterationsNmax.Output:approximatesolutionXoramessageoffailure.Step 1Setk=1;Step 2While(k Nmax)dosteps3-6Step 3Fori=1,nSet;/*computexk*/Step 4IfthenOutput(X);STOP;/*successful*/Step 5Fori=1,nSetX0=X;/*updateX0*/Step 6Setk+;Step 7Output(Maximumnumberofiterationsexceeded);STOP./*unsuccessful*/Whatifaii=0?迭代过程中，迭代过程中，A的元素的元素不改变，故可以不改变，故可以事先调整事先调整好好A使得使得aii 0，否则否则A不可逆不可逆。必须等必须等X(k)完全计算完全计算好了才能计算好了才能计算X(k+1)，因此因此需要需要两组向量两组向量存储。存储。A bit wasteful,isnt it?3Jacobi&Gauss-SeidelIterativeMethods Gauss-SeidelIterativeMethod只存一组向量即可。只存一组向量即可。写成写成矩阵形式矩阵形式：BGauss-Seidel迭代阵迭代阵A mathematician about his colleague:Hemadealotofmistakes,buthemadetheminagooddirection.Itriedtocopythis,butIfoundoutthatitisverydifficulttomakegoodmistakes.3Jacobi&Gauss-SeidelIterativeMethods注：注：注：注：二种方法都存在二种方法都存在收敛性问题收敛性问题。有例子表明：有例子表明：Gauss-Seidel法收敛时，法收敛时，Jacobi法可能法可能不收敛；而不收敛；而Jacobi法收敛时，法收敛时，Gauss-Seidel法也可能法也可能不收敛。不收敛。p.76#2给出了例子。给出了例子。收敛性分析将在下节课讨论。收敛性分析将在下节课讨论。3Jacobi&Gauss-SeidelIterativeMethodsLab07.Gauss-SeidelMethodUsetheGauss-SeidelmethodtosolveagivennnlinearsystemwithaninitialapproximationandagiventoleranceTOL.InputThereareseveralsetsofinputs.Foreachset:The1stlinecontainsaninteger100 n 0whichisthesizeofamatrix.n=1signalstheendoffile.Thefollowingnlinescontaintheaugmentedmatrixinthefollowingformat:Thenumbersareseparatedbyspacesandnewlines.ThelastlineofeachtestcasecontainsarealnumberTOL,whichis the tolerance for|norm,and an integer N 0 which is themaximumnumberofiteration.3Jacobi&Gauss-SeidelIterativeMethodsOutput /*represents a space*/EachentryofthesolutionistobeprintedasintheCfprintf:fprintf(outfile,%12.8fn,x);Ifthematrixhasazerocolumn,printthemessage“Matrixhasazerocolumn.Nouniquesolutionexists.n”.If the method fails to give a solution after N iterations,print the message“Maximumnumberofiterationsexceeded.n”.Ifthereisanentryofthatisoutoftherange,printthemessage“Noconvergence.n”.Theoutputsoftwotestcasesmustbeseperatedbyablankline.Sample InputSample Input (represents a space)represents a space)31010911027041060.000000001100033101360033040.00000000110001Sample OutputSample Output (represents a space)represents a space)1.000000001.000000001.00000000Matrixhasazerocolumn.Nouniquesolutionexists.
