Lagrange Interpolation

[yfnaji]

Lagrange Polynomial Interpolation

This pull request implements the Lagrange interpolator as one of the polynomial interpolators in issue https://github.com/avhz/RustQuant/issues/5.

The results have been benchmarked against SciPy's lagrange function.

Important note before merging!

This Interpolation method requires the std::ops::MulAssign trait to be implemented for the InterpolationValue type, however, this has already been done in this PR https://github.com/avhz/RustQuant/pull/301 for Natural Cubic splines.

I will not include it in this PR to avoid a (more complicated) merge conflict - so it is best to merge https://github.com/avhz/RustQuant/pull/301 first before this PR.

If you want to test it beforehand, these lines must be included in RustQuant_math/src/interpolation/mod.rs to avoid error:

use std::ops::{Div, Mul, Sub, AddAssign, MulAssign};

impl<T> InterpolationValue for T where T: num::Num + AddAssign + MulAssign + std::fmt::Debug + Copy + Clone + Sized {}

Mathematical Background

Say we want to construct a polynomial that interpolates the following coordinates:

$$ (x_0, y_0),(x_1, y_1),\ldots, (x_n, y_n) $$

Define the Lagrange basis polynomial associated with $x_j$:

$$ L_j(x) = \prod_{{i=0, \ i\neq j}}^n\frac{x-x_i}{x_j-x_i} $$

It is clear that

$$ L_j(x)=\begin{cases} 1, & \text{if $x=x_j$}\ 0, & \text{if $x=x_i$ for $i\neq j$} \end{cases} $$

The interpolation polynomial takes the form:

$$ P(x)=\sum^{n}_{i=0}y_i L_i(x) $$

Now, evaluating at an interpolation point $x_j$:

$$ P(x_j) = y_0 L_0(x_j) + y_1 L_1(x_j) + \cdots + y_jL_j(x_j) + \cdots + y_nL_n(x_j) $$

$$ = 0 + 0 + \cdots + y_j \cdot 1 + \cdots + 0\ $$

$$ =y_j $$

as required.