数值分析
1. 数值分析的病态性是指因初始数据的微小变化,导致计算结果的剧烈变化。 病态问题:因初始数据微小变化,导致计算结果剧烈变化的问题 良态问题:初始数据微小变化,只引起计算结果微小变化的计算问题。
数值不稳定算法:指算法进行计算的初始数据有误差,而计算过程中产生的舍入误差不断增长。例子
2. 误差的来源:①模型误差:在数学建模时,由于忽略了某些次要因素而产生的误差;②观测误差:在采集原始数
据时,由仪器的精度或其他客观因素产生的误差;③截断误差:对产与计算的数学公式做简化处理后所产生的误差;④舍入误差:计算机因数系不全,由接受和运算数据的舍入引起的误差。
科学计算中值得注意的地方:①避免两个相近的数相减;②合理安排量级相差很大的数之间的运算次序,防止大数吃小数;③避免绝对值很小的数做分母;④简化运算步骤,减少运算次数。 3. 用计算机做科学计算时的溢出错误。
机器数系是有限的离散集,机器数系中有绝对值最大和最小的非零数M 和m ,若一个非零实数的绝对值大于M ,则计算机产生上溢错误,若其绝对值小于m ,则计算机产生下溢错误。上溢错误时,计算机中断程序处理;下溢错误时,计算机将此数用零表示并继续执行程序。
4. 解非线性方程f x ()
=0单根的牛顿法具有二阶收敛。简单迭代法具有一阶收敛性。当f '
x *
()10且有2阶导数时,
Newton 迭代法才有二阶敛速。
5. 对(n+1)个节点的Newton-cotes 求积公式,在n £7时,Cotes 系数大于0,而在n >7时,考虑到公式的稳定性不实用该公式。
6. 当系数矩阵A 是严格对角占优矩阵,Jacobi 格式、Seidel 格式都收敛。
7. 用高斯消元法求解线性方程组,一般使用选主元的技术是因为要减少舍入误差。
8. 解非线性方程组迭代法的整体收敛和局部收敛的主要区别是局部收敛在较小邻域内取初值,有初值限制。 9. 二分法是全部收敛,简单迭代法是局部收敛。
10. 四种插值方法:Lagrange 插值、Newton 插值、Hermite 插值、分段多项式插值。
11. 截断误差是对参与计算的数学公式作简化处理后所产生的误差,在所学的数值方法中插值和数值积分都涉及截断误差处理的内容,分别为插值余项和积分余项。
例:e x =1+x +x 2
2!
+
+x n n!+无穷项相加,我们用e x =1+x +x 2
2!
+
+x n
n!
近似计算e x 就产生截断误差。 12. 线性方程组迭代解法的基本思想是将现行方程组作等价变形,得到同解的易于作迭代计算的线性方程组,用计算出的迭代序列来逼近解。考虑线性方程组Ax =b 及由次方程组构造的迭代格式x k +1()
=Bx k
()+g ,判断此迭代格
式的收敛方法有:
(1) 若r B ()
<1,则迭代格式收敛;
(2)若B <1,则迭代格式收敛,B 是矩阵B 的某种算子范数;
(3) 若矩阵A 是严格对角占优矩阵,则线性方程组Ax =b 的Jacobi 迭代和Seidel 迭代对任意初值都收敛; (4)若矩阵A 是对称正定矩阵,则线性方程组Ax =b 的Seidel 迭代对任意初值都收敛; (5) Sor 法收敛的必要条件是松弛因子w 满足0 <0(2)f ' x ()10,x ?a,b é?ù?(3)f '' x ()存在且不变号,x ?a,b é?ù? 则x 0 ?a,b é?ù?,只要f x 0()f '' x 0()>0,则迭代公式产生的数列x k {}一定收敛于a,b é ?ù?上的为一根x * 。 14. 引入分段插值的原因及目的。 Runge 现象:随着节点n 的增加,误差不但没减小,反而不断增大。原因是当节点n 较大时,对应的是高次插值多项式,而高次多项式的舍入误差是随次数的增加而不断变大的,用高次多项式插值作数值计算时舍入误差将“淹没”了增加节点提高的精度。Runge 现象否认了用高次插值公式提高逼近精度的做法,因此引入了分段插值法。定义如下: 取a,b é?ù?上的n+1个节点x k :a =x 0 =g k , k =0,1,,n 。若函数j x () 满足条件:(1)j x ()在a,b é?ù?上连续;(2)j x () =y k ,k =0,1, ,n ;(3)j x ()在每个小 区间x k ,x k +1é?ù?是m 次多项式,k =0,1,,n -1,则称j x () 为f x ()在a,b é?ù?上的分段m 次插值多项式。 15. Newton 法的基本思想:将函数f x () 做线性化处理,把方程f x () =0转化为对应的近似方程L x () =0,再从 L x () =0中构造迭代公式。Newton 法在x *附近是平方收敛的。 16. Seidel 格式比Jacobi 格式占用的内存空间大。 17.①列范数:A 1 =max 1£j £n a ij i =1 n ?;②行范数:A ¥ =max 1£i £n a ij j =1 n ?;③F 范数:A F = a ij 2i ,j =1 n ?; ④2范数:A 2 =l max ,l max 是A T A 最大特征值;⑤谱半径:r A () =max 1£k £n l k ; ⑥条件数:Cond p A () =A p ×A -1 p 。特征值:mI -A =0求得的m 即为A 的特征值。 矩阵的条件数可反映系数的敏感性,其值越大,解对系数越敏感,因而方程组越病态。 18. 2点Newton-Cotes 公式【梯形公式】: f x () a b òdx ? b -a 2f a ()+f b () é? ù? 3点Newton-Cotes 公式【Simpson 公式】: f x () a b òdx ? b -a 6f a () +4f a +b 2?è???÷+f b () é ?êù? ú 复化梯形公式: f x () a b òdx ?b -a 2n f a ()+f b ()+2f x k ()k =1n -1 ?é ?êù? ú,余项:R f ,T n ()=-b -a 12h 2f ''h () ,h ?a,b é?ù? 复化Simpson 公式: f x () a b òdx ?b -a 6n f a ()+f b ()+4f x k +1+x k 2?è???÷k =0n -1?+2f x k () k =1n -1?é ?êêù? úú, 余项:R f ,S n () =-b -a 180h 2?è???÷4 f 4() h () =-h 4b -a () 2880 f 4()h () ,h ?a,b é?ù? 19. 插值与拟合的区别。 插值与拟合都是有一组数据点构造一个近似函数,但他们的近似要求不同。二者都属于函数逼近范畴。 ①插值函数在几何上的描述为过所有给定数据点集散点图的任何一条曲线。插值是对f x () 在区间a,b é?ù?上的n+1 个互异的点x 0 ,x 1 ,x 2 ,,x n 及各个点对应的函数f x 0(),f x 1(),f x 2(),,f x n (),找出f x ()的一个近似函数P x (),使得P x i ()=f x i (),P x ()即为插值函数。 ②拟合函数在几何上的描述为穿越所有给定数据点集散点图的任何一条曲线。拟合是对f x ()在区间a,b é?ù?上的n+1个点x 0,x 1,x 2,,x n (不一定互异),根据各个点对应的函数f x 0(),f x 1(),f x 2(),,f x n ()画出的点图来选择用什么类型的函数做逼近函数j x (),逼近函数j x ()通过min d ,d =d 0,d 1,d 2,d n ()T ,d i =f x i ()-j x i ()的拟合条件获得,则这样求出的j x ()称为拟合函数。 20. Lagrange 插值步骤:①利用互异插值节点x 0,x 1,x 2,,x n ,算出插值基函数l in x (),i =0,1,,n ; ②利用插值基函数构造插值多项式L n x ()。 优点:利用插值基函数很容易得到Lagrange 插值多项式,公式结构紧凑,在理论分析中很方便。 缺点:当插值节点增减时,l in x () 全部要随之变化,在实际计算中很不方便。 n 次Lagrange 插值多项式至少需要n+1个插值节点数据。与其相比,Newton 插值具有承袭性和易于变动节点的特点。 21. L-插值和N-插值的异同。 l in x () =x -x k x i -x k ?è???÷k =0,k 1i n ?L n x () =y i i =0 n ?x -x k x i -x k ?è?? ?÷ k =0,k 1i n ? 余项:R n x ()=f n +1x ()n +1()! w n +1x (),x ?a,b ()其中:w n +1 x ()=x -x k ()k =0 n ? ,x k ?a,b é?ù? f x 0,x 1,x 2, ,x n é?ù?=f x i ()w n +1 'x i () i =0 n ?=f n ()x ()n!余项:E n x ()=f x 0,x 1 , ,x n ,x é?ù?w n +1x () f x ()=f x 0()+f x 0,x 1é?ù?x -x 0()+f x 0,x 1,x 2é?ù?x -x 0()x -x 1()+ +f x 0,x 1,x 2 , ,x n é?ù?x -x 0()x -x 1 ()x -x n -1 () 同:①L n x ()=N n x (),余项;②表达式均为基函数的线性组合。 异:①L-基与N-基不同;②计算L-插值主要计算基函数,计算N-插值主要计算组合系数或各阶商差; ③高次N-插值包含低次N-插值,而L-插值不然。 22. 数值分析中,线性方程组的数值解法主要分为直接法和迭代法两大类。 ①直接法使用有限次计算就能求出线性方程组“准确解”的方法,这里的“准确解”是指在求解过程中不考虑舍入误差影响得出的解。 ②迭代法是由线性方程组构造出迭代计算公式,然后以一个猜测的向量作为迭代计算的初始向量,逐步迭代计算,来获得满足精度要求的近似解,是一种逐次逼近的方法。 23. 三对角线性方程组用追赶法计算求解效果最好,对称线性方程组用LDL T 法。 24. 若n 点的求积公式具有2n-1次的代数精度,则称该求积公式为Gauss 型求积公式。 n 点插值型求积公式的代数精度至少是n-1,至多为2n-1。 【注意:若下标从1开始,则代数精度为2n-1,若下标从0开始,则代数精度应为2n+1】 25. 判断迭代的收敛阶:写出迭代方程计算各阶导数,判断各阶导数在根处是否为0,若j n () x ()10,则最高为n 阶收敛。 判断求积公式的代数精度:取f x () =x k ,k =0,1,,代入R x k () =f x ()a b òdx -V ,验证R x k () =0是否成立, R x 0()=R x 1()=R x 2() = =0,第一个使R x k () 10的k 值,则对应的代数精度为k-1。 26. 求微分方程初值问题的Euler 方法的绝对稳定域是1+l h £1,绝对稳定区间是-2,0é?ù?。 R n x ()=E n x () 第一章 绪论 1.绝对误差e *:e *=x *-x 绝对误差限e *:e *=x *-x £e * 相对误差e r *:e r *=e *x =x *-x x 相对误差限e r * :e r *=x *-x x £e r * 2.绝对误差计算公式: e x *±y *()=e x *()±e y *()e x *×y *( )?y *e x *()+x *e y *() e y *x *?è???÷?y *e x *()-x *e y *()y *() 2 3.相对误差计算公式: e r x *±y * ( )? x *e x *() ±y *e y * ()x *±y * e r x * ×y * ()?e r x * ()+e r y * ()e r x * y * ?è??? ÷?e r x *()-e r y * () 4.绝对误差:e x * ()=dx 相对误差:e x * ()x =dx x =d ln x e V ()=e abc () = ?V ?a e a () +?V ?b e b ()+?V ?c e c ()e V ()=e abc ()=?V ?a e a ()+?V ?b e b ()+?V ?c e c () 5.有效数字:e x * ()=x * -x £0.5′10 m -n ,则称x *有n 位有效数字。 6. ①若x * 有n 个有效数字,则x * 的相对误差为:e r x * () =x *-x x £1 2a 1 ′101-n ; ②若x * 的相对误差为:e r x * () =x *-x x £1 2a 1+1 () ′101-n ,则x *有n 个有效数字。 第二章 非线性方程的球根方法 1.二分法:精度e ,x * -x k 2 k +1b -a () ln b -a ()-ln e ln 2-1x k -x k -1 =0转化为不动点方程x =j x (),构造迭代公式x k +1 =j x k () ,取定一个初值x 0,由迭代 公式求的:x 1 =j x 0 (),x 2 =j x 1() ,?? ★收敛判别:①当x ?a,b é?ù?时,有j x () ?a,b é?ù?;②任取x 1,x 2?a,b é ?ù?存在与x 1,x 2无关的正常数L <1,满足 j x 1()-j x 2()£L x 1-x 2,则j x ()在a,b é?ù?中有唯一的不动点x * ,且迭代公式x k +1=j x k ()对任取的x 0?a,b é?ù?,产生的数列都收敛于x *。 ★②可替换为:j ' x () £L <1,x ?a,b é?ù?,定理同样成立 x * 是j x ()的不动点,j ' x ()在x * 处连续,j ' x ()<1时,x k +1 =j x k () 局部收敛;j 'x ()>1时,x k +1=j x k () 发散。 ★误差估计式:x * -x k £L 1-L x k -x k -1,x * -x k £L k 1-L x 1-x 0 精度e ,x * -x k 1-L x 1-x 0 1-L ( ) e x 1-x 0?ln L x k -x k -1 ★步骤:①说明方程在所取区间内有唯一解:f a ()×f b () <0,f ' x ()在a,b é?ù?上不变号; ②证明采取的迭代公式具有收敛性:x ?a,b é?ù?,j x ()?a,b é?ù?,j ' x ()£L <1; ③迭代求解,用x k -x k -1 3.判断迭代的收敛阶:写出迭代方程计算各阶导数,判断各阶导数在根处是否为0,若j n () x ()10,则最高为n 阶收敛。 ★步骤:①确定迭代格式:x k +1=j x k () ; ②据已知条件建立方程组:f ' x * ()=0,f '' x * ()=0,??; ③求出未知系数,建立迭代公式,计算f n () x * ()10,则迭代收敛阶最高为m 。 4.Newton 迭代法:x k +1=x k -f x k ()f ’ x k () 当f x * ()10时,且有二阶导数,则至少是平方收敛,否则为线性收敛。 ★收敛判别:f x () ?C 2 a,b é?ù?,满足下列三个条件: ①当f a ()×f b ()<0;②f ‘ x ()10,x ?a,b é?ù?;③f '' x ()存在且在a,b é?ù?上不变号; 则在a,b é?ù?内任取一点x 0 ,只要f x 0()f '' x 0()>0,则迭代公式产生的数列x k {},一定收敛于a,b é?ù?上的唯一根x * 第三章 线性方程组的解法 1.数值分析中,线性方程组的数值解法主要分为直接法和迭代法两大类。 ①直接法使用有限次计算就能求出线性方程组“准确解”的方法,这里的“准确解”是指在求解过程中不考虑舍入误差影响得出的解。 ②迭代法是由线性方程组构造出迭代计算公式,然后以一个猜测的向量作为迭代计算的初始向量,逐步迭代计算,来获得满足精度要求的近似解,是一种逐次逼近的方法。 2.迭代法: Jacobi 迭代法:x 1k +1()=1a 11b 1-a 12x 2k ()-a 13x 3k ()--a 1n x n k () () x 2k +1()=1a 22b 2-a 21x 1k ()-a 23x 3k ()--a 2n x n k () ( ) x n k +1()=1a nn b n -a n 1x 1k ()-a n 2x 2k ()--a nn -1x n -1 k ()() ìí?? ??? ? ???x i k +1()=1a ii b i -a ij x j k ()j =1,j 1i n ??è???÷i =1,2,,n Ax =b D -L -U ()x =b x k +1() =D -1L +U ()x k ()+D -1b B J =D -1L +U () g J =D -1b Seidel 迭代法:x 1k +1()=1a 11b 1-a 12x 2k ()-a 13x 3k ()--a 1n x n k () () x 2k +1()=1a 22 b 2-a 21x 1k +1()-a 23x 3k ()--a 2n x n k ()( ) x n k +1()=1a nn b n -a n 1x 1k +1()-a n 2x 2k +1()--a nn -1x n -1k +1() () ìí?? ??? ? ? ??x i k +1()=1a ii b i -a ij x j k +1()j =1i -1?-a ij x j k ()j =i +1n ??è???÷ D -L () x k +1()=Ux k ()+b x k +1()=D -L ()-1Ux k ()+D -L ()-1b B S =D -L ()-1U g S =D -L ()-1b Sor 迭代法:以Seidel 迭代法为基础,可以改变收敛速度。 x k +1() =1-w () x k () +w x S k +1()x i k +1()=1-w () x i k +1()+w a ii b i -a ij x j k +1() j =1i -1?-a ij x j k ()j =i +1 n ??è???÷i =1,2,,n x k +1 ()=D -w L () -1 w U +1-w ()D é?ù? x k ()+D -w L () -1 w b B w =D -w L ()-1 w U +1-w ()D é?ù?g w =D -w L () -1 w b 其中:A =D -L -U D =a 11a 22 a nn é? êêê êêù? úúúúúL =-0 00a 21 0a n 1a n 20é?êêêêêù?úúúúúU =-0a 12 a 1n 00 a 2 n 0 00é?êêêêêù ? úúúúú 3.判断收敛性:当不能用范数或者矩阵本身性质判定时: ①对Jacobi ,对其求特征值,det l I -B J ()=0,r B J ()=max 1£k £m l k ,若r B J () <1,则Jacobi 迭代收敛。 ②对Seidel ,求特征值,det l I -B S ()=0,即det l D -L ( ) -U () =0,r B J ()=max 1£k £m l k ,若r B J () <1,则迭代收敛。 4. 范数:①列范数:;②行范数:;③F 范数:; ④2范数:,是最大特征值。特征值:求得的m 即为A 的特征值。 5.Gauss 消元法:消元过程——回代过程,计算量为n 33+n 2-n 3 :N 消=n 3n 2-1()+n 2n -1();N 回=n 2n +1() 适用条件:Ax =b 的系数矩阵A 的顺序主子式都不为0。 列主消元法和全主消元法(首选) 6.LU 分解法:Ax =b ,将系数矩阵分解为下三角矩阵L 和上三角矩阵U 的乘积。LUx =b ,Ly =b ,Ux =y ①Doolittle 分解:非奇异矩阵A 的Doolittle 分解是唯一的 L =1l 211l 31 l 31 1 l n 1l n 2 l nn -1 1é? êêê êêêêù ?úú úú ú úúU =u 11u 12…u 1n 0u 22…a 2n u nn é?êêêêêù? úúúúú ②Grout 分解: L =l 11l 21l 22 l n 1l n 2 l nn é?êêêêêù ?úúú ú úU =1u 12 u 13u 1n 1u 23u 2n 1 u n -1n 1é? êêêêêêê ù ? úú úúú úú ③LDU 分解: L =1l 211l 31 l 31 1 l n 1l n 2 l nn -1 1é? êêê êêêêù ? ú ú úú ú úúD =d 1d 2d n é?êêêêêù ?úúú ú úU =1u 12 u 13u 1n 1u 23u 2n 1 u n -1n 1é? êêêêêêê ù ? úú úúú úú 7.法:专用于对称线性方程组,计算量为n 3 4 。 A =A T ,A =LDU ,A T =LDU () T =U T DL T =LDU =A ,由矩阵A 的LDU 分解的唯一性可得U =L T , Ly =b ,Dz =y ,L T x =z , A 1 =max 1£j £n a ij i =1 n ?A ¥ =max 1£i £n a ij j =1 n ?A F = a ij 2 i ,j =1 n ?A 2 =l max l max A T A mI -A =0LDL T 8.追赶法:求解三对角方程组的专用方法,计算量仅为5n-4。 三对角方程组的系数矩阵A :A =b 1c 1a 2b 2c 2a 3 b 3 c 3 a n -1 b n -1 c n -1 a n b n é? êêê êê êêêêù ? ú úúúúúúúú=1p 2 1 p n 1é?êêêêêù?úúúúúq 1r 1 q 2r 2 q n -1r n -1 q n é? ê êêêêêêù? úúúúúúú q 1=b 1,r k =c k ,p k =a k q k -1,q k =b k -p k c k -1 9.条件数:设A ?R n ′n 为非奇异矩阵,称为矩阵A 的条件数。 矩阵的条件数可反映系数的敏感性,其值越大,解对系数越敏感,因而方程组越病态。 第五章 插值与拟合方法 1.插值与拟合的区别。 插值与拟合都是有一组数据点构造一个近似函数,但他们的近似要求不同。二者都属于函数逼近范畴。 ①插值函数在几何上的描述为过所有给定数据点集散点图的任何一条曲线。插值是对在区间上的n+1 个互异的点及各个点对应的函数,找出的一个近似函数,使得,即为插值函数。 ②拟合函数在几何上的描述为穿越所有给定数据点集散点图的任何一条曲线。拟合是对在区间上的n+1个点(不一定互异),根据各个点对应的函数画出的点图来选择用什么类型的函数做逼近函数,逼近函数通过,,的拟合条件获得,则这样求出的称为拟合函数。 2. Lagrange 插值。 余项:,其中:, 3.商差表: ,,x 2Cond p A () =A p ×A -1p f x () a,b é?ù?x 0 ,x 1 ,x 2 ,,x n f x 0(),f x 1(),f x 2(),,f x n ()f x ()P x ()P x i ()=f x i ()P x ()f x ()a,b é?ù?x 0,x 1,x 2,,x n f x 0(),f x 1(),f x 2(),,f x n ()j x ()j x ()min d d =d 0,d 1,d 2,d n ()T d i =f x i ()-j x i ()j x ()l in x () =x -x k x i -x k ?è???÷k =0,k 1i n ?L n x () =y i i =0n ?x -x k x i -x k ?è?? ? ÷k =0,k 1i n ?R n x ()=f n +1x ()n +1()! w n +1x ()x ?a,b ()w n +1 x ()=x -x k ()k =0 n ? x k ?a,b é?ù? 4. Newton 插值。 余项: 5.Newton 前插公式:D f i =f x i +h ()-f x i () D m f i =D m -1f i +1-D m -1f i N n x ()=N n x 0+th ()=f x 0() +t D f 0+ t t -1()2! D 2 f 0+ + t t -1 ()t -n +1()n! D n f 0x =x 0+th t ?0,n é?ù? Newton 后插公式:?f i =f x i ()-f x i -h () ?m f i =?m -1f i -?m -1f i +1 N n x ()=N n x n +th ()=f x n () +t ?f n + t t +1()2! ? 2 f n + + t t +1 ()t +n -1()n ? n f n x =x n +th t ?-n,0é?ù? 当x 值靠近x 0时,用Newton 前插公式,而当x 靠近x n 时,用Newton 后插公式。 5.Hermite 插值:有(2n+2)个条件,所以有(2n+1)次多项式。2n+1次Hermite 插值多项式是唯一的。 2n+1次Hermite 插值多项式的余项为:R 2n +1x ()=f 2n +2 ( ) x ()2n +2()!w n +1 2 x ()x ?a,b () 6.分段多项式插值: Runge 现象:随着节点n 的增加,误差不但没减小,反而不断增大。原因是当节点n 较大时,对应的是高次插值多项式,而高次多项式的舍入误差是随次数的增加而不断变大的,用高次多项式插值作数值计算时舍入误差将“淹没”了增加节点提高的精度。Runge 现象否认了用高次插值公式提高逼近精度的做法,因此引入了分段插值法。定义如下: 取上的n+1个节点:,并给出这些节点上的函数值, 。若函数满足条件:(1)在上连续;(2),;(3)在每个小 区间是m 次多项式,,则称为在上的分段m 次插值多项式。 7.曲线拟合法——最小二乘曲线拟合方法: ★步骤:①根据题意取基函数:j k x () =x k ,k =0,1,,m ; ②建立m 次曲线拟合函数:,j x () =a 0+a 1x +a 2x 2 a m x m ; ③求建立法方程组:若题中有c 组数据,则n=c-1,法方程组如下: w i i =0n ?w i x i i =0n ?w i x i m i =0n ?w i x i i =0 n ?w i x i 2i =0 n ?w i x i m +1i =0n ?w i x i m i =0n ?w i x i m +1i =0 n ?w i x i 2m i =0 n ?é ? êêêêêêêêêêù ? úúúúúúúúúúa 0a 1a m é?êêêêêù?úúúúú=w i x i i =0 n ?w i x i y i i =0 n ?w i x i m y i i =0n ?é ? êêêêêêêêêêù? ú úúú úúú ú úú 8.最佳平方逼近:曲线拟合是用已知离散数据点来求拟合函数,若用已知连续函数取代离散数据去求拟合函数,则为函数逼近的内容,即最佳平方逼近。只要将曲线拟合中设计节点累加的符号?换成定积分符号a b ò f x 0,x 1,x 2, ,x n é?ù?=f x i ()w n +1 'x i () i =0 n ?=f n ()x ()n!E n x ()=f x 0,x 1 , ,x n ,x é?ù?w n +1x () f x ()=f x 0()+f x 0,x 1é?ù?x -x 0()+f x 0,x 1,x 2é?ù?x -x 0()x -x 1() + +f x 0,x 1,x 2,,x n é?ù?x -x 0()x -x 1 ()x -x n -1 ()w n +1 x ()=x -x k ()k =0 n ?a,b é?ù?x k a =x 0 =g k k =0,1,,n j x ()j x ()a,b é?ù?j x ()=y k k =0,1,,n j x () x k ,x k +1é?ù?k =0,1,,n -1j x ()f x () a,b é?ù? 第六章数值积分与数值微分方法 1.若存在实数x 1,x 2, ,x n ;A 1,A 2,,A n ,且任取f x () ?C a,b é?ù?,都有f x ()a b òdx ?A i f x i ()i =1 n ?,则称为一个数值求 积公式。A i 称为求积系数,x i 称为求积节点。 2.评价一个求积公式的优劣可以用求积余项来说明,通常用与求积余项有关的代数精度来评价求积公式。 判断求积公式的代数精度:取,,代入,验证是否成立, ,第一个使的k 值,则对应的代数精度为k -1。 3.插值型求积公式:当f x ()为次数小于n 的多项式时,f n ()x ()o0,R f () =0,插值型求积公式的代数精度至少为n-1 求积系数:A i = l in -1x () a b ò dx 求积公式:f x ()a b òdx ?A i f x i ()i =1 n ?求积余项:R f ()?f n ()x ()n! a b òw n x ()dx 4.Newton-Cotes 求积公式:当求积节点个数为奇数时,Newton-Cotes 求积公式代数精度至少为n ;为偶数时,代数精度至少为n-1 为使求积系数A i 计算简单,将求积节点x i 取为a,b é?ù?上的等距节点,x i =a +i -1() h ,h =b -a n -1 ,i =1,2,,n n 点的Newton-Cotes 求积公式: f x ()a b òdx ?b -a ()C i n () f x i () i =1 n ?C i n () =1n -1t -k +1i -k k =1,k 1i n ??è??? ÷0n -1òdt 2点Newton-Cotes 公式【梯形公式】: ,余项:R f ()=-b -a ()12f ''h (), 3点Newton-Cotes 公式【Simpson 公式】: ,余项:R f ()=-b -a ()5 2880f 4()h () 对n 个节点的Newton-cotes 求积公式,在n £8时,Cotes 系数大于0,而在n >8时,考虑到公式的稳定性不实用该公式。 5.Gauss 型求积公式:Gauss 型求积公式是稳定的。 若n 点的求积公式具有2n-1次的代数精度,则称该求积公式为Gauss 型求积公式。【注意:若下标从1开始】 Gauss 型求积公式的求积余项:R f ()= f 2n ()h ()2n ()!r x ()w n 2 x ()dx a b òh ?a,b é?ù? 6.复化求积公式:x i =a +ih ,h =b -a n ,i =0,1,2,,n ,将积分区间a,b é?ù?n 等分,有n+1个节点。 复化梯形公式(代数精度为1): ,余项: 若f '' x () £M 2,对于给定精度e ,令R f ,T n () £- b -a 12 h 2 M 2£e ,得出h £ 复化Simpson 公式(代数精度为3): , 余项:, f x () =x k k =0,1,R x k () =f x ()a b òdx -V R x k () =0R x 0()=R x 1()=R x 2() = =0R x k () 10f x () a b òdx ? b -a 2 f a ()+f b () é?ù?h ?a,b é?ù?f x () a b òdx ?b -a 6f a () +4f a +b 2?è???÷+f b () é ?êù? úf x () a b òdx ?b -a 2n f a ()+f b ()+2f x k ()k =1n -1 ?é ?êù? úR f ,T n ()=-b -a 12h 2f ''h () f x () a b òdx ?b -a 6n f a ()+f b ()+4f x k +1+x k 2?è???÷k =0n -1?+2f x k () k =1n -1?é ?êêù? úúR f ,S n () =-b -a 180h 2?è??? ÷4 f 4() h () =-h 4b -a () 2880f 4()h () h ?a,b é?ù? 第七章 常微分方程初值问题数值解法 1.Euler 公式:y k +1=y k +hf x k ,y k () ,k =0,1,2 n -1,h =x k +1-x k 若用数值积分法:利用梯形公式得,y k +1=y k + h 2f x k ,y k ()+f x k +1,y k +1() é? ù?,k =0,1,2n -1 显示方法——可以直接解出y k +1;隐式方法——需要解方程组解出y k +1,后退Euler 方法 2. 误差:局部截断误差是指计算一步所产生的误差 局部截断误差:T k +1=y x k +1()-y x k () -h j x k ,y x k (),h () 若某种数值解法的局部截断误差为T k +1 =O h P +1 (),则称该方法具有p 阶精度或该方法是p 阶方法 数值方法的阶越高,该方法越好,这是因为步长h 一般小于1,故h P +1随p 的增大而减小,从而使局部截断误差更小 如果某方法是p 阶方法,主要关心其局部截断误差T k +1=O h P +1 ()按h 展开的第一项,该项称为主局部截断误差 或局部截断误差主项。T k +1 =O h P +1 ()=g x k ,y x k ()()h P +1 +O h P +2 (),其中,g x k ,y x k ()()h P +1 就是局部截断误差主项 ①Euler 方法:T k +1=y x k +1()-y x k ()-hf x k ,y x k ()()=y x k +h ()-y x k ()-hy ' x k () =y x k ()+y 'x k () h + y ''x k ()2 h 2 -y x k () -hy 'x k ()+o h 3() = y ''x k ()2 h 2 +o h 3() ,所以为一阶方法 ②后退Euler 方法:T k +1=y x k +1()-y x k () -hf x k +1,y x k +1 ()()=y x k +h ()-y x k ()-hy ' x k +1() =y x k () +y 'x k () h + y ''x k ()2 h 2 -y x k () -hy 'x k +1()+o h 3() =y x k () +y ' x k () h + y ''x k ()2 h 2 -y x k ()-h y 'x k () +y ''x k () h é?ù? +o h 3 () =- y ''x k ()2 h 2 +o h 3() ,所以为一阶方法 ③梯形方法:T k +1=y x k +1()-y x k ()- h 2 f x k ,y x k ()()+f x k +1,y x k +1()() é ?ù? =y x k +h ( )-y x k ()-h 2 y 'x k () +y ' x k +1() é?ù? =y x k () +y ' x k () h + y ''x k ()2 h 2 + y 3 ()x k ()3! h 3 -y x k ()-h 2y 'x k ()+y 'x k ()+y '' x k () h +y 3 ()x k () 2h 2é?êêù? úú+o h 4 () =- y 3 ()x k ()12 h 3 +o h 4() ,所以为二阶方法 ④若用某种数值解法求初值问题,在任意节点x k 的数值解y k 时,满足e k +1£e k ,则称该数值方法绝对稳定。 对于Euler 方法,y n +1=1+l h ()y n ,y n +1*=1+l h ()y n *=1+l h ()y n +e n ()=y n +1+1+l h ()e n ,所以e k +1=1+l h () e n 所以,绝对稳定域为1+l h £1,以-1,0() 为圆心,以1为半径的圆的域;绝对稳定区间为-2,0é?ù? 对于改进Euler 方法(梯形方法):绝对稳定域为整个左半平面;绝对稳定区间为整个负半轴。 ★可见,梯形方法绝对稳定域比Euler 方法大,还是二阶方法,故梯形发放比Euler 方法好。隐式方法虽然计算麻烦但是稳定性较好。 3. 线性多步法 n 步Adams 显示(外插)公式:y k +1=y k +h b i f k -i i =0 n -1 ?, 局部截断误差:T =R n = y n ()x ()n!w n x ()x k x k +1ò dx =h n +1 t t +1()t +n -1()0 1 òy n ()x ()n! dt =O h n +1 ()。 n 步Adams 隐式(内插)公式:y k +1=y k +h b i f k +1-i i =0 n -1 ?,局部截断误差:T =R n =O h n +1 ()。 4步Adams 显示(外插)公式:y k +1=y k + h 24 55f k -59f k -1+37f k -2-9f k -3() , 局部截断误差:T = 251720 h 5y 5() x () ,x k -3 24 9f k +1+19f k -5f k -1+f k -2(), 局部截断误差:T =-19720 h 5y 5() x () ,x k -2