数值计算方法复习提纲

1、数值计算方法复习提纲第一章数值计算中的误差分析1 了解误差及其主要来源，误差估计;2 了解误差(绝对误差、相对误差)和有效数字的概念及其关系;3 掌握算法及其稳定性，设计算法遵循的原则。1、误差的来源模型误差观测误差截断误差舍入误差2误差与有效数字绝对误差E (x) =x-x绝对误差限XXX相对误差Er (X) (X X*)/X (X X*)/X*有效数字x0.a1a2.an 10m*Im n*若x X -10 ，称X有n位有效数字。2有效数字与误差关系(1)m 一定时，有效数字n越多，绝对误差限越小;(2)X有n位有效数字，则相对误差限为Er(X)12a110(n 1)选择算法应遵循的原则1

2、、选用数值稳定的算法，控制误差传播;例1 n11 n x .x e dxe 0In 1n 1 n 11011eXnn!叫1厂严脈二-列严-巴知“严aa j2、简化计算步骤，减少运算次数；3、避免两个相近数相减，和接近零的数作分母;避免第二章线性方程组的数值解法1 了解Gauss消元法、主元消元法基本思想及算法；2 掌握矩阵的三角分解，并利用三角分解求解方程组；（Doolittle 分解；Crout分解；Cholesky 分解；追赶法）3 .掌握迭代法的基本思想，Jacobi迭代法与Gauss-Seidel迭代法;4 .掌握向量与矩阵的范数及其性质，迭代法的收敛性及其判定。本章主要解决线性方程组

3、求解问题，假设n行n列线性方程组有唯一解，如何得到其解？a1 Xax?a1nXnb1a?1 xa?2 X2.a2n Xnb2an 1X1an2X2.annXnbn两类方法，第一是直接解法，得到其精确解；第二是迭代解法，得到其近似解。Gauss消去法 1、顺序G auss消去法记方程组为:(1)a；1 X1(1)a?1 X(1) a2 X2(1) a?2 X2a1(?Xna2n Xnbby(1)an1 X1(1)an2 X2(1)ann Xnbn1)a22)X2b1(1)b22)消元过程: 经n-1步消元，化为上三角方程组小(1)a1 X1(2) a 21 X1an；）X1an；）X2ann)x

4、nbnn)若 akk)0(k)Jk 1)3aikJk)aijaijakk)akj回代过程:b(k 1)(k)b(k)爲匕律akkk1,.n1 i, j k1,., nXi(n)(n)bn / ann(i)Xn(iin 1, n 2,.1)2、G auss Jordan 消去法避免回代，消元时上下同时消元3、G auss列主元消去法例：说明直接消元，岀现错误0.00001x1X12x22x23由顺序G auss消去法，得X21,X10 ;G auss列主元消去法原理： 每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵A Mbaij表示。n(n 1)(1)消元过程:对 k=1,2,n-1.

5、选主元，找ik k,k 1,n使得a,k max ak如果aik,k 0，则矩阵a奇异，程序结束；否则执行 3如果ik k，则交换第k行与第ik行对应的元素位置，akjaikj,j k,ggg n 1.消元，对i=k+1, L ,n,计算 likL ,n+1,计算aij aij lik akj(2)回代过程: 1 若ann 0,则矩阵a奇异，程序结束；否则执行Xi,2,1,计算举例说明。4、消元法应用(1 )行列式计算;(2 )矩阵求逆二、利用矩阵三角分解求解线性方程组1、求解原理线性方程组写成矩阵形式为：AX=b若 A=LU，贝U LUX= b，记 UX=Y则 LY= b若L、U为特殊矩阵，

6、则求解线性方程组变为解两个特殊线性方程组问题。2、Doolittle 分解L为下三角矩阵，U为上三角矩阵，不一定能分解，分解也不一定唯一；设L或U是单位三角矩阵，若能分解，则可分解唯一.L是单位下三角矩阵，称为Doolittle 分解；U是单位上三角矩阵，称为Crout分解；定理：n阶矩阵A有唯一分解的充要条件为A的前n-1阶主子式都不为0.Doolittle分解算法:a11a12 .a1n1U11 U12 .U1 na21a22 .a2nl211U22 .U2nan1an2.annl n1l n2.1Unn由矩阵乘法：naijlikUkjk 1得到：k 1Ukjakjl krUrjjr 1k

7、, k 1,.n;k 1l ik(aiklirUrk ) /Ukki k,k 1,.nr 1算法特点：先计算U的行，再计算L的列，交替进行；存储时可用紧凑格式。矩阵分解后，解两个三角方程组：LY= b，UX=Yyibii 1yibi hyki 2,3,.nk 1nXi(yiUikXk)/Uiii n,n 1,1k i 13、Crout 分解若L为下三角矩阵，U是单位上三角矩阵，则称 Crout分解；算法特点：先计算L的列，再计算U的行，交替进行。4、正定对称矩阵的平方根法(Cholesky分解)(1)正定对称矩阵性质与判定：定义：是n阶对称矩阵，若对任意非零向量XRn，有XT AX 0 ,则称

8、A为正定对称矩阵;判定：A为n阶正定对称矩阵充要条件 A的各阶顺序主子式大于 0。(2) Cholesky 分解定理：设A为n阶正定对称矩阵，则存在唯一主对角线元素都是正数的下三角阵L,使得A LLT.a11a12 .a1nl11a21a22 .a2nl 21l22Cholesky分解算法:ll 11 l121nl22. l2nan1 an2annl n1ln2l nnl nnj 11ljj (ajj l2k)2k 1j 1l ij (aijl ik l jk ) / l jjk 1j1,2,n;i j 1,j2,.n5、追赶法三对角矩阵的特殊分解b|c1a2 b2C2a3b3C3an 1bn

9、 1cn 1anbnXiXn(yi Ci Xi 1)/Uiyn / Un1 u1c11 21U2C2I31. un 1 Cn-1In 1Unu1b1li ai /ui 1 i2,3,.nUi b1 ici 1三对角方程组的追赶法: 追的过程LY=D% d1yidili yi 1 i2,3,.n赶的过程UX=Y2线性方程组的迭代解法例：11X1 x22211X1x222Jacobi迭代公式其解为 X11, X2方程变形得到迭代公式(k 1)1(k)1X1X2022给初值X(O)计算，观察解的变化。x2k 1)1 v(k)10X122一般地，对线性方程组a1 X1&12X2a1nXnb1821X1

10、&22X2a2nXnb2an1 X1an2 x2ann xn若an0,则可从第i个方程中解出Xi,得到Jacobi迭代公式:x；k 1) (ba12x2k)amxnk)/aii(k 1) x( 1(bi(k) aiixainxn ) /aii(kxni)(bn(k)(k) 、 /an1 xi . annxn 1 ) / ann简记为：n(k 1)(k)、斤)(biajXj )/aHi 1,2,.,nj ij iGauss-Seldel 迭代公式xi(k1)(bii 1(k 1)aij Xjj 1jnaij xj ) / aiii 1三、SOR迭代公式四、迭代公式的矩阵表示X(k 1) GX (

11、k) D3 迭代公式的收敛性一、向量与矩阵的范数与性质1、向量范数定义：向量XRn，对应非负实数|x|，满足三条件:（1） 非负性| X0, X O,|x 0（2） 齐次性|kX|k|x|（3）三角不等式 l|X Y|X|Y|称 |X| 为向量范数2、常见向量范数1 范数|xhx1x2.xn2 范数X 2: X；X；.X；a范数 | XmaxXiI n3、矩阵范数定义：方阵A R n ,对应非负实数 A，满足三条件:(1) 非负性| A 0, A 0,制 0(2) 齐次性 |k|k|A(3)三角不等式A B A |B(4)绝对值不等式AB A B称| A为矩阵范数;向量范数与矩阵范数相容性：|

12、 AX AX4、常见矩阵范数n1范数，列范数：| A1 max aIjj n I 18范数，行范数max1 I n jaij2范数，谱范数 ：n nF 范数：IIAIfJa2V I 1 j 1举例计算迭代公式收敛性的判定1、向量的极限2、矩阵的谱半径：(A) max Ii为特征值；3、收敛性的判定收敛的充要条件：迭代公式X (k 1)GX (k) D收敛的充要条件为谱半径判定定理1 :若IG 1,则迭代公式X (k 1) GX (k) D收敛。判定定理2 :(G)1。若对方程AX=b的系数矩阵A为对角占优，则Jacobi迭代公式，Gauss-Seidel迭代公式收敛;判定定理3 :若对方程AX

13、=b的系数矩阵A为对称正定，则 Gauss-Seidel迭代公式收敛；Jacobi迭代公式收敛与Gauss-Seidel迭代公式收敛关系举例：第三章非线性方程的数值解法1 了解二分法的原理与算法；2 .掌握一般迭代法的基本思想及其收敛性判定；3 .掌握Newt on切线法、弦截法，并用它们求方程近似根的方法。本章问题：求方程f(x)=0的根 二分法一、根的存在性定理：函数f(x)在区间a，b连续，且f(a).f(b)0,则方程f(x)=0在区间a，b有根。方程的根存在，不一定唯一，若在区间a，b上有唯一根，称区间a，b为根隔离区间。二、二分法(区间逐次分半法)原理：通过计算根隔离区间中点，将区

14、间分半，缩小区间，得到方程近似根数列Xn。ka,b ai ,bi.an,bn. bk ak （b a）/2取 x （an bn ）/2迭代法一、迭代原理迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。方程f（x）=0变形为x （X），得到递推公式Xk 1 （Xk）简单迭代公式称（X）为迭代函数给初值计算，得到数列Xn，若 lim Xk X*，则称迭代收敛，否则发散。K1例：X*求方程 10 X 20 X 0.3,0.4写出两个简单迭代公式：（1）Xk 1 10Xk 2（2）Xk 1lg（Xk2）观察计算得到数列Xn的收敛性。迭代法的几何解释：二、迭代收敛性判定收敛性定

15、理：设方程 X （X）的迭代函数 （X）在a，b满足：（1 ）当 X a,b时，（x）a,b；(2)(x)在a, b可导，且(x) L 1, x a,b,则(1)方程x (x)在a , b有唯一根x ;（2 ）迭代公式Xk 1(Xk)收敛，即 |jm Xk x ；（3 ）误差估计XLkXk X1Xg。1 L说明可根据迭代函数（x）的导数判断迭代收敛性。三、迭代公式的加速3 Newt on 迭代法Newt on 切线公式 几何作法迭代公式Xk 1 Xkf(Xk)f(Xk)例：利用解二次方程x2 c 0,推导近似计算.c的公式。由Newton 切线公式 Xk 1cXk三、Newt on 弦截公式N

16、ewt on切线公式的缺点及改进几何作法迭代公式Xk 1 Xkf (Xk)f(Xk) f(Xk 1)(XkXk 1)Newton 弦截公式是两步公式。第五章插值法1. 掌握代数插值问题及其解存在唯一性，Lagrange插值多项式构造及其余项， 插值基函数性质；2. 掌握差商的概念及其性质，Newt on插值多项式构造，两种插值法之间的区 别与联系；3 了解差分与等距节点插值多项式公式；4.掌握Hermite插值问题及其构造方法。本章问题：函数 f(x)复杂，或无表达式，构造简单函数P(x)来代替f(X)。 Lagrange 插值一、代数插值问题及插值多项式存在唯一条件1、代数插值问题：已知f

17、(x)在区间a,b中互异的n+1个点X0, X1, , Xn的函数值y0, y1,., yn，求次数 n次多项 式 Pn (x)a.anXn且满足Pn(xi)f (xi)yi，(i=0,1,n).2、插值多项式存在唯一条件：定理：Pn(x) a0 a1x . anxn存在唯一条件是n+1个节点互异。二、Lagrange 插值构造1、线形插值(n=1 )几何解释；l1 (X)满足利用插值基函数构造：基函数：一次多项式 l0(X),1o(Xo)ili (xo) olo ( xi)oli(Xi)ilo(x)XXiXXoli(x)XoXiXiXoLi(x)yo lo(X)yili(x)-1次Lagra

18、nge 插值多项式例i :求f (X)、X过点(4，2)，( 9，3)的i次Lagrange 插值多项式,2、抛物插值(n=2)几何解释;利用插值基函数构造:基函数：二次多项式lo(x),li (x),l2 (x)满足并计算. 5近似值。lo(Xo)ili (Xo)olo (xi)oli (Xi)ilo ( X2 )oli (X2)olo(x)(xX-I )(x X2)(XoXi )(XoX2)Li(x)yol o(X) yili(x)例2 :求f(x)X过点(i，3、一般情形：利用插值基函数构造：基函数：1n次多项式l o(X),li(Xj)iji i o ij jlk(x)(x Xo)(X

19、Xi)(XkXo )(XkXi).(xo)I 2 (xi)I 2 (x2)(xXo)(X x2)li(x)(XiXo)(Xi X2)y22(x)2次 LagrangeLn(X)I2(X) (X SX Xi)(X2 Xo)(X2 Xi)插值多项式1), (4 , 2), (9 , 3)的2次Lagrange插值多项式，并计算J5近似值。li(x),. ln(x)满足(XXki)(XXki)(XXn) (XkXk i)(XkXk i).(Xk Xn)yolo(x)yili(x) . yn(x)nyk(x)k 0n 次Lagrange 插值多项式三、插值余项f(n)(x)在a,b连续，fni)(x)

20、在a,b存在，则 插 值误差Rn(X)f(X)Ln(X):(n 1)()(TV (x)，其中a,b 依赖于x。分段插值一、分段线性插值在区间a, b，分为n个区间Xj,Xj訂，i=0,1,2n-1每个区间由直线代替曲线，形成分段线性插值函数(X)(X) li(x)yi li1(x)yi 1X Xi ,Xi1X Xi 1 li(x)li i(x)XxiXiXi 1Xi 1Xi二、分段抛物插值3一、差商及其性质定义：Newton插值一阶差商:fXi ,Xif (Xi 1) f (Xi)1Xi 1Xi二阶差商:fXi ,Xi1,Xi2込3fXi,Xi 1Xi 2XiK阶差商:fXi ,Xi1,，xi

21、 kf Xi 1,Xi 2,，Xi k fXi,Xi 1,Xi k 1Xi kXi性质：（1）差商可由节点函数值表示;（2）差商值与节点次序无关。二、Newton 插值多项式由差商定义f (X) f (X0) f X0, x(xX0)fx,x fX0,X fX,X1,X(X X1)fX,X1,X fX,X1,X2 fX,X1,X2,X(X X2)fX0,X1,.Xn 1,xf X0,X1,.Xnf【X。，捲，.X. , X( X X.)依次带入Nn(x) f(Xo)fXo,Xi(X Xo) . fXo, Xi,.Xn(X X).(X X. 1) Newton插值多项式计算时先造差商表；三、余项

22、fX,Xi，Xn,X(n 1)(n 1)!4 差分与等距节点插值多项式一、差分及其性质：二、等距节点插值多项式5 Hermite 插值一、带导数的插值多项式1、 问 题： 求 次 数 不 超 过 3 次 多 项 式IIHa（x）,满足 H3（Xo）yo,H3（xJ y1,H3（Xo） m,H3（X1）mn ；2、利用基函数构造H3(x)o(x)y1&)力o(x)m1(x)m)10(x)(1Xo X1 Xo X11(x)(1X1X1X0)(X1生)2X0X X-I 20(x) (X Xo)(-)XoX1X Xo 21(X) (X X1)(-)XI Xo二、一般情形2n+11、 问 题H2n1(x

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

24、用函数值积分中值定理：ba f(x)dx (b a)f()f()为平均高度;bn机械求积方法：If (x)dxAi f (xi)ai 0Xj为求积节点；Ai为求积系数2、几个简单求积公式左矩形公式1ba f (x)dx(ba) f (a)右矩形公式1bf (x)dx a(ba)f(b)中矩形公式1bf(x)dx a(ba b、a)f( 2 )梯形公式1bf(x)dxab a2(f(a)f(b)二、Newton-Cotes 公式1、公式推导由Lagrange插值多项式Ln(x)代替函数f(x)f(x)dx abLn(x)dxb nli(x) f (xjdx ai 0n b(a h(x)dx) f

25、 (xji 0ba li (x)dxba f(x)dxA f (xj求积系数A的计算:Ci(n)为 Cotes(1)nii!(n i)!n g j 0 (i j i(b a)C(n)系数;bnI f (x)dxAi f (xi)ai 0(ba)nCi(n) f (xi )Newton-Cotes 求积公式i 02、Cotes系数性质对称性：Ci(n)(n) C n in权性：c,n)1i 03、常用公式n=1bb a梯形公式：| f(x)dx(f(a) f (b)a 2n=2bb aa bSimpson,抛物公式：I g f (x)dx( f (a)4 f () f (b)n=4bb aCot

26、es公式： I f(x)dx (7f(x。)32f(xj 12f(X2)32f (xa) 7f(X4) a90.b axia i -44误差估计：见教材举例说明。 Romberg求积公式、复化梯形公式将积分区间a,b，n等份，步长hhn 1Tn -f(a) 2 f (xi)f(b)2i i误差估计：二、梯形公式递推化2i三、Romberg由梯形公式修正,f(xiil)2求积公式41T2n-T33161S2n1515641C2n6363提高精度SnRnCnSnCn3Gauss型求积公式、代数精确度定义：若求积公式Iba f(x)dxnAi f (xi )对任意wm次代数多项式精确成立，而对m+1

27、次代数多项式不精确成立，称求积公式具有m次代数精确度。判定：求积公式具有m次代数精确度 求积公式对f(x) 1,X,X2,.,xm精确成立；而对m 1f (x) X不精确成立。例：梯形公式具有1次代数精确度；定理1 : n+1个节点的插值型求积公式代数精确度至少为n ;定理2 ； Newton-Cotes 公式代数精确度至少为 n ；当n为偶数时，可达n+1次代数精确度。二、Gauss型求积公式定义：若n+1个节点求积公式If(x)dxA f (Xj 具有 2n+1i 0次代数精确度，则称为Gauss型求积公式，节点为 Gauss点Gauss点的特性：见教材第八章常微分方程数值解1. 掌握Eu

28、ler方法(Euler公式，梯形公式，Euler预估-校正公式)，局部截断误差，公式的阶；2. 了解Runge-Kutta方法的基本思想及四阶经典 Runge-Kutta公式；3. 掌握线性多步方法的原理与公式推导。本章问题：一阶常微分方程初值问题dy f (x, y)dxy(x) y。解的存在性定理：解析解的概念数值解的概念 Euler方法一、Euler 公式导数离散化y(Xn) f (Xn, y(Xn)由向前差商代替导数,、y(Xn 1) y(Xn)y (Xn)h得y(Xn 1)y(Xn) hf(Xn,y(Xn)记为 yn 1 yn hf(Xn,yn)Euler 显式公式y (Xn 1)得y(Xn 1)记为y n 1二、Euler梯形公式y(X