Interpolacja Newtona

[alba marina]

wiadomo ze przez N+1 punktow
\(\displaystyle{ (x_{k},y_{k} ), k=0,1,...,N}\)
przechodzi jeden i tylko jeden wielomian stopnia N. Jesli mamy wspolrzedne tych punktow to mozna ten wielomian znalezc rozwiazujac uklad rownan, lub przez formule Lagrange.
Pomysl Newtona polega na wyrazeni tego wielomiano jako:
\(\displaystyle{ W(x)=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+ . . . +a_{N}(x-x_{0})(x-x_{1})...(x-x_{N-1})}\)
wtedy latwo wykazac ze wspolczynniki ak mozna znalezc budujac macierz D nxn gdzie pierwsza kolumna D to wektor Y =(y0,..,yN) a D(k,j) =(D(k,j-1)-D(k-1,j-1))/(X(k)-X(k-1)), i potem wektor wspolczynnikow ak to bedzie A=diag(D)

nagle znajduje sie z algorytmem w ktorym te wspolczynniki ak licza sie nastepujacym sposobem

A=Y
for j=2:n
for k=Nj
A(k)=(A(k)-A(k-1))/(X(k)-X(k-j+1));
end
end

Niby powinno wyjsc to samo, ale nie rozumiem dlaczego. A moze cos tam zle zrozumialam

Alba Marina

[bisz]

badalem to zagadnienie kiedys ale nawet niewiedziaelm ze to wlasnie ten slynny wielomian interplacyjny. robilem to tak
dajmy na to mamy 4 punkty
\(\displaystyle{ P_{1}=(-2,2)}\)
\(\displaystyle{ P_{2}=(1,-3)}\)
\(\displaystyle{ P_{3}=(3,8)}\)
\(\displaystyle{ P_{4}=(5,-6)}\)

z nich tworzylem uklad rownan 4x4

\(\displaystyle{ \large 2=a(-2)^{3}+b(-2)^{2}+c(-2)+d}\)
\(\displaystyle{ \large -3=a(1)^{3}+b(1)^{2}+c(1)+d}\)
\(\displaystyle{ \large 8=a(3)^{3}+b(3)^{2}+c(3)+d}\)
\(\displaystyle{ \large -6=a(5)^{3}+b(5)^{2}+c(5)+d}\)

i z tego dalej macierzami wyznaczniki i otrzymasz abcd wielomianu 3 stopnia

[alba marina]

W tym przypadku

\(\displaystyle{ X=(-2 1 3 5)'}\)
\(\displaystyle{ D=\left[\begin{array}{cccc}2 & 0 & 0 & 0 \\-3 & \frac{-5}{3} & 0 & 0\\8 & \frac{11}{2} & \frac{43}{6} & 0\\-6 & -7 & \frac{-25}{2} &\frac{-59}{3}\end{array}\right]}\)
wiec
\(\displaystyle{ W(x)=2-\frac{-5}{3}(x+2)+\frac{43}{6}(x+2)(x-1) -\frac{59}{3}(x+2)(x-1)(x-3)}\)

Kazdy sposob ma swoje plusy i minusy . Najwiekszy plus tego sposobu to ze jesli dodajesz jeszcze jeden punkt i chcesz znalezc wielomian, ktory przechodzi przez poprzednie cztery punktyi tez przez npwy punkt (x5,y5) juz tylko musisz rozwiazac jedno rownanie
\(\displaystyle{ y_{5}=2-\frac{-5}{3}(x_{5}+2)+\frac{43}{6}(x_{5}+2)(x_{5}-1) -\frac{59}{3}(x_{5}+2)(x_{5}-1)(x_{5}-3)+a_{4}(x_{5}+2)(x_{5}-1)(x_{5}-3)(x_{5}-5)}\)
zamiast rozwiazywac nowy uklad pieciu rownan