数值分析牛顿插值法演示课件.ppt

数值分析--第2章 插值法

2 第2章 插值法

在科学研究与工程技术中，常常遇到这样的问题：由实验或测量得到一批离散样点，要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工。反映在数学上，即已知函数在一些点上的值，寻求它的分析表达式。此外，一些函数虽有表达式，但因式子复杂，不易计算其值和进行理论分析，也需要构造一个简单函数来近似它。

解决这种问题的方法有两类：一类是给出函数)(xf的一些样点，选定一个便于计算的函数)(x形式，如多项式、分式线性函数及三角多项式等，要求它通过已知样点，由此确定函数)(x作为)(xf的近似，这就是插值法；另一类方法在选定近似函数的形式后，不要求近似函数过已知样点，只要求在某种意义下在这些样点上的总偏差最小。这类方法称为曲线（数据）拟合法。

设已知函数f在区间],[ba上的1n个相异点ix处的函数值(),0,,iiffxin，要求构造一个简单函数()x作为函数()fx的近似表达式()()fxx，使得

()(),0,1,,iiixfxfin (2-1)

这类问题称为插值问题。称f为被插值函数；()x为插值函数；nxx,,0为插值节点；(2-1)为插值条件。

若插值函数类{()}x是代数多项式，则相应的插值问题为代数插值。若{()}x是三角多项式，则相应的插值问题称为三角插值。若{()}x是有理分式，则相应的插值问题称为有理插值。

3

§1 Lagrange 插值

1.1 Lagrange 插值多项式

设函数f在1n个相异点01,,,nxxx上的值nixffii,,1,0),(是已知的，在次数不超过n的多项式集合nP中，求()nLx使得

(),0,1,,niiLxfnn (2-2)

定理2.1 存在惟一的多项式nnPL满足插值条件(2-2)。

数值分析-插值法

我们能得到⼀个函数f在区间[a,b]上某些点的值或者这些点上的⾼阶导数

我们就能通过插值法去得到⼀个函数g，g与f是⾮常相近的

⼀般来说g分为三类，⼀类是n次多项式 an*xn + a

n-1*xn-1 + .......+a

0，⼀类是三⾓多项式，最后⼀类是分段n次多项式

多项式插值

这个可以说是最简单的插值了

对于a

n*xn + a

n-1*xn-1 + .......+a0，我们有n+1个未知数，我只需要知道n+1个点的函数值就可以解出这n+1个未知数

将解出的值带⼊即可

优点:简单粗暴

缺点:要解n+1个⽅程，时间复杂度较⾼，n不好确定，若n过⼤，容易过拟合，若n过⼩，容易⽋拟合

拉格朗⽇插值

先说⼀阶多项式

我们有两点式

f(x) = y

k*(x

k+1 - x) / (x

k-x

k+1) + y

k+1*(x-x

k) / (x

k+1 - x

k)

此两点式可以看做∂ * yk + (1-∂) * y

k+1

那么⾃然的在x=xk的时候 ∂=0 在x=xk+1的时候∂=1

这⾥的∂其实是与x相关的⼀阶多项式

再说⼆阶多项式

对于⼀个⼆次函数，我们有三个点(xk-1,y

k-1) ,(x

k,y

k) ,(x

k+1,y

k+1)

我们有lk-1,l

k,l

k+1

f(x) = l

k-1*y

k-1 + l

k*y

k + l

k+1*y

k+1

其中l是与x相关的⼆次多项式

我们可以把l当作基函数

这样的话就有

x = x

k-1 时lk-1 = 1, l

k=0, l

k+1 = 0

x = x

k时 lk-1 = 0, l

k=1, l

k+1 = 0

x = x

k+1时lk-1 = 0, l

k=0, l

k+1 = 1

那么这个插值基函数是很好求的

因为每个插值函数都有两个零点

对于lk-1来说有零点xk,x

k+1

那么lk-1就可以表⽰为lk-1 = A*(x-x

k)*(x-x

k+1)

因为x=xk-1时lk-1 = 1

所以A = 1 / (（xk-1 - x

k）* (xk-1 - x

第三节 牛顿插值多项式

拉格朗日插值的优点是插值多项式特别容易建立，缺点是增加节点时原有多项式不能利 用，必须重新建立，即所有基函数都要重新计算，这就造成计算量的浪费；牛顿(Newton )插值多项式是代数插值的另一种表现形式，当增加节点时它具有所谓的“承袭性”，这 要用到差商的概念。

5.3.1 差商的定义与性质

定义 已知函数f(x)的n+1个插值点为),(jiyx，iy=f(ix)，i=0,1, …,n，jijixxxfxf)()(称为f(x)在点),(jiyx的一阶差商，记为f［jiyx,］，即

f［jiyx,］=jijixxxfxf)()( (5.3.1)

一阶差商的差商kikjjixxxxfxxf],[][称为f(x) 在点kjixxx,,的二阶差商，记为f［kjixxx,,］，即

f［kjixxx,,］=kikjjixxxxfxxf],[][(5.2.2)

一般地，k-1阶差商的差商kkkxxxxxfxxxf021110],...,[],...,,[称为f(x)在点kxxx,...,,10的k阶差商，记为f［kxxx,...,,10］，即

f［kxxx,...,,10］=kkkxxxxxfxxxf021110],...,[],...,,[ (5.3.3)

差商具有以下性质：

性质1 n阶差商可以表示成n+1个函数值)(),...,(),(10nxfxfxf的线 性组合，即

f［kxxx,...,,10］=niniiiiiiixxxxxxxxxf0110))...()()...(()(

事实上，由式(1)当n=1时，

011100101010)()()()(],[xxxfxxxfxxxfxfxxf

当n=2时， ))(()())(()())(()())(()()11()())(()())()((1))()((1],[],[],[],[],,[12022210112010012022210120120100122211020111002002211010212110210xxxxxfxxxxxfxxxxxfxxxxxfxxxxxxxfxxxxxfxxxfxxxfxxxxxfxxxfxxxxxxfxxxxfxxxxfxxfxxxf

牛顿(newton)插值法

牛顿插值法是一种数值分析中的插值方法，它用于找到一个多项式函数，该函数会经过给定的一系列数据点。该方法最初由英国数学家艾萨克·牛顿（Isaac Newton）发明并称为插值多项式，它也被称作差分插值法。

插值是数学和工程学中的一项重要任务，它是用于在给定数据点之间构建连续函数的一种数值方法。插值方法通常涉及过渡从观察结果派生出抽象结果的过程，从而使得预测可能的结果取得更加准确。

下面介绍牛顿插值法的基本原理。

插值基础

插值基础是插值方法中的一个重要概念。在这里，我们将对牛顿插值法中用到的插值基础进行简要介绍。

一个插值基础是指一个已知数据点的集合，通常是一个 x 坐标和对应的 y 坐标。每个插值基础一般定义为一个数据点的函数，该函数包含了给定点的所有信息并将这些信息用于构建连续函数。

在牛顿插值法中，我们使用差分来定义插值基础。差分是指两个相邻数据点之间 y

坐标的差值。具体来说，若给定以下节点：

x0, y0

x1, y1

x2, y2

...

xn, yn

我们则通过以下的 "+" 符号所示的不断进行差分的方式来构建一个插值基础：

y0

y1-y0

…

yn-yn-1 yn-yn-1 yn-yn-2 ... yn-y0 上述图表所展示的差分的值即为定义插值基础的差商（divided difference）。

牛顿插值公式

基于上述插值基础和差商，我们现在可以使用牛顿插值公式来实现插值。具体来说，牛顿插值公式可以表示为：

f(x) = y0 + d1*f[x0,x1] + d2*f[x0,x1,x2] + ... + dn*f[x0,x1,...,xn]

其中 f(x) 是插值函数，x0, x1, ..., xn 是给定的节点，y0, y1, ..., yn 是对应的 y 值，f[x0,x1] 是差商 f(x0,...,x1) 的值，d1, d2, ..., dn 也是差商。请注意，插值函数的次数最高为 n - 1，这意味着插值函数与插值基础的次数相同。