Lagrange interpolation

1.1 Interpolation polynomial

Using polynomials as a tool to study interpolation is called algebraic interpolation. The basic problem is: known functions $f(x)$ in the interval $[a, b]$ on $n+1$ differences $x_{0}, x_{1}, dots, x_{n}$ function value at $y_{i}=feft(x_{i}ight)(i=0,1, dots, n)$ , find at most one $n$ Degree polynomial:
$arphi_{n}(x)=a_{0}+a_{1} x+dots+a_{n} x^{n}（1）$
so that at a given point it is equal to $f(x)$ The same value, that is, the interpolation condition is met:
$arphi_{n}eft(x_{i}ight)=feft(x_{i}ight)=y_{i} uad(i=0,1, dots, n)（2）$

$arphi_{n}(x)$ calledinterpolating polynomial， $x_{i}(i=0,1, dots, n)$ calledinterpolation node, abbreviationnode， $[a, b]$ calledinterpolation interval. Geometrically, $n$ Sub-degree polynomial interpolation is $n+1$ points, draw a polynomial curve $y=arphi_{n}(x)$ approximate curve $y=f(x)$ 。

$n$ Degree polynomial (1) has $n+1$ undetermined coefficients, exactly given by the interpolation condition (2) $n+1$ equation:
$eftegin{array}{l}{a_{0}+a_{1} x_{0}+a_{2} x_{0}^{2}+dots+a_{n} x_{0}^{n}=y_{0}} {a_{0}+a_{1} x_{1}+a_{2} x_{1}^{2}+dots+a_{n} x_{1}^{n}=y_{1}} {dots dots dots dots dots dots dots dots dots dots dots} {a_{0}+a_{1} x_{n}+a_{2} x_{n}^{2}+dots+a_{n} x_{n}^{n}=y_{n}}nd{array}ight.（3）$

Let the coefficient matrix of this system of equations be $A$ , then:
$peratorname{det}(A)=eft|egin{array}{ccccc}{1} & {x_{0}} & {x_{0}^{2}} & {dots} & {x_{0}^{n}} {1} & {x_{1}} & {x_{1}^{2}} & {dots} & {x_{1}^{n}} {} & {dots} & {dots} & {dots} & {dots} {1} & {x_{n}} & {x_{n}^{2}} & {dots} & {x_{n}^{n}}nd{array}ight|$

is called the Vandermont determinant. when $x_{0}, x_{1}, dots, x_{n}$ When they are different from each other, the determinant value is not zero. Therefore the system of equations (3) has a unique solution. This shows that as long as $n+1$ nodes are different from each other and satisfy the interpolation requirement (2)
The interpolation polynomial (1) is unique.

The difference between the interpolating polynomial and the interpolated function:
$R_{n}(x)=f(x)-arphi_{n}(x)$

It is called the truncation error, also known as the interpolation remainder. when $f(x)$ When fully smooth,
$R_{n}(x)=f(x)-L_{n}(x)=rac{f^{(n+1)}(i)}{(n+1) !} mega_{n+1}(x), i n(a, b)$
Among them,
$mega_{n+1}(x)=rod_{j=0}^{n}eft(x-x_{j}ight)$

1.2. Lagrangian interpolation polynomial

In fact, the more convenient way is not to solve equation (3) to find the undetermined coefficients, but to first construct a set of basis functions:
$egin{aligned} l_{i}(x) &=rac{eft(x-x_{0}ight) dotseft(x-x_{i-1}ight)eft(x-x_{i+1}ight) dotseft(x-x_{n}ight)}{eft(x_{i}-x_{0}ight) dotseft(x_{i}-x_{i-1}ight)eft(x_{i}-x_{i+1}ight) dotseft(x_{i}-x_{n}ight)} &=rod_{j=0 top j eq i}^{n} rac{x-x_{j}}{x_{i}-x_{j}}, uad(i=0,1, dots, n) nd{aligned}$
$l_{i}(x)$ Yes $n$ Degree polynomial satisfies:
$l_{i}eft(x_{j}ight)=eftegin{array}{ll}{0} & {j eq i} {1} & {j=i}nd{array}ight.$
Order:
$L_{n}(x)=um_{i=0}^{n} y_{i} l_{i}(x)=um_{i=0}^{n} y_{i}eft(rod_{j=0 top j eq i}^{n} rac{x-x_{j}}{x_{i}-x_{j}}ight)（4）$

The above formula is called $n$ times $Lagrange$ Interpolation polynomial, uniqueness of solution from equation (3), $n+1$ nodes $n$ times $Lagrange$ The interpolation polynomial exists uniquely.

The pseudo code is as follows

LagrangeInterpolationPolynomia(ele, n, x[], y[])
//ele is the element value that needs to be predicted, n is the number of values provided, x[] and y[] store the known x value and the corresponding y value respectively. sum <- 0 k<-0 while k < n do t<-1 j <- 0 while j < n do if j != k t <- ((ele - x[j])/(x[k] - x[j]))*t sum <- t * y[k] + sum end j <- j + 1 end k <- k + 1 end return sum

c++ implementation

#include <iostream>
using namespace std;
float LagrangeInterpolationPolynomia(float x,int n,float a[],float b[]); int main()
{ float x,y,t,a[100],b[100]; int i,j,k,n; cout << "Enter the value of n"<<endl; cin >> n; cout << "Enter the value of x"<<endl; cin >> x; y = 0; for (i=0;i<n;i++) { cout<< "Input the data of x"<<i<<":"; cin >> a[i]; cout<< "Input the data of y"<<i<<":"; cin >> b[i]; } cout << "y="<<LagrangeInterpolationPolynomia(x,n,a,b)<<endl; return 0;
} float LagrangeInterpolationPolynomia(float x,int n,float a[],float b[])
{ int k; float t,y=0; int j; for (k = 0;k < n;k++) { t = 1; for (j = 0;j < n;j++) { if (j != k) t = ((x - a[j])/(a[k]-a[j]))*t; } y = t * b[k]+y; cout << y << endl; } return y;
}

# 1.1 Interpolation polynomial

# 1.2. Lagrangian interpolation polynomial

1.1 Interpolation polynomial

1.2. Lagrangian interpolation polynomial