Evaluarea erorilor de calcul în interpolarea prin polinoame

EVALUAREA ERORILOR DE CALCUL IN INTERPOLAREA PRIN POLINOAME

de

T. POPOVICIU

Membru al Academiei R. P. R.
(Cluj)

1.

Utilizarea practică a formulei de interpolare a lui Lagrange

f(x)\approx L\left(x_{1},x_{2},\ldots,x_{n+1};f\mid x\right),

(1)

unde în membrul al doilea avem polinomul lui Lagrange de gradul $n$ care ia valorile funcţiei $f(x)$ pe nodurile (distincte) de interpolare $x_{i}(i=1,2,\ldots$ , $n+1$ ), depinde în mare măsură de forma sub care este pus acest polinom. Acest lucru este mai cu seamă important atunci cînd este vorba de calculul efectiv al valorilor polinomului pentru diferitele valori ale variabilei $x$ . Aici ne ocupăm numai de cazul cînd variabila $x$ şi funcţia $f(x)$ sînt reale. În acest caz, pentru aflarea valorii polinomului trebuie efectuate un număr finit de operații elementare de adunare, scădere, înmulțire și împărțire asupra unor numere reale, deobicei fracti zecimale limitate, și într-o ordine determinată. Forma sub care se pune polinomul lui Lagrange este în legătură tocmai cu aceasta ordine a operaților. In ceea ce privește operaţiile, ele se execută, pe baza unor procedee cunoscute, direct sau cu maşina, şi care în mod practic revin la determinarea succesivă a cifrelor zecimale ale rezultatului fiecărui calcul parțial, exact sau aproximativ, în parte.

Procedeul de calcul întrebuințat comportă erori inerente datorită faptului că calculele succesive se fac cu aproximaţie, de exemplu din cauza limitării la un anumit număr de zecimale ale rezultatelor parțiale obținute. Aceste erori se reflectă asupra rezultatului final, determinînd o corecție care, în problema de interpolare considerată, va trebui adăugată la corecţiile determinate de erorile de care sînt afectate datele problemei.

Vom presupune întîi că nodurile nu sînt neapărat echidistante şi ne vom ocupa de calculul membrului al doilea al formulei (1) pentru $x=x_{0}$ , cu ajutorul formulei lui Newton

L\left(x_{1},x_{2},\ldots,x_{n+1};f\mid x_{0}\right)=\sum_{i=0}^{n}\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right)\ldots\left(x_{0}-x_{i}\right)D_{1}^{i},*;

(2)

unde coeficienții $D_{i}^{j},(i=0,1,\ldots,n)$ , se obțin din tabloul 1 al diferențelor divizate în care avem în general

D_{i}^{j}=D_{i}^{j}[f]=\left[\begin{array}[]{cccc}x_{i},&x_{i+1},&\ldots,&x_{i+j};f\end{array}\right],D_{i}^{0}=f_{i}=f\left(x_{i}\right),

folosind notatiile obişnuite pentru diferențele divizate ale functiei $f(x)$ .
Formarea tabloului 1 al diferentelor divizate se face calculînd succesiv coloanele cu ajutorul formulei de recurență

	$\displaystyle D_{i}^{j}[f]=\frac{D_{i+1}^{j-1}[f]-D_{i}^{j-1}[f]}{x_{i+j}-x_{i}}\quad\left(D_{i}^{0}[f]=f_{i}\right)$		(4)
	$\displaystyle(i=1,2,\ldots,n+1-j;\quad j=1,2,\ldots,n).$

Se vede că acest calcul necesită împărțiri (cu diferențe de noduri) din care cauză, în general, diferențele divizate nu se pot calcula, de exemplu, sub forma practică de fracții zecimale limitate, decît cu o anumită aproximație, chiar dacă nodurile și valorile funcției pe aceste noduri sînt date sub această formă.

Table 1: Tabloul 1

$x$	$f(x)$	$D^{1}$	$D^{2}$	$D^{3}$	. . .	$D^{n}$
$x_{1}$	$f_{1}$
		$D_{1}^{1}$
$x_{2}$	$f_{2}$		$D_{1}^{2}$
$x_{3}$	$f_{3}$	$D_{2}^{1}$	$D_{2}^{2}$	$D_{1}^{3}$
$\vdots$	$\vdots$	$\vdots$			$D_{2}^{n-1}$	$D_{1}^{n}$
$x_{n-1}$	$f_{n-1}$		$D_{n-2}^{2}$
		$D_{n-1}^{1}$		$D_{*-2}^{3}$
$x_{n}$	$t_{n}$		$D_{n-1}^{2}$
$x_{n+1}$	$f_{n+1}$	$D_{n}^{1}$

⁰⁰footnotetext: *) Pentru

i=0

termenul corespunzător al sumei se reduce la

D_{i}^{0}

. O convenție analoagă

Dacă însă elementele tabloului 1 se calculează aproximativ, erorile comise se transpun asupra polinomului de interpolare.

Pe de altă parte, înmulțirile care intervin în calculul valorii polinomului de interpolare se fac de asemenea cu erori. In cele ce urmează ne propunem să examinăm pe rînd efectul acestor două feluri de erori, care se suprapun. Pentru simplificare vom presupune că nodurile și punctul $x_{0}$ , unde se interpolează, nu sînt afectate de erori.
2. Ne ocupăm în primul rînd de efectul erorilor ce apar la calculul diferențelor divizate, presupunînd că înmulțirile indicate în formula (2) se fac exact.

Coloanele tabloului 1 se calculează succesiv cu anumite aproximații.
Fie $\widetilde{f}_{i},(i=1,2,\ldots,n+1)$ , niște valori aproximative ale valorilor funcției pe noduri, $c_{i}^{(0)},(i=1,2,\ldots,n+1)$ , corecţiile respective, deci $f_{i}=\tilde{,}_{i}+c_{i}^{(0)},(i=1,2,\ldots,n+1)$ . Fie apoi, in general, $\widetilde{D}_{i}^{j}=\widetilde{D}_{i}^{j}[f]$ , $(i=1,2,\ldots,n+1-j)$ , valorile aproximative ale elementelor coloanei $j$ , calculate cu ajutorul elementelor deja calculate ale coloanei $j-1$ și $c_{i}^{(j)},(i=1,2,\ldots,n+1-j)$ , corecțiile respective. Vom avea atunci

	$\displaystyle\widetilde{D}_{i}^{j}+c_{i}^{(j)}=$	$\displaystyle\frac{\widetilde{D}_{i+1}^{j-1}-\widetilde{D}_{i}^{j-1}}{x_{i+j}-x_{i}}\left(\widetilde{D}_{i}^{0}=\widetilde{f}_{i}\right)$		(5)
		$\displaystyle(i=1,2,\ldots,n+1-j,\quad j=1,2,$		( $.,n)$ )

Tabloul 1 al diferentelor divizate se înlocuiește atunci cu tabloul 2 al valorilor aproximative calculate ale diferentelor divizate.

Table 2: Tabloul 2

$x$	$\widetilde{f}(x)$	$\widetilde{D}^{1}$	$\widetilde{D}^{2}$	$\widetilde{D}^{3}$	$\widetilde{D}^{n-1}$	$\widetilde{D}^{n}$
$x_{1}$	$\widetilde{f}_{1}$	$\widetilde{D}_{1}^{1}$
$x_{2}$	$f_{2}$		$\widetilde{D}_{1}^{2}$
		$\widetilde{D}_{2}^{1}$		$\widetilde{D}_{1}^{3}$
$x_{3}$	$\widetilde{f_{3}}$		$\widetilde{D}_{2}^{2}$		$\widetilde{D}_{1}^{n-1}$
$\vdots$ $x_{n-1}$	$\vdots\begin{gathered}\vdots\\ \tilde{f}_{n-1}\end{gathered}$	$\vdots$	$\vdots$	$\vdots$	$\widetilde{D}_{2}^{n-1}$	$\widetilde{D}_{1}^{n}$
$x_{n-1}$	$\dot{\tilde{f}}_{n-1}$		$\widetilde{D}_{n-2}^{2}$
$x_{n}$	$\widetilde{f}_{n}$	$\widetilde{D}_{n-1}^{1}$	$\widetilde{D}_{n-1}^{2}$	$\widetilde{D}_{n-2}^{3}$
$x_{n+1}$	$\widetilde{f}_{n+1}$	$\widetilde{D}_{n}^{1}$

O valoare aproximativă $\widetilde{L}$ a expresiei (2) se obţine atunci cu ajutorul tabloului 2 cu formula

\widetilde{L}=\sum_{i=0}^{n}\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right)\cdots\left(x_{0}-x_{i}\right)\widetilde{D}_{1}^{i}

(6)

şi vom avea

L\left(x_{1},x_{2},\ldots,x_{n+1};f\mid x_{0}\right)=\widetilde{L}+\lambda

(7)

$\lambda$ fiind corecţia respectivă.
In vederea delimitării corecţiei $\lambda$ se introduc funcţionalele liniare $D_{i}^{j,k}[f]$ , definite astfel $(k<n)$ :

D_{i}^{j,k}[f]=\frac{D_{i+1}^{j-1,k}[f]-D_{i}^{j-1,k}[f]}{x_{i+j+k}-x_{i}},

(8)

pentru $j=1,2,\ldots,n-k,i=1,2,\ldots,n+1-k-j$ şi

D_{i}^{0,k}[f]=f_{i},

(9)

pentru $i=1,2,\ldots,n+1-k$ . In lucrarea [1] se stabileşte formula

D_{i}^{j,k}[f]=D_{i}^{r,k+j-r}\left[D_{i}^{j-1,k}[f]\right]\quad(0\leqslant r\leqslant j),

(10)

care se mai scrie simbolic

D^{\alpha+\beta,k}=D^{\alpha,\beta+k}D^{\beta,k}

Notația folosită se bazează pe observația că orice şir de $n+1$ numere $\varphi_{1},\varphi_{2},\ldots,\varphi_{n+1}$ poate fi considerat ca fiind format de valorile $\varphi_{i}=\varphi\left(x_{i}\right)$ ,
$=1,2,\ldots,n+1$ ale unei funcții $\varphi(x)$ , definite pe nodurile $x_{1},x_{2},\ldots,x_{n+1}$ .
Ținînd seama de formula (10) s-a obținut în lucrarea citată următoarea expresie pentru corectia $\lambda$ :

\lambda=\sum_{i=0}^{n}\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right)\ldots\left(x_{0}-x_{i}\right)\left[\sum_{r=0}^{i}D_{1}^{r_{1},i-r}\left[c^{(i-r)}\right]\right].

(11)

Pentru a delimita corecția $\lambda$ avem nevoie de o delimitare convenabilă pentru $D_{i}^{j,k}[f]$ .

Diferența divizată $D_{1}^{n}=\left[x_{1},x_{2},\ldots,x_{n+1};f\right]$ se delimitează uşor ținînd seama de formula binecunoscută

\left[x_{1},x_{2},\ldots,x_{n+1};f\right]=\sum_{i=1}^{n+1}\frac{f_{i}}{l^{\prime}\left(x_{i}\right)},

unde $l(x)=\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{n+1}\right)$ . Avem

\left|D_{1}^{n}\right|\leqslant N\left(x_{1},x_{2},\ldots,x_{n+1}\right)M,

unde

N\left(x_{1},x_{2},\ldots,x_{n+1}\right)=\sum_{i=1}^{n+1}\frac{1}{\left|l^{\prime}\left(x_{i}\right)\right|}

(12)

şi $M=\max_{i=1,2,\ldots,n+1}\left(\left|f_{i}\right|\right)$ .
O delimitare analoagă a lui $D_{1}^{n-k,h}[f]$ se poate scrie

\left|D_{1}^{n-k,k}[f]\right|\leqslant N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)M

(13)

unde, de altfel, $M$ se poate înlocui $\mathrm{cu}\underset{i=1,2,\ldots,n+1-k}{\max}\left(\left|f_{i}\right|\right)$ .
În formula (13) avem

N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=\sup_{\begin{subarray}{c}i=1,2,\ldots,n+1-k\\ |fi|\leq 1\end{subarray}}\left|D_{1}^{n-k,k}\left[f_{i}\right]\right|.

şi deci

N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=D_{1}^{n-k,k}[f]

cu condiția să alegem toate numerele $f_{i},i=1,2,\ldots,n+1-k$ , egale cu 1 sau -1 , în mod convenabil.

Avem

N_{0}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=N\left(x_{1},x_{2},\ldots,x_{n+1}\right)

membrul al doilea fiind dat de (12). Pentru $k>0$ , expresia lui $N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)$ este însă mai complicată.

În formarea lui $D_{1}^{n-k,k}[t]$ intervin efectiv numai nodurile $x_{i}$ pentru $i=1,2,\ldots,n-k,k+2,k+3,\ldots,n+1$ . Dacă deci $2k\leqslant n-1$ , vor interveni toate nodurile. Dacă însă $2k>n-1$ nu vor interveni decît primele $n-k$ și ultimele $n-k$ dintre nodurile $x_{1},x_{2},\ldots,x_{n+1}$ . Deducem de aici următoarea formulă:

N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=N_{n-k-1}\left(x_{1},x_{2},\ldots,x_{n-k},x_{k+2},x_{k+3},\ldots,x_{n+1}\right)

(14)

dacă $2k>n-1$ . Este suficient să presupunem $k<n$ , deoarece avem evident

N_{n}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=1

(15)

In cazul particular

x_{1}<x_{2}<\ldots<x_{n+1}

(16)

se arată că are loc formula

N_{k}\left(x_{1},x_{2},\ldots,x_{j+k+1}\right)=\frac{N_{k}\left(x_{1},x_{2},\ldots,x_{j+k}\right)+N_{k}\left(x_{2},x_{3},\ldots,x_{j+k+1}\right)}{x_{k+k+1}-x_{1}}

(17)

15 - Studii și cercetări de matematică (Cluj), anexă/1961-1962

Formulele (14), (15), (17) determină complet pe $N_{k}\left(x_{1},x_{2},\ldots,x_{i}\right)$ şi avem

\left|D_{i}^{j,k}[f]\right|\leqslant N_{k}\left(x_{i},x_{i+1},\ldots,x_{i+j+k}\right)M

unde $M=\max_{r=i,i+1,\ldots,i+j}\left(\left|f_{r}\right|\right)$ .
În particular, dacă toate corectiile $c_{i}^{(j)}$ rămîn, în valoare absolută cel mult egale cu $\varepsilon$ , pe baza formulei (15) avem

\left|D_{1}^{r,i-r}\left[c^{(i-r)}\right]\right|\leqslant N_{i-r}\left(x_{1},x_{2},\ldots,x_{i+1}\right)\varepsilon

şi putem scrie

|\lambda|\leqslant V\left(x_{0}\right)\varepsilon

((18)

unde

	$\displaystyle V(x)$	$\displaystyle=\sum_{i=1}^{n}\left\|\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{i}\right)\right\|\times$
		$\displaystyle\times\left[\sum_{r=0}^{i}N_{i-r}\left(x_{1},x_{2},\ldots,x_{i+1}\right)\right].$		(19)

Cînd valorile funcţiei sînt exacte, deci cînd $c_{i}^{0}=0,i=1,2,\ldots,n+1$ . se poate lua chiar

	$\displaystyle V(x)$	$\displaystyle=\sum_{i=1}^{n}\left\|\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{i}\right)\right\|\times$
		$\displaystyle\times\left[\sum_{r=0}^{i-1}N_{i-r}\left(x_{1},x_{2},\ldots,x_{i+1}\right)\right].$		(20)

3.

Ne vom ocupa în continuare de efectul erorilor ce provin de la înmulţirile indicate în formula (2), presupunînd că diferențele divizate $D_{1}^{i}$ care intervin în această formulă sînt calculate exact. Pentru aceasta sînt necesare anumite consideraţii teoretice asupra formulei de interpolare (1).

La orice permutare

x_{v_{1}},x_{v_{2}},\ldots,x_{v_{s+1}}

(21)

a nodurilor

x_{1},x_{2},\ldots,x_{n+1}

(22)

va corespunde o formulă de interpolare de forma

	$\displaystyle f(x)$	$\displaystyle=\sum_{i=0}^{n}\left(x-x_{v_{1}}\right)\left(x-x_{v_{1}}\right)\ldots\left(x-x_{v_{i}}\right)\times$
		$\displaystyle\times\left[x_{v_{1}},x_{v_{2}},\ldots,x_{v_{i+1}};f\right]+R(x)$		(23)

Bineînțeles că restul $R(x)$ nu depinde de permutarea considerată și se poate scrie

R(x)=l(x)\left[x,x_{1},x_{2},\ldots,x_{n+1};f\right]

(24)

,unde

l(x)=\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{n+1}\right)

(25)

Utilizarea practică a formulei de interpolare (23) va depinde de rapiditatea și exactitatea calculului coeficienţilor

\left[x_{v_{1}},x_{v_{2}},\ldots x_{v_{i+1}};f\right],i=0,1,\ldots,n

(26)

ai acestei formule.
Aceşti coeficienți se vor găsi pe latura superioară (descendentă) a tabloului de diferențe divizate corespunzător nodurilor luate în ordinea (21). Însă, pentru formarea acestui tablou, va fi avantajos ca nodurile (21) să fie aşezate în ordinea crescătoare a valorilor lor numerice, căci atunci toate împărțirile ce se fac cu diferențe de noduri în vederea formării tabloului, se fac cu numere pozitive. In felul acesta sînt eliminate erorile care ar putea proveni din neatenție la semnele diferențelor de noduri.

Pentru simplificarea notatiilor, să presupunem că nodurile, pe care le considerăm distincte, sînt luate în ordinea crescătoare, deci că

x_{1}<x_{2}<\ldots<x_{n+1}

Atunci, pe baza observației precedente, tabloul 1 este cel mai avantajos dintre toate cele $(n+1)$ ! tablouri analoage obținute permutînd în toate modurile cele $n+1$ noduri.

Observăm că nu numai formula (2) se bucură de proprietatea că toți coeficienții săi sînt cuprinși în tabloul 1. Să găsim atunci toate formulele (23) care au toți coeficienții lor în tabloul 2. Vom zice că aceste formule apartin tabloului 1. Pentru aceasta este necesar și suficient ca pentru orice $i=0,1,\ldots,n$ punctele $x_{\nu_{1}},x_{\nu_{2}},\ldots,x_{\nu_{i+1}}$ să fie $i+1$ puncte consecutive (luate într-o anumită ordine) ale șirului (22), deci ca permutarea

v_{1},v_{2},\ldots v_{n+1}

(27)

a numerelor $1,2,\ldots,n+1$ să se bucure de proprietatea că orice secţiune

v_{1},v_{2},\ldots,v_{i+1},\quad i=0,1,\ldots,n

a șirului (27) să fie formată din $i+1$ numere naturale consecutive, luate într-o anumită ordine.

Dacă convenim a spune despre o astfel de permutare (27) că este o permutare consecutivă permutării inițiale $1,2,\ldots,n+1$ , vedem că:
condiția necesară şi suficientă pentru ca formula de interpolare (23) să aparțină tabloului 1 este ca permutarea (27) să fie o permutare consecutivă permutării inițiale $1,2,\ldots,n+1$ [permutării cu care s-a format tabloul 1 ].

Să numim elemente vecine unui element al tabloului 1 , acei termeni ai tabloului, care se găsesc în coloana imediat precedentă și în coloana
imediat următoare, situate imediat deasupra și imediat dedesubtul elementului considerat. Elementele vecine elementului $\left[x_{i},x_{i+1},\ldots,x_{i+j};f\right]$ sînt atunci figurate în schema

Coeficienții (26) ai formulelor (23) care aparţin tabloului 1 sînt atunci caracterizati de proprietatea că doi coeficienți consecutivi oarecare sînt elemente vecine în tabloul 1.

Numărul formulelor de interpolare (23) aparținînd tabloului 1 se poate uşor determina. O formulă (23) se obține alegînd coeficienți, cîte unul din fiecare coloană, doi coeficienți consecutivi fiind vecini. Numărul $N_{n}$ al acestor formule este deci egal cu numărul drumurilor ce se pot descrie plecînd din prima coloană pînă în ultima, trecînd numai prin elemente vecine.

Să presupunem că $(n+1)!$ se divide cu $2^{n}$ și fie atunci $(n+1)!=2^{n}p$ . Se poate pune însă întrebarea dacă nu pot fi găsite $p$ tablouri de diferențe divizate, obținute prin permutări convenabile ale nodurilor (1), astfel ca ele să conțină toate cele $(n+1)$ ! formule (5). In acest caz ar trebui ca fiecare din cele $(n+1)$ ! formule (5) să aparțină unuia și numai unui s ngur tablou dintre cele $p$ tablouri considerate. In lucrarea [2] se arată că acest lucru este imposibil, afară de cazul banal $n=1$ .

Tot în lucrarea [2] se mai arată că numărul formulelor (23) aparţinînd tabloului nr. 1 în care primele $j$ noduri sînt $x_{i},x_{i+1},\ldots,x_{i+j-1}$ într-o ordine oarecare, este egal $\mathrm{cu}2^{j-1}\binom{n-j+1}{i-1}$ .

Cu aceste considerații introductive ne propunem să determinăm permutarea (21) a nodurilor, astfel ca efectul erorilor ce provin din inmulțirile (2) să fie cel mai mic, atunci cînd aceste înmulțiri se fac ca deobicei după schema

\left.\alpha_{0}\left(D_{1}^{0}+\alpha_{1}\right)\left(D_{1}^{1}+\ldots+\alpha_{n-1}\left(D_{1}^{n-1}+\alpha_{n}D_{1}^{n}\right)\ldots.\right)\right),

unde s-a notat $\alpha_{i}=x_{0}-x_{i},i=0,1,\ldots,n$ . Aceasta revine la determinarea permutării (21) astfel ca șirul

\left|x-x_{v_{1}}\right|,\left|x-x_{v_{2}}\right|,\ldots,\left|x-x_{v_{n+1}}\right|

(28)

să fie nedescrescător.
Prin această proprietate, permutarea (2) nu este neapărat determinată în mod unic, dar:
$x$ fiind un punct dat al axei reale, orice permutare (21) pentru care șirul (28) este nedescrescător este o permutare consecutivă permutării inițiale $1,2,\ldots,n+1$ .

Proprietatea aceasta subzistă indiferent de faptul că $x$ coincide sau nu cu un nod.

Dacă permutarea (21) se bucură de proprietatea că este posibil de a găsi un $x$ , astfel ca șirul (28) să fie nedescrescător, vcm zice că aceasta permutare sau formula (23) corespunzătoare verifica proprictatea de minimum.

Formulele de interpolare (23), pentru care șirul (28) devine nedescrescător pentru un $x$ convenabil, aparțin deci toate tabloului 1 format cu nodurile luate în ordinea crescătoare.

Nu toate cele $2^{n}$ formule (23) aparținînd tabloului 1 verifică proprietatea de minimum studiată.

Se arată în lucrarea [2] că cel puțin $2n$ dintre aceste formule verifică proprietatea de minimum.

Pentru $n=1,2$ cele 2 , respectiv 4 formule aparținînd tabloului 1 verifică proprietatea de minimum.

Dacă $n=3$ şi $x_{1}+x_{4}\neq x_{2}+x_{3},7$ dintre cele 8 formule aparțiind tabloului 1 verifică prcpietc.tea de minimum, iar dacă $x_{1}+x_{4}=x_{2}+x_{3}$ , toate cele 8 formule verifică proprietatea de minimum.

În cazul $n=4$ , dintre cele 16 formule (23) aparținînd tabloului 1 , cel puțin 11 și cel mult 14 verifică proprietatea de minimum.

Ar fi interesant de vazut, pentru $n$ oarecare, care este numarul minim $(\geqslant 2n)$ și care este numărul maxim ( $<2^{n}$ daca $n>3$ ) de permutari consecutive permutării inițiale, care pot verifica preprietatea de minimum.

Pentru o configuratie dată de noduri, numărul formulelor care verifică proprietatea de minimum se poate determina uçor. Pentru determinarea acestui număr nu este nevoie să examinăm monotonia șirului (28) pentru toate valorile 1ui $x$ din motive de continuitate, numai acele valori ale lui $x$ pentru cas a ficător. Aceasta revin la a fart) a livi pentru care avem revine la a examina valorile (în numar finit) ale lui $x$ , pentru care avem

\left|x-x_{r}\right|=\left|x-x_{s}\right|\quad(r\neq s),

egalitate care nu poate avea loc decît dacă

x=\frac{x_{r}+x_{s}}{2}

Este destu1 deci să examinăm numai punctele $x$ care coincid cu mijloacele segmentelor determinate de două noduri.

În particular, dacă nodurile (22) sînt echidistante, punctele $x$ care intervin sînt nodurile însiși precum şi mijloacele segmentelor determinate de cîte două noduri consecutive.

O entumerare detaliată, pe care nu o mai reproducem, ne conduce 1 a rezultatul că dacă nodurile sînt echidistante, numarul formulelor (23) aparținînd tabloului 1, care verifică proprietatea de minim, este egal cu

4.2^{\left[\frac{n}{2}\right]}+2.3^{\left[\frac{n+1}{2}\right]}-2n-6

unde $[\alpha]$ este întregul cuprins în $\alpha$ .
Pentru aplicarea formulei de interpolare, în punctul $x$ se va alege acea formulă (23) care verifică proprietatea că şirul (28) este nedescrescător.

Să presupunem, în particular, că nodurile sînt simetrice față de un punct al axei reale. Acest punct poate fi originea 0. Trebuie atunci să distingem două cazuri, după cum nodurile sînt în număr impar sau par. Dacă presupunem că se interpolează în vecinătatea originii, trebuie de asemenea să distingem două cazuri după cum punctul $x$ este la stînga sau la dreapta lui $O$ .

Cazul I. Număr impar de noduri. Nodurile în ordine crescătoare se pot scrie atunci ( $n=2k$ )

-t_{k},-t_{k-1},\ldots,-t_{1},0,t_{1},t_{2},\ldots,t_{k},

iar permutările care verifică proprietatea de minimum corespund următoarelor permutări ale nodurilor:

\begin{gathered}0,-t_{1},t_{1},-t_{2},t_{2},\ldots,-t_{k},t_{k},\\ 0,t_{1},-t_{1},t_{2},-t_{2},\ldots,t_{k},-t_{k},\end{gathered}

după cum $x$ este la stînga sau la dreapta lui $O$ .
Dacă $x$ este suficient de aproape de origine, acestea sînt de altfel singurele permutări care verifică proprietatea de minimum.

Formulele de interpolare corespunzătoare sînt generalizări cunoscute ale unor formule ale lui Euler, la care se reduc cînd nodurile sînt echidistante. Făcînd media aritmetică a acestor formule, se deduce o generalizare cunoscută a formulei de interpolare a lui Stirling (inutil să scriem aici explicit aceste formule).

Cazul II. Număr par de noduri. Nodurile în ordine crescătoare se pot scrie atunci ( $n=2k-1$ )

-t_{k},-t_{k-1},\ldots-t_{1},t_{1},t_{2},\ldots,t_{k},

iar permutările care verifică proprietatea de minimum corespund următoarelor permutări ale nodurilor:

		$\displaystyle-t_{1},t_{1},-t_{2},t_{2},\ldots,-t_{k},t_{k}$
		$\displaystyle t_{1},-t_{1},t_{2},-t_{2},\ldots,t_{k},-t_{k}$

după cum $x$ este la stînga sau la dreapta lui 0 . Aceste permutări sînt dealtfel singurele care verifică proprietatea de minimum dacă $x$ este suficient de aproape de origine.

Formulele de interpolare corespunzătoare sînt generalizări cunoscute ale altor formule ale lui Euler, la care dealtfel se reduc dacă nodurile sînt echidistante. Făcînd media aritmetică a acestor două formule, obtinem o generalizare cunoscută a formulei de interpolare a lui Bessel (inutil să mai scriem explicit aceste formule).

Proprietatea de minimum pe care am stabilit-o constituie o justificare a utilizării acestor formule, în cazul cînd se interpolează în mijlocul tabloului diferentelor divizate.
4. Ne ocupăm în continuare cu cazul particular important al nodurilor echidistante, studiat în lucrarea [3]. Atunci printr-o transformare simplă, problema de interpolare se pune sub forma egalităţii aproximative.

f(a+xh)\approx\sum_{n=0}^{r}\frac{x(x-1)\ldots(x-v+1)}{v!}\Delta_{h}^{v}f(a),

(29)

unde coeficienţii $\Delta_{k}^{v}f(a)$ se calculează cu ajutorul tabloului de diferențe ale valorilor $f(a+vh),v=0,1,\ldots,n$ , ale functiei $f(x)$ pe noduri.

Calculul valorii polinomului

L(x)=\sum_{v=0}^{n}\frac{x(x-1)\ldots(x-v+1)}{v!}\Delta_{k}^{v}f(a),

(30)

pentru o valoare dată a lui $x$ , se face pe baza schemei

y_{v+1}=\Delta_{h}^{n-v}f(a)+\frac{x-n+v}{n-v+1}y_{v},\quad v=0,1,\ldots,n,\quad\left(y_{0}=0\right).

(31)

Atunci

y_{n+1}=L(x)

(32)

Într-o astfel de schemă de calcul însă, în mod practic, fiecare număr $y_{v+1}$ se calculează aproximativ, folosind valorile aproximative deja obţinute ale numerelor precedente $y_{1},\ldots,y_{v-1},y_{v}$ . Dacă notăm cu $\bar{y}_{v}$ valoarea aproximativă astfel calculată a lui $y_{v}$ și cu $c_{v}$ corecţia respectivă, succesiunea de calcule se va face, în loc de (4), pe baza schemei
$\bar{y}_{v+1}+c_{v+1}=\Delta_{h}^{n-v}f(a)+\frac{x-n+v}{n-v+1}\bar{y}_{v},\quad v=0,1,\ldots,n\quad\left(\bar{y}_{0}=0\right)$ .

Avem atunci

L(x)=\bar{y}_{n+1}+c

(34)

unde corectia $c$ este dată de formula

c=\sum_{\nu=0}^{n}\frac{x(x-1)\ldots(x-\nu+1)}{\nu!}c_{n-\nu+1}

(35)

Dacă eroarea absolută maximă în calculul valorilor aproximative ale numerelor $y_{\nu}$ este $\leqslant\varepsilon$ , deci dacă

\left|c_{v}\right|\leqslant\varepsilon,\quad v=1,2,\ldots,n+1

(36)

avem

|c|\leqslant\varepsilon K_{1}(x)

(37)

unde

K_{1}(x)=\sum_{v=0}^{n}\left|\frac{x(x-1)\ldots(x-v+1)}{v!}\right|

(38)

Formula de interpolare (29) este avantajoasă în special cînd $x$ este aproape de 0 . Această afirmatie este justificată, de ex., de cercetările noastre anterioare asupra utilizării practice a formulelor de interpolare [2]:

Este deci suficient să studiem aici cazul cînd $0<x<1$ . Avem atunci

K_{1}(x)=2-\frac{(1-x)(2-x)\ldots(n-x)}{n!},\quad x\in(0,1)

(39)

și se vede că $K_{1}(x)$ este crescător în intervalul $(0,1)$ . Rezultă că

1=K_{1}(0)<K_{1}(x)<K_{1}(1)=2,\quad x\in(0,1),

(40)

deci

|c|<2\varepsilon.

(41)

Un tablou al valorilor lui $K_{1}(x)$ poate fi utilizat în practică pentru obținerea unei delimitări mai bune.

Dăm mai jos tabloul valorilor lui $K_{1}(x)$ pentru $x=v\cdot 10^{-1}$ , $v=1,2,\ldots 9$ , şi $n=2,3,4,5,6$ .

Table 3: Tabloul 3

$x\backslash n$	2	3	4	5	6
0,1	145	1735	1941625	21027925	2234412625
0,2	28	328	3616	387136	4075648
0,3	405	4645	5046625	53438375	5576636125
0,4	52	584	6256	655552	6785152
0,5	625	6975	7265625	75390625	7744140625
0,6	72	776	8096	832448	8492032
0,7	805	8505	8766625	89392975	9063046125
0,8	88	912	9296	940864	9487488
0,9	945	9615	9701625	97553325	9792032625

În acest tablou valorile sînt calculate exact și nu figurează decît partea lor zecimală. Partea întreagă este evident 1 peste tot. Pentru o valoare a lui $x$ care nu figurează în tablou, se delimitează superior $K_{1}(x)$ prin valoarea sa pentru valoarea imediat superioară a lui $x$ care figurează în tablou. Este clar că pentru $0,9<x<1$ nu putem obține pe această cale o delimitare mai buna decit (41). In practică este suficient să luăm niçte valori aproximative convenabile ale valorilor care figurează în tablou.

Formula (37) dă pentru $c$ delimitarea

-\varepsilon K_{1}(x)\leqslant c\leqslant\varepsilon K_{1}(x)

(42)

inferioară și superioară. Cînd natura calculului indică anumite condiții suplimentare verificate de corecţiile $c_{\nu}$ , o analiză mai amănunțită permite à precizăm aceste delimitări.

Să presupunem că sîntem în cazul în care $0<x<1$ și, ceea ce se întîmplă des în practică, că numerele $y_{v}$ sînt pozitive. Aceasta va avea loc aproape totdeauna cînd $\Delta_{h}^{v}f(a),\quad v=0,1,\ldots,n$ sînt numere pozitive. Pentru a calcula produsul

\frac{x-n+v}{n-v+1}y

(43)

se calculează totdeauna întîi o valoare aproximativă, de exemplu prin lipsă, a valorij sale absolute, care în cazul nostru este

\left|\frac{x-n+v}{n-v+1}\right|\bar{y}_{v}.

(44)

Acest caz are loc de exemplu dacă se calculează numerele (44) cu un număr oarecare de zecimale exacte.

Dacă presupunem că $c_{1}=0$ , ceea ce practic este acceptabil, deoarece presupunem aici că valorile funcției pe noduri nu sînt afectate de erori, vedem că în conditiile de mai sus corecțiile $c_{2},c_{3},\ldots,c_{n}$ sînt $\leqslant 0($ și $\geqslant-\varepsilon)$ iar $c_{n+1}\geqslant 0($ și $\leqslant\varepsilon)$ . Vom avea atunci

-\varepsilon\left[K_{1}(x)-K_{2}(x)\right]\leqslant c\leqslant\varepsilon K_{2}(x)

(45)

unde Pentru delimitarea lui $K_{2}(x)$ observăm că pentru $n=2$ avem $K_{2}(x)=1$ , iar pentru $n>2$ putem scrie

K_{2}(x)=1+xK_{3}(x),

(47)

unde

K_{3}(x)=\sum_{v=1}^{\left[\frac{n-1}{2}\right]}\frac{(1-x)(2-x)\ldots(2v-1-x)}{(2v)!}

(48)

Funcția $K_{3}(x)$ este descrescătoare în intervalu1 ( 0,1 ) şi vom putea utiliza un tablou de valori ale functiei $K_{3}(x)$ pentru delimitarea lui $K_{2}(x)$ cu ajutorul formulei (47).

Dacă formăm un tablou al valorilor lui $K_{3}(x)$ , pentru valorile $\xi_{v}$ , $v=0,1,\ldots,m-1(m>1)$ , ale variabilei, unde

0=\xi_{0}<\xi_{1}<\ldots<\xi_{m-1}<1,\quad\xi_{m}=1

(49)

și dacă $x$ nu figurează în acest tablou, formula (47) ne dă delimitarea

K_{2}(x)<1+xK_{3}\left(\xi_{i}\right),

(50)

presupunînd că $\xi_{i}<x<\xi_{i+1}$ .

Trebuie să observăm că din (13) și din faptul că $K_{1}(x)-K_{2}(x)>0$ rezultă că

K_{2}(x)<2,

(51)

aşa că pentru $\xi_{i}<x<\xi_{i+1}$ , delimitarea (50) nu ne va da o delimitare mai bună decit delimitarea imediata (51), decit daca $xK_{3}\left(\xi_{1}\right)<1$ . Deci price $0<x<1$ pună decît (51) pentru orice $0<x<1$ , este necesar şi suficient ca să avem

\xi_{i+1}K_{3}\left(\xi_{i}\right)<1,\quad i=0,1,\ldots,m-1.

(52)

În particular, prima condiţie (52) se scrie

\xi_{1}\sum_{v==1}^{\left[\frac{n-1}{2}\right]}\frac{1}{2v}<1,

(53)

care, din cauza divergenței seriei armonice, nu este verificată pentru $n$ destul de mare. Dacă deci numerele $\xi_{v},\nu=0,1,\ldots,m-1$ , sînt date, conditii sînt însă verifica, condițille (52) nu sînt toate verificate. Aceste intervalul $(0,1)$ în 10 če daca, de exemplu, $\xi_{v}$ sînt punctele care împart lui $\xi_{\text{v }}$ si $n$ avem următori ale lu $\xi_{v}$ și $n$ avem urmatorul tablou de valori ale funcţiei $K_{3}(x)$ .

Table 4: Tabloul 4

$x$	3,5	5,6	7,8
0,0	5	75	$91\overline{6}$
0,1	45	656625	788245125
0,2	4	568	670144
0,3	35	483875	561477875
0,4	3	404	461408
0,5	25	328125	369140625
0,6	2	256	$283925\overline{3}$
0,7	15	187375	205053375
0,8	1	122	131856
0,9	05	059625	$063702791\overline{6}$

În acest tablou valorile sînt calculate exact și nu figurează decît partea lor zecimală. Partea intreagă este peste tot egală cu 0 . Pentru a delimita pe $K_{2}(x)$ cu ajutorul formulei (47) pentru o valoare a lui $x$ care nu figurează în tablou, se ia din tablou valoarea lui $K_{3}(x)$ , pentru valoarea lui $x$ imediat inferioară și care figurează în tablou. Se verifică că condițiile (52) sînt satisfăcute în aceste cazuri. În practică se pot lua bineînțeles și aici niste valori aproximative prin adaos calorilor din tablou.

Pentru $n=3,4$ , în multe cazuri se poate obține destul de uşor direct, delimitarea lui $K_{2}(x)$ cu ajutorul formulei

K_{2}(x)=1+\frac{x(1-x)}{2}=\frac{(1+x)(2-x)}{2}.

(54)

Pentru delimitarea numărului $K_{1}(x)-K_{2}(x)$ observăm că el este egal cu $x$ pentru $n=2,3$ , iar pentru $n>3$ se poate scrie

K_{1}(x)-K_{2}(x)=xK_{4}(x),

(55)

unde

K_{4}(x)=\sum_{v-1}^{\left[\frac{n-2}{2}\right]}\frac{(1-x)(2-x)\ldots(2v-x)}{(2v+1)!}

(56)

este o funcţie descrescătoare în intervalul ( 0,1 ). Se pot face observații analoage cu cele de mai sus, relativ la utilizarea unui tablou al valorilor lui $K_{4}(x)$ pentru delimitarea lui $K_{1}(x)-K_{2}(x)$ prin formula (55). Din formula (40) şi din $K_{2}(x)>1$ rezultă

K_{1}(x)-K_{2}(x)<1,\quad x\in(0,1)

(57)

şi condițiile pentru ca tabloul să dea o delimitare mai bună decît (57) pentru $\xi_{i}<x<\xi_{i+1}$ sînt ca $xK_{4}\left(\xi_{i}\right)<1$ . Aici $\xi_{v}$ sînt numerele (49). Dacă $i=m-1$ , această condiție cu siguranță nu este verificată pentru orice $x$ , deoarece $K_{4}\left(\xi_{m-1}\right)>1$ . In cazul acesta nu poate fi deci vorba decit ca tabloul să dea o delimitare mai bună decît (57) pentru orice $0<x\leqslant\xi_{m-1}$ şi orice $\xi_{m-1}\leqslant x\frac{1}{K_{4}\left(\xi_{m-1}\right)}$ . Condiţiile necesare şi suficiente pentru ca să fie astfel se scriu

\xi_{i+1}K_{4}\left(\xi_{i}\right)<1,\quad i=0,1,\ldots,m-2.

(58)

În tabloul 5 dăm valorile lui $K_{4}(x)$ pentru valorile lui $x$ care împart intervalul $(0,1)$ în 10 părţi egale și pentru $4\leqslant n\leqslant 9$ .

Table 5: Tabloul 5

${}_{x}{}^{n}$	4,5	6,7	8,9
0,0	$\overline{3}$	$5\overline{3}$	$\overline{6761804}$
0,1	285	4461675	5571044625
0,2	24	38288	4675136
0,3	1983	$2974008\overline{3}$	$3605917458\overline{3}$
0,4	16	23488	2808064
0,5	125	1796875	2119140625
0,6	$09\overline{3}$	$13141\overline{3}$	15295573
0,7	065	0896675	$103052555357142\overline{8}$
0,8	04	05408	0614016
0,9	$018\overline{3}$	$0243008\overline{3}$	02727179583

In acest tablou figurează părțile zecimale exacte ale valorilor funcției $K_{4}(x)$ . Partea întreagă este peste tot egală cu 1. Delimitarea lui $K_{1}(x)$ – $K_{2}(x)$ cu ajutorul lui (55), utilizînd acest tablou, se face în acelaşi fel cum s-a procedat la delimitarea lui $K_{2}(x)$ cu ajutorul tabloului 2.

Condițile (58) sint îndeplinite în aceste cazuri. In felınl arătat mai sus, tabloul 5 dă o delimitare mai bună decît (57) pentru

\left\{\begin{array}[]{l}0<x<0,981996\ldots(n=4,5)\\ 0<x<0,976275\ldots(n=6,7)\\ 0<x<0,973452\ldots(n=8,9)\end{array}\right\}

respectiv.
5. Rezultatele precedente se pot extinde la cazul interpolării prin polinoame de două variabile [4].

Să considerăm $(m+1)(n+1)$ puncte $\left(x_{i},y_{j}\right),i=1,2,\ldots,m+1$ , $j=1,2,\ldots,n+1$ , în plan, formînd o rețea dreptunghiulară de noduri’. Pentru fixarea notațiilor vom presupune că $x_{1}<x_{2}<\ldots<x_{m+1}$ , $y_{1}<y_{2}<\ldots<y_{n+1}$ . Permutarea $P\left(r_{1},r_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ a rețelei de noduri este definită de o permutare $r_{1},r_{2},\ldots,r_{m+1}$ a indicilor $1,2,\ldots,m+1$ , de o permutare $s_{1},s_{2},\ldots,s_{n+1}$ a indicilor $1,2,\ldots,n+1$ şi de renumerotarea coordonatelor nodurilor retelei, astfel ca să avem $x_{i}^{\prime}=x_{r_{i}},i=1,2,\ldots,m+1,y^{\prime}=y_{sj},j=1,2,\ldots,n+1$ .

Să introducem notațiile

D_{v,\mu}^{i,j}[f]=\left[\begin{array}[]{llll}x_{v}^{\prime},&x_{v+1}^{\prime},&\ldots,&x_{v+i}^{\prime}\\ y_{\mu}^{\prime},&y_{\mu+1}^{\prime},&\ldots,&y_{\mu+j}^{\prime}\end{array};f\right]

pentru diferentele divizate pe punctele $\left(x_{v+\alpha}^{\prime},y_{\eta+\beta}^{\prime}\right),\alpha=0,1,\ldots,i$ , $\beta=0,1,\ldots,j$ , relative la funcția $f(x,y)$ .
D.d. $=$ (diferența divizată sau diferențele divizate).
$D_{v,\mu}^{i,j}[f],\quad v=1,2,\ldots,m+1-i,\mu=1,2,\ldots,n+1-j$ ,

i=0,1,\ldots,m,j=0,1,\ldots,n

(61)

constituie tabloul d.d. corespunzător permutării
a rețelei de noduri.

P\left(r_{1},r_{2},\ldots,r_{m+1};\quad s_{1},s_{2},\ldots,s_{n+1}\right)

Sistemul de $(m+1)(n+1)$ d.d.

D_{1,1}^{i,j}[f],i=0,1,\ldots,m;j=0,1,\ldots,n,

(62)

formează un sistem înlănțuit de d.d.
Dacă fiecare termen al unui sistem înlănțuit de d.d. aparține unui aceluiaşi tablou de d.d. vom zice că sistemul înlănțuit considerat aparține acestui tablou de d.d. In particular, sistemul înlănțuit (€2) aparține tabloului 2. Bineînțeles însă sistemu1 înlănțuit (62) aparține în acelaşi timp şi altor tablouri de d.d.

În particular, tabloul 2, corespunzător permutării inițiale $P(1,2,\ldots,m+1;2,\ldots,n+1)$ a rețelei de noduri, se va numi
tabloul normal de d.d. și orice sistem înlănţuit de d.d. aparţinînd acestui tablou se va numi un sistem înlănţuit normal de d.d.. In cazul permutării inițiale avem

r_{i}=i,s_{j}=j,D_{v,\mu}^{i,j}[f]=\left[\begin{array}[]{c}x_{v},x_{v+1},\ldots,x_{v+i}\\ y_{\mu},y_{\mu+1},\ldots,y_{\mu+j}\end{array}\right]

pentru toate valorile posibile ale lui $i,j,\nu,\mu$ .

Permutării $P\left(r_{1},r_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ a reţelei de noduri, îi corespunde polinomul de interpolare de două variabile, care sub forma sa generală este [2]

	$\displaystyle L(x,y)=$
	$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{n_{i}}\left(x-x_{r_{1}}\right)\left(x-x_{r_{3}}\right)\ldots\left(x-x_{r_{i}}\right)\left(y-y_{s_{1}}\right)\left(y-y_{s_{2}}\right)\ldots\left(y-y_{s_{j}}\right)\quad D_{1,1}^{i,j}[f]$		(63)

unde $0=n_{i}\leqslant n,i=0,1,\ldots,m$ , iar pentru $i=0$ respectiv $j=0$ produsul $\left(x-x_{r_{1}}\right)\left(x-x_{r_{2}}\right)\ldots\left(x-x_{r_{i}}\right)$ respectiv $\left(y-y_{s_{1}}\right)\left(y-y_{s_{2}}\right)\ldots\left(y-y_{s_{j}}\right)$ este înlocuit cu 1 .

Pe un punct de interpolare dat ( $x,y$ ), determinarea unei valori aproximative pentru $f(x,y)$ cu ajutorul polinomului (63) necesită calculul valorii numerice a acestui polinom. Acest calcul se face prin executarea, exact sau aproximativ, a unei anumite succesiuni de operații elementare : adunări, scăderi, înmulțiri şi împărțiri. Deoarece operațiile se execută în general aproximativ, va rezulta o eroare de calcul care depinde de precizia cu care s-au executat calculele precum şi, bineînțeles, de ordinea efectuării acestor calcule, adică de programul pe baza căruia ele au fost executate. Nu vom lua în considerare erorile de care sînt eventual afectate datele problemei, deci coordonatele nodurilor și valorilor funcţiei $f(x,y)$ pe aceste noduri.

Pentru a calcula valoarea numerică a polinomului (63), poate fi utilă şi o modificare a expresiei lui, punînd

X_{0}=1,X_{i}=\frac{x-x_{r_{i}}}{k_{i}},Y_{0}=1,\quad Y=\frac{y-y_{s_{i}}}{l_{j}}

unde $k_{0}(=1),k_{1},k_{2},\ldots,k_{m},l_{0}(=1),l_{1},l_{2},\ldots,l_{n}$ sînt nişte numere date, diferite de 0 . Avem atunci

L(x,y)=\sum_{i=0}^{m}\sum_{j=0}^{n_{i}}X_{0}X_{1}\ldots X_{i}Y_{0}Y_{1}\ldots Y_{j}E_{i,j}

care se calculează, deobicei efectuînd suma

\sum_{i=0}^{m}X_{0}X_{1}\ldots X_{i}A_{i}

(64)

în prealabil fiind calculate sumele

A_{i}=\sum_{j=0}^{n_{i}}Y_{0}Y_{1}\ldots Y_{i}E_{i,j},i=0,1,\ldots,m

(65)

Fiecare dintre sumele (64), (65) este de forma

c_{0}C_{0}+c_{0}c_{1}C_{1}+\ldots+c_{0}c_{1}\ldots C_{\alpha}C_{\alpha}.

(66)

Să presupunem că adunările și scăderile nu comportă erori (ele se efectuează exact, sau, în orice caz, cu niște erori care se neglijează). Atunci dacă calculăm suma (66) pe baza schemei

c_{0}\left(C_{0}+c_{1}\left(C_{1}+\ldots+c_{\alpha-1}\left(C_{\alpha-1}+c_{\alpha}C_{\alpha}\right)\ldots\right)\right)

(67)

aşa cum se procedează de obicei, eroarea provine numai din efectuarea celor $\alpha+1$ înmulțiri succesive $\mathrm{cu}c_{\alpha},c_{\alpha-1},\ldots,c_{0}$ respectiv. Este uşor de văzut că dacă aceste înmulțiri se efectuează cu o eroare absolută cel mult egală cu $\varepsilon$ , rezultatul aproximativ obţinut va avea o eroare absolută mai mică đecît

\varepsilon\left(1+\sum_{i=0}^{\alpha-1}\left|c_{0}c_{1}\ldots c_{i}\right|\right)\quad(=\varepsilon\text{ dacă }\alpha=0).

In cazurile pe care le vom considera efectiv, înmulţirea prin $c_{0}$ nu comportă erori (vom avea totdeauna $c_{0}=1$ ). In acest caz eroarea absolută a rezultatului este mai mică decît

\varepsilon\sum_{i=0}^{\alpha-1}\left|c_{0},c_{1},\ldots,c_{i}\right|\quad(=0,\text{ dacă }\alpha=0).

Să aplicăm această schemă de calcul sumelor (64) (65). Suma (65) este de forma (66), unde punem

\alpha=n_{i},c_{v}=Y_{v},C_{v}=E_{i,v}\quad v=0,1,\ldots,n_{i}.

Deci, dacă efectuăm calculele pe baza schemei (67), înmulțirile fiind executate cu o eroare absolută $\leqslant\varepsilon$ , rezultatul obținut $\widetilde{A}_{i}$ este cu o eroare absolută $\leqslant\varepsilon\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|\quad\left(=0\right.$ , dacă $\left.n_{i}=0\right)$ . Rezultă că aproximarea sumei (64),

\sum_{i=0}^{m}X_{0}X_{1}\ldots X_{i}\widetilde{A}_{i},

(68)

are o eroare absolută $\leqslant\varepsilon\sum_{i=0}^{m}\left|X_{0}X_{1}\ldots X_{i}\right|\left(\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|\right)$ .

Suma (68) este de asemenea de forma

\alpha=m,c_{v}=X_{v},C_{v}=\widetilde{A}_{v},\quad v=0,1,\ldots,m.

Deci, dacă și aici efectuăm calculele pe baza schemei (67), înmulţirile fiind executate cu o eroare absolută $\leqslant\varepsilon$ , valoarea aproximativă obţinută pentru (68) va avea o eroare absolută cel mult egală cu $\varepsilon\sum_{i=0}^{n-1}\left|X_{0}X_{1}\ldots X_{i}\right|$ ( $=0$ , dacă $m=0$ ).

În definitiv, deci, făcînd calculele pe baza schemei indicate, obținem pentru $L(x,y)$ o valoare aproximativă cu o eroare absolută $\leqslant\varepsilon M$ , unde

M=\sum_{i=0}^{m}\left|X_{0}X_{1}\ldots X_{i}\right|\left(\sum_{j=0}^{n_{i}-1}\left|Y_{0}\quad Y_{1}\ldots Y_{j}\right|\right)+\sum_{i=0}^{m-1}\left|X_{0}X_{1}\ldots X_{i}\right|.

(69)

Ne putem pune problema de a găsi, pentru punctul de interpolare dat $(x,y)$ , aceea permutare $P\left(r_{1},\dot{r}_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ a rețelei de noduri, pentru care numărul $M$ dat de formula (69) este cel mai mic posibil. Dacă această condiție este îndeplinită, vom considera că polinomul (63) este cel mai avantajos pentru calculele numerice (făcute pe baza schemei indicate).

Atît sumele

B_{i}=\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|,

(70)

cît şi suma (69) sînt de forma

S_{0}+s_{v_{1}}S_{1}+s_{v_{1}}s_{v_{2}}S_{2}+\ldots+s_{v_{1}}s_{v_{2}}\ldots s_{v_{\alpha}}S_{\alpha},

(71)

unde $S_{0},S_{1},\ldots,S_{\alpha}$ sînt numere pozíive, $\operatorname{iar}s_{\nu_{1}},s_{\nu_{2}},\ldots,s_{\nu_{\alpha}}$ este o permutare a unui șir $s_{1},s_{2},\ldots,s_{\alpha}$ de numere pozitive.

Șirul (70) este de forma (71), unde
$\alpha=n_{i}-1,s_{j}=\left|y-y_{j}\right|,v_{i}=s_{j},S_{j}=\frac{1}{\left|l_{0}l_{1}\cdots l_{j}\right|},j=1,2,\ldots,n_{i}-1,S_{0}=1$ ,
iar suma (69) este de forma (71), unde
$\alpha=m,s_{i}=\left|x-x_{i}\right|,v_{i}=r_{i},S_{i}=\frac{1}{\left|k_{0}k_{1}\ldots k_{i}\right|}\left(1+\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|\right);$

i=0,1,\ldots,m-1,S_{m}=\frac{1}{\left|k_{0}k_{1}\ldots k_{m}\right|}\left(\sum_{j=0}^{n_{m}-1}\left|Y_{2}Y_{1}\ldots Y_{j}\right|\right),v_{m}=r_{m}

Avem acum următoarea
LemĂ. Suma (71) îşi atinge cea mai mică valoare a sa dacă şirul $s_{v_{1}},s_{v_{2}},\ldots,s_{v_{\alpha}}$ este nedescrescător (cu alte cuvinte pentru o permutare nedescrescătoare a șirului $s_{1},s_{2},\ldots,s_{\alpha}$ ).

Demonstrația este imediată. Se vede uşor că minimul este atins numai pentru permutările nedescrescătoare ale şirului $s_{1},s_{2},\ldots,s_{\alpha}$ .

Din lema precedentă rezultă atunci următoarea
Teoremă. Dacă permutarea $P\left(r_{1},r_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ este astfel incît şirurile
$\left|x-x_{r_{1}}\right|,\left|x-x_{r_{2}}\right|,\ldots,\left|x-x_{r_{m}}\right|;\left|y-y_{s_{1}}\right|,\left|y-y_{s_{3}}\right|,\ldots,\left|y-y_{s_{n-1}}\right|$
să fie nedescrescătoare, numărul $M$ işi atinge cea mai mică valoare a sa.

Rezultă din cele precedente că dacă şirurile

\left|x-x_{r_{1}}\right|,\left|x-x_{r_{2}}\right|,\ldots,\left|x-x_{r_{m+1}}\right|;\left|y-y_{s_{1}}\right|,\left|y-y_{s_{2}}\right|,\ldots,\left|y-y_{s_{n+1}}\right|

(72)

sînt nedescrescătoare, polinomul (63) este cel mai avantajos pentru calculul unei valori aproximative a lui $f(x,y)$ . In acest caz, pe baza unui rezultat anterior [2], permutarea $r_{1},r_{2},\ldots,r_{m+1}$ trebuie să fie consecutivă permutării $1,2,\ldots,m+1$ , iar permutarea $s_{1},s_{2},\ldots,s_{n+1}$ consecutivă permutării $1,2,\ldots,n+1$ . Aceasta înseamnă că pentru orice $t(t=1,2$ , $\ldots,m+1$ , respectiv $t=1,2,\ldots,n+1)$ șirurile $r_{1},r_{2},\ldots,r_{t}$ și $s_{1},s_{2}$ , … $s_{1}$ , sînt formate din cîte $t$ numere naturale consecutive (într-o anumită ordine).

Cînd șirurile (72) sînt nedescrescătoare şi, în acest caz, polinomul (63) este avantajos prin calcule în sensul arătat mai sus, sistemul înlănțuit de d.d. corespunzător este un sistem înlănţuit normal. Este deci suficient să folosim tabloul normal de d.d. pentru a putea construi toate polinoamele (63) avantajoase, după diferitele poziții ale punctului de interpolare.

Putem, ca și în cazul unei singure variabile [2], să studiem diferite cazuri particulare. Dacă punctul de interpolare este în vecinătatea unuia din nodurile extreme $\left(x_{1},y_{1}\right),\left(x_{1},y_{n+1}\right),\left(x_{m+1},y_{1}\right),\left(x_{m+1},x_{n+1}\right)$ , găsim ca cele mai avantajoase polinoamele ordonate după diferentele ascendente și descendente în raport cu $x,y$ , deci acelea pentru care sistemul înlănțuit (62) corespunde permutărilor $P(1,2,\ldots,m+1;1,2,\ldots,n+1)$ , $P1,2,\ldots,m+1;n+1,n,\ldots,1),P(m+1,m,\ldots,1;1,2,\ldots,n+1)$ , $P(m+1,m,\ldots,1;n+1,n,\ldots,1)$ . Dacă punctele $x_{i}$ și $y_{j}$ sînt respectiv echidistante, deci dacă

	$\displaystyle x_{i}=x_{1}+(i-1)h,i=1,2,\ldots,m+1,y_{j}=y_{1}+(j-1)h^{\prime}$
	$\displaystyle j=1,2,\ldots,n+1\quad\left(h,h^{\prime}>0\right)$		(73)

și dacă punctul de interpolare este în vecinătatea centrului rețelei de noduri, găsim ca cele mai avantajoase polinoame (63) acelea ordonate după diferențele centrale în raport cu $x$ și $y$ .

În înceiere, observăm că în locul tabloului normal de d.d., putem folosi tabloul format cu numerele $k_{0}k_{1}\ldots k_{j}l_{0}l_{1}\ldots l_{j}D_{v,\mu}^{i,j}[f]$ , d.d. fiind referitoare la permutarea inițială a rețelei de noduri. Dacă luăm $k_{i}=ih,l_{j}=jh^{\prime}$ , pentru orice $i,j\geqslant 1$ , numerele considerate se reduc la diferentele $\Delta_{h,h^{\prime}}^{i,i}f(x,y)$ ale funcției $f(x,y)$ . Tabloul normal de d.d. se poate atunci înlocui cu tabloul diferentelor a cărui formare este deosebit de simplă, deoarece nu necesită decît scăderi succesive.

În sfîrșit, considerațiile precedente se pot extinde la cazul a mai mult de două variabile independente.

BIBLIOGRAFIE

1.

Popoviciu T, Despre precizia calculului numeric in interpolarea prin polinoame. Bul. ştiinț. - Acad R P R., Secția de ştiințe matematice şi fizice, VIII, 954-961 (1955).
2.
- •
  
  Consideratii teoretice asupra utilizării practice a unor formule de interpolare. Bul. științ. - Acad. R.P.R., Secția de ştiințe matematice şi fizice, III, 441-449 (1951).
3.
- •
  
  Desfre precizia calculului numeric în interpolarea prin polinomul lui Newton cu noduri echidistante. Studii şi cercetări ştiințifice, Ser. I, VI, 3-4, 27-35 (1955).
4.
- •
  
  Asupra preciziei calculului numeric în interpolarea prin polinoame de două variabile. Studii şi cercetări de matematică (Cluj), XI, fasciculă anexă, 159-165 (1960).
5.

Steffensen J. F., Interpolation, New York, 1950.

Evaluarea erorilor de calcul în interpolarea prin polinoame

Abstract

Autori

Cuvinte cheie

PDF

Citați articolul în forma

Despre acest articol

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

Referințe

Lucrare in format HTML

EVALUAREA ERORILOR DE CALCUL IN INTERPOLAREA PRIN POLINOAME

de

BIBLIOGRAFIE

Related Posts