数值分析期末复习资料.docx

1、1 数值分析期末复习 题型：一、填空 二、判断 三、解答（计算） 四、证明 第一章 误差 与有效数字 一、 有效数字 1、 定义：若近似值 x*的误差限是某一位的半个单位，该位到 x*的第一位非零数字共有 n 位，就说 x*有 n 位有效数字。 2、 两点理解： （ 1） 四舍五入的一定是有效数字 （ 2） 绝对误差不会超过末位数字的半个单位 eg. 3、 定理 1（ P6）：若 x*具有 n 位有效数字，则其相对误差限为 4、 考点： （ 1）计算有效数字位数：一个根据定义 理解 ，一个根据定理 1（ P7 例题 3） 二、 避免误差危害原则 1、 原则： （ 1） 避免大数吃小数 （方法：

2、从小到大相加；利用韦达定理： x1*x2= c / a） （ 2） 避免相近数相减（方法：有理化） eg. 或 （ 3） 减少运算次数（方法：秦九韶算法） eg.P20 习题 14 三、 数值运算的误差估计 1、 公式： （ 1） 一元函数： | *( f (x*)| | f (x*)| *(x)|或其变形公式求相对误差（两边同时除以 f (x*)） eg.P19 习题 1、 2、 5 （ 2） 多元函数（ P8） eg. P8 例 4， P19 习题 4 * ( 1)11 102 nr a ;xx xx ;1lnlnln xxx xcos1 2sin2 2 x2 第二章 插值法 一、 插值条

3、件 1、 定义：在区间 a,b上，给定 n+1 个点， a x0 x1 xn b 的函数值 yi=f(xi)，求次数不超过 n 的多项式 P(x)，使 2、 定理：满足插值条件、 n+1 个点、点互异、多项式次数 n 的 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） 可表

4、示为函数值的线性组合 （ 2） 差商的对称性：差商与节点的排列次序无关 （ 3） 均差与导数的关系（ P31（ 3.5） 2、 均差表计算及牛顿插值多项式 四、 埃尔米特插值（书 P36） 两种解法： （ 1） 用定义做：设 P3(x)=ax3+bx2+cx+d，将已知条件代入求解（ 4 个条件：节点函数值、导数值相等各 2 个） （ 2） 牛顿法（借助差商）：重节点 eg.P49 习题 14 五、 三次样条插值定义 niyxP iin ,2,1,0)( 3 （ 1） 分段函数，每段都是三次多项式 （ 2） 在拼接点上连续（一阶、二阶导数均连续） （ 3） 考点：利用节点函数值、导数值相等进行

5、解题 第三章 函数逼近与曲线拟合 一、 曲线拟合的最小二乘法 解题思路：确定 i，解法方程组，列方程组求系数（注意 i 应与系数一一对应） eg.P95 习题 17 形如 y=aebx 解题步骤： （ 1） 线性化（ 2）重新制表（ 3）列法方程组求解（ 4）回代 第四章 数值积分与数值微分 一、 代数精度 1、 概念：如果某个求积公式对于次数不超过 m 的多项式准确成立，但对于 m+1次多项式不准确成立，则称该求积公式具有 m 次代数精度 2、 计算方法：将 f(x)=1,x,x2, xn 代入式子求解 eg.P100 例 1 二、 插值型的求积公式 求积系数 定理 ：求积公式至少具有 n

6、次代数精度的充要条件是：它是插值型的。 njyxS jj ,1,0,)( 4 三、 牛顿 -科特斯公式 1、 掌握科特斯系数 n=1,2 的情况即可（ P104 表 4-1），性质：和为 1，对称性 2、 定理 ： 当 n 为奇数时，牛顿 -柯斯特公式至少有 n 次代数精度； 当阶 n 为偶数时，牛顿 -科特斯公式至少具有 n+1 次代数精度 3、 在插值型求积公式中求积节点取为 等距节点，即 ,k bax a kh h n ， k=0， 1， 2， .n。则可构造牛顿 -柯斯特求积公式 : ( ) ( )n0 0000( 1 )= b - a ( ) ,! ( )nn nknnn nnk k

7、 kk jjj k j kb a t jI C f x C d t t j d th k j n k n k （ ） ！n=1 时，求积公式为梯形公式： 2babaf x d x f a f b n=2 时，求积公式为辛普森公式 ： 462baba abf x d x f a f f b n=4 时，求积公式为柯特斯公式： 0 1 2 3 47 3 2 1 2 3 2 790babaf x d x f x f x f x f x f x 4、 低阶求积公式的余项： 梯形公式： 2 ,12T baR b a f a b 辛普森公式： 4 4 ,18 0 2S ba baR f a b 柯特斯公式

8、： 6 62 ,94 5 4C ba baR f a b 5、 复合梯形公式及余项（ P106） 1122 nnkkhT f a f x f b 1 2 10 b - a ,12nn n k k k kkR f I T h f x x 6、 复合辛普森公式及余项（ P107） 1 21101426 nnnk kkkhS f a f x f x f b 41 4 10 b- a ,18 0 2nn n k k k kk hR f I S f x x 5 四、 高斯型求积公式 （书 P117-120） 1、 定义：如果求积公式具有 2n+1 次代数精度，则称其节点 xk 为高斯点。 求积公式： 2

9、 120 1,bb n nk k kk k n kaaf x x d x A f x A x d xx x x 余项： 22 212 2 !n bnn afR f x x dxn 2、 第五章 解线性方程组的直接方法 一、 高斯消去法： 利用 增广矩阵 二、 LU 分解 Ly=b； Ux=y 1、特点： L 对角线均为 1，第一列等于 A 的第一列除以 a11； U 的第一行等于 A 的第一行 2、 LU 分解唯一性： A 的顺序主子式 Di 0 三、 平方根法 ： ; TLy b L x y 例题 ： 用平方根法解对称正定方程组 解：先分解系数矩阵 A 91096858137576321xx

10、x6 改进平方根法： 1 , TA LD L Ly b D L x y 四、 追赶法： A=LU， Ly=f， Ux=y 111 12 2 22211 1 11111nn n nn n nnnbca b crAa b crab 五、 范数 （误差分析） 1、 向量范数定义及常用范数 i1 i nx = m a x x 范 数 （ 最 大 范 数 ） ：ni1 i= 11 x = x 范 数 ：1n22i2 i= 12 x = x 范 数 ： 1pi= 1p x = x , 1N Ppi P 范 数 ： 7 2、矩阵范数定义及常用范数 nij1 i n j= 1= m a x aA 范 数 （

11、行 范 数 ） ：nij1 1 j n i= 11 = m a x aA 范 数 （ 列 范 数 ） ： m a x22= TA A A 范 数 ： 1n 22iji, j= 1=aFFA 范 数 ：其中 max TAA 表示半正定矩阵 TAA的最大特征值，矩阵的前三种范数分别与向量的 前三种范数相容 3、 条件数 条件数是 线性方程组 Ax=b 的解对 b 中的误差或不确定度的敏感性的度量。数学定义为矩阵 A 的条件数等于 A 的 范数 与 A 的逆的范数的乘积，即 1cond A A A 的逆 ，对应矩阵的 3 种范数，相应地可以定义 3 种条件数。 条件数事实上表示了矩阵计算对于误差的敏

12、感性。对于线性方程组 Ax=b，如果 A 的条件数大， b的微小改变就能引起解 x 较大的改变，数值稳定性差。如果 A 的条件数小， b 有微小的改变， x 的改变也很微小，数值稳定性好。它也可以表示 b 不变，而 A 有微小改变时， x 的变化情况。 所以当 cound（ A） 1 时，方程组 Ax=b 是病态的，否则称为良态 4、 条件数的性质： 1 ( ) 1 .vA c o n d A 、 对 任 何 非 奇 异 矩 阵 ， 都 有 11 ( ) 1 .v vvvc o n d A A A A A I 由 定 义 2 0 ( ) ( )vvA c c o n d c A c o n d

13、 A、 设 为 非 奇 异 矩 阵 且 （ 常 数 ） ， 则 22 2 23 ( ) 1 ( ) ( ) ( ) .A c o n d A A Rc o n d R A c o n d A R c o n d A、 如 果 为 正 交 矩 阵 ， 则 ； 如 果 为 非 奇 异 矩 阵 ， 为 正 交 矩 阵 , 则 n62 3 61112n1123il be r t =1n+11 1 1n n+1 2n- 1c ound =27 c ond 748 c ond( H ) =2. 9 10 ( )nc ond H 例 ： H 阵 H（ H ） （ H ）8 第六章 解线性方程组的迭代法 一、

14、 迭代法： k1 0x kB x f 迭代法收敛的两种判断方法： 1、 若 A 是 nn 矩阵，且满足ii ijjiaa()ii ijjiaa（ 1, 2, ,in ），则称 A 为对角占优矩阵（严格对角占优矩阵）。 2、 （非常重要） 谱半径 小于 1 收敛 即： 1m a x 1iinA （谱半径越小，收敛速度越快） 3、 收敛性判别条件： 1) SOR 迭代法收敛的必要条件： SOR 迭代收敛，则 0 W 2。 2) SOR 迭代法收敛的充要条件： A 为对称正定矩阵且 0 W 2，则 SOR 收敛。 根据迭代法收敛性定理， SOR 法收敛的充分必要条件为 1wG ，但要计算 wG 比

15、较复杂，通常都不用此结论，而直接根据方程组的系数矩阵 A 判断 SOR 迭代收敛性，下面先给出收敛必要条件 . 定理 1： 设 , 0 1 , 2 , . . . .nnij ijA a R a i n ， 则解方程 Ax=b 的 SOR 迭代法收敛的 必要条件是 0 2. 定理 2： 若 nnAR 对称正定，且 0 2，则解 Ax=b 的 SOR 迭代法 1kkx Gx f 对nxR 迭代收敛 . 对于 SOR 迭代法，松弛因子的选择对收敛速度影响较大， 二、 雅克比迭代法 1 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 2. . . .nnnnn n n n n n

16、a x a x a x ba x a x a x ba x a x a x b 0iia 1 12 2 1 1112 21 1 2 2221 1 1 11.1. . . .1.nnnnn n nn n nnnx a x a x bax a x a x bax a x a x ba Ax=b 1kkx Bx f （ f=b） 由方程 Ax=b 解得：11 , 1 , 2 , 3. . .ni i ij jjii jix b a x i na 9 对该方程应用迭代法 即得解方程组 Ax=b 的雅可比迭代公式（分量形式） 1k11 , 1 , 2 , 3 . . . k = 0 1 2 . . .n

17、ki i ij jjii jix b a x i na ， ， ， 11 1 2 121 221,1 , 10 00+0 0nnnn n n nna aaa aA L D Uaaa a 11( ) , f = bB D L U D 三、 高斯 -赛德尔迭代法 1 1 1 1 2 2 1 12 1 1 2 2 2 2 21 1 2 2. . . .nnnnn n n n n na x a x a x ba x a x a x ba x a x a x b 0iia ( 1 ) ( 1 ) ( ) ( ) ( )1 1 2 1 1 3 3 1 4 4 1 112( 1 ) ( 1 ) ( ) (

18、) ( )2 2 1 1 2 3 3 2 4 4 2 222( 1 ) ( 1 ) ( 1 ) ( ) ( )3 3 1 1 3 2 2 3 4 4 3 333( 1 )1()1()1(). . . .1(k k k k knnk k k k knnk k k k knnknnnx a x a x a x a x bax a x a x a x a x bax a x a x a x a x baxaa ( 1 ) ( 1 ) ( 1 ) ( 1 )1 1 2 2 3 3 1 1)k k k kn n n n n n nx a x a x a x b 应用迭代法即得解方程组 Ax=b 的高斯

19、-赛德尔迭代公式（分量形式） j- 11 k + 1 k111 , 1 , 2 , 3. . k= 0 1 2. .nki i ij j ij jj j iiix b a x a x i na ， ， ， 11, f = bB D L U D L 4、 逐次超松驰迭代法（ SOR 法 ） 10 ( 1 ) ( ) ( 1 ) ( ) ( ) ( )1 1 1 2 1 1 3 3 1 4 4 1 112( 1 ) ( ) ( 1 ) ( ) ( ) ( )2 2 2 1 1 2 3 3 2 4 4 2 222( 1 ) ( ) ( 1 ) ( 1 ) ( ) ( )3 3 3 1 1 3 2 2

20、 3 4 4 3 3331()1()1(). .k k k k k knnk k k k k knnk k k k k knnx x w a x a x a x a x bax x w a x a x a x a x bax x w a x a x a x a x ba ( 1 ) ( ) ( 1 ) ( 1 ) ( 1 ) ( 1 )1 1 2 2 3 3 1 1. .1()k k k k k kn n n n n n n n nnnx x w a x a x a x a x ba 111 , f = w bB D w L w D w U D w L 参数 w 称为松弛因子， 01 时，上式

21、称为逐次超松弛迭代法；当 w =1 时，上式为Gauss-Seidel 迭代法；当 0 w1 时，上式称为低松弛迭代法 第七章 非线性方程与方程组的数值解法 一、 二分法 P214 1、 优缺点：算法简单且总是收敛，但收敛慢。 2、 公式 可能考点：已知 、 b、 a，求 n 二、 不动点迭代 及收敛性 1、 形式： kkxx 1 (k=0,1,2, ) （ 由 f(x)=0 移项得 ） x*=(x*)为 (x)的不动点 2、 定理 1（不动点存在唯一性或整体收敛）： 设 (x) Ca, b满足以下两个条件： 1 对任意 x a, b有 a (x) b. 2 存在正数 L1，使对任意 x,y a, b都有 111* ( ) ( )22n n n nx x b a b a yxLyx )()(