În analiză numerică , polinomul de interpolare Newton , numit după inventatorul său Isaac Newton , este polinomul de interpolare , exprimat sub forma Newton, folosind diferențe divizate .
Având un set de k + 1 puncte de date diferite între ele:
(
x
0
,
y
0
)
,
…
,
(
x
k
,
y
k
)
{\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})}
polinomul de interpolare în forma Newton este o combinație liniară din polinoamele Newton polinoame de bază
N
(
x
)
:=
∑
j
=
0
k
a
j
n
j
(
x
)
{\displaystyle N(x):=\sum _{j=0}^{k}a_{j}n_{j}(x)}
unde polinoamele Newton de bază sunt definite astfel:
n
j
(
x
)
:=
∏
i
=
0
j
−
1
(
x
−
x
i
)
{\displaystyle n_{j}(x):=\prod _{i=0}^{j-1}(x-x_{i})}
pentru
j
>
0
{\displaystyle j>0}
n
0
(
x
)
≡
1
{\displaystyle n_{0}(x)\equiv 1}
a
j
:=
[
y
0
,
…
,
y
j
]
{\displaystyle a_{j}:=[y_{0},\ldots ,y_{j}]}
unde
[
y
0
,
…
,
y
j
]
{\displaystyle [y_{0},\ldots ,y_{j}]}
sunt diferențele divizate.
Astfel, polinomul Newton poate fi scris ca:
N
(
x
)
=
[
y
0
]
+
[
y
0
,
y
1
]
(
x
−
x
0
)
+
⋯
+
[
y
0
,
…
,
y
k
]
(
x
−
x
0
)
(
x
−
x
1
)
⋯
(
x
−
x
k
−
1
)
.
{\displaystyle N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\cdots +[y_{0},\ldots ,y_{k}](x-x_{0})(x-x_{1})\cdots (x-x_{k-1}).}
"Polinomul Newton 'de mai sus poate fi exprimat într-o formă simplificată atunci când
x
0
,
x
1
,
…
,
x
k
{\displaystyle {x}_{0},{x}_{1},\dots ,{x}_{k}}
h
=
x
i
+
1
−
x
i
{\displaystyle \displaystyle {h}={x}_{{i}+{1}}-{x}_{i}}
i
=
0
,
1
,
…
,
k
−
1
{\displaystyle i=0,1,\dots ,k-1}
x
=
x
0
+
s
h
{\displaystyle \displaystyle x=x_{0}+sh}
x
−
x
i
{\displaystyle \displaystyle x-{x}_{i}}
(
s
−
i
)
h
{\displaystyle \displaystyle (s-i)h}
polinomul Newton" de mai sus devine:
N
(
x
)
=
[
y
0
]
+
[
y
0
,
y
1
]
s
h
+
⋯
+
[
y
0
,
…
,
y
k
]
s
(
s
−
1
)
⋯
(
s
−
k
+
1
)
h
k
{\displaystyle N(x)=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}}
=
∑
i
=
0
k
s
(
s
−
1
)
⋯
(
s
−
i
+
1
)
h
i
[
y
0
,
…
,
y
i
]
=
∑
i
=
0
k
(
s
i
)
i
!
h
i
[
y
0
,
…
,
y
i
]
{\displaystyle =\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}]}
N
(
x
)
=
∑
i
=
0
k
(
s
i
)
i
!
h
i
[
y
0
,
…
,
y
i
]
{\displaystyle N(x)=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}]}
se numește formula diferențelor divizate ale lui Newton".
În cazul în care nodurile sunt ordonate ca
x
k
,
x
k
−
1
,
…
,
x
0
{\displaystyle {x}_{k},{x}_{k-1},\dots ,{x}_{0}}
N
(
x
)
=
[
y
k
]
+
[
y
k
,
y
k
−
1
]
(
x
−
x
k
)
+
⋯
+
[
y
k
,
…
,
y
0
]
(
x
−
x
k
)
(
x
−
x
k
−
1
)
⋯
(
x
−
x
1
)
{\displaystyle N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1})}
Dacă
x
k
,
x
k
−
1
,
…
,
x
0
{\displaystyle {x}_{k},\;{x}_{k-1},\;\dots ,\;{x}_{0}}
x
k
+
s
h
{\displaystyle {x}_{k}+sh}
x
i
=
x
k
−
(
k
−
i
)
h
{\displaystyle {x}_{i}={x}_{k}-(k-i)h}
i
=
0
,
1
,
…
,
k
{\displaystyle i=0,\;1,\;\dots ,\;k}
N
(
x
)
=
[
y
k
]
+
[
y
k
,
y
k
−
1
]
s
h
+
⋯
+
[
y
k
,
…
,
y
0
]
s
(
s
+
1
)
⋯
(
s
+
k
−
1
)
h
k
=
∑
i
=
0
k
(
−
1
)
i
(
−
s
i
)
i
!
h
i
[
y
k
,
…
,
y
k
−
i
]
{\displaystyle N(x)=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}]}
N
(
x
)
=
∑
i
=
0
k
(
−
1
)
i
(
−
s
i
)
i
!
h
i
[
y
k
,
…
,
y
k
−
i
]
{\displaystyle N(x)=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}]}
se numește formula diferențelor divizate inversate ale lui Newton".
Diferențele divizate pot fi scrise în forma unui tabel. De exemplu, pentru o funcție
f
{\displaystyle f}
x
0
,
l
d
o
t
s
,
x
n
{\displaystyle x_{0},\ ldots,x_{n}}
x
0
f
(
x
0
)
f
(
x
1
)
−
f
(
x
0
)
x
1
−
x
0
x
1
f
(
x
1
)
f
(
x
2
)
−
f
(
x
1
)
x
2
−
x
1
−
f
(
x
1
)
−
f
(
x
0
)
x
1
−
x
0
x
2
−
x
0
f
(
x
2
)
−
f
(
x
1
)
x
2
−
x
1
x
2
f
(
x
2
)
⋮
⋮
⋮
⋮
⋮
x
n
f
(
x
n
)
{\displaystyle {\begin{matrix}x_{0}&f(x_{0})&&\\&&{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}}&\\x_{1}&f(x_{1})&&{{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}-{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}&\\x_{2}&f(x_{2})&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&f(x_{n})&&\\\end{matrix}}}
Atunci polinomul de interpolare este format ca mai sus folosind mențiunile cel mai de sus din fiecare coloană ca coeficienți.
De exemplu, să presupunem că trebuie să construim polinomul de interpolare pentru
f
(
x
)
=
tan
x
{\displaystyle f(x)=\tan {x}}
x
0
=
−
1.5
{\displaystyle x_{0}=-1.5}
x
1
=
−
0.75
{\displaystyle x_{1}=-0.75}
x
2
=
0
{\displaystyle x_{2}=0}
x
3
=
0.75
{\displaystyle x_{3}=0.75}
x
4
=
1.5
{\displaystyle x_{4}=1.5}
f
(
x
0
)
=
−
14.1014
{\displaystyle f(x_{0})=-14.1014}
f
(
x
1
)
=
−
0.931596
{\displaystyle f(x_{1})=-0.931596}
f
(
x
2
)
=
0
{\displaystyle f(x_{2})=0}
f
(
x
3
)
=
0.931596
{\displaystyle f(x_{3})=0.931596}
f
(
x
4
)
=
14.1014
{\displaystyle f(x_{4})=14.1014}
Pentru utilizarea unei precizii de 6 zecimale, vom construi tabelul
−
1.5
−
14.1014
17.5597
−
0.75
−
0.931596
−
10.8784
1.24213
4.83484
0
0
0
0
1.24213
4.83484
0.75
0.931596
10.8784
17.5597
1.5
14.1014
{\displaystyle {\begin{matrix}-1.5&-14.1014&&&&\\&&17.5597&&&\\-0.75&-0.931596&&-10.8784&&\\&&1.24213&&4.83484&\\0&0&&0&&0\\&&1.24213&&4.83484&\\0.75&0.931596&&10.8784&&\\&&17.5597&&&\\1.5&14.1014&&&&\\\end{matrix}}}
Astfel, polinomul de interpolare este:
−
14.1014
+
17.5597
(
x
+
1.5
)
−
10.8784
(
x
+
1.5
)
(
x
+
0.75
)
{\displaystyle \ -14.1014+17.5597(x+1.5)-10.8784(x+1.5)(x+0.75)}
+
4.83484
(
x
+
1.5
)
(
x
+
0.75
)
(
x
)
+
0
(
x
+
1.5
)
(
x
+
0.75
)
(
x
)
(
x
−
0.75
)
{\displaystyle \ +4.83484(x+1.5)(x+0.75)(x)+0(x+1.5)(x+0.75)(x)(x-0.75)}
=
−
0.00005
−
1.4775
x
−
0.00001
x
2
+
4.83484
x
3
{\displaystyle \ =-0.00005-1.4775x-0.00001x^{2}+4.83484x^{3}}
Având în vedere o acuratețe mai mare în tabel, coeficienții primul și al treilea vor fi egali cu zero.
Constantin Ilioi, Probleme de optimizare și algoritmi de aproximare a soluțiilor , Editura Academiei Republicii Socialiste România, București, 1980.
www.utgjiu.ro/math/mbuneci/book/mn2009.pdf/ Metode numerice - Aspecte teoretice și practice, Mădălina Roxana Buneci, Editura Academică Brâncuși, Târgu Jiu, 2009
http://cs.upm.ro/~bela.finta/.files/carti/Numerika.pdf Arhivat în 7 septembrie 2012 , la Wayback Machine .www.vpetrehus.home.ro/Lectii_AN.pdf/ Lecții de analiză numerică, Viorel Petrehus, Universitatea Tehnică de Construcții București, 2010 
![{\displaystyle a_{j}:=[y_{0},\ldots ,y_{j}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f40744c93b8380df3b93026cedb3e03e51e3dd2e)
![{\displaystyle [y_{0},\ldots ,y_{j}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e845258d4c5470e5c7fdfdaab88ea5e9734aaf16)
![{\displaystyle N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\cdots +[y_{0},\ldots ,y_{k}](x-x_{0})(x-x_{1})\cdots (x-x_{k-1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b68037ee2fd3c52e2f564605fcd6308048dee2f1)
![{\displaystyle N(x)=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d443d9b9c6081eb13800ab0c70327b133bfaae28)
![{\displaystyle =\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dc163936635374da27013d604a0d5b4655854a1)
![{\displaystyle N(x)=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4e7ac1dcbc80cb99cb98a304dfe355eca5ce970)
![{\displaystyle N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0920f11e9b22550334ffcfa07157b8861597792)
![{\displaystyle N(x)=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aebc8b1a8616e74ec2bbe2c98a0fed19d716bd1a)
![{\displaystyle N(x)=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3830a746770ffb0ff544d9c96f800e535d7b649e)
