%% Harmadik gyakorlat: Interpoláció I.
% Cél: egy f: \mathbb{R} \rightarrow \mathbb{R} függvény n+1darab pontban (ún. alappontban) ismert (x_i, f_i) értékeiből állítsunk elő egy olyan (megadott tulajdonságokkal rendelkező) g görbét, amire teljesül, hogy g(x_i) = f_i.
%% 1. Lagrange- és Newton-féle interpoláció
% Tegyük fel, hogy x_i \neq x_j igaz minden i \neq j alappontra. Ekkor rögzített n+1 darab pontra pontosan egy legfeljebb n-edfokú L_n polinom létezik, amire L_n(x_i)=f_i teljesül \forall i=1,2,\dots n+1.
% Lagrange-féle interpoláció:
% L_n(x) = \sum_{i=1}^{n+1} f_i \;l_i(x),
% ahol
% l_i(x) = \prod_{j=1, j\neq i}^{n+1} \frac{x-x_j}{x_i-x_j}.
% Newton-féle interpoláció:
% N_n(x) = \sum_{i=1}^{n+1} f[x_1, \dots x_i] \prod_{j=1}^{i-1} (x-x_j),
% ahol
% f[x_1,\dots x_k] = \sum_{j=1}^k \frac{f_j}{\prod_{l=1,l\neq j}^k (x_j - x_l)}.
% Legyenek adottak az alábbi függvényértékek:
% f(-1)=-1,\quad f(0) = 0, \quad f(2)=8.
% Illesszünk ezekre Lagrange, ill. Newton-féle interpolációs polinomot!
% Megoldás: Mivel három pontról van szó, így ezekre legfeljebb másodfokú polinom illeszthető egyértelműen.
% a) Lagrange-féle polinom elemei:
% l_1(x)=\frac{x-x_2}{x_1-x_2} \cdot \frac{x-x_3}{x_1-x_3} = \frac{x-0}{-1-0} \cdot \frac{x-2}{-1-2}=(-x) \frac{x-2}{-3} = \frac{x^2}{3} - \frac{2x}{3},
% l_2(x) = \frac{x-x_1}{x_2-x_1} \cdot \frac{x-x_3}{x_2-x_3} = \frac{x-(-1)}{0-(-1)} \cdot \frac{x-2}{0-2} =(x+1) \left( -\frac{x}{2} + 1\right) = -\frac{x^2}{2} + \frac{x}{2} + 1,
% l_3(x) = \frac{x-x_1}{x_3-x_1} \cdot \frac{x-x_2}{x_3 - x_2} = \frac{x-(-1)}{2-(-1)} \cdot \frac{x-0}{2 - 0} = \frac{x+1}{3} \frac{x}{2} = \frac{x^2}{6} + \frac{x}{6}.
% Így az interpolációs polinom:
% L_2(x) = (-1) \cdot l_1(x) + 0 \cdot l_2(x) + 8 \cdot l_3(x) = (-1) \left( \frac{x^2}{3} - \frac{2x}{3}\right) + 8 \cdot \left( \frac{x^2}{6} + \frac{x}{6} \right) = x^2 + 2x.
% b) Newton-féle polinom elemei: ezeket a legegyszerűbben az osztott differencia táblázat segítségével határozhatjuk meg, ahol használjuk az alábbi képletet:
% f[x_1,\dots x_n] = \frac{f[x_2,\dots x_n] - f[x_1,\dots x_{n-1}]}{x_n - x_1}.
% Így a táblázat:
% \matrix{x_i  & f(x_i) & f[x_i, x_{i+1}] & f[x_i, x_{i+1}, x_{i+2}] \cr
% -1 & -1 & & \cr
% 0 & 0 & \frac{0-(-1)}{0-(-1)}=1 & \cr
% 2 & 8 & \frac{8-0}{2-0}=4 & \frac{4-1}{2-(-1)}=1
% }
% és a polinom pedig
% N_2(x) = -1 + 1\cdot(x-(-1)) + 1 \cdot (x-(-1))(x-0)=-1+x+1+x(x+1)=x^2+2x.
%
%             2. Tekintsük az alábbi pontpárokat:
% \matrix{
% x_i & 0.1 & 0.5 & 0.8 \cr
% f_i & 1.9048 & 1.6065 & 1.4493
% }
% Írjunk egy kódot, amely kiszámolja adott pontokra illeszkedő Largange-polinom értékét valamely x_0 helyen! Alaklmazzuk a kódot a fenti három pontra, és számítsuk ki az interpolációs polinom értékét a 0.35 helyen!
% Megoldás: A függvény (szerkeszthető változatban a fájl végén):
% function out=lagrange(x,f,x0)
% % Legyen x a helyek, f az értékek és x0 a pont, ahol ki akarjuk értékelni.
%
% n=length(x); % Megnézzük, hány pontunk van.
%
% % Kiszámoljuk az l_j(x0) értékeket:
% L=zeros(1,n);
% for i=1:n
%     L(i)=1;
%     for j=1:n
%          if j ~= i
%             L(i)=L(i)*(x0-x(j))/(x(i)-x(j));
%          end
%     end
% end
%
% out=sum(f.*L);
% end

x=[0.1 0.5 0.8];
f=[1.9048 1.6065 1.4493];
lagrange(x,f,0.35)

%
%% 2. Közelítés legkisebb négyzetek értelemben
% Legyenek az (x_i,f_i) értékpárok ismertek, és keressük azt a g: \mathbb{R} \rightarrow \mathbb{R} függvényt, amelyre az alábbi összeg minimális:
% \sum_{i=1}^n (f_i - g(x_i))^2.
% Ezen közelítés előállításához használhatjuk a polyfit függvényt.
%             3. Illesszünk első-, másod- és harmadrendű polinomokat az alábbi pontokra a polyfit függvény segítségével!
% \matrix{
% x_i & -1 & 0 & 1 & 2 \cr
% f_i & 1 & 2 & 2 & 4
% }
% Ábrázoljuk is a kapott görbéket, illetve az eredeti pontokat!
% Megoldás:

x = [-1 0 1 2];
f = [1 2 2 4];
p1 = polyfit(x, f, 1) % Elsőrend
p2 = polyfit(x, f, 2) % Másodrend
p3 = polyfit(x, f, 3) % Harmadrend
xi = linspace(-2, 3);
f1 = polyval(p1, xi);
f2 = polyval(p2, xi);
f3 = polyval(p3, xi);
plot(xi, f1, xi, f2, xi, f3, x, f, 'o')
legend('Elsőfokú','Másodfokú','Harmadfokú')

%

function out=lagrange(x,f,x0)
% Legyen x a helyek, f az értékek és x0 a pont, ahol ki akarjuk értékelni.

n=length(x); % Megnézzük, hány pontunk van.

% Kiszámoljuk az l_j(x0) értékeket:
L=zeros(1,n);
for i=1:n
    L(i)=1;
    for j=1:n
         if j ~= i
            L(i)=L(i)*(x0-x(j))/(x(i)-x(j));
         end
    end
end
% A végeredmény: 
out=sum(f.*L);
end