应用数值分析全书课件整本书电子教案

应用数值分析

Applied

NumericalAnalysis

提问：数值分析是做什么用的？数学建模

构造算法程序设计上机计算求出结果实际问题近似解

数值分析

计算机输入复杂问题或运算第一章科学计算简介Therearethreegreatbranchesofscience:theory,experimentandcomputation.Thefundamentallawofcomputerscience:Asmachinesbecomemorepowerful,theefficiencyofalgorithmsgrowsmoreimportant,notless.—L.N.Trefethen一、研究对象数值分析（NumericalAnalysis），也称数值方法、计算方法或计算机数学，是计算数学的一个主要部分，计算数学是数学科学的一个分支，它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现，是用公式表示数学问题以便可以利用算术和逻辑运算解决这些问题的技术。二、学科特点

算法能在计算机上实现，并有好的计算复杂性；

面向计算机，提供切实可行的有效算法；

有可靠理论，对算法进行误差分析，并能达到精度要求；

通过数值实验

证明算法行之有效；§1数值分析简介三、学习理由1数值方法能够极大地覆盖所能解决的问题类型；2学习数值分析可以让用户更加智慧地使用“封装过的”软件；3很多问题不能直接用封装的程序解决，如果熟悉数值方法并擅长计算机编程的话，就可以自己设计程序解决问题；4数值分析是学习使用计算机的有效载体，对于展示计算机的强大和不足是非常理想的；5数值分析提供了一个增强对数学理解的平台.§2误差一.来源与分类

从实际问题中抽象出数学模型——模型误差

通过测量得到模型中参数的值——观测误差

求(数学表达的)近似解——方法误差(截断误差)

模型的准确解与用数值方法求得的准确解之差称为“截断误差”。

机器字长有限——舍入误差简化…实际算法:有限、四则运算化…（理论计算误差）大家一起猜？11/e解：将作Taylor展开后再积分S4R4取则称为截断误差|

舍入误差

|=0.747……由截去部分引起由留下部分引起二、误差的定义

绝对误差其中x为精确值，x*为x的近似值。，例如：上常记为，称为绝对误差限，一般地，的上限记为

由于通常准确值x是不知道的，所以误差e*

的准确值也不可能求出，但根据具体情况，可事先估计出误差的范围——误差绝对值不能超过某个正数，我们把叫做误差绝对值的“上界”，或称“误差限”。≤≤≤工程注：e*理论上讲是唯一确定的，可能取正，也可能取负。e*>0时，x*称为强近似值，e*<0时，x*称为弱近似值e*>0不唯一，当然e*越小越具有参考价值。x的相对误差限常定义为注：从的定义可见，实际上被偷换成了，而后才考察其上限。那么这样的偷换是否合法？严格的说法是，与是否反映了同一数量级的误差？关于此问题的详细讨论可见教材p5。实际计算中，相对误差通常取为：相对误差三、有效数字

若近似值x*的误差限是某一位的半个单位,该位到x*

的第一位非零数字共有n位,就说x*有n位有效数字.例:问：有几位有效数字？请证明你的结论。43注：0.2300有4位有效数字，而0.0023只有2位有效数字。12300如果写成0.123105，则表示只有3位有效数字。

数字末尾的0不可随意省去！用科学计数法，记（其中）。若（即的截取按四舍五入规则），则有n位有效数字，精确到。注：关于有效数字有以下几点说明：1、用四舍五入法取准确值的前n位作为近似值，则x*必有n位有效数字；2、有效数字位数相同的两个近似数，绝对误差限不一定相同；3、将任何数乘以10m(m为整数)，等于移动该数的小数点，并不影响它的有效数字的位数；4、准确值被认为具有无穷位有效数字.有效数字与相对误差的关系

有效数字

相对误差限已知x*有n位有效数字，则其相对误差限为

相对误差限

有效数字已知x*的相对误差限可写为则可见x*至少有n位有效数字。例：为使的相对误差小于0.001%,至少应取几位有效数字？解：假设

*取到n

位有效数字，则其相对误差上限为要保证其相对误差小于0.001%，只要保证其上限满足已知a1=3，则从以上不等式可解得n>6log6，即n6，应取

*=3.14159。§3

误差的传播一、误差估计特别地，由上式可得和、差、积、商之误差及相对误差公式注：函数值的绝对误差等于函数的全微分，自变量的微分即为自变量的误差；函数值的相对误差等于函数的对数的全微分。例.)871.030.1(~005.00022.00005.030.1871.0sin005.030.1871.0cos)~(sincos49543.030.1871.0cos)871.030.1(~

22能有二位有效数字，所以而，由于，解：fuuxyyfxyxffu=<»´+´»-=¶¶-=¶¶»==e二、病态问题与条件数三、算法的数值稳定性(NumericalStability)例：蝴蝶效应

——青岛的一只蝴蝶翅膀一拍，风和日丽的纽约就刮起台风来了？！QFNY以上是一个病态问题关于本身是病态的问题，我们还是留给数学家去头痛吧！例：计算

公式一:注意此公式精确成立记为则初始误差????!!!发生了什麽?!考察第n步的误差我们有责任改变。造成这种情况的是不稳定的算法迅速积累,误差呈递增走势.可见初始的小扰动

公式二:注意此公式与公式一在理论上等价。方法：先估计一个IN

,再反推要求的In(n<<N)。可取取

我们很幸运！考察反推一步的误差：以此类推，对n<N

有：误差逐步递减,这样的算法称为稳定的算法。

在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。§4数值误差控制1.避免相近二数相减例：a1=0.12345，a2=0.12346，各有5位有效数字。而a2

a1=0.00001，只剩下1位有效数字。

几种经验性避免方法：当|x|<<1时：2.避免小分母:分母小会造成舍入误差增大3.避免大数吃小数例：用单精度计算的根。精确解为

算法1：利用求根公式在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.00000000011010，取单精度时就成为：109+1=0.100000001010+0.000000001010=0.100000001010大数吃小数

x3.81574

y0.0001==38157.4

x3.81574

y+

y0.0001+0.00001==34688.5算法2：先解出再利用注：求和时从小到大相加，可使和的误差减小。例：按从小到大、以及从大到小的顺序分别计算1+2+3+…+40+1094.先化简再计算，减少步骤，避免误差积累。再如秦九韶算法补充材料

20世纪十大算法在世纪之交，经过科学家的评选和投票，20世纪的十大算法得到了国际学术界的公认。现在按照时间顺序列于下。本课程将讨论其中一部分。Monte-Carlo方法（1946）；

(2)线性规划的单纯形算法（1947）；

线性代数方程组的krylov子空间迭代方法（1950）；

(4)矩阵计算的分解方法（1951）；(5)Fortran计算机语言编译器（1957）；(6）计算矩阵特征值问题的QR方法（1961）；(7)快速排序算法（1962）；(8)快速Fourier变换（1965）；(9)整数关系算法（1977）；

(10)快速多极算法（1987）第二章插值法插值法是数值分析中很古老的分支，有着悠久的历史。等距节点内插公式是由我国隋朝数学家刘焯（544-610年）首先提出的，不等距节点内插公式是由唐朝数学家张遂（683-727年）提出的，比西欧学者的相应结果早一千多年（2.1）

设函数在区间上有定义，且已知在相异点上的值，若存在一简单函数，使成立，就称为的插值函数，点称为插值节点，包含节点的区间称为插值区间，求插值函数的方法称为插值法.

若是次数不超过的代数多项式，其中为实数，就称为插值多项式，相应的插值法称为多项式插值.本章只讨论多项式插值与分段插值.

若为分段的多项式，就称为分段插值.

若为三角多项式，就称为三角插值.即一、待定系数法§1代数多项式插值上的函数值,求次数不超过的多项式，使（2.3）

设在区间上给定个点代数多项式插值问题的具体提法就是:唯一性说明：不论用何种方法来构造，也不论用何种形式来表示插值多项式,只要满足插值条件(2.1)其结果都是相互恒等的。

二、Lagrange插值多项式（1）线性插值

线性插值是代数插值的最简单形式。假设给定了函数f(x)在两个互异的点的值，，，,

现要求用线性函数近似地代替。选择参数a和b，使。称这样的线性函数

为

的线性插值函数。线性插值的几何意义:用通过点和的直线近似地代替曲线

由解析几何知道,这条直线用点斜式表示为（2）抛物插值抛物插值又称二次插值，它也是常用的代数插值之一。设已知在三个互异点

的函数值，要构造次数不超过二次的多项式使满足二次插值条件。几何意义是用经过3个点的抛物线

近似代替曲线。该三元一次方程组的系数矩阵

的参数直接由插值条件决定，即满足下面的代数方程组：的行列式是范德蒙行列式，当时，方程组的解唯一。例2.2已知

的函数表

1

3

1

2求线性插值多项式,并计算

的值解:由线性插值多项式公式得例2.3求过点(0,1)、(1,2)、(2,3)的三点插值多项式解:由Lagrange插值公式（给定的三个点在一条直线上）例2.4已知

的观测数据012419233构造Lagrange插值多项式.解

四个点可构造三次Lagrange插值多项式:基函数为Lagrange插值多项式为为便于上机计算,常将拉格朗日插值多项式(5.8)改写成例2.5已知用线性插值估计在

时的截断误差.解:由插值余项公式知

因为二、Newton插值多项式所以f[x1,x2]-f[x0,x1]x2–x0

首先根据给定函数表造出均差表.2.6给出的函数表（见表2-2），求4次牛顿插值多项式，并由此计算的近似值.例

从均差表看到4阶均差近似常数，5阶均差近似为0.

故取4次插值多项式做近似即可.于是

按牛顿插值公式，将数据代入截断误差这说明截断误差很小，可忽略不计.xif[xi]f[xi,xi+1]f[xi,xi+1,xi+2]114293例2.7已知

的平方根值，求解：三、Matlab函数§3分段低次插值一.龙格现象及高次插值的病态性质

对于函数,在区间上取节点,所作Lagrange插值多项式为,当时,内收敛于在这区间之外发散，这一现象称为Runge现象。

二.分段线性插值直观上容易想象,如果不用多项式曲线，而是将曲线的两个相邻的点用线段连接，这样得到的折线必定能较好地近似曲线。而且只要连续，节点越密，近似程度越好。由此得到启发，为提高精度，在加密节点时，可以把节点间分成若干段，分段用低次多项式近似函数，这就是分段插值的思想。用折线近似曲线，相当于分段用线性插值，称为分段线性插值。设已知函数在上的

个节点

上的函数值,作一个插值函数,s.t.,(1);(2)在每个小区间上，是线性函数，则称函数为上关于数据的分段线性插值函数。

由Lagrange线性插值公式容易写出的分段表达式为了建立的统一表达式，我们需要构造一组基函数：且在每个小区间上是线性函数。在几何上就是用折线替代曲线,如右图所示若用插值基函数表示,则在

a,b

上

其中定理2.4

如果

在上二阶连续可微，则分段线性插值函数

的余项有以下估计其中

。说明：当节点加密时，分段线性插值的误差变小，收敛性有保证。另一方面，在分段线性插值中，每个小区间上的插值函数只依赖于本段的节点值，因而每个节点只影响到节点邻近的一、二个区间，计算过程中数据误差基本上不扩大，从而保证了节点数增加时插值过程的稳定性。但分段线性插值函数仅在区间

上连续，一般地，在节点处插值函数不可微，这就不能满足有些工程技术问题的光滑要求。例2.8已知

在四个节点上的函数值如下表所示304560901求

在区间上的分段连续线性插值函数

解将插值区间

分成连续的三个小区间

则

在区间

上的线性插值为

在区间

45,60

上的线性插值为

在区间

60,90

上的线性插值为将各小区间的线性插值函数连接在一起，得§4三次样条插值

我们知道,给定n+1个节点上的函数值可以作n次插值多项式,但当n较大时,高次插值不仅计算复杂,而且可能出现Runge现象,采用分段插值虽然计算简单、也有一致收敛性,但不能保证整条曲线在连接点处的光滑性,如分段线性插值,其图形是锯齿形的折线,虽然连续,但处处都是“尖点”,因而一阶导数都不存在,这在实用上,往往不能满足某些工程技术的高精度要求。如在船体、飞机等外形曲线的设计中,不仅要求曲线连续,而且要有二阶光滑度,即有连续的二阶导数。这就要求分段插值函数在整个区间上具有连续的二阶导数。因此有必要寻求一种新的插值方法,这就是样条函数插值法

一、三次样条函数定义2.2设函数定义在区间

a,b

上，给定n+1个节点和一组与之对应的函数值，若函数满足:（1）在每个节点上满足

（2）在

a,b

上有连续的二阶导数（3）在每个小区间

xi,xi+1

(i=0,1,…,n-1)

上是一个三次多项式。则称为三次样条插值函数。在上确定4个待定系数，共确定4n个参数

求出二、三次样条插值函数的求法

设

在节点xi处的二阶导数为

连续两次积分得由上讨论可知,只要确定这n+1个值,就可定出三样条插值函数S(x)。为了求出,利用一阶导数在子区间连接点上连续的条件对上式求导一次,得在区间

xi-1,xi

上的表达式为（2.32）

也就是在右端点xi上有在左端点xi-1上有将上式中的i-1改为i,即得在子区间

xi,xi+1

上的表达式,并由此得利用在内接点的连续性,即就可得到关于参数的一个方程上式两边同乘以,即得方程

若记

简写即

这是一个含有n+1个未知数、n-1个方程的线性方程组.要完全确定的值还需要补充两个条件,这两个条件通常根据实际问题的需要，根据插值区间

a,b

的两个端点处的边界条件来补充。第一种边界条件：即已知插值区间两端的一阶导数值：则可得到包含Mi的两个线性方程,由(2.33)知,S(x)在子区间

上的导数为由条件得即

(2.37)同理,由条件得

边界条件的种类很多，常见的有以下3种：(2.38)

将式（2.36）和式（2.37）以及式（2.38）合在一起即得确定的线性方程组(2.39)其中第二种边界条件:即已知插值区间两端的二阶导数值:,由于在区间端点处二阶导数

，所以方程（2.36）中实际上只包含有n-1个未知数，从而得方程组(2.40)

第三种边界条件:由与，可得

和

(2.41)(2.42)(2.43)其中将式(5.36),(5.41),(5.42)合在一起，即得关于的线性方程组。(2.44)

利用线性代数知识,可以证明方程组（2.39）,（2.40）和（2.44）的系数矩阵都是非奇异的，因此有惟一解。例2.9已知的函数值如下：x1245f(x)1342在区间

1,5

上求三次样条插值函数S(x),使它满足边界条件解:这是在第二种边界条件下的插值问题，故确定的方程组形如前面所示，由已知边界条件,有则得求解的方程组为根据给定数据和边界条件算出与

则得方程组解得又

即得S(x)在各子区间上的表达式,由式（2.32）知,S(x)在上的表达式为代入式(2.32)将代入上式化简后得

同理S(x)在上的表达式为

S(x)在上的表达式为故所求的三次样条插值函数S(x)在区间上的表达式为三、误差界与收敛性

用三次样条绘制的曲线不仅有很好的光滑度，而且当节点逐渐加密时，其函数值在整体上能很好地逼近被插函数，相应的导数值也收敛于被插函数的导数，不会发生龙格现象。因此三次样条在计算机辅助设计中有广泛的应用。本章小结

本章介绍的插值法是实用性很强的方法。它们解决的实际问题虽然各式各样，但抽象为数学问题却有它的共性，即利用已知的数据去寻求某个较为简单的函数P(x)来逼近f(x)。插值法给出了寻求这种近似函数的原则，以及构造近似函数的几种具体方法。插值法要求近似函数在已知的数据点必须与f(x)完全一致。

插值法中的拉格朗日插值多项式是研究数值微积分与微分方程数值解的重要工具。牛顿插值多项式是拉格朗日插值多项式的变形，具有承袭性，比拉格朗日插值多项式节省计算量。分段低次多项式插值由于具有良好的稳定性与收敛性，且算法简单，便于应用。特别是应用广泛的三次样条插值，不但有较好的稳定性和收敛性，而且具有较好的光滑性，从而满足了许多实际问题的要求。§3分段低次插值一.龙格现象及高次插值的病态性质

对于函数,在区间上取节点,所作Lagrange插值多项式为,当时,内收敛于在这区间之外发散，这一现象称为Runge现象。

二.分段线性插值直观上容易想象,如果不用多项式曲线，而是将曲线的两个相邻的点用线段连接，这样得到的折线必定能较好地近似曲线。而且只要连续，节点越密，近似程度越好。由此得到启发，为提高精度，在加密节点时，可以把节点间分成若干段，分段用低次多项式近似函数，这就是分段插值的思想。用折线近似曲线，相当于分段用线性插值，称为分段线性插值。设已知函数在上的

个节点

上的函数值,作一个插值函数,s.t.,(1);(2)在每个小区间上，是线性函数，则称函数为上关于数据的分段线性插值函数。

由Lagrange线性插值公式容易写出的分段表达式为了建立的统一表达式，我们需要构造一组基函数：且在每个小区间上是线性函数。在几何上就是用折线替代曲线,如右图所示若用插值基函数表示,则在

a,b

上

其中定理2.4

如果

在上二阶连续可微，则分段线性插值函数

的余项有以下估计其中

。说明：当节点加密时，分段线性插值的误差变小，收敛性有保证。另一方面，在分段线性插值中，每个小区间上的插值函数只依赖于本段的节点值，因而每个节点只影响到节点邻近的一、二个区间，计算过程中数据误差基本上不扩大，从而保证了节点数增加时插值过程的稳定性。但分段线性插值函数仅在区间

上连续，一般地，在节点处插值函数不可微，这就不能满足有些工程技术问题的光滑要求。例2.8已知

在四个节点上的函数值如下表所示304560901求

在区间上的分段连续线性插值函数

解将插值区间

分成连续的三个小区间

则

在区间

上的线性插值为

在区间

45,60

上的线性插值为

在区间

60,90

上的线性插值为将各小区间的线性插值函数连接在一起，得§4三次样条插值

我们知道,给定n+1个节点上的函数值可以作n次插值多项式,但当n较大时,高次插值不仅计算复杂,而且可能出现Runge现象,采用分段插值虽然计算简单、也有一致收敛性,但不能保证整条曲线在连接点处的光滑性,如分段线性插值,其图形是锯齿形的折线,虽然连续,但处处都是“尖点”,因而一阶导数都不存在,这在实用上,往往不能满足某些工程技术的高精度要求。如在船体、飞机等外形曲线的设计中,不仅要求曲线连续,而且要有二阶光滑度,即有连续的二阶导数。这就要求分段插值函数在整个区间上具有连续的二阶导数。因此有必要寻求一种新的插值方法,这就是样条函数插值法

一、三次样条函数定义2.2设函数定义在区间

a,b

上，给定n+1个节点和一组与之对应的函数值，若函数满足:（1）在每个节点上满足

（2）在

a,b

上有连续的二阶导数（3）在每个小区间

xi,xi+1

(i=0,1,…,n-1)

上是一个三次多项式。则称为三次样条插值函数。在上确定4个待定系数，共确定4n个参数

求出二、三次样条插值函数的求法

设

在节点xi处的二阶导数为

连续两次积分得由上讨论可知,只要确定这n+1个值,就可定出三次样条插值函数S(x)。为了求出,利用一阶导数在子区间连接点上连续的条件对上式求导一次,得在区间

xi-1,xi

上的表达式为（2.32）

也就是在右端点xi上有在左端点xi-1上有将上式中的i-1改为i,即得在子区间

xi,xi+1

上的表达式,并由此得利用在内接点的连续性,即就可得到关于参数的一个方程上式两边同乘以,即得方程

若记

简写即

这是一个含有n+1个未知数、n-1个方程的线性方程组.要完全确定的值还需要补充两个条件,这两个条件通常根据实际问题的需要，根据插值区间

a,b

的两个端点处的边界条件来补充。第一种边界条件：即已知插值区间两端的一阶导数值：则可得到包含Mi的两个线性方程,由(2.33)知,S(x)在子区间

上的导数为由条件得

即

(2.37)同理,由条件得

边界条件的种类很多，常见的有以下3种：(2.38)

将式（2.36）和式（2.37）以及式（2.38）合在一起即得确定的线性方程组(2.39)其中第二种边界条件:即已知插值区间两端的二阶导数值:,由于在区间端点处二阶导数

，所以方程（2.36）中实际上只包含有n-1个未知数，从而得方程组(2.40)

第三种边界条件:由与，可得

和

(2.41)(2.42)(2.43)其中将式(2.36),(2.41),(2.42)合在一起，即得关于的线性方程组。(2.44)

利用线性代数知识,可以证明方程组（2.39）,（2.40）和（2.44）的系数矩阵都是非奇异的，因此有惟一解。例2.9已知的函数值如下：x1245f(x)1342在区间

1,5

上求三次样条插值函数S(x),使它满足边界条件解:这是在第二种边界条件下的插值问题，故确定的方程组形如前面所示，由已知边界条件,有则得求解的方程组为根据给定数据和边界条件算出与

则得方程组解得又

即得S(x)在各子区间上的表达式,由式（2.32）知,S(x)在上的表达式为代入式(2.32)将代入上式化简后得

同理S(x)在上的表达式为

S(x)在上的表达式为故所求的三次样条插值函数S(x)在区间上的表达式为三、误差界与收敛性

用三次样条绘制的曲线不仅有很好的光滑度，而且当节点逐渐加密时，其函数值在整体上能很好地逼近被插函数，相应的导数值也收敛于被插函数的导数，不会发生龙格现象。因此三次样条在计算机辅助设计中有广泛的应用。本章小结

本章介绍的插值法是实用性很强的方法。它们解决的实际问题虽然各式各样，但抽象为数学问题却有它的共性，即利用已知的数据去寻求某个较为简单的函数P(x)来逼近f(x)。插值法给出了寻求这种近似函数的原则，以及构造近似函数的几种具体方法。插值法要求近似函数在已知的数据点必须与f(x)完全一致。

插值法中的拉格朗日插值多项式是研究数值微积分与微分方程数值解的重要工具。牛顿插值多项式是拉格朗日插值多项式的变形，具有承袭性，比拉格朗日插值多项式节省计算量。分段低次多项式插值由于具有良好的稳定性与收敛性，且算法简单，便于应用。特别是应用广泛的三次样条插值，不但有较好的稳定性和收敛性，而且具有较好的光滑性，从而满足了许多实际问题的要求。

第三章逼近方法

函数逼近的处理方法：

插值法

最小二乘曲线（最小二乘回归）内容概要3.1基本概念3.2函数的最佳平方逼近3.3曲线拟合的最小二乘法3.4最佳平方三角逼近与快速傅立叶变换3.5Matlab曲线拟合工具箱介绍

f(x)p(x)§3.1基本概念函数逼近问题：对于函数类A中给定的函数，记作，要求在另一类简单的便于计算的函数类B中求函数，使

与的误差在某种度量意义下达到最小。

范数与赋范数空间

定义：设是实数域上的线性空间，，如果存在唯一实数，满足条件：

（正定性）（齐次性）（三角不等式）

则称为线性空间上的范数，与一起称

为赋范线性空间，记为。例如，对上的向量，有三种常用范数：类似地，对，可定义常用范数：内积与内积空间3.1.1正交函数族与正交多项式3.1.2勒让德（Legendre）多项式3.1.3Chebyshev（切比雪夫）多项式3.1.3Chebyshev（切比雪夫）多项式3.1.3Chebyshev（切比雪夫）多项式3.1.4拉盖尔（Laguerre）多项式3.1.5埃尔米特（Hermite）多项式3.2函数的最佳平方逼近3.2.2用正交函数族作最佳平方逼近3.3曲线拟合的最小二乘法3.3.1最小二乘原理3.3.2法方程3.3.3常用的拟合方法

例3.5已知实测数据表如下,确定数学模型y=aebx,用最小二乘法确定a，b。i01234

xi

yi1.001.251.501.752.005.105.796.537.458.46i01234

xi

yi

zi1.001.251.501.752.005.105.796.537.458.461.6291.7561.8762.0082.135i01234

xi

yi192531384419.032.349.073.397.8解按式(3-25)和(3-26)计算，得3.4最佳平方三角逼近与快速傅里叶变换3.4.1最佳平方三角逼近与三角插值3.4.2*快速傅氏变换（FFT）第四章数值微积分内容提要4.1数值积分的基本概念4.2牛顿-柯特斯公式4.3复化求积公式4.4龙贝格求积公式4.5高斯求积公式4.6数值微分4.1数值积分（numericalquadrature）的基本概念4.1.1数值求积分的基本思想但有时原函数不能用初等函数表示，有时原函数又十分复杂，难于求出或计算；另外如被积函数是由测量或数值计算给出的一张数据表示时，上述方法也不能直接运用。因此有必要研究积分的数值计算问题。积分中值定理：平均高度f(ζ)

a

ζ

b

yxy=f(x)0

a

b

yxy=f(x)0

a

f((a+b)/2)

b

yxy=f(x)0平均高度梯形公式平均高度中矩形公式更一般地，我们构造具有下列形式的求积公式求积节点求积系数

这类数值方法通常称为机械求积，其特点是将积分求值问题归结为函数值的计算，这就避开了牛顿-莱布尼兹公式需要寻求原函数的困难。4.1.2代数精度的概念利用代数精度的概念构造求积公式4.1.3插值型的求积公式4.1.4求积公式的收敛性与稳定性4.2Newton-Cotes公式4.2.1Cotes系数4.2.2偶阶求积公式的代数精度4.2.3几种低阶求积公式的余项4.3复化求积公式

在使用牛顿-柯特斯公式时将导致求积系数出现负数(当n≥8时,牛顿.柯特斯求积系数会出现负数)，因而不可能通过提高阶的方法来提高求积精度。为了提高精度通常采用将积分区间划分成若干个小区间，在各小区间上采用低次的求积公式(梯形公式或辛普森公式)，然后再利用积分的可加性，把各区间上的积分加起来，便得到新的求积公式，这就是复化求积公式的基本思想。本节只讨论复化的梯形公式和复化的辛普森公式。问题与基本思想4.3.1复化梯形公式4.3.2复化辛普森公式xi01/81/43/81/2f(xi)10.99739780.98961580.97672670.9588510xi5/83/47/81f(xi)0.93615560.90885160.84147090.84147094.4龙贝格求积公式4.4.1梯形公式的逐次分半算法4.4.2李查逊（Richardson）外推法第四章数值微积分内容提要4.1数值积分的基本概念4.2牛顿-柯特斯公式4.3复化求积公式4.4龙贝格求积公式4.5高斯求积公式4.6数值微分4.4龙贝格求积公式4.4.1梯形公式的逐次分半算法

于是可以逐次对分形成一个序列｛T1,T2,T4,T8,…},此序列收敛于积分真值I。当|T2n-Tn|<ε时，取T2n为I的近似值。以上算法称为变步长求积法。但由于此序列收敛太慢。下节我们将其改造成为收敛快的序列。4.4.2李查逊（Richardson）外推法4.4.3龙贝格求积公式如何提高收敛速度以节省计算量是龙贝格算法要讨论的中心问题。

这样我们从收敛较慢的{Tn}序列推出了收敛较快的{Sn}序列。可以证明{Sn}序列实际上就是逐次分半的复化辛普森公式序列。

这样我们从{Cn}序列又推出了收敛更快的{Rn}序列.{Rn}序列也称为龙贝格序列。我们从收敛较慢的{Tn}序列只用了一些四则运算，便推出了收敛更快的{Sn}序列,{Cn}序列和{Rn}序列。运算顺序表T1T2S1T4S2C1T8S4C2R1T16S8C4R2﹕﹕﹕T1T2S1T4S2C1T8S4C2R1T16S8C4R2﹕﹕﹕﹕kT2kS2k-1C2k-2R2k-300.920735510.93979330.946145920.94451350.94608690.946083030.94569090.94608330.94608310.9460831这里利用二分3次的数据（它们的精度都很差，只有两三位有效数字）通过三次加速求得R1=0.9460831,这个结果的每一位数字都是有效数字，可见加速效果是十分显著的。4.5高斯求积公式一般理论4.6数值微分4.6.1利用差商求导数

数值微分就是要用函数值的线性组合近似函数在某点的导数值。由导数定义差商近似导数得到数值微分公式。中点方法与误差分析hG(h)hG(h)hG(h)10.36600.050.35300.0010.35000.50.35640.010.35000.00050.30000.10.35350.0050.35000.00010.3000插值型的求导公式第五章解线性方程组的直接方法内容提要5.1引言5.2高斯消去法5.3高斯列主元消去法5.4矩阵三角分解法5.5平方根法5.5向量与矩阵的范数5.6误差分析引言关于线性方程组的数值解法一般有两类：1、直接解法：经过有限次的算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。本章主要研究此类问题的解法。2、迭代法：用某种极限过程去逐步逼近现行方程组精确解的方法。迭代法具有需要计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。高斯消去法再求解三角方程组,得高斯消去法的条件高斯列主元消去法列主元消去法矩阵三角分解法

Ax=b是线性方程组,A是n×n方阵,并设A的各阶顺序主子式不为零。令A(1)=A,当高斯消元法进行第一步后,相当于用一个初等矩阵左乘A(1)。不难看出，这个初等矩阵为重复这个过程，最后得到一般地

这就是说，高斯消去法实质上产生了一个将A分解为两个三角形矩阵相乘的因式分解，于是我们得到如下重要定理。当A进行LU分解后，Ax=b就容易解了.即Ax=b等价于:

追赶法

在一些实际问题中，例如解常微分方程边值问题，热传导方程以及船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线方程组其中|i-j|>1时,aij=0,且满足如下的对角占优条件:(1)|b1|>|c1|>0,|bn|>|an|>0(2)|bi|≥|ai|+|ci|,aici≠0,i=2,3,…,n-1.平方根法平方根法（Cholesky分解法）第一步第二步：求解下三角形方程组第三步：求解上三角形方程组用平方根法解对称正定方程组时，计算的元素需要开方。为了避免这一运算，引进改进的平方根法。定义1(向量范数)x和y是Rn中的任意向量,向量范数‖•‖是定义在Rn上的实值函数,它满足:(1)‖

x

‖≥0,并且当且仅当x=0时,‖

x

‖=0;(2)‖k

x

‖=|k|‖

x

‖,k是一个实数;(3)‖

x+y

‖≤‖

x

‖+‖

y

‖常使用的向量范数有三种,设x=(x1,x2,…,xn)T

敏感性与解的误差分析常使用的矩阵范数有三种,设x=(x1,x2,…,xn)T

由向量导出的矩阵范数：F范数误差分析内容提要

6.1单步定常迭代法

6.2基于矩阵分裂的迭代法

6.3特殊方程组迭代法的收敛性

6.4迭代法在数值求解偏微分方程中的应用第六章解线性代数方程组的迭代法

即AX=b其中A为非奇异矩阵，当A为低阶稠密矩阵时，线性方程组用直接法(如高斯消去法和三角分解法)是有效的，但对于由工程技术中产生的大型稀疏矩阵方程组（A的阶数n很大，但零元素较多），利用迭代法求解是适合的。在计算机内存和运算两方面，迭代通常都可利用A中有大量零元素的特点。考虑线性方程组

本章将介绍迭代法的一般理论及雅可比迭代法、高斯—塞德尔迭代法、逐次超松弛迭代法，研究它们的收敛性。6.1

单步定常迭代法矩阵序列的极限单步定常迭代法单步定常迭代法将方程组迭代矩阵迭代法的一般理论迭代法的收敛速度6.2基于矩阵分裂的迭代法Jacobi迭代法等价变形高斯—塞德尔迭代法逐次超松驰(SOR)迭代法SOR迭代法的计算公式:对k=0,1,…,说明:

1)ω=1,即为GS（高斯-赛德尔迭代法）;2)ω>1，称为超松驰法；

ω<1，称为低松驰法；

3)SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法。例6-3

用SOR迭代法解线性代数方程组6.3迭代法的收敛性单步定常迭代法的基本定理

注：定理4中的矩阵是迭代矩阵，常用格式的迭代矩阵如下：1)雅可比迭代法:2)高斯-赛德尔迭代法:3)SOR迭代法:

例6-4

考察用雅可比迭代法求解线性方程组的收敛性。某些特殊方程组的迭代收敛性定义6.3（1）按行严格对角占优

（2）按行弱对角占优

上式至少有一个不等号严格成立。

定理8(对角占优定理)若矩阵A按行(或列)严格对角占优，或按行(或列)弱对角占优且不可约；则矩阵A非奇异。

定理6.8

若矩阵A按行(或列)严格对角占优,或按行(或列)弱对角占优不可约；则Jacobi迭代、Gauss-Seidel迭代都收敛。定理6.11

对于线性方程组，若(1)A为对称正定矩阵，(2)0<ω<2，

则解

的SOR迭代收敛。

定理12

对于线性代数方程组Ax=b，若A按行(或列)严格对角