数值计算方法复习提纲

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

2、算法应遵循的原那么 1、选用数值稳定的算法，控制误差传播;例In1xneXdxoInn! x0nI n 11M广右】严山*Ra J Xn2、简化计算步骤，减少运算次数;3、防止两个相近数相减，和接近零的数作分母;防止第二章线性方程组的数值解法1了解Gauss消元法、主元消元法根本思想及算法；2掌握矩阵的三角分解，并利用三角分解求解方程组；Doolittle分解；Crout分解；Cholesky分解；追赶法3. 掌握迭代法的根本思想，Jacobi迭代法与Gauss-Seidel迭代法;4掌握向量与矩阵的范数及其性质，迭代法的收敛性及其判定。本章主要解决线性方程组求解问题，假设n行n列线性方程组有

3、唯一解，如何得到其解?aXax?a1nXnb1a2Xa?2 X2.a2n Xnb2an 1X1an2X2annXnbn两类方法，第一是直接解法，得到其精确解;第二是迭代解法，得到其近似解。Gauss消去法 1、 顺序G auss消去法记方程组为:a1(l)x1ax2b1(1)a21)x1a 22 x2(1) ainXn1n(1)an1 X1(1)an2 X2消元过程:经n-1步消元，化为上三角方程组a1(11X1bi1a22) 3x1a22)(2)2an;.an;%a；x；(n)假设akk)0a(k 1)丿) aijaija(k)aikakk)b(k 1) b(k)(k)kjiiakka(k)

4、£k 1,.n 1akki, j k 1,.,n回代过程：x； bn(n) /annXi(bin(i)(i)aij Xj)/aii(i n1, n 2,.1)j i 10.0000仅1Xi2x22x23由顺序G auss消去法，得x21, X10 ；G auss列主元消去法原理：每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵A：baj表示。j n(n 1)1消元过程：对 k=1,2,n-1,选主元，找ik k,k 1,n使得aik,kmax aikkin如果aik,k0 ,那么矩阵a奇异，程序结束；否那么执行 3。如果ik k，那么交换第k行与第ik行对应的元素位置,akj

5、akj, jk,：n 1.消元，对i=k+1,，n,计算lik,对j=L+1,，n+1,计算aijaijlik akj2丨回代过程：1 假设ann0,那么矩阵A奇异，程序结束；否那么执行2 Xn% 1-;对 i n 1,2,1,计算nnai,n 1j i 1aijJ i 1举例说明。4、消元法应用1行列式计算;2丨矩阵求逆。二、利用矩阵三角分解求解线性方程组1、求解原理线性方程组写成矩阵形式为：AX=b假设 A=LU,那么 LUX= b,记 UX=Y那么 LY= b假设L、U为特殊矩阵，那么求解线性方程组变为解两个特殊线性方程组问题。2、 Doolittle 分解L为下三角矩阵，U为上三角矩阵

6、，不一定能分解，分解也不一定唯一 设L或U是单位三角矩阵，假设能分解，那么可分解唯一.L是单位下三角矩阵，称为Doolittle分解；U是单位上三角矩阵，称为Crout分解；定理：n阶矩阵A有唯一分解的充要条件为A的前n-1阶主子式都不为0.Doolittle 分解算法：a11a12. a1n1a21a22. a2nl21an1an2. annln1由矩阵乘法：naijl k1ikukj得到k1ukjakjl r1kr urjjk1lik(aikr1l irurk )/ukku11 u12 .u1n1u22 . u2nn2 . 1unnk,k 1,.n;i k,k 1,.n算法特点：先计算U

7、的行，再计算L 的列，交替进行；存储时可用紧凑格式。矩阵分解后，解两个三角方程组：LY= b， UX=Yy1 b1i1yi bilik yki 2,3,.nk1nxi (yiuik xk)/uiii n,n 1,.1ki13、 Crout 分解假设 L 为下三角矩阵， U 是单位上三角矩阵，那么称 Crout 分解；算法特点：先计算L的列，再计算U的行，交替进行4、正定对称矩阵的平方根法Cholesky分解1 正定对称矩阵性质与判定：定义：是n阶对称矩阵，假设对任意非零向量X Rn，有XT AX 0，那么称A为正定对称矩阵;判定：A为n阶正定对称矩阵充要条件A的各阶顺序主子式大于 0L,使得

8、A LLt .(2) Cholesky 分解定理：设A为n阶正定对称矩阵，那么存在唯一主对角线元素都是正数的下三角阵Cholesky分解算法：ai1ai2 ainl111111l12 .l1na21 a22.a2nl 21l22l22 .Jnan1an2.annl n1l n2.nnl nnljj(6j 11l2k)2 k 1j 1lij(aijl ik l jk ) / l jj k 1j 1,2,.n;i j 1, j2,. .n5、追赶法三对角矩阵的特殊分解b1c1a2 b2C21U1C1asbsC3l 21ls 1U2C2an 1bn 1Cn 1.un 1Cn-1ln 1Unanbnu

9、1b|l i ai / Uj i i 2,3,.nui bi 1 ici 1三对角方程组的追赶法:追的过程LY=Dyidiy1 d1h % 1 i2,3, .n赶的过程UX=YXnyn / UnXi(yiCi Xi 1)/Uii n 1, n 2,.,1§ 2线性方程组的迭代解法一、Jacobi迭代公式例：1 1Xx222 其解为 X,1, x21111 2X1X222方程变形得到迭代公式0计算，观察解的变化。0(k 1)1(k)X1X22(k 1)1 vkX2X1212 给初值X (0)2一般地，对线性方程组a1 xa2 X2a1n Xnb1a 21X1a 22 X2a2n Xnb

10、2an1X1an2 X2ann Xnbn假设 aii 0 ，那么可从第 i 个方程中解出 xi ,得到 Jacobi 迭代公式：x1(k 1)(b1a12 x(2k)a1n xn(k) )/a11xi(k 1)(bi ai1x1(k )(k) ainxn)/aiixn(k1)(bn(k) (k) an1x1 . ann xn 1)/ann简记为：n(k 1) (k)xi(k 1)(biaij xj )/aiii 1,2,.,nj1jiGauss-Seidel 迭代公式i1xi(k 1)(bi(k 1) aijxjj1aij1x(jk)/aiii 1,2,.,n三、SOR迭代公式四、迭代公式的矩

11、阵表示X (k 1) GX (k) D§3 迭代公式的收敛性向量与矩阵的范数与性质1、向量范数定义：向量X Rn，对应非负实数 X|，满足三条件:1非负性 X 0, X 0, X 02齐次性 kX kX3三角不等式 llX Y IIX IIY称 |X| 为向量范数2、常见向量范数1 范数 |Xh x1 x2. xn2 范数 X 2Xi2 X； . X；.ii max范数|x|Xi1 i n3、矩阵范数定义：方阵A Rn n，对应非负实数| A，满足三条件:1非负性 A 0, A 0, A 02齐次性 | kAk|A|3三角不等式 AB A | B4绝对值不等式 lAB HIIBII称

12、| A为矩阵范数；向量范数与矩阵范数相容性：AX AX4、常见矩阵范数n1范数，列范数： |Ai maxaji 1行范数max1 i n .aij2范数,谱范数n nF范数:2 aiji 1 j 1举例计算二、迭代公式收敛性的判定 1、向量的极限2、矩阵的谱半径:(A) max i i为特征值;3、收敛性的判定收敛的充要条件：迭代公式X (k ° GX (k) D收敛的充要条件为谱半径(G)1。判定定理1:假设G1,那么迭代公式X(k1) GX (k) D收敛。判定定理2 :假设对方程AX=b的系数矩阵A为对角占优，那么Jacobi迭代公式，Gauss-Seidel迭代公式收敛;判定

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

14、二、二分法区间逐次分半法 xn 。原理：通过计算根隔离区间中点，将区间分半，缩小区间，得到方程近似根数列ka,ba1,b1 an,bn .bk ak (b a)/2取 x* (an bn)/2§2 迭代法一、迭代原理 迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。 方程 f(x)=0 变形为 x (x) ，得到递推公式 xk 1(xk) 简单迭代公式称 (x) 为迭代函数给初值计算，得到数列 xn ，假设lim xk x* ，那么称迭代收敛，否那么发散。k例：x*求方程 10x x 2 0 x* 0.3,0.4写出两个简单迭代公式：1 xk 1 10xk

15、22 xk 1 lg(xk 2)观察计算得到数列 xn 的收敛性。迭代法的几何解释：、迭代收敛性判定收敛性定理：设方程 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)收敛，即Ijm xk3误差估计x*XkLkx1x0。1 L说明可根据迭代函数(x)的导数判断迭代收敛性。三、迭代公式的加速§ 3 Newton迭代法一、Newt on切线公式几何作法迭代公式f(Xk)Xk 1 Xk'f (Xk)例：利用解二次方程 X2 c

16、0,推导近似计算.c的公式。1 c由Newton切线公式 xk 1 (xk )2 Xk三、Newt on弦截公式Newt on切线公式的缺点及改进几何作法迭代公式Xk 1Xk空 (Xk f(Xk) f(Xki)Xk 1)Newt on弦截公式是两步公式。第五章 插值法1. 掌握代数插值问题及其解存在唯一性，Lagra nge插值多项式构造及其余项， 插值基函数性质；2. 掌握差商的概念及其性质，Newt on插值多项式构造，两种插值法之间的区别 与联系；3了解差分与等距节点插值多项式公式；4. 掌握Hermite插值问题及其构造方法。本章问题：函数f(x)复杂，或无表达式，构造简单函数P(x)

17、来代替f(X)。§ 1 Lagrange 插值一、代数插值问题及插值多项式存在唯一条件1、代数插值问题：f (x)在区间a,b中互异的n+1个点x0 , X-i, Xn的函数值yoy.，yn，求次数 n次多项式Pn(x)aoaiX .anXn且满足Pn (Xi)f(Xi)yi , i=0,1,Tn.2、插值多项式存在唯一条件：定理：Pn(x)a0a1x . anxn存在唯一条件是n+i个节点互异。二、Lagrange插值构造1、线形插值n=1几何解释；利用插值基函数构造：基函数：一次多项式|0(x), l1(X)满足lo(Xo)1li(Xo)0lo(Xi)0li(Xi)1l°

18、;(x)XX1XX1h(x)xX0X1X0L1(x)y°l°(x)y'1(X)1 次Lagrange插值多项式例1 ：求 f (X). X 过点4，2，9，3的1次Lagrange插值多项式，并计算 J5近似值2、抛物插值n=2几何解释；利用插值基函数构造:基函数：二次多项式|°(x), h(x), l2(X)满足lo(Xo)110(X1) 010(X2)0ll(x0)011 (Xi)1li(X2) 012(X0) 012(X1)0l2(X2)1l°(x)(X(X0X1)( XX2 )X1)( X0X2)l1(x)(X X0)(X X2)(X1X

19、°)(X1X2)l2(X)(X X°)(x X1)(X2X0)(X2X1)L1(x)y°l°(x) y1h(x)y22x2 次Lagrange插值多项式例2 :求fXJX过点1, 1，4, 2，9, 3的2次Lagrange插值多项式，并计算 J5近似值3、一般情形：利用插值基函数构造:基函数：n 次多项式 l 0(x),l1 (x),. ln (x)满足li(Xj)1 i j ij0 i jlk(x)(x X°)(xX1).(X Xk1)(XXk1).(X Xn)(XkX0 )(XkX1).(XkXk1)(XkXk1).(XkXn)Ln(x)

20、ny00(x)y1h(x). yn(x)yklk(x) n 次 Lagrange插值多项式k 0三、插值余项定理:假 设 fx在a,b连续，fn1x在a,b存在，_那么 插 值误差Rn(x)f(n 1()f (X)Ln(x)(X)，(n 1)!其中a,b依赖于x。§ 2分段插值一、分段线性插值在区间a, b，分为n个区间伙必訂，i=0,1,2每个区间由直线代替曲线，形成分段线性插值函数X(X) li(x)yi li1(x)yi 1X Xi,Xi1X Xi 1 li(x) dli1(x)XxiXiXi 1Xi 1 Xi二、分段抛物插值Newton插值一、差商及其性质定义:一阶差商:fX

21、i ,Xi 1f (Xi1) f (Xi)Xi 1 Xi二阶差商:fXi ,Xi 1,Xi2fXi 1,Xi 2f Xi,Xi 1Xi 2XiK阶差商:fXi,Xj 1,Xi kfXi 1,Xi 2,，Xi k fXi,Xi 1,.Xi k 1Xi k Xi性质:1差商可由节点函数值表示;2差商值与节点次序无关。二、Newton插值多项式由差商定义f(x)f(Xo)fx°,x(x Xo)fXo,xfXo,XifXo,Xi,x(X xi )fXo,Xi,xfXo, Xi,X2f Xo,Xi, X2, X(X X2)fXo,Xi,.Xn1,Xf Xo,Xi,.XnfX°,Xi,

22、.Xn,X(XXn)依次带入Nn(x) f(Xo)fXo,Xi(xXo).fXo,Xi,.Xn(xX。)(XXn 1)-一Newton 插值多项式计算时先造差商表；三、余项fXo, Xi，Xn, X(n 1)(n 1)!§ 4差分与等距节点插值多项式、差分及其性质：、等距节点插值多项式§ 5 Hermite 插值、带导数的插值多项式求 次 数 不 超 过 3 次 多 项 式Ha(x),满足 H3(x°) y°,H3(X1) y1,H3(x°) m°,H3(X1) mn ； 2、利用基函数构造H3(x)o(x)i(x)(12XXoX w

23、XiXoXi)(XoXiXXiXXo2Xi XoXiXo)2)2o(x)yoi(x) yio(x)m°i(x)miX X-I 2o(X) (X Xo)(-)XoXiX X02i(x) (X Xi)(-)2XiXo0,i,. n；、一般情形i、问题：求次数不超过2n+i次多项式H2ni(x),满足Hzn'xJyi, Hi (xi) mi, i2、利用基函数构造 见教材第七章 数值微积分1. 了解数值求积根本思想；2. 掌握Newton-Cotes公式梯形公式，Simpson公式，Cotes公式推导及误 差；3. 了解 Romberg 求积公式原理；4了解数值微分的方法。本章问题

24、：数值积分问题b求定积分 f (x)dx F(b) F(a)a不能使用微积分公式情形存在问题：1f(x)表达式复杂，原函数更复杂；2f(x)表达式不复杂，但原函数复杂； 3原函数不存在；3f(x)无表达式§ 1 Newton -Cotes 公式一、 数值求积根本思想1、 不利用原函数，直接利用函数值b积分中值定理： f(x)dx (b a)f ( )af( ) 为平均高度；bn机械求积方法：Ia f(x)dxAjf(Xj)i 0Xi为求积节点；Ai为求积系数2、几个简单求积公式左矩形公式Ibf (x)dx a(ba) f(a)右矩形公式Ibf (x)dx a(ba)f(b)中矩形公式

25、bf(x)dx a(ba)f(a2b)2梯形公式Iba f(x)dxb a2(f(a) f (b)Newton -Cotes 公式1、公式推导由Lagrange插值多项式Ln (x)代替函数f(x)f(x)dxbLn(x)dxb nli(x) f (xi)dxa i 0bli(x)dx) f (xjabli(x)dxaba f(x)dxAf(xJ求积系数a的计算:n i!( n i)!n (tj 0 (i 訥(b a)Ci(n)j i(n) ICi f (xi )0Newton - Cotes求积公式I f (x)dx A f (Xi) (b a)ai 0i2、Cotes系数性质对称性：G(n

26、)cnn)n权性：ci(n)1i 03、常用公式n=1bb af(b)梯形公式：| f(x)dx(f (a)a 2n=2bb aa bSimpson,抛物公式： I f(x)dx (f(a)4f(=)f(b)a 6 2n=4bbaCotes 公式：I f (x)dx(7f(x0) 32f (x1) 12f(x2) 32f (x3) 7f (x4)a90.b axi a i -44误差估计：见教材举例说明。§ 2 Romberg 求积公式一、复化梯形公式将积分区间a,b ，n等份，步长hhn 1Tn -f(a) 2f(xj f(b)2i i误差估计：二、梯形公式递推化2Tnhnf(xi

27、1)2三、Romberg 求积公式由梯形公式修正,提高精度Sn43T2n13TnCnRn63C2n63Cn§ 3 Gauss型求积公式、代数精确度定义：假设求积公式|bf(x)dxaAi f (xi)对任意w m次代数多项式精确成立，而对i 0m+1次代数多项式不精确成立，称求积公式具有m次代数精确度。判定：求积公式具有m次代数精确度 求积公式对f(x)1,X,X2,.,xm精确成立；而对f (x) xm 1不精确成立。例：梯形公式具有1次代数精确度；定理2； Newton -Cotes公式代数精确度至少为 n ；当n为偶数时，可达n+1次代数精确度。二、Gauss型求积公式定义：假

28、设n+1个节点求积公式|a f(X)dXAi f (xi )具有2n+1次代数精确度，那么称为i 0Gauss型求积公式，节点为 Gauss点Gauss点的特性：见教材第八章 常微分方程数值解1. 掌握Euler方法Euler公式，梯形公式，Euler预估-校正公式，局部截断误差，公式的阶;2. 了解Runge-Kutta方法的根本思想及四阶经典 Runge-Kutta 公式;3. 掌握线性多步方法的原理与公式推导。本章问题：一阶常微分方程初值问题¥ f(x,y) dxy(x°)y°解的存在性定理：解析解的概念数值解的概念§ 1 Euler 方法一、Euler 公式 导数离散化y(Xn)f(Xn,y(Xn)由向前差商代替导数'、y(Xn i) y(Xn)y (Xn)h得y(Xn 1) y(Xn) hf (Xn,y(Xn)记为 yn iynhf(xn,yn)Euler显式公式由向后差商代替导数1y(Xn1) y(Xn)y (Xn l)h得y(Xn 1)y(Xn)hf(Xn 1,y(Xn 1)记为yn1 ynhf(Xn 1：,yn 1)Eule