数值计算方法复习提纲

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

2、x)110 (n 1) 。2a1选择算法应遵循的原则1、 选用数值稳定的算法，控制误差传播；例 I n11nxexe dx01I n1nI n 1I 0 1e xnn! x 02、 简化计算步骤，减少运算次数；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( n1) xnb1(1)a21(1) x1a22(1) x2. a2(1n) xnb2(1).an(11) x1an(12) x2. ann(1) xnbn(1)消元过程：经步消元，化为上三角方程组a11

4、(1) 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 列主元消去法原理：每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵AMbaij表示。n( n 1)（1）消元过程：对 k=1,2,n-1,选主元，找 i k k, k1, 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,计算akkaij

6、aij l ik akj（2）回代过程：1若 ann0, 则矩阵 A 奇异，程序结束；否则执行。an,n1; 对in 1,L ,2,1,计算2 xnannai, n 1naij xjj ixi1aii.举例说明。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 u rjjk, k1,.n;r1k1l ik( aikl ir u rk ) / ukkik, k1,.n

8、r1算法特点：先计算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 c

10、1a2b2c2l 2 1u2 C2a3b3 c3.l 3 1. . .un 1cn-1an 1 bn 1cn 1ln1unanbn.u1b1l iai / ui 1i 2,3,.nuibil i ci1三对角方程组的追赶法：追的过程LY=Dy1d1yidil i yi 1i2,3,.n赶的过程UX=Yxnyn / unxi( yici xi1 ) / uii n 1, n 2,.,1 2 线性方程组的迭代解法一、 Jacobi 迭代公式例：x11 x2122其解为x1 1, x211 x1x2122方程变形得到迭代公式x1( k 1)1 x2(k )2x2(k 1)1 x1( k )2一般地，

11、对线性方程组12给初值 X ( 0)0计算，观察解的变化。102a11 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)(biai1x1(k ). ain xn(k ) ) / aii.xn(k1)(bnan1 x1(k ) .ann xn(k1) ) / ann.简记为：nxi( k 1)(biaij x j ( k) ) / aiii 1,2,.,

12、 nj1ji二、 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、 矩阵范数定义：方阵 AR

13、n n ，对应非负实数A ，满足三条件：（1）非负性A 0,A 0, A0.（ 2）齐次性（ 3）三角不等式kAk AABAB（4）绝对值不等式ABA B称A 为矩阵范数；向量范数与矩阵范数相容性：AXA X4、常见矩阵范数n1 范数，列范数： A 1maxaij1 j ni 1n范数，行范数：Amaxaij1 in1j2 范数，谱范数：nnaij2F 范数： A Fi1 j1举例计算二、 迭代公式收敛性的判定1、 向量的极限2、 矩阵的谱半径：( A)max ii 为特征值；1 i n3、收敛性的判定收敛的充要条件：迭代公式 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) / 2 k取x*( anbn ) / 22迭代法一、迭代原理迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。方程 f(x)=0 变形为 x( x) ，得到递推公式xk 1(xk ) -简单迭代公式称 ( x) 为

16、迭代函数给初值计算，得到数列 x n ，若lim xkx* ，则称迭代收敛，否则发散。k例：求方程 10xx 2 0x*0.3,0.4写出两个简单迭代公式：.（1） xk 110 xk2（ 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 xkx* ；k（

17、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. 掌握代数插值问题及其解存在唯一性， Lagrange插值

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

19、)yi ，（ i=0,1,n）.2、插 多 式存在唯一条件：定理： Pn ( x)a0 a1 x.an xn 存在唯一条件是n+1 个 点互异。二、 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 ( x)x 过点（ 4，2），（9，3）的 1 次 Lagrange

20、 插值多项式，并计算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 ( x)( xx1 )( xx2 )( x0x1 )( x0x2 )l 2 ( x)( xx0 )( xx1 )(x2x0 )( x2x1 )l 2( x0 )0l2( x1 )0l 2 (x2 )1l 1( xx0 )( xx2 )( x)x0 )( x1x2 )( x1L1 (x) y0 l0 ( x)

21、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), .ln (x) 满足l i ( x j )1ijij0ijl k ( x)( xx0 )( xx1 ).( xxk 1 )( xxk 1 ).( xxn )(xkx0 )( xkx1 ).( xkxk 1 )( xkxk 1 ).( xkxn )nLn (x)y0 l0 ( x)y1l1 (x) .

22、ynl n (x)k 0yk lk (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 1 l i ( x)x xi 1， li 1 (x)x xixixi 1xi 1x

23、i二、分段抛物插 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 ,., xik f xi , xi 1 ,.xi k 1 xixik性 ：（1）差商可由 点函数 表示；（2）差商 与 点次序无关。二、 Newton插 多 式由差商定 f ( x)f ( x0 )f x0 , x( xx0 )f x0 , xf x0 , x1 f

24、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 , x1 ,.xn , x(n1)!4差分与等距节点插值多项式一、差分及其性质：二、等距节点插值多项式 5

25、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 ) 2x1x0x1x00 (x)(x x0 )(xx1 ) 2x0x11 (x)(x x1 )(xx0 )2x1x0二、一般情形1、问题：求次数不超过2n+1 次多项式 H 2

26、n1 ( x), 满足 H 2n1 (xi )yi , H 2n 1 ( xi )mi ,i0,1,.n;2、利用基函数构造见教材.第七章数值微积分1. 了解数值求积基本思想；2. 掌握 Newton -Cotes公式（梯形公式， Simpson 公式， Cotes 公式）推导及误差；3. 了解 Romberg 求积公式原理；4了解数值微分的方法。本章问题：数值积分问题b求定积分f ( x) dxF (b)F (a)a不能使用微积分公式情形存在问题：（ 1）f(x)表达式复杂，原函数更复杂；（ 2）f(x)表达式不复杂，但原函数复杂；（ 3）原函数不存在；（ 3）f(x)无表达式 1 Newt

27、on -Cotes 公式一、 数值求积基本思想1、 不利用原函数，直接利用函数值bf ( x)dx(ba) f ()积分中值定理：af ( ) 为平均高度；bn机械求积方法： If ( x)dxAif ( xi )ai 0xi 为求积节点；Ai 为求积系数。2、 几个简单求积公式bf (x)dx(ba) f (a)左矩形公式 Ia.右矩形公式 Ibf ( x)dxa中矩形公式 Ibf ( x)dxa梯形公式 Ibf (x)dxa(ba) f (b)ab(ba) f ()b a ( f ( a) f (b)2二、 Newton -Cotes 公式1、公式推导由 Lagrange 插值多项式 Ln

28、 ( x) 代替函数 f(x)bbbnnbl i ( x) f (xi )dxIf (x)dxLn ( x)dx( li ( x)dx) f (xi )aaa0i 0aib记 Ail i ( x)dxabn则 IAi f (xi )f ( x)dxai 0求积系数 Ai 的计算：b a( 1)n innAii!( n i )! 0 jn0ji(ti ) dt (b a)Ci( n) -(ij)C i( n) 为 Cotes 系数；bnnIAi f (xi )(b a) C i(n ) f ( xi ) - Newton -Cotes 求积公式f (x)dxai 0i 02、 Cotes 系数性

29、质对称性： Ci( n)C n(n i)n(n )权性：Ci13、常用公式n=1Ibf ( x)dxba(f(a)f( )梯形公式：a2n=2baabbIf ( x) dx( f (a)4 f ()f(bSimpson,抛物公式：a62n=4babCotes 公式： If ( x) dx90(7 f( x0 )32f ( x1 )12 f ( x2 )32 f ( x3 ) 7 f ( x4 )a.baxiai4 误差估计：见教材举例说明。42Romberg求积公式一、复化梯形公式ba将积分区间 a,b， n 等份，步长hnh f (a) 2n 1Tnf (xi ) f (b)2i 1误差估计

30、：二、梯形公式递推化T2 n1 Tnh22n 1f ( xi1)i 02三、 Romberg求积公式由梯形公式修正，提高精度4 1Sn3 T2n 3 TnCn16 S2n1 Sn1515Rn64 C2n1Cn63 63 3 Gauss 型求积公式一、代数精确度bn定义：若求积公式If ( x)dxAi f ( xi ) 对任意 m 次代数多项式精确成立，而对m+1 次代数ai 0多项式不精确成立，称求积公式具有m 次代数精确度。判定 ：求 积公 式 具有 m 次 代数 精确 度求 积 公式 对 f ( x)1, x, x 2 ,., x m 精确 成立 ； 而对f (x) x m 1不精确成立

31、。例：梯形公式具有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求积公式，节点为 Gauss 点。Gauss 点的特性：见教材第八章常微分方程数值解1. 掌握 Euler 方法（ Euler 公式，梯形公式， Euler 预估 -校正公式），局部截断误差，公式的阶；2. 了解 Runge-K

32、utta 方法的基本思想及四阶经典 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 )记为 yn 1yn hf (xn , yn ) - Euler 显式公式由向后差商代替导数y (xn 1 )y( xn 1 ) y(xn )h得.y( xn 1 )y( xn ) hf ( xn 1 , y( x