研究生数值分析(15)插商与牛顿(Newton)插值多项式 共17页

称为在xi,xj,xk处的2阶差商
k阶差商：
f [ x0 , x1 ,, xk 1 ] f [ x1 , x2 ,, xk ] f [ x0 , x1 ,, xk ] x0 xk
利用插值条件和差商,可求出Nn(x)的系数 Ai :
A0 f ( x0 ) f [ x0 ] A1 f [ x0 , x1 ]
差商具有如下性质
性质1 (差商与函数值的关系)
f ( xi ) f x0 , x1 ,..., xn i 0 ' ( xi )
性质2 （对称性）：差商的值与结点排列顺序无关
f x0 , , xi , , x j , , xn f x0 ,, x j ,, xi ,, xn
f ( xi ) f ( xi h) f ( xi )
f ( xi ) f ( xi ) f ( xi h)
一阶中心差分 f ( x ) f ( x h ) f ( x h ) i i i /* centered 2 2 difference */
一般地,称k阶差分的差分为k+1阶差分,如二阶 向前和向后差分分别为
f [ x, x0 ] f [ x0 , x1 ] ( x x1 ) f [ x, x0 , x1 ]
1
2
n1
…………
f [ x, x0 , ... , xn1 ] f [ x0 , ... , xn ] ( x xn ) f [ x, x0 , ... , xn ]
1 + (x x0) 2 + … … + (x x0)…(x xn1)
性质5(差分与导数的关系）
k fi k !h k f [ xi , xi 1 ,, xi k ] hk f ( k ) ( ), ( xi xi k )

当增加一个节点 xn+1 时，只需加上基函数
n 1 ( x xi )
i 0 n
即可。
Newton 插值
此时 f(x) 的 n 次插值多项式为
pn ( x ) a0 a1 ( x x0 ) a2 ( x x0 )( x x1 ) an ( x xi )
, xk ]
为 f(x) 关于 x0 , … , xk 的 k 阶差商。
差商的性质
1) 差商可以表示为函数值的线性组合。
可以用归纳法证明
f [ x0 , x1,, xk ]
j 0 k
f (xj ) ( x j x0 )( x j x j 1 )( x j x j 1 )( x j xk )
n
所以
f [ x, x0 , ... , xn ]
=
f ( n1) ( ξ x ) ( n 1) !
将 x 看作是一个节点，即可推广到一般情形：
f ( k ) ( ) f [ x0 , ... , xk ] k!
Newton 插值举例
例：已知函数 y = lnx 的函数值如下
x lnx
记：n+1(x) = (x-x0)(x-x1)…(x-xn)
f [ x0 , x1 , , xk ]
j 0 k
f (x j )
n1 '( x j )
2) 差商对节点具有对称性： f [ x0 ,, xi ,, x j ,, xk ] f [ x0 ,, x j ,, xi ,, xk ]
i 1 n1
其中 a0 f ( x0 ), ai f [ x0 ,, xi ], i 1,2,, n

牛顿插值法例题求解牛顿插值法是一种用于多项式插值的方法。

它利用给定数据点的函数值和差商的计算来构造一个多项式函数，从而在给定数据点之间进行插值。

以下是一个求解多项式插值的牛顿插值法的例题：假设有以下给定数据点与函数值：x: 0 1 2 4 y: 1 4 11 36现在要使用牛顿插值法，通过这些数据点拟合出一个多项式函数来进行插值。

解题步骤如下：1.计算差商表：x0 f[x0] 0 1 f[x0,x1] 1 4 f[x0,x1,x2] 2 11 f[x0,x1,x2,x3] 4 36差商的计算可以使用以下公式：f[xi,xi+1,...,xi+k] = (f[xi+1,xi+2,...,xi+k] - f[xi,xi+1,...,xi+k-1]) / (xi+k - xi)2.使用差商表计算插值多项式：插值多项式P(x) = f[x0] + f[x0,x1](x-x0) + f[x0,x1,x2](x-x0)(x-x1) + f[x0,x1,x2,x3](x-x0)(x-x1)(x-x2)P(x)的展开式为：P(x) = 1 + 3(x-0) + 2(x-0)(x-1) + 2(x-0)(x-1)(x-2)3.使用得到的插值多项式进行插值计算。

例如，要计算在x=3 的位置的插值结果，将x 替换为3，计算P(3)：P(3) = 1 + 3(3-0) + 2(3-0)(3-1) + 2(3-0)(3-1)(3-2) = 1 + 9 + 12 + 6 = 28因此，使用牛顿插值法，给定数据点(0,1), (1,4), (2,11), (4,36)，在 x=3 的位置的插值结果为 28。

注意，此例仅为示例，实际问题中，使用牛顿插值法时可能需要更多的数据点和计算过程。

在实际应用中，还需要考虑插值误差、阶数选择以及数据点的分布等因素。

z
0.612547 0.641384 0.641186
6 求方程 m重根的Newton法 设 s 是方程 f(x)=0 的 m 重根(m≥2), f(x)
在 s 的某邻域内有m阶连续导数 ,这时
f (s) f (s) f (m1) (s) 0, f (m) (s) 0
由Taylor公式,得
设 f '(x) 0 ，上式解为
x

xk

f (xk ) f ' (xk )
于是方程 f(x)=0的新的近似根xk+1，可由牛顿
迭代公式
xk 1

xk

f (xk ) f ' (xk )
k 0,1, 2,
求出
牛顿迭代公式具有明显的几何意义。 方程 y f (xk ) f '(xk )(x xk ) 是曲线 y=f(x)在点 (xk , f (xk )) 处的切线方程，迭代公式就是切线与x轴 交点的横坐标。因此，牛顿迭代法又称为切线法。
这表明牛顿迭代法用于求单根时至少是二阶收敛的。
（2）若 x* 是方程 f (x) 0 的 m(m 2) 重根，
即
f (x) (x x*)m q(x)
(q(x*) 0)
此时有
g ' (x*) lim g ' (x) lim
x x*
x x*
f (x) f '' (x) [ f ' (x)]2
k
xk
k
xk
4 0.635498 8 0.640964
5 0.643719 9 0.641285
6 0.640061 10 0.641142

第5章 插值与拟合方法插值与拟合方法是用有限个函数值(),(0,1,,)i f x i n =⋅⋅⋅去推断或表示函数()f x 的方法，它在理论数学中提到的不多。

本章主要介绍有关解决这类问题的理论和方法，涉及的内容有多项式插值，分段插值及曲线拟合等。

对应的方法有Lagrange 插值，Newton 插值，Hermite 插值，分段多项式插值和线性最小二乘拟合。

1 实际案例2 问题的描述与基本概念先获得函数（已知或未知）()=在有y f x由表中数据构造一个函数P(x)作为f(x) 的近似函数，去参与有关f (x)的运算。

科学计算中，解决不易求出的未知函数的问题主要采用插值和拟合两种方法。

1）插值问题的描述已知函数()y f x =在[a,b ]上的n +1个互异点nx x x ⋅⋅⋅,,10处的函数值()i i y f x =，求f (x ) 的一个近似函数P (x )，满足()()(0,1,,)i i P x f x i n ==⋅⋅⋅ （5.1）● P (x ) 称为f (x )的一个插值函数; ● f (x ) 称为被插函数;点i x 为插值节点; ● ()()(0,1,,)i i P x f x i n ==⋅⋅⋅称为插值条件; ● ()()()R x f x P x =-称为插值余项。

当插值函数P (x )是多项式时称为代数插值（或多项式插值）。

一个代数插值函数P (x )可写为0()()()mkm k k k P x P x a x a R ===∈∑若它满足插值条件（5.1），则有线性方程组20102000201121112012m m m m m n n m n na a x a x a x y a a x a x a x y a a x a x a x y ⎧+++⋅⋅⋅=⎪+++⋅⋅⋅=⎪⎨⎪⎪+++⋅⋅⋅=⎩ （5.2）当m=n ，它的系数行列式为范德蒙行列式)(1110212110200j i ni j n nnnn nx x x x x x x x x x x D -∏==≤≤≤因为插值节点互异，0D ≠，故线性方程组（5.2）有唯一解，于是有定理 5.1 当插值节点互异时，存在一个满足插值条件()()(0,1,,)i i P x f x i n ==⋅⋅⋅的n 次插值多项式。

数值分析报告班级：专业：流水号：学号：姓名：常用的插值方法序言在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数据点。

插值是离散函数逼近的重要方法，利用它可通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值。

早在6世纪，中国的刘焯已将等距二次插值用于天文计算。

17世纪之后，牛顿、拉格朗日分别讨论了等距和非等距的一般插值公式。

在近代，插值法仍然是数据处理和编制函数表的常用工具，又是数值积分、数值微分、非线性方程求根和微分方程数值解法的重要基础，许多求解计算公式都是以插值为基础导出的。

插值问题的提法是：假定区间[a，b〕上的实值函数f（x）在该区间上n＋1个互不相同点x0，x1……x n处的值是f（x0），……f（x n），要求估算f（x）在[a，b〕中某点的值。

其做法是：在事先选定的一个由简单函数构成的有n＋1个参数C0，C1，……C n的函数类Φ(C0，C1，……C n)中求出满足条件P（x i）＝f（x i）（i＝0，1，……n）的函数P(x)，并以P(x)作为f(x)的估值。

此处f（x）称为被插值函数，x0，x1，……xn 称为插值结(节)点，Φ(C0，C1，……C n)称为插值函数类，上面等式称为插值条件，Φ（C0，……C n）中满足上式的函数称为插值函数，R（x）＝f（x）－P（x）称为插值余项。

求解这类问题，它有很多种插值法，其中以拉格朗日(Lagrange)插值和牛顿(Newton)插值为代表的多项式插值最有特点，常用的插值还有Hermit 插值，分段插值和样条插值。

一．拉格朗日插值1.问题提出：已知函数()y f x =在n+1个点01,,,n x x x 上的函数值01,,,n y y y ，求任意一点x '的函数值()f x '。

说明：函数()y f x =可能是未知的；也可能是已知的，但它比较复杂，很难计算其函数值()f x '。

数值计算⽅法实验之Newton多项式插值（MATLAB代码）⼀、实验⽬的在⼰知f(x),x∈[a,b]的表达式，但函数值不便计算或不知f(x),x∈[a,b]⽽⼜需要给出其在[a,b]上的值时,按插值原则f(x i)=y i (i=0,1,……, n)求出简单函数P(x)(常是多项式)，使其在插值基点x i处成⽴(x i)= y i(i=0,1,……,n),⽽在[a,b]上的其它点处成⽴f(x)≈P(x).⼆、实验原理三、实验内容求f(x)=x4在[0,2]上按5个等距节点确定的Lagrange插值多项式四、实验程序(1).m⽂件%输⼊的量:X是n+1个节点(x_i,y_i)(i = 1,2, ... , n+1)横坐标，Y是纵坐标，%x是以向量形式输⼊的m个插值点，M在[a,b]上满⾜｜f~(n+1)(x)｜≤M%注：f~(n+1)(x)表⽰f(x)的n+1阶导数%输出的量：向量y是向量x处的插值，误差限R，n次⽜顿插值多项式L及其系数向量C，%差商的矩阵Afunction[y,R,A,C,L] = newton(X,Y,x,M)n = length(X);m = length(x);for t = 1 : mz = x(t);A = zeros(n,n);A(:,1) = Y';s = 0.0; p = 1.0; q1 = 1.0; c1 = 1.0;for j = 2 : nfor i = j : nA(i,j) = (A(i,j-1) - A(i-1,j-1))/(X(i)-X(i-j+1));endq1 = abs(q1*(z-X(j-1)));c1 = c1 * j;endC = A(n, n); q1 = abs(q1*(z-X(n)));for k = (n-1):-1:1C = conv(C, poly(X(k)));d = length(C);C(d) = C(d) + A(k,k);%在最后⼀维，也就是常数项加上新的差商endy(t) = polyval(C,z);R(t) = M * q1 / c1;endL = poly2sym(C);　（2）命令窗⼝输⼊X = [0 0.5 1.0 1.5 2.0];Y = [0 0.0625 1 5.0625 16];x = linspace(0,pi,50);M = 1;[y,R,A,C,L] = newton(X, Y, x, M);y1 = x.*x.*x.*x; %可根据所给函数更改errorbar(x,y,R,'.g')hold onplot(X, Y, 'or', x, y, '.k', x, y1, '-b');legend('误差','样本点','⽜顿插值估算','x^4');五、运算结果(1) 图像(2) 运算结果第⼀列为所得多项式系数：。

f [xi , xi1 , xi2 ]
f [ xi , xi1 ] f [ xi1 , xi2 ] xi xi2
fi fi1 2h2
2 fi 2h2
fi1
fi2 2h2
2 fi2 2h2
f [xi , xi1 , xi2 , xi3 ]
f [ xi , xi1 , xi2 ] f [ xi1 , xi2 , xi3 ] xi xi3
2 fi 2 fi1 3 2h3
3 fi 3!h3
2
fi2 2 fxi3 3 2h3
3 fi3 3!h3
依此类推
f
[ xi , xi1 ,, xim ]
m fi m!hm
m fim m!hm
f
[ x0
,
x1
,,
xk
]
k f0 k!hk
k fk k!hk
2. Newton向前(差分)插值公式
n
k 1
n
f0 f [x0 , x1 ,, xk ] (x xj ) f [x, x0 , x1 ,, xn ] (x xj )
k 1
j0
j0
n
Nn(x) f [x, x0 , x1 ,, xn ] (x xj ) j0
Nn(x) Rn(x)
因此
Rn ( x)
f (n1) ( )
一般，可定义
向
0 fi fi
前 差 分
k fi k1 fi1 k1 fi (k 1,2,, n; i 0,1,2,, n k)
为f (x)在 xi 处的 k 阶向前差分。
同样可以定义 f x 的向后差分：
向
后
fi fi fi1
差 分

同 理 ： (t) 至 少 有n 个 互 异 零 点；
(t) 至 少 有n 1 个 零 点 ；
(n1) (t ) 至 少 有 一 个 零 点 ； 即 (a ，b)，
(n1) (
)
R(n1) n
(
)
K ( x)n1(n1) (
)
R(n1) n
(
)
K ( x) (n
1)!
f (n1) ( ) K ( x) (n 1)! 0
x x0 x1 x2 xn ， y f ( x)？ y y0 y1 y2 yn
（1）有的函数没有表达式，只是一种表格函数，而我们需要的 函数值可能不在该表格中。
（2）如果函数表达式本身比较复杂，计算量会很大；
对于这两种情况，我们都需要寻找一个计算方便且表达简单
的函数 P x来近似代替 f ( x)，求 P x 的方法称为插值法。
Ln1( x)
为此我们考虑对Lagrange插值多项式进行改写； ——由唯一性，仅是形式上的变化
期望：Ln ( x) 的计算只需要对Ln1( x)作一个简单的修正.
考虑 h( x) Ln ( x) Ln1( x) h( x) 是次数 n 的多项式，且有
h( x j ) Ln ( x j ) Ln1( x j ) 0 ，j 0 ，1，2 ，L ，n 1 ；
)
3
)
1 2
(x
(
4
6
6
)( x
)(
4
3
)
3
)
1
(
x
6
)(
x
4
)
2
(
3
6
)(
3
4
)
3 2

上页
下页Biblioteka 其中P 次插值多项式, 称为被插函 其中 n(x) 称为 f(x) 的n次插值多项式 f(x) 称为被插函 次插值多项式 称为插值节点 数, xi(i=0,1, ...,n)称为插值节点 (xi, yi) (i=0,1, … ,n) 称为 称为插值节点, 插值点, 称为插值区间 插值区间, 称为插值条件 插值点 [a,b] 称为插值区间 式(5-1)称为插值条件。 称为插值条件。 从几何意义来看,上 从几何意义来看 上 述问题就是要求一条多 项式曲线 y=Pn(x), 使它 通过已知的n+1个点 通过已知的 个点 (xi,yi) (i=0,1, … ,n),并用 并用 Pn(x)近似表示 近似表示f(x). 近似表示
第2章 插 值 法 章
在工程技术与科学研究中， 在工程技术与科学研究中，常会遇到函数表达 式过于复杂而不便于计算， 式过于复杂而不便于计算，且又需要计算众多点处 的函数值；或已知由实验（测量） 的函数值；或已知由实验（测量）得到的某一函数 y=f(x)在区间 在区间[a,b]中互异的 中互异的n+1个xi ( i=0, 1, ... ,n)处 处 在区间 中互异的 个 的值y 需要构造一个简单易算的 的值 i=f(xi) (i=0,1,...,n), 需要构造一个简单易算的 函数P(x)作为 作为y=f(x)的近似表达式 函数 作为 的近似表达式 y=f(x)≈P(x) , 使得 P(xi)= f(xi) = yi (i=0,1, ..., n) 这类问题就称为插值问题， 称为插值函数 这类问题就称为插值问题， P(x)称为插值函数， 插值问题 称为插值函数， P(x)一般取最简单又便于计算得函数。 一般取最简单又便于计算得函数。 一般取最简单又便于计算得函数

研究生数值分析目录1. 内容概要 (3)1.1 研究背景 (3)1.2 研究目的与意义 (4)1.3 研究内容与方法 (5)2. 数值分析基本概念 (6)2.1 数值分析的定义 (8)2.2 数值分析的研究对象 (9)2.3 数值分析的应用领域 (10)3. 数值逼近 (11)3.1 插值法 (12)3.1.1 插值问题的提出 (13)3.1.2 插值函数的性质 (14)3.1.3 常用插值方法 (15)3.2 近似计算 (16)3.2.1 近似计算的必要性 (18)3.2.2 近似误差分析 (19)3.2.3 常用近似方法 (20)4. 线性代数方程组 (22)4.1 线性代数方程组的基本理论 (23)4.2 高斯消元法 (24)4.3 迭代法 (25)4.3.1 迭代法的原理 (26)4.3.2 常用迭代法 (27)5. 微分方程数值解法 (28)5.1 常微分方程初值问题的数值解法 (29)5.1.1 欧拉法 (30)5.1.2 迭代法 (31)5.1.3 高斯赛德尔法 (32)5.2 偏微分方程数值解法 (33)5.2.1 有限差分法 (34)5.2.2 有限元法 (36)6. 最优化方法 (37)6.1 最优化问题的基本理论 (38)6.2 无约束最优化方法 (39)6.3 约束最优化方法 (40)6.3.1 拉格朗日乘子法 (40)6.3.2 内点法 (41)7. 数值计算软件介绍 (42)7.1 MATLAB软件介绍 (44)7.2 Python编程语言在数值分析中的应用 (45)7.3 其他数值计算软件简介 (46)8. 实例分析 (47)8.1 某工程问题的数值分析 (48)8.2 某科学问题的数值模拟 (49)9. 总结与展望 (50)9.1 研究成果总结 (52)9.2 存在的问题与不足 (53)9.3 未来研究方向 (54)1. 内容概要本课程《研究生数值分析》旨在为研究生提供深入的数值分析理论知识和实践技能。

n
n
H
h 3
(
x
)

i ( x) yi
i ( x) y'i
i0
i0
i ( x)是对应于第i个节点函数的基函数,
i ( x)是对应于第i个节点导数的基函数,
i ( x)应满足:
(1)分段三次多项式，
i ( x)应满足:
(1)分段三次多项式，
(2)
i
(
x
j
)


ij
,
' i
n
Lh1 ( x) lih( x) yi
i0
其中lih( x)为分段线性插值基函数.
分段线性插值基函数lih( x)应满足
（1）lih( x)为分段线性函数，
（2）lih( x j ) ij

1 0
i j i j
数值分析
数值分析
分段线性插值基函数lih( x)的具体形式为
l0h
分段线性插值问题的解存在唯一.
数值分析
数值分析
2.分段线性插值函数的表达式
由定义， (x)在每个子区间[xi ,xi+1](i=0,1,2,,n-1)
上是一次插值多项式;
( x) L1( x)
x xi1 xi xi1
yi

x xi xi1 xi
yi1
Y
y=f(x)
是否有
lim
n
Pn
(
x
)

f (x)，即要讨论收敛性问题。
数值分析
数值分析
龙格(Runge)现象
插值节点的增多,尽管使插值多项式在更多的插
值节点上与函数 f(x) 的值相等,但在两个节点之间

牛顿差值法牛顿差值法（Newton’s Difference Method）是一种在数值分析中广泛应用的二次多项式拟合方法和根求解方法。

该方法引入了多项式中的牛顿多项式（Newton Polynomial）。

牛顿多项式将一组数据的多项式拟合能力极大地提升，从而使得求解方程的精度和速度都更加有效。

牛顿差值法又称为牛顿插值法，最早可以追溯到17世纪法国数学家叶塞立雅（Isaac Newton）提出的，叶塞立雅是一位非常伟大的数学家，他发明了多种重要的数学方法，而牛顿差值法是他的最重要的发现之一。

牛顿的思想是从一组已知的点的函数值拟合出一个多项式，其中的每个点都被精确的表示。

牛顿差值法是一种称为牛顿形式的特殊牛顿多项式的拟合方法，这种多项式简单并产生了一系列的非线性多项式公式，它将一组数据的拟合能力极大地提升，从而求解方程的精度和速度都更加有效。

牛顿差值法通常是基于插值函数的形式。

基于此函数形式，其计算（或估计）插值点的值时，都是使用已知的点的函数值的线性组合。

如一次多项式的形式为p_0+p_1x+p_2x^2，则给定点(x_0,f(x_0))...(x_n,f(x_n))，组合函数值f(x)即为f(x)= a_0 f (x_0)+a_1 f (x_1)...+a_n f (x_n).牛顿差值法中，系数a_0,a_1...a_n是拟合多项式系数，可以通过求解方程组来求解。

需要注意的是，牛顿差值法更能反映函数在点之间变化，它同样可用于插补曲线，主要用于拟合数据点，求解方程，以及求解极值点，等等。

由于牛顿多项式的拟合能力较强，牛顿差值法的估计和求解过程都比较精确，在实际应用中拥有良好的精度与准确性。

它常常被用于求解和拟合数据，尤其是函数的拟合，是一种经常应用的方法之一。

设给定函数个互异的节点处的函数值为关于节点的二阶差商缺倒数第二个节点缺最后一个节点最后一个节点倒数第二个节点缺倒数第二个节点缺最后一个节点最后一个节点倒数第二个节点由此定义显然
第4章 插值与拟合
4.3 差商与牛顿插值公式
Lagrange 插值多项式的基函数：
l j ( x)
( x x0 )(x x1 )( x x j 1 )(x x j 1 )( x xn ) ( x j x0 )(x j x1 )( x j x j 1 )(x j x j 1 )( x j xn )
4.3.3 牛顿插值余项
若将 x xi , (i 0,1,, n) 视为一个节点,则由一阶均差定义 有
f ( x) f ( x0 ) f [ x, x0 ](x x0 )
同理,由二阶均差定义 有
f ( x0 ) f ( x) f [ x, x0 ] f [ x, x0 ] f [ x0 , x1 ] f [ x, x0x ,0x1 ]( xx x1 )
j 1 k 0
n
j 1
2.差商的性质
性质1：差商与函数值的关系 f(x) 关于 x0 , x1 ,, xk 1 , xk 的 k 阶差商是 f(x) 在这些点上 函数值的线性组合,即
1 f [ x0 , x1 ,, xk 1 , xk ] f ( x j ) j 0 i 0 x j xi
(i j k )
为 f ( x) 关于节点 xi , x j , xk 的二阶差商
最后一个节点－倒 数第二个节点
称
缺倒数第二个节点
缺最后一个节点
f [ x0 , x1,, xk 1, xk ]
f [ x0 , x1 ,, xk 2 , xk ] f [ x0 , x1 ,, xk 1 ] xk xk 1

2 2
这里h为常数，称为步长， , 和 分别为向前, 向后和中心差分算子.
以向前差分为例 利用一阶差分可定义二阶差分
2 f k f k 1 f k f k 2 2 f k 1 f k .
还可以定义m阶差分 m f k m 1 f k 1 m 1 f k ;
xi ƒ(xi) x0 x1 x2 x3 xn ƒ(x0) ƒ(x1) ƒ(x2) ƒ(x3) ƒ(xn) 一阶 均差 二阶均差 三阶均差 n阶均差
ƒ[x0, x1] ƒ[x1, x2] ƒ[x0, x1, x2] ƒ[x2, x3] ƒ[x1, x2, x3] ƒ[x0, x1, x2, x3] ƒ[xn-1, xn] ƒ[xn-2, xn-1, xn] ƒ[xn-3, xn-2, xn-1, xn] ƒ[x0, x1,…, xn]
0 ( x) 1 1 ( x ) x x0 2 ( x ) ( x x0 )( x x1 )
LL n ( x ) ( x x0 )( x x1 ) L ( x xn1 )
当增加一个节点xn+1时，只需加上基函数
n1 ( x xi ) 即可.
n n n j
f k ( I E ) f k (1)
1 2
n1
………… f [ x, x0 , ... , xn1 ] f [ x0 , ... , xn ] ( x xn ) f [ x, x0 , ... , xn ]
1 + (x x0) 2 + … … + (x x0)…(x xn1)
n1
f [ x, x0 ] f [ x0 , x1 ] ( x x1 ) f [ x, x0 , x1 ]

Newton插值的原理和算法
Newton插值法是一种数学方法，用于通过已知的离散数据点来构造多项式，该多项式可以用来估计未知数据点的值。

以下是Newton插值的原理和算法：
原理：
Newton插值基于差商的概念。

差商可以理解为两个相邻数据点之间的值与它们之间距离的比的极限。

对于给定的数据点集，可以通过构造差商表来找到插值多项式。

算法：
1.确定插值节点：选择一组已知数据点的x坐标，这些点将成为插值的节
点。

2.计算差商：根据差商的定义，计算每个数据点与其相邻数据点之间的差
商。

具体来说，对于第i个数据点，其差商Di(x)可以表示为：Di(x) =
[f(xi)/xi - f(xi-1)/(xi-1)] / (xi - xi-1)，其中f(xi)和f(xi-1)分别是第i个和第i-1
个数据点的函数值，xi和xi-1分别是它们的x坐标。

3.构造差商表：将计算出的差商存储在一个表格中，以便后续使用。

4.构建插值多项式：根据差商表，使用Newton插值公式来构建插值多项
式。

具体来说，对于任意x坐标，其对应的函数值f(x)可以通过插值多项式来计算。

5.计算未知数据点的值：将需要估计的x坐标代入插值多项式中，即可得
到对应的函数值估计。

需要注意的是，Newton插值法在处理大量数据点时可能会遇到数值稳定性问题。

此外，当插值节点过多时，差商的计算量会变得非常大，因此在实际应用中需要谨慎选择插值节点数量。

数值计算⽅法实验之newton多项式插值（Python代码）⼀、实验⽬的在⼰知f(x),x∈[a,b]的表达式，但函数值不便计算或不知f(x),x∈[a,b]⽽⼜需要给出其在[a,b]上的值时,按插值原则f(x i)=y i (i=0,1,……, n)求出简单函数P(x)(常是多项式)，使其在插值基点x i处成⽴(x i)= y i(i=0,1,……,n),⽽在[a,b]上的其它点处成⽴f(x)≈P(x).⼆、实验原理三、实验内容求f(x)=x4在[0,2]上按5个等距节点确定的Lagrange插值多项式四、实验程序import matplotlib.pyplot as pltfrom pylab import mplimport mathx = [0, 0.5, 1, 1.5, 2]y = [0, 0.0625, 1, 5.0625, 16]"""计算四次差商的值"""def four_order_difference_quotient(x, y):# i记录计算差商的次数，这⾥循4次，计算4次差商。

i = 0quotient = [0, 0, 0, 0, 0]while i < 4:j = 4while j > i:if i == 0:quotient[j]=((y[j]-y[j-1])/(x[j]-x[j-1]))else:quotient[j] = (quotient[j]-quotient[j-1])/(x[j]-x[j-1-i])j -= 1i += 1return quotient;def function(data):return parameters[0] + parameters[1]*(data-0) + parameters[2]*(data-0)*(data-0.5) + parameters[3]*(data-0)*(data-0.5)*(data-1) + parameters[4]*(data-0)*(data-0.5)*(data-1)*(data-1.5)"""计算插值多项式的值"""def calculate_data(x,parameters):returnData=[];for data in x:returnData.append(function(data))return returnData"""画函数的图像newData为曲线拟合后的曲线"""def draw(newData):plt.scatter(x,y,label="离散数据",color="blue")plt.plot(datax,newData,label="⽜顿插值拟合数据",color="orange")plt.scatter(1.75,1.75**4, label="准确值",color="red")plt.title("⽜顿插值法拟合数据")mpl.rcParams['font.sans-serif'] = ['SimHei']mpl.rcParams['axes.unicode_minus'] = Falseplt.legend(loc="upper left")plt.show()parameters=four_order_difference_quotient(x,y)datax=[0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2]datay=calculate_data(datax,parameters)draw(datay)print("⽜顿插值多项式为：N(x) = %f(x-0) + %f(x-0)(x-0.5) + %f(x-0)(x-0.5)(x-1) + %f(x-0)(x-0.5)(x-1)(x-1.5)"%(parameters[1], parameters[2], parameters[3],parameters[4]))五、运算结果(1) 图像（2）运算结果六、⼼得体会通过本次实验，我对数值分析有了更深⼀个层次的认识，将数学理论和计算机软件结合会得到意想不到的结果⽐如插值法，在先学习了拉格朗⽇插值法后，对其理解透彻，了解了其中的原理和思想，再学习之后的⽜顿插值以及三次样条插值等等，都很容易的融会贯通，很容易的就理解了其中所想，其中⼼思想并没有多⼤的变化，但是使⽤的⽅式却是不同的每个不同的思考⽅式带来的都是不同的算法。