Numeričke metode - veoma teški zadaci sa rešenjima

Rešenje:
Neka je [tex]\omega(x)=(x-x_1)(x-x_2)\ldots(x-x_n)[/tex] i [tex]P(x)=x^n-\omega(x)[/tex]. Imamo
[tex]\omega(x)=x^n-(x_1+x_2+\ldots+x_n)x^{n-1}+\ldots[/tex]
pa se članovi [tex]x^n[/tex] skraćuju i [tex]P[/tex] je polinom stepena najviše [tex]n-1[/tex]; osim toga, [tex]P(x_i)=x_i^n-0=f(x_i)[/tex] za [tex]i=1,\ldots,n[/tex]. Interpolacioni polinom stepena [tex]\le n-1[/tex] kroz [tex]n[/tex] različitih čvorova je jedinstven, pa je [tex]P[/tex] interpolacioni polinom funkcije [tex]f[/tex] u čvorovima [tex]x_1,\ldots,x_n[/tex]. U Njutnovom obliku on glasi
[tex]P(x)=f[x_1]+f[x_1,x_2](x-x_1)+\ldots+f[x_1,\ldots,x_n](x-x_1)\ldots(x-x_{n-1})[/tex]
pa je [tex]f[x_1,\ldots,x_n][/tex] koeficijent uz [tex]x^{n-1}[/tex] u [tex]P[/tex]. Iz
[tex]P(x)=x^n-\omega(x)=(x_1+x_2+\ldots+x_n)x^{n-1}+\ldots[/tex]
dobijamo
[tex]f[x_1,x_2,\ldots,x_n]=x_1+x_2+\ldots+x_n[/tex]
Provera za [tex]n=2[/tex]: [tex]f[x_1,x_2]=\frac{x_2^2-x_1^2}{x_2-x_1}=x_1+x_2[/tex].

Rešenje:
Fiksirajmo proizvoljno realno [tex]x[/tex] i posmatrajmo polinom stepena [tex]n+2[/tex] po promenljivoj [tex]t[/tex]
[tex]g(t)=(x-t)^{n+2}[/tex]
Podelimo ga moničnim polinomom [tex]\omega(t)[/tex] stepena [tex]n+1[/tex]:
[tex]g(t)=\omega(t)q(t)+r(t),\qquad \deg q=1,\qquad \deg r\le n[/tex]
Pošto je [tex]\omega(x_k)=0[/tex], imamo [tex]r(x_k)=g(x_k)[/tex] za [tex]k=0,\ldots,n[/tex]. Lagranžov polinom [tex]L(t)=\sum_{k=0}^{n}g(x_k)l_k(t)[/tex] je jedinstveni polinom stepena [tex]\le n[/tex] koji u [tex]n+1[/tex] različitih čvorova uzima vrednosti [tex]g(x_k)[/tex], pa je [tex]r=L[/tex]. Za [tex]t=x[/tex], koristeći [tex]g(x)=0[/tex], dobijamo
[tex]\sum_{k=0}^{n}(x-x_k)^{n+2}l_k(x)=r(x)=g(x)-\omega(x)q(x)=-\omega(x)q(x)[/tex]
Ostaje da odredimo [tex]q(t)=\alpha t+\beta[/tex]. Neka je [tex]s=x_0+x_1+\ldots+x_n[/tex]; tada je
[tex]\omega(t)=t^{n+1}-s\,t^n+\ldots,\qquad g(t)=(-1)^n(t-x)^{n+2}=(-1)^n\left(t^{n+2}-(n+2)x\,t^{n+1}+\ldots\right)[/tex]
Pošto je [tex]\deg r\le n[/tex], koeficijenti uz [tex]t^{n+2}[/tex] i [tex]t^{n+1}[/tex] u [tex]g[/tex] i u [tex]\omega q=(t^{n+1}-s\,t^n+\ldots)(\alpha t+\beta)[/tex] se poklapaju:
[tex]\alpha=(-1)^n,\qquad \beta-\alpha s=-(-1)^n(n+2)x\ \Rightarrow\ \beta=(-1)^n\left(s-(n+2)x\right)[/tex]
Prema tome,
[tex]q(x)=(-1)^n\left(x+s-(n+2)x\right)=(-1)^n\left(s-(n+1)x\right)=-(-1)^n\sum_{k=0}^{n}(x-x_k)[/tex]
pa je
[tex]\sum_{k=0}^{n}(x-x_k)^{n+2}l_k(x)=-\omega(x)q(x)=(-1)^n\omega(x)\sum_{k=0}^{n}(x-x_k)[/tex]
Pošto je [tex]x[/tex] bilo proizvoljno, identitet važi za svako realno [tex]x[/tex]. (Za [tex]n=0[/tex]: [tex]l_0=1[/tex] i obe strane su jednake [tex](x-x_0)^2[/tex].)