计算方法B课程总结

1、计算方法总结计算方法总结 课件地址课件地址: : http:/ 上机题目地址上机题目地址: : http:/ 目录目录 第第1 1章章 绪论绪论 第第2 2章章 线性代数方程组线性代数方程组 第第3 3章章 数据近似数据近似 第第4 4章章 数值微积分数值微积分 第第5 5章章 非线性方程求解非线性方程求解 第第6 6章章 常微分方程数值解法常微分方程数值解法 第第7 7章章 最优化方法简介最优化方法简介 (基本工具) (误差分析基础) (计算方法应用) 第第1章章 绪论绪论 1.1.误差误差: :近似值与真正值之差近似值与真正值之差 分为模型误差、数据误差、截断误差、舍入误差分为模型误差、数

2、据误差、截断误差、舍入误差 2.2.数制表示数制表示 12 1 2 (),1,0,2,3, l t j t xt ddd xddjt 实数 可以表示以下形式的 进制 位有效数字 1212 1 0.10 ,0.10 , 0.5 10, ll tt t xd ddxd dd xxxt 有效数字: 指一个近似数的有意义的数字的位数 若 如果 则称 有 位有效数字 1 ( , , ,), 2(1)(1) 1 t Ft L UUL 数系:表示为个数: lU上溢:lL下溢: 第第1章章 绪论绪论 3.3.舍入误差舍入误差: :对数进行舍入，得到有对数进行舍入，得到有t t位尾数的浮点数位尾数的浮点数 (

3、) : ( ) xfl x x x 相对舍入误差 1 1 ( ) 2 t x 12 3 :()(1-)() ()(1-)() ( )(1-)( ) fl xyxyfl xyxy xx fl yy 性质 浮点运算的注意事项浮点运算的注意事项 (1)避免产生大结果的运算，尤其是避免小数作为除数 参加运算； (2)避免“大”“小”数相加减； (3)避免相近数相减，防止大量有效数字损失； (4)尽可能简化运算步骤，减少运算次数。 )(xfl 第第1章章 绪论绪论 5.5.方法的稳定性方法的稳定性 数值稳定:若初始误差导致最终解的误差能被有效地控制 6.6.算法算法由有限个无二义性法则组成的一个计算过程

4、 数值不稳定:若初始误差导致最终解的误差不能被有效地控制 4.4.问题的性态问题的性态: :问题的解对原始数据扰动的敏感性问题的解对原始数据扰动的敏感性 病态问题:数据相对小的扰动引起解的相对大的变化 良态问题:数据相对小的扰动不会引起解的相对大的变化 ,( ) ( ) ( )sup xf x f x cond f x 条件数:当输入数据具有的误差 引起问题的结果误差为 则 算法的特点,描述 第第1章章 绪论绪论 11 2.718281828,2.71828325,6xxx例.则 的有 位有效位数 ( )2.71828225,fl x若则有7位有效位数 (10,5,-2,3)F例.在中有多少个

5、数? 例.若桌子长为100cm,宽为50cm,实测长为102cm,宽为51cm, 求面积的相对误差 3 3 6 6 1 ) , ) 11 38,19601 6930 8,19601 6930 8 38 3 3- 8 例.下列各式均与等价,在浮点数系F(10,5,-10,10)中 3+ 8 哪个公式能获得最准确的结果:(17-6 8 (17+6 8 第第1章章 绪论绪论 1- ( , , ,), -( )1 ( )( ) 2 t Ft L U xfl x xx x 例.证明在浮点数系中 浮点数的相对误差 满足 ,.)3 , 2(0 ,1 ,)( 1 1 1 3 3 2 21 jdd dddd x

6、 j l t t 其中其中 设设 2 1 1 t d若若 l t t dddd xfl )()( 3 3 2 21 有有 l t t d xflx 1 1 )(此时此时 l t 1 2 1 tl 2 1 l xd 1 ,1 1 有有由于由于 tl x xflx 2 1)( 第第1章章 绪论绪论 2 1 1 t d，若若同理同理 l t t dddd xfl ) 1 ()( 3 3 2 21 有有 l t t d xflx 1 1 )( l t 1 2 1 tl 2 1 l xd 1 ,1 1 有有由于由于 tl x xflx 2 1)( 第第1章章 绪论绪论 23 346 10 -1 -1-1

7、 y x xx 例.为了使计算的乘除法次数尽可 能少,应将该式改写为_ 2 1610 xx 例.在浮点数系下,计算的两个根,应如何 计算才能使精度较高？ ( ),( )f xf x例.对于函数在某个区间上连续可微 则求的近似条件数 第第2章章 线性代数方程组线性代数方程组 , , LULDU GG Gauss解法 列主元Gauss解法 数值解法 矩阵分解法:分解分解 分解 追赶法 Jacobi迭代法 迭代解法 Gauss-Seide 线性方 l迭代法 程组解法 32 :(),: ()o nnsoGaus消去的时间复杂度回代消去法 32 :(),: ()o nGasnsou消去的时间复列主元消去

8、法杂度回代 3 :,:,()LUoUnL:单位下三角阵上三角阵 时间复杂度分解 3 :,:,() 3 n LDULDUo:单位下三角阵对角阵,单位上三角阵 时间复杂度分解 3 (/6),oGnGn:分针对对称正定矩阵,加 个解开方运算 :三对角阵分带状矩阵分解解,追赶法 第第2章章 线性代数方程组线性代数方程组 :定义,性质.向量与矩阵范数的相范数容性,等价性 -1 ( )mcond AA A方程组的条:件数 * 1 * xx b bAA bx (1)当右端向量有扰动 * * ( ) xx xA ACond A Axx (2)当系数矩阵有扰动 1 , 1 ( ) Ab xxbAk AxbA k

9、 A kcond AAA (3)当系数矩阵有扰动右端向量有扰动 其中 第第2章章 线性代数方程组线性代数方程组 xGxd迭代算:构造,法判断收敛 -11 1 ()GDEFID A dD b Jacobi: -1 1 () () GDEF dDEb Gauss-Seidel: 1, TH2.6 收敛 G则迭代 性判定定理 格式收敛 ,AJacobiTH2.7 为严格对角占优格式收敛 ,-AGauss SeidelTH2.8 为严格对角占优格式收敛 ,-;2-,AGauss SeidelD AJacobiTH2.9 对称正定收敛对称正定收敛 (1)( ) )1 kk xGxdG TH2.10 迭代

10、格式收敛的充要条件为 ( TH2.11 迭代格式的误差估计 第第2章章 线性代数方程组线性代数方程组 1 1 ,_,_,_ 0 1 00 4 AAA 1 1 -1 2 例:矩阵A=则 1 1 3 1 21 :12, 1 , T AaGGG a aa 例 若矩阵可以分解为的形式 其中 为下三角阵 且对角元均为正问 的取值范围 并请按此要求将此 分解 36, 37PP 第第2章章 线性代数方程组线性代数方程组 123 123 123 5210 :24225 2465 - xxx xxx xxx JacobiGauss Seidel 例 考查方程组 的迭代格式,格式的收敛性. 123123 123

11、:(,) ,23 23 T xxxxxxx xxx 例 设则是否是范数, 是否是范数 第第3章章 数据近似数据近似 Lagrange Newton Hermit 多项式插值 插值 连续多项式插值 插值 插值多项式插值 分段一次插值 分段多项式插值 分段二次插值 分段三次样条插值 最小二乘近似 数据近似 第第3章章 数据近似数据近似 ( )( )( ) nn f xpxR x TH 3.1 经过给定插值点的插值多项式唯一 多项式插值 0 ( )( ) n nii i L xl x y Lagrange 插值 0 ( ) ( ) ( )() ()( ) n ii i ii x l xxxx xxx

12、 001001201 01201 ( ),(),()() + ,()()() n nn Nxy xy x xxxy x x xxxxx y x x xxxxxxxx Newto 插 n值 101201 ( ),()()() nnn Nxy x x xxxxxxxx 差商性质1,对称性 ( ) 1 ( ) ,., , ! k iii kii k y y x xxx x k 差商性质2, 第第3章章 数据近似数据近似 ( ) 1 ( ) ,., ! k i iii k Newton yx y x xx k 个 计算带导数条件的插值多项式 利用差商性质2,使用插值多项式的思想进行构造 Hermit

13、插值 插值多项式的误差 (1) 0 01 3.2 ( )( )-( ) ( ) ( ) , (1)! ,., ( ) nn n n n THR xy xP x y xx x n y x xxx (P97) 第第3章章 数据近似数据近似 分段插值多项式 2 1221 1 3.3() max( ) max 8 ii a x bi THE gMMy xxx 分段一次多项式的误差 3 2331 1 3.4() max( ) max 12 ii a x bi THE gMMyxxx 分段二次多项 式的误差 2 221 1 3.5( )- ( ) max( ) max 2 ii a x bi THy xs

14、 xMMy xxx 分段三次样条插值多项式的误差 第第3章章 数据近似数据近似 最小二乘法 111211111211 212222212222 1212 ()()() ()()() ()()() nn nn nnnnnnmmnm TT aaabg xgxgx aaabg xgxgx G aaabg xgxgx G GaG y 得到方程组 或法方程 12 1122 1/2 2 2 1 ,(1,2,.,)( )(1,2,., ), ,.,(), ( )( )( )( ) ( ( ) iik n nn m ii i x yimgx kn mn p xg xgxgx Ep xy 给定数据点和一组函数求

15、系数 假定使函数 满足达到最小 1 ,.() TT aG GG y 可以证明 最小二乘问题的法方程总有解存在 QR分解 R QG O T R GQ O 第第3章章 数据近似数据近似 012 012 1) ( ) xxxx f xyyy 例.求满足以下插值条件的插值多项式 ( 012 012 1 2)( ) ( ) xxxx f xyyy fxy ( 012 02 1 3)( ) ( ) xxxx f xyy fxy ( 第第3章章 数据近似数据近似 (0)(0)0,(1)(1)1,(2)1ppppp 例.求不超过四次的插值多项式,满足条件 (4) ( ),( )( ),( )( ), ( )1

16、1, 2,( ) 12 ( )13 ( )11 iiii p xp xf xp xfx fxxp x x f x fx 例.求不超过三次的多项式满足条件 若求的误差界 .( ),0,1,2,., ,(,() 1 ( ),( )()() 1 (1) kkk k nnnkk k n x f xxnxf x x x pxpxpxf x x p n 例设取以为插值数据点 做插值多项式则满足 试求 第第3章章 数据近似数据近似 01 01 0 ,., ( ) ,., ( ) n n i n i i x xx f x f x xx x 例.设节点互异 试证明 01 00 ,., ( ) ( )( ) (

17、)( ) ()( ) n nn iii ii ii x xxLagrange x L xl x f xf x xxx 解:由节点互异 则插值多项式为 0 ( )( ) ()( ) n i i ii f xx xxx 0 ( ) ( ) n i i f x x 因此,该多项式最高项的系数为: 01 001001201 01011 ,., ( ),(),()() ,()()() n nn x xxNewton N xyy x xxxy x x xxxxx y x xxxxxxxx 另一方面,由节点形成的插值多项式为 01 , n y x xx该多项式最高项的系数为:因此得证 第第3章章 数据近似数

18、据近似 1 01 0 (0,1, ),(0)( 1) ( ) n nn iiin i i x inlxx xx l xLagrange 例.设为互异实数 试证明 其中为插值多项式 0 ( )( ) ( )( ) n iin i f xl x f xR x 证明:构造lagrange插值多项式,有 11 0 ( ),(0)0(0)(0) n nn iin i f xxflxR 取 (1) 01 ( ) ( )( )( )()()() (1)! n nn f R xxxxxxxxx n 1 01 (0)( 1) n nn Rx xx 得证 第第3章章 数据近似数据近似 3 ( )234(),1,2

19、,3_, 0,1,2,3_, 0,1,2,3,4_ f xxaxaf ff 例.设为实数 则差商 32 ( )25( , ,),1,2,0, 0,1,_ f xxpxqxc p q cfm fm 例.设均为实数 若差商 则 53 4 ( )2009200720062005,2, 1,0,1,2 ( )_ f xxxx L x 例.设则以为 插值节点的不超过四次的插值多项式 ( )23 1234 ( )0.7 f x x f x 例.给定以下的数据点,利用插值多项式,计算在 到 之间的根的 近似值 第第3章章 数据近似数据近似 01 2 101010 001 22 010101

20、 ( ) , , ()(2)()()() ( )()()() ()() ( )( )( ) f xa bxxa b xxxxxxxxxxx p xf xfxf x xxxxxx R xf xp x 例.设在区间上有三阶连续导数,有相应的插值多项式 试求此插值多项式的余项的表达式 001100 ()(),()(),()()p xf xp xf xp xfx解:由于 因此插值多项式的余项公式为: 2 00101 2 01 ( )( )( ) , () () 1 ( )() () , 6 R xf xp x f xxx x xxxx fxxxxa b 第第3章章 数据近似数据近似 - 4664 (

21、)1.060.5671.43 1.77 ( )sincos x f x p xAxBx 例.已知函数f(x)有以下测试数据 求形如最小二乘近似 解:构造法方程 sin()cos()1.06 44 0.7070.7071.06 sin()cos()0.567 0.50.8660.567 66 0.50.8661.43 sin()cos()1.43 66 0.7070.7071.77 sin()cos()1.77 44 AB AB A B AB AB 0.7070.7071.06 0.50.8660.567 , 0.50.8661.43 0.7070.7071.77 Gy 令得法方程 第第3章章

22、数据近似数据近似 0.7070.707 0.707.500.500.7070.50.866 .707.866.866.7070.50.866 0.7070.707 1.06 0.707.500.500.7070.567 .707.866.866.7071.43 1.77 A B 1.5003 02.501.25 A B 即 2.00 .500 ( )2sin0.5cos A B f xxx 解得 因此 第第3章章 数据近似数据近似 ( ) 01.4452.8904.3355.780 1.84192.9633 18.23698.7410529.2178 ( ) x f x x y p xe 例.

23、已知函数有以下测试数据 求形如的最小二乘近似函数 ( ) ln( )ln p x p xx 解:对两边求对数,有 ( )ln( ),ln, ( ) f xp xAB f xABx 令则最小二乘函数变为 01.4452.8904.3355.780 ln0.61071.08632.90344.59256.2714 x y 相应的数据 构造法方程. 下略 第第4章章 数值微积分数值微积分 (1) -(3) (5) () () () m Newton CotesSimpsonm Cotesm Simpson Cotes 梯形公式 公式公式 公式 等距结点 复化梯形公式 二阶 复化求积公式 复化公式 四

24、阶 复化公式 六阶 不等距结点:Ga Th 数值积 4.9 uss型求 (构造方法 积公式,利用正交多项 ) TH 4.11 式进行构 TH4. 造 12 分 Romberg积分:利用低精度的求积公式,构造高精度的公式 待定系数法:利用代数精度的定义求得最 4-39计算系数 4-4 高代数精度的求积公式 0计算误差 135.47 4.1PTh 136.48 4.2PTh 136.49 4.3PTh 140.4 13 4.4PTh 140.4 14 4.5PTh 140.4 15 4.6PTh 第第4章章 数值微积分数值微积分 01001 11010 2 0012 2 102 2012 11 (

25、)()()( )() 2 11 ()()()( )() 2 1 ()3 ()4 ()()( ) 23 1 ()()()( ) 26 1 ()()4 ()3 () 2 fxf xf xfxx h fxf xf xfxx h h fxf xf xf xf h h fxf xf xf h fxf xf xf x h 数 两点公式 一阶导数公式 三点式 分 公 值微 2 2 (4) 001212 2 2 (4) 1012 2 2 (4) 201212 2 ( ) 3 1 ()()2 ()()( )() 6 1 ()()2 ()()( ) 12 1 ()()2 ()()( )() 6 h f h fxf

26、 xf xf xhff h h fxf xf xf xf h h fxf xf xf xhff h 二阶导数公式 待定系Taylor 数法:利用公式可求得最高计算精度的微分公式 第第4章章 数值微积分数值微积分 . ( )() 2 b a ab f x dxba f 例试导出中矩形公式,并给出其误差公式 2 012 0 . ( )(0)( )(2 ) h f x dxA fA f hA fh 例确定以下公式中的系数,使其具有尽可能高的代数精度 (1) 1 123 1 11 ( )()(0)( ) 22 f x dxA fA fA f (2) 1 1122 1 ( )()()f x dxA f

27、xA f x (3) 第第4章章 数值微积分数值微积分 1 1 1 1 .( ) , ( ), (1,2,.,1)( ), ( ). ( ) ( )(). : (1) 0,( )( ) k ik ii n b kk a k n kkiji i xa bx x inx l xxLagrange x f x dxA f x k jn kjAxx 例设是定义在区间上的关于权函数的正交多项式族 节点为的零点 为以为节点的插值基函数 为高斯型求积公式 证明 当时 1 1 2 1 0 (2) ( ) ( ) ( )0, (3) ( ) ( )( ) b kj a n bb k aa k x lx lx d

28、xkj x lx dxx dx 第第4章章 数值微积分数值微积分 0001020 . ()()()(2 )fxA f xA f xhA f xh 例确定如下的数值微分公式的系数,使其对尽可能高次的多项式精确成立 并给出误差表达式 1 1 0 2488 .( )0.45675, 0.47117,0.47446,0.47612,_ f x dxS SSSS 例按照复化Simpson公式计算的数值微分值为 则 的误差近似为 第第5章章 非线性方程求解非线性方程求解 (1)( ) ( ) (1)( ) ( ) ( )( -1) (1)( )( ) ( )( -1) () () - () - -() (

29、)-() kk k kk k kk kkk kk xx f x Newtonxx fx xx xxf x f xf x 简单迭代法 迭代法迭代法 非线性方程求解 割线法 区间法:二分法 5.1 (1) , , ( ) , (2) ( )- ( ) 01 5.2 ( )1 THxa bxa b xyq xyq THxs 收敛性 * 1 (),( )( ) 1 xxxx 取构造 收敛性的改善 第第5章章 非线性方程求解非线性方程求解 00 5.4(1)( ) ( )0 (2) ( ),( )0 (3) ( ) (4)()()0 THf Newton a f b fxfx fx f xfx 不变号

30、且 不变号 迭代格式的收敛性 (1)* ( )* lim0, k p kk xx p xx 若 则称收敛速度 收敛速度 为 阶收敛 第第5章章 非线性方程求解非线性方程求解 32*(1)( )-1/2 -101.5,(-1) kk xxxxx 方程在邻近有根讨论迭例.代格式的收敛性 -1/2 ( )( -1)xx解: 令 -3/2 1 ( )( -1) 2 xx 1.4,1.6取区间 * 1.4,1.6 (1.4)1.5811, (1.6)1.29099x有 ( )0,( )xx且在此区间上即单调减 -5/2 3 ( )( -1)0 4 xx又( )x单调增 ( )(1.4)1.9761x *

31、 ( )( )()( )xxxxxxxx 可知 ( ) x迭代格式不收敛 (1.5)1.414 取 1/2 1(1)1.414 ( )( ) 12.414 xx xxx 构造 则此迭代格式收敛 第第5章章 非线性方程求解非线性方程求解 lim222222 k 试用迭代法明例原理证 . (1)( )(0) 2,0 ( )2,2( )0 kk xxx xxxx 解: 构造迭代格式 则当时, 1 ( )0,( ) 2 2 xx x 即单调增 ( )202x 5/2 1 ( )0 4(2) x x * 0,2,( )0,2,( )15.2xxxTh x 考虑区间有由知,对任何初始点 迭代格式都收敛于不

32、动点 * 2,2xxx由方程知其不动点 ( )x单调减 ( ) 2 k x因此, 第第6章章 常微分方程数值解法常微分方程数值解法 0 ( )( , ( ) , ( ) y tf t y t ta b y ay 初值问题 1.数值微分法 2 2 1 ( ,) ( , )( )() 2 iiiiii h Euleryyhf t yE t hyo h 公式 2 2 111 (,) ( , )( )() 2 iiiiii h Euleryyhf tyE t hyo h 后退公式 2.数值积分法 11 1 1 ( )( , ( )( )( , ( ) ( )()( , ( ) ii ii i i tt

33、 tt t ii t y tf y y ty t dtf y y t dt y ty tf t y t dt 3 3 111 ( ,)(,) ( , )( )() 212 iiiiiiii hh yyf t yf tyE t hyo h 梯形公式 111111 5 (5)5 (,)4 ( ,)(,) 3 ( , )( )() 90 iiiiiiii ii h yyf tyf t yf ty h E t hyo h Simpson公式 第第6章章 常微分方程数值解法常微分方程数值解法 Adams公式 2(2) 1011 ( , )( ) kk iiiiki kii h yyb fb fb fE

34、t hrhy A 显示公式 01 *2(2) 111 ( , )( ) k kk iiiii kii h yyb fb fb fE t hr hy A 隐示公式 3.待定系数法 111 10 kk ijijjij jj yyhf 1k 当时为单步法1k 当时为多步法 0 0当时为显式公式 0 0当时为隐式公式 第第6章章 常微分方程数值解法常微分方程数值解法 4.预估-校正公式 (1)利用两个同阶公式,相同步长 _ 1(1)1(1) 111121 _ 1111 ()-( ) ()-() ()() pppp iiii iiii y tyhyy tyhy y tyyy _ 1111 () iiii

35、 y tyyy (2)利用两个不同阶公式,相同步长 _ _ 1 1111 ()()/ 1/ p iiii hh y tyyyh h (3)利用同一个公式,不同的步长 和计算 第第6章章 常微分方程数值解法常微分方程数值解法 1321 12111 ( 9375955 ) 24 (4) (5199 (,) 24 iiiiii iiiiiii h pyffff ABM h yyffff tp 1321 11111 4 (22) 3 Milne-Simpson (4(,) 3 iiiii iiiiii h pyfff h yyfff tp 1 111 ( ,) :( ,)(,) 2 iiii iiiiii pyhf t y h yyf t yf tp 预估: Heun方法 校正 第第6章章 常微分方程数值解法常微分方程数值解法 1321 11 11111 4 (22) 3 28 Milne-Simpson() 29 4(,) 3 iiiii iiii iiiiii h pyfff mpyp h yyfff tm 预估校正 1321 11 12111 1111 4 (22) 3 112 () 121 13 (9)2(,)