数值分析课件

数值分析数值分析

能够做什么？

§1

Introduction应用问题举例今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-------《九章算术》1、一个两千年前的例子线性方程组的求解！2、天体力学中的Kepler方程x是行星运动的轨道，它是时间t的函数.非线性方程求根！全球定位系统：在地球的任何一个位置，至少可以同时收到4颗以上卫星发射的信号

3、全球定位系统（GlobalPositioningSystem,GPS)

表示地球上一个接收点R的当前位置，卫星Si的位置为，则得到下列非线性方程组记为其中，非线性方程组的求解！4、已经测得在某处海洋不同深度处的水温如下：深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温.插值法！5、人口预测

下面给出的是中国1900年到2000年的人口数，我们的目标是预测未来的人口数（数据量较大时）19505519619606620719708299219809870519901143332000126743数据拟合！6、铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的.假若要求波纹瓦长4英尺,每个波纹的高度(从中心线)为1英寸,且每个波纹以近似2π英寸为一个周期.求制做一块波纹瓦所需铝板的长度L.

这个问题就是要求由函数f(x)=sinx给定的曲线从x=0到x=48英寸间的弧长L.

由微积分学我们知道,所求的弧长可表示为:上述积分称为第二类椭圆积分,它不能用普通方法来计算.数值积分！计算机辅助设计：波音777应用三维立体建模，数字化设计与有限元计算的第一架喷气客机。天气预报：计算能力的发展将把海洋、大气和生态系统的综合知识融合成一个气象变化模型。医学与生物工程：CT、核磁共振与Radon变换；至病基因与药物设计；人造生物材料的彷真响应；传染病动力学模型。现代科学计算在工程计算中的应用电子系统自动化设计：大规模集成电路的设计与逻辑检测。材料设计：性能设计的大规模计算与模拟：设计用于生产新的高热值、高压材料中的化学蒸发沉淀反应器。车辆与道路工程设计与模拟：车辆与道路相互作用综合系统设计。存储与物流系统：工农业发展使得产品的存储、交流和时效性极大提高；废物和垃圾问题成为城市生活的重大问题。规划计算和系统分析成为常用计算方法。燃烧与爆炸工程：燃烧对环境的影响；计算流体力学与爆炸工程。网络设计与计算：搜索引擎的设计航空航天工程：神州飞船系列信息与通信工程：GPS卫星导航数值计算方法的意义、内容与方法软件的核心就是算法。20世纪最伟大的科学技术发明---计算机

计算机是对人脑的模拟，它强化了人的思维智能；计算机的发展和应用，已不仅仅是一种科学技术现象，而且成了一种政治、军事、经济和社会现象；没有软件的支持，超级计算机只是一堆废铁而已；算法犹如乐谱，软件犹如CD盘片，而硬件如同CD唱机。理论研究科学实验科学计算计算数学诺贝尔奖得主,计算物理学家Wilson提出现代科学研究的三大支柱

科学方法论的巨大变革：如果说伽利略和牛顿在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由冯.诺依曼研制的现代电子计算机把计算推上了人类科学活动的前沿，使计算成为第三种方法。21世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”21世纪信息社会对科技人才的要求：--会用数学解决实际问题--会用计算机进行科学计算建立数学模型选取计算方法编写上机程序计算得出结果科学计算解题过程数值计算方法是计算数学的一个主要组成部分，“什么是数值计算方法？”它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）;对求得的解的精度进行评估以及在计算机上实现求解等。

数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被称为“第三种科学研究方法”。

科学计算可视化是目前研究的热门问题，下面的艺术图形是基于科学计算的数据表示的例子分形图混沌图1、数值逼近

插值与拟合、FFT、数值积分与微分2、数值代数

代数基础、线性代数方程组的解法、非线性代数方程（组）的解法、特征值与特征向量3、微分方程数值解

ODE、PDE和有限元法4、最优化方法*无约束优化与约束优化方法融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。传统的数值计算的主要研究内容

现代计算方法：数值计算方法的主要特点借助计算机提供切实可行的数学算法.想的精确度;收敛且稳定;误差可以分析或估计.所提出的算法必须具有：可靠的理论分析;理时间复杂性好__指节省时间；空间复杂性好__指节省存储量。计算复杂性好

通过数值实验证明算法行之有效.采用“近似替代”方法→逼近采用“构造性”方法采用“离散化”方法

把求连续变量的问题转化为求离散变量的问题采用“递推化”方法

复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。采用各种搜索方法构造数值算法的主要手段

希望：求近似解，但方法简单可行，行之有效（计算量小，误差小,需存储单元少等）,

以计算机为工具，易在计算机上实现。计算机运算:

只能进行加，减，乘，除等算术运算和一些逻辑运算。数值计算方法：

把求解数学问题转化为按一定次序只进行加，减，乘，除等基本运算.设计数值算法的出发点？如何学好数值计算方法？威尔金森（JamesHardy.Wilkinson，1919-1986）Wilkinson是数值分析和数值计算的开拓者和奠基人。1940年，开始研究弹道的数学模型与数值计算。1946年成为Turing的助手，协助设计PilotACE计算机。1969年他当选为英国皇家学会院士；1970年工业和应用数学会(s1am)授予他冯·诺伊曼奖；1987年他获得美国数学会的chauvenet奖。著名的美国阿尔贡国家实验室曾聘威尔金森为荣誉高级研究员并两次向他授奖。

Wilkinson在数值分析研究领域作出了杰出贡献，是数值计算的早期开拓者，其工作加速了数字计算机(在科学计算中)的使用。他研究的主要问题是线性代数方程组和矩阵特征值问题的数值解法，特别是他的向后误差分析法(backwarderroranalysis)的创造性工作奠定了数值分析和数值计算早期的理论基础。

1975年J.H.Wilkinson成为第五位图灵奖获得者。教材现代科学与工程计算孟大志刘伟（高等教育出版社）参考书目

数值分析孙志忠袁慰平等（东南大学出版社,第二版）

应用数值方法使用MATLAB和C语言

RobertJ.Schilling&SandraL.Harris（机械工业出版社）

数值分析（第4版）李庆杨王能超易大义华中科技大学出版社数值分析与科学计算JefferyJ.Leader著，张威，刘志军，李艳红等译，（清华大学出版社)

数值分析精品课程网站：/na/html/index_common.htm

§2

算法一、算法的概念

描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。

定义：由基本运算及运算顺序的规定所构成的完整的解题步骤，称为算法。例：求解二元一次联立方程组用行列式解法：首先判别

（1）如果，则令计算机计算

输出计算的结果x1，x2。（2）如果D=0，则或是无解，或有无穷多组解。是否为零，存在两种可能：令通过求解过程，可以总结出算法步骤如下：S2计算S3如果则输出原方程无解或有无穷多组解的信息;否则S1输入S4输出计算的结果输入

D=a11a22-a12a21D=0开始输出

x1,x2

结束

No输出无解信息Yes二、算法优劣的判别

计算量的大小

存贮量

逻辑结构例：用行列式解法求解线性方程组:n阶方程组，要计算n+1个n阶行列式的值，总共需要做n!(n-1)(n+1)

次乘法运算。

n=20需要运算多少次？n=100?一、误差的来源与分类从实际问题中抽象出数学模型

——模型误差例:质量为m的物体，在重力作用下,自由下落，其下落距离s

与时间t的关系是：

其中g

为重力加速度。§3误差通过测量得到模型中参数的值

——观测误差求近似解——方法误差(截断误差）例如，当函数用Taylor多项式

近似代替时，数值方法的截断误差是

与0之间。在机器字长有限——

舍入误差

用计算机、计算器和笔算，都只能用有限位

=3.1415926…

小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：四舍五入后……在数值计算方法中，主要研究截断误差和舍入误差（包括初始数据的误差）对计算结果的影响！二、误差的概念1、绝对误差与绝对误差限例:若用以厘米为最小刻度的尺去量桌子的长，大约为1.45米，求1.45米的绝对误差。1.45米的绝对误差=？不知道！是近似值的绝对误差,简称为误差。

定义：设是准确值，为

的一个近似值，称但实际问题往往可以估计出不超过某个正数，即则称为绝对误差限，有了绝对误差限,就可以知道的范围为即落在内。在应用上，常常采用下列写法来刻划的精度。2、相对误差与相对误差限定义：设是准确值，是近似值，是近似值的误差，通常取为近似值的相对误差，记作，称一般情况下是不知道的，怎么办？事实上，当较小时是的二次方项级,故可忽略不计.相应地，若正数满足

则称为的相对误差限。3、有效数字定义：如果则说近似表示准确到小数后第位，并从这第位起直到最左边的非零数字之间的一切数字都称为有效数字，并把有效数字的位数称为有效位数。如果一个近似数的所有数字均为有效数字，则称之为有效数。由上述定义故若取作的近似值，就有五位有效数字。若取作的近似值，就有六位有效数字。取作的近似值，就有三位有效数字。注：若一近似数是由原真值经四舍五入得到，则必为有效数.定义:若近似值的误差限是某一位的半个单位,也即，若有位有效数字。则称其中，是1到9中的一个数字；是0到9中一个数字；为整数，且该位到的左边第一位非零数字共有位,就说有位有效数字。由上述定义故的近似值分别有三位、五位和六位有效数字。4、相对误差限与有效数字的关系Th1.1：

则

至少具有位有效数字。对于用式表示的近似数，若具有位有效数字，则其相对误差限为反之，若的相对误差限为Th1.2：

设反之,若的相对误差的绝对值大于，其中为整数,为正整数,。有位有效数字。则至多若至多有位有效数字,即是有效数字,而不是有效数字,则的相对误差的绝对值必大于;证明：不是有效数字

反之,若

则

不是有效数字，

即至多有位有效数字.

§4

数值运算的误差估计一、四则运算的误差估计两个近似数与,其误差限分别为及,它们进行加减乘除运算得到的误差限分别为二、函数误差估计当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的Taylor展开式进行估计。

设是一元函数，的近似值为,以近似，其误差限记作，可用Taylor展开

介于之间.取绝对值得假定与的比值不太大,,可忽略的高阶项,于是可得计算函数的误差限为

当为多元函数时计算,如果的近似值为,则的近似为于是函数值的误差由Taylor展开,得：于是误差限为而的相对误差限为(1.3.1)(1.3.2)例:已测得某场地长的值为,宽的值为,已知,.试求面积的绝对误差限与相对误差限.解:因

其中由式(1.3.1)得而于是绝对误差限为相对误差限为§5

算法的数值稳定性

数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称其为数值不稳定。

例：求定积分的值.解：直接积分可产生递推公式若取初值可得递推公式按公式就可以逐步算出注意此公式精确成立，且Whathappened?!不稳定的算法！这就是误差传播所引起的危害!

NYBJ蝴蝶效应——纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！这是一个病态问题由题设中的递推公式（1）可看出，

的误差扩大了5倍后传给

，因而初值

的误差对以后各步这就造成的计算结果严重失真。计算结果的影响，随着

的增大愈来愈严重。要怎么做才能解决这个问题呢?可求得I9

0.017，按改写后的公式可逐次求得不妨设I9

I10，于是由将公式变为

I8

0.019I7

0.021 I6

0.024I8

0.028 I4

0.034I3

0.043 I2

0.058I1

0.088 I0

0.182稳定的算法！

在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。注：递推公式(1)的舍入误差以5的幂次增长进行传播，因此是数值不稳定的，而递推公式(2)的舍入误差在一定范围内以0.2的幂次进行传播，随着n的增大，误差逐步减少，因此该算法是数值稳定的。

因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为无条件稳定。而对某些数据数值稳定，对其它数据数值不稳定的算法，称为条件稳定。1.要避免两个相近的数相减在数值计算中，两个相近的数作减法时有效数字会损失。例:

求的值。当x=1000，y的准确值为0.01580

§6数值计算中应该注意的一些原则类似地

(2)若将原式改写为则y=0.01581(1)直接相减有3位有效数字！只有1位有效数字2.尽量避免绝对值太小的数作分母例：如分母变为0.0011，也即分母只有0.0001的变化时结果相差这么大!3.避免大数吃小数精确解为

算法1：利用求根公式例：用单精度计算的根。在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.00000000011010，取单精度时就成为：109+1=0.100000001010+0.000000001010=0.100000001010算法2：先解出再利用注：求和时从小到大相加，可使和的误差减小。例：按从小到大、以及从大到小的顺序分别计算1+2+3+…+40+1094.简化计算步骤，避免误差积累。一般来说，计算机处理下列运算的速度为例：多项式求值：给定的x求下列n次多项式的值。

解：1.用一般算法，即直接求和法；

2.逐项求和法；3.秦九韶方法(即Hornor算法）；先计算x2,x3,…,xn,再作线性组合，需做2n-1次乘法和n次加法。解法一：直接求和法解法二：逐项求和法按顺序依次计算每一项的值再求和，需做n(n+1)/2次乘法和n次加法。解法三：秦九韶算法（即Horner算法）只需做n次乘法和n次加法。且可以递推实现。计算机上使用的算法常采用递推化的形式，递推化的基本思想是把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节省计算量。算法的递推性例：用秦九韶方法求多项式p(x)在x=-2处的值解：

Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0x+a420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a0约翰·冯·诺依曼（JohnvonNeumann,1903-1957）美藉匈牙利人，1930年接受了普林斯顿大学客座教授的职位，西渡美国。1931年成为该校终身教授。1933年成为新成立的普林斯顿高等研究院的终身研究员。1951年至1953年任美国数学会主席。冯·诺依曼是20世纪少有的数学科学通才，在许多领域都有重要的贡献，被西方人誉为“数学奇才、计算机之父”。冯·诺依曼对人类的最大贡献是对计算机科学、计算机技术和数值分析的开拓性工作。并行计算

一、电子计算机的并行计算分类

传统计算机一般采用VonNeumann结构，每一时刻只有一个进程的算法，即串行算法。

并行计算机每一时刻具有2个以上的进程的算法称为并行算法。并行机必须包含2台以上处理机，按指令流是单个还是多个并行算法可分为两类：

SIMD算法适用于单指令流多数据流系统；

MIMD算法适用于多指令流多数据流系统。

按照进程之间是否同步可将并行算法分为:

同步算法:是指在k个进程的算法中有些进程的若干算法必须在另一些进程的某些算法之后执行；异步算法:指k个进程间有信息联系但不须同步，它只能在一个具有k台处理机的MIMD系统中实现。二、并行计算的算法设计

并行算法设计的重要原则是“分而治之”。其基本思想是把问题依次划分为可以独立完成的较小问题，将规模逐次减半的二分技术是并行算法设计的一种基本技术。二分算法的设计原理是反复地将所给计算问题加工成规模减半的同类计算问题而计算。可利用串行算法来改造或设计并行算法，不少数值算法包含了可直接利用的并行性。还可以根据并行算法的特点设计具有新思想的新算法，它的出发点仍然是“分而治之”的原理，符合此原理的区域、算子、系统的分裂方法和技术是设计和实现并行处理的重要手段。此外，异步数值算法基本上是混乱迭代法，是并行算法最富有特色的组成部分之一。第二章插值§1引言一、引例已经测得在某处海洋不同深度处的水温如下：深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温.这就是本章要讨论的“插值问题”问题驱动：汽车的刹车距离

司机驾驶汽车时需要根据车速估计汽车的刹车距离以确保行车安全。图2.1.1某车型干燥路况刹车距离示意图

美国的某司机培训课程的有如下驾驶规则：正常的驾驶条件下对车与车之间的距离的要求是每小时10英里的速率可以允许一辆车的跟随距离。实现这一规则的简便方法就是“2秒法则”：这种方法不管车速为多少，后车司机从前车经过某一标志开始默数“一千零一，一千零二”，这样用英文读完就是两秒。如果你在默数完这句话前就到了同一标志处，那么你的车和前面的车靠得太近了。

假设车长为15英尺，根据这条法则可以得到如图2.1.1所示的图形，它表明该法则允许的距离间隔和速率成比例，即。其中为比例常数。

图2.1.2“2秒法则”的几何解释

下面给出一组经测试得到的关于刹车距离与速度的较为理想的实验数据，如表2.1.1所示。要想了解刹车的距离与车速的关系，试建立适当的数学模型，预测车辆的总停止距离d（英尺）关于速度v（英里/小时）的函数，检验2秒法则与驾驶规则是否一致，并尝试寻找更好的驾驶规则。v20253035404550d425673.591.5116142.5173v556065707580d209.5248292.5343401464表2.1.1刹车距离实验数据

插值法是一种古老的数学方法。早在1000多年前，我国历法上已经记载了应用一次插值和二次插值的实例。

伟大的数学家：拉格朗日（Lagrange）、牛顿Newton）、埃尔米特（Hermite）等人分别给出了不同的解决方法。二、插值问题的定义

当精确函数y=f(x)非常复杂或未知时，在区间这个问题称为“插值问题”

(2.1.1)近似函数g(x)

f(x)，满足条件

,由此构造一个简单易算的

上一系列节点

处测得函数值

这里的g(x)

称为f(x)的插值函数。节点x0…xm称为插值节点,条件（2.1.1)称为插值条件，区间称为插值区间。如果利用g(x)来求f(x)

在y点的近似值，则称y为插值点。插值函数的类型有很多种最常用的插值函数是

…?代数多项式用代数多项式作插值函数的插值称为代数插值，即选取次数不超过n的多项式Pn(x)，使得

Pn(xj)=yj(j=0,1…n)(2.1.2)本章主要讨论的内容插值问题插值法插值函数§2代数插值代数插值一、插值问题解的存在唯一性？二、插值多项式的常用构造方法？三、插值函数的误差如何估计？一、插值多项式的存在唯一性：设所要构造的插值多项式为：

由插值条件得到如下线性代数方程组：（2.2.1）（2.2.2）此方程组的系数行列式为

当

时，

D

0，因此，Pn(x)由a0,a1,…,an唯一确定。范得蒙行列式的转置！定理插值条件的n

阶插值多项式Pn(x)存在且唯一。插值多项式的构造：插值多项式的存在唯一性说明，满足插值条件的多项式存在，并且插值多项式与构造方法无关。如何构造插值函数才能达到预期的效果呢？对于给定的互异节点x0…xn,满足

，用于插值的简单函数元素集+线性组合结构→插值多项式简单函数元素集是指构成多项式的基函数集合，例如自然形式（2.2.1）的自然基底,、

、

(结构)(集合)若求自然形式(2.2.1)的插值多项式问题，只要求解线性方程组（2.2.2）计算出多项式系数即可。一般插值多项式的构造方法通过解方程组(2.2.2)求得插值多项式的方法并不可取.这是因为当n较大时解方程组的计算量较大，而且方程组系数矩阵的条件数一般较大（可能是病态方程组）,当阶数n越高时，

病态越重。怎样可以不通过求解方程组而获得插值多项式呢?在n次多项式空间Pn中找一组合适的基函数

,使不同的基函数的选取导致不同的插值方法.Lagrange插值Newton插值Hermite插值二、拉格朗日(Lagrange)插值1．线性插值(n=1)

x0x1(x0,y0)(x1

,y1)f(x)P1(x)n=1已知

x0

,

x1

;

y0

,

y1

，求l0(x)l1(x)2．抛物插值(n=2)p2(x)

f(x)x0x1x2f(x)因过三点的二次曲线为抛物线，故称为抛物插值。

3．n次拉格朗日插值公式设连续函数y=f（x）在[a,b]上对给定n+1个不同结点：

x0,x1,…,xn,分别取函数值y0,y1,…,yn其中

yi=f(xi)i=0,1,2,…,n试构造一个次数不超过n的插值多项式使之满足条件

i=0,1,2,…,n要求：无重合节点，即若能求得n次多项式lk(x),k=0,1,…,n，则

i=0,1,2,…,n即Pn(x)满足插值条件（2.1.2）.

满足因此，令又由lk(xk)=1，得：

的表达式推导：根据lk(x)的定义，xk以外所有的结点都是lk(x)的根，从而得n

阶拉格朗日（Lagrange）插值公式：4、插值余项/*Remainder*/定理4.3.1

若

在[a,b]内存在,则在[a,b]上的n+1个互异的点，对f（x)所作的n次Lagrange插值多项式有误差估计也称为Lagrange插值多项式的插值余项。当n=1时，线性插值的余项当n=2时，抛物插值的余项注：

通常不能确定

,而是估计,

x(a,b)，将作为误差估计上限。

当

f(x)为任一个次数

n

的多项式时，,可知，即插值多项式对于次数

n的多项式是精确的。

插值多项式一般仅用来估计插值区间内点的函数值（即内插），用它来计算插值区间外点的函数值（即外插）时，误差可能很大。

通常取依靠增加节点不一定能减少误差；

事后误差估计在实际计算中，由于函数f(x)往往未知或很难求得，也就难以求出或估计出其较精确的上界，从而难以估计一般可使用求出两个插值多项式之差的方法来估计误差，称之为事后估计。图2.1前后两组插值节点的划分插值余项可表示成取n+2个节点分别用前n+1个节点和后n+1个节点和，如图2.1所示构造n次插值多项式例：已知分别利用sinx的1次、2次Lagrange插值计算

sin50

，

并估计误差。解：n=1分别利用x0,x1

以及x1,x2

计算

利用

利用计算得：sin50

0.76008,

sin50=0.7660444…利用x0,x1

作为插值节点的实际误差

0.01001利用x1,x2作为插值节点的实际误差

0.00596n=2

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

0.00061三、牛顿插值（Newton’sInterpolation）Lagrange插值虽然易算，但若要增加一个节点时，全部基函数li(x)

都需要重新计算。希望每加一个节点时，只附加一项上去即可。

1、能否重新在

中寻找新的基函数？回顾：Lagrange插值的优缺点：

优点：具有严格的规律性,便于记忆。

缺点：计算量大、不具有承袭性。利用插值条件代入上式，得关于的线性代数方程组:设当

互异时，系数矩阵非奇异，且容易求解.Itisnotadifficultthingforamathematician.WecanusenotationHowcomplextheexpressionare!2．差商2.1差商的定义(亦称均差)

定义1：设已知函数f(x)在一系列互不相等的上的函数值

f(xi)

,

称为f(x)在点xi,xj处的一阶差商，记作f[xi,xj]，

节点，（即在时，）又称为f(x)在点xi,xj,xk处的二阶差商

称

为f(x)在点x0,x1,…,xk处的k阶差商。由差商定义可知：

高阶差商是两个低一阶差商的差商。利用差商的定义,可得的系数

:从而

因此，每增加一个结点，Newton插值多项式只增加一项，克服了Lagrange插值的缺点。

2.2差商的性质:

性质1(差商与函数值的关系):

记,则

性质2

（对称性）：

差商的值与结点排列顺序无关，即性质3(差商与导数的关系):设在上有阶导数,且则存在使得性质4(特征定理):差商可列表计算：

f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]xi

yi

一阶差商

二阶差商

n阶差商

……x0x1x2xn-1xn

xn+1f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]2.3差商的计算:

3.牛顿插值余项由插值多项式的唯一性可知，故其余项也相同，即定理：Newton插值多项式的余项为

其中，从而，例:给定的数据表

2.202.402.602.803.000.788460.875470.955511.029621.098611.构造差商表2.分别写出二次、四次Newton插值多项式解:构造差商表一阶差商二阶差商三阶差商四阶差商余项四、等距节点插值

1．引入(微商的离散化)2．差分的定义设函数在等距节点上的值

为已知,这里为常数,称为步长.定义:分别称为在处以为步长的一阶向前差分,一阶向后差分,以及一阶中心差分.3、差分表

计算各阶差分可按如下差分表进行：4、差分的性质性质1

(差分与函数值的关系):

各阶差分均可表示为函数值的线性组合:其中，性质2(向前差分与向后差分的关系):性质3(多项式的差分):

若f(x)∈Pn(n次多项式类),则性质4(差分与差商的关系):在等距节点的前提下，性质5(差分与导数的关系）：在等距节点的前提下，性质6：常数的差分等于零.性质7：差分算子为线性算子，即性质8：这个性质类比于

性质9：

（类比于分部积分法则）

5、等距节点的牛顿插值公式牛顿公式:

牛顿前插公式（用于计算最小节点附近的函数值）利用差分的性质,可将Newton公式简化为(1)称公式(1)为Newton向前差分插值公式,其余项为(2)

牛顿后插公式（用于计算最大节点附近的函数值）如果将Newton插值公式改为按节点的(3)次序排列的Newton插值公式,即令x=xn-th,则当x0≤x≤xn时,0≤t≤1.利用差商与向后差分的关系,式(3)可简化为(4)称式(4)为Newton向后差分插值公式。其余项为注：一般当x

靠近x0时用前插，靠近xn时用后插，故两种公式亦称为表初公式和表末公式。例

给定f(x)在等距节点上的函数值表如下:

xi0.40.60.81.0

f(xi)1.51.82.22.8分别用Newton向前和向后差分公式求f(0.5)及f(0.9)的近似值.

解

先构造向前差分表如下:

xi

fi

△fi

△2fi△3fi

0.41.50.61.80.30.82.20.40.11.02.80.60.20.1

x0=0.4,h=0.2,x3=1.0.分别用差分表中对角线上的值和最后一行的值,得Newton向前和向后插值公式如下:(1)

(2)当x=0.5时,用公式(1),这时t=(x-x0)/h=0.5.将t=0.5代入(1),得

f(0.5)≈N3(0.5)=1.64375.当x=0.9时,用公式(2),这时t=(x3-x)/h=0.5.将t=0.5代入(2),得

f(0.9)≈N3(0.9)=2.46875.五、Hermite插值1．引入

在实际问题中，对所构造的插值多项式，不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数P(x)满足:（1）把此类插值问题称为带导数的插值多项式，相应的插值多项式称为埃米尔特（Hermite）插值多项式或称H(x)

存在且唯一埃米尔特（Hermite）插值记为H(x)。2.推导只讨论函数值与导数值个数相等的情况.设在节点上,要求插值多项式,满足条件(5)这里给出的个条件,可唯一确定一个次数不超过的多项式其形式为如根据条件(5)来确定个系数,显然非常复杂。先求插值基函数及,共有个,每一个基函数都是次多项式,且满足条件Lagrange型Hermite插值多项式基函数方法(6)于是满足条件(5)的插值多项式可写成用插值基函数表示的形式,即(7)由条件(6),显然有下面的问题就是求满足条件(6)的基函数及为此,可利用Lagrange插值基函数.令其中,由条件式(6),有整理,得解得由于两端取对数再求导,得于是同理可得(8)(9)仿照Lagrange插值余项的证明方法,若在内的阶导数存在，则其插值余项为多少？(10)其中且与有关.3.Hermite插值余项作为带导数插值多项式(7)的重要特例是n=1的情形.这时可取节点为及,插值多项式为,满足条件(11)相应的插值基函数为,它们满足条件根据(8)式及(9)式的一般表达式,可得于是满足条件(11)的插值多项式是其余项为,由式(10)得注：

N

个条件可以确定阶多项式。其余项为N

1

要求在1个节点x0处直到m0阶导数都重合的插值多项式即为在点处的Taylor多项式Newton型Hermite插值（1）单节点的重节点差商（2）多节点的重节点差商插值条件：重节点差商可列表计算：

重节点差商的计算其中，例：设

x0

x1

x2,已知

,

求多项式

P(x)满足

解：首先，P的阶数为3,模仿Lagrange多项式的思想，设其中且

,并估计误差。4.举例h0(x)有根x1,x2，且

x1是重根。又:h0(x0)=1C0

h2(x)与h0(x)完全类似。h1(x)有根

x0,x2

由余下条件

h1(x1)=1和

可解。

(x)

h1

有根

x0,x1,x2又:

C1可解。与Lagrange分析完全类似

六、分段低次插值1.多项式插值的龙格现象例：在[5,5]上考察的Ln(x)。取

-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)

n

越大，端点附近抖动越大，称为Runge现象2.分段线性插值在每个区间上，用1阶多项式

(直线)逼近f(x):记,易证：当时，一致失去了原函数的光滑性。yxoy=f(x)y=p(x)若令则是分段一次的连续函数且满足条件

则即为分段线性插值的基函数,

基函数只在附近不为零,在其它地方均为零。这种性质称为局部非零性质。相应的分段线性插值函数为：分段线性插值的误差估计定理1

如果在上二阶连续可微,则分段线性插值函数的余项有以下估计

其中,3.分段三次Hermite插值

给定节点，在节点上的函数值及导数值分别为。其中基函数为是分段三次，总体是直至一阶导数连续，插值函数为在每个子区间上作两点三次Hermite插值，因此分段Hermite插值余项

由三次Hermite插值的余项可以估计分段Hermite插值的余项：设是给定节点

上的分段三次Hermite插值函数，，与的误差限为其中，

要求：插值曲线既要简单，又要在曲线的连接处比较光滑。

这样的分段插值函数在分段上要求多项式次数低，这种插值方法称为——样条插值。它所对应的曲线称为样条曲线，其节点称为样点，把满足这样条件的插值函数，称为样条插值函数，而在节点上不仅连续，还存在连续的低阶导数，图2.1早期机翼下轮廓的放样如图2.1所示，在早期的板材曲线切割时，常把富有弹性的细长木条（样条）固定在样点上，其它地方让其自由弯曲，然后画出长条的曲线称为样条曲线，由此启发设计整体连续光滑的样条插值函数。

问题

分段低次插值虽然具有简单、收敛性、整体连续性及数值计算的稳定性等优点，但在节点处常有“尖点”出现，光滑性较差。特别是需要给出节点处的导数值，这在多数问题中是不实际的。如何在没有节点导数数据时也能达到上述目的？为此引入样条插值函数。七、三次样条插值1.引入定义：设对y=f(x)在区间[a,b]上给定一组节点a=x0<x1<x2<…<xn=b和相应的函数值y0,y1,…,yn，如果s(x)具有如下性质：（1）在每个子区间[xi-1,xi](i=1,2,…,n)上s(x)是不高于三次的多项式;（2）s(x)，s’(x)，s

(x)在[a,b]上连续；则称s(x)为三次样条函数.如再有（3）s(xi

)=f(xi)(i=0,1,2,…,n)，则称s(x)为y=f(x)的三次样条插值函数。注：三次样条与分段Hermite插值的根本区别在于S(x)自身光滑，不需要知道f的导数值（除了在2个端点可能需要）；而Hermite插值依赖于f在所有插值点的导数值。S(x)H(x)f(x)给定函数f(x)在[a,b]上的一组节点：及节点上的函数值

，函数S(x)是满足下列条件的函数的三次样条插值(2)S(x)在子区间

上是三次多项式，记为;；

2.三次样条插值函数的构造(3)在插值节点处连续，即

(4)即(1)。

要保证S(x)的存在唯一性，必须附加两个边界条件。例如，满足下列四种边界条件中的任意一个：(1)固支边界条件（D1-样条）：3.边界条件(2)弯矩边界条件（D2-样条）：

(3)自然边界条件（自然样条）：

(4)周期边界条件（周期样条）

：上述几种边界条件都有它们的实际意义，从力学角度看，附加边界条件相当于在细梁两端加上约束。工程中常用自然边界条件求样条插值函数，这类插值函数称为自然样条函数，利用插值条件和连续线性条件列出线性方程组并求解，是一种构造样条的基本方法。构造思想:

通过构造含待定参数的分段三次Hermite插值多项式来构造三次样条插值函数。构造Hermite插值多项式需要知道被逼近函数f(x)的导数，而导数通常是不知道的。三次样条插值函数的构造则不需要知道f(x)的导数值，直接将其作为待定参数，利用各节点在连接处的光滑性与连续性条件，建立关系式来确定待定参数，从而构造插值多项式。4.三弯矩方程设f(x)是定义在

[a,b]区间上的一个二次连续可微函数，

为分划：令i=0,1,2,…,n在每一个小区间[xi-1,xi]i=1,…,n

上都是三次多项式，

S

(x)在

[xi-1,xi]上的表达式为：其中，将（12）两次积分得：（12）Ai和Bi为积分常数。

因为所以它满足方程：

（13）解得故求

Mi，确定S(x)的表达式。微分（13）式于是

11111163)(++++++--+=¢iiiiiiiiiMhhyyMhxS由

得（14）则（13）可以写为各项除以hi+hi+1，并记

（1）D1-样条：于是可得有给定两端点导数值：

分别补充为方程组（13）的第一个和最后一个方程组，得D1-样条的三弯矩方程为：

（2）D2-样条：给定边界条件得三弯矩方程若取M0=Mn=0，称为三次自然样条。（3）周期样条：若f(x0)=f(xn),则可将s(x0

)=f(x0)或

s(xn

)=f(xn)去掉，再加入条件①②③可得周期样条的三弯矩方程补充（14）中的最后及第一个方程经补充后的方程组（13）为（14）其中，对端点条件①，有对端点条件③，有（14）是一个三对角方程组，可用追赶法解之。此方程组系数严格对角占优！从而存在唯一解。求出了Mi(i=0,1,…,n)，也就求得了S(x)在各个小区间的表达式Si(x)（i=0,1,2,…,n）5、三次样条插值的计算步骤(1)根据已知条件顺次计算方程组系数

，求出三次样条插值的三弯矩方程组；

(2)由给定边界条件，确定

；(3)用追赶法求解方程组(14)，求出

，再使用逆序回代求出

；(4)将求出的代入(13)式，求出

上的三次样条插值

函数。对给定的点

，须首先确定所在的子区间然后按三次样条插值的计算步骤计算，，进而求出

。6.算法若取等距节点

hi=h,i=1,…,n–1（1）

i=1,2,…,nhi=xi–xi-1（2）i=1,2,…,n（3）解n–1阶三对角方程组，得M1,M2,…,Mn-1

代入端点条件计算M0,Mn（4）

若取，计算7.三次样条插值函数的收敛性定义:设是区间上的连续函数，记函数的范数.为定理

设被插值函数为满足边界条件①或③的3次样条插值函数，则在插值区间

上成立余项估计式其中,汽车刹车距离求解

使用三次样条插值来预测车辆的停止距离，若给定自然边界条件进行三次样条插值，则有

，由公式可计算出代入(14)可得由追赶法可求得代入公式求得三次样条函数如表2.1所示，插值图像如图2.2所示。表2.1图2.2刹车距离问题的三次样条插值函数

显然这个结果与“2秒法则”并不一致，对于每小时40英里以下速率是相当吻合的，而对速率大于每小时40英里的汽车来说则大大低估了停止距离。根据样条插值函数，计算不同速率的刹车时间为：

由此可以提出一种新的法则为：当速率介于为英里/小时之间时遵循“2秒法则”，当速率介于为英里/小时之间时遵循“3秒法则”，当速率介于为英里/小时之间时遵循“4秒法则”。历史与注记

1756年，拉格朗日被任命为普鲁士科学院通讯院士。1766年任普鲁士科学院数学部主任。1786年出任法国米制委员会主任。1795年拉格朗日被选为法兰西研究院科学院数理委员会主席。1813年4月3日，拿破仑授予他帝国大十字勋章。

拉格朗日在数学上最突出的贡献是使数学分析与几何与力学脱离开来，使数学的独立性更为清楚。他在数值计算上的主要贡献是发展了欧拉所开创的变分法，为变分法奠定了理论基础。近百余年来，数学领域的许多新成就都可以直接或间接地溯源于拉格朗日的工作，在数学史上被认为是对数学的发展产生全面影响的数学家之一。拉格朗日(Joseph-LouisLagrange，1736～1813)拉格朗日1736年生于意大利都灵，1813年卒于巴黎。

在近代，插值法是观测数据处理和函数制表所常用的工具，又是导出其它许多数值方法（如数值积分、非线性方程求根、微分方程数值解等）的依据。插值法的一般参考资料见文献[1,2]，关于样条的一篇有重要影响的论文参见文献[3]。

插值一词最早是由Wallis提出的，公元6世纪，中国刘焯已将等距二次插值用于天文计算。17世纪，牛顿和格雷果里建立了等距节点上的插值公式。18世纪，拉格朗日给出了更一般的非等距节点上的插值公式。1946年,Schoenberg首先提出了样条插值函数。[1]P.J.Davies.TheFiniteElementMethod:AFirstApproach.OxfordUniversityPress,NewYork,1980.[2]M.J.D.Powell.ApproximationTheoryandMethods.CambridgeUniversityPress,NewYork,1981.[3]I.J.Schoenberg.Contributionstotheproblemofapproximationofequidistantdatabyanalyticfunctions.QuarterlyofAppliedMathematics4,1946.参考文献第三章函数逼近与计算

在科学与工程技术的很多领域，人们常碰到大量带有误差的实验数据，这时采用高次插值会出现震荡，采用分段插值则会使函数非常复杂，无法准确反映被侧函数的整体性态，因此，不适合用插值法。§1引言

如何在给定精度下，求出计算量最小的近似式，这就是函数逼近要解决的问题。

一、问题的提出二、函数逼近问题的一般提法：对于函数类

中给定的函数

，要求在另一类较简单的且便于计算的函数类

中寻找一个函数

，使

与

之差在某种度量意义下最小。注：本章中所研究的函数类

通常为区间

上的连续函数，记做

;而函数类

通常是代数多项式或三角多项式。

的函数逼近称为最佳一致逼近或均匀逼近。三、常用的度量标准：

(一)最佳一致逼近若以函数f(x)和P(x)的最大误差作为度量误差

f(x)－P(x)

“大小”的标准,在这种意义下(二)最佳平方逼近：采用

作为度量误差“大小”标准的函数逼近称为最佳平方逼近或均方逼近。§2最佳一致逼近一、最佳一致逼近的概念设函数

是区间

对于任意，如果存在多项式

，使不等式则称多项式

在区间

上一致逼近(或均匀逼近)于函数

定义上的连续函数，给定的成立，。二、最佳一致逼近多项式的存在性定理1（维尔斯特拉斯定理）

若f(x)是区间[a,b]上的连续函数，则对于任意

>0，总存在多项式

P(x)，使对一切a≤x≤b

有上的最佳一致逼近在能否在所有次数不超过n的代数多项式中找到一个

表示由所有次数不超过n的代数多项式构成的线性空间。空间中的最佳一致逼近问题。

意义下:，使得其中，这就是三、四、上最佳一致逼近多项式的存在性

定理2（Borel定理)

在

中都存在对

的最佳一致逼近多项式,记为

的n次最佳一致逼近多项式。称为简称最佳逼近多项式。,使得

成立.对任意的

五、相关概念1、偏差定义

上的偏差。则称为与在注：

，集合，记作

，它有下界0.显然，若的全体组成一个2、最小偏差若记集合的下确界为则称

为

在上的最小偏差。定义

3、偏差点定义

设

若在

上有

则称

是

的偏差点。

若

若

则称

则称

为“正”偏差点。

为“负”偏差点。

4、交错点组定义

若函数

在其定义域的某一区间

个点

上存在使得

则称点集

为函数

在区间

上的一个交错点组，称为交错点。点六、上的最佳一致逼近的特征引理3.1是区间

上的连续函数，是

的n次最佳一致逼近多项式，存在正负偏差点。

则设必同时定理3

（Chebyshev定理）是区间

上的连续函数，

设则

是

的n次最佳一致逼近多项式的充要条件是:

在区间

上存在一个至少由组。个点组成的交错点推论1是区间

上的连续函数，是

的n次最佳一致逼近多项式，在

内存在且保号，在区间

个点组成的交错点组，端点

都在交错点组中。

上恰好存在一个由设若则且两推论2推论3中,若存在对函数

的最佳一致逼近元，则惟一.在是区间上的连续函数，的

次最佳一致逼近多项式是

的某个

次插值多

项式。设则七、一次最佳逼近多项式1、推导过程设

，且

在内不变号，要求在上的一次最佳一致逼近多项式由推论1，在上恰好有3个点构成的交错且区间端点属于这个交错点组，组，设另一个交错点为则解得即即2、几何意义？3、举例求在上的最佳一次逼近多项式。解：由可算出故解得由得于是得的最佳一次逼近多项式为故误差限为(*)在（*）式中若令，则可得一个求根的公式八、Chebyshev多项式及其应用(1)定义称为n次Chebyshev多项式.[注]Itisveryimportant

令则而故为关于的次代数多项式。(2)性质正交性：由Tn(x)所组成的序列{Tn(x)}是在区间[-1,1]上带权

的正交多项式序列。

且

递推关系相邻的三个切比雪夫多项式具有如下递推关系式：

奇偶性：

切比雪夫多项式

，当

为奇数时为奇函数；

为偶数时为偶函数。