数值计算方法教案.doc

《计算方法》教案

课程名称： 计算方法
适用专业： 医学信息技术
适用年级： 二年级
任课教师： 张利萍
编写时间： 2011年 8月

新疆医科大学工程学院 张利萍

教案目录
《计算方法》教学大纲 3
一、课程的性质与任务 3
二、课程的教学内容、基本要求及学时分配 3
三、课程改革与特色 4
四、推荐教材及参考书 4
《计算方法》教学日历 5
第一章 绪论 6
第1讲 绪论 有效数字 6
第2讲 误差…………………………………………………………………………… …
第二章 线性方程组的直接法 12
第3讲 直接法、高斯消去法 13
第4讲 高斯列主元消去法 21
第5讲 平方根法、追赶法 27
第三章 插值法与最小二乘法 30
第6讲 机械求积、插值型求积公式 30
第7讲 牛顿柯特斯公式、复化求积公式 35
第8讲 高斯公式、数值微分 41
第9讲
第10讲
第12讲
第四章 数值积分与数值微分 46
第11讲 欧拉公式、改进的欧拉公式 46
第12讲 龙格库塔方法、亚当姆斯方法 51
第13讲 收敛性与稳定性、方程组与高阶方程 54
第14讲
第15讲
第五章 微分常微分方程的差分方法 57
第16讲 迭代收敛性与迭代加速 58
第17讲 牛顿法、弦截法 62
第18讲
第19讲
第20讲
第六章 线性方程组的迭代法 65
第21讲 迭代公式的建立 66
第22讲
第23讲
第24讲 向量范数、迭代收敛性 69
第25讲

80
《计算方法》教学大纲
课程名称 ：计算方法/Computer Numerical Analysis　B
学时/学分：54/4
先修课程 ：高等数学、线性代数、高级语言程序设计（如：Matlab语言）
适用专业 ：计算机科学与技术、信息管理与信息系统
开课学院（部）、系(教研室)：医学工程技术学院、医学信息技术专业
一、课程的性质与任务
计算方法是一门专业必修课。当前，由于科学技术的快速发展和计算机的广泛应用，学习和掌握计算机上常用的数值计算方法及有关的基础理论知识，并能用某种高级语言（如Matlab语言）将这些常用算法编程实现，这对于计算机专业的学生来说是非常重要的。
本课程着重介绍进行科学建设所必须掌握的一些最基本、最常用的算法，向高等院校有关专业的学生普及计算方法的知识。
二、课程的教学内容、基本要求及学时分配
（一）教学内容
1．引论
数值分析的研究对象、误差及有关概念、数值计算中应注意的一些原则。
2．线性代数方程组的数值解法
Gauss消去法、Gauss消去法的矩阵形式、主元消去法、三角分解法、迭代法、迭代法的收敛条件及误差估计。
3．插值方法
Lagrange插值、Newton插值、分段插值、Hermite插值、三次样条插值、数据拟合的最小二乘法。
4．数值积分与微分
机械求积、Newton-Cotes求积公式、复化求积、Romberg求积算法、Gauss求积公式、数值微分。
5．常微分方程初值问题的数值解法
Euler方法及其改进、龙格-库塔(Runge-Kutta)方法、线性多步法、收敛性与稳定性、一阶方程组与高阶方程。
6．方程求根的数值方法
二分法、迭代法、迭代过程的加速、Newton迭代法、Newton迭代法的几种变形。
（二）基本要求
1．了解数值分析的研究对象、掌握误差及有关概念。
2．正确理解使用数值方法求方程的解的基本思想、数学原理、算法设计。
3．了解插值是数值逼近的重要方法之一，正确理解每一种算法的基本思想、计算公式、算法设计、程序框图设计和源程序。
4．掌握数值积分的数学原理和程序设计方法。
5．能够使用数值方法解决一阶常微分方程的初值问题。
6．理解和掌握使用数值方法对线性方程组求解的算法设计。
（三）学时分配
本课程的理论教学时数为54学时分配如下表：
教学环节
课程内容 　学时
讲　课
引论
4
线性代数方程组的数值解法
6
插值方法
12
数值积分与微分
10
常微分方程初值问题的数值解法
10
方程求根的数值方法
10
总复习
2
合计
54

（四）课程内容的重点、难点
重点：Lagrange插值、Newton插值、分段插值、Hermite插值、三次样条插值、机械求积、Newton-Cotes求积公式、复化求积、Romberg求积算法。
难点：Gauss消去法、Gauss消去法的矩阵形式、主元消去法、三角分解法、迭代法、迭代法的收敛条件及误差估计。
三、课程改革与特色
本课程是一门重要的专业基础课。数值计算方法既是一门古老的学科，又是一门新兴的学科。电子计算机的产生和发展极大地促进了数值计算方法的发展。只有把数值计算方法和程序设计紧密结合起来，把算法变为计算机能直接执行的程序，才能真正使计算机帮助人们解决各种复杂的计算任务。
本课程试图将数值计算方法和程序设计方法学融为一体，这也是一种尝试。
四、推荐教材及参考书
推荐教材：《计算机数值方法》（第三版），主编：施吉林、刘淑珍、陈桂芝，出版社：高等教育出版社，出版时间：2005年3月
参考书：
《数值计算方法和算法》，主编：张韵华、奚梅成、陈效群，出版社：科学出版社，出版时间：2002年3月
《Numerical Analysis》，主编：Richard L.Burden ，出版社：高等教育出版社影印，出版或修订时间：2003
《数值分析》，主编：金聪、熊盛武，出版社：武汉理工大学出版社，出版时间：2003年8月

第一章 绪论
一、教学目标及基本要求
通过对本章的学习，使学生对了解涉及工程和科学实验中常见的数学问题，其中包括线性方程组、函数插值、离散数据的拟合、微积分、微分方程等，这些问题是其他数学问题的基础。
二、教学内容及学时分配
本章主要介绍数值分析的研究对象及误差的概念。具体内容如下：
第1-2学时讲授内容：计算方法的研究内容、对象与特点；误差的基本概念。
三、教学重点难点
1．教学重点：误差、误差种类；误差分析：误差与有效数字的关系。
2. 教学难点：误差分析、误差与有效数字的关系。
四、教学中应注意的问题
多媒体课堂教学为主。适当提问，加深学生对概念的理解。

第1讲 绪论
基本求解步骤
实际问题
建立数学
模型
构造数值 算法
编程上机
计算结果

数学模型是通过科学实验或者观察分析一系列数据后，用数学作为工具近似地描述客观事物的一种数学表达式。在数学模型中，往往包含了若干参量，这些物理参数通常由实验仪器测得，根据仪器的精密程度，物理参数的确定也会产生一定的误差。
在建立了数学模型之后，并不能立刻用计算机直接求解，还必须寻找用计算机计算这些数学模型的数值方法，即将数学模型中的连续变量离散化，转化成一系列相应的算法步骤，编制出正确的计算程序，再上机计算得出满意的数值结果。
算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。
例1

需乘法5次，加法3次。

需乘法3次，加法3次。
一般地，计算n次多项式的值

如若按有次乘法运算,计算共需次乘法和次加法运算。
采用：秦九韶算法(1247) 有递推公式:
从内往外一层一层计算，社

需乘法n次，加法n次，存储单元n+3个。
Y
N
开始
输入

k=n
输出v
结束

对算法所要考虑的问题,包括如下:
§ 计算速度
例如,求解一个20阶线性方程组,用消元法需3000次乘法运算；而用克莱姆法则要进行次运算,如用每秒1亿次乘法运算的计算机要30万年。
§ 存储量
大型问题必要考虑计算机的数据存贮。
§ 数值稳定性
在大量计算中,舍入误差是积累还是能控制,这与算法有关。
实际算法往往表现为某种无穷递推过程
算法的精度控制
方程根的二分法求解

若，则为所求根
否则若,则根在区间，取
若,则根在区间，取

每一区间为前一区间的一半，有根区间长度

§1.2 预备知识和误差
(1) 误差的来源
实际问题è建立数学模型è研究计算方法è编程上机计算解结果。
模型误差: 在建立数学模型过程中,不可能将所有因素均考虑,必然要进行必要的简化,这就带来了与实际问题的误差。
测量误差: 测量已知参数时,数据带来的误差。
截断误差: 模型的准确解与某种数值方法的准确解之间的误差称为截断误差或方法误差。
舍入误差: 计算机的字长是有限的,每一步运算均需四舍五入,由此产出的误差称舍入误差。如：π、1／3，……取小数点8位、16位。
[截断误差的实例]

解：利用展开式的前三项取n=2，

截断误差为：0.17
[舍入误差的实例]
，设在一台虚构的4位数字的计算机上计算，舍入误差为 0.000472。
数值计算方法主要讨论截断误差和舍入误差的影响,不讨论模型误差和测量误差。
三、误差的基本概念
(1) 误差与误差限
误差不可避免，设以代表数的近似值，称是近似值的绝对误差。简称误差。误差是有量纲的,可正可负。
误差通常是无法计算的,但可以估计出它的一个上界。即
称是近似值的误差限，或称精度，即
。
(2) 相对误差与相对误差限
绝对误差并不能完全反应精度，称为近似值的相对误差,记作。相对误差是个相对数,是无量纲的,也可正可负。
相对误差的估计,称为相对误差限,即
。
(3) 有效数字
定义: 如果近似值的误差限是(某一数位的半个单位),则称准确到小数点后n位,并从第一个非零的数字到这一位的所有数字均为有效数字。
如：π＝3.1415926535,
3.14有三位有效数字,误差限ε=0.005;
3.1416有五位有效数字,误差限为0.00005。
(4) 有效数字与误差限的关系：
有n位有效数字，标准形式为 其中ai(i=1,2,…)是0~9之间的整数,且,如果误差，称为的具有l位有效数值的近似值.
(5)有效数字与相对误差的关系：
标准形式为，则：
a)
证：

b)则
证：
例，已知，试问其近似值各有几位有效数字？并给出它们的误差限和相对误差限。
，十分位以前都是有效数字，有两位有效数字

有三位有效数字

，有四位有效数字

，有五位有效数字

例：为使π*的相对误差小于0.001%,至少应取几位有效数字？
解：

，则π*=3.14159
§1.3数值计算的若干原则
1. 避免两相近数相减
当x较大时，计算，可先转化为
,精确值
令h=0.1得
令h=0.0001得
计算，分子出现相近数相减，可转换为
，再计算
2.避免绝对值太小的数做除数
分母接近零的数会产生溢出错误,因而产生大的误差,此时可以用数学公式化简后再做.

3.要防止大数“吃掉”小数
计算机在进行算术计算时,首先要把参加运算的数对阶，即把两数都写成绝对值小于1,而阶码相同的数。如：必须改写成: 如果计算机只能表示8位小数，则算出, 大数吃掉了小数。这种情形是要尽量避免的。
4. 简化计算步骤，提高计算效率
简化计算步骤是提高程序执行速度的关键，它不仅可以节省时间，还能减少舍入误差。
例4：设A、B、C、D分别是10´20、 20´50、 50´1、 1´100的矩阵，试按不同的算法求矩阵乘积E=ABCD.
解：由矩阵乘法的结合律，可有如下算法
1. E=((AB)C)D. 计算量N=11500flop
2. E=A(B(CD)). 计算量N=125000flop
3. E=(A(BC))D. 计算量N=2200flop
5.要使用数值稳定的算法
我们已经知道，所谓算法的稳定性，是指误差的传播可以得到控制，在用计算机解决实际问题时，运算次数成千上万。如果误差的传播得不到控制，那么误差的累积会使问题的解答成为荒谬的，尤其是某些病态问题（如病态方程组），舍入误差对其计算结果往往有非常严重的影响。因此，在选择计算方案时，要特别谨慎。
考察方程组
解为
四舍五入系数后，解为
尽管系数变动不大，但求出得解却变动很大，这类问题称为病态的
例：蝴蝶效应（气象学家洛伦兹，1963）
——南美洲亚马孙河流域热带雨林中的一只蝴蝶翅膀一拍，偶尔扇动几下翅膀，可能在两周后引起美国德克萨斯引起一场龙卷风？！

第二章 插值法
一、教学目标及基本要求
通过对本章的学习，使学生掌握插值法计算常见的数学问题。
二、教学内容及学时分配
本章主要介绍数值分析的插值法。具体内容如下：
第3-4学时讲授内容：问题的提法、拉格朗日插值公式。第5-6学时讲授内容：插值余项、牛顿插值公式。第7-8学时讲授内容：曲线拟合。
三、教学重点难点
1．教学重点：插值方法的由来、拉格朗日插值公式、牛顿插值公式、曲线拟合。
2. 教学难点：拉格朗日插值公式、牛顿插值公式。
四、教学中应注意的问题
多媒体课堂教学为主。适当提问，加深学生对概念的理解。
第2讲 拉格朗日插值公式
众所周知，反映自然规律的数量关系的函数有三种表示方法：
A. 解析表达式
.
(开普勒(Kepler)方程).。
悬链线方程: 。
B. 图象法

C. 表格法

1、插值法 对于一组离散点，选定一个便于计算的简单函数，如多项式函数，要求满足，由此确定函数作为的近似函数，然后通过处理获得关于的结果。这就是插值方法。
2、曲线拟合 选定近似函数时，不要求近似函数必须满足，而只要求在某种意义下（最小二乘法原理），使近似函数在这些点上的总偏差量最小，这类方法成为曲线拟合。
§1.1 多项式插值问题的一般提法
1 插值法的概念:
假设函数y=f(x)是[a,b]上的实值函数，x0,x1,…,xn是[a,b]上n+1个互异的点，f(x)在这些点上的取值分别为y0,y1,…,yn,
求一个确定的函数P(x),使之满足:
P(xi)=yi (i=0,1,2,…,n) (1)
称x0,x1,…,xn为插值节点，关系式(1)称为插值原则，函数P(x)称为函数y=f(x)的插值函数，区间[a,b]称为插值区间。

2 泰勒插值
人们熟悉的泰勒展开方法其实就是一种插值方法，泰勒多项式：
（1）
与在点邻近会很好的逼近。
泰勒余项定理:
定理1 假设在含有点的区间[a,b]内有直到n+1阶导数，则当时，对于式（1）给出的，成立

其中介于与x之间，因而。
所谓泰勒插值指下述问题：
问题 1 求作n次多项式，使满足，为一组已给数据。
易看出，上述插值问题的解就是泰勒多项式（1）。
例1 例题分析:
求作在的一次和二次泰勒多项式，利用它们计算的近似值并估算误差。
解：
， ， ，
， ， ，
在的一次泰勒多项式是

时
根据定理1可估计误差

误差小于十分位的一半，故十分位及前面的数字为有效数字，所以结果有三位有效数字。
修正可进一步得到二次泰勒公式

误差小于百分位的一半，故百分位及前面的数字为有效数字，所以结果有四位有效数字。
泰勒插值是一种有效的插值方法，对函数要求严格（要足够光滑，存在高阶导数），要计算函数的高阶导数，而高阶导数的计算对计算机来说就很困难；另外，计算过程不能形成机械重复的过程，不利于计算机程序实现。
§1.2 拉格朗日(Lagrange)插值
1 多项式插值的存在惟一性:
多项式导数易于计算，函数表达式简单，计算机易于计算，故考虑用多项式函数作为插值函数来模拟实际函数。
从如下数据表着手,并假定，
x : x0 x1 x2 … xn
y : y0 y1 y2 … yn

求 n 次多项式, 使得：
P(xi)=yi (i=0,1,2,…,n) 。
根据插值条件，有：
(1)
显然，这是一个关于的n+1元线性方程组，其系数矩阵的行列式为

注意到插值节点两两相异，而
故方程组(1)有惟一解,于是满足插值条件的多项式存在且惟一。
定理 由n+1个不同插值节点可以惟一确定一个n次多项式满足插值条件。
从理论上说，由方程组(1)可以求出的惟一解,从而确定。但从数值计算上看，当n较大时求解线性方程组的工作量较大且不便应用。
解方程组（1）需计算n+1个n阶行列式，每个n阶行列式为n!项之和，每项又是n个元素的乘积，需n-1次乘法，所以求解需要次乘法，当n较大时，计算量非常大。
为解决此问题，现已提出了不少构造的巧妙办法。
2 Lagrange插值的基函数构造法
首先讨论n=1时的情形。
已知，求使得
显然是过 和两点的一条直线。

由点斜式容易求得

其中，具有如下特点：

称其为线性插值基函数。可以通过函数组合得出，且组合系数恰为所给数据y0,y1。

再讨论n=2时的情形。
显然是过 、、三点的一条抛物线。

仿照线性插值基函数的构造方法，令

其中，具有如下特点：

称其为抛物线插值基函数(如下图所示)。

于是，

最后讨论一般情形。
求Ln(x)使得L(xi)=yi (i=0,1,2,…,n) 。
令n次多项式插值基函数为:
,
具有如下特点：
。
于是，满足插值条件的n次多项式可以直接写为:

我们称Ln(x)为Lagrange多项式，其Lagrange插值基函数。

Y
N
开始
输入

k=n
输出y
结束

思考 给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是l2(x)的图像？

3 插值余项
如图所示，其截断误差Rn(x)=f(x)-Ln(x)，称为Lagrange插值多项式的余项。

定理 假设f(x)在[a,b]上有连续的直到n+1阶导数，且在不同插值节点取值为,是经过插值样点的Lagrange插值多项式，若引进记号：

则当时，有如下的误差估计：

证明：因为
于是可假定具有如下形式：

将x看作(a,b)上的一个固定点，作辅助函数

容易看出，有共n+2个相异零点,且在[a,b]上存在n+1阶导数。根据罗尔,在的两个零点之间至少有一个零点，故在[a,b]上至少有n+1个零点。如此类推,在(a,b)上至少有1个零点,使得

注意到是n次多项式，；的首项为，
故。由上述方程解得
。
于是

4 例题
例1 已知函数y=f(x)的观察数据为
xk
－2
0
4
5
yk
5
1
－3
1
试构造f(x)的拉格朗日多项式Ln (x)，并计算f(－1)。
解 先构造基函数

所求三次多项式为
L3(x)=
＝ ＋
-＋
＝
L3(－1)＝

第3讲 牛顿公式
§1.4 差商与差分及其性质
1 差商的概念:
称为函数f(x)的一阶差商；
称为函数f(x)的二阶差商；
一般地，称为函数f(x)的n阶差商；
特别地，定义为函数f(x)关于xo的零阶差商。
由此可知，高阶差商总是由比它低一阶的的两个差商组合而成。
2 差商性质
（a） 性质1:n阶差商可以表示成n+1个函数值的线性组合,即

该性质说明：k阶差商计算是由函数值f(x0),f(x1),…f(xk)线性组合而。
如:；

(b) 性质2(对称性): 差商与节点的顺序无关。即
，

这一点可以从性质1看出。
3 利用差商表计算差商
利用差商的递推定义,可以用递推来计算差商。
差商表：

一阶差商
二阶差商
三阶差商

如要计算四阶差商,应再增加一个节点,表中还要增加一行。
4 差分的概念
定义设函数y=f(x)在等距节点上的函数值f(xi)=fi,其中，h为常数称作步长。称
△fi=fi+1-fi
▽fi=fi-fi-1
δfi=f(xi+h/2)-f(xi-h/2)=
分别为f(x)在处以h为步长的一阶向前差分，一阶向后差分和一阶中心差分。称符号△、▽、δ分别为向前差分算子，向后差分算子和中心差分算子。

在节点等距情况下，差商可用差分表示，设步长，有

一般形式(数学归纳法可证)

§1.5 牛顿插值公式
1. 牛顿插值公式的构造
Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x) 都需重新算过。本节介绍另外一种方法-牛顿插值法，并用它解决上面所述问题。
由线性插值
，令
二次插值能否写成

由条件得

推广得
,
其中，为待定系数。如何求?
解: 因为,
所以 (0)
又,有
(1)
又

(2)
一般地,
(n)
将式(n)代入式(n-1), ...,式(2)代入式 (1),式(1)代入式 (0),
如此可得:

尤为注意的是：最后一项中,差商部分含有,乃是余项部分,记作;而前面n+1项中,差商部分都不含有,因而前面n+1项是关于的n次多项式,记作,这就是牛顿插值公式。
2 算例
例1:当n=1时，
,
其中,

。
这就是牛顿一次插值多项式，也就是点斜式直线方程。
当n=2时,

这就是牛顿二次插值多项式。显然,
,

。
即满足二次插值条件。

例2: 已知

1
2
4
7

0
1
15
12
求满足以上插值条件的牛顿型插值多项式。
解: 由于:
,,,;
则牛顿三次插值多项式为
。
3 拉格朗日插值与牛顿插值的比较
(1)和均是n次多项式,
且均满足插值条件:
。
由多项式的唯一性,,因而,两个公式的余项是相等的,即

(2)当插值多项式从n-1次增加到n次时,拉格朗日型插值必须重新计算所有的基本插值多项式;而对于牛顿型插值,只需用表格再计算一个n阶差商,然后加上一项即可。
4 等距牛顿插值公式
插值节点为等距节点：
，,如下图：
h h h ... h
...
牛顿插值公式
设等距节点，
记.当，令，. 例如（下图）

x在x2，x3的中点时，。
将牛顿插值公式中的差商用差分代替,而
从而,牛顿插值公式在等距插值节点下的形式为:

余项为

这是等距牛顿向前插值公式。
例4: 设插值节点为,相应的函数值如下表,求f(2.2)。

xi
yi
Δyi
Δ2yi
Δ3yi
Δ4yi
1
2.71828
1.76341
1.14396
0.74210
0.48146
1.5
4.48169
2.90737
1.88606
1.22356

2
7.28906
4.79343
3.10962

2.5
12.18249
7.90305

3
20.08554

解：精确值f(2.2)=e2.2=9.025011。
此时[xk, xk+1],x=2.2=1+2.4h 故t=2.4,于是
求时，在后加一项：
，所以
求时，在后再加一项：
，所以

第4讲 曲线拟合
§1.9 曲线拟合的最小二乘法
1 拟合问题的数学提法
通过观测、测量或试验得到某一函数在的函数值。我们可以用插值的方法对这一函数进行近似,而插值方法要求所得到的插值多项式经过已知的这n个插值结点;在n比较大的情况下,插值多项式往往是高次多项式,这也就容易出现振荡现象:虽然在插值结点上没有误差,但在插值结点之外插值误差变得很大,从“整体”上看,插值逼近效果将变得“很差”。于是,我们采用曲线拟合的方法。
所谓曲线拟合是求一个简单的函数,例如是一个低次多项式,这儿不要求通过已知的这n个点,而是要求在整体上“尽量好”的逼近原函数。这时,在每个已知点上就会有误差,,数据拟合就是从整体上使误差,尽量的小一些。
x1

x2

x3

……

xn-1

xn

如果要求达到最小，因误差可正可负,本来很大的误差可能会正负抵消,为防止正负抵消,可以要求达到最小,但是由于绝对值函数不可以求导，分析起来不方便,求解也很难。
为了既能防止正负抵消,又能便于我们分析、求解，提出如下问题
求一个低次多项式,使得达到最小,此问题便是一个曲线拟合的最小二乘问题。
1直线拟合（一次函数）
a) 问题的提法
通过观测、测量或试验得到某一函数在的函数值，即得到n组数据,如果这些数据在直角坐标系中近似地分布在一条直线上，我们可以用直线拟合的方法。
问题:已知数据,求一个一次多 项式（实际上，就是求a,b）, 使得 达到最小
注意到中,均是已知的，而a,b是未知量,是未知量a,b的二元函数,利用高等数学中求二元函数极小值(最小值)的方法，因此，上述问题转化为求解下列方程组

b) 正则方程组
由得：

得到如下的正则方程组

这是个关于a,b的二元一次方程组，称其为最小二乘问题的正则方程组.解得a,b,便得到最小二乘问题的拟合函数。
c) 算例
例1. 已知10对数据如下表,利用最小二乘法求拟合曲线。
解：先列表来计算四个：

形成正则方程组

解得
，
于是，最小二乘拟合一次函数为。

第三章 数值积分
一、教学目标及基本要求
通过对本章的学习，使学生掌握积分的数值解法。
二、教学内容及学时分配
本章主要介绍积分的数值解法。具体内容如下：
第9-10学时讲授内容：机械求积、插值型求积公式。第11-12学时讲授内容：牛顿柯特斯公式、复化求积公式。第13-14学时讲授内容：高斯公式、数值微分。
三、教学重点难点
1．教学重点：机械求积、牛顿柯特斯公式；复化求积公式；高斯公式。
2. 教学难点：复化求积公式；高斯公式。
四、教学中应注意的问题
多媒体课堂教学为主。适当提问，加深学生对概念的理解。

第5讲 机械求积、插值型求积公式
2.0 引 言
1.定积分的计算可用著名的牛顿-莱布尼兹公式来计算:

其中F(x)是f(x)的原函数之一，可用不定积分求得。
然而在实际问题中，往往碰到以下问题：
1）被积函数f(x)是用函数表格提供的；
2）被积函数表达式极为复杂，求不出原函数，或求出原函数后，由于形式复杂不利于计算；
3）大量函数的原函数不容易或根本无法求出，例如
概率积分，正弦型积分，等根本无法用初等函数来表示其原函数，因而也就无法精确计算其定积分，只能运用数值积分。
2.所谓数值积分就是求积分近似值的方法。
§2.1 机械求积公式
1 数值积分的基本思想
基本思想：定积分的几何意义：曲线，直线与x轴所围成得曲边梯形得面积，无论被积函数是什么形式，只要近似计算曲边梯形面积，就可求定积分的值，这就是数值求积的基本思想。
积分中值定理，点具体值未知，只要对平均高度提供一种数值算法，相应就求得一种数值求积方法。
（1） 用f(x)的零次多项式来近似代替,于是，
（为左矩公式）

（为右矩公式）
（为中矩公式）
（2） 用f(x)的一次多项式

来近似代替,于是，
（为梯形公式）

（3） 用f(x)的二次插值多项式,其中

来近似代替,于是，

特别地：当时，有
（为Simpson公式）
一般在区间[a,b]上的定积分，就是在区间[a,b]内取n+1个点，利用被积函数f(x)在这n+1个点的函数值的某一种线性组合来近似作为待求定积分的值，即

右端公式称为左边定积分的某个数值积分公式。其中,xk称为积分节点，Ak称为求积系数。因此，一个数值积分公式关键在于积分节点xk的选取和积分系数Ak的决定，其中Ak与被积函数fx)无关，称为机械求积公式。

2 代数精确度
定义：若积分的数值积分公式对于任意一个次数不高于m次的多项式都精确成立，且存在一个m+1次多项式使之不精确成立，则称该数值积分公式的代数精确度为m。
对于代数精确度为m的求积公式，若f(x)是不超过m次的代数多项式，求积公式是精确成立的。
一般地，要使具有n 次代数精度，只要令它对于都准确成立,也就是对给定n+1个互异节点，相应的求积系数满足：

方程组的系数行列式是范德蒙行列式，当互异时，其值非零，利用克莱姆法则可以惟一的求出进而可以构造出求积公式，于是，有如下结论：对于任意给定n+1个互异节点总存在相应系数使至少具有n次代数精度。
例：在如下求积公式中，求积分节点和相应的求积系数使其代数精确度尽可能高。

解：(1) f(x)=1, ,而数值积分为；
得到方程；
(2) f(x)=x，，而数值积分为；
得到方程；
(3) ，，而数值积分为；
得到方程；
(4) ，，而数值积分为；
得到方程；
综合上述方程：

解得:
。
于是我们得到积分公式
。
再取，有，
而数值积分为，两式不相等，求积公式不精确成立了。
所以，该积分公式的代数精确度为3。
2.1.3 插值型的求积公式
用求线性方程组的方法构造求积公式计算量太大，现在，用插值多项式来构造数值求积公式。设在互异节点处的函数值为，则可构造拉格朗日插值多项式：

由于代数多项式的原函数容易求出，可取:
(1)
(2)
我们称求积系数由(2)式确定的求积公式称为插值求积公式。其余项为：

当被积函数取次数不超过n次多项式时，由于，所以余项，这说明求积公式对一切次数不超过n 次的多项式精确成立，所以对有n+1个互异节点的插值型求积公式至少具有n次代数精度。
反之，如果求积公式至少有n次代数精度，则它对于n次插值基函数也是准确成立的，即有: ，因而（2）成立，这说明至少有n次代数精度的求积公式必为插值型的。
综上所述，有如下结论：
定理 求积公式是插值型求积公式的充分必要条件是它至少具有n 次代数精度。
这样，给定求积节点，求积系数可通过求解线性方程组或通过插值函数计算。
例1，已知，
1） 推导以这三个点为求积节点，在[0,1]上的插值型求积公式；
2） 求其代数精度

例2 P80题2

第6讲 牛顿柯特斯公式、复化求积公式
§2.2 Newton-Cotes公式
1 公式的推导
Newton-Cotes公式是由拉格朗日插值公式推导出来的数值积分公式。
将区间[a,b]等分n等份,记,分点为,k=0,1,...,n,这n+1个节点上的函数值为,从而区间[a,b]上的拉格朗日插值多项式为

由于插值结点是等距节点，故插值多项式可以进一步化简:
因为 ，
故 ，

因 ，作积分变量代换，，当x=a时，t=0；当x=b时，t=n；
故

记，我们称为柯特斯（Cotes）系数，它不仅与函数f(x)无关，而且与积分区间[a,b]无关。
例如：
当n=1时 (梯形积分公式中的系数)
,;
当 n=2时 (抛物线积分公式中的系数)
,
,
;
当n=4时柯特斯公式

于是，由柯特斯（Cotes）系数公式出发，我们得到n阶Newton—Cotes公式：
。
柯特斯公式市节点等距条件下的插值型求积公式，至少具有n次代数精度，当n为偶数时，能达到n+1次代数精度。（可以证明）
从表中看出n=8时，出现负数，稳定性没保证，所以一般采用n=4的牛顿-柯特斯求积公式 。
2 低阶公式及其余项
常用的Newton—Cotes公式
a) 梯形公式
n=1时，积分节点为，，则数值积分公式为：

其几何意义是曲边梯形的面积近似地用梯形面积来代替。
其余项
b) 抛物线公式（辛浦生Simpson公式）
n=2时，积分节点为x0=a，，x2=b；
柯特斯系数为；
则数值积分公式为:

其几何意义是曲边梯形的面积近似地用由抛物线形成的曲边梯形面积来代替。其余项

c) 柯特斯公式
n=4时，积分节点为，，；
柯特斯系数为,；
则数值积分公式为：

其余项
综上所述，Newton-Cotes数值积分公式具有如下特点：
(1) 建立在等距积分节点上，
(2) 是封闭型的，即两个端点a,b也是积分节点，
(3) 是由拉格朗日插值公式推导而得到的。
3 Cotes系数的性质
引理: Newton—Cotes公式的代数精确度至少是n。
证明: 如果是一个次数不超过n次的多项式，则
其拉格朗日插值公式的插值余项为：

故，这是对一切x均相等，精确成立。
所以，

即，数值积分公式的值精确地等于定积分的值，故n阶Newton—Cotes公式的代数精确度至少是n。
性质1:
归一公式：

证明：由于数值积分公式的代数精确度至少为n，故对于，数值积分公式是精确成立的：
，而
由上述两式相等，得到：

性质2:
对称性：。
定理 Newton—Cotes公式中，n为奇数时，代数精度为n，n为偶数时，代数精度为n+1。(用求积公式余项来证明)

4 复化求积法
随着n的增加可以减少积分误差，但高阶N-C公式又会造成数值不稳定。另外，通过求积公式的余项可以看出，截断误差与积分区间长度关系很大。通常将积分区间划分成若干小区间，每个小区间采用次数不高的求积公式，再将它们加起来，这类方法称为复化求积法。
复化梯形公式
将区间等分n等份,,分点是(k=0,1,...,n),其中。在每个子区间上用梯形公式

则

此公式就是复化梯形公式。
余项：
梯形公式余项为
复化梯形公式
由定积分定义
故
复化新甫生公式
在每个小区间上用辛普生公式，记的中点为，得

此公式就是复合辛浦生公式。
余项：

复化柯特斯公式
每个小区间四等分，记为，得

此公式就是复化柯特斯公式。
余项：

算例
分别利用梯形公式和Simpson公式计算积分： 。
解：设,步长h=1/8
由复合梯形