Interpolacja wielomianami Newtona

Przybliżanie, metoda najmniejszych kwadratów, wielomiany interpolacyjne i inne.
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Interpolacja wielomianami Newtona

Post autor: janusz47 »

Interpolacja wielomianami Newtona

Interpolacja wielomianami Newtona opiera się na bazie wielomianów:

\(\displaystyle{ \mathcal{B} = \{1, \ \ x-x_{0}, \ \ (x-x_{0})(x-x_{1}) \ \ ,..., \ \ (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}) \},}\) która stanowi podstawę

konstrukcji wielomianu Newtona:

\(\displaystyle{ p_{n}(x) = a_{0}\cdot 1 + a_{1}\cdot (x-x_{0}) + a_{2}\cdot (x-x_{0})(x-x_{1})+ \ \ ... \ \ a_{n}\cdot (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}) }\)

Wprowadzając oznaczenia tzw. różnic dzielonych \(\displaystyle{ a_{j} = f[x_{0}, x_{1}, ..., x_{j}], \ \ j = 0,1,2,..., n }\) - możemy zapisać Wielomian

Interpolacyjny Newtona w postaci:

\(\displaystyle{ p_{n}(x) = f[x_{0}] + f[x_{0},x_{1}]\cdot (x-x_{0}) + \ \ ... \ \ + f[(x_{0},x_{1},\ \ ... \ \ x_{n}]\cdot (x-x_{0})(x-x_{1})\cdot ... \cdot (x-x_{n-1}).}\)

Można udowodnić [patrz np. Josef Stoer, Roland Bulirsch. Wstęp do analizy numerycznej, PWN Warszawa 1987], że między różncami dzielonymi

zachodzi rekurencja:

\(\displaystyle{ f[x_{0}, x_{1},\ \ ... \ \ x_{n}] = \frac{f[x_{0}, x_{1},\ \ ... \ \ x_{n-1}] - f[ x_{1},\ \ ... \ \ x_{n}]}{x_{0}-x_{n}} }\)

Relację tą wykorzystujemy, budując tablicę różnic dzielonych w celu obliczenia współczynników wielomianu Newtona.

Program w OCTAVE

Kod: Zaznacz cały

function newtondd(x,y)
  disp('Różnice dzielone')
  disp('___________________________________________________________')
  disp('     x        y       f[,]      f[,,]        f[,,,]     ...')
  disp('___________________________________________________________')
  n=length(x);
  for k=1:n-1
    % Obliczenie pierwszej różnicy dzielonej
      d(k,1)=(y(k+1)-y(k))/(x(k+1)-x(k));
    end
  for i=2:n-1
    for k=1:n-i
    % Obliczenie  i-tej różnicy dzielonej
     d(k,i)=(d(k+1,i-1)-d(k,i-1))/(x(k+i)-x(k));
   end
  end
  % Drukowanie wyników
  if (rem(n,2)==0)
    p=n/2;
  else
    p=fix(n/2);
    m=fix(n/2)+1;
  end
  for i=1:p
    fprintf('%8.2f %8.2f',x(i),y(i));
    for k=1:i-1
      fprintf('         %8.5f',d(i-k,2*k));
    end
    fprintf('\n    ')
    for k=1:i
      fprintf('         %8.5f',d(i-k+1,2*k-1));
    end
    fprintf('\n')
  end
  j=p;
  for i=m:-1:1
    j=j+1;
    fprintf('%8.2f %8.2f',x(j),y(j));
    for k=1:i-1
      fprintf('         %8.5f',d(j-k,2*k));
    end
    fprintf('\n    ')
    for k=1:i-1
      fprintf('         %8.5f',d(j-k+1,2*k-1));
     end
      fprintf('\n')
    end
Przykład

Kod: Zaznacz cały

                                                                                                                                                                                                                              >> x=[1 2 3 5 7]';
>> y=[3 5 9 11 15]';
>> newtondd(x,y)

Różnice dzielone
___________________________________________________________________________
     x        y            f[,]          f[,,]        f[,,,]        ...
___________________________________________________________________________
    1.00     3.00
                            2.00000
    2.00     5.00                      1.00000
                            4.00000                  -0.50000
    3.00     9.00                     -1.00000                     0.12500
                            1.00000                   0.25000
    5.00    11.00                      0.25000
                            2.00000
    7.00    15.00

[size=85][color=green]Dodano po    10 godzinach 15 minutach 40 sekundach:[/color][/size]
[b]Interpolacja  wielomianami Newtona[/b]

Interpolacja wielomianami   Newtona opiera się na bazie wielomianów:

[latex] \mathcal{B} = \{1, \ \ x-x_{0}, \ \ (x-x_{0})(x-x_{1}) \ \ ,..., \ \ (x-x_{0})(x-x_{1})\cdot ... \cdot  (x-x_{n-1}) \},[/latex] która stanowi  podstawę 

konstrukcji wielomianu Newtona:

[latex] p_{n}(x) = a_{0}\cdot 1 + a_{1}\cdot (x-x_{0}) + a_{2}\cdot (x-x_{0})(x-x_{1})+ \ \ ... \ \ a_{n}\cdot (x-x_{0})(x-x_{1})\cdot ... \cdot  (x-x_{n-1}) [/latex]

Wprowadzając oznaczenia  tzw. różnic dzielonych  [latex] a_{j} = f[x_{0}, x_{1}, ..., x_{j}], \ \ j = 0,1,2,..., n  [/latex] -  możemy zapisać Wielomian 

Interpolacyjny Newtona w postaci:

[latex] p_{n}(x) = f[x_{0}] + f[x_{0},x_{1}]\cdot (x-x_{0}) + \ \ ... \ \ + f[(x_{0},x_{1},\ \ ... \ \ x_{n}]\cdot  (x-x_{0})(x-x_{1})\cdot ... \cdot  (x-x_{n-1}).[/latex]

Można udowodnić [patrz np. Josef Stoer, Roland Bulirsch.  Wstęp do analizy numerycznej, PWN Warszawa 1987], że między różncami dzielonymi 

zachodzi rekurencja:

[latex] f[x_{0}, x_{1},\ \ ... \ \ x_{n}] = \frac{f[x_{0}, x_{1},\ \ ... \ \ x_{n-1}] - f[ x_{1},\ \ ... \ \ x_{n}]}{x_{0}-x_{n}} [/latex]

Relację tą wykorzystujemy, budując tablicę różnic dzielonych w celu obliczenia współczynników wielomianu Newtona.

[b]Program w OCTAVE[/b]

[code]
function newtondd(x,y)
  disp('Różnice dzielone')
  disp('___________________________________________________________')
  disp('     x        y       f[,]      f[,,]        f[,,,]     ...')
  disp('___________________________________________________________')
  n=length(x);
  for k=1:n-1
    % Obliczenie pierwszej różnicy dzielonej
      d(k,1)=(y(k+1)-y(k))/(x(k+1)-x(k));
    end
  for i=2:n-1
    for k=1:n-i
    % Obliczenie  i-tej różnicy dzielonej
     d(k,i)=(d(k+1,i-1)-d(k,i-1))/(x(k+i)-x(k));
   end
  end
  % Drukowanie wyników
  if (rem(n,2)==0)
    p=n/2;
  else
    p=fix(n/2);
    m=fix(n/2)+1;
  end
  for i=1:p
    fprintf('%8.2f %8.2f',x(i),y(i));
    for k=1:i-1
      fprintf('         %8.5f',d(i-k,2*k));
    end
    fprintf('\n    ')
    for k=1:i
      fprintf('         %8.5f',d(i-k+1,2*k-1));
    end
    fprintf('\n')
  end
  j=p;
  for i=m:-1:1
    j=j+1;
    fprintf('%8.2f %8.2f',x(j),y(j));
    for k=1:i-1
      fprintf('         %8.5f',d(j-k,2*k));
    end
    fprintf('\n    ')
    for k=1:i-1
      fprintf('         %8.5f',d(j-k+1,2*k-1));
     end
      fprintf('\n')
    end
Przykład

Kod: Zaznacz cały

>> x=[1 2 3 5 7]';                                                                                                                                                                                                                              
>> y=[3 5 9 11 15]';
>> newtondd(x,y)

Różnice dzielone
___________________________________________________________________________
     x        y            f[,]          f[,,]        f[,,,]        ...
___________________________________________________________________________
    1.00     3.00
                            2.00000
    2.00     5.00                      1.00000
                            4.00000                  -0.50000
    3.00     9.00                     -1.00000                     0.12500
                            1.00000                   0.25000
    5.00    11.00                      0.25000
                            2.00000
    7.00    15.00
ODPOWIEDZ