计算方法期末复习

12014《计算方法》复习复习的目的是深入的理解和掌握，并进一步提高。希望大家在不上课的这段时间对前面讲过的章节进行回顾，总结和思考！如果同学们对某个问题感兴趣，建议你利用空闲时间进行研究并写成小论文。最后祝同学们学习进步！“五一”愉快！6月10号（7，8节上课）我们再会。第一章绪论一、了解绝对误差（限）、相对误差（限）、有效数字的概念，以及它们之间的关系。已知其中之一会求其余两个。设x~是精确值x（未知）的一个近似值，定义：xxxe~)~(−=为x~的（绝对）误差。绝对误差也是未知的，但可以对其大小估计，如果)~()~(xxeε≤则称)~(xε为x~的（绝对）误差限。如果考虑x本身的大小，则定义xxxxxxxxexer~~~)~()~(−≈−==为x~的相对误差。由于x未知，就把上式约等于号改为等于号作为相对误差的定义。如果)~()~(xxerrε≤则称)~(xrε为x~的一个相对误差限。如果知道绝对误差限，则有xxxr~)~()~(εε=计算机常用规格化的浮点形式表示实数。maax10.021×±=（01≠a）2这里21aa称为尾数，m称为阶数。计算机中尾数长度是固定的（假设为n位），当不能精确表示时，就用舍入法保留n位：⎩⎨⎧≤≤×+±≤≤×±=+−+95,10)10.0(40,10.0)(121121nmnnnmnaaaaaaaaxfl它是机器所能表示的与x误差最小的一个数。其误差限mnxflx101021)(××≤−−把x~写为规格化浮点形式mnaaax10.0~21×±=如果mtxx101021~××≤−−且t是满足此不等式的最大正整数，则称x~具有t位有效数字。意为尽管x未知，如果同时把x和x~四舍五入保留t位尾数则它们相等，如果保留1+t位则不等。这也是观察一个近似值有几位有效数字方法之一。当然四舍五入得到的数其尾数长度正好是有效数字位数。[例1]设32012.2~=x，4106.0~−×≤−xx，问x~有几位有效数字？相对误差有多大？相对误差限为44103.02106.0~)~()~(−−×=×≤=xxxrεε改写成规格化浮点形式110232012.0~×=x，144101021106.0~××≤×≤−−−xx知x~具有4位有效数字。[例2]已知有效数字位数，求相对误差限，反之也可求。（见P4定理1）二、了解数值稳定的概念。如果某方法（公式）在计算过程中有小的舍入误差，而这个误差对以后的影响不会放大，就称该方法是数值稳定的。如果方法A计算的结果比方法B产生的舍入误差小，也说方法A比方法B数值稳定好。数值稳定性指的是方法，与问题本身无关，是计算数学区分3于理论数学的重要标志。在数值计算中要尽量遵循P5~7的若干原则。[例3]（P11第6题）求方程根的两个根01562=+−xx(982.27783=)方法一：982.55982.2728783281=+=+=x（具有5位有效数字）018.0982.2728783282=−=−=x（具有2位有效数字）方法二：982.55982.2728783281=+=+=x（具有5位有效数字）017863.07832812=+=x（具有5位有效数字）显然方法二比方法一数值稳定好。实际上在五位尾数的机器上这是最好的结果了。第二章非线性方程（组）求解一、迭代法的基本概念和主要结果主要结论：压缩映照原理(P17定理1)和误差估计(P17定理2)，以及局部收敛的阶(P20定理3)[例1]证明xex−=在[]2ln5.0中有唯一的实根，且迭代序列kxkex−+=1对任意初值[]2ln5.00∈x都收敛于这个实根。又问要使误差不超过610−至少要迭代多少步？(提示：根据定理1和定理2做，至少迭代25步)[例2]P35第7题（提示：仿P20例4）[例3]确定常数rqp,,使得迭代法),2,1,0(5221=++=+kxarxaqpxxkkkk局部收敛到)0(3=∗aax，并有尽可能高的收敛阶，这时阶数是多少？【解】迭代函数为4522)(xarxaqpxx++=ϕ首先要1)(=++⇒ϕ=∗∗rqpxx为有尽可能高的收敛阶，令0520)52()(*623*=−−⇒=−−=ϕ′=rqpxarxaqpxxx再令050)306()(*724*=+⇒=+=ϕ′′=rqxarxaqxxx解之得：95==qp,91−=r可直接验证0)(*≠′′′xϕ，所以最高的收敛阶是3阶。二、Newton迭代法主要思想是非线性问题线性化，掌据其迭代格式和变形，知道收敛阶数，并会推广到方程组。[例4]P36第15题(提示：令0)(),()()(**≠−=xgxgxxxfm)第三章线性方程组求解一、范数理论◆常用范数：x是向量∞xxx,,21?=，A是方阵?,,,21=∞FAAAA二、矩阵分解（方程组的直接解法）◆LU分解A=LU（紧凑格式求解）◆正定矩阵的Cholesky分解RRLLATT==（L为下三角，R为上三角，主对角元全为正）◆三对角矩阵的LU分解（追赶法）三、迭代法重要结论：（1）fGxxkk+=−1收敛的充要条件1)(Gρ，且谱半径越小收敛速度越快5（2）J迭代，G-S迭代，SOR迭代的迭代矩阵是什么？（3）A严格对角占优，则J迭代，G-S迭代，SOR迭代)10(ω收敛A对称正定，则SOR迭代收敛)20(ω（包括了G-S迭代）（4）误差估计，P61定理7[例6]P70第18题（2）求得J迭代的迭代矩阵的特征值为12,12,0−−−=aaλ收敛的充要条件1λ，得2a[例7]P69第17题，此题也说明正定矩阵并不能保证J迭代收敛。[例8]设A是n阶实对称正定矩阵，其最大（小）的特征值为)(1nλλ，建立迭代公式：),2,1,0()(1=ω+ω−=+kbxAExkk求出ω的范围使迭代收敛，并求出最佳的∗ω使迭代收敛速度最快。【解】迭代矩阵AEMω−=的特征值为iωλ−1，其中iλ是A的特征值。则迭代收敛的充要条件是：1)(ρM⇔ωλ−⇔≤≤11max1ini1/20λω为使迭代收敛速度最快，∗ω要使iniωλ−≤≤1max1达到极小，由于ωλ−1是关于λ在],[1λλn上的线性函数，其极值在端点达到，故该问题化为求∗ω使{})1,)1max1201nωλ−ωλ−λω达到最小，易知（可通过作图）充要条件是nωλ−=ωλ−−1)1(1解之得)/(21nλ+λ=ω∗[例9]线性方程组bAx=⎥⎦⎤⎢⎣⎡=2123A，⎥⎦⎤⎢⎣⎡−=13b，试确定参数ω的范围，使下面的迭代法6)()()()1(bAxxxkkk−ω−=+，收敛，并求使收敛速度最快ω的值。【解】把迭代公式改写为bxAIxkkω+ω−=+)()1()(，知迭代矩阵AIMω−=从而M的特征值ωλ−=μ1（其中λ为A的特征值）。易求得A的两个特征为4,121==λλ，得M的两个特征值为ω−=μω−=μ41,121。（Ι）迭代公式收敛21012,1ω⇔μ⇔（ΙΙ）当),max()(21μμ=ρM极小时，收敛速度最快。为求使)(Mρ达到极小的ω，可通过作图或分别对410≤ω，5241≤ω≤，2152ω≤讨论，可得当52=ω时，)(Mρ取得极小值53，此时收敛速度最快。四、条件数pppAAAcond1)(−=重要结论：P55中间的估计式P56定理51)(≥Acond)()(AcondcAcond=(说明：不可能通过把矩阵乘上一个数来改变条件数)第四章插值法一、Lagrange和Newton插值多项式。◆Lagrange插值多项式：∑===nkkknnxlxfxLxP0)()()()(7其中∏≠=−−=nkjjjkjkxxxxxl0)(（称为L-基函数，它是n次多项式）◆Newton插值多项式：+−−+−+==))(](,,[)](,[)()()(102100100xxxxxxxfxxxxfxfxNxPnn)())(](,,,[11010−−−−+nnxxxxxxxxxf其中],,,[10kxxxf为k阶差商，定义见教材。◆余项（即载断误差）：L-的：∏=−+=−niinnxxnfxLxf0)()()!1()()()(ξ(P75定理2)两个简单情况（证明一下）线性插值：22181)(hMxR≤（],[,)(max,10201xxxxfMxxh∈′′=−=）抛物插值：332273)(hMxR≤（],[,)(max,2031201xxxxfMxxxxh∈′′′=−=−=）N-的：=−)()(xNxfn)())(](,,,,[1010nnxxxxxxxxxxf−−−(P78)[例1]P100第4题[解]!4)(),2)(1)(0)(1(!4)()()()4()4(3=−−−+=−xfxxxxfxPxfξxxxxP22)(233−+=[例2]P100第7题。提示：考虑过))(,()),(,(bfbafa的线性插值函数0)(1=xP二、Hermite插值和分段低次插值。[例3]（P101第15题）三、收敛性◆高次插值多项式不能保证收敛，了解Runge现象;◆分段低次插值都是收敛的，只要f(x)连续;8第五章曲线拟合和函数逼近一、线性最小二乘拟合◆问题：设)(,),(),(21xxxnϕϕϕ是],[baC上的n个线性无关的函数（称为基函数），Φ是它们线性组合的全体。即)}()()({)}(,),(),({221121xaxaxaxxxspannnnϕϕϕϕϕϕ+++==Φmkkkxfx1))}(,{(=是给定的采样点)(mn。在Φ中求一函数)()()()(*2*21*1*xaxaxaxSnnϕϕϕ+++=满足∑∑=Φ∈=−=−mkkkxSmkkkxfxSxfxS12)(12*)]()([min)]()([◆结论：记∑==m1k)()(),(kkxgxfgf，称方程组⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡),(),(),(),(),(),(),(),(),(),(),(),(2121212221212111fffaaannnnnnnnϕϕϕϕϕϕϕϕϕϕϕϕϕϕϕϕϕϕϕϕϕ#####为法方程组。系数矩阵记为G称为Gram矩阵，它是对称半正定的。如记nmnnmmnnxxxxxxxxxA×⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=)()()()()()()()()(212222111211ϕϕϕϕϕϕϕϕϕ###,⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=)()()(21nxfxfxfF#,⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=naaaa#21法方程组又可改写为FAaAATT=)(（由前面的条件数理论知，这样的方程一般都是病态的）（1）法方程组必有解（2）最小二乘问题的解与法方程组的解等价（3）平方误差9∑∑==−=−≡mkkkmkkkfaffxfxS1*12*22),(),()]()([ϕδ（222δδ=称为均方误差）[例1]根据下面数据求二次最小二乘拟合多项式，并计算平方误差ix-2–1012iy0-2-112方法一：设221022102,,1,)(xxxaxaaxP===++=ϕϕϕ直接计算法方程组（又有两种方法）得⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡7703401001001005210aaa解得21,107,1210==−=aaa，22211071)(xxxP++−=方法二：用正交多项式作为基函数。利用三项递推公式得离散正交多项式2,,12210−===xxϕϕϕ设)()()()(2211002xaxaxaxPϕϕϕ++=，用前面公式直接计算得21,107,0210===aaa，)2(21107)(22−+=xxxP平方误差：6.122=δ二、函数逼近最佳平方逼近（书上的例题和课后作业的练习题）第六章数值积分与微分一、积分◆插值型求积公式：∑∫==≈=nkkknbaxfAIdxxfI0)()(（n+1个节点）10其中∫=bakkdxxlA)(，∏≠=−−=nkjjjkjkxxxxxl0)(（L-基函数，它是n次多项式）（节点定了，系数就唯一确定了）◆插值型求积公式的代数精度m：12+≤≤nmn◆Newto