Diferențe divizate
În analiză numerică , diferențele divizate reprezintă un algoritm recursiv folosit pentru a calcula coeficienții unui polinom de interpolare în forma Newton .
Având în vedere k+1 puncte de date
(
x
0
,
y
0
)
,
… … -->
,
(
x
k
,
y
k
)
{\displaystyle (x_{0},y_{0}),\ldots ,(x_{k},y_{k})}
Diferențele divizate înainte sunt definite ca:
[
y
ν ν -->
]
:=
y
ν ν -->
,
ν ν -->
∈ ∈ -->
{
0
,
… … -->
,
k
}
{\displaystyle [y_{\nu }]:=y_{\nu },\qquad \nu \in \{0,\ldots ,k\}}
[
y
ν ν -->
,
… … -->
,
y
ν ν -->
+
j
]
:=
[
y
ν ν -->
+
1
,
… … -->
,
y
ν ν -->
+
j
]
− − -->
[
y
ν ν -->
,
… … -->
,
y
ν ν -->
+
j
− − -->
1
]
x
ν ν -->
+
j
− − -->
x
ν ν -->
,
ν ν -->
∈ ∈ -->
{
0
,
… … -->
,
k
− − -->
j
}
,
j
∈ ∈ -->
{
1
,
… … -->
,
k
}
.
{\displaystyle [y_{\nu },\ldots ,y_{\nu +j}]:={\frac {[y_{\nu +1},\ldots ,y_{\nu +j}]-[y_{\nu },\ldots ,y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}},\qquad \nu \in \{0,\ldots ,k-j\},\ j\in \{1,\ldots ,k\}.}
Diferențele divizate înapoi sunt definite ca:
[
y
ν ν -->
]
:=
y
ν ν -->
,
ν ν -->
∈ ∈ -->
{
0
,
… … -->
,
k
}
{\displaystyle [y_{\nu }]:=y_{\nu },\qquad \nu \in \{0,\ldots ,k\}}
[
y
ν ν -->
,
… … -->
,
y
ν ν -->
− − -->
j
]
:=
[
y
ν ν -->
,
… … -->
,
y
ν ν -->
− − -->
j
+
1
]
− − -->
[
y
ν ν -->
− − -->
1
,
… … -->
,
y
ν ν -->
− − -->
j
]
x
ν ν -->
− − -->
x
ν ν -->
− − -->
j
,
ν ν -->
∈ ∈ -->
{
j
,
… … -->
,
k
}
,
j
∈ ∈ -->
{
1
,
… … -->
,
k
}
.
{\displaystyle [y_{\nu },\ldots ,y_{\nu -j}]:={\frac {[y_{\nu },\ldots ,y_{\nu -j+1}]-[y_{\nu -1},\ldots ,y_{\nu -j}]}{x_{\nu }-x_{\nu -j}}},\qquad \nu \in \{j,\ldots ,k\},\ j\in \{1,\ldots ,k\}.}
În continuare sunt prezentate diferențele divizate înainte, cele mai utilizate în practică. Pentru diferențele divizate înapoi, raționamentul este asemănător.
Dacă punctele de date sunt valorile unei funcții ƒ ,
(
x
0
,
f
(
x
0
)
)
,
… … -->
,
(
x
k
,
f
(
x
k
)
)
{\displaystyle (x_{0},f(x_{0})),\ldots ,(x_{k},f(x_{k}))}
uneori se scrie
f
[
x
ν ν -->
]
:=
f
(
x
ν ν -->
)
,
ν ν -->
∈ ∈ -->
{
0
,
… … -->
,
k
}
{\displaystyle f[x_{\nu }]:=f(x_{\nu }),\qquad \nu \in \{0,\ldots ,k\}}
f
[
x
ν ν -->
,
… … -->
,
x
ν ν -->
+
j
]
:=
f
[
x
ν ν -->
+
1
,
… … -->
,
x
ν ν -->
+
j
]
− − -->
f
[
x
ν ν -->
,
… … -->
,
x
ν ν -->
+
j
− − -->
1
]
x
ν ν -->
+
j
− − -->
x
ν ν -->
,
ν ν -->
∈ ∈ -->
{
0
,
… … -->
,
k
− − -->
j
}
,
j
∈ ∈ -->
{
1
,
… … -->
,
k
}
.
{\displaystyle f[x_{\nu },\ldots ,x_{\nu +j}]:={\frac {f[x_{\nu +1},\ldots ,x_{\nu +j}]-f[x_{\nu },\ldots ,x_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}},\qquad \nu \in \{0,\ldots ,k-j\},\ j\in \{1,\ldots ,k\}.}
Câteva notații pentru diferența divizată a funcției f pe nodurile 'x0 , ..., sunt următoarele:
[
x
0
,
… … -->
,
x
n
]
f
,
{\displaystyle [x_{0},\ldots ,x_{n}]f,}
[
x
0
,
… … -->
,
x
n
;
f
]
,
{\displaystyle [x_{0},\ldots ,x_{n};f],}
D
[
x
0
,
… … -->
,
x
n
]
f
{\displaystyle D[x_{0},\ldots ,x_{n}]f}
etc
Exemplu
Pentru primele valori ale
ν ν -->
{\displaystyle \nu }
[
y
0
]
=
y
0
[
y
0
,
y
1
]
=
y
1
− − -->
y
0
x
1
− − -->
x
0
[
y
0
,
y
1
,
y
2
]
=
[
y
1
,
y
2
]
− − -->
[
y
0
,
y
1
]
x
2
− − -->
x
0
=
y
2
− − -->
y
1
x
2
− − -->
x
1
− − -->
y
1
− − -->
y
0
x
1
− − -->
x
0
x
2
− − -->
x
0
=
y
2
− − -->
y
1
(
x
2
− − -->
x
1
)
(
x
2
− − -->
x
0
)
− − -->
y
1
− − -->
y
0
(
x
1
− − -->
x
0
)
(
x
2
− − -->
x
0
)
[
y
0
,
y
1
,
y
2
,
y
3
]
=
[
y
1
,
y
2
,
y
3
]
− − -->
[
y
0
,
y
1
,
y
2
]
x
3
− − -->
x
0
{\displaystyle {\begin{aligned}{\mathopen {[}}y_{0}]&=y_{0}\\{\mathopen {[}}y_{0},y_{1}]&={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\{\mathopen {[}}y_{0},y_{1},y_{2}]&={\frac {{\mathopen {[}}y_{1},y_{2}]-{\mathopen {[}}y_{0},y_{1}]}{x_{2}-x_{0}}}={\frac {{\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}-{\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}}{x_{2}-x_{0}}}={\frac {y_{2}-y_{1}}{(x_{2}-x_{1})(x_{2}-x_{0})}}-{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})(x_{2}-x_{0})}}\\{\mathopen {[}}y_{0},y_{1},y_{2},y_{3}]&={\frac {{\mathopen {[}}y_{1},y_{2},y_{3}]-{\mathopen {[}}y_{0},y_{1},y_{2}]}{x_{3}-x_{0}}}\end{aligned}}}
Pentru a face procesul recursiv mai clar diferentele divizate pot fi puse într-o formă de tabel
x
0
y
0
=
[
y
0
]
[
y
0
,
y
1
]
x
1
y
1
=
[
y
1
]
[
y
0
,
y
1
,
y
2
]
[
y
1
,
y
2
]
[
y
0
,
y
1
,
y
2
,
y
3
]
x
2
y
2
=
[
y
2
]
[
y
1
,
y
2
,
y
3
]
[
y
2
,
y
3
]
x
3
y
3
=
[
y
3
]
{\displaystyle {\begin{matrix}x_{0}&y_{0}=[y_{0}]&&&\\&&[y_{0},y_{1}]&&\\x_{1}&y_{1}=[y_{1}]&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&y_{2}=[y_{2}]&&[y_{1},y_{2},y_{3}]&\\&&[y_{2},y_{3}]&&\\x_{3}&y_{3}=[y_{3}]&&&\\\end{matrix}}}
(
f
+
g
)
[
x
0
,
… … -->
,
x
n
]
=
f
[
x
0
,
… … -->
,
x
n
]
+
g
[
x
0
,
… … -->
,
x
n
]
{\displaystyle (f+g)[x_{0},\dots ,x_{n}]=f[x_{0},\dots ,x_{n}]+g[x_{0},\dots ,x_{n}]}
(
λ λ -->
⋅ ⋅ -->
f
)
[
x
0
,
… … -->
,
x
n
]
=
λ λ -->
⋅ ⋅ -->
f
[
x
0
,
… … -->
,
x
n
]
{\displaystyle (\lambda \cdot f)[x_{0},\dots ,x_{n}]=\lambda \cdot f[x_{0},\dots ,x_{n}]}
(
f
⋅ ⋅ -->
g
)
[
x
0
,
… … -->
,
x
n
]
=
f
[
x
0
]
⋅ ⋅ -->
g
[
x
0
,
… … -->
,
x
n
]
+
f
[
x
0
,
x
1
]
⋅ ⋅ -->
g
[
x
1
,
… … -->
,
x
n
]
+
⋯ ⋯ -->
+
f
[
x
0
,
… … -->
,
x
n
]
⋅ ⋅ -->
g
[
x
n
]
{\displaystyle (f\cdot g)[x_{0},\dots ,x_{n}]=f[x_{0}]\cdot g[x_{0},\dots ,x_{n}]+f[x_{0},x_{1}]\cdot g[x_{1},\dots ,x_{n}]+\dots +f[x_{0},\dots ,x_{n}]\cdot g[x_{n}]}
Din teorema valorii intermediare, rezultă că
lim
(
x
0
,
… … -->
,
x
n
)
→ → -->
(
ξ ξ -->
,
… … -->
,
ξ ξ -->
)
f
[
x
0
,
… … -->
,
x
n
]
=
f
(
n
)
(
ξ ξ -->
)
n
!
{\displaystyle \lim _{(x_{0},\dots ,x_{n})\to (\xi ,\dots ,\xi )}f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}}
[
x
0
,
… … -->
,
x
n
]
f
{\displaystyle [x_{0},\ldots ,x_{n}]f}
∑ ∑ -->
i
=
0
n
f
(
x
i
)
∏ ∏ -->
j
=
0
,
j
≠ ≠ -->
i
n
(
x
i
− − -->
x
j
)
{\displaystyle \sum _{i=0}^{n}{\frac {f(x_{i})}{\prod _{j=0,j\neq i}^{n}(x_{i}-x_{j})}}}
Pentru n=1, evident. Pentru n>1, demonstrația se continuă aplicând inducția matematică.
Tot prin inducție matematică , știind că orice permutare se poate reprezenta ca un produs de transpoziții, se demonstrează că:
[
x
0
,
… … -->
,
x
n
]
f
,
{\displaystyle [x_{0},\ldots ,x_{n}]f,}
x
0
{\displaystyle x_{0}}
x
n
{\displaystyle x_{n}}
Bibliografie
Dan Larionescu, Metode numerice , Editura Tehnică, 1989, p 77-80
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 [y_{\nu }]:=y_{\nu },\qquad \nu \in \{0,\ldots ,k\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0b559f584afa31efe09d04b4be0e091807e66c6)
![{\displaystyle [y_{\nu },\ldots ,y_{\nu +j}]:={\frac {[y_{\nu +1},\ldots ,y_{\nu +j}]-[y_{\nu },\ldots ,y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}},\qquad \nu \in \{0,\ldots ,k-j\},\ j\in \{1,\ldots ,k\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3fbf429b65bad77486a9d90314d4af6e5edf0c1)
![{\displaystyle [y_{\nu },\ldots ,y_{\nu -j}]:={\frac {[y_{\nu },\ldots ,y_{\nu -j+1}]-[y_{\nu -1},\ldots ,y_{\nu -j}]}{x_{\nu }-x_{\nu -j}}},\qquad \nu \in \{j,\ldots ,k\},\ j\in \{1,\ldots ,k\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9ca4b8abdebfbfaf509c340f8aa07f1508e8c8b)
![{\displaystyle f[x_{\nu }]:=f(x_{\nu }),\qquad \nu \in \{0,\ldots ,k\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d88b6aba15e3cd2f79af1376a2d5e9b1df1c416)
![{\displaystyle f[x_{\nu },\ldots ,x_{\nu +j}]:={\frac {f[x_{\nu +1},\ldots ,x_{\nu +j}]-f[x_{\nu },\ldots ,x_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}},\qquad \nu \in \{0,\ldots ,k-j\},\ j\in \{1,\ldots ,k\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/424ee9e0456399b61b1ed8c66e90ca761fa7dc3e)
![{\displaystyle [x_{0},\ldots ,x_{n}]f,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52676412ab23500b8def307e74643ea7146220fe)
![{\displaystyle [x_{0},\ldots ,x_{n};f],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a0edff404a8cd6ec5f52354e4988a9dfe8badce)
![{\displaystyle D[x_{0},\ldots ,x_{n}]f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/025c36fb7047d8abf731cb19957cca1f7bd2b23a)
![{\displaystyle {\begin{aligned}{\mathopen {[}}y_{0}]&=y_{0}\\{\mathopen {[}}y_{0},y_{1}]&={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\{\mathopen {[}}y_{0},y_{1},y_{2}]&={\frac {{\mathopen {[}}y_{1},y_{2}]-{\mathopen {[}}y_{0},y_{1}]}{x_{2}-x_{0}}}={\frac {{\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}-{\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}}{x_{2}-x_{0}}}={\frac {y_{2}-y_{1}}{(x_{2}-x_{1})(x_{2}-x_{0})}}-{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})(x_{2}-x_{0})}}\\{\mathopen {[}}y_{0},y_{1},y_{2},y_{3}]&={\frac {{\mathopen {[}}y_{1},y_{2},y_{3}]-{\mathopen {[}}y_{0},y_{1},y_{2}]}{x_{3}-x_{0}}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7c5a021041c0405a351383f2e34f0de88e4e58b)
![{\displaystyle {\begin{matrix}x_{0}&y_{0}=[y_{0}]&&&\\&&[y_{0},y_{1}]&&\\x_{1}&y_{1}=[y_{1}]&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&y_{2}=[y_{2}]&&[y_{1},y_{2},y_{3}]&\\&&[y_{2},y_{3}]&&\\x_{3}&y_{3}=[y_{3}]&&&\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d60ef92b00038923edcedaecccbadd25373b07c1)
![{\displaystyle (f+g)[x_{0},\dots ,x_{n}]=f[x_{0},\dots ,x_{n}]+g[x_{0},\dots ,x_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9f98450062d604d6056db6fed7a9294708084a8)
![{\displaystyle (\lambda \cdot f)[x_{0},\dots ,x_{n}]=\lambda \cdot f[x_{0},\dots ,x_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5285d5f07af1a864344dc27d700002afb4e4e82e)
![{\displaystyle (f\cdot g)[x_{0},\dots ,x_{n}]=f[x_{0}]\cdot g[x_{0},\dots ,x_{n}]+f[x_{0},x_{1}]\cdot g[x_{1},\dots ,x_{n}]+\dots +f[x_{0},\dots ,x_{n}]\cdot g[x_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/534095e5ec06e0a714829f32de106d9c65c62b9e)
![{\displaystyle \lim _{(x_{0},\dots ,x_{n})\to (\xi ,\dots ,\xi )}f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e49173eb38e27d576bf6ecc75d2552d68067a8fe)
![{\displaystyle [x_{0},\ldots ,x_{n}]f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1926ec7f558f45434e01fb33edddef040251026)
