1、数值分析期末复习资料数值分析期末复习资料数值分析期末复习题型：一、填空 二、判断 三、解答（计算） 四、证明第一章误差与有效数字一、有效数字1、定义：若近似值X*的误差限是某一位的半个单位，该位到x*的第一位非零数字共有n位，就说 x*有n位有效数字。2、 两点理解：（1） 四舍五入的一定是有效数字（2） 绝对误差不会超过末位数字的半个单位eg. 丄3、 定理1 （P6）：若x*具有n位有效数字，则其相对误差虧疗茲T4、 考点：（1）计算有效数字位数：一个根据定义理解，一个根据定理1 （P7例题3）二、避免误差危害原则1、原则:（1） 避免大数吃小数（方法：从小到大相加；利用韦达定理：xl*x
2、2= c / a）避免相近数相减（方法：有理化）eg. V777-77 =c2 X2sin 7 或 减少运算次数（方法：秦九韶算法）eg. P20习题143.数值运算的误差估计1、公式：（1） 一元函数：I *（ f 3）1 Q |（於）1| *（力|或其变形公式求相对误差（两边同时除以f （卅）eg. P19习题1、2、5（2） 多元函数（P8） eg. P8例4, P19习题4第二章插值法一、 插值条件1、 定义：在区间a, b上，给定n+1个点，aWxoVxVVxWb的函数值 yi=f(xi),求次数不超过n的多项式P(x),饋兀)=儿 i = 0,1,2,，力2、 定理：满足插值条件、
3、n+1个点、点互异、多项式次数Wn的P(x)存在且唯一二、 拉格朗日插值及其余项1、 n次插值基函数表达式(P26 (2.8)2、 插值多项式表达式(P26 (2.9)3、 插值余项(P26 (2.12)：用于误差估计4、 插值基函数性质(P27 (2. 17及2. 18) eg. P28例1三、 差商(均差)及牛顿插值多项式1、 差商性质(P30)：(1)可表示为函数值的线性组合(2)差商的对称性：差商与节点的排列次序无关(3)均差与导数的关系(P31 (3.5)2、 均差表计算及牛顿插值多项式例：已知X=1,4,9的平方根为1,2,3,利用牛顿基本差商 公式求的近似值。 P2 (x) =
4、1 + 0.33333( 丫 l)-0.01667(x-l)(.v- 4) 因此计算得祈 的近似值为為(7) = 2.69992.四、埃尔米特插值(书P36)两种解法：(1)用定义做：设P$(x)二ax+bY+cx+d,将已知条件代入求解(4个条件：节点函数值、导数值相等各2个)(2)牛顿法(借助差商)：重节点eg. P49习题14五、三次样条插值定义(1)分段函数，每段都是三次多项式(2)在拼接点上连续(一阶、二阶导数均连续)S(xj) = yj/j = O/l/-/n(3)考点：利用节点函数值.导数值相等进行解题第三章函数逼近与曲线拟合曲线拟合的最小二乘法解题思路：确定輕，解法方程组，列方
5、程组求系数(注意应与系数一一对应)eg.F95习题17 形如尸ae “解题步骤：(1)线性化(2)重新制表(3)列法方程组求解(4)回代第四章数值积分与数值微分一、代数精度K概念：如果某个求积公式对于次数不超过m的多项式准确成立，但对于m+1次多项式不准确成立, 则称该求积公式具有m次代数精度2、计算方法：将f (x)=l, x, x2,x”代入式子求解eg. P100例12.插值型的求积公式(*).f(x)dx 匕 (J 二 0其中k(x)二n匕生为Lagrange插值基函数 “胪f 求积系数Ak=jalk(x)dx定理：求积公式至少具有n次代数精度的充要条件是：它是插值型的。三、牛顿-科特
6、斯公式K掌握科特斯系数n=l,2的情况即可（P104表4-1）,性质：和为1,对称性2.定理：当n为奇数时，牛顿-柯斯特公式至少有n次代数精度；当阶n为偶数时，牛顿-科特斯公式至少具有n+1次代数精度b ci3.在插值型求积公式中求积节点取为等距节点，即xk=a + khji = ,k=0, 1, 2,n。则n可构造牛顿-柯斯特求积公式：时，求积公式为梯形公式：匕冲 与0几4）+/（町n=2时，求积公式为辛普森公式：口+ /0） a 6 L I 2 丿n=4时，求积公式为柯特斯公式：”（护心气7/（观）+ 32/（召）+ 12/（勺）+ 32/（耳）+ 7/（亠）CI4、低阶求积公式的余项：梯
7、形公式：R丁 = -匚-U）2 /（“）, e a,b丄厶6.复合辛普森公式及余项(P107)h 一】 w-iS” = 7 .心)+ 4f (%) + 2/ (“ ) + f (b) L A=O k= _h J ( h、4心(/) = /-s” =-曲& f4(久), e(x, + xk+l)A=0 loU Z 7四、高斯型求积公式（书PU7-120）7Si1、定义：如果求积公式具有2n+l次代数精度，则称其节点&为高斯点。b n b 2求积公式：”（少（兀）厶= 4/（耳），4 =Jo（x） “a R=（） a I% 玉丿+S 丿f2+2（ ） b余项：& /卜帀琲归况砂心）厶2.第五章解线
8、性方程组的直接方法一、 髙斯消去法：利用增广矩阵二、 LU 分解 Ly=b； Ux=yK特点：L对角线均为1,第一列等于A的第一列除以皿；U的第一行等于A的第一行2、LU分解唯一性：A的顺序主子式DiHO 三.平方根法：Ly = bx = y例题：用平方根法解对称解：先分解系数矩阵A10最后解l7x = y7_a/6改进平方根法：A = LDLLy=bJDLix = y5.范数（误差分析）1.向量范数定义及常用范数oo-范数（最大范数）：|x| =max x11 l|x liXK|)(，= 1,2,),则称A为对角占优矩阵(严格对角占优矩阵)。z?(A) = max|Z|l2.(非常重要)谱半
9、径小于1收敛即: 7凶如II (谱半径越小，收敛速度越快)3、收敛性判别条件：1)SOR迭代法收敛的必要条件：SOR迭代收敛，则0 W2。2)SOR迭代法收敛的充要条件：A为对称正定矩阵且0 (W 2,则SOR收敛。根据迭代法收敛性定理，SOR法收敛的充分必要条件为但要计算q(GJ比较 复杂，通常都不用此结论，而直接根据方程组的系数矩阵A判断SOR迭代收敛性，下面先给出收 敛必要条件.定理1：设A = (心1,2,.)，则解方程Ax二b的SOR迭代法收敛的必要条件是0 V3 V2.定理2：若AeRnKn对称正定，且0V3V2,则解Ax=b的SOR迭代法x(k+1 = Gxk) + f对Vx e
10、 Rn迭代收敛.对于SOR迭代法，松弛因子的选择对收敛速度影响较大， 二、雅克比迭代法Ax=b(f=b)对该方程应用迭代法即得解方程组Ax=b的雅可比迭代公式（分量形式） 0 d_0 2仏。21 “22 + an-.na.ann . 00=L + D+UClii J=1B = -D(L + Uf=Db三、高斯-赛德尔迭代法a.xx. +a门X。+ + e“X =b11 1 12 2 1/J n I。2內 + a22X2 + + a2nXn = b21时，上式称为逐次超松弛迭代法；当軒=1时，上式为 Gauss-Seidel迭代法；当时，上式称为低松弛迭代法第七章非线性方程与方程组的数值解法一、
11、二分法 P214K优缺点：算法简单且总是收敛，但收敛慢。* 1 1公式兀一兀“ M（仇一绻）=盯（一“） 可能考点：已知、b、a,求n二、不动点迭代及收敛性1、 形式：耳+1=0（耳）（=0,1, 2, -）（由 f（x） =0 移项得）为卩（动的不动点2、 定理1 （不动点存在唯一性或整体收敛）：设卩（x）WCa, b满足以下两个条件: 1对任意xG a,刃有2存在正数Z1,使对任意x, ye a,刃都有祕Q -讽刃| 芈-丁则p（方在3,刃上存在唯一的不动点3、 定理2：设）ecs,刃满足定理1中的两个条件，有误差估计式4、 定理3（局部收敛）：设为认必的不动点，卩（X）在/的某个邻域连续
12、，且 0（*）1 , 则迭代法心刊闆局部收敛.做法：不动点F不知道，用h附近的x代替（题目已知“根附近x。”，代入&证明则迭代法局部收敛）5、 定理4 （收敛阶的定义及判定定理）：对于迭代过程无+i=0（无），如果0）（兀）在所求根x*的邻近连续，并馬U = （pU =0 门7（/） = 0, （pPlx*、H 0.则该迭代过程在X*的邻近是p阶收敛的.三、牛顿迭代法（切线法）及应用（大小题都可考）g s = xk_韶 a = 0,1,.）k2.收敛性：x*为单根时，牛顿迭代法在根X*的邻近是二阶（平方）收敛；x亦为重根时，仅为线性收敛。3、 应用：用牛顿法求、解法：令f（x）=x-c,代入公
13、式求解。Eg. P239习题13第八章矩阵特征值计算一.格什戈林圆盘1、设n阶矩阵A=（刚）,则A的每一个特征值必属于下面某个圆盘之中并集中.2、如果力有加个圆盘组成一个连通的并集S,且S与余下旷加个圆盘是分离的，则S内恰包含力的加个特征值。圆盘）,则2中精确地包含A的一个特征值.掌握入范围即可。Eg. P243例1二、幕法（P248例2）K幕法的基本思想是：任取非零的初始向量vO ,Vo = Wo 丰 ，U 二 A 绰-，2、计算公式:以=max(vj, 伙= 1,2,) uk =叫/人向量的规范化4、 原点平移法: 由前面讨论知道，应用幕法计算A的主特征值的时，收敛可能很慢.这时，一个补救
14、办法是采用加速收 敛的方法.引进矩阵B二A-pI其中p为参数，设A的特征值为“贝II对矩阵B的特征值为“p ,而且A, B的特征向量相 同。如果要计算力的主特征值;U只要选择合适的数使入-卩为矩阵企知Z的主特征值，且幕法求其主特征值入-必收敛速度将会加快.这种通过求虽力-pZ的主特征值和特征向量，而得到力的主特征值和特征向量的方法叫原点平移法.对于A的特征值的某种分布，它是十分有效的.5、反幕法：反幕法是用于求非奇异矩阵A的按模最小的特征值和对应特征向量的方法.而结合原点平移法的反幕法则可以求矩阵A的任何一个具有先了解的特征值和对应的特征向量。设矩阵A非奇异，其特征值人 （i=l,2, -.,
15、n）,满足 |x1|a2|-|4_1|i|o 心=右0人、 =石*其相应的特征向量 知知皿线性无关，贝!I 的特征值为1/入，对应的特征向量仍为Xi （1-1, 2,此时，的特征值满足禺划以，这种求T的方法就称为反幕法.5 =如丰0=A 、伙=1,2,） 为了避免求A 可通过解线性A = max （叫）W =叫 / A方程组Avk=u得到采用厶分解法，即先对力进行W乩=仏，求出族Uvr=和，求出叫/ 、 1（、 （比=1，2,）人严一,你从=max （叫） 从u严J人反幕法的收敛速度取决于比值收敛越快.三、豪斯霍尔德变换（初等反射矩阵）1、定义：设向量 心且2产1,称矩阵H（w） = I-2w
16、wl为初等反射阵（或称为豪斯霍尔德(Householder)变 换）.如 果 记 = （vvpw2,，叫）1-2 叶-2ww2-2wwn_2咛片1-2w；AM-2vv9vv厂2讣_2叫巴1一2”；H (w)=/2、约化定理（P255、P260例7）设x=（xif屁, X0,则存在初等反射阵H,快昭-O 6,其中r = sgn（au）|x|2=sgn（11）乞尤 ，V 1=2 丿弓=1，0,0X =如，v q 二 X + ,1 ?寸=b（b + xj.H严 I-卩一UU：,A = h a）考点：用初等反射矩阵将A进行QR分解或转化为上海森伯格矩阵（思想相同，不同之处上海森伯 格矩阵对角线下还有一
17、列）四、吉文斯变换（平面旋转变换）（P257）设石心,则变换血?为正交矩阵。用中变换：尸Px,其中COS& 丿x=g X2、xy、尸（儿乃另）：使而cos3 sin。 iIP=PG.jeu .i-sin 8 cos j1I L称为尺中平面&, X的旋转变换（或称为吉文斯（Givens） 变换），P=P（i, j,叭叫,J）称为平面旋转矩阵.显然，P（i, J, 0）具有性质：尸与单位阵z只是在（Y, Y）,（7, J）, （7； 1） , （j； J） 位置元素不一样，其它相同.（2）尸为正交矩阵（尸=戸）.P（i, （左乘）只需计算第Y行与第丿行元素，即对其中，c=cos 0,尸sin （4
18、） g丿）（右乘）只需计算第i列与第丿列元素，即 五、矩阵的QR分解，Q是正交矩阵，R是上三角矩阵 正交矩阵通常用字母Q表示。举例：A=r r12 r13;r2,也也;心 r32 nJ则有：rl 1 A2+r21 A2+r31A2=r12A2+r22A2+r32A2=r13A2+r23A2+r33八2=1r11 *r12+r21 *r22+r31 *r32=0 等性质第九章常微分方程初值问题数值解法一、 欧拉公式1、 显示欧拉公式：儿+i二儿+妙（&，儿） eg. P317习题42、 隐式欧拉公式：儿+| =儿+（+，儿+1）二、 梯形公式h1、公式：儿+=儿 + 于/（,儿）+ 儿+J考法：
19、用移项做,将右式中的畑移到左边，求出畑的表达式，再将各节点代入求解Xeg. P317 习题 3三、 改进的欧拉方法（二阶R-K公式）1、公式:$”+严儿+妙（柿几），儿宀+级比，儿）Eg. P316 习题 2四、 龙格-库塔法：*y“+严儿+”（C|K +仑2心+.+ 5心）,=0丄2, ）. p 阶精度注意点：要求局部截断误差主项时还应多写一项；泰勒展开:y（和） = y（%）+ -2尸+eg. P317-318 习题 6、7、11 12预测考题：一、 填空1、 有效数字计算2、 避免误差危害原则3、 误差估计4、 插值条件定义：求n次插值多项式5、 插值基函数性质6、 差商的对称性7、 三
20、次样条插值定义：求系数8、 根据代数精确度定义求解等式右边的系数或求解代数精确度9、 向量或矩阵范数、条件数计算10、 二分法：求n二、 判断1、 插值条件定理（条件缺一不可）。Eg.对给定的数据做插值，插值函数个数可以有许多。（J）2、 给定点集的多项式插值是唯一的，则其多项式表达式也是唯一的。（X）3、 代数精确度是衡量算法稳定性的一个重要指标。（X）4、 求积公式的阶数与所依据的插值多项式的次数一样。（X）5、 梯形公式与两点高斯公式的精度一样。（X）6、 SOR迭代法收敛，则松弛参数0 W 2o （ V）7、 A对称正定则SOR迭代一定收敛。（X）8、 只要矩阵是对称的，则阀三料（ V
21、）9、 x*为单根时，牛顿迭代法是二阶收敛的，x*为重根时，是线性收敛的。所以牛顿迭代法总是收敛的。（X）10、 0（F） 1 定收敛。（X）或/（X）定发散。（V）11、 11+hX IW1为欧拉法的绝对稳定域，hA越大越稳定。（J）三、计算1、 牛顿插值多项式计算2、 最小二乘拟合3、 复合梯形公式及余项或复合辛普森公式及余项考一题4、 利用LU解方程组5、 代数精确度：求等式右边系数、代数精确度m、余项6、 利用初等反射矩阵或吉文斯变换进行QR分解7、 用梯形公式或改进的欧拉公式求解初值问题四、证明1、 用雅克比和高斯-赛德尔迭代法证明收敛性（借助谱半径求解）eg. P209习题3、5、62、 不动点迭代（应用定理4）可能考题：证明某个迭代式子至少3阶收敛解法：计算1阶、2阶导数为0,无需证明3阶不为0 （如果题目是“证明某个迭代式子是3阶收 敛”，则需证明3阶不为0） eg. P239习题153、 局部阶段误差可能考题：给定几”的式子，求式子中的系数及局部阶段误差主项，并说明是几阶解法：利用局部截断误差的定义并借助泰勒展开
