1、数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 计算方法（B）全册精品 完整课件 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 计算方法（B） 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 第0章 绪论 计算方法的作用 计算方法的内容 误差 一些例子 数 学 系 Univ
2、ersity of Science and Technology of China DEPARTMENT OF MATHEMATICS 现实中，具体的科学、工程问题的解决： 实际问题实际问题 物理模型物理模型 数学模型数学模型 数值方法数值方法 计算机求结果计算机求结果 计算方法是一种研究并解决数 学问题的数值近似解近似解方法 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 数值数值 分析分析 输入复杂问题或运算输入复杂问题或运算 .),(,)( ,ln, xf dx d dxxf bx
3、Axax b a x 计算机计算机 近似解近似解 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 计算方法的特性 理论性：数学基础 实践性 计算方法连接了模型到结果的重要环节 随着计算机的飞速发展，数值分析方法已深入到计算 物理、计算力学、计算化学、计算生物学、计算经济学等 各个领域。本课仅限介绍最常用的数学模型的最基本的数 值分析方法。 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATI
4、CS 学习的目的、要求 会套用、修改、创建公式 编制程序完成计算 课程评分方法课程评分方法 (Grading Policies) 总分总分 (100) = 平时作业平时作业(20)+上机作业上机作业(10)+期末期末 (70) 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 3、以E-Mail形式交： E-Mail: 主题 : PB05023001 内容 : 一次作业一个附件，并在内容中写出运行结果 上机作业要求 1、编程可以用任何语言； （C,C+,Matlab,Mathematica
5、,Delphi,Fortran,等）不允许 使用内置函数完成主要功能 2、结果输出要求小数点后至少13位 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 内容 2、数值代数线性代数的数值求解，如解线性方程组、数值代数线性代数的数值求解，如解线性方程组、 逆矩阵、特征值、特征向量逆矩阵、特征值、特征向量 3、微分方程常微分，、微分方程常微分，Runge-Kutta法、积分法法、积分法 1、数值逼近数学分析中的数值求解，如微分、积分、数值逼近数学分析中的数值求解，如微分、积分、 b a aF
6、bFdxxf)()()( DDxbAx ii / 20 107 . 9 ,20n 100亿/秒，算3,000年，而Gauss消元法2660次 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 误差 绝对误差 设 * x为精确值， x 为近似值， xxe * 为误差或绝对误差 例如： ) 1ln()(xxf作Taylor展开， 10 , )1)(1( ) 1() 1( 1 1 1 1 n nn i n i i xn x x i 舍弃，即为误差 数 学 系 University of Scie
7、nce and Technology of China DEPARTMENT OF MATHEMATICS 相对误差 * * * x xx x e er 称为相对误差 150分满考139，100分满考90，两者的绝对误差分别 为11和10，优劣如何？ 前者相对误差(150139)/150=0.073， 后者相对误差(100-90)/100=0.100 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 误差来源 原始误差模型误差（忽略次要因素， 如空气阻力）物理模型，数学模型 方法误差截断误
8、差（算法本身引起） 计算误差舍入误差（计算机表示数据 引起） 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 误差的运算 yx eeyxyx)()( * 1、 * yx ee yx 两相近数相减，相 对误差增大 |)e|e|(|y| |,xmax| )()()()( yx * * * yx exye xxyyyxyxyx2、 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 例子例子
9、 求根 012000 2 xx 005. 0 2 420002000 2 2 2, 1 xx 0050005. 0 1 2 420002000 2 1 2 2 1 x x x x 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS * * * * * * * * )()( yy yeex yy xxyyyx yy xyyx y x y x xy 3、 小数作除数，绝 对误差增大 误差的运算 数 学 系 University of Science and Technology of China
10、 DEPARTMENT OF MATHEMATICS 有效位数 当x的误差限为某一位的半个单位，则这 一位到第一个非零位的位数称位x的有效 位数。 有效位的多少直接影响到近似值的绝对误差和相对误差 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 一些例子 dx x x I n n 1 0 5 1、 n dxxdx x xx II n nn nn 1 5 5 5 1 0 1 1 0 1 1 则，我们有 构造方法如下： 5 6 ln , 5 1 01 II n I nn n I 1. 019
11、.0 , 1 5 1 81 II n I nn n I 2. 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS n 0 0.182 0.182 0.182 1 0.088 0.090 0.088 2 0.058 0.050 0.058 3 0.0431 0.083 0.0431 4 0.0343 -0.165 0.0343 5 0.0284 1.025 0.0284 6 0.024 -4.958 0.024 7 0.021 24.933 0.021 8 0.019 -124.540 0.0
12、19 n I n I n I 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 原因：对格式1，如果前一步有误差， 则被放大5倍加到这一步 称为不稳定 格式 稳定格式，对舍入误差有抑制作用 在我们今后的讨论中，在我们今后的讨论中，误差误差将不可回避，将不可回避， 算法的算法的稳定性稳定性会是一个非常重要的话题。会是一个非常重要的话题。 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS
13、0 1 yax ayx 2、 有时候，模型本身就是病态 （系数引入小变化，解产生大变化） 25.50 99. 0 xa 81.55 991. 0 xa 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 例：例：蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北纽约的一只蝴蝶翅膀一拍，风和日丽的北 京就刮起台风来了？！京就刮起台风来了？！ NY BJ 以上是一个以上是一个病态问题病态问题 /* ill/* ill- -posed problem*/posed problem*/ 关于本身
14、是病态的问题，我们还是留给数学家去头痛吧！关于本身是病态的问题，我们还是留给数学家去头痛吧！ 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Lab 01. 级数计算级数计算Hamming (1962) x取值取值, x = 0.0, 0.1,1.0 ; 10.0,20.0,300.00. 绝对误差小于绝对误差小于 1.0e-6. 输出输出 两列输出：两列输出： x 和和 (x) 如如 C fprintf: fprintf(outfile,%6.2f%16.12fn,x,psix);/*
15、 hererepresents a space */ 1 )( 1 )( k xkk x 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Sample Output ( represents a space) 0.001.644934066848 0.101.534607244904 . 1.001.000000000000 10.000.000000000000 . 300.000.020942212934 数 学 系 University of Science and Technol
16、ogy of China DEPARTMENT OF MATHEMATICS H.W. 给出计算如下式子的方法，以达到相当的精度 nn axaxf)()() 1 ( axaxfsin)sin()()2( axxxf 2 )() 3( 其中，()、()中x接近，()中xa 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 一些基本数学定理 介值定理 若f(x)在a,b上连续，则任意g在f(a)与f(b)之间，都存 在 , ca b使 f(c)= g 若f(x)在a,b上连续，x1,xn为a,
17、b内的点， g1,gn为 同号的实数，则存在 使 , a b 11 ( )( ) nn iii ii f x gfg 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 积分均值定理 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Taylor展开 数 学 系 University of Science and Technology of China DEPARTMENT OF MAT
18、HEMATICS 第1章 插 值 实际中，f(x)多样，复杂，通常只能观测到一些离散数据； 或者f(x)过于复杂而难以运算。这时我们要用近似函数g(x)来 逼近f(x)。 自然地，希望g(x)通过所有的离散点 概念 x0 x1 x2 x3 x4 x g(x) f(x) 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 定义： 为定义在区间 上的函数， 为区间上n+1个互不 相同的点， 为给定的某一函数类。求 上的函数 满足 )(xf ba, 0 n i i x )(xg nixfxg ii
19、 , 0 , )()( 问题 是否存在唯一 如何构造 误差估计 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 00 00 ( )( )( ) ()()()() nn iiinni g xaxax g xf xaxax 设 则 00011000 00111111 0011 ()()()() ( )( )( )( ) ()()()() nn nn nnnnnn axaxaxf x axaxaxf x axaxaxf x 所以 有解，当且仅当系数行列式不为系数行列式不为0 0 n ii a
20、数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 存在唯一定理 定理1.1 ： 为n1个节点， n+1维空间，则插值函数存在唯一，当且仅当 0 n i i x , 10n span 0 )()( )()( 0 000 nnn n xx xx 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 1. 与基函数无关 2. 与原函数f(x)无关 3. 基函数个数与点个数相同 特点：特点： 数
21、学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS , 1)( 2nn xxxspanx对应于对应于 则则 0 1 1 0 0 nij ji n n n xx x x Vandermonde行列式 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 多项式插值的Lagrange型 如何找？ 在基函数上下功夫，取基函数为 nn ii xl 0 )( 要求 ji ji xl ijji , 1 ,0
22、 )( 则 )()()( 0 i n i i xfxlxg 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 求 n ii xl 0 )( ，易知： )()()()( 110niiii xxxxxxxxaxl )()()( 1 110niiiiii i xxxxxxxx a 011 011 ()()()() ()()()() iin i iiiiiin xxxxxxxx l xxxxxxxx 0 ( )() n ni i xxx 记 ( ) ( ) ()() n i nii x l x x
23、xx 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 线性插值 01 0 1 10 1 0 )( , )( xx xx xl xx xx xl )()()()()( 11001 xlxfxlxfxL 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 二次插值 12 0 0102 ()() ( ) ()() xxxx l x xxxx 2001122 ( )() ( )( ) ( )(
24、) ( )L xf x l xf x l xf x l x 02 1 1012 ()() ( ) ()() xxxx l x xxxx 01 2 2021 ()() ( ) ()() xxxx lx xxxx 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS )3 , 3(),1 , 2(),0 , 0(),2 , 1( 例： ) 31)(21)(01( )3)(2)(0( )( 0 xxx xl )23)(03)(13( )2)(0)(1( )( 3 xxx xl ) 32)(02)(1
25、2( ) 3)(0)(1( )( 2 xxx xl )30)(20)(10( )3)(2)(1( )( 1 xxx xl )(3)(1)(0)(2)( 3210 xlxlxlxlxg 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 算法： fx=0.0 for(i=0;i=n;i+) tmp=1.0; for(j=0;ji;j+) tmp=tmp*(x-xj)/(xi-xj); for(j=i+1;j=n;j+) tmp=tmp*(x-xj)/(xi-xj); fx=fx+tmp*yi;
26、 return fx; 011 011 ()()()() ()()()() iin i iiiiiin xxxxxxxx l xxxxxxxx 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Lab02 Lagrange插值 2 1 ( ), 5,5 1 f xx x 对函数 构造插值，并求 55 max( )( )max()() ,5,0,100 10 iii xi i f xp xf yp yyi 插值节点取为： 10 5,0,1, i xi iN N (1) 21 5cos,0,1
27、, 22 i i xiN N (2) 对N=5，10，20，40比较以上两组节点的结果。 Chebyshev点 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 误差 )()()(xLxfxR nn 解： )()()( , 0 , 0)( , 0 , )()( 0nn in ini xxxxxkxR nixR nixLxf 求 ?)(xk 0)( and , 0, 0)( )()()()()( ?)(, 0 anix xtxtaktLtft aka i nn 设 易知 数 学 系 Univ
28、ersity of Science and Technology of China DEPARTMENT OF MATHEMATICS )(t 有n+2个零点 )!1( )( )( )!1)()()( 0)( , )1( )1()1( )1( n f ak nakf n nn n )()( )!1( )( )( 0 )1( n n n xxxx n f xR 由a的任意性 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 例：例：已知已知 2 3 3 sin, 2 1 4 sin, 2 1
29、 6 sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 解：解： 0 x 1 x 2 x 18 5 500 n = 1 分别利用分别利用x0, x1 以及以及 x1, x2 计算计算 4 , 6 10 xx利用利用 2 1 6/4/ 6/ 2 1 4/6/ 4/ )( 1 xx xL 这里这里 ) 3 , 6 (,sin)(,sin)( )2( xxx f
30、xxf 而而 ) 4 )( 6 ( !2 )( )(, 2 3 sin 2 1 )2( 1 xx f xR x x 00762. 0) 18 5 (01319. 0 1 R sin 50 = 0.7660444 ) 18 5 ( 50 sin 1 0 L 0.77614 外推外推 /* extrapolation */ 的实际误差的实际误差 0.010010.01001 3 , 4 21 xx利用利用 sin 50 0.76008, 00660. 0 18 5 00538. 0 1 R 内插内插 /* interpolation */ 的实际误差的实际误差 0.005960.00596 内插通
31、常优于外推。选择内插通常优于外推。选择 要计算的要计算的 x 所在的区间的所在的区间的 端点，插值效果较好。端点，插值效果较好。 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS n = 2 2 3 )( )( 2 1 )( )( 2 1 )( )( )( 4363 46 3464 36 3646 34 2 xxxxxx xL ) 18 5 ( 50 sin 2 0 L 0.76543 2 3 cos 2 1 ;) 3 )( 4 )( 6 ( !3 cos )( 2 x x xxxxR 0
32、0077. 0 18 5 00044. 0 2 R sin 50 = 0.7660444 2次插值的实际误差次插值的实际误差 0.000610.00061 高次插值通常优于高次插值通常优于 低次插值低次插值 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 事后误差估计 给定 1 0 n ii x 任取n+1个构造 )(xLn )( 1, 1 )( , 0 xLni xLni n n 如： 另取 则 )()( )!1( )( )( )( )()( )!1( )( )()( 11 2 )1(
33、 0 1 )1( n n n n n n xxxx n f xLxf xxxx n f xLxf 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 近似 )()( 2 )1( 1 )1( nn ff 则 )( )()()( )( )()( )( )( )()( 10 0 01 0 10 1 1 0 xLxL xx xx xLxf xL xx xx xL xx xx xf xx xx xLxf xLxf nn n n n n n n n nn n 数 学 系 University of Sc
34、ience and Technology of China DEPARTMENT OF MATHEMATICS Home Work 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Lagrange 插值的缺点 无承袭性。增加一个节点，所有的基函数都要重新计算 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 为实数 Newton型多项式插值 , 110n xxx, 10n xxx 且
35、 1 ( )( )( ) , 0, ninii NxNxf xin )()()( 011nnn xxxxaxq 同样 )()()( 10 nnn xxxxaxq )()()( 1 xqxNxN nnn 承袭性承袭性： )()()( 11 xqxNxN nnn 1 n P 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS )()()()( 10010 nnn xxxxaxxaaxN 而且有： )()()()()( )()()()( )()()( )()( 10010 21202202102
36、101101 000 nnnnnnnn n n n xfxxxxaxxaaxN xfxxxxaxxaaxN xfxxaaxN xfaxN 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 这样： )( 00 xfa 01 01 1 )()( xx xfxf a 1 02 02 12 2 )()(1 a xx xfxf xx a 30 312 323031 ()()11f xf x aaa xxxxxx 数 学 系 University of Science and Technology o
37、f China DEPARTMENT OF MATHEMATICS 0 101 0 01 01 10 , , )()( , xx xxfxxf xxf xx xfxf xxf k kk k 称为k阶差商 称为1阶差商 定义：差商差商 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 差商的一个性质差商的一个性质： （用归纳法易证） 对称性： , 0 0 k iik xxfxxf 定义关键：找不同的元素相减作分母 的任意排列是kii k ,0, 0 数 学 系 University of S
38、cience and Technology of China DEPARTMENT OF MATHEMATICS )( 00 xfa , )()( 10 01 01 1 xxf xx xfxf a , 1 )()(1 0120102 12 1 02 02 12 2 xxxfxxfxxf xx a xx xfxf xx a 由归纳： , 0nn xxfa 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS Newton插值构造 )(, 00 xfx )(, 11 xfx )(, 22 xfx
39、)(, nn xfx , 10 xxf , 12 xxf , 1nn xxf , 012 xxxf , 21nnn xxxf , 0 xxf n 1、先构造差商表 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 例子 2点Newton型插值 )( )()( )()( 0 01 01 01 xx xx xfxf xfxN 2、利用差商表的最外一行，构造插值多项式 )()(,)(,)()( 1000100 nnn xxxxxxfxxxxfxfxN 数 学 系 University of Sc
40、ience and Technology of China DEPARTMENT OF MATHEMATICS 差商表 求值 算法： for(i=1;i=i;j-) yj=(yj-yj-1)/(xj-xj-i); fx=yn; for(i=n;i=1;i-) fx=yi-1+(x-xi-1)yi-1; 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 问题：如果要做到增加一个点，而尽可能减少重 复计算，要如何改进前面的算法？ 数 学 系 University of Science and
41、Technology of China DEPARTMENT OF MATHEMATICS 一些性质 n i niiiiii i n n nn xxxxxxxx xf xxf x xLxN 0 110 0 )()()( )( , )()( 的系数一样 性质2 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 误差 0 0100 1 00 Newton( ) ( )( ), ()() ( )( ) ( )( ), ()() n iin n iinnnn n nnn xNx xaNtN tf
42、xx a txtx Naf a f aNaf xx a axax 另一方面 设插值为 则有为 显然 (1) 0 ( ) , (1)! n n f f xxa n 性质3 (1) 0 ( ) ( ) ( )()() (1)! n nnn f NxR xxxxx n 同样的误差为 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 差商性质总结 n i niiiiii i n xxxxxxxx xf xxf 0 110 0 )()()( )( , , 0 0 n iin xxfxxf ( ) 0
43、 ( ) , ( )! n n f f xx n nk nka xxfxPxf n k n , 0 , ,),()( 0 推论：若 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 011 , mm k k fmkf x xxx 若 则 PP 证明作为作业 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 1.4 Hermite插值 有时候，构造插值函数除了函数值的条件以外，还需要一定
44、的 连续性条件，如一阶导数值等，这种插值称为Hermite插值。 ( ) 00 ,( ),( ,( ),1,), Hermite nkn iiiiiii x f xx fxkk 定义：满足和条件的插值 称为插值 n iii n iii i xfxxfx k 00 )( ,)(, 1 和 满足一阶导条件为例，即每个点上还要以所有 称为二重密切Hermite插值 数 学 系 University of Science and Technology of China DEPARTMENT OF MATHEMATICS 例：例：设设 x0 x1 x2, 已知已知 f(x0)、 f(x1)、 f(x2)
45、 和和 f (x1), 求多项式求多项式 P(x) 满足满足 P(xi) = f (xi)，i = 0, 1, 2，且且 P(x1) = f (x1), 并估计误差。并估计误差。 模仿模仿 Lagrange 多项式的思想，设多项式的思想，设 解：解：首先，首先，P 的阶数的阶数 = 3 2 1 3 ) ( ) ( ) ( ) ( ) ( 0 i i i x h x1 f x h x f x P h0(x) 有根有根 x1, x2，且且 h0(x1) = 0 x1 是重根。是重根。 ) ( ) ( ) ( 2 2 1 0 0 x x x x C x h 又又: h0(x0) = 1 C0 )()( )()( )( 20 2 10 2 2 1 0 xxxx xxxx xh h2(x) 与与h0(x) 完全类似。完全类似。 其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1
