数值计算方法复习提纲

1、.数值计算方法复习提纲第一章数值计算中的误差分析1了解误差及其主要来源，误差估计；2了解误差 ( 绝对误差、相对误差 ) 和有效数字的概念及其关系；3掌握算法及其稳定性，设计算法遵循的原则。1、 误差的来源模型误差观测误差截断误差舍入误差2 误差与有效数字绝对误差E（x）=x-x*绝对误差限x*x x*相对误差Er (x) ( x x* ) / x ( xx* ) / x*有效数字x*0.a1 a2 .an10 m若 xx*110mn ，称 x* 有 n 位有效数字。2有效数字与误差关系（ 1）m 一定时，有效数字n 越多，绝对误差限越小；（ 2）x* 有 n 位有效数字，则相对误差限为Er

2、(x)110 (n 1) 。2a1选择算法应遵循的原则1、 选用数值稳定的算法，控制误差传播；例 I n11nexdxex0I011I n1nI n1e xnn! x02、 简化计算步骤，减少运算次数；3、 避免两个相近数相减，和接近零的数作分母；避免;.第二章线性方程组的数值解法1了解 Gauss 消元法、主元消元法基本思想及算法；2掌握矩阵的三角分解，并利用三角分解求解方程组；（ Doolittle 分解； Crout 分解； Cholesky 分解；追赶法）3掌握迭代法的基本思想，Jacobi 迭代法与 Gauss-Seidel迭代法；4掌握向量与矩阵的范数及其性质, 迭代法的收敛性及其

3、判定。本章主要解决线性方程组求解问题，假设n 行 n 列线性方程组有唯一解，如何得到其解？a11x1a12 x2.a1n xnb1a21x1a22 x2.a2n xnb2.an1x1an 2 x2.ann xnbn两类方法，第一是直接解法，得到其精确解；第二是迭代解法，得到其近似解。一、Gauss消去法1、 顺序 auss 消去法记方程组为：a11(1) x1a12(1) x2. a1(1n) xnb1(1)a21(1) x1a22(1) x2. a2(1n) xnb2(1).an(11) x1an(12) x2. ann(1) xnbn(1)消元过程：经步消元，化为上三角方程组a11(1)

4、x1b1(1)a 21(2) x1a22(2 ) x2b2( 2).an(1n) x1a n(n2) x2.ann(n ) xnbn( n)第步若 akk(k)0( k 1)( k)aik(k )(k )( k 1)( k )aik(k )( k)aijaijakk(k ) akjbibiakk(k )bkk 1,.n 1 i, j k 1,.,n回代过程：;.xn bn(n)/ ann(n)nxi (bi(i )aij(i ) x j ) / aii(i)(i n 1, n 2,.1)ji 1、 auss消去法避免回代，消元时上下同时消元、 auss 列主元消去法例 ：说明直接消元，出现错误

5、0.00001x12x22x1x23由顺序 auss 消去法，得 x21, x1 0 ； auss 列主元消去法原理：每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵AMbaijn( n 1) 表示。（ 1）消元过程：对 k=1,2,n-1,选主元，找 i k k, k 1, n 使得aik, kmax aikk i n如果 aik ,k0 ，则矩阵 A 奇异，程序结束；否则执行3。如果 ikk，则交换第 k 行与第 ik 行对应的元素位置，akjai k j , jk,ggg,n1.消元，对 i=k+1,L ,n,计算likaik, 对 j=L+1,L ,n+1,计算akkaijai

6、jlik akj（2）回代过程：1若 ann0, 则矩阵 A 奇异，程序结束；否则执行。xnan,n 1n1,L,2,1,计算2ann ; 对inai , n1aij x jj i 1xiaii;.举例说明。4、消元法应用（ 1）行列式计算；（ 2）矩阵求逆。二、利用矩阵三角分解求解线性方程组1、求解原理线性方程组写成矩阵形式为：AX=b若 A=LU，则 LUX= b，记 UX=Y则 LY= b若 L、 U 为特殊矩阵，则求解线性方程组变为解两个特殊线性方程组问题。2、 Doolittle 分解L 为下三角矩阵 , U 为上三角矩阵 ,不一定能分解 ,分解也不一定唯一 ; 设 L 或 U 是单

7、位三角矩阵 , 若能分解 ,则可分解唯一 .L 是单位下三角矩阵,称为 Doolittle 分解 ;U 是单位上三角矩阵,称为 Crout 分解；定理 : n 阶矩阵 A 有唯一分解的充要条件为A 的前 n-1 阶主子式都不为0.Doolittle 分解算法：a11a12.a1n1u11u12.u1na21a22.a2nl 211u22.u2 n. . . . . . .an1an2.annln1l n2.1unn由矩阵乘法：aijnl ik ukjk1得到：k1ukjakjl kr urjjk, k1,.n;r1k1l ik( aikl ir u rk ) / ukkik, k1,.nr1算

8、法特点：先计算U 的行，再计算L 的列，交替进行；存储时可用紧凑格式。矩阵分解后，解两个三角方程组：LY= b，UX=Y;.i 1y1b1yibilik yki2,3,.nk 1nxi( yiuik xk ) / uiiin, n1,.1k i13、 Crout 分解若 L 为下三角矩阵， U 是单位上三角矩阵，则称Crout 分解；算法特点：先计算L 的列，再计算U 的行，交替进行。4、正定对称矩阵的平方根法（Cholesky 分解）（1） 正定对称矩阵性质与判定：定义：是 n 阶对称矩阵，若对任意非零向量XRn ，有 X T AX0 ，则称 A 为正定对称矩阵；判定： A 为 n 阶正定对

9、称矩阵充要条件A 的各阶顺序主子式大于 0。（ 2） Cholesky 分解定理：设 A 为 n 阶正定对称矩阵，则存在唯一主对角线元素都是正数的下三角阵L，使得 A LLT .Cholesky 分解算法：a11a12.a1nl11ll 11l12.l1na21a22.a2nl 21l 22l 22.l 2n. . . . . . .an1an2.annl n1l n 2 .l nnl nnj 11l jj(a jjl 2jk ) 2k 1j 1l ij( aijl ik l jk ) / l jjk 1j1,2,.n;ij1, j2,.n5、 追赶法三对角矩阵的特殊分解b1c11u1 c1a

10、2b2c2l 2 1u2C2a3b3 c3.l3 1. . .un 1cn-1an 1 bn 1cn 1ln1unanbn;.u1b1l iai / ui 1i 2,3,.nuibil i ci1三对角方程组的追赶法：追的过程LY=Dy1d1yidili yi 1i2,3,.n赶的过程UX=Yxnyn / unxi( yici xi1 ) / uii n 1, n 2,.,1§ 2线性方程组的迭代解法一、 Jacobi 迭代公式例：x11x2122其解为 x1 1, x211x1x2122方程变形得到迭代公式(k 1)1(k )1x12x22给初值 X (0)0计算，观察解的变化。(

11、 k 1)1(k )10x22x12一般地，对线性方程组a11 x1a12 x2.a1n xnb1a21 x1a22 x2.a2n xnb2.an1 x1an2 x2.ann xnbn若 aii0 ，则可从第 i 个方程中解出 xi ,得到 Jacobi 迭代公式：x1( k1)(b1a12 x2(k).a1n xn(k) ) / a11.xi( k 1)(biai1 x1(k ). ain xn(k ) ) / aii.xn(k1)(bnan1x1(k ) .ann xn(k1) ) / ann;.简记为：nxi( k 1)(biaij x j ( k) ) / aiii 1,2,., nj

12、1ji二、 Gauss-Seidel迭代公式i1nxi( k 1)(biaij x j ( k 1)aij x(j k) ) / aiii 1,2,.,nj1j i 1三、 SOR迭代公式四、 迭代公式的矩阵表示X (k1)GX ( k ) D§ 3迭代公式的收敛性一、 向量与矩阵的范数与性质1、 向量范数定义：向量 XRn ，对应非负实数X ，满足三条件：（ 1）非负性（ 2）齐次性（ 3）三角不等式X0,X0,X0kXk XXYXY称 X 为向量范数2、 常见向量范数1 范数X 1x1x2.xn2 范数X 2x12x22.xn2范数Xmaxn xi1i3、 矩阵范数定义：方阵 A

13、Rn n ，对应非负实数A ，满足三条件：（1）非负性A 0,A 0,A0;.（ 2）齐次性（ 3）三角不等式kAk AABAB（4）绝对值不等式ABA B称 A 为矩阵范数；向量范数与矩阵范数相容性：AXAX4、常见矩阵范数n1 范数，列范数：A1maxaij1 j ni 1n范数，行范数：Amaxaij1 i n1j2 范数，谱范数：nnaij2F范数： A Fi 1j1举例计算二、 迭代公式收敛性的判定1、 向量的极限2、 矩阵的谱半径：( A)max ii为特征值；1 in3、收敛性的判定收敛的充要条件：迭代公式X (k 1)GX ( k )D 收敛的充要条件为谱半径(G ) 1。判定

14、定理1：若 G1, 则迭代公式 X (k 1)GX ( k )D 收敛。判定定理2：若对方程AX=b 的系数矩阵 A 为对角占优，则Jacobi 迭代公式， Gauss-Seidel迭代公式收敛；判定定理3：若对方程AX=b 的系数矩阵 A 为对称正定，则Gauss-Seidel迭代公式收敛；Jacobi 迭代公式收敛与Gauss-Seidel迭代公式收敛关系举例：;.第三章非线性方程的数值解法1了解二分法的原理与算法；2掌握一般迭代法的基本思想及其收敛性判定；3掌握 Newton 切线法、弦截法，并用它们求方程近似根的方法。本章问题：求方程f(x)=0 的根§1二分法一、根的存在性

15、定理：函数f(x) 在区间 a， b连续，且f(a).f(b)<0, 则方程 f(x)=0 在区间 a， b有根。方程的根存在，不一定唯一，若在区间a， b上有唯一根，称区间a， b为根隔离区间。二、二分法（区间逐次分半法）原理：通过计算根隔离区间中点，将区间分半，缩小区间，得到方程近似根数列 x n 。a, ba1 ,b1.an ,bn.bkak(ba) / 2k取x*(anbn ) / 2§2迭代法一、迭代原理迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。方程 f(x)=0 变形为 x( x) ，得到递推公式 xk 1(xk ) -简单迭代公式称

16、 ( x) 为迭代函数给初值计算，得到数列 x n ，若lim xkx* ，则称迭代收敛，否则发散。k例：求方程 10xx 2 0x*0.3,0.4写出两个简单迭代公式：;.（1） xk 110xk2（ 2） xk 1lg( xk2)观察计算得到数列 x n 的收敛性。迭代法的几何解释：二、迭代收敛性判定收敛性定理：设方程x(x) 的迭代函数( x) 在 a， b满足：（1）当 x a,b 时，(x)a,b ；（2） ( x) 在 a， b可导，且( x)L1 ， x a, b ，则（ 1）方程 x(x) 在 a， b有唯一根 x*；（ 2）迭代公式 xk 1( xk ) 收敛，即 lim x

17、kx* ；k（ 3）误差估计x*xkLkx1x0 。1L说明可根据迭代函数( x) 的导数判断迭代收敛性。三、迭代公式的加速§ 3Newton迭代法一、 Newton 切线公式几何作法迭代公式f ( xk )xk 1xkf ' (xk )例：利用解二次方程x 2c0, 推导近似计算c 的公式。由 Newton 切线公式xk 11 (xkc )2xk三、 Newton 弦截公式Newton 切线公式的缺点及改进几何作法迭代公式;.xk 1f ( xk )xk( xk xk 1 )f ( xk )f (xk 1 )Newton 弦截公式是两步公式。第五章插值法1. 掌握代数插值问

18、题及其解存在唯一性， Lagrange插值多项式构造及其余项，插值基函数性质；2. 掌握差商的概念及其性质， Newton 插值多项式构造， 两种插值法之间的区别与联系；3了解差分与等距节点插值多项式公式；4. 掌握 Hermite 插值问题及其构造方法。本章问题：函数f ( x) 复杂，或无表达式，构造简单函数P(x) 来代替 f (x) 。§ 1 Lagrange插值一、代数插值问题及插值多项式存在唯一条件1、代数插值问题：已知 f( x) 在区间 a,b 中互异的n+1 个点 x0 , x1, ., xn 的函数值 y0 , y1 ,., yn ，求次数n 次多项式Pn (x)

19、a0a1 x .an xn 且满足 Pn ( xi )f (xi ) yi ，（i=0,1,n）.2、插值多项式存在唯一条件：定理： P ( x)a0a x.anxn 存在唯一条件是 n+1 个节点互异。n1二、 Lagrange插值构造1、线形插值（ n=1）几何解释；利用插值基函数构造：基函数：一次多项式l 0 ( x),l1 (x) 满足l 0 ( x0 ) 1l1 ( x0 )0l0 ( x1 ) 0l1 (x1 ) 1;.xx1xx0l 0 ( x)x1l1 ( x)x0x0x1L1 (x) y0 l0 ( x)y1l1 (x) -1 次 Lagrange插值多项式例 1：求 f (

20、 x)x 过点（ 4， 2），（9， 3）的 1 次 Lagrange 插值多项式，并计算5 近似值。2、抛物插值（ n=2）几何解释；利用插值基函数构造：基函数：二次多项式l 0 ( x),l1 ( x),l 2 (x) 满足l 0 ( x0 )1l1 ( x0 )0l 0 ( x1 )0l1 ( x1 )1l0 ( x2 )0l1 (x2 )0l 0( xx1 )( xx2 )( x)x1 )( x0x2 )(x0l 2( xx0 )( xx1 )( x)x0 )( x2x1 )(x2l 2 (x0 )0l 2 (x1 )0l 2 (x2 )1l 1( xx0 )( xx2 )( x)x0

21、 )( x1x2 )( x1L1 (x)y0 l0 ( x)y1l1 (x)y2 l 2 (x) -2 次 Lagrange插值多项式例 2：求 f ( x)x 过点（ 1， 1），（4， 2），（9， 3）的 2 次 Lagrange 插值多项式，并计算5 近似值。3、一般情形：利用插值基函数构造：基函数： n 次多项式 l 0 ( x),l1 (x),.l n (x) 满足l i ( x j )1ijij0ijl k ( x)( xx0 )( xx1 ).( xxk 1 )( xxk 1 ).( xxn )(xkx0 )( xkx1 ).( xkxk 1 )( xkxk 1 ).( xkx

22、n )nLn (x)y0 l0 ( x)y1l1 (x) .ynl n ( x)k 0yk l k (x)-n 次 Lagrange 插值多项式三、插值余项定理：若f( n)(n1)(x)在 a,b存在 ， 则插值误差( x)在 a, b连续 ，f;.Rn (x)f (n 1)( )f (x) Ln ( x)( x) ，(n1)!其中 a,b依赖于 x 。§ 2分段插值一、分段线性插值在区间 a，b，分为 n 个区间 xi , xi 1 ,i=0,1,2n-1每个区间由直线代替曲线，形成分段线性插值函数(x)( x)l i ( x) yil i 1 (x) yi 1x xi , xi

23、 1 l i ( x)x xi 1， li 1 ( x)x xixixi 1xi 1xi二、分段抛物插值§3Newton插值一、差商及其性质定义：一阶差商： f xi , xi 1f ( xi 1 )f ( xi )xixi 1f xi 1 , xi 2 f xi , xi 1 二阶差商： f xi , xi 1, xi 2 xi 2xiK 阶差商： f xi , xi 1 ,., xi k f xi 1 , xi2 ,., xi k f xi , xi 1 ,.xi k 1 xi kxi性质：（ 1）差商可由节点函数值表示；（ 2）差商值与节点次序无关。二、 Newton 插值多项

24、式由差商定义f ( x)f ( x0 )f x0 , x( xx0 )f x0 , xf x0 , x1 f x0 , x1 , x( xx1 )f x0 , x1 , xf x0 , x1 , x2 f x0 , x1, x2 , x( xx2 )。f x0 , x1 ,.xn 1 , xf x0 , x1 ,.xn f x0 , x1 ,.xn , x( xxn );.依次带入N n ( x)f ( x0 )f x0 , x1 ( xx0 ).f x0 , x1 ,.xn ( xx0 ).( xxn 1 ) - Newton 插值多项式计算时先造差商表；三、余项f (n 1) ()f x0

25、 , x1 ,.xn , x(n1)!§4差分与等距节点插值多项式一、差分及其性质：二、等距节点插值多项式§ 5 Hermite 插值一、带导数的插值多项式1、问题：求次数不超过3次多项式H 3 ( x), 满足 H 3 (x0 )y0 , H 3 ( x1 )y1 , H 3' ( x0 ) m0 , H 3' (x1 )m1 ；2、利用基函数构造H 3 ( x)0 (x) y01 ( x) y10 (x)m01 ( x) m10 (x)(1 2x x0 )(x x1 ) 2x0x1x0x11 (x) (1 2xx1 )( x x0 ) 2x1x0x1x0

26、0 (x)(x x0 )(xx1 ) 2x0x11 (x)(x x1 )(xx0 ) 2x1x0二、一般情形1、问题：求次数不超过2n+1 次多项式 H 2n1 ( x), 满足 H 2 n1 (xi )yi , H 2'n1 (xi )mi ,i0,1,.n;2、利用基函数构造见教材;.第七章数值微积分1. 了解数值求积基本思想；2. 掌握 Newton-Cotes 公式（梯形公式， Simpson 公式，Cotes 公式）推导及误差；3. 了解 Romberg 求积公式原理；4了解数值微分的方法。本章问题：数值积分问题b求定积分f ( x)dxF (b)F (a)a不能使用微积分公

27、式情形存在问题：（ 1）f(x)表达式复杂，原函数更复杂；（ 2）f(x)表达式不复杂，但原函数复杂；（ 3）原函数不存在；（ 3）f(x)无表达式§ 1 Newton-Cotes 公式一、 数值求积基本思想1、 不利用原函数，直接利用函数值b积分中值定理：f ( x)dx(ba) f ( )af ( ) 为平均高度；bn机械求积方法： If ( x)dxAi f ( xi )ai 0xi 为求积节点；Ai 为求积系数。2、 几个简单求积公式左矩形公式右矩形公式Ib(b a) f ( a)f (x)dxaIb(b a) f (b)f ( x)dxa;.中矩形公式 Ib(ba) f (

28、 ab )f ( x)dx2abab( )()梯形公式f (x)dxfafbI2a二、 Newton-Cotes 公式1、公式推导由 Lagrange 插值多项式 Ln (x) 代替函数 f(x)bbbnIf (x)dxLn ( x)dxl i ( x) f ( xi )dxaaai 0b.nb(l i ( x)dx) f ( xi )ai0记 Ail i ( x)dxabnAi f ( xi )则 If ( x)dxa0i求积系数 Ai 的计算：b a( 1)n innAini!( n i )!0 j0ji(ti ) dt (b a)Ci( n) -(ij )Ci( n) 为 Cotes 系

29、数；bnnAi f ( xi )(b a) C i( n ) f ( xi ) - Newton-Cotes 求积公式If (x)dxai 0i 02、 Cotes 系数性质对称性： Ci( n)C n(n i)n权性：Ci(n )1i 03、常用公式n=1bba()()If ( x)dxff梯形公式：a2n=2Simpson,抛物公式： Ibbaabf ( x) dx( f (a) 4 f () f (b)a62n=4Cotes 公式： Ibba (7 f ( x0 )32 f ( x1 )12 f ( x2 ) 32 f ( x3 ) 7 f ( x4 )f ( x)dxa90baxiai

30、4;.4 误差估计：见教材举例说明。§2Romberg求积公式一、复化梯形公式将积分区间 a,b， n 等份，步长hbanh f (a) 2n 1Tnf (xi ) f (b)2i 1误差估计：二、梯形公式递推化T2 n1 Tn h22n 1f (x 1 )i 0i2三、 Romberg求积公式由梯形公式修正，提高精度Sn4 T2n1 Tn3316 1Cn15 S2n 15 SnRn64 C2n1 Cn6363§ 3Gauss型求积公式一、代数精确度bn定义：若求积公式If ( x)dxAi f ( xi ) 对任意 m 次代数多项式精确成立，而对m+1 次代数ai 0多项

31、式不精确成立，称求积公式具有m 次代数精确度。判定 ：求 积公 式 具有 m 次 代数 精确 度求 积公 式对 f ( x)1, x, x 2 ,., x m 精确 成 立； 而对f (x) x m 1不精确成立。例：梯形公式具有1 次代数精确度；定理 1：n+1 个节点的插值型求积公式代数精确度至少为n；定理 2；Newton-Cotes 公式代数精确度至少为 n；当 n 为偶数时，可达n+1 次代数精确度。二、 Gauss 型求积公式bn定义：若 n+1 个节点求积公式 If ( x) dxAi f ( xi ) 具有 2n+1 次代数精确度，则称为 Gauss 型ai 0;.求积公式，节

32、点为Gauss 点。Gauss 点的特性：见教材第八章常微分方程数值解1. 掌握 Euler 方法（ Euler 公式，梯形公式， Euler 预估 -校正公式），局部截断误差，公式的阶；2. 了解 Runge-Kutta 方法的基本思想及四阶经典 Runge-Kutta 公式；3. 掌握线性多步方法的原理与公式推导。本章问题：一阶常微分方程初值问题dyf (x, y)dxy( x0 )y0解的存在性定理：解析解的概念数值解的概念§ 1 Euler 方法一、 Euler 公式导数离散化y' (xn )f ( xn , y( xn )由向前差商代替导数y' (xn )y( xn 1 ) y( xn )h得y( xn 1 )y( xn ) hf ( xn , y( xn )记为 yn1yn hf (xn , yn ) - Euler 显式公式由向后差商代替导数y' (xn 1 )y( xn 1 ) y(xn )h得y( xn 1 )y( xn ) hf ( xn 1 , y(xn 1 )记为 yn1yn