张韵华编著 数值计算方法解题指导 SHUZHI JISUAN FANGFA JIETI ZHIDAO 里恭
参 论 随着计算机和计算方法的飞速发展，几乎所有学科都走向定量化和精确化，从而产 生了一系列计算性的学科分支，如计算物理学、计算化学、计算生物学、计算地质学 计算气象学和计算材料学等，计算数学中的数值计算方法则是解决“计算”问题的桥梁 和工具。我们知道，计算能力是计算工具和计算方法效率的乘积，提高计算方法的效率 与提高计算机硬件的效率同样重要。科学计算已广泛用于科学技术和社会生活的各个领 域中。 数值计算方法是一种研究并解决数学问题的数值近似解方法，简称计算方法。计算 机是数值计算方法最常用的计算工具，随着计算机技术的迅速发展和普及，计算方法课 程已成为所有理工科学生的必修课程。 计算方法是一门理论性和实践性都很强的学科，计算方法既有数学类课程的抽象性 和严谨性的理论特性，又有实用性和实验性的技术特征。 在学习计算方法课程中，对数学系信息和计算科学专业及计算机系的学生，教学内 容侧重计算方法的理论部分；对一般理工科的学生，教学内容侧重计算方法的实用性和 实验性部分。本书的宗旨既不以严谨理论为主导，也不是全篇数据的数值计算，而是两 者兼顾，兼收计算方法的基本理论和实用性。以方法为中心，以例题为载体，围绕方法 给出简单的典型的数值例题，通过例题进一步理解计算对象、计算公式、计算的限定条 件和计算步骤。为适合不同层次的读者，对有一定难度的例题标以星号(*)，部分关 于计算方法的收敛性和稳定件的证明题型也都标以星号，这些例题的内容已经超出理工 科计算方法课程的范围。 本书作为学习数值计算方法课程的辅导教材，与科学出版社2002版《数值计算方 法和算法》教材配套，其顺序为“插值”、“数值微分和数值积分”、“曲线拟合”、“非线 性方程求根”、“解线性方程组的直接法”、“解线性方程组的迭代法”、“计算矩阵特征值 和特征向量”和“常微分方程数值解”。每一章都给出基本内容、常规和典型例题列举 及点评、程序示例、习题和答案。 在每章的“基本内容”中，列出本章内容要点和核心计算公式，并给出部分计算公 式的算法描述。用算法容易准确而简便地描述计算公式，在算法中能简洁地表达计算公 式中的循环和迭代等操作，缩短了从方法到在计算机上实施的距离。近年来在国外的计 算方法教材中算法也是重要的组成内容，例如，由教育部高等教育司推荐的国外优秀信 息科学与技术系列教学用书《数值分析》(Numerical Analysis,Richard L.Burden著) 中给出大部分计算方法的算法。有了方法的算法，也就容易将它转化成C或Pascal等语 言的程序上机运行了。 在每章的“例题汇集”中，以计算题为主体，将一些定理的证明和算法用例题形式 给出，有利于巩周课堂教学效果。在部分例题中给出解题引导和点评，目的是指导解题 思路和拓宽理论背景。本书以普通高校理工科学生为主要对象，特别要说明的是标以星
号的例题，其教学内容超出对一般理工科学生的要求，是为数学系信息和计算科学专 业以及计算机系的学生提供的，也可供对计算方法有兴趣的学生参阅，部分例题附有 些用符号计算语言Mathematica编写的程序。 在每章的“程序示例”中，给出用C语言编写的方法的程序和计算实例，这些程 序基于数值计算公式，没有进行优化处理，其目的是通过编程上机，加深对方法运行过 程的理解，训练和提高学生计算机应用技术能力和水平。通过学生自选语言平台，在计 算机上编程序做计算方法的作业，在编程中领会和理解计算方法的计算要领和步骤，在 编程中体会问题的条件和限制范围，在编程中理解一般问题和特殊问题的区别。在数值 实验中观察误差的影响，通过误差量来观察计算方法的适应范围。 在每章的“习题”中，给出部分习题和简要答案 希望通过例题和习题帮助学生进一步理解计算方法中的逼近和迭代等数学思想，掌 握常用的数值方法，获取近似计算的能力，激发学生的学习兴趣，扩大学生数值计算的 知识面，并能触类旁通地应用到各自的科研和技术领域中，培养学生的数学综合分析能 力和计算能力 奚梅成教授多年来一直担任中国科技大学数学系的“数值分析”和“线性代数计算 方法”课程的主讲老师，他治学严谨，教学经验丰富，他为本书提供了许多有深度的例 题并核查了大部分例题；本书“程序示例”部分由中国科技大学数学系博士生窦斗完 成；博士生刘晾林核查和验算了所有例题，在此向他们深表感谢。 还要衷心感谢科学出版社赵卫江编辑，她在本书和《数值计算方法和算法》的出版 过程中给了作者很大的帮助，并为本书编写提出了建设性的建议。 编者 2003年3月
目 录 第1章插值 11基本内容.1 1.2例题汇集4 13程字示例.44.+.4 20 1.4习题.24 第2章数值微分和数值积分. 28 2.基木内容 28 22例汇集.*.*. 2 2.3 程序示例 48 51 第3章曲线拟合 455 3基本内容. 3.2例题汇集 56 3,3程字示例.” 6 3.4习题. 71 第4章非线性方程求根 75 4.1基本内容. 75 4.2例题汇集. 79 4.3习题. 90 第5章解线性方程组的直接法. 93 5.1基本内容.9 5.2例题汇集. 96 5.3程序示例 ,108 5.4习题. 10 第6章解线性方程组的迭代法. 113 6.1基本内容. 13 6.2例题汇集 11 6.3程序示例. 127 6.4习题 133 第7章计算矩阵特征值和特征向量 136 71基本内容 ·136 7.2例题汇集 140 7.3程序示例 151 7.4习题 .153
第8章常微分方程数值解.155 8.1 基本内容 8.2例题汇集. 7 8.3程序示例 16 主要参考文献： 176
第1章插值 1.1基本内容 1.插值定义 设f(x)是定义在区间[a,b]上的连续函数，x0,x1,.,xm是[a,b]上n+1个互不 相同的点，中是给定的某一函数类。若上有函数(x),满足 p(x）=f（x）,i=0,1,.,n 则称9(x)为(x)关于节点01，x,在上的插值函数：称x01,为插值 节点：称(x,f八x)(i=0,1,.,n)为插值型值点，简称型值点或插值点；f(x)称为被插 函数。 2.拉格朗日(Lagrange)插值多项式 给定(，f(x)(i=0,1,.,n;x互不相同)，构造次数至多为n的插值多项式 L(): Lx)=会4e） -含) 称L(x)为f(x)关于x0,21,.,的n次拉格朗日插值多项式，它满足 Ln(x:)=f(x）,i=0,1,",n 可以证明插值多项式Ln(x)存在并惟一。 3,插值多项式的截断误差 设Ln(x)是在[a,b]上关于(x,f(x)(i=0,1,.,n;x:互不相同)的n次插值多 项式，f(x)在[a,b]上有n阶连续导数，了"+D(x)在[a,b]上存在，则插值多项式Lm(x) 的截断误差为 Rn(x）=f(x)-Ln(x）= G- e=(x)∈[a,b] (1.2) 4.差商的定义 (1)设x0≠x1,称 +1
fo]=f)-fro) 是f(.r)关于xo,x1的一阶差商。f(.x)在x的零阶差商为f[ro]=f(xo)。 (2)设点r1,互不相同.f(x)关于点x0,x1,.4的k阶差商为 几n1.,4]=12小-f八04.4 (1.3) 5.差商的性质 mn小-名n (2)若i0,i1.,为0,1，.，k的任一排列，则 几01]=f[x,.,] (1.4) (3)设>(x)存在，则 f01,】=m( (1.5) n1 6.牛顿(Newton)插值多项式 关于型值点(，f(x,)(i=0,l,.,:互不相同)，次数至多为n的牛顿插值多 项式为 N(r)=fro]+fro.(x-xo)+fro.x1,x(-xo)(x-x1) +.+f几.x0,x1,.,xt](x-x0)(x-x)小.(x-xm-i） (1,6) 插值误差为 Rn(x)=f[x,o,.,xn](x-x0)(x-x1).(x-xm） 注：由橘值多项式的旅一性，f(x)关于x01,x,的拉格期日插值多项式及牛领 插值多项式是同一多项式，只是表达形式不同而已。 7.埃尔米特(Hermite)插值 如果在给定的节点处，不但要求插值多项式的函数值与被插函数值相同，同时还要求 在节点处插值多项式的一阶直至指定阶的导数值也与被插函数相应阶的导数值相同，这 类插值称为埃尔米特插值，或称为密切插值(osculating polynomial)。 插值条件： d ,i=0,1,.,n友=0,1，.，m (1.7) 在插值条件(1.7)式中，当m:=0时，即为拉格朗日插值；当m,=1时的埃尔米特插 值，也称二重埃尔米特插值。 设f(.x)具有一阶连续导数，给定n+1个插值点的函数值和导数值(x,f(x,), 广(x,)(1=0,1,n):若有至多为2”+1次的多项式函数H2m+1(x)满足 H2n1(,）=f(x,）,H3n+1(x,）=f(x,),i=0,1,.,n 2
则称Hm(x)为f(x)关于节点x(i=0,1,n)的埃尔米特的插值多项式，或称 H2m+1(.x)为f(x)的二重密切插值；x,(i=0,1,.,n)为二重插值节点，于是前而的拉格 朗日插值和牛顿插值形式可称为单重节点插值，而更一般的埃尔米特插值，不同节点的重 数可以不同。例如，在1.2节例1.15中，a为三重节点，b为一重节点。 下面是插值条件(1.7)式中”=1和m,=1的埃尔米特插值多项式。 给定f(.x0)=,f(.x1)=y,f(xo)=m0,f(x1)=m1,r0≠x1,fx)关于x0,x 的埃尔米特插值多项式为 H3(.x）=(1-2(.x-x0)10(x0)6(x)f(x0）+(1-2(x-x1)l(.x1)1(.x)f(.x) (r-x0)()f (zo)+(x-x1)()f ( w-%+1-2二4- H()=1-20x-x2 ri-xo(ri-xoy lro-i mo+(r-r)zt t-ro]m (1.8) 8.差商型埃尔米特插值 用牛顿插值也能构造埃尔米特插值。例如，给定(x,f(x),∫()(i=0,【, n),定义序列20=x0,1=x0,2=x1,之3=T1,.,2n=无n,21+1=a,即 22=22i+1=,i=0,1,.,n 令 12]=e2)-2- ，i=1,2,.,n 22:-x2i-1 f[2i,2i+1]=f(）, i=0,1,.,n 得到差商型埃尔米特插值公式： he)=i+nlr-o-）.9 9.三次样条函数 给定区间[a,b]上n+1个节点a=x0<x1<.<xm=b和这些点上的函数值 f(x,)=y,(i=0,1,.,n)。若S(x)满足S(.x)=y(i=0,1,.,n):S(x)在每个小区 间[.x,1]上至多是一个三次多项式：S(x)在[a,b]上有连续的二阶导数，则称S(.x) 为f(x)关于剖分a=x0<x1<<xn=b的=次样条插值函数，称x0,x1,.,xn为样 条节点。 10.M关系式 给定插值点(x,f(x)(i=0,1,n:x互不相同)，并设S(x,)=M,(i=0, 1,.,n)利用在节点x:的函数值、一阶导数和二阶导数的连续性得到关于M,的M关 系式： 4M-1+2M+入M+1=d,i=1,2,.,n-1 (1.10) ·3
其中： f（x)= h;=x+1- ha Ai=hi+hi-l 4=1- 641-5-当=6x4西小 di=ha+hit hi h:-1 附加两个边界条件，解出方程组(1.10)，得到样条函数表达式： S）=1-xPM+(x-P户M+1=x%+e-xa 6h: h: -[(1-x)M+(红-z)M] (1.11) x∈[x4,x+1],i=1,2,.,n 11.m关系式 给定插值点(x4,(x,)(i=0,1,.,n;,互不相同)，并设S(x)=m:(i=0,1,. n)。利用在节点x,的函数值、一阶导数和二阶导数的连续性得到关于m:的m关系式： 入：m,-1+2m+hm+1=G,i=1,2,.,n-1 (1.12) 其中： f八x,)= h:=工+1-x hi A=+- =1-入 c=3(af[无，-1，x,]+4f[x,x+1]) 附加两个边界条件，解出方程组(1.12)，由埃尔米特插值多项式(1.8)得到样条函数 表达式： s(x)=1-2r-五]z-x41]2 a-xm m +1-24x-五]2 x-x+1+（x二+11-G%, x∈[x,xi],i=1,2,n (1.13) 1.2例题汇集 例1.1插值函数作为被插函数的通近，可以用作函数值的近似计算。 4
已知27=3,64=4,125=5，构造二次拉格朗日插值多项式。 (1)计算100： (2)估计误差并与实际误差相比较。 解(1)以插值点(27,3)，(64,4)，(125,5)代人插值公式(1.1)，得 L(x)=lo(x)f(xo)+(x)f()+12(x)f(z2) (x-x)(x-x2) = (x-x0)(x-x2 o-0-o+-1-fx） +(-) （2-xo(x2-fx2) 27-6427-12×3+-27x-125) =x-64)(x-125 64-27)64-125×4 (x-27)(x-64) +(125-27125264× .100≈L(100) -980”-×3+40=别80×4 (64-27)(64-125) +10-27)100-64 025-27)125-64×5 =4.68782 (2)由误差公式 R(x)=9(2(z-27z-64(z-125) 记x）=,8(x)=9,(x)在[27,1251上是单调递减函数。 |3(x)川≤f3(27)≈5.64503×105 ÷1R（10)1≤2(100-27100-6410-125)≈0.618131 实际误差：|/100-L(100)川=0.04623 例1.2用插值点(2,4)，(3,9)，(5,25)分别构造拉格朗日插值函数和牛顿插值函 数，并计算L(3.5)和N(3.5)。 解(1)以插值点(2,4)，(3.9)，(5,25)代入插值公式(1.1)，得 (x-x1)(x-x2) （x-x0)(x-x2) (x-x0)(x-x1) -告沿-}×4+告-×9+告-张指-易×25 (2-3)(2-5) 4(）=号x-3x-5)-x-2x-5)+2x-20x-3) ·5