数值分析公式总结

1 / 110 数值分析公式总结 第一章 1 霍纳方法： 输入 =c + bn*c bn?1*c b3*c b2*c b1*c an an?1 an?2 a2 a1 a0 bn bn?1 bn?2 b2 b1 b0 Answer P=b0 该方法用于解决多项式求值问题=anxn+an?1xn?1+an?2xn?2+a2x2+a1x+a0 2 / 110 ? 2 注： p为近似值 P 绝对误差： ?|Ep?|p?p ?|p?p Rp? |p| 相对误差： ?|101?d|p?p Rp? |p|2 有效数字 : 3 / 110 3 Big Oh(精度的计算 )： O(h?)+O(h?)=O(h?); O(hm)+O(hn)=O(hr) r=minp,q; O(hp)O(hq)=O(hs) s=q+p; 第二章 求解 x=g(x)的迭代法 用迭代规则 ，可得到序 列值。 设函数 g 满足 y 定义在得 。如果对于所有 x ， 则函数 g 在 4 / 110 ，映射 y=g(x)的范围 内有一个不动点 ; 此外，设 ，存在正常数 K 内，且对于所有 x，则函数 g 在 内有唯一的不动点 P。 ， K是一个正常数， 。如果对于所有 定理 设有 g， g 5 / 110 如果对于所有 x在 这种情况下， P成为排斥不动点，而且迭代显示出局部发散 性。波理 尔 查 . 诺 二 分 法 ( 6 / 110 二 分 法 定 ) 试值法： 应注意 越来越 小，但可能不趋近于 0，所以二分法的终止判别条件不适合于试值法 . 7 / 110 f(pk?1) 其中 k=1,2, 证明：用 f(pk?1) 牛顿 拉夫森迭代函数： pk?g(pk?1)?pk?1? 泰勒多项式证明 第三章线性方程组的解法 对于给定的解线性方程组 Ax=b a11x1 ? a12x2 ? ? ? a1nxn ? b1 a21x1 ? a22x2 ? ? ? a2nxn ? b2 ? an1x1 ? an2x2 ? ? ? annxn ? bn 一 Gauss Elimination a11x1 ? a12x2 ? ? ? a1nxn ? b1 a21x1 ? a22x2 ? ? ? a2nxn ? b2? 8 / 110 ） Back 初始值 0,x0,?,x0x1n2 四 Jacobi Method 1.选择初始值 2.迭代方程为 0,x0,?,x0x1n2 k?1? x1k?1 ? x2 k? ? ? axk)b1?(a12x1nn a11 k? ? ? axk)b2?(a21x2nn 9 / 110 a22 k ? axk ? ? ? ak)bn?(an1xxn2nn?1? k?1 xn ? ann 五 Gauss Seidel Method 1.迭代方程为 kk b?(ax? ? ? axk?111221nn)x1? a11k?1k b?(ax? ? ? axk?122112nn)x2 ? 10 / 110 a22 ? k?1 k?1 k?1 2.选择初始值 判断是否能用 0,x0,?,x0x1n2 Jacobi Method 或者 Gauss Seidel Method 的充分条件 第四章 插值与多项式逼近 第一节 泰勒级数和函数计 算 11 / 110 一些常用函数的泰勒级数展开： for all x for all x for all x -1 -1 for 第一章 非线性方程和方程组的数值解法 1）二分法的基本原理，误差： x? b?a k?1 12 / 110 2 2）迭代法收敛阶： lim i? ?i?1?i p ?c?0，若 p?1则要求 0?c?1 3）单点迭代收敛定理： 定理一：若当 x?a,b?时， ?(x)?a,b?且 ?(x)?l?1， ?x?a,b?，则迭代格式收敛 于唯一的根； 定理二：设 ?(x) 满足： x?a,b? 时， ?(x)?a,b? ， 13 / 110 ?x1,x2?a,b?, 有 ?(x1)?(x2)?lx1?x2,0?l?1 则对任意初值 x0?a,b?迭代收敛，且： 1 xi?1?xi 1?l li ?xi?x1?x0 1?l ?xi? 定理三：设 ?(x)在 ?的邻域内具有连续的一阶导数，且 ?(?)?1，则迭代格式具有局部收敛性； 定理四：假设 ?(x)在根 ?的邻域内充分可导，则迭代格式xi?1?(xi)是 P阶收敛的 ? 14 / 110 (j) (?)?0,j?1,?,P?1,?(P)(?)?0 f(xi) ，平方收敛 f(xi) 4） Newton 迭代法： xi?1?xi?5） Newton 迭代法收敛定理： 设 f(x)在有根区间 ?a,b?上有二阶导数，且满足： ：f(a)f(b)?0； ： f(x)?0,x?a,b?； ： f不变号 ,x?a,b? ：初值 x0?a,b?使得 f(x)f(x)?0； 15 / 110 则 Newton迭代法收敛于根 ?。 6）多点迭代法： xi?1?xi? f(xi)f(xi)f(xi?1) ?xi?1?xi ii?1f(xi)?f(xi?1)f(xi?1)?f(xi)xi?xi?1 收敛阶： P? f(xi) f(xi) 7） Newton 迭代法求重根，对 Newton 法进行修改 ：已知根的重数 r， xi?1?xi?r ：未知根的重数： xi?1?xi?根。 16 / 110 8）迭代加速收敛方法： u(xi)f(x) ， ?为 f(x)的重根，则 ?为 u(x)的单 ,u(x)? u(xi)f(x) xixi?2?xi2?1 xi?1? xi?2?2xi?1?xixi?1?(xi)xi?2?(xi?1) 当不动点迭代函数 ?(x)在 ?的某个邻域内具有二阶导数， ?(?)?L?1,0 平方收敛 9）确定根的重数：当 Newton 迭代法收敛较慢时，表明方程有重根 17 / 110 xixi?2?xi2?1xi?11 r? xi?2?2xi?1?xixi?2?xi?1xi?2?xi?1 10）拟 Newton法 ?xi?1?xi?Ai?1F(xi)?i?1ii?1i?1?Ai?1(x?x)?F(x)?F(x)若 Ai非奇异，则 Hi?Ai?A?A?A ii?i?1 i?1ii?x?x?HiF(x)?i?1ii?1i?Hi?1(F(x)?F(x)?(x?x)?H?H?H ii?i?1 ?f1?f1?f1 ?i?xi?xi 18 / 110 ?xn12 ? ?f2?f2?f2 ?iii?i ?xn其中 Ai?F(x)?x1?x2 ? ?f?f?fnn?n?iii?xn?x1?x2? 11）秩 1 拟 Newton 法： ?xi?1?xi?Ai?1F(xi)?iT, 其中ri?xi?1?xi,yi?F(xi?1)?F(xi) ?(r)iiA?A?(y?Ar)ii?i?1 (ri)Tri? Broyden 秩 1方法 ?xi?1?xi?HiF(xi) 19 / 110 ?(ri)THi ii ?Hi?1?Hi?(r?Hiy)(ri)THyi i? 第二章 线性代数方程组数值解法 1）向量范数： ：非负性： x?0，且 x?0的充要条件是 x?0； ：齐次性： ?x?x ：三角不等式： x?y?x?y 1 范数： x1? ?x i?1 20 / 110 n i 12 2 范数： x 2 ?(?xi) i?1? n 2 ?范数： x p 范数： x 21 / 110 ?maxxi 1?i?n p ?(?xi) i?1 n p 1p 2）矩阵范数： ：非负性： A?0，且 A?0的充要条件是 A?0； ：齐次性： ?A?A 22 / 110 ：三角不等式： A?B?A?B ：乘法不等式： AB?AB F 范数： A F ?2?aij? ?i?1j?1? n n 1?j?n 1 2 1 范数： A?max ?a 23 / 110 i?1 n ij ，列和最大 ?范数： A1?max?aij，行和最大 1?i?n j?1 n 2 范数： A 24 / 110 2 ? ?max?i， ?i为 AHA的特征值， ?(A)?A 1?i?n 3） Gauss消元法： M? 13 n； 3 13 Gauss-Jordan 消元法： M?n； 2 25 / 110 列选主元消元法：在消元之前进行行变换，将该列最大元素换置对角线主元位置； 全选主元消元法：全矩阵搜索矩阵最大元素进行行变换和列变换至其处于对角线主元位置； 4）三角分解法： ： Doolittle分解法： A=LU， L单位下三角阵， U 上三角阵 ： Crout分解法： A=LU， L下三角阵， U 单位上三角阵 ：Cholesky分解法： A 对称正定， A?LL， L 为单位下三角阵 ：改进的 Cholesky 分解法： A 对称正定， A?LDL， L 为单位下三角阵， D为对角阵 ：追赶法： Crout分解法解三对角方程 ?1 5）矩阵的条件数 cond(A)?AA?1，谱条件数： cond2(A)?A T T 26 / 110 2 A?1 2 ?x x Cond(A)? ?A A 1?Cond(A) A A 27 / 110 ?1 6）如果 B?1，则 I?B为非奇异阵，且 (I?B)? 1 1?B 7）迭 代法基本原理： ：迭代法： x i?1 ?Bxi?K i i? ： ?(B)?1(?limB?0，迭代格式收敛 ) ：至少存在一种矩阵的从属范数，使 B?1 8） Jacobi 迭代： A?L?D?U 28 / 110 xi?1?(I?D?1A)xi?D?1b 9） Gauss-Seidel 迭代： x10）超松弛迭代法 x i?1 i?1 ?(L?D)?1Uxi?(L?D)?1b ?xi?ri?1 11）二次函数的一维搜索： x2?x1?1P1 12）最速下降法： 选择方向 Z0?gradf(x0)?r0?b?Ax0 (r0,r0)进行一维搜索： x?x?0r，其中 ?0? (Ar0,r0) 1 29 / 110 13）共轭梯度法： 11 第一步：最速下降法， P?r， r?b?Ax， (r0,r1)?0 (r1,AP0)11 Px 第二步：过 x 选择 P 的共轭方向 P?r?P，其中 ?0，过以为方 0 (P,AP) 1 110 ?x2?x1?1P1?11 向的共轭直线为 x?x?tP，进行二次函数的一维搜索 ?(r1,P1) ?1?(AP1,P1)? 30 / 110 14）一般的共轭梯度法： 第三章 插值法与数值逼近 1）Lagrange插值： Ln(x)? ?l(x)f(x)， j j j?0 n lj(x)? (x?x1)?(x?xj?1)(x?xj?1)?(x?xn)(xj?x1)?(xj?xj?1)(xj?xj?1)?(xj?xn) ? Pn?1(x) 31 / 110 (x?xj)Pn?1(xj) f(n?1)(?) 余项： E(x)?Pn?1(x) (n?1)! 2） Newton 插值：差商表 x0 f(x0) x1 f(x1) x2 f(x2) x3 f(x3) fx0 x1 fx0 x2 fx0 x3 fx0 x1 x2 fx0 x1 x3 fx0 x1 x2 x3 f(x)?f(x0)?fx0 x1(x?x0)?fx0 x1?xn(x?x0)?(x?xn?1)?fx0 x1?xnx(x?x0)?(x?xn) 32 / 110 f(n?1)(?) 余项 E(x)?fx0 x1?xnx(x?x0)?(x?xn)?Pn?1(x) (n?1)! 3）反插值 第一章 绪论 误差来源：模型误差、观测误差、截断误差、舍入误差 x =|x?x?| 是 x?的绝对误差， e=x?x 是 x?的误差， x = x?x? ， 为 x?的绝对误差 限 er=x= e x?xx x? 的相对误差，当 |er|较小时，令 er=x= e 33 / 110 x?xx x =r 相对误差绝对值得上限称为相对误差限记为： r 即： er = |x?x| x 绝对误差有量纲，而相对误差无量纲 若近似值 x?的绝对误差限为某一位上的半 个单位，且该位直到 x?的第一位非零数字共有 n位，则称近似值 x?有 n 位有效数字，或说 x ?精确到该位。 例：设 x= 那么 x?=3,1 x =100, 则 x?有效数字为 1 位，即个位上的 3，或说 x ?精确到个位。 科学计数法：记 x?=?an10m 其中 a10 , 若 x?x? 34 / 110 10m?n ，则 x?有 n 位有效数字，精确到 10m?n。 由有效数字求相对误差限：设近似值 x?=?an10m 有 n位有效数字，则其相对误差限为 12a1 101?n 由相对误差限求有效数字：设近似值 x?=?an10m 的相对误差限为为 12 101?n 则它有 n 位有效数字 令 x?、 y?是 x、 y的近似值，且 |x?x| x 、 |y?y|(y) 1. x+y 近似值为 x?+y?,且 x+y = x + 和的误差等于误差的和 2. x-y近似值为 x?y?,且 x+y = x + 3. xy近似值为 x?y?, xy x? ? y + y? ?(x) 4. (y 35 / 110 x x? ? y + y? ?(x) |y?|2 1避免两相近数相减 2避免用绝对值很小的数作除数 3避免大数吃小数 4尽量减少计算工作量 第二章 非线性方程求根 1.逐步搜索法 设 f (a) 0，有根区间为 (a, b)，从 x0=a 出发， 按某个预定步长 (例如 h=(b-a)/N)一步一步向右跨，每跨一步进行一次根的搜索，即判别 f(xk)=f(a+kh)的符号，若 f(xk)0(而f(xk-1) 2.二分法 设 f(x)的有根区间为 a,b= a0,b0, f(a)0.将 a0,b0对分，中点 x0= (a0+b0)/2),计算 f(x0)。对于给定精度 ，即 36 / 110 b?a2 ln b?a ?ln?() ln2 3.比例法 一般地，设 ak,bk为有根区间，过 (ak, f(ak)、 (bk, f(bk)作直线，与 x 轴交于一 点 xk,则： x=a?f b ?f(a)?(b?a) 1.试位法每次迭代比二分法多算一次乘法，而且不保证收敛。 2.比例法不是通过使求根区间缩小到 0 来求根，而是在一定条件下直接构造出一个点列，使该点列收敛到方程的根。 这正是迭代法的基本思想。 事先估计 :|x?xk| 事后估计 |x?xk| L1?L11?L 37 / 110 f(a) |x1?x0| |xk+1?xk| 局部收敛性判定定理：设 x?为方程 x= x 的根， (x)在 x?的某一邻域内连续， 且 (x?) 局部收敛性定理对迭代函数的要求较弱，但对初始点要求较高，即初始点必须选在精确解的附近 Steffensen迭代格式： x k+1=(xk) k+1=(xx k+1) xk+1 Newton 法： xk+1=xk?f (xk) k (x k+1?xk)2=xk? 38 / 110 k+1k+1k f(x) Newton 下山法： xk+1=xk? 弦割法： xk+1=xk? f(xk)f(xk) , 是下山因子 f xk ?(xk?xk?1) f xk ?f(xk?1) 抛物线法：令 t=x?xk,h0=xk?2?xk,h1=xk?1?xk,可化为 y t =at2+bt+c 其中： f xk?2 ?c ?h1? f xk?1 ?c ?h0a=h1?h0?h0?h1 f xk?1 ?c ?h02? f xk?2 ?c ?h12b=h1?h0?h0?h1c=f(xk) 则： 39 / 110 b0 = x+b0 k ek+1 ek xk?2c xk+1 设迭代 xk+1 = g(xk) 收敛到 g(x) 的不动点 x* 设 ek = xk ? x*若 limk =C， 则称该迭代为 p 阶收敛，其中 C (不为 0)称为渐进误差常数 第三章 解线性方程组直接法 ?1 列主元 LU 分解法：计算主元 Si=aik? kr=1lirurk，i=k,k+1n 选主元 Sik =maxkin Si 40 / 110 u1j=a1j， m=1 k?1 Cholesky平方根法：系数矩阵 A必须对称正定 AX=b? k?1 Ly=b (其中 A=LLT) T Lx=y l11= 11， li1= k?1 ai1 41 / 110 (i=2,3n)11 1 lkk= akk? lkm2， lik=(a? limlkm)(i=k+1,k+2n ， k=2,3n) kkik m=1m=1 改进 Cholesky 分解法： A=LDLT 1 l 21L= l31 ln11 l 21 A= l31 ln1 1l32ln21l32ln2 1 j?1 42 / 110 1 ln(n?1) ? d 1 ， D= 1 d1 ， D= 1 d2 ? ? T 。由 A=L(DL) dn ? 43 / 110 d1ln1 d2ln2 d3ln3 ，逐行相乘 ? dn d1l21d2 d1l31d2l32? ln(n?1) ? 1 l=: xi(k+1)= (k)xi ? k+1 k ?(bi? aijxj? 44 / 110 aijxj),(i=1,2n;k=0,1,2) ii j=1 j=i+1 i?1 n i?1n 或： xi (k+1) ? k k+1 k = 1? xi+(bi? aijxj? aijxj),(i=1,2n;k=0,1,2) ii 45 / 110 j=1 j=i+1 当 ?=1时，就是基于 Jacobi迭代的 Gauss-Seidel迭代。 第五章 插值法 Lagrange插值法： lj xi = 0， ij1 ， i=j n ，则 lj x = i=0 x?xi ji 46 / 110 构造插值函数： Ln xi =f xi =yi， i=0,1n ，令 L x =l0 x y0+l1 x y1+?+ln(x)yn nin 则： y=Ln x = nj=0lj x yj= j=0 i=0(x?x) yj ij j i (x?x) 若记： ? x = x?x0 x?x1 x?xn = ni=0 n+1 则可改为： lj x = x?x ? j 47 / 110 ?(x) n+1 i x = n n n，则 Ly=i=0njj=0j=0 x?x ?(x)yj (x)(x?x)j ij j i j j (x?x)?(x) 则插值余项： Rn x =f x ?Ln x = 48 / 110 fn+1 ?n+1(x) n+1! 逐次线性插值法 Aitken ： ?,? ? ?,? ? ?(?)? ? =? ?,?,?=?,?+ ? ?(?)? Newton 插值法： N(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+an(x -x0)(x-x1)(x-xn)并满足 N(x)=f(x) 差商的函数值表示： f x0,x1xk = ki=0? 差商与导数的关系： f x0,x1xk = f n ()n! f(xi) k+1(xi) 49 / 110 则： f x =f x0 +f x0,x1 ?1 x +?+f x0,x1xn ?n x +f x,x0,x1xn+1 ?n+1 x 等距节点 Newton 插值公式： ttk Newton 向前插值： Nn a+th =f x + nk=1?y0 k ，其中 k =t 余项： Rn x =fn+1 hn+1 n+1 ， t= x?x0h t t?1 (t?k+1) k! t+k?1k Newton 向后插值： Nn xn+th =f xn + nk=1?yn k t+n 余项： Rn x =fn+1 hn+1 n+1 n Hermite插值： H x = nj=0j x yj+ j=0j x yj 2 j x = Ax+B l2j x ， j x = Cx+ D lj(x) 50 / 110 i x = 1?2 x?xi nl2k=0i(x)x?xkkii 可得： 2 i x = x?xi li(x) 1 数值分析复习提要 一、纲要 数值积分与数值微分一章中主要的要点如下： 、数值积分的提法、插值型求积公式的导出及其余项估计 、低阶数值积分公式及其余项的估计 、数值积分的加速过程： Romberg 算法与埃特金方法 、高精度求积公式： Gauss求积公式 二、要点 、若要求积分 I? ?f?x?dx，当 f?x?的解析表达式未知或其解析表达式51 / 110 不易于计算积分值 a b 时，可以考虑用数值的方法求得它的一 个近似值 I*。如果已知函数 f?x?在 n?1 个节点上的值 f?xi?,i?0,1,?,n，那么可以用这些节点构造一个插值多项式 Pn?x?，用 Pn?x?近似表示 f?x?，并用 I? * ? n b a Pn?x?近似表示 I，这时 52 / 110 n b n I * ? ? b b a Pn?x?dx? 53 / 110 ?f?x?l?x?dx?f?x?l?x?dx?Af?x? a i i i i?0 i?0 a i i i 54 / 110 i?0 n b 上式就称为插值型求积公式。更一般地，如果一种求积公式可以写为： I? ?f?x?dx a ?I * ? 55 / 110 ?Af?x? i i i?0 就称为机械求积公式，显然，插值求积公式就是一种机械求积公式。 、在上述的插值型求积公式中，特别地，当给定的 n?1 个节点是等距的时候，构造出来的求 积公式称为 Newton-Cotes 求积公式它的一般表达式可以写为： In?b?a?Ck k?0n ?n? 56 / 110 f?xk? ?n? 其中 Ck称为 Cotes 系数。特别地当 n?1时 Newton-Cotes 求积公式称为梯型求积公式，写 为： T? 12 ?b?a?f?a?f?b? 当 n?2时 Newton-Cotes 求积公式称为抛物求积公式，写为： S? 16 57 / 110 ?b?a?f?a?4f? ? ? ?a?b? ?f?b? ?2? 当 n?4 时 Newton-Cotes 求积公式称为 Cotes 求积公式，写为： C? 190 ?b?a?7f?a?32f?x1?12f?x2?32f?x3?7f?b? 其中 a,x1,x2,x3,b 是区间 ?a,b?的四等分点。 58 / 110 、为了估计上面求积公式的精度，引入代数精度的概念。如果一种求积公式 I? ?f?x?dx a b ?I * ? ?Af?x? i 59 / 110 i i?0 n 对于 f?x?是 n 次代数多项式时是精确成立的，但对于 n?1 的代数多项式不能再精确成立那么，就称上面的求积公式具有n 次代数精度。由概念可以直接得到这样的结论插值型求积公式至少具有 n次代数精度。容易证明第二个结论：当 n 为偶数的时候插值型求积公式至少具有 n?1 次代数精度。由代数精度的概念出发，再加上积分中值定理可以得到一些低阶的求积公式的余项估计。 、梯型求积公式的余项估计为： R?T?I?T? ? b f?2 60 / 110 ? a ?x?a?x?b?dx ? f?12 ?b?a?3,?a,b? 辛甫森求积公式的余项估计为： R?S?I?S? ? b f ?4? 61 / 110 ? a 4! a?b? ?x?a?x? 2? 6 2 b?a?b?a? ?x?b?dx?f 180?2? 62 / 110 4 ?4? ? Cotes求积公式的余项估计为： 2?b?a?b?a? R?C?I?C?f 945?4? ?6? ? 、当用 Newton-Cotes 求积公式的时，当 n 很大时一样存在数值不稳定性。为了使用低阶求积 公式，并且能达到较高的计算精度，可以将区间 ?a,b?做若干等分，在每个子区间 ?xi,xi?1?上使用低阶求积公式，这样的方法称为复化求积方法。若在子区间中用梯型求积公式63 / 110 就有： ? b a f?x?dx? ? i xi?1 xi f?x?dx? ? 64 / 110 i ?1? ?x?xfx?fxi?1iii?1?2? ?T i i ?Tn 称为复化梯型求积公式；若在子区间上用辛甫森求积公式，就有： ? b a 65 / 110 f?x?dx? ? i xi?1 xi f?x?dx ? ?f?xi?1? ? ? ? ii 66 / 110 ?1? ?xi?1?xi?f?xi?4f?x1 ?i?6?2? i ?S ?Sn 称为复化辛甫生求积 公式；同理可得其它的复化求积公式。 、复化求积公式的余项估计是先估计每个子区间的误差，然后再取和。其过程是简单的。几个简单复化求积公式的余项估计： I?Tn? b?a12 67 / 110 hf?,h 是区间 ?a,b?的等分步长 2 I?Sn b?a?h?f 180?2? 4 ?4? ? ?6? I?Cn 2?b?a?h?f 68 / 110 945?4? 6 ? 、由以上的误差估计式，在 f?x?较平坦、光滑的假设下，可以容易导出复化求积 过程的一个收敛加速算法： Romberg 算法，可以表示为 Tn?Sn?Cn?Rn? ? i ?1?x?xfx?fxiii?1?2i?1? 13Tn115163 69 / 110 43 T2n? 16156463 (来自 : 海达范文网 :数值分析公式总结 ) SnCn S2n?C2n? 、 Romberg算法可以实现的前提是 “f?x? 较平坦、光滑 ” ，如果这个条件不成立，那么 Romberg 算法的收敛是值得商榷的。为了解决这个问题，利用一致逼近的思想可以找到一个高精度 的数值求积算法： Gauss 求积方法，它可以达到最高的代数精度为 2n?1。一般表达式可以写为： G? ?Af?x? 70 / 110 i i i?0 n 其中 xi,i?0,1,?,n 是 Gauss点， Ai,i?0,1,?,n 是求积系数。 、利用一些插值方法可以求得在给定的那些节点上的微分值，这种方法称为数值微分。 三、例题 、确定下列求积公式中的待定系数，使其代数精度尽量高，并指出求积公式所具有的代数精度。 ?1? ? h 71 / 110 ?h f?x?dx?A?1f?h?A0f?0?A1f?h? 解：这是 n?2的 Newton Cotes求积公式，至少具有三次代数 精 度 。 由 此 可 以 确 定 它 的 系 数 ， 取f?x?1,f?x?x,f?x?x,f?x?x 可得以下方程组： 2 3 ?h1dx?A?A?A?2h ?101 ?h?h ?hxdx?hA?1?hA1?0?h 72 / 110 2 ?x2dx?h2A?1?h2A1?h3 3?h ?h333 xdx?hA?1?hA1?0?h 1?A?A?h?11?3? ?A?4h0?3? 如果取 f?x?x，它的积分真值为 I? 4 ? h 73 / 110 ?h xdx? 4 25 h，如果用积分公式来计算则得到它的近 5 似值为 I? * 13 h? 5 74 / 110 13 h 5 ? 23 h，所以 I*?I，求积公式只具有 3 次代数精度。 5 、验证梯型求积公式只具有一次代数精度 证明：梯型求积公式为 T? 12 ?b?a?f?a?f?b?，取 f?x?1时，有 ? 75 / 110 b a 1dx?b?a? 12 ?b?a?1?1?T 取 f?x?x时 ? b a xdx? 12 76 / 110 ?b?a?f?a?f?b?T 2 取 f?x?x时，积分真值为 ? b a xdx? 2 13 ?b 3 77 / 110 ?a 3 ? 梯型求积公式的值为 T? b?a2 ?a 2 ?b 2 ? 78 / 110 1 x 故 I?T，即梯型求积公式只具有 1 次代数精度。 、分别应用梯型求积公式、 Simpson 求积公式、 Cotes 求积公式计算积分 ?edx，并估计各 种方法的误差 解：运用梯形求积公式 ? 1 x 10 edx? 79 / 110 2 ?e ?e 1 ? 其误 差 R?f ? ? 1 80 / 110 ? 3 112 e?1?0? 12 e? 应用 Simpson求积公式， ?1 ex dx?1?1 04e2 81 / 110 ?e1?06?e? ?其误差为 R?f ? ? 12880 e ? ? e2880 ? 82 / 110 应用 Cotes求积公式，有 ?1 x1?1130424 7e1?0edx?90?7e?32e?12e?32e? ?其误差为： 6 R?f ? ?2?1?2e 945?e?4 ? ?4?9456 83 / 110 、推导下列三种矩形求积公式 ?ba f?x?dx?b?a?f?a?f?2 2 ?b?a?bf?a f?x?dx?b?a?f?b?2 ?b?a?2 ? b f?x?dx?b?a?f?a?b? f?a 84 / 110 ?2? ? 24?b?a?3 解 ： 将 f?x? 在 x?a 处 Taylor 展开，得 f?x?f?a?f?x?a?,?a,x? 两边在 ?a,b?上积分，得 ?b a f?x?dx ? ?bf?a?dx?b a ? 85 / 110 a f?x?a?dx ?b?a?f?a? ? b a f?x?a?dx ?b?a?f?a?f?b a ?x?a?dx?由积分中值定理得来的 ?b?a?f?a? 86 / 110 12 f?b?a?2 , ?。 数值分析复习总结 第二章 数值分析基本概念 教学内容： 1. 误差与有效数字 误差、误差限、 相对误差、相对误差限和有效数字的定义及相互关系； 误差的来源和误差的基本特性； 误差的计算的基本方法。 2. 算法的适定性问题 数值分析中的病态和不稳定性问题介绍； 病态问题和不稳87 / 110 定算法的实例分析。 3. 数值计算的几个注意问题 避免相近二数相减； 避免小分母； 避免大数吃小数； 选用稳定的算法。 1.数值分析简介 数值分析的任务 数值 分析是研究求解各类数学问题的数值方法和有关理论的学科 数值分析的过程 构造算法、使用算法、分析算法 2. 数值计算的基本概念 ? 误差概念和分析 误差的定义： 设 x 是精确值， p 是近似值，则定义两者之差是绝对误差 : ?a 88 / 110 ?x?p 由于精确值一般是未知的 ,因而 不能求出来 ,但可以根据测量误差或计算情况估计它的上限 |x-p|? ?称为绝对误差限。 相对误差定义为绝对误差与精确值之比 ?r? ?ax ?r? 89 / 110 ?a ?x 称为相对误差限 误差的来源： 舍入误差 将无限位字长的精确数处理成有限位字长近似数的处理方法称为舍入方法。带来舍人误差。 有效数字 对于 a=a0 a1 am . am+1 am+n(a00) 的近似数， 若| ， 则称 a为具有 m+n+1 位有效数字的有效数，其中每一位数字都叫做 a 的有效数字。有效数和可靠数的最末位数字称为可疑数字 有效数位的多少直接影响到近似值的绝对误差与相对误差90 / 110 的大小。 推论 1 对于给出的有效数，其绝对误差限不大于其最末数字的半个单位。 x?an?10m 1 ?x?x?10m?n 2x?an?10m 5 ?r(x)?10?n a1 推论 2 对于给出的一个有效数，其相对误差限可估计如下： 例 :计算 y = ln x。若 x ? 20，则取 x的几位有效数字可保证 y 的相对误差 截断误差 91 / 110 用数值法求解数学模型时，往往用简单代替复杂 ,或者用有限过程代替无限过程所引起的误差。 ? 数值计算的算法问题 “ 良态 ” 问题和 “ 病态 ” 问题 在适定的情况下，若对于原始数据很小的变化 X ，对应的参数误差 y 也很小，则称该数学问题是良态问题； 若 y很大，则称为病态问题。 病态问题中解对于数据的变化率都很大，因此数据微小变化必将导致参数模型精确解的很大变化。 数学问题的性态完全取决于该数学问题本身的属性，在采用数值方法求解之前就存在，与数值方法无关。 稳定算法和不稳定算法 如果用数值方法计算时 ,舍入误差对结果影响小的算法称为稳定算法。否则称为不稳定算法。 92 / 110 ? 数值计算应注意的问题 第三章 线性方程组求解的数值方法 教学内容： 1. 高斯消元法 消元法的实现过程； 主元问题。 2. 矩阵分解 矩阵 LU 分解的一般计算公式； 利用 LU 分解的线性方程组求解方法； Cholesky 分解； Matlab 的 Cholesky 分解函数。 3. 93 / 110 向量范数与矩阵范数 向量范数及其性质； 矩阵函数及其性质； 常用范数形式。 4. 线性方程组的迭代法求解 迭代求解的思路； Jacobi 迭代法； 高斯 _赛德尔迭代法； 松弛法； 迭代法的收敛性。 5. 方程组的病态问题与误差分析 线性方程组解的误差分析； 条件数和方程组的病态性。 消元法： 问题： 消去法是按照系数矩阵的主对角线上的元素进行消元。从而可能出现： 某个主元为零，导致消元过程无法进行。 当某个主元的绝对值很小时，计算结果误差很大。 定理： 若 A 的所有顺 序主子式 均不为 0，