Is this code efficient to generate the Lagrange polynomial?

% P57_MN0306_08_06M


clearvars


%% Datos:
% xi=1:7;yi=[.5,2.5,2,4,3.5,6,5.5];
% xa=1.5;n=2;

xi=[1,4,6];yi=log(xi);
xa=2;n=2;

% n   - grado del polinomio
% n+1 - mínimo número de puntos
% Li=producto(x-xi)/(xj-xi), j=1,n+1, j<>i
% yL=suma(Li*yi), i=1,n+1



% Generación y evaluación del Polinomio de interpolación de Lagrange 
% con los operadores Li, de grado n, dependiendo del número de n+1 datos
% Evaluación en x = xa
S=0;Li=zeros(1,n+1);
for k=1:n+1
    P=1;
    for kk=1:n+1        
        if k~=kk
            P=P*(xa-xi(kk))/(xi(k)-xi(kk));
        end          
    end
    Li(k)=P; 
    S=S+Li(k)*yi(k);
end

% Resultado
S
log(2)




% Generación del Polinomio de interpolación de Lagrange 
% con los operadores Li, de grado n, dependiendo del número de n+1 datos
% En forma simbólica y numérica
%
disp('Generación del Polinomio de interpolación de Lagrange, de grado n')
%
L=zeros(n,n+1);Sp=zeros(1,n+1);
for k=1:n+1
    P=1;
    for kk=1:n+1        
        if k~=kk
            P=conv(P,[1,-xi(kk)]/(xi(k)-xi(kk)));
        end          
    end
    L(k,:)=P;
    Sp=Sp+L(k,:)*yi(k);
end
Sp
Sps=poly2sym(Sp);pretty(Sps)
polyval(Sp,xa)
log(xa)

Answer 1

[John D'Errico]

Is your code efficient to generate something you should not be doing in the first place? Note that a Lagrange interpolating polynomial is one of those things everybody gets taught in the beginning, but many people think that means it is something good, that they should remember and use in the future. WRONG. High order interpolating polynomials are just bad news. Virtually ALWAYS this is true. Sadly, that part is something teachers often forget to tell their students, probably because they learned from someone who knew no better themselves.

Is your code efficient? No. It uses repeated calls to conv, when a simple use of polyfit would do the same thing, more efficiently. Hint: polyfit with an n'th degree polynomial, applied to n+1 points will yield an interpolating polynomial. Since the interpolating polynomial is unique, there is no need to do something inefficient as you have done. Even better than polyfit would probably be just a simple use of backslash with a Vandermonde matrix. Compared to the doubly nested loop in your code, the difference should be significant.

Again, that polynomial is nothing you want to generate in the first place in any real problem, but you asked only about efficiency.

As such, if this was for a homework assignment, then who cares how efficient it is? If this is for some real problem, then STOP! Return to step 1, and learn how to use other tools, usually splines in some form, that will do the job far better.

[Teddy Negrete Peña]

Best regards, John D’Errico.

Very kind for the prompt reply from him.

I agree that using Matlab functions, with updated interpolation algorithms, provide an efficient solution to the curve fitting problem and according to several authors it is best to use Splines. I also agree that the residual error is not less even when the degree of the polynomial is raised, in fact, dividing the segments into cubic polynomial fragments produces an interpolation with smaller residuals, practically null.

Personally, if I am asked to generate efficient code for curve fitting by interpolation, then I use the Spline function (interpolation by cubic segments), and if I want to do analysis of various types of fits, then I use the splinetool interface

The proposed topic is to generate the Lagrange polynomial, we are not asking to find an efficient way to fit a curve to the presented data. What is requested is directly to the generation of the polynomial. If you realize the first block of the code does not generate the polynomial, it only interpolates a value using the algorithm that generates the Lagrange polynomial.

Could you explain a difference between least squares regression and the concept of interpolation with polynomials?

Thank you very much again.

Sincerely,

Teddy

Answer 2

[Teddy Negrete Peña]

Best regards, John D’Errico.

Very kind for the prompt reply from him.

I agree that using Matlab functions, with updated interpolation algorithms, provide an efficient solution to the curve fitting problem and according to several authors it is best to use Splines. I also agree that the residual error is not less even when the degree of the polynomial is raised, in fact, dividing the segments into cubic polynomial fragments produces an interpolation with smaller residuals, practically null.

Personally, if I am asked to generate efficient code for curve fitting by interpolation, then I use the Spline function (interpolation by cubic segments), and if I want to do analysis of various types of fits, then I use the splinetool interface

The proposed topic is to generate the Lagrange polynomial, we are not asking to find an efficient way to fit a curve to the presented data. What is requested is directly to the generation of the polynomial. If you realize the first block of the code does not generate the polynomial, it only interpolates a value using the algorithm that generates the Lagrange polynomial.

Could you explain a difference between least squares regression and the concept of interpolation with polynomials?

Thank you very much again.

Sincerely,

Teddy