Interpolacioni polinomi

Često je u praksi potrebno neku funkciju \(f\) predstaviti nekom drugom, jednostavnijom, funkcijom \(g,\) koja je u nekom smislu bliska funkciji \(f.\) Ova potreba se najčešće javlja iz dva razloga:

• nisu sve vrednosti početne funkcije \(f\) poznate. Na primer, funkcija \(f\) je određena eksperimentalnim putem samo u konačno mnogo tačaka; ili
• sama funkcija \(f\) je isuviše komplikovana za bilo kakva složenija izračunavanja (na primer, za integraciju).

Postoji mnogo načina za određivanje funkcije \(g\) koja će „zameniti“ početnu funkciju \(f.\) Najčešće se funkcija \(g\) aproksimira kao linearna kombinacija \(g\approx c_1\phi_1\left(x\right)+c_2\phi_2\left(x\right)+\dots+c_n\phi_n\left(x\right),\) gde su \(\phi_1,\dots,\phi_n\) neke realne funkcije. U zavisnosti od osobina funkcije \(g,\) uzimaju se različiti sistemi funkcija \(\left\{\phi_n\right\}\) (tako se, na primer, za aproksimaciju periodične funkcije uzimaju trigonometrijske funkcije). U ovom tekstu biće pokazano kako se proizvoljna realna glatka funkcija može aproksimirati polinomom. Traženi polinom \(g\) će biti određen tako da važi niz jednakosti \(f\left(x_i\right)=g\left(x_i\right),\) za \(0\le i\le n,\) gde su \(x_0,x_1,\dots,x_n\) različite tačke domena funkcije \(f.\) Ovakav način aproksimacije se naziva interpolacija, a tačke \(x_0,x_1,\dots,x_n\) se nazivaju čvorovi interpolacije.

Lagranžov interpolacioni polinom

Nakon konstantnih, najjednostavniji polinomi su linearni polinomi, to jest polinomi oblika \(a_0+a_1x.\) Ako su nam poznate barem dve vrednosti funkcije \(f,\) tada uz pomoć linearnog polinoma možemo napraviti jednu jednostavnu aproksimaciju koristeći se samo matematikom iz osnovne škole. Naime, ako je \(y_0=f(x_0)\) i \(y_1=f(x_1),\) tada postoji jedinstvena linearna funkcija \(L\) za koju važi \(L(x_0)=y_0\) i \(L(x_1)=y_1.\) Ta funkcija \(L\) je zadata jednačinom \[y=\frac{y_1-y_0}{x_1-x_0}\left(x-x_0\right)+y_0,\] koja se dobija rešavanjem linearnog sistema \[y_0=kx_0+m \qquad y_1=kx_1+m.\]

U nekim situacijama linearna aproksimacija je sasvim dovoljna za naše potrebe:

Primer 1. Aproksimirajmo funkciju \(\log_{10}\left(x\right)\) linearnom funkcijom na intervalu \(\left[10,100\right].\) Koristeći gornju formulu, dobijamo polinomsku funkciju \(y=\frac{x}{90}+\frac{8}{9}.\) Uz pomoć malo analize, može se izračunati da je greška ove aproksimacije na intervalu \(\left[10,100\right]\) manja od \(1/3.\) ▲

Ipak, ponekad linearna interpolacija nije zadovoljavajuća:

Primer 2. Ako ponovo aproskimiramo funkciju \(\log_{10}\left(x\right),\) ovog puta na intervalu \(\left[\frac{1}{10000},10\right]\) koristeći krajeve intervala za interpolacione čvorove, dobićemo linearnu funkciju koja u jednoj tački odstupa za više od \(4\) od naše logaritamske funkcije. ▲

Intuicija nam govori da, ako iskoristimo veći broj podataka o funkciji \(f\) koju želimo da aproksimiramo, to jest ako iskoristimo veći broj čvorova, tada će se greška interpolacije smanjiti.

Primer 3. Aproksimirajmo funkciju \(\sin\left(x\right)\) na intervalu \(\left[0,\pi\right]\) koristeći vrednosti u tačkama \(x_0=0,\) \(x_1=\pi/2\) i \(x_2=\pi.\) Funkcija \(\sin\left(x\right)\) u navedenim tačkama uzima redom vrednosti \(0,\) \(1\) i \(0.\) Kako tačke \(\left(0,0\right),\) \(\left(\pi/2,1\right)\) i \(\left(\pi,0\right)\) nisu kolinearne, interpolacioni polinom ne može biti linearna funkcija. Pretpostavimo zato da je traženi interpolacioni polinom \(L\) drugog stepena. Tada je on oblika \(ax^2+bx+c\) za neke realne koeficijente \(a,\) \(b\) i \(c.\) Iz definicije interpolacionog polinoma sledi da važi \(\sin\left(0\right)=L\left(0\right),\) \(\sin\left(\frac{\pi}{2}\right)=L\left(\frac{\pi}{2}\right)\) i \(\sin\left(\pi\right)= L\left(\pi\right),\) to jest \[\begin{aligned} 0&=a\cdot0^2+b\cdot0+c \\ 1&=a\left(\frac{\pi}{2}\right)^2+b\frac{\pi}{2}+c\\ 0&=a\pi^2+b\pi+c.\end{aligned}\]

Rešenje navedenog sistema je \(a=-\frac{4}{\pi^2},\) \(b=\frac{4}{\pi}\) i \(c=0,\) pa je određen interpolacioni polinom drugog stepena \[L\left(x\right)=-\frac{4}{\pi^2}x^2+\frac{4}{\pi}x,\] koji datu funkciju aproksimira s greškom manjom od \(1/10\) na navedenom intervalu. Grafik funkcije \(\sin\left(x\right)\) i interpolacionog polinoma dat je na slici 1.

▲

Analogno postupku opisanom u prethodnom primeru, možemo postupiti i u slučaju kada imamo više interpolacionih čvorova. Prilikom takvog postupka, potrebno je rešiti linearni sistem \[\tag{1}\left[\begin{matrix} f\left(x_0\right) \\ f\left(x_1\right) \\ \vdots \\ f\left(x_n\right) \end{matrix}\right] = \left[\begin{matrix} x_0 & x_1 & \dots & x_n \\ x_0^2 & x_1^2 & \dots & x_n^2 \\ \vdots & \vdots & & \vdots \\ x_0^n & x_1^n & \dots & x_n^n \end{matrix}\right] \left[\begin{matrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{matrix}\right],\] gde su \(x_1,x_2,\dots, x_n\) čvorovi interpolacije, a \(a_0,a_1,\dots,a_n\) koeficijenti traženog polinoma. Drugim rečima, potrebno je pronaći koordinate interpolacionog polinoma u bazi \(\left[1\;x\;x^2\;\dots\;x^n\right],\) ako takav polinom postoji.

Čitaocu je možda poznato da je kvadratna matrica iz sistema (1) takozvana Vandermondova matrica reda \(n,\) koja ima determinantu različitu od nule kad god su \(x_0,x_1,\dots, x_n\) međusobno različiti brojevi. Kako su u našem slučaju čvorovi \(x_0,x_1,\dots, x_n\) uvek različiti, rešenje sistema (1) uvek postoji i jedinstveno je. Ovim je pokazano da za svaki niz \(x_0,x_1,\dots, x_n\) od \(n+1\) različitih tačaka postoji jedinstveni interpolacioni polinom \(L_n\) stepena \(n,\) koji zadovoljava jednakosti \(L_n\left(x_i\right)=f\left(x_i\right)\) za \(0\le i\le n.\)

Ipak, postoji jedan prirodniji postupak za pronalaženje interpolacionog polinoma \(L.\) Ovaj postupak se zasniva na korišćenju jedne baze polinomskih funkcija koja zavisi od izbora čvorova interpolacije. Fiksirajmo zato čvorove interpolacije \(x_0,x_1,\dots,x_n.\) Novu bazu čine funkcije oblika \[l_i\left(x\right)=\prod\limits_{{j=0\atop j\ne i}}^n\frac{x-x_j}{x_i-x_j}.\] Za polinome \(l_i\) važi \(l_i\left(x_j\right)=1\) ako je \(j=i,\) a u suprotnom \(l_i\left(x_j\right)=0.\) Uz pomoć navedene osobine sada je lako odrediti interpolacioni polinom \(L_n,\) kao linearnu kombinaciju polinoma \(l_i\) \[L_n\left(x\right)=f\left(x_0\right)l_0\left(x\right)+f\left(x_1\right)l_1\left(x\right)+\dots+f\left(x_n\right)l_n\left(x\right).\] Prethodna definicija zaista ima smisla, jer ako je \(x\) jednak nekom od čvorova \(x_i\) tada svaka od funkcija \(l_k\) uzima vrednost nula, osim funkcije \(l_i\) koja uzima vrednost \(1.\) Prema tome, važi \(L_n\left(x_i\right)=l_i\left(x_1\right)f(x_i)=f\left(x_i\right)\) za svako \(0\le i\le n.\) Raspisujući definicije funkcija \(l_i\left(x\right),\) dobija se da je \[\tag{2}L_n\left(x\right)=\sum\limits_{i=0}^n\left(f\left(x_i\right)\prod\limits_{j=0 \atop j\ne i}^n\frac{x-x_j}{x_i-x_j}\right).\] Interpolacioni polinom, zapisan u obliku (2), naziva se Lagranžov interpolacioni polinom.

U komentarima nakon jednakosti (1), već je pokazano da interpolacioni polinom stepena \(n\) mora biti jedinstven. Ali pokažimo to opet na jedan jednostavniji način. Pretpostavimo da postoje dva različita polinoma \(L^1_n\left(x\right)\) i \(L^2_n\left(x\right)\) takva da važe jednakosti \(L^1_n\left(x_i\right)=f\left(x_i\right)=L^2_n\left(x_i\right)\) za \(0\le i\le n.\) Tada je polinom \(L^1_n\left(x\right)-L^2_n\left(x\right)\) različit od nula polinoma, stepena ne većeg od \(n,\) i poseduje \(n+1\) nulu. Ovo je naravno nemoguće, pa polinomi \(L^1_n\left(x\right)\) i \(L^2_n\left(x\right)\) moraju biti isti.

Iz svega navedenog, zaključujemo da važi naredna teorema.

Teorema 1. Neka je realna funkcija \(f\) definisana na različitim tačkama \(x_0, x_1, \dots, x_n.\) Tada postoji jedinstveni polinom \(L\left(x\right)\) stepena \(n\) koji zadovoljava jednakosti \(L\left(x_i\right)=f\left(x_i\right)\) za \(0\le i\le n.\)

Lagranžov polinom je moguće zapisati u malo drugačijem obliku. Uvedimo prvo oznaku \[\omega_{n+1}\left(x\right)=\prod\limits_{j=0}^{n}\left(x-x_j\right).\] Tada je \(\omega_{n+1}'\left(x\right)=\sum_{k=0}^{n}\left(\prod_{{j=0 \atop j\ne k}}^{n}\left(x-x_j\right)\right)\) pa je \(\omega_{n+1}'\left(x_i\right)=\prod_{{j=0 \atop j\ne i}}^{n}\left(x_i-x_j\right).\) Iz ovoga sledi da je polinome \(l_i\left(x\right)\) moguće zapisati kao \[l_i\left(x\right)=\prod\limits_{{j=0\atop j\ne i}}^n\frac{x-x_j}{x_i-x_j}=\frac{\omega_{n+1}\left(x\right)}{\left(x-x_i\right)\omega_{n+1}'\left(x_i\right)},\] pa (2) postaje \[\tag{3} L_n\left(x\right)=\sum\limits_{i=0}^{n}\frac{f\left(x\right)\omega_{n+1}\left(x\right)}{\left(x-x_i\right)\omega_{n+1}'\left(x_i\right)}.\]

Naredna teorema nam daje ocenu greške Lagranžovog polinoma.

Teorema 2. Neka je \(f\colon \mathbb{R}\rightarrow\mathbb{R}\) diferencijabilna \(n+1\) puta, i neka je \(L\left(x\right)\) Lagranžov interpolacioni polinom formiran na osnovu čvorova \(x_0,x_1,\dots,x_n.\) Tada za svako \(x\in\mathbb{R}\) postoji tačka \(\xi\in\mathbb{R}\) koja pripada minimalnom intervalu koji sadrži tačke \(x_0,x_1,\dots,x_n,x,\) takva da je \[\tag{4}f\left(x\right) - L_n\left(x\right) = \frac{f^{\left(n+1\right)}\left(\xi\right)} {\left(n+1\right)!}\omega_{n+1}\left(x\right).\]

Dokaz. Neka je \(\bar{x}\) proizvoljna tačka. Ako je \(\bar{x}=x_i\) za neko \(0\le i \le n,\) tada jednakost (4) trivijalno važi za \(x=\bar{x}.\) Pretpostavimo zato da je tačka \(\bar{x}\) različita od svih čvorova interpolacije. Neka je funkcija \(F\) zadata kao \(F\left(x\right)=f\left(x\right)-L_n\left(x\right)-C\omega_{n+1}\left(x\right),\) pri čemu je konstanta \(C\) određena tako da funkcija \(F\) ima nulu u tački \(\bar{x},\) \[\tag{5}C=\frac{f\left(\bar{x}\right)-L_{n}\left(\bar{x}\right)}{\omega_{n+1}\left(\bar{x}\right)}.\] Funkcija \(F\) takođe ima nule u tačkama \(x_0, x_1, \dots, x_n.\) Uzastupnom primenom Rolove teoreme na funkcije \(F,F',F'',\dots, F^{\left(n\right)},\) zaključujemo da \(F^{\left(n+1\right)}\) ima barem jednu nulu \(\xi\) na minimalnom intervalu koji sadrži tačke \(x_0,x_1,\dots,x_n,\bar{x}.\) Kako je \(L_{n}^{\left(n+1\right)}\equiv0\) i \(\omega_{n+1}^{\left(n+1\right)}\equiv\left(n+1\right)!,\) važi \[0=F^{\left(n+1\right)}\left(\xi\right)=f^{\left(n+1\right)}\left(\xi\right)-C\left(n+1\right)!,\] to jest \[\tag{6}C=\frac{f^{\left(n+1\right)}\left(\xi\right)}{\left(n+1\right)!}.\] Sada jednakost (4) za \(x=\bar{x}\) sledi na osnovu jednakosti (5) i (6). □

Kao što vidimo iz jednakosti (4), greška Lagranžovog interpolacionog polinoma zavisi od broja interpolacionih čvorova, kao i od izvoda funkcije \(f.\) Međutim, uvećavanjem broja interpolacionih čvorova (\(n\)), ne možemo sa sigurnošću reći da se greška interpolacije smanjuje.

Primer 4. Nađimo Lagranžov polinom funkcije \(\sin\left(x\right)\) uzimajući za čvorove tačke \(0,\) \(\frac{\pi}{2}\) i \(\pi\): \[\begin{aligned} L\left(x\right)&= \sin\left(0\right)\frac{\left(x-\frac{\pi}{2}\right)\left(x-\pi\right)}{\left(0-\frac{\pi}{2}\right)\left(0-\pi\right)}+\sin\left(\frac{\pi}{2}\right)\frac{\left(x-0\right)\left(x-\pi\right)}{\left(\frac{\pi}{2}-0\right)\left(\frac{\pi}{2}-\pi\right)}+ \sin\left(\pi\right)\frac{\left(x-0\right)\left(x-\frac{\pi}{2}\right)}{\left(\pi-0\right)\left(\pi-\frac{\pi}{2}\right)}\\ &=\sin\left(\frac{\pi}{2}\right)\frac{\left(x-0\right)\left(x-\pi\right)}{\left(\frac{\pi}{2}-0\right)\left(\frac{\pi}{2}-\pi\right)}=-\frac{4}{\pi^2}x^2+\frac{4}{\pi}x.\end{aligned}\] Kao što vidimo, dobili smo isti polinom kao u primeru 3, što ne bi trebalo da nas iznenađuje jer smo dokazali da je interpolacioni polinom jedinstven.

Na osnovu formule (4), možemo proceniti grešku interpolacije na intervalu \(\left[0,\pi\right]\): \[\left\lvert \sin\left(x\right) - L\left(x\right)\right\rvert= \left\lvert\frac{ \sin^{\left(3\right)}\left(\xi\right)}{3!} \omega_3\left(x\right) \right\rvert \le \frac{\max_{x\in\left[0,\pi\right]}\left\lvert\sin\left(x\right)\right\rvert}{6}\max_{x\in\left[0,\pi\right]}\left\lvert\omega_{3}\left(x\right)\right\rvert = \frac{1}{6}\frac{\sqrt{3}\pi^3}{36}\approx0.248632\] Za konkretne vrednosti promenljive \(x,\) izraz \(\left\lvert\omega_{3}\left(x\right)\right\rvert\) nije potrebno procenjivati sa \(\max_{x\in\left[0,\pi\right]}\left\lvert\omega_{3}\left(x\right)\right\rvert,\) pa je moguće dobiti mnogo bolju ocenu greške. ▲

Uz pomoć formule (2), lako je napisati funkciju u nekom programskom jeziku koja formira Lagranžov polinom. Upravo je u nastavku teksta data jedna takva funkcija napisana u MATLAB jeziku. Funkcija LagranzovPolinom(X, Y) vraća koeficijente Lagranžovog interpolacionog polinoma formiranog na osnovu vektora čvorova X i vektora odgovarajućih vrednosti funkcije Y. Pritom se pretpostavlja da su vektori X i Y iste dužine, kao i da vektor X ne sadrži ponovljene vrednosti. Ugrađena MATLAB funkcija conv koristi se za množenje dva polinoma zadata vektorima koeficijenata.

function [L] = LagranzovPolinom(X, Y)

n = length(X);
L = 0;

for i = 1:n
    Q = 1;
    for j = 1:n
        if j ~= i
            Q = conv(Q, [1, -X(j)] / (X(i) - X(j)));
        end
    end
    L = L + Y(i)*Q;
end

end

Ako je potrebno vratiti samo vrednost interpolacionog polinoma, tada MATLAB algoritam izgleda još jednostavnije.

Njutnov interpolacioni polinom

Interpolacioni polinom se može zapisati i u obliku Njutnovog interpolacionog polinoma, koji se može shvatiti kao uopštenje Tejlorovog polinoma. Pritom, u Njutnovom polinomu figurišu podeljene razlike koje odgovaraju izvodima u Tejlorovom polinomu.

Neka su dati različiti čvorovi \(x_0,x_1,\dots,x_n.\) Podeljene razlike funkcije \(f\) definišu se na sledeći način:

• podeljena razlika nultog reda, u oznaci \(f\left[x_0\right],\) jeste vrednost funkcije \(f\) u tački \(x_0.\)
• podeljena razlika \(k\)-tog reda, u oznaci \(f\left[x_0,x_1,\dots,x_k\right],\) definisana je izrazom \[f\left[x_0,x_1,\dots,x_k\right]=\frac{f\left[x_1,x_2,\dots,x_k\right]-f\left[x_0,x_1,\dots,x_{k-1}\right]}{x_k-x_0}.\]

Šematski, podeljene razlike se mogu zapisati u tabeli:

Uz pomoć indukcije lako se dokazuje da je podeljena razlika reda \(k\) data formulom \[\tag{7}f\left[x_0,\dots,x_k\right]=\sum\limits_{i=0}^{k}\frac{f\left(x_i\right)}{\prod_{{j=0\atop j\ne i}}^{k}\left(x_i-x_j\right)}.\]

Iz navedene formule sledi da je podeljena razlika linearni operator, to jest važi \[\left(\alpha f+\beta g\right)\left[x_0,\dots,x_k\right]=\alpha f\left[x_0,\dots,x_k\right]+\beta g\left[x_0,\dots,x_k\right],\] gde su \(\alpha\) i \(\beta\) proizvoljni realni brojevi, a \(f\) i \(g\) proizvoljne realne funkcije. Iz formule (7) sledi i da je podeljena razlika simetrična funkcija svojih argumenata, to jest da se vrednost podeljene razlike ne menja pri permutaciji čvorova.

Indukcijom se dokazuje i Lajbnicova formula za podeljene razlike: \[\left(fg\right)\left[x_0,\dots,x_k\right]=\sum_{i=0}^{k}f\left[x_0,\dots,x_{i}\right] g\left[x_{i},\dots,x_k\right].\]

Definicija podeljenih razlika se lako može implementirati u MATLAB jeziku. U nastavku je dat kôd funkcije koja na osnovu vektora interpolacionih čvorova X i vektora odgovarajućih vrednosti funkcije Y, vraća gornjetrougaonu matricu sa svim podeljenim razlikama reda ne većeg od n (gde je n dužina vektora X). Kao i u prethodnom algoritmu, pretpostavlja se da su vektori X i Y iste dužine, kao i da vekor X ne sadrži ponovljene vrednosti.

function [PR] = PodeljeneRazlike(X, Y)

n = length(X);
PR = [Y', zeros(n, n-1)];

for i = 2:n
    for j = 1:n-i+1
        PR(j, i) = (PR(j+1, i-1) - PR(j, i-1))/(X(j+i-1)-X(j));
    end
end

end

Vratimo se na interpolacione polinome. Da bismo pronašli Njutnov interpolacioni polinom, izrazimo prvo grešku interpolacije uz pomoć podeljenih razlika. Koristeći definiciju Lagranžovog interpolacionog polinoma i formule (4), dobijamo da je \[\begin{aligned} f\left(x\right)-L_{k}\left(x\right)&=f\left(x\right)-\sum\limits_{i=0}^{k}\frac{f\left(x\right)\omega_{k+1}\left(x\right)}{\left(x-x_i\right)\omega_{k+1}\left(x_i\right)}\\ &=\omega_{k+1}\left(x\right)\left(\frac{f\left(x\right)}{\prod_{j=0}^{k}\left(x-x_j\right)}+\sum\limits_{i=0}^{k}\frac{f\left(x\right)}{\left(x-x_i\right)\prod_{{j=0\atop j\ne i}}^{k}\left(x_i-x_j\right)}\right).\end{aligned}\] Na osnovu (7) sledi da je \[\tag{8}f\left(x\right)-L_{k}\left(x\right)=f\left[x,x_0,\dots,x_n\right]\omega_{k+1}\left(x\right).\] Zapišimo sada Lagranžov interpolacioni polinom \(n\)-tog reda kao \[\tag{9}L_n\left(x\right)=\left(L_n\left(x\right)-L_{n-1}\left(x\right)\right)+\dots+\left(L_{1}\left(x\right)-L_{0}\left(x\right)\right)+L_0\left(x\right)\] gde je \(L_k\left(x\right)\) polinom određen čvorovima \(x_0,\dots,x_k.\) Svaka od razlika \(L_k\left(x\right)-L_{k-1}\left(x\right)\) jeste polinom stepena \(k\) koji ima nule u tačkama \(x_0,\dots,x_{k-1}.\) Sledi da je \[\tag{10}L_k\left(x\right)-L_{k-1}\left(x\right)=\alpha_k\omega_k\left(x\right)\] gde je \(\alpha_k\) neka realna konstanta. Uvrštavanjem vrednosti \(x_k\) u jednakost (10) dobijamo da je \[L_k\left(x_k\right)-L_{k-1}\left(x_k\right)=f\left(x_k\right)-L_{k-1}\left(x_k\right)=\alpha_k\omega_k\left(x\right),\] što nam u poređenju sa (8) daje da je \(\alpha_k=f\left[x_0,\dots,x_k\right].\) Zamenom u (10) imamo da je \(L_k\left(x\right)-L_{k-1}\left(x\right)=f\left[x_0,\dots,x_k\right]\omega_k\left(x\right),\) pa je na osnovu (9), \[\tag{11}L_n\left(x_k\right)=f\left[x_0\right]+f\left[x_0,x_1\right]\left(x-x_0\right)+\dots+f\left[x_0,\dots,x_n\right]\left(x-x_0\right)\cdots\left(x-x_{n-1}\right).\] Interpolacioni polinom zapisan u obliku (11) nazivamo Njutnov interpolacioni polinom.

Poredeći izraze (4) i (8) zaključujemo da je veza podeljenih razlika i izvoda data izrazom \[f\left[x_0,\dots,x_n,x\right]=\frac{f^{\left(n+1\right)}\left(\xi\right)}{\left(n+1\right)!},\] gde \(\xi\) pripada intervalu koji sadrži brojeve \(x_0, x_1, \dots, x_n, x.\)

Čitalac bi trebalo da ima na umu da su Lagranžov i Njutnov interoplacioni polinom potpuno isti polinomi, samo zapisani u različitom obliku. Za konkretne interpolacione čvorove \(x_i\) i odgovarajuće vrednosti \(f(x_i),\) ova dva zapisa svode se na potpuno iste polinomske funkcije.

Koristeći MATLAB funkciju za izračunavanje podeljenih razlika, koju smo ranije opisali, lako možemo konstruisati MATLAB funkciju koja računa vrednost y interpolacionog polinoma u tački x uz pomoć Njutnovog polinoma (11).

function [y] = NjutnovPolinom(x, X, Y)

n = length(X);
PR = PodeljeneRazlike(X, Y);
y = 0;
Q = 1;

for i = 1:n
    y = y + Q * PR(1, i);
    Q = Q * (x - X(i));
end

end

Jednostavnom modifikacijom navedenog algoritma mogu se izračunati i koeficijenti interpolacionog polinoma.

Za kraj ove sekcije, navedimo jedan primer konstrukcije Njutnovog interpolacionog polinoma.

Primer 5. Interpolirajmo funkciju \(f\left(x\right)=\sin\left(\frac{\pi x}{2}\right)+0.2e^{-0.2x}\sin\left(2\pi x+1\right)\) koristeći za čvorove interpolacije \(-2,-1.5,-1,0\) i \(2.\) Tablica podeljenih razlika izgleda ovako:

Na osnovu izraza (11) dobijamo da je \[\begin{aligned}L_{5}(x)&=0.251-2.371\left(x+2\right)+2.65\left(x+2\right)\left(x+1.5\right)-1.097\left(x+2\right)\left(x+1.5\right)\left(x+1\right)\\&+0.218\left(x+2\right)\left(x+1.5\right)\left(x+1\right)\left(x-0\right)\\&=0.218x^4-0.116x^3-0.8695x^2+0.4285x+0.17.\end{aligned}\]

Kao što vidimo sa slike 2, greška interpolacije \(\left\lvert f\left(x\right) -L_5\left(x\right)\right\rvert\) za neke izbore promenljive \(x\) je velika. Zbog toga, možemo dodati još jedan čvor interpolacije, \(x_5=1.\) Računanjem pet podeljenih razlika, dobijamo da je \(f\left[x_0,x_1,x_2,x_3,x_4,x_5\right]=-0.8741,\) pa po (11) sledi da je \[\begin{aligned}L_6\left(x\right)&=L_5\left(x\right)+f\left[x_0,x_1,x_2,x_3,x_4,x_5\right]\left(x-x_0\right)\left(x-x_1\right)\left(x-x_2\right)\left(x-x_3\right)\left(x-x_4\right)\left(x-x_5\right)\\ &=L_5\left(x\right)-0.8741\left(x-x_0\right)\left(x+2\right)\left(x+1.5\right)\left(x-0\right)\left(x-2\right)\left(x-1\right)\\ &=-0.08741x^5-0.000135x^4+0.10362x^3+0.004165x^2+0.94984x+0.16802.\end{aligned}\] Dodavanjem jednog čvora, greška interpolacije je smanjena, što se vidi sa slike 3.

Analognim postupkom moguće je dodati još interpolacionih čvorova. Napomenimo da to ne garantuje da će se greška interpolacije smanjiti. ▲

Kao što se vidi iz prethodnog primera i formule (11), prilikom dodavanja interpolacionih čvorova Njutnov polinom nije potrebno računati ispočetka, već je dovoljno izračunati nekoliko podeljenih razlika i poslednji sabirak u formuli (11). Za razliku od toga, prilikom dodavanja interpolacionih čvorova Lagranžov interpolacioni polinom je potrebno u celosti ponovo izračunati. Zbog toga se Njutnov interpolacioni polinom koristi kada nije unapred poznat potreban broj interpolacionih čvorova.

Interpolacioni polinom sa ravnomerno raspoređenim čvorovima

U Lagranžovom i Njutnovom interpolacionom polinomu, poredak i pozicija čvorova interpolacije nisu bili bitni (važno je bilo samo da su svi čvorovi različiti). U slučaju kada su čvorovi interpolacije ravnomerno raspoređeni, interpolacioni polinom možemo zapisati u još nekoliko različitih oblika koji se zasnivaju na Njutnovom interpolacionom polinomu. Međutim, umesto podeljenih razlika, u ovim zapisima koristimo konačne razlike. U nastavku ćemo koristiti dve oznake za konačne razlike. Svaka od ovih oznaka se definiše induktivno, baš kao i podeljena razlika:

• Razlika unapred \(k\)-tog reda u oznaci \(\Delta^{k}f_{i}\) definiše se kao \(\Delta^{k-1}f_{i+1}-\Delta^{k-1}f_{i}.\)
• Razlika unazad \(k\)-tog reda u oznaci \(\nabla^{k}f_{i}\) definiše se kao \(\nabla^{k-1}f_{i}-\nabla^{k-1}f_{i-1}.\)

Pritom se razlika (unapred, unazad) prvog reda definiše kao razlika vrednosti funkcije \(f\) u čvorovima: \(\Delta^{1}f_{i}=\nabla^{1}f_{i+1}=f(x_{i+1})-f(x_{i}).\)

Direktno iz definicije, dobijamo da između razlika unapred i razlika unazad formiranih nad istim skupom čvorova važi veza \(\Delta^k f_i = \nabla^{k} f_{i+1}.\)

Koristeći indukciju, lako se izvodi formula uz pomoć koje se konačne razlike reda \(k\) izražavaju preko vrednosti funkcije.

Lema 1. Konačne razlike reda \(k\) mogu se računati pomoću formule \[\Delta^{k}f_i=\sum\limits_{j=0}^{k}\left(-1\right)^{j}{k\choose j}f_{i+k-j}.\]

Dokaz. Navedeno tvrđenje ćemo dokazati matematičkom indukcijom. Za \(k=1\) navedena formula se svodi na definiciju podeljene razlike. Pretpostavimo zato da formula važi za podeljene razlike stepena manjeg od \(k.\) Sledi \[\begin{aligned}\Delta^{k+1}f_i&=\Delta^{k}f_{i+1}-\Delta^{k}f_i \\ &=\sum\limits_{j=0}^{k}\left(-1\right)^{j}{k\choose j}f_{i+k+1-j} - \sum\limits_{j=0}^{k}\left(-1\right)^{j}{k\choose j}f_{i+k-j} \\ &= {k \choose 0}f_{i+k+1}+\sum\limits_{j=0}^{k-1}\left(-1\right)^{j+1}{k\choose j+1}f_{i+k-j} - \sum\limits_{j=0}^{k-1}\left(-1\right)^{j}{k\choose j}f_{i+k-j}-\left(-1\right)^{k}{k \choose k}f_{i}\\ &= {k+1 \choose 0}f_{i+k+1}+\sum\limits_{j=0}^{k-1}\left(-1\right)^{j}{k+1\choose j}f_{i+k+1-j}+\left(-1\right)^{k+1}{k+1 \choose k+1}f_{i}\\ &=\sum\limits_{j=0}^{k+1}\left(-1\right)^{j}{k+1\choose j}f_{i+k+1-j}.\end{aligned}\] Pritom četvrta jednakost sledi na osnovu izraza \((-1)^{j+1}{n \choose j+1} - (-1)^j{n \choose j} = (-1)^{j+1}{n+1 \choose j+1}.\) □

Lema 2. Ako je \(x_i=x_0+ih,\) tada je \[\tag{12}f\left[x_i,\dots,x_{i+k}\right]=\frac{\Delta^{k}f_i}{h^kk!}.\]

Dokaz. Navedeno tvrđenje dokazujemo indukcijom. Za \(k=1,\) tvrđenje se svodi na definiciju konačne razlike. Neka je zato tvrđenje tačno za sve podeljene razlike reda ne većeg od \(k.\) Za \(f\left[x_i,\dots,x_{i+k+1}\right]\) imamo \[\begin{aligned} f\left[x_i,\dots,x_{i+k+1}\right] &= \frac{f\left[x_{i+1},\dots,x_{i+k+1}\right]-f\left[x_{i},\dots,x_{i+k-1}\right]}{x_{i+k+1}-x_{i}} \\ &= \frac{1}{(n+1)h}\left(\frac{\Delta^{n}f_{i+1}}{h^nn!}-\frac{\Delta^{n}f_{i}}{h^nn!}\right)=\frac{\Delta^{n+1}f_{i}}{h^{n+1}\left(n+1\right)!}. \end{aligned}\]

□

Ako su interpolacioni čvorovi ravnomerno raspoređeni, tada interpolacioni polinom možemo zapisati u nekoliko različitih oblika u kojima figurišu konačne razlike. Pretpostavimo zato da su dati ravnomerno raspoređeni interpolacioni čvorovi, i tačka \(x\) koja pripada najmanjem intervalu koji sadrži sve date interpolacione čvorove, a za koju želimo da izračunamo približnu vrednost funkcije. Neka je \(h\) razmak između svaka dva čvora. Označimo sa \(x_0\) tačku takvu da \(x\) pripada intervalu \(\left[x_0-h,x_0+h\right].\) Čvorove veće od \(x_0\) označimo indeksima \(1,2,3,\dots,\) a čvorove manje od \(x_0\) označimo indeksima \(-1,-2,-3,\dots,\) tako da su čvorovi raspoređeni na realnoj pravoj kao što su u donjoj tabeli.

Za ovakav raspored čvorova važi formula \(x_i=x_0+ih.\) Uvedimo i novu promenljivu \(q\in\left(-1, 1\right)\) za koju važi \[\tag{13}x=x_0+qh.\]

Ako svi čvorovi imaju pozitivan indeks, tada polinom (11) možemo zapisati u obliku Njutnovog interpolacionog polinoma za interpolaciju unapred: \[\tag{14}L(x_0+qh)=f_0+\frac{q}{1!}\Delta^1 f_0+\frac{q(q-1)}{2!}\Delta^2 f_0+\dots+\frac{q\left(q-1\right)\dots\left(q-n+1\right)}{n!}\Delta^n f_0.\] Za izvođenje gornjeg zapisa iskorišćena je veza (12) i jednakost \(\omega\left(x_0+qh\right)=h^k\prod_{i=0}^{k-1}(q-i)\) koja sledi iz jednakosti (13).

Ako svi čvorovi imaju negativan indeks, tada Njutnov polinom (11) možemo formirati uvođenjem redom čvorova \(x_0, x_{-1}, x_{-2},\dots,x_{-n}.\) Korišćenjem ponovo (12) i (13), dobijamo Njutnov interpolacioni polinom za razliku unazad: \[\tag{15}L(x_0+qh)=f_0+\frac{q}{1!}\Delta^{1} f_{-1}+\frac{q\left(q+1\right)}{2!}\Delta^2 f_{-2}+\dots+\frac{q\left(q+1\right)\dots\left(q+n-1\right)}{n!}\Delta^n f_{-n}.\]

Veća tačnost interpolacije se postiže ako se uzmu u obzir čvorovi sa obe strane tačke \(x.\) Pretpostavimo zato da nam je poznato \(2n+1\) čvorova \(x_{-n},\dots,x_{n+1},\) i neka tačka \(x\) pripada intervalu \(\left(x_0,x_0+\frac{h}{2}\right].\) Tada formiranjem Njutnovog polinoma (11) korišćenjem redom čvorova \(x_0, x_1, x_{-1}, x_2,\dots, x_{n+1}\) (redosled čvorova je formiran na osnovu njihove udaljenosti od \(x_0\)), a zatim iskorišćavanjem veze (12) i (13) dobijamo Gausov interpolacioni polinom za interpolaciju unapred: \[\tag{16}L(x_0+qh)=f_0+\frac{q}{1!}\Delta^{1} f_{0}+\frac{q\left(q-1\right)}{2!}\Delta^2 f_{-1}+\dots+\frac{q\left(q^2-1\right)\dots\left(q^2-n^2\right)}{\left(2n+1\right)!}\Delta^{2n+1} f_{-n}.\]

Ako \(x\in\left[x_0+\frac{h}{2}, x_1\right)\) tada polinom (11) formiramo uvođenjem redom tačaka \(x_1, x_0, x_2, x_{-1},\dots, x_{n+1}, x_{-n}.\) Ponovo, korišćenjem (12) i (13) dobijamo prvi Gausov interpolacioni polinom za interpolaciju unazad (17): \[L(x_0+qh)=f_1+\frac{q-1}{1!}\Delta^{1} f_{0}+\dots+\frac{q\left(q^2-1\right)\dots\left(q^2-(n-1)^2\right)(q-n)(q-(n+1))}{\left(2n+1\right)!}\Delta^{2n+1} f_{-n}.\]

Ako je \(x\in\left[x_0-\frac{h}{2}, x_0\right),\) tada čvorove \(x_0,x_{-1},x_2,\dots,x_{n},x_{-(n+1)}\) uvodimo redom u polinom (11), pa analognim postupkom kao za prethodne polinome dobijamo drugi Gausov interpolacioni polinom za interpolaciju unazad (18): \[L(x_0+qh)=f_0+\frac{q}{1!}\Delta^{1} f_{-1}+\frac{q\left(q+1\right)}{2!}\Delta^2 f_{-1}+\dots+\frac{q\left(q^2-1\right)\dots\left(q^2-n^2\right)}{\left(2n+1\right)!}\Delta^{2n+1} f_{-(n+1)}.\]

Aritmetička sredina polinoma (16) i (17) je Beselov interpolacioni polinom koji se koristi kada je \(\left\lvert q\right\rvert\le 0.25.\) Aritmetička sredina polinoma (16) i (18) je Stirlingov interpolacioni polinom koji se koristi kada je \(0.25\le q\le 0.75.\)

Za grešku navedenih interpolacionih polinoma može se iskoristiti formula (4).

Greška interpolacije

Neka je \(f\colon I\rightarrow\mathbb{R}\) proizvoljna funkcija, gde je \(I\subseteq\mathbb{R}\). Tada definišemo beskonačnu ili ravnomernu normu \(\left\lVert f\right\rVert_{\infty}\) funkcije \(f\) kao \[\left\lVert f\right\rVert_{\infty}=\sup_{x\in I}\left\lvert f\left(x\right) \right\rvert.\] Ako je u prethodnom izrazu funkcija \(f\) neprekidna, a \(I\) kompaktan skup, tada se supremum funkcije dostiže, pa možemo pisati \(\left\lVert f\right\rVert_{\infty}=\max_{x\in I}\left\lvert f\left(x\right) \right\rvert\). U nastavku ćemo uvek smatrati da je skup \(I\) neki interval \(\left[a,b\right]\), a funkcije pod normom neprekidne, osim ako drugačije nije naglašeno. Prema tome \(\left\lVert f\right\rVert_{\infty}=\max_{x\in \left[a,b\right]}\left\lvert f\left(x\right) \right\rvert\)

Jasno je da pojam ravnomerne norme opisuje koliko neka funkcija \(f\) odstupa od nula funkcije na \(\left[a,b\right]\). Prema tome, ravnomerna norma razlike dve funkcije \(\left\lVert f-g\right\rVert_{\infty}\) je jedan od načina da se opiše koliko dve funkcije odstupaju jedna od druge, to jest jedan od načina da se definiše rastojanje među funkcijama \(f\) i \(g\).

Neka je \(f\) proizvoljna funkcija i \(L_n\) odgovarajući interpolacioni polinom formiran na osnovu \(n\) čvorova. U nastavku ćemo posvetiti pažnju vrednosti \(\left\lVert f-L_n\right\rVert_{\infty}\) koja nam opisuje koliko dobro interpolacioni polinom \(L_n\) „oponaša“ funkciju \(f.\) Ako \(\left\lVert f-L_n\right\rVert_{\infty}\rightarrow 0\) kada \(n\rightarrow\infty,\) tada kažemo da interpolacioni polinom ravnomerno konvergira funkciji \(f.\) U ovoj sekciji ćemo odrediti uslove koji nam obezbeđuju ravnomernu konvergenciju interpolacionog polinoma.

Sasvim je lako pronaći primere funkcija \(f\) koje „odstupaju“ od odgovarajućeg interpolacionog polinoma \(L_n\) bez obzira na izbor broja i pozicije čvorova polinoma \(L_n\) (npr. funkcije koje imaju neotklonjive prekide, horizontalne asimptote i slično…). Prema tome, ne može se očekivati bilo kakva ocena veličine \(\left\lVert f-L\right\rVert_{\infty}\) bez postavljanja dodatnih uslova na funkciju \(f.\) Ako je funkcija \(f\) dovoljno glatka, tada nam teorema 2 garantuje formulu (4) \[f\left(\bar{x}\right) - L_n\left(\bar{x}\right) = \frac{f^{\left(n+1\right)}\left(\xi\right)} {\left(n+1\right)!}\omega_{n+1}\left(\bar{x}\right),\] gde \(\xi\) zavisi od \(\bar{x}\) i pripada minimalnom intervalu koji obuhvata sve čvorove interpolacije i tačku \(\bar{x}.\) Stavljanjem apsolutnih vrednosti i uzimanjem maksimuma po \(\xi\) i \(\bar{x}\) s obe strane navedene jednakosti, dobijamo ograničenje uniformne norme greške interpolacije \[\tag{19}\left\lVert f-L_n \right\rVert_{\infty} = \max_{x\in\left[a,b\right]}\left\lvert f\left(x\right)-L_n\left(x\right)\right\rvert \le \frac{\max_{x\in\left[a,b\right]}\left\lvert f^{\left(n+1\right)}\left(x\right)\right\rvert} {\left(n+1\right)!}\max_{x\in\left[a,b\right]} \left\lvert\omega_{n+1}\left(x\right)\right\rvert,\] gde je \(\left[a,b\right]\) najmanji interval koji sadrži sve tačke \(\bar{x},x_0,\dots,x_n.\)

Sada se nameće sledeće pitanje: Da li postoje uslovi koji obezbeđuju da veličina \(\left\lVert f-L\right\rVert_{\infty}\) teži nuli kada se broj interpolacionih čvorova uvećava? Nemački matematičar Karl Runge jednostavnim primerom je pokazao da beskonačna diferencijabilnost funkcije \(f\) ne obezbeđuje potvrdan odgovor na prethodno pitanje:

Primer 6. Za beskonačno diferencijabilnu funkciju \(f\left(x\right)=\left(1+x^2\right)^{-2}\) važi da \(\left\lVert f-L_n\right\rVert_{\infty}\rightarrow\infty\) kad \(x\rightarrow\infty,\) gde je \(L_n\) interpolacioni polinom formiran na osnovu \(n\) ravnomerno raspoređenih čvorova u intervalu \(\left[-5,5\right].\)

Crtanjem grafika još nekoliko interpolacionih polinoma, može se naslutiti da se uvećanjem broja interpolacionih čvorova greška interpolacije na krajevima intervala \(\left[-5,5\right]\) nekontrolisano uvećava, dok se greška interpolacije u sredini intervala smanjuje. Ovaj fenomen se naziva Rungeov fenomen. Precizan dokaz navedenih tvrđenja može se pronaći u literaturi. ▲

Međutim, ako je funkcija \(f\) analitička u dovoljno velikoj oblasti, tada \(\left\lVert f-L_n\right\rVert_{\infty}\rightarrow 0\) kad \(x\rightarrow\infty\) bez obzira na izbor interpolacionih čvorova. Tačnije, pretpostavimo da je funkcija \(f\) analitička na krugu radijusa \(R\) centriranog u sredini intervala \(\left[a,b\right].\) Pretpostavimo i da je radijus kruga dovoljno veliki tako da se ceo interval \(\left[a,b\right]\) sadrži u njemu, to jest da je \(R\ge\frac{1}{2}\left(b-a\right).\) Tada, za svako prirodno \(m\), iz Košijeve nejednakosti sledi \[\tag{20}\left\lvert f^{\left(m\right)}\left(x\right)\right\rvert\le\frac{m!}{2\pi}\oint\limits_{C_R}\left\lvert\frac{f\left(z\right)}{\left(z-x\right)^{m+1}}\right\rvert dz\le \frac{m!}{2\pi}\frac{\max_{z\in C_R} \left\lvert f\left(x\right) \right\rvert}{(R-\frac{1}{2}\left(b-a\right))^{m+1}} 2R\pi.\] gde je \(C_R\) kružnica oko sredine intervala \(\left[a,b\right]\) radijusa \(R.\) Zamenom (20) za \(m=n+1\) u (19), i primećivanjem da je \[\tag{21}\left\lvert\omega_{n+1}\left(x\right)\right\rvert=\left\lvert\left(x-x_0\right)\left(x-x_1\right)\dots\left(x-x_{n}\right)\right\rvert\le(b-a)^{n+1}\] za svako \(x\in[a,b],\) dobijamo da je \[\tag{22}\left\lVert f - L_n \right\rVert_{\infty} \le \frac{R\cdot\max_{x\in C_R} \left\lvert f\left(x\right)\right\rvert}{\left(R-\frac{1}{2}\left(b-a\right)\right)} \left(\frac{b-a}{R-\frac{1}{2}\left(b-a\right)}\right)^{n+1}.\] Prvi činilac s desne strane nejednakosti (22) konstantan je za fiksirano \(R,\) dok drugi teži nuli ako je \(b-a\lt R-\frac{1}{2}\left(b-a\right),\) odnosno ako je \(R\gt\frac{3}{2}(b-a).\) Ovim je dokazana sledeća teorema:

Teorema 4. Neka je \(f\) analitčka na krugu poluprečnika \(R\) sa centrom u tački \(\frac{1}{2}(b+a),\) i neka je poluprečnik \(R\) dovoljno velik tako da važi nejednakost \(R\gt\frac{3}{2}(b-a).\) Tada interpolacioni polinom ravnomerno konvergira funkciji \(f\) na intervalu \(\left[a, b\right]\) bez obzira na izbor interpolacionih čvorova.

Uz navedenu teoremu i dokaz, postaje delimično jasno zašto je u primeru \(6\) došlo do Rungeovog fenomena. Naime, funkcija \(f\left(x\right)=\left(1+x^2\right)^{-2}\) ima polove u tačkama \(i\) i \(-i\) pa se prethodna teorema nije mogla primeniti na ceo interval \(\left[-5,5\right].\)

Ocene, posebno nejednakost (21), iskorišćene u dokazu teoreme 4 su grube. Ako se čvorovi interpolacije fiksiraju, tada je moguće mnogo bolje oceniti izraz \(\left\lVert\omega_{n+1}\right\rVert_\infty.\) Ispostavlja se da postoji jedinstvena distribucija čvorova na intervalu \([a,b],\) za koju je izraz \(\left\lVert\omega_{n+1}\right\rVert_\infty\) najmanji. Ti čvorovi se nazivaju čvorovi Čebiševa, po ruskom matematičaru Pafnutiju Lavovoiču Čebiševu.

U nastavku ćemo definisati čvorove Čebiševa. Bez umanjenja opštosti, možemo definisati čvorove Čebiševa samo na intervalu \([-1,1],\) dok će se čvorovi Čebiševa na proizvoljnom intervalu dobiti prostom linearnom transformacijom. Definišimo prvo polinom Čebiševa \(n\)-tog stepena, kao polinom \(T_n\) koji zadovoljava jednakost \[\tag{23}\cos n\theta=T_n\left(\cos\theta\right).\] Na osnovu jednakosti \(\cos\left(k+1\right)\theta+\cos\left(k-1\right)\theta=2\cos\theta\cos k\theta,\) sledi da je \[\tag{24}\cos\left(k+1\right)\theta=2\cos\theta\cos k\theta -\cos\left(k-1\right)\theta,\] što induktivnom primenom pokazuje da je \(\cos n\theta\) moguće izraziti kao polinom stepena \(n\) po \(\cos \theta.\) Dakle, definicija (23) je dobra.

Ako stavimo \(x=\cos \theta,\) iz (23) i (24) sledi da su polinomi Čebiševa definisani rekurentnom relacijom \[\begin{aligned}T_{0}\left(x\right)&=1\\T_{1}\left(x\right)&=x\\T_{k+1}\left(x\right)&=2xT_{k}\left(x\right)-T_{k-1}\left(x\right)\quad\text{za } k\ge1.\end{aligned}\] Iz navedene rekurentne relacije uočava se da je u polinomu \(T_n\) (\(n\ge1\)) vodeći koeficijent \(2^{n-1}.\) Zbog toga definišemo monične polinome Čebiševa \(t_n,\) kao \(t_n\left(x\right)=\frac{1}{2^{n-1}}T_n\left(x\right)\) za \(n\ge1,\) i \(t_0\left(x\right)=T_0\left(x\right).\)

Iz formule (23) direktno slede dve važne osobine polinoma Čebiševa. Prvo, \(\left\lVert T_n\right\rVert_\infty = 1\) za svaki prirodan broj \(n,\) dok je \(\left\lVert t_n\right\rVert_\infty = \frac{1}{2^{n-1}}\left\lVert T_n\right\rVert_\infty =\frac{1}{2^{n-1}}.\) Drugo, kako je \(\cos n\theta = 0\) ako i samo ako je \(n\theta=\left(2k-1\right)\pi/2,\) sledi da su nule Čebiševog polinoma \(T_n\) date sa \[\tag{25}x_k=\cos\left(\frac{2k-1}{2n}\pi\right)\quad\text{za }1\le k\le n.\] Jasno je da su ovo ujedno i nule moničnog Čebiševljevog polinoma \(t_n.\) Prema tome, sve nule (moničnog) Čebiševljevog polinoma su različite, realne i pripadaju intervalu \(\left(-1,1\right).\) Za dat prirodan broj \(n,\) čvorove Čebiševa \(n\)-tog reda definišemo kao skup od \(n\) nula polinoma \(T_n.\)

Vratimo se na problem smanjivanja greške interpolacije. Ako za čvorove interpolacije uzmemo čvorove Čebiševa \(\left(n+1\right).\) reda, tada će polinom \(\omega_{n+1}\left(x\right)\) u izrazu (4) biti baš moničan polinom Čebiševa \(t_{n+1}.\) Na osnovu izvedene osobine moničnih Čebiševih polinoma \(\left\lVert t_{n+1}\right\rVert_\infty=\frac{1}{2^{n}},\) iz formule (19) dobijamo ocenu \[\left\lVert f-L_n \right\rVert_{\infty}\le\frac{\max_{x\in\left[a,b\right]} \left\lvert f^{\left(n+1\right)}\left(x\right)\right\rvert} {2^{n}\left(n+1\right)!},\] koja je prilično oštra. Prirodno se sada postavlja pitanje Da li se za neki drugi izbor čvorova može dostići još manja vrednost izraza \(\left\lVert\omega_{n+1}\right\rVert_\infty\) ? Odričan odgovor na postavljeno pitanje daje naredna teorema.

Teorema 5. Za proizvoljan moničan polinom \(P_n\) stepena \(n\ge1,\) važi \(\left\lVert P_n\right\rVert_{\infty}\ge\left\lVert t_n\right\rVert_{\infty}=\frac{1}{2^{n-1}},\) gde je \(t_n\) moničan polinom Čebiševa stepena \(n.\)

Dokaz. Pretpostavimo suprotno, da postoji moničan polinom \(P_n\) stepena \(n\) za koji važi \(\max_{-1\le x\le1}\left\lvert P_n\left(x\right)\right\rvert=\left\lVert P_n\right\rVert_{\infty}\lt\frac{1}{2^{n-1}}.\) Tada polinom \(t_n -P_n\) stepena strogo manjeg od \(n\) menja znak najmanje \(n\) puta, pa poseduje barem \(n\) nula. Kako je stepena strogo manjeg od \(n,\) sledi da je polinom \(t_n -P_n\) identički jednak nuli. Ovo je u kontradikciji sa činjenicom da \(t_n -P_n\) menja znak najmanje \(n\) puta. Dakle, pretpostavka da je \(\left\lVert P_n\right\rVert_{\infty}\lt\frac{1}{2^{n-1}}\) ne može biti tačna □

Moguće je dokazati da niz interpolacionih polinoma formiranih na osnovu čvorova Čebiševa \(n\)-tog reda ravnomerno konvergira funkciji \(f,\) pod pretpostavkom da je \(f\) klase \(C^1\) na intervalu na kom se interpolira funkcija. Ovaj dokaz nije elementaran pa ga izostavljamo.

Hermitov interpolacioni polinom

Interpolacioni polinom \(L_n\) je konstruisan tako da važe uslovi \(L_n\left(x_i\right)=f\left(x_i\right)\) za \(0\le i\le n.\) Ipak, često je poznato malo više od vrednosti funkcije u čvorovima. Na primer, poznato je i prvih nekoliko izvoda funkcije \(f\) u čvorovima interpolacije. Korišćenjem dodatnih informacija o izvodima funkcije \(f,\) moguće je konstruisati polinom koji bolje oponaša funkciju \(f\) od običnog interpolacionog polinoma.

Hermitov interpolacioni polinom \(H_n\) je interpolacioni polinom stepena \(n\) formiran tako da važi \(\left(n-1+m\right)\left(m+1\right)\) uslova: \[\tag{26}H_n^{\left(j\right)}\left(x_i\right)=f^{\left(j\right)}\left(x_i\right)\quad\text{za }0\le j\le n_i,\, 0\le i\le m.\] gde je \(n=\sum_{i=0}^{m} n_i -1.\)

Za fiksirane uslove (26) Hermitov interpolacioni polinom \(H_n\) mora biti jedinstven. Naime, ako bi postojao još jedan polinom \(\bar{H}_n\) koji zadovoljava uslove (26), tada bi polinom \(H_n-\bar{H}_n\) bio polinom stepena manjeg od \(n,\) i pritom bi imao barem \(n+1\) nula (u svakom čvoru \(x_i\) po \(n_i\) nula), što je nemoguće. Direktno iz jedinstvenosti Hermitovog polinoma sledi i njegova egzistencija: kako je Hermitov polinom jedinstven, linearni sistem (26) je određen nesingularnom matricom. Zbog toga ovaj sistem mora imati rešenje, nezavisno od izbora vektora sa desne strane.

Hermitov polinom \(H_n\) koji zadovoljava uslove (26) konstruisaćemo uz pomoć Njutnovog interpolacionog polinoma na sledeći način: za svaki čvor \(x_i\) odaberimo \(n_i-1\) dodatnih različitih tačaka \(x_i^1,x_i^{2},\dots,x_i^{n_i-1}\) u okolini čvora \(x_i.\) Na osnovu komentara nakon formule (11) zaključujemo da je \[f\left[x_i, x_i^1,x_i^{2},\dots,x_i^{n_i-1}\right]=\frac{f^{\left(n_i-1\right)}\left(\xi\right)}{\left(n_i-1\right)!},\] gde \(\xi\) pripada najmanjem intervalu koji sadrži \(x_i,x_i^1,x_i^{2},\dots,x_i^{n_i-1}.\) Puštanjem limesa da svaki od brojeva \(x_i^1,x_i^{2},\dots,x_i^{n_i-1}\) teži ka \(x_i\) u prethodnoj jednakosti, dobijamo da je \[\tag{27}f\left[\underbrace{x_i,\dots, x_i}_{n_i\text{ puta}}\right]=\frac{f^{\left(n_i-1\right)}\left(x_i\right)}{\left(n_i-1\right)!}.\] Odavde se, indukcijom, zaključuje da svaka od podeljenih razlika oblika \[f\left[\underbrace{x_i,\dots, x_i}_{n_i\text{ puta}},\underbrace{x_2,\dots, x_2}_{n_2\text{ puta}},\dots,\underbrace{x_{i+k-1},\dots, x_{i+k-1}}_{n_{i+k-1}\text{ puta}}, \underbrace{x_{i+k},\dots, x_{i+k}}_{\le n_{i+k}\text{ puta}}\right]\] postoji. Ako u Njutnovom polinomu \[\tag{28}\begin{aligned}L_n\left(x\right)=&f\left[x_0\right]+f\left[x_0,x_0^{1}\right]\left(x-x_0\right)+f\left[x_0,x_0^{1},x_0^{2}\right]\left(x-x_0\right)\left(x-x_0^{1}\right)+\cdots\\&+f\left[x_0,x_0^{1},x_0^{2},\dots,x_0^{n_i-1}\right]\left(x-x_0\right)\left(x-x_0^{1}\right)\cdots\left(x-x_0^{n_i-2}\right)+\dots \\ &+f\left[x_0,\dots, x_0^{n_0-1},\dots, x_{m},\dots, x_{m}^{n_m-1}\right]\left(x-x_0\right)\cdots\left(x-x_n^{n_m-2}\right), \end{aligned}\] formiranom na osnovu čvorova \(x_0, x_0^1,\dots, x_m^{n_m-2}\) pustimo limes tako da \(x_{i}^{j} \rightarrow x_i\) za svako \(0\le i\le m,\) dobijamo Hermitov interpolacioni polinom \[\tag{29}\begin{aligned}H_n\left(x\right)=&f\left[x_0\right]+f\left[x_0,x_0\right]\left(x-x_0\right)+f\left[x_0,x_0,x_0\right]\left(x-x_0\right)^2+\cdots\\&+f\left[\underbrace{x_0,\dots, x_0}_{n_0\text{ puta}}\right]\left(x-x_0\right)^{n_i-1}+f\left[\underbrace{x_0,\dots, x_0}_{n_0\text{ puta}},x_1\right]\left(x-x_0\right)^{n_i}+\dots \\ &+f\left[\underbrace{x_0,\dots, x_0}_{n_0\text{ puta}},\dots, \underbrace{x_{m},\dots, x_{m}}_{n_{m}\text{ puta}}\right]\left(x-x_0\right)^{n_0}\cdots\left(x-x_n\right)^{n_m-1}.\end{aligned}\]

Ocena greške Hermitove interpolacije može se izvesti iz greške polinoma (28) prelaskom na limes tako da \(x_{i}^{j} \rightarrow x_i\) za svako \(0\le i\le m.\) Time se dobija \[\tag{30}f\left(x\right) - L_n\left(x\right) = \frac{f^{\left(n+1\right)}\left(\xi\right)} {\left(n+1\right)!}\omega_{n+1}\left(x\right)=\frac{f^{\left(n+1\right)}\left(\xi\right)} {\left(n+1\right)!}\prod\limits_{k=0}^{m}\left(x-x_k\right)^{n_k},\] gde \(\xi\) pripada najmanjem intervalu koji sadrži tačke \(x,x_0, x_1,\dots, x_m.\)

U praksi, Hermitov interpolacioni polinom se konstruiše tako što se prvo napravi tablica podeljenih razlika. Tablica se pravi tako što se u njoj svaki čvor \(x_i\) navede \(n_i\) puta, a zatim se upišu odgovarajuće podeljene razlike na osnovu poznatih izvoda po formuli (27). Time se dobija nepotpuna tabela podeljenih razlika poput naredne (u njoj je čvor \(x_i\) naveden četiri puta, i upisane su podeljene razlike \(f\left[x_i,x_i\right],\) \(f\left[x_i,x_i,x_i\right],\) \(f\left[x_i,x_i,x_i,x_i\right]\)).

Nakon toga, ostatak tabele se popuni u skladu s definicijom podeljenih razlika. Na kraju se zapiše polinom (29) na osnovu podataka iz konstruisane tabele.

Primer 6. Nađimo Hermitov interpolacioni polinom \(H\) takav da važi \[H\left(x_0\right)=f\left(x_0\right),\quad H'\left(x_0\right)=f'\left(x_0\right),\quad H''\left(x_0\right)=f''\left(x_0\right),\quad H'''\left(x_0\right)=f'''\left(x_0\right).\] Na osnovu opisanog postupka dobijamo da je \[H\left(x\right)=f\left(x_0\right)+f'\left(x_0\right)\left(x-x_0\right)+\frac{f''\left(x_0\right)}{2!}\left(x-x_0\right)^2+\frac{f'''\left(x_0\right)}{3!}\left(x-x_0\right)^3.\] Kao što se vidi, Tejlorov polinom je specijalan slučaj Hermitovog polinoma. Na osnovu formule (30) greška interpolacije je \(\frac{f^{\left(4\right)}\left(\xi\right)}{4!}\left(x-x_0\right)^4,\) gde je \(\xi\) između \(x_0\) i \(x,\) što je Lagranžov oblik ostatka u Tejlorovoj formuli. ▲

Primer 7. Nađimo Hermitov interpolacioni polinom \(H\) takav da važi \[H\left(0.5\right)=\sin\left(0.5\right),\quad H'\left(0.5\right)=\sin'\left(0.5\right),\quad H\left(5.5\right)=\sin\left(5.5\right),\quad H'\left(5.5\right)=\sin'\left(5.5\right).\] Tablica podeljenih razlika izgleda ovako:

Sledi da je Hermitov interpolacioni polinom \[\begin{aligned}H\left(x\right)&=0.4794+0.8776\left(x-0.5\right)-0.2229\left(x-0.5\right)^2+0.0824\left(x-0.5\right)^2\left(x-5.5\right)\\&=0.0824x^3-0.7585x^2+1.5743x-0.128425.\end{aligned}\]

▲

Literatura

1. Roland Bulirsch, Josef Stoer, Introduction to Numerical Analysis
2. Walter Gautschi, Numerical Analysis
3. Desanka Radunović, Numeričke metode