高等教育数值分析教案正文--学案教案.doc

高等教育数值分析教案
Ch1、引 论
§1、数值分析及其特点
1、数值分析及其主要内容
数值分析也称计算方法，主要研究用计算机求解数学问题的数值方法及理论，内容主要包括：
(1)数值逼近—插值与拟合、多项式逼近、有理逼近等(Ch2~Ch3)；
(2)数值积分与微分(Ch4)；
(3)数值代数—求解方程(组)以及特征问题的数值方法(Ch6~Ch9)；
(4)常微分方程的数值解法(Ch5)。
2、数值分析的特点
(1)首先要有可靠的理论分析，以确保算法在理论上的收敛性和数值稳定性；
(2)其次要对计算结果进行误差估计，以确定其是否满足精度；（见例3）
(3)还要考虑算法的运行效率，即算法的计算量与存储量。
例如Cooley和Tukey1965年提出FFT，，N=32K，1000倍。
例1、分析用Cramer法则解一个阶线性方程组的计算量。
解：计算机的计算量主要取决于乘除法的次数。
用Cramer法则解一个阶线性方程组需计算个阶行列式，而用定义计算阶行列式需次乘法，故总计共需。
此外，还需次除法。
当时，计算量约为次乘法。即使用每秒百亿次乘法的计算机，也需计算3000多年才能完成。
可见，Cramer法则仅仅是理论上的，不是面向计算机的。
§2、数值分析中的误差
1、误差的类型与来源
(1)模型误差；(2)观测误差；
(3)截断误差(方法误差) —模型的准确解与数值方法准确解之间的误差；
(4)舍入误差—实数形式的原始数据与有限字长的计算机数据之间的误差。
数值分析主要研究截断误差与舍入误差。
例2、根据Taylor展式计算(误差小于0.01)。
解：
(截断误差) (舍入误差)。
2、误差的基本概念
(1)误差与误差限
设为某量的精确值，为的一个近似值，则称为的（绝对）误差，为的相对误差。
用某种方法确定的误差的某个上界称为的误差限，显然，即，称为的相对误差限。
误差限取决于测量工具和计算方法。
(2)函数值的计算误差
设，为的近似值，则

(多元函数一阶Taylor展式)
，。
§3、算法的数值稳定性与病态问题
1、算法的数值稳定性
例3、计算，并做误差分析。
解：。
算法1：，结果见下表。
又, 。
算法2：，结果见下表。
n
算法1
算法2
准确值
0
1
2
3
4
5
6
0.1823
0.0885
0.0575
0.0458
0.0208
0.0958
-0.3125
0.1823
0.0884
0.0580
0.0431
0.0344
0.0281
0.0262
0.1823
0.0884
0.0580
0.0431
0.0343
0.0285
0.0243
误差分析:
算法1：
，即在计算过程中误差放大了倍。
算法2：，
即误差缩小了倍。
定义1：若某算法受初始误差或计算过程中产生的舍入误差的影响较小，则称之是数值稳定的，反之称为不稳定算法。
2、病态问题
例4、将方程，即改为摄动方程，即，其中。
Wilkinson用精密方法计算出其根为：
。
令，其根为，则当
时，。显然反映了初始数据的微小摄动对的影响程度即问题的条件数。
因，故

1
4
6
8
10~19
20 （坏条件问题）
定义2：若初始数据的微小误差都会对最终的计算结果产生极大的影响，则称这种问题为病态问题（坏条件问题），反之称其为良态问题。
例5、分别将线性方程组

的右端向量和系数矩阵中数据做一个微小变化，具体数据如下：

然后用精确方法求解，发现其解与原方程解相比发生了很大的变化。
这表明此方程组为病态方程组。
§4、算法的实现与常用的数学软件
用计算机实现数值分析中的算法通常有两种途径：(1)用Fortran、C、VB、VC等自编程序；(2)借助于现成的数学工具软件。
目前常用的数学软件约30余个，可分为通用与专用两大类。
专用系统主要是为解决数学中某个分支的特殊问题而设计的。
1、 SAS和SPSS（统计分析）；
2、 Lindo、Lingo和CPLEX（运筹与优化计算）；
3、 Cayley和GAP（群论研究）；
4、 PARI（数论研究）；
5、 Origin（科技绘图与数据分析）；
6、 DELiA（微分方程分析）等。
通用系统中又可分为数值计算型与解析计算型。
数值计算型：Matlab、Xmath、Gauss、MLAB和Origin等。
解析计算型：Maple、Mathematica、Macsyma、Axiom和Reduce等。
其中Matlab、Mathematica、Maple与另一个面向大众的普及型数学软件Mathcad并称数学软件中的“四大天王”。
Matlab意思为“矩阵实验室”，是美国计算机科学家Cleve Moler在70年代末开发出的以矩阵数值计算为主的数学软件，如今已发展成为融科技计算、图形可视化与程序语言为一体的功能强大的通用数学软件。Matlab最突出的特点是其带有一系列的“工具包”，可广泛应用于自动控制、信号处理、数据分析、通讯系统和动态仿真等领域。高版本的Matlab也可进行符号计算，不过它的代数运算系统是从Maple移植过来的。Mathematica是美国物理学家Stephen Wolfram开发出的第一个将符号计算、数值计算和图形显示很好地结合在一起的数学软件，在国内较为流行，拥有广泛的用户。Mathcad是MathSoft公司在80年代开发的一个交互式数学文字软件，与Matlab和Mathematica不同的是，该软件的市场定位是：向广大教师、学生、工程技术人员提供一个兼备文字、数学和图形处理能力的集成工作环境，而并不致力于复杂的数值计算与符号计算问题，具有面向大众普及的特点。不过，新版Mathcad的计算能力已远远超出了其早期的设计目标。
Maple是加拿大Waterloo大学符号计算研究小组于80年代初开始研发，1985年才面世的计算机代数软件，起初并不为人们所注意，但Maple V release 2于1992年面世后，人们发现它是一个功能强大、界面友好的计算机代数系统。随着版本的不断更新，Maple已日益得到广泛的承认和欢迎，用户越来越多，声誉越来越高，从1995年以后，Maple一直在IEEE的数学软件评比中居符号计算软件的第一名。目前，Maple的最高版本为Maple V release 11。
第一章上机
实验目的：
1、 熟悉Maple中的定义函数、解方程、积分、循环语句和列表等命令；
2、 通过具体问题的计算，加深对数值稳定性和病态问题的理解。
实验内容：
1、 设，由得算法一：；又，取，从而又得算法二：。分别用上述两种算法计算，根据计算结果判定其数值稳定性，并给予证明。
2、将方程，即改为摄动方程，对不同的求解此方程，观察对解的影响程度，判定此方程是否为病态方程。
15、已知三角形面积，其中为弧度，，且测量的误差分别为，证明面积的误差满足。
证：根据零阶多元Taylor公式

，
令，则，
因，从而，得，即。又，故，即。
从而。
Ch2、插值法
§1、插值问题
引例：矿井中某处的瓦斯浓度与该处距地面的距离有关，现用仪器测得从地面到井下500米每隔50米的瓦斯浓度数据，根据这些数据完成下列工作：(1)寻找一个函数，要求从此函数中可近似求得从地面到井下500米之间任意一点处的瓦斯浓度；(2)估计井下600米处的瓦斯浓度。
第一个问题可归结为“已知函数在处的值，求函数在区间内其它点处的值”，这种问题适宜用插值方法解决。
但对第二个问题不宜用插值方法，因为600米已超出所给数据范围，用插值函数外推插值区间外的数据会产生较大的误差。
解决第二个问题的常用方法是，根据地面到井下500处的数据求出瓦斯浓度与地面到井下距离之间的函数关系，由求井下600米处的瓦斯浓度。
定义：设在中个点处的值为已知，现根据上述数据构造一个简单函数，使，这种问题称为插值问题。
,分别称为被插值函数、插值函数、插值节点和插值条件。若为多项式，则此问题称为多项式插值或代数插值。
定理1：在插值节点处，取给定值，且次数不高于的插值多项式是存在且唯一的。
证：令，则根据插值条件有下列等式
（关于的阶线性方程组），
其系数行列式是范德蒙（Vandermonde）行列式
。
根据克莱姆法则，此方程组存在唯一解，即存在且唯一。
§2、Lagrange插值
1、线性插值与抛物插值
(1)线性插值
，
其中称为线性插值的基函数。

(2)抛物插值
设，
分别令，即得
，
故
，
其中称为抛物插值的基函数。
2、Lagrange插值多项式
定义：对个插值节点，令
，
则显然。此时，满足 称之为Langrange插值多项式，称为Lagrange插值的基函数。
编程时宜用。
3、插值公式的余项
定理2：设上连续，在内可导，则以插值多项式逼近的截断误差（即余项）
。
例1、已知函数的数据如下，分别用线性插值和二次插值求的近似值。
0.5 0.6 0.7
-0.693147 -0.510826 -0.356675
解：，

§3、逐次线性插值法
对插值节点及对应的函数值，用表示一个非负整数序列，将个节点所确定的不高于次的插值多项式记为，则
，
即次插值多项式可以用两个次插值多项式通过线性插值获得—逐次线性插值。
Aitken算法：

例2、根据下表近似计算在处的值。

同理可得。
类似可得。
，
故。
§4、均差与牛顿插值公式
1、均差（差商）及其性质
定义：称为关于的一阶均差；
称为关于的二阶均差；
类似地可定义阶均差
。
定理：，即阶均差可表示为的线性组合，从而阶均差与节点的排列次序无关。
证：当时，右左
不妨假设成立，则

。
2、牛顿插值公式
设插值节点上的插值多项式为
。
分别令，则有
；
；
从而，
，
，
故
—— 牛顿插值公式。
例3、 P34

0.40
0.55
0.65
0.80
0.90
1.05
K=0
0.41075
0.57815
0.69675
0.88811
1.02652
1.25382
K=1

1.11600
1.18600
1.27573
1.38410
1.51533
K=2

0.28000
0.35893
0.43348
0.52493
K=3

0.19733
0.21300
0.22863
K=4

0.03134
0.03126
K=5

-0.00012

，
。

。
§5、差分与等距节点插值公式
1、差分及其性质
定义：对等距节点，记。
向前差分：；
向后差分：；
中心差分：；
二阶差分：；
阶差分：。
不变算子与移位算子，即。
由，得。
(1)差分类似于微分的性质

(2)函数值与差分可相互线性表示

(3)差分与均差的关系
。
证：时，。
假设时成立，则

。
2、等距节点插值公式
令，则，，
。
代入牛顿插值公式得

。
§6、Runge现象与高次插值的讨论
1、Runge现象
例4、，节点，求插值多项式。
解： ——10次Langrange插值多项式
结果如下：

2、讨论
(1)节点的增多固然能使插值函数在更多的地方与相等，但在两个节点之间不一定能很好地逼近，有时差异很大，所以在实际中，高次插值（7次以上）很少使用；
(2)可将分成若干小区间，在小区间内用低次（二次，三次）插值，即分段低次插值，如样条函数插值。
§7、三次样条插值
分段低次插值：
(1)分段线性插值(连续)；(2)分段Hermite插值(导数连续)；
(3)三次样条插值(二阶导数连续)。
1、三次样条插值函数
能够逐段表示成三次多项式且二阶导数连续(具有二阶光滑度)的函数。
定义：设，且在上为三次多项式，其中，则称为上的三次样条函数。
若对给定的，满足，则称为三次样条插值函数。

边界条件：
第一种边界条件： 固支梁条件；
第二种边界条件： 简支梁条件。
特别地，时的样条称为自然样条。
2、三弯距方程与三次样条的计算
记—弯距，
因在上为三次多项式，故为一次多项式，可令
—Lagrange线性插值。
对积分两次并代入，得

其中。
对求导得，从而可得
，
类似可得。
利用得
，
其中。
对第二种边界条件，，则关于弯距的矩阵方程为
，
其中。
上述方程称为三弯距方程，其系数矩阵为三对角，可用追赶法求解。求出代入即可得每个上的表达式。
例5、 求§6例中的三次样条插值函数(自然样条)。
解：表达式如下：

3、三次样条插值的存在唯一性
定理：三弯矩方程中的系数矩阵是可逆的，即三次样条插值存在、唯一。
证：设为的解，满足，
因，故。
又有

，
即。
若不可逆，则有非零解，由前所证，应有，矛盾，故可逆，存在唯一的。
4、样条函数的极性
极性定理：对若为满足的三次样条插值函数，则，其中。
证：
，
而
，
故，
得，即，二阶导数的范数最小。
第二章上机
实验目的：
3、 熟悉Maple中的一般插值、样条插值和序列等命令；
4、 通过对具体数据做高次插值、样条插值，加深对龙格现象以及样条插值优越性的理解与认识。
实验内容：
对数据
x
1 2 5 6 7 8 10 13 17
f(x)
3.0 3.7 3.9 4.2 5.7 6.6 7.1 6.7 4.5
1、 做出折线图，得出的大致形状；
2、 求出一般插值多项式（8次）；
3、 求出三次样条插值多项式；
4、 将与、与分别做图对照，观察高次插值的危害性以及样条插值的优越性。
1．矩形区域二元函数的分片线性插值
已知平面上一矩形域内四个顶点顶点处的函数值分别为。
分两片的函数表达式如下：
第一片(下三角形区域)：满足，插值函数为：
。
第二片(上三角形区域)：满足，插值函数为：
。
2．矩形区域二元函数的双线性插值
双线性插值函数的形式如下：，它是分片空间二次曲面。利用该函数在矩形的四个顶点（插值节点）的函数值，得到四个代数方程，可以确定四个待定系数。
双线性插值函数可按下方法计算。
已知平面上一矩形域内四个顶点顶点处的函数值分别为，求函数，使其满足条件：
。
令，则有
。
Ch3、函数逼近与计算
§1、引言
1、引例
某气象仪器厂要在某仪器中设计一种专用计算芯片，以便于计算观测中经常遇到的三角函数以及其它初等函数。设计要求在区间中变化时，近似函数在每一点的误差都要小于某一指定的正数。
(1)由于插值法的特点是在区间中的个节点处，插值函数与被插值函数无误差，而在其它点处。对于，逼近的效果可能很好，也可能很差。在本问题中要求在区间中的每一点都要“很好”地逼近，应用一般的插值方法显然是不可行的，龙格现象就是典型的例证。采用样条插值固然可以在区间的每一点上满足误差要求。但由于样条插值的计算比较复杂，需要求解一个大型的三对角方程组，在芯片中固化这些计算过程较为复杂。
(2)可以采用泰勒展式解决本问题。
将在特殊点处做泰勒展开

取其前项作为的近似，即

但泰勒展式仅对附近的点效果较好，为了使得远离的点的误差也小于，只好将项数取得相当大，这大大增加了计算量，降低了计算速度。因此，从数值计算的角度来说，用泰勒展式做函数在区间上的近似计算是不合适的。
(3)引例提出了一个新的问题，即能否找到一个近似函数，比如说，它仍然是一个次多项式，不一定要在某些点处与相等，但却在区间中的每一点处都能“很好”地、“均匀”地逼近。
2、逼近问题
对，求一个多项式，使在某种衡量标准下最小。
(1)一致逼近（均匀逼近）
无穷范数：最小
(2)平方逼近（均方逼近）
欧氏范数：最小。
3、维尔斯特拉斯定理
定理：设，则对任意，有多项式，使在上一致成立。
本定理的证法很多，伯恩斯坦在1921年引入了一个多项式

他证明了。
伯恩斯坦多项式在自由外形设计中有较好的应用。但它有一个致命的缺点，就是收敛太慢。要提高逼近精度，只好增加多项式的次数，这在实际中是很不合算的。
切比雪夫从另一个角度去研究逼近问题。他不让多项式的次数趋于无穷，而是先把固定。对于，他提出在次多项式集合中，寻找一个多项式，使在上“最佳地逼近”。
§2、正交多项式
一、正交多项式的概念及性质
定义1：设区间上非负函数满足
(1)存在；(2)对非负连续函数，若，则在上，则称为区间上的权函数。
定义2：设，为上的权函数，则积分
称为与在上的内积。
定义3：设为上的次多项式，若满足 ，则称为上关于权函数的正交多项式系。
定理：上的正交多项式在内有个不同的实零点。
二、Legendre多项式
1、定义
，称为Legendre多项式。
2、性质
(1)正交性：。
(2)奇偶性：，即为奇（偶）数时，为奇（偶）函数。
(3)递推公式：。
三、Chebyshev多项式
1、定义
称为第一类Chebyshev多项式。
若记，即，则。
2、性质
(1)在上关于权正交，即。
证：。
(2)当为奇（偶）数时，为奇（偶）函数。
证：
。
(3)递推关系。
证：，
，
，
即。
(4)是次多项式，其最高项系数为。
证：由③易知为次多项式。

故，
即最高项系数为。
§3、最佳平方逼近
1、问题
对，在生成的子集中求一函数，使最小。
2、求解
记，
令，得，
，
即，也可改写为下列矩阵形式
——法方程。
3、用正交多项式做最佳平方逼近
若取，因，
由法方程可得，
从而即为的最佳平方逼近多项式。
若取，因，
由法方程可得，
，
从而即为的最佳平方逼近多项式。
例1、用正交多项式求在上的三次最佳平方逼近多项式。
解：用Chebyshev多项式，
，
，
故
。

用Legendre多项式
，
故。

§4、函数按切比雪夫多项式展开
定义：称为切比雪夫级数或广义傅立叶级数，
其中
根据切比雪夫多项式的性质，切比雪夫级数的部分和
可作为的近似最佳一致逼近多项式。
例2、将在上展成切比雪夫级数。
解：因为奇函数，从而也为奇函数，故

从而
注：的泰勒展式为

即切比雪夫展式可用较小的项数达到泰勒展式的精度，如对要达到10位有效数字，泰勒展式要25项，而切比雪夫展式仅要10项。
§5、离散数据的拟合与最小二乘法
1、离散数据的拟合问题
引例1：矿井中某处的瓦斯浓度与该处距地面的距离有关，现用仪器测得从地面到井下500米每隔50米的瓦斯浓度数据，根据这些数据完成下列工作：(1)寻找一个函数，要求从此函数中可近似求得从地面到井下500米之间任意一点处的瓦斯浓度；(2)估计井下600米处的瓦斯浓度。
根据所学内容，分别给出解决上述问题的方法，并说明理由。
对于第一个问题，可根据已有瓦斯浓度数据，求出其样条插值函数，由即可较为准确地求得从地面到井下500米之间任意一点处的瓦斯浓度。
但对第二个问题不宜用插值方法，因为600米已超出所给数据范围，用插值函数外推插值区间外的数据会产生较大的误差。
解决第二个问题的常用方法是，根据地面到井下500米处的数据求出瓦斯浓度与地面到井下距离之间的函数关系，由求井下600米处的瓦斯浓度。
引例2：在某化学反应中，根据实验测得生成物浓度与时间的关系如下表，求浓度与时间的对应函数关系，并据此求出反应速度曲线。
时间x
1
2
3
4
5
6
7
8
9
10
浓度y
4.00
6.40
8.00
8.80
9.22
9.50
9.70
9.86
10.00
10.20
11
12
13
14
15
16
10.32
10.42
10.50
10.55
10.58
10.60
显然，从理论上讲是客观存在的，但在实际中仅由离散数据 是不可能得出的精确表达式的，只能寻找的一个近似表达式，这种问题称为离散数据的曲线拟合问题。
曲线拟合需解决如下两个问题：
(1)线型的选择；(2)中参数的计算。
2、线型的选择
通常主要根据专业知识和散点图确定的线型，常见的线型有：
(1)线性函数：；
(2)可化为线性函数的非线性函数，如

(1)

(3)非线性函数。
3、计算线性拟合的最小二乘法
做数据的散点图，若近似为直线，则可用线性函数拟合。
对于本问题通常采用最小二乘法，即所求参数使得在处的值与之差的平方和
最小，
将上式视为关于的二元函数，对分别关于求偏导并令其为零
，即，
解上方程组得
，。
例1、观测物体的直线运动，得出以下数据，求运动方程。
时间t
0 0.9 1.9 3.0 3.9 5.0
距离s
0 10 30 50 80 110
解：

数据点的折线图

所求运动方程为
可用相关系数衡量数据线性化程度，本例中相关系数，这表明数据的线性相关性较好。

拟合运动方程与数据点对照图
4、可线性化的非线性拟合
例2、根据本节引例中的数据拟合出生成物浓度与时间的近似表达式。
解：

数据的散点图
(1) 用双曲线型拟合
令，则为线性函数。
经计算，从而

(2) 用指数线型拟合
两边取对数，令，则为线性函数。
经计算，从而

两种线型的误差分析：
令（均方误差），分别将和代入计算得，，，显然，此结果表明，线型(2)优于线型(1)。
作业：在某化学反应中，根据实验所得分解物的浓度与时间关系如下，求浓度y与时间t的拟合曲线。(用指数线型拟合)
时间x
5
10
15
20
25
30
35
40
45
50
55
浓度y
1.27
2.16
2.86
3.44
3.87
4.15
4.37
4.51
4.58
4.62
4.64

拟合结果的评价准则：
设数据点为，拟合函数为，则称为拟合残差。
准则1：最大误差准则，即最小。
准则2：平均误差准则，即最小。
准则3：均方误差准则，即最小。
上述三准则与数据的大小、量纲有关，不具可比性。
下面给出一种规范的误差准则
，其中
显然，，越接近于1，拟合效果越好。
§7、Fourier逼近与FFT
一、周期函数的最佳平方逼近
设以为周期，则称为的傅立叶级数，其中。
称为傅立叶级数的部分和，也称为次三角多项式，下面讨论三角多项式对周期函数的最佳平方逼近。
1、连续情形
设是以为周期的平方可积函数，则因= 为上的正交函数系，事实上，

故根据用正交多项式作最佳平方逼近的法方程，在上的最佳平方逼近多项式存在且唯一，其系数

即傅氏级数的部分和即为的最佳平方逼近三角多项式。
2、离散情形
① 在上取的个观测值，其中
记

可证，
，即共个向量构成正交系。
② 取正交系对进行最佳逼近，则

其中
二、快速Fourier变换(FFT)
1、Fourier变换——Fourier级数的推广
对任意函数，

则称为的Fourier变换，称为的Fourier逆变换，与称为Fourier变换对。
常用的Fourier变换有
(1) 方脉冲， 函数

(2)

2、离散的Fourier变换
对给定序列
，
分别称为离散Fourier变换与离散Fourier逆变换。
若给出在上的值，则的离散Fourier变换为。
采样定理：若的频率范围为，则只有当采样间隔时，才能正确恢复。此时，采样频率，称为Nyguist频率。
3、快速Fourier变换(FFT)的计算
从的表达式中可以看出，计算一个需要次乘法、次加法，计算所有需要次乘法。当较大时，就很大，即常规离散Fourier变换计算量太大。
1965年Cooley和Tukey提出了一种快速Fourier变换，其乘法次数仅为 ，大大降低了计算量。
例如，当时，。
第三章上机
实验目的：
5、 熟悉Maple中的拟合、求相关系数等命令；
6、 通过对具体数据做可线性化的非线性拟合，了解曲线拟合的具体步骤。
实验内容：
在某化学反应中，根据实验所得分解物的浓度与时间关系如下，求浓度y与时间x的拟合曲线。
时间x
5
10
15
20
25
30
35
40
45
50
55
浓度y
1.27
2.16
2.86
3.44
3.87
4.15
4.37
4.51
4.58
4.62
4.64
5、 做出数据的散点图，根据的大致形状，选择相应的线型(用指数线型或双曲线型拟合)；
6、 将方程线性化，用Maple相应命令求出此线性方程及相关系数；
7、 将线性方程还原为原非线性方程，并将此方程的图形与散点图加以对照，观察拟合效果。
Pade逼近（有理逼近）简介

借助函数的Taylor级数来研究函数的性质，或直接用它的部分和逼近该函数，不仅是纯数学领域中经常使用的手段，也是应用中赖以发展的方法之一。在数值计算领域中，用Taylor多项式来逼近一个函数并进而导致各种有效的数值方法巳司空见惯，并在很多情况下获得了成功。但有时这种方法的应用显露出某些缺陷。这些缺陷一般来说是由于函数的Taylor级数的收敛速度较慢或其收敛范围较狭。如果采用有理函数作为逼近工具则能常常获得出人意外的好结果。
例1、的Taylor级数为

其部分和为

用计算的近似值，收敛速度很慢。比如为了保证误差不超过，就需要取。
若取有理函数对其进行逼近，则效果大不相同。
例2、的Taylor级数为

当时，上述级数发散，但用有理函数逼近可扩大其逼近范围。
Ch4、数值积分与数值微分
§1、引言
1、对采用数值积分的原因
①的原函数不是初等函数或过于复杂，如等；
②为离散形式。
2、数值积分的基本思想——机械求积
将表示为在若干点处值的线性组合即
，、和分别称为求积节点、求积系数和余项。
称为求积公式
3、代数精度
定义：若对于不高于次的多项式，余项，而总存在次多项式使，则称求积公式代数精度为。
4、插值型求积公式
定义：对及，做插值，则，，称此求积公式为插值型求积公式。
显然，插值型求积公式的代数精度至少为。
§2、Newton-Cotes公式
一、Newton-Cotes公式
1、定义：对插值型求积公式，若取等距节点， ，则，，，此时称求积公式为Newton-Cotes公式。
当时， 梯形公式
当时，称为Simpson公式

当时，称为Simpson-3/8公式

2、余项

Newton-Cotes公式的代数精度为
3、收敛性与数值稳定性
① 求积公式收敛的必要条件为有界；
② 对较大的，Newton-Cotes公式不稳定，不宜采用。

二、复化求积法
将等分，在每个小区间上用低阶Newton-Cotes公式求得该区间的积分值，则，此方法称为复化求积法。
1、复化梯形公式

2、复化Simpson公式

例1、分别用复化梯形公式(n=8)和复化Simpson公式(n=4)计算。
解：
x 0 1/8 2/8 3/8 4/8 5/8 6/8 7/8 1
f(x) 1 0.9973978 0.9896158 0.9767267 0.9588510 0.9361556 0.9088516 0.8771925 0.8414709

3、复化公式的误差
复化公式余项为

§3、Romberg加速收敛法
1、加速收敛技巧
在用序列逼近时，若能从产生出新序列，它比更快地收敛于，此即加速收敛技巧。
例如用逼近时
，，

类似地
此加速收敛算法称为Richardson外推算法。

2、Romberg求积法

将步长逐次减半，得序列，分析误差可得新序列。

用逼近I的算法称为Romberg算法。

§4、高斯型求积公式
1、高斯公式与高斯点
定义：对插值型求积公式，若能选择适当的
使其具有次代数精度，则称此求积公式为高斯公式，其节点称为高斯点。
2、高斯公式的构造
定理：求积公式为高斯公式的充要条件是以为零点的多项式与任意不超过次的多项式均正交，即。
证：必要性：设为次数不超过的多项式，则不超过次，
因为高斯公式，故，
又，从而。
充分性：对次数不超过的多项式，用除，商为，余式为，则次数均不超过，且，

又，故
推论：上次正交多项式的零点即为Gauss点。
证：因为正交多项式与比它次数低的任意多项式都正交，且上次正交多项式恰好有个不同的实零点，故得证。
3、Gauss-Legendre公式
①对积分区间，取其上次Legendre多项式的零点为节点，则称为Gauss-Legendre求积公式。
此时，，
令

又

故。
两点Gauss公式：
三点Gauss公式：
例、
解：两点Gauss公式：
两点梯形公式：
三点Gauss公式：
三点Simpson公式：

②若积分区间为，可作代换，则

4、高斯公式的稳定性
①Gauss公式中的
证：因为次多项式，为次，Gauss公式准确成立，
，故。
②Gauss公式是数值稳定的。
证：设的近似值，则为的近似值，

Ch5、常微分方程的数值解法
§1、基本概念与Euler公式
1、数值解法的必要性
① 不能给出解的解析表达式；② 求封闭形式的解计算量太大。
例如

2、数值解法的基本思想——离散化
对初值问题求出解在节点上值的近似值，其中。

3、Euler公式
将在上积分，，得，用数值积分法求。
① （矩形公式），得 Euler公式
② （矩形公式），得 后退的Euler公式
③ （梯形公式）
得 梯形公式（隐形）

4、改进的Euler公式
Euler公式计算简便，但精度差，梯形公式为隐式，计算较复杂，但精度较高，可将两者结合。

称为改进的Euler公式，上式也可写为

例1、求解初值问题 ()
解：Euler公式
改进的Euler公式
x
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Euler
1.100
1.192
1.277
1.358
1.435
1.509
1.580
1.650
1.717
1.785
Euler改
1.096
1.184
1.266
1.343
1.416
1.486
1.553
1.616
1.678
1.738
准确
1.095
1.183
1.265
1.342
1.414
1.483
1.549
1.612
1.673
1.732

§2、Runge-Kutta方法
1、Taylor级数方法与阶
对，有Taylor级数
将此级数截断，并用代替，得阶Taylor公式

显然截断误差为
定义：若某方法的截断误差为，则称此方法精度为阶。

2、Runge-Kutta方法基本思想
，，
——平均斜率
①取，即为Euler公式；
②取，即为后退的Euler公式；
③取，即为梯形公式。
借用Taylor级数法的思想，将中的(平均斜率)表示为在若干点处值的线性组合，通过选择组合系数使公式达到一定的阶。

3、二阶Runge-Kutta方法
选为在某两点处值的线性组合，即，其中，，待定。
将代入得

将上式与二阶Taylor公式对比得（*）。
根据Euler公式， ，代入得，，其中满足（*）式，称之为二阶Runge-Kutta公式。
特别地，当时，
——改进的Euler公式

4、四阶Runge-Kutta方法
三阶Runge-Kutta方法较少使用，仿二阶Runge-Kutta方法，可得四阶Runge-Kutta公式，经典的四阶Runge-Kutta公式为

特点：①单步、自开始；②精度高，误差为，四阶；③数值稳定；④要计算四次函数值；⑤对解的光滑性要求高。

§3、单步法的收敛性与稳定性
1、收敛性
定义：若某数值解法对固定的，当时（此时），，则称此方法收敛。
例2、对典型方程考察Euler方法的收敛性。
解：Euler公式为，

而，即， 故收敛。

定理：若数值方法中的关于满足Lipschitz条件，则该方法收敛。

2、稳定性
定义：若某方法在节点值上有大小为的摄动，而其后各节点上的误差无效不超过，则称此方法是稳定的。
例3、对方程，考察Euler公式和后退的Euler公式的稳定性。
解：对应的Euler公式为，
若在上有摄动值，而它使产生的摄动值为，则
，
显然，即时，Euler公式稳定，称之为条件稳定。
后退的Euler公式为，

即后退的Euler公式无条件稳定。
Ch6、解非线性方程的数值方法
§1、二分法
零点定理：设，且，则在内至少有一根。
令为的中点，若，则内有根，否则内有根。
类似地进行步之后，设有根区间为，则，可取为的近似根，显然误差。
特点：
§2、迭代法
1、迭代格式
对非线性方程，给定一个初值，按照某种方法产生一个序列，使得，且。
例如，将改写为，令(Picard迭代)

2、收敛性与误差估计
定理1：若①对任意，有(压缩映射)；②存在正数，使对任意，有(Lipschitz条件)，则对任意，迭代序列收敛于的唯一根，且有误差估计式

证：令，由Lipschitz条件，