数值分析 课件全套 陈丽娟 ch1-绪论-ch8-常微分方程数值解法

数值分析

学银在线教学平台（学习通）

教材

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

构造算法程序设计实际问题近似解输入复杂问题或运算数值计算方法

逻辑运算计算机数值分析算法影响计算的速度和效率

数值分析算法影响计算的精度

数值分析算法影响计算的精度

即使数学上的恒等公式，用计算机来算，结果也是不一样的。绪论01Chapter1.1数值分析研究对象与特点数值分析也称计算方法.它根椐实际问题的数学模型提出求解问题的数值计算方法.算法能在计算机上实现，并有好的计算复杂性；面向计算机，提供切实可行的有效算法；有可靠理论，对算法进行误差分析，并能达到精度要求；通过数值实验证明算法行之有效；研究对象学科特点1.2误差来源与误差分析实际问题数学模型建立算法上机计算结果(初值误差)观测误差模型误差(方法误差)截断误差舍入误差误差来源1.2误差来源与误差分析1.模型误差（描述误差）/*ModelingError*/简化，抽象问题后建立的数学模型与实际问题之差。2.观测误差/*MeasurementError*/观测和实验得到的参量（物理量为电压、电流、温度等）误差种类1.2误差来源与误差分析误差种类3.截断误差（方法误差）/*TruncationError*/有限过程代替无限过程的误差（无穷级数求和，只能取前面有限项求和来近似代替）。这种计算方法本身出现的误差，所以也称为方法误差。如右端是截断误差。

1.2误差来源与误差分析误差种类4.舍入误差/*RoundoffError*/计算机字长有限，一般实数不能精确存储，于是产生舍入误差。例如：在10位十进制数限制下：舍入误差很小，本课程将研究它在运算过程中是否能有效控制。

1.2误差来源与误差分析大家一起猜？11/e

S4R4取则称为截断误差|

舍入误差|由截去部分引起由留下部分引起=0.747……1.3误差的基本概念

绝对误差/*absoluteerror*/相对误差/*relativeerror*/

1.3误差的基本概念

有效数字/*significantdigits*/

1.3误差的基本概念用四舍五入法取准确值的前n位作为近似值，则x*必有n位有效数字；有效数字位数相同的两个近似数，绝对误差限不一定相同；有效位数与第一个非0项后的数字个数是不一致的。四舍五入所得到的数是一致的。准确值被认为具有无穷位有效数字.一定要从规格化后的数来判断其位数将任何数乘以10m(m为整数)，等于移动该数的小数点，并不影响它的有效数字的位数；有效数字的几点说明1.3误差的基本概念

数字末尾的0不可随意省去1.3误差的基本概念

1.3误差的基本概念有效数字与误差之间的关系

1.3误差的基本概念

1.3误差的基本概念

1.3数值运算的误差估计代数运算的误差估计加法和减法结果的误差乘法和除法结果的误差积的误差积的相对误差商的误差1.3数值运算的误差估计一元函数情形

1.3数值运算的误差估计多元函数情形

1.3数值运算的误差估计例1.3.4：测得某桌面的长a的近似值a*=120cm,宽b的近似值b*=60cm。若已知|e(a*)|≤0.2cm,|e(b*)|≤0.1cm。试求近似面积s*=a*b*的绝对误差限与相对误差限。

Ch1绪论

解1.4选用算法应遵循的原则BS

避免相近二数相减

几种经验性避免方法：

1.4选用算法应遵循的原则BS

避免小分母

分母小会造成舍入误差增大例：1.4选用算法应遵循的原则BS

避免大数吃小数

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

避免大数吃小数

注：求和时从小到大相加，可使和的误差减小。1.4选用算法应遵循的原则BS

简化计算步骤，避免误差累积

一般来说，计算机处理下列运算的速度为

1.4选用算法应遵循的原则选用稳定的算法

注意此公式精确成立

1.4选用算法应遵循的原则选用稳定的算法

????!!!发生了什麽?!

造成这种情况的是不稳定的算法迅速积累,误差呈递增走势.可见初始的小扰动1.4选用算法应遵循的原则选用稳定的算法

注意此公式与公式一在理论上等价。

可取1.4选用算法应遵循的原则选用稳定的算法

考察反推一步的误差：

误差逐步递减,这样的算法称为稳定的算法插值法02Chapter2.1引言2.1引言在实际问题中，我们会遇到两种情况变量间存在函数关系，但只能给出一离散点列上的值例如:从实验中得到一个数据表,或是一组观测数据变量间的函数关系可以表示,但计算复杂,只能计算特殊点的函数值例如:求指数函数、对数函数、三角函数、反三角函数值等为了研究自变量与因变量间的变化关系，我们需要建立变量间的函数关系，从而可以计算原始数据以外需要处的值，这就是我们研究插值的目的。2.1引言

插值条件插值函数插值节点求插值函数的方法称为插值法

…………[a,b]称为插值区间如何构造P(x)???2.1引言根据实际需要，可以用各种不同的函数来近似原来的函数。最常用的插值函数是

代数多项式最简单，计算其值只需用到加、减乘运算，且积分和微分都很方便；所以常用它来近似表示表格函数(或复杂函数),这样的插值方法叫做多项式插值法，简称插值法。2.1引言

是否任意给定n+1个不同的插值节点都可以构造出满足插值条件的插值多项式??

2.2拉格朗日插值

2.2拉格朗日插值线性插值

n=1

直线方程常用表达式两点式

点斜式

2.2拉格朗日插值二次插值n=2

方程组的解是否存在?若存在解,是否唯一?!2.2拉格朗日插值

然而,方程组的求解也并不是一件容易的事对于线性插值的两种形式解进行适当的分析,从中寻求规律而得到启发,就有了所谓的拉格朗日插值法(公式)和牛顿插值(公式).2.2拉格朗日插值两点式

线性插值的两点式可看作是两个特殊的线性函数的一种线性组合.

1001

于是，线性插值即是用基函数的线性组合来构造的.

2.2拉格朗日插值由此启发，我们希望二次插值也能由一些二次插值基函数来线性组合:

100010001

2.2拉格朗日插值同理可得

2.2拉格朗日插值n次插值

li(x)

2.2拉格朗日插值n次插值

拉格朗日多项式与有关，而与无关节点f2.2拉格朗日插值

证明：(存在性可利用Vandermonde

行列式论证)

矛盾2.2拉格朗日插值插值余项

2.2拉格朗日插值

2.2拉格朗日插值

解：三个插值节点及对应的函数值为

由抛物插值公式得

2.2拉格朗日插值例2：已知

sin50=0.7660444…解：

外推

(extrapolation)

的实际误差

0.01001内插

(interpolation)

的实际误差

0.00596

2.2拉格朗日插值

sin50=0.7660444…2次插值的实际误差

0.00061高次插值通常优于低次插值但绝对不是次数越高就越好2.2拉格朗日插值Lagrange插值公式缺点：一是计算量大，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，全部插值基函数均要随之变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要增加一项计算。为克服上述两个缺点,努力：把插值多项式变形为便于计算的形式。希望：计算改变的过程中,尽可能能利用已有的计算结果.下面我们将看到,这是可能的。我们可以有具有“承袭性”的所谓牛顿公式。优点：利用插值基函数很容易得到，含义直观,结构紧凑,在理论分析中非常方便;计算机上实现也很容易.2.3差商与牛顿插值2.3差商与牛顿插值差商定义

2.3差商与牛顿插值差商性质

12

这个性质也表明均差与节点的排列次序无关,称为均差的对称性,即

由性质1可得:

2.3差商与牛顿插值

3

所以2.3差商与牛顿插值

变形☆希望：计算改变的过程中,尽可能能利用已有的计算结果.

常数(差商)由此启发，我们希望二次插值也能类似地有有规律的组合表达式:

2.3差商与牛顿插值

事实上,从上述可看出二次牛顿插值公式是用待定系数法求得的;它也可看作是三个特殊函数的一种线性组合:

2.3差商与牛顿插值

来线性组合为：

那么其组合系数是什么样的呢？怎么求呢？

2.3差商与牛顿插值12…………n

1n

1

Rn(x)Nn(x)

2.3差商与牛顿插值

牛顿插值余项为

牛顿插值多项式它比拉格朗日插值多项式计算量省,且便于程序设计.2.3差商与牛顿插值差商表一阶均差二阶均差三阶均差四阶均差

2.3差商与牛顿插值

插值基函数xk0124f(xk)19233拉格朗日插值多项式为:

2.3差商与牛顿插值xkf(xk)

一阶均差二阶均差三阶均差0119822314343-10-8

建立如下差商表牛顿插值多项式为:

(3)唯一性验证.

2.3差商与牛顿插值

xk0123f(xk)13927解：差商表:牛顿插值多项式为:

2.3差商与牛顿插值当题目中没有指明用那一种方法建立插值多项式时,原则上拉格朗日插值方法和牛顿插值方法都可行,选较为简便的一种方法.近似计算时,由于牛顿插值多项式的非整理形式可以直接写成秦九韶算法的形式,计算量小,且当增加节点时只需增加一项,前面的工作依然有效,因而通常情况下牛顿插值比较方便.相对之下,拉格朗日插值法没有上述优点,但它在理论证明上因插值基函数的许多特点而得到广泛应用.在前面的讨论中，节点是任意分布的，但实际上经常遇到等距节点的情况，这时插值公式可以得到简化。2.4差分与等距节点插值公式2.4差分

简记为

简记为

简记为一阶向前差分一阶向后差分中心差分前差算子后差算子差分定义2.4差分如又如用低阶差分可以定义高阶差分高阶向前差分高阶向后差分一般地可定义m阶差分为2.4差分一般有前差与后差的关系再定义前移算子不变算子后移算子则有2.4差分差分的性质各阶差分均可用函数值表示性质1二项式展开2.4差分函数值可用各阶差分表示性质2

差商与差分的关系性质3

m阶向前差商与m阶向前差分的关系m阶向后差商与m阶向后差分的关系

2.4差分差分与导数的关系性质42.4差分等距节点插值公式

Newton插值公式

得

向前差分

参照2.4差分

Newton前插公式

2.5Hermite插值2.5Hermite插值

其余项为

2.5Hermite插值

采用构造插值基函数的方法2.5Hermite插值

且满足其中且满足令

Kronecker（克罗内克）符号柏林科学院院士，巴黎科学院通讯院士，伦敦皇家学会外籍会员。主张分析学应奠基于算术，而算术的基础是整数。克罗内克名言：“上帝创造了整数，其余都是人做的工作”2.5Hermite插值令则其中

又则由(1),(2)得2.5Hermite插值所以

其中则所以2.5Hermite插值令则又由得所以

2.5Hermite插值

解

所以

2.5Hermite插值

令

解：在点0，1，2上做Lagrange插值函数

则

所以2.5Hermite插值练习：给定数表-1012-1120

2.5Hermite插值

2.6分段低次插值2.6分段低次插值

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

Ln(x)

f(x)

如何避免高次插值的病态问题???一种办法是采取分段低次插值2.6分段低次插值分段线性插值

123

在小区间上的线性插值函数2.6分段低次插值分段线性插值示意图…………从几何上看，就是用折线逼近曲线易证：当时，一致2.6分段低次插值

分段线性函数的缺点：失去了原函数的光滑性。2.6分段低次插值分段Hermite插值

123

在小区间上的三次Hermite插值函数已知数表

缺点：导数不易得到2.6分段低次插值分段低次插值优点：收敛性，稳定性好，算法简单，易于在计算机上实现缺点：光滑性差，分段Hermite插值也仅有一阶光滑度问题许多实际问题中，有更高的光滑度要求，例如高速飞机的机翼线形等往往要求具有二阶光滑度，即函数曲线要求有二阶连续导数。2.7三次样条插值2.7三次样条插值样条(splime)是早期飞机、造船工业中绘图员用来画光滑曲线的细木条或细金属丝.绘图时,为了将一些已知的点连成光滑曲线,绘图员用压铁把样条固定在相邻的若干点上,样条具有弹性,形成通过这些点的光滑曲线,沿着它就可画出所需的曲线.数学上仿此得出的函数便称为样条函数.样条插值是用分段低次多项式去逼近被逼近函数,并且能满足对光滑性的要求,又无需给出每个节点处的导数值.

它除了要求给出各个节点处的函数值之外,只需提供两个边界节点处的导数信息.2.7三次样条插值

定义

2.7三次样条插值

f(x)H(x)S(x)如何求三次样条插值函数???2.7三次样条插值

2.7三次样条插值

特别

称固支边界条件称自然边界条件

三转角方程三弯矩方程称周期性条件

2.7三次样条插值三转角方程

步骤2.7三次样条插值

应用第一种边界(固支边界条件)得到的三转角方程矩阵形式第一类边界条件2.7三次样条插值

2.7三次样条插值三弯矩方程

积分两次得

2.7三次样条插值

应用第一种边界(固支边界条件)得到的三弯矩方程矩阵形式

2.7三次样条插值

函数逼近与计算03Chapter3.1引言3.1引言本章继续讨论用简单函数近似代替较复杂函数的问题.上章提到的插值就是近似代替的方法之一,插值的近似标准是在插值点处误差为零.但在实际应用中,有时不要求具体某些点误差为零,而要求考虑整体的误差限制,这就引出了拟合和逼近的概念.对离散型函数(即数表形式的函数)考虑数据较多的情况.若将每个点都当作插值节点,则插值函数是一个次数很高的多项式,比较复杂.而且由于龙格振荡现象,这个高次的插值多项式可能并不接近原函数.同时由于数表中的点一般是由观察测量所得,往往带有随机误差,要求近似函数过所有的点既不现实也不必要.3.1引言3.1引言目标函数集合简单函数集合

3.1引言何为”逼近”?如何逼近？无穷范数：

平方范数：

一致逼近平方逼近3.1引言存在性▲1834年入波恩大学学习法律和财政。▲

1842～1856年，中学教师。▲

1856年柏林科学院，1864年升为教授。▲

1854年解决了椭圆积分的逆转问题，引起数学界的重视。▲

1856年解决了椭圆积分的雅可比逆转问题，建立了椭圆函数新结构的定理，一致收敛的解析函数项级数的和函数的解析性的定理，圆环上解析函数的级数展开定理等。3.1引言存在性

3.1引言存在性

3.1引言存在性

3.2最佳一致逼近多项式3.2最佳一致逼近多项式

即

使得

3.2最佳一致逼近多项式1、Chebyshev给出如下概念

3.2最佳一致逼近多项式2、Chebyshev得到如下结论

3.2最佳一致逼近多项式以最佳一次逼近多项式为例

3.2最佳一致逼近多项式以最佳一次逼近多项式为例

得

3.2最佳一致逼近多项式求解最佳一次一致逼近多项式步骤

3.2最佳一致逼近多项式

由

得

即

解因此

所求一次最佳逼近多项式为3.2最佳一致逼近多项式Matlab程序x=0:0.1:1;y1=sqrt(1+x.*x);y2=0.414*x+0.955;plot(x,y1);holdonplot(x,y2);3.2最佳一致逼近多项式

由

得

解因此

所求一次最佳逼近多项式为

3.3最佳平方逼近3.3最佳平方逼近定义内积

记内积则称内积的定义

关于内积、范数的详尽内容可参见《高等代数》或《线性代数》等相关书籍。3.3最佳平方逼近

即一般的最佳平方逼近问题

3.3最佳平方逼近

多元函数求极值令

则

即3.3最佳平方逼近

得

即

3.3最佳平方逼近如果取

则希尔伯特矩阵3.3最佳平方逼近顾最佳平方逼近函数计算步骤

(1)确定

3.3最佳平方逼近

解：则

由法方程

解得

3.3最佳平方逼近3.3最佳平方逼近如果令

即

则解得

从而3.3最佳平方逼近3.3最佳平方逼近

解得

所以

解得

所以

3.3最佳平方逼近

正交多项式函数系

3.3最佳平方逼近

解

3.4正交多项式3.4正交多项式

正交函数族

若内积

例如，三角函数族1,cosx,sinx,cos2x,sin2x,…就是在区间[-π,π]上的正交函数族。3.4正交多项式正交多项式定义

3.4正交多项式勒让德多项式

勒让德多项式有下述几个重要性质：

性质1.正交性

3.4正交多项式勒让德多项式性质3.递推关系

3.5曲线拟合的最小二乘法3.5曲线拟合的最小二乘法引例：考察某种纤维的强度y与其拉伸倍数x的关系，下表是实际测定的24个纤维样品的强度与相应的拉伸倍数的记录:

3.5曲线拟合的最小二乘法纤维强度随拉伸倍数增加而增加并且24个点大致分布在一条直线附近

必须找到一种度量标准来衡量什么曲线最接近所有数据点.3.5曲线拟合的最小二乘法常见做法：

太复杂

不可导，求解困难

最小二乘法

3.5曲线拟合的最小二乘法

一般的曲线拟合问题

注：更一般地，考虑加权平方和

3.5曲线拟合的最小二乘法

多元函数求极值令

则

即

3.5曲线拟合的最小二乘法

得

即

离散点标号基函数标号3.5曲线拟合的最小二乘法

3.5曲线拟合的最小二乘法

ixiyilnyixi2xjlnyi01.005.101.6291.00001.62911.255.791.7561.56252.19521.506.531.8762.25002.81431.747.452.0083.06253.51442.008.462.1354.00004.270

3.5曲线拟合的最小二乘法

3.5曲线拟合的最小二乘法S*1(x)=1.6238+3.365953xS*2(x)=3.5171+0.693376x+0.89113x2S*(x)=3.071exp(0.5056x)在各种模型下拟合曲线的比较3.5曲线拟合的最小二乘法123444.568

解

非线性方程的近似解法04ChapterCh4方程求根从多项式方程求根说起

20世纪考古发现，公元前1700年，美索不达米亚人已经有了解二次方程的成法；用现代的代数语言来叙述就是：Ch4方程求根意大利数学家费罗(S.d.Ferro，1465～1526)首先得到了该方程的一般求根公式，没有公开他的解法，按当时的习俗作为挑战对手的秘密武器；

Ferro在临终前将解法传给了他的学生安东尼奥·菲奥尔(AntonioM.Fior);费罗去世后，菲奥尔向当时意大利最大的数学家之一塔尔塔利亚(Tartaglia，1500—1557)提出挑战，要他解出30个三次方程,塔尔塔利亚用8天时间解出了全部30个方程，得到了解缺项三次方程的一般方法。Ch4方程求根从二次方程到三、四次方程求根公式历经至少3245年；米兰的数学和物理教授卡尔达诺(Cardano，1501—1576)获悉该事后央求塔尔塔利亚将密诀告诉他，并发誓保密，在卡尔达诺的恳求下，塔尔塔利亚把他的方法写成一首晦涩的诗告诉了卡尔达诺；

1545年卡尔达诺出版著作《大法》(Arsmagna)，公布了一般三次方程求根公式，称为卡尔达诺公式；《大法》同时公布了意大利数学家费拉里（Ferrali，1522-1565）仿照一般三次方程求根思想，推导的一般四次方程求根公式；Ch4方程求根意大利数学家的成功促使当时的众多数学家开始寻求更高次方程的解法；量变引起了质变，数学家们徒劳了两个多世纪，没有成功；

1771年法国数学家拉格朗日在论文《关于代数方程解法的思考》中指出，用代数运算解一般的(n>4)次方程是不可能的,或者这个问题超出了人类的智力范围，或者是根的表达方式不同于当时所知道的一切;

1824年，天才的挪威数学家阿贝尔(Abel，1802—1829)在其出版的著作中证明：如果方程的次数n≥5，并且将方程的系数看成字母，那么任何一个由这些字母组成的根式都不可能是方程的根；近300年的努力果然是徒劳的；Ch4方程求根阿贝尔之后，不少人找到了特殊高次方程的求根方法，得到了有理根式形式的解；到底哪些方程可以得到有理根式形式的解？

1831年天才的法国数学家伽罗瓦(E.Galois，1811—1832)给出了高次方程存在根式解的充分必要条件。Ch4方程求根天才的伽罗华

1829年，伽罗华中学毕业前，把关于群论的初步研究结果的论文提交给法国科学院，科学院委托当时法国最杰出的数学家柯西审核论文。在1830年1月18日柯西计划对伽罗华的研究成果在科学院举行一次全面的意见听取会。他在一封信中写道：“今天我应当向科学院提交一份关于年轻的伽罗华的工作报告……但因病在家，我很遗憾未能出席今天的会议，希望安排我参加下次会议，讨论已指明的议题。”Ch4方程求根

1830年2月，伽罗华将论文寄给当时的科学院终身秘书傅立叶，傅立叶于当年5月去世，在他的遗物中未发现伽罗华的手稿。伽罗华递交的两次数学论文均被遗失。

1831年1月，伽罗华将包含新成果的论文提交给法国科学院，负责审查的数学家泊松（Possion),四个月后，以“完全不能理解”，建议科学院退稿。

1831年1月8日，因伽罗华揭发校长的政治两面派行为，被皇家国民教育委员会批准开除出巴黎师范大学；第二周，柯西向科学院宣读他自己的一篇论文时，忘记了原来的议题。Ch4方程求根

1832年5月29日夜，伽罗华仓促地把自己生平的数学研究心得扼要写出，附以论文手稿，并在给朋友舍瓦利叶的信中说：“我在分析方面做出了一些新发现。有些是关于方程论的；有些是关于整函数的……。公开请求雅可比或高斯，不是对这些定理的正确性，而是对这些定理的重要性发表意见。我希望将来有人发现，这些对于消除所有有关的混乱是有益的。”

l832年3月16日伽罗华获释后不久，为了一个舞女决定为“爱情与荣誉”决斗；

1832年5月30日上午，伽罗华死于决斗；

1831年5月l0日，伽罗华以“企图暗杀国王”的罪名被捕，关押在圣佩拉吉监狱；Ch4方程求根伽罗华死后，舍瓦利叶把他的信发表在《百科评论》中。

1846年，法国数学家刘维尔领悟到伽罗华的天才思想，他花了几个月的时间将伽罗华手稿中的部分内容发表在他的极有影响的《纯粹与应用数学杂志》上，并向数学界推荐。

1870年法国数学家约当根据伽罗华的思想，写了《论置换与代数方程》一书，向人类展示了跨越世纪的伽罗华思想：关于群和域的理论。这套理论创立了抽象代数学，把代数学的研究推向了一个新的里程，并标志着数学发展现代阶段的开始。Ch4方程求根

困难：方程的解难以用公式表达。例如:1)多项式方程：

需要一定精度的近似解！2)超越方程:

4.1根的搜索4.1根的搜索

逐步搜索法

求根问题的三个方面：存在性，分布，精确化4.1根的搜索

二分法

4.1根的搜索解：

f(1)=-5<0有根区间f(2)=14>0-(1,2)+f(1.5)>0-(1,1.5)+f(1.25)<0-(1.25,1.5)+f(1.375)>0(1.25,1.375)f(1.313)<0(1.313,1.375)f(1.344)<0(1.344,1.375)f(1.360)<0(1.360,1.375)f(1.368)>0(1.360,1.368)

4.1根的搜索

因此，一般常用该方法求根的初始近似值，然后再用其它的求根方法精确化。4.2迭代法4.2迭代法迭代法基本思想

不动点迭代法

迭代法是一种逐次逼近方法4.2迭代法

迭代函数有多种选择4.2迭代法

4.2迭代法

由此可见，这种迭代格式是发散的

4.2迭代法

同样的方程不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?4.2迭代法

迭代法的几何意义4.2迭代法

4.2迭代法

4.2迭代法迭代法的收敛性

4.2迭代法4.2迭代法4.2迭代法4.2迭代法迭代法的收敛性

4.2迭代法

kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123

׃

x0

x1

x2

x3

׃23987׃21.521.5׃21.751.734751.732631׃21.751.7321431.732051׃

4.2迭代法迭代法的收敛阶

4.2迭代法迭代法的收敛阶下面给出超线性收敛的一个充分条件

4.3牛顿迭代法4.3牛顿迭代法基本思想：将非线性方程转化为线性方程来求解。牛顿迭代法思想

Newton迭代法4.3牛顿迭代法yx0abx0x1x2x*y=f(x)Newton迭代法逼近过程Newton法的几何意义是逐次用切线代替曲线，求切线与横坐标轴的交点。

Newton法亦称为切线法4.3牛顿迭代法

01230.50.571020.567160.56714

4.3牛顿迭代法

0123411.51.347831.325201.324724.3牛顿迭代法牛顿迭代法的局部收敛性

4.3牛顿迭代法

(2)写出一个一般迭代公式，分析迭代公式的收敛性.

4.3牛顿迭代法牛顿迭代法的优缺点yx0abx0x1x2x*y=f(x)优点:牛顿迭代法具有平方收敛的速度,所以在迭代过程中只要迭代几次就会得到很精确的解.这是牛顿迭代法比简单迭代法优越的地方.缺点:选定的初值要接近方程的解,否则有可能得不到收敛的结果;再者,牛顿迭代法计算量比较大,因每次迭代除计算函数值外还要计算微商值.4.3牛顿迭代法牛顿下山法

4.3牛顿迭代法

012341.51.347831.325201.324720.617.9发散0.6-1.3841.1406250.6566431.361810.18661.326280.006671.324720.00000864.4弦截法与抛物线法4.4弦截法与抛物线法弦截法

4.4弦截法与抛物线法弦截法

4.4弦截法与抛物线法抛物线法

线性方程组的直接解法05ChapterCh5线性方程组的直接解法研究数值解法的必要性

求解线性方程组根据克莱姆(Gramer)法则方程组的解可表示为两个行列式之比

Ch5线性方程组的直接解法

计算量太大寻找数值解法有必要5.1Gauss消元法5.1高斯消元法

5.1高斯消元法

消元5.1高斯消元法

回代5.1高斯消元法思路1.消元过程：将一般线性方程组化为上三角矩阵方程组2.回代过程：回代求解

0高斯消元法基本思想5.1高斯消元法消元过程

5.1高斯消元法

5.1高斯消元法

将(1)式化为(2)式的过程称为消元过程.5.1高斯消元法

回代过程5.1高斯消元法

5.1高斯消元法例5.1.1

解方程组

解：用Gauss消去法计算：

若将1，2两行互换

5.1高斯消元法

顺序消去法的缺点消元过程中选择适当的主元素是十分必要的Gauss主元素消去法5.2高斯主元素消元法5.2高斯主元素消元法全主元消去法思路

消元5.2高斯主元素消元法

5.2高斯主元素消元法列主元消去法思路

消元5.2高斯主元素消元法

5.2高斯主元素消元法

解：

5.2高斯主元素消元法一些特殊情况,主元就在对角线上,不需选主元.元素满足如下条件的矩阵

即对角线上每一元素的绝对值均大于同行其他各元素绝对值之和,这样的矩阵称为按行严格对角占优矩阵,简称严格对角占优矩阵.例：

性质：严格对角占优矩阵必定非奇异.

5.3高斯消元法的变形5.3高斯消元法的变形LU分解

5.3高斯消元法的变形LU分解

5.3高斯消元法的变形LU分解可见,消元过程相当于下述矩阵乘法运算：

由分块乘法可得：

直接计算可得

5.3高斯消元法的变形LU分解

，则

5.3高斯消元法的变形

记为单位下三角阵/*unitarylower-triangularmatrix*/记

U=

5.3高斯消元法的变形LU分解

5.3高斯消元法的变形直接LU分解

根据矩阵乘法法则,先比较等式两边第1行和第1列元素有：

5.3高斯消元法的变形

5.3高斯消元法的变形

5.3高斯消元法的变形

5.3高斯消元法的变形

5.3高斯消元法的变形例5.3.1

解：

由得

得由

得由

由

得得由

得

再由

得5.3高斯消元法的变形

5.3高斯消元法的变形

5.3高斯消元法的变形追赶法

5.3高斯消元法的变形

其中：5.3高斯消元法的变形

上述方法为求解三对角方程组的追赶法，也称Thomas算法.

5.3高斯消元法的变形例5.3.3

5.3高斯消元法的变形由得

由得

5.3高斯消元法的变形平方根法

记为

5.3高斯消元法的变形

5.4向量和矩阵的范数5.4向量和矩阵的范数

向量范数的性质

5.4向量和矩阵的范数常用范数

(p-范数)

(无穷范数)

(1-范数)

(2-范数)5.4向量和矩阵的范数

5.4向量和矩阵的范数5.4向量和矩阵的范数矩阵范数

5.4向量和矩阵的范数5.4向量和矩阵的范数常用矩阵范数

它们满足如下相容关系：

5.4向量和矩阵的范数5.4向量和矩阵的范数

5.5误差分析5.5误差分析例，考查以下三个方程组及其准确解其准确解其准确解其准确解可以看到，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有0.0005以下的误差，但准确解却相差很大。对这样的方程组，无论用多么稳定的算法求解，一旦计算中产生误差就使解面目全非，所以该方程组的性态很差。5.5误差分析

5.5误差分析

绝对误差放大因子

相对误差放大因子5.5误差分析

(只要A充分小，使得

是关键的误差放大因子，称为A的条件数，记为cond(A),越则A越病态，难得准确解。大5.5误差分析

5.5误差分析

5.5误差分析

行列式的值很大或很小（如某些行、列近似相关）；

元素间的数量级相差大，且无规则；

主元消去过程中出现小主元；

特征值相差大数量级。线性方程组的迭代解法06ChapterCh6线性方程组的迭代解法

迭代法方法简单，便于实现需要选取合适的迭代公式及初值Jacobi迭代Gauss-Seidel迭代超松弛迭代Ch6线性方程组的迭代解法基本思想:用某种极限过程逐步逼近方程组的精确解。迭代法基本思想迭代法的基本步骤

则迭代过程收敛.迭代矩阵形式迭代公式的收敛性和收敛速率误差估计6.1Jacobi迭代法6.1Jacobi迭代法引例

解方程组

解1）等价形式

6.1Jacobi迭代法2）迭代公式

Jacobi迭代公式

6.1Jacobi迭代法迭计算结果如表012301.41.110.92900.51.201.05501.41.110.92945670.99061.011591.0002510.998240.96450.99531.0057951.0001260.99061.011591.0002510.99824

终止条件

6.1Jacobi迭代法n阶方程组的Jacobi迭代法

等价方程组

终止条件

6.1Jacobi迭代法Jacobi迭代法的矩阵描述

其中，6.1Jacobi迭代法Jacobi迭代法的矩阵描述

雅可比迭代公式的矩阵形式

6.1Jacobi迭代法

雅可比迭代格式Jacobi迭代矩阵

Jacobi迭代矩阵对角线为06.2Gauss-Seidel迭代法6.2Gauss-Seidel迭代法引例

解方程组

解1）等价形式

6.2Gauss-Seidel迭代法2）迭代公式

Gauss-Seidel迭代公式

6.2Gauss-Seidel迭代法迭计算结果如表01201.41.0634

00.781.0204801.0260.98751

34

0.9951041.00123

0.9952751.00082

1.00190.99963

终止条件【注】高斯-赛德尔迭代法比雅可比迭代法收敛快。

6.2Gauss-Seidel迭代法n阶方程组的Gauss-Seidel迭代法

等价方程组

终止条件6.2Gauss-Seidel迭代法Gauss-Seidel迭代法的矩阵描述

G-S迭代公式的矩阵形式

6.2Gauss-Seidel迭代法

Jacobi发散，G-S发散.

Jacobi发散，而G-S10次达到精度0.001雅可比迭代法和高斯-赛德尔迭代法可能同时发散；也可能同时收敛，但一个快另一个慢；可能一个收敛而另一个发散。

6.2Gauss-Seidel迭代法

G-S迭代格式G-S迭代矩阵

G-S迭代矩阵第一列为06.3迭代法的收敛性6.3迭代法的收敛性

等价形式为

迭代公式

迭代法收敛，否则发散

6.3迭代法的收敛性定义和定理

6.3迭代法的收敛性定义和定理

6.3迭代法的收敛性例6.3.1证明:Jacobi收敛，G-S发散。

证明1)

∴Jacobi收敛。2)

G-S发散6.3迭代法的收敛性特殊方程组的迭代法收敛性定义2（对角占优矩阵）行占优：弱对角占优矩阵：

且至少有一个不等式是严格成立。

定义3可约矩阵：

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

例

严格对角占优,∴Jacobi和G-S收敛.6.4超松弛迭代法6.4超松弛迭代法基本思想SOR迭代法:G-S迭代法基础上,用参数校正残差加速.

6.4超松弛迭代法

6.4超松弛迭代法超松弛迭代法的矩阵描述

超松弛迭代公式的矩阵形式

6.4超松弛迭代法

用G-S迭代得

用SOR方法

6.4超松弛迭代法迭代计算结果

12345111.3431.195451.20347211.491.47531.402361.40287351.71.6161.650951.60198151.59390590.790.81520.8295850.7895530.7999129SOR迭代5次，与G-S法迭代10次的结果大体相同，SOR方法的松驰因子起到了加速收敛的重要作用.数值积分与微分07Chapter7.1引言7.1引言

——Riemann积分积分的概念

即7.1引言黎曼是世界数学史上最具独创精神的数学家之一,著作不多，却异常深刻，富于对概念的创造与想象，思想极其深邃难以理解。许多奠基性、创造性的工作，直接影响了19世纪以后的数学发展，在黎曼思想的影响下数学许多分支取得了辉煌成就。■黎曼几何、流形、微分流形、椭圆几何的创始人爱因斯坦用黎曼几何将广义相对论几何化。黎曼几何是现代理论物理必备的数学基础。■完善微积分理论的出杰人物之一

■解析数论、与复变函数的里程碑■组合拓扑的开拓者■代数几何的奠基人

■在数学物理、微分方程等领域贡献卓著7.1引言根据定义计算

积分的计算Riemann积分从定义上基本不可算

Newton-Leibniz公式求定积分的值,Newton-Leibnitz公式无论在理论上还是在解决实际问题上都起了很大作用，但它并不能完全解决定积分的计算问题7.1引言N-L公式的局限性积分学涉及的实际问题极为广泛，而且极其复杂，在实际计算中经常遇到以下三种情况：1.被积函数有原函数，但形式复杂难解

2.找不到原函数

7.1引言希望研究一种新的积分方法来解决N-L公式所不能或很难解决的积分问题数值积分方法

7.1引言

左矩形公式

右矩形公式中矩形公式梯形公式

Simpson公式

7.1引言

求积系数求积节点值机械求积公式求积节点

为截断误差,又称求积余项.7.1引言数值积分方法是近似方法近似程度(精度)代数精度考虑如何衡量代数精度

如果

但

7.1引言

考查

如果

则

一般，如果

则7.1引言

即

因此，判断代数精度只需用最简多项式

7.1引言代数精度

7.1引言

所以梯形公式具有1次代数精度

7.1引言

所以Simpson公式具有3次代数精度

7.1引言

具有三阶的代数精度7.1引言

为插值型求积公式插值型求积公式

4.1引言

证:充分性

必要性所以该求积公式为插值型。

7.2Newton-Cotes公式7.2Newton-cotes公式Cotes系数

7.2Newton-cotes公式

Cotes系数

Newton-Cotes公式7.2Newton-cotes公式Cotes系数

Simpson求积公式

梯形公式

Cotes求积公式4.2Newton-cotes公式

7.2Newton-cotes公式

数值积分的误差分析

7.2Newton-cotes公式以梯形公式误差为例

7.2Newton-cotes公式

梯形公式Simpson公式

Cotes公式

7.2Newton-cotes公式

如何改进复化求积法复化求积法第一步：等分区间：

第三步：求和

7.2Newton-cotes公式

7.2Newton-cotes公式复化求积公式的误差复化梯形公式为

则

7.2Newton-cotes公式同理，复化Simpson和复化Cotes公式的误差分别为

复化梯形、复化Simpson和复化Cotes公式分别具有二阶、四阶和六阶收敛精度。7.2Newton-cotes公式

7.3Romberg算法7.3Romberg算法考察复化梯形公式

二分前的步长

7.3Romberg算法

可以得到两个结果结果一:

区间二分后的误差是二分前后差值的三分之一结果二：

加速公式7.3Romberg算法

令

即

则

7.3Romberg算法考察复化Simpson公式

可以验证得

7.3Romberg算法考察复化Cotes公式

记

称Romberg公式7.3Romberg算法Romberg算法计算步骤

1.梯形公式2.变步长梯形公式3.加速公式

（1）二分前的步长（2）二分前的区间中值

二分点7.3Romberg算法解：

因此

例7.3.1：计算

对照值

7.3Romberg算法

7.3Romberg算法例7.3.2：用Romberg算法计算

0***1**2*3

7.4Gauss公式7.4Gauss公式

定义：如果适当选取求积公式

Gauss点

7.4Gauss公式Gauss点

定义

Gauss定理：对于插值型求积公式

即

7.4Gauss公式Gauss-Legendre公式回顾：Legendre多项式

n=3时

n=2时n=1时

见P587.4Gauss公式Legendre多项式的两个重要结论

（1）

（2）

且

则Gauss-Legendre公式7.4Gauss公式Gauss-Legendre公式

例如取

利用两个Gauss点构造求积公式：代入求积公式

又因为有3次代数精度（n=1)所以

即7.4Gauss公式两点Gauss-Legendre求积公式因此

类似可得三点Gauss-Legendre求积公式

7.4Gauss公式解：（1）

7.4Gauss公式

7.4Gauss公式得Gauss点

根据代数精度得

即

7.4Gauss公式7.4Gauss公式梯形和Simpson求积公式低精度的方法,但对于光滑性较差的被积函教有时效果比用高精度的方法还好,再加上公式简单,因而使用非常广泛.特别在计算上,复化的梯形公式和Simpson公式便于采用逐次分半的方法,计算程序十分简单Romberg求积方法算法简单,程序也便于实现,且当节点加密时,前面的计算结果直接参与后面的计算,因而大大减少了计算量.此方法的一个最大缺点是节点的增加是成倍的。Gauss型求枳公式最高代数精度的求积方法,但它的节点和求积系数都没有规律,当节点增加时,前面的计算结果不能被利用,只能重新计算。它的最大优点是适用于某些无穷区间上的广义积分的计算。7.5数值微分7.5数值微分

关于微分的计算通过微分法则基本可以得到任意可微初等函数的导函数,但对于列表函数，求导数通常使用数值微分。

微分的数值运算大多应用于微分方程的离散化。

即将微分方程转化为离散点上的代数方程.7.5数值微分插值函数数值微分法

思想方法：以插值多项式近似代替函数，以插值多项式在节点上的导数值近似代替函数在节点上的导数值。推导公式：用此方法求微商，可以先求出插值多项式，然后各点上的微商就可以同时求出。

7.5数值微分

常用的数值微分公式

一阶微商的两点公式一阶微商的三点公式

7.5数值微分一阶微商的五点公式三点公式与五点公式中有中点项。由于中点的导数值的表达式中不含有中点的函数值项，且函数值项的系数不大，因此选取节点的方法：在考察的节点两侧选取。中点微分公式精度较高。实际应用中,多利用中点微分公式。用五点公式求数值导数,其精确度高于三点公式(同阶导数)。7.5数值微分数值微分在常微分方程离散化的应用例

记

7.5数值微分整理得

即有其中事实上，本方程的解析解为

7.5数值微分解析解近似解h=(b-a)/10近似解h=(b-a)/20误差h=(b-a)/10误差h=(b-a)/20u11.45521.49741.47690.04220.0217u21.90331.98251.94410.07920.0408u32.33842.44762.39460.10920.0562u42.75552.88612.82270.13060.0672u53.15103.29293.22400.14190.0730u63.52293.66473.59590.14180.0730u73.87154.00023.93770.12870.0662u84.19884.30034.25100.10150.0522u94.50944.56844.53980.05900.03047.5数值微分N=20时N=10时常微分方程数值解法08Chapter8.1引言8.1引言在工程和科学计算中，所建立的各种常微分方程的初值或边值问题，除很少几类的特殊方程能给出解析解，绝大多数的方程是很难甚至不可能给出解析解的，其主要原因在于积分工具的局限性。

因此，人们转向用数值方法去解常微分方程，并获得相当大的成功，讨论和研究常微分方程的数值解法是有重要意义的。8.1引言常微分方程与解为n阶常微分方程。

8.1引言

方程的通解满足定解条件的解微分关系（方程）解的图示8.1引言一阶常微分方程的初值问题

实际中常常需要求解常微分方程的定解，这类问题最简单的形式是一阶方程的初值问题：定解条件（初始条件）8.1引言

仅有极少数的方程可以通过“常数变易法”、“可分离变量法”等特殊方法求得初等函数形式的解，绝大部分方程至今无法理论求解。如

等等实际问题中归结出来的微分方程主要靠数值解法.8.1引言数值解的思想

两种：单步法、多步法8.1引言*数学界关注工程师关注如果找不到解函数数学界还关注：解的存在性解的唯一性解的光滑性解的振动性解的周期性解的稳定性解的混沌性……8.2初值问题数值解法的构造8.2初值问题数值解法的构造Taylor展开可借助Taylor展开（导数法）、差商法、积分法实现离散化来构造求积公式

Euler格式截断误差8.2初值问题数值解法的构造

18世纪最杰出的数学家之一，13岁时入读巴塞尔大学，15岁大学毕业，16岁获得硕士学位。

1727年-1741年（20岁-34岁）在彼得堡科学院从事研究工作，在分析学、数论、力学方面均有出色成就，并应俄国政府要求，解决了不少地图学、造船业等实际问题。

24岁晋升物理学教授。

1735年（28岁）右眼失明。

1741年-1766（34岁-59岁）任德国科学院物理数学所所长，任职25年。在行星运动、刚体运动、热力学、弹道学、人口学、微分方程、曲面微分几何等研究领域均有开创性的工作。

1766年应沙皇礼聘重回彼得堡，在1771年（64岁）左眼失明。

Euler是数学史上最多产的数学家，平均以每年800页的速度写出创造性论文。他去世后，人们用35年整理出他的研究成果74卷。

8.2初值问题数值解法的构造差商法

用向前差分近似导数

Euler公式

用向后差分近似导数

向后Euler公式

8.2初值问题数值解法的构造积分法对方程两边取积分取不同的数值积分可得不同的求解公式

用左矩形公式Euler公式

用右矩形公式

向后Euler公式用梯形公式

梯形公式8.2初值问题数值解法的构造