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.

Definiție

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 ne vom referi la diferențele divizate înainte, cele mai utilizate în practică. Pentru diferențele divizate înapoi, raționamentul este asemănător.

Observații

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, ..., xn 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}}}

Proprietăți

  • Liniaritate
( 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}]}
  • Regula Leibniz
( 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,} nu depinde de ordinea punctelor 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 , 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