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),\dots ,(x_k,y_k)$

Diferențele divizate înainte sunt definite ca:

$[y_{\nu }]:=y_{\nu },\nu \in \{0,\dots ,k\}$

$[y_{\nu },\dots ,y_{\nu +j}]:=\frac{[y_{\nu +1},\dots ,y_{\nu +j}]-[y_{\nu },\dots ,y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }},\nu \in \{0,\dots ,k-j\},j\in \{1,\dots ,k\}.$

Diferențele divizate înapoi sunt definite ca:

$[y_{\nu }]:=y_{\nu },\nu \in \{0,\dots ,k\}$

$[y_{\nu },\dots ,y_{\nu -j}]:=\frac{[y_{\nu },\dots ,y_{\nu -j+1}]-[y_{\nu -1},\dots ,y_{\nu -j}]}{x_{\nu }-x_{\nu -j}},\nu \in \{j,\dots ,k\},j\in \{1,\dots ,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.

Observații

Dacă punctele de date sunt valorile unei funcții ƒ,

$(x_0,f(x_0)),\dots ,(x_k,f(x_k))$

uneori se scrie

$f[x_{\nu }]:=f(x_{\nu }),\nu \in \{0,\dots ,k\}$

$f[x_{\nu },\dots ,x_{\nu +j}]:=\frac{f[x_{\nu +1},\dots ,x_{\nu +j}]-f[x_{\nu },\dots ,x_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }},\nu \in \{0,\dots ,k-j\},j\in \{1,\dots ,k\}.$

Câteva notații pentru diferența divizată a funcției f pe nodurile 'x₀, ..., xn sunt următoarele:

$[x_0,\dots ,x_n]f,$

$[x_0,\dots ,x_n;f],$

$D[x_0,\dots ,x_n]f$

etc

Exemplu

Pentru primele valori ale $\nu$

$\begin{array}{cc}[y_0]& =y_0\\ [y_0,y_1]& =\frac{y_1-y_0}{x_1-x_0}\\ [y_0,y_1,y_2]& =\frac{[y_1,y_2]-[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)}\\ [y_0,y_1,y_2,y_3]& =\frac{[y_1,y_2,y_3]-[y_0,y_1,y_2]}{x_3-x_0}\end{array}$

Pentru a face procesul recursiv mai clar diferentele divizate pot fi puse într-o formă de tabel

$\begin{array}{ccccc}{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{array}$

Proprietăți

• Liniaritate

$(f+g)[x_0,\dots ,x_n]=f[x_0,\dots ,x_n]+g[x_0,\dots ,x_n]$

$(\lambda \cdot f)[x_0,\dots ,x_n]=\lambda \cdot f[x_0,\dots ,x_n]$

• Regula Leibniz

$(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ă

$\underset{(x_0,\dots ,x_n)\to (\xi ,\dots ,\xi )}{\lim }f[x_0,\dots ,x_n]=\frac{f^{(n)}(\xi )}{n!}$

• $[x_0,\dots ,x_n]f$ = $\sum _{i=0}^n\frac{f(x_i)}{\prod _{j=0,j\ne 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,\dots ,x_n]f,$ nu depinde de ordinea punctelor $x_0$, ..., $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 Format:Webarchive
• www.vpetrehus.home.ro/Lectii_AN.pdf/ Lecții de analiză numerică, Viorel Petrehus, Universitatea Tehnică de Construcții București, 2010