Interpolation and the Lagrange Polynomial

• nth Larange interpolating polynomial
• Neville’s Iterated Interpolation
• Newton’s Divided-Difference Formula
• Natural Cubic Spline
• Clamped Cubic Spline

nth Lagrange interpolating polynomial

If $x_{0},x_{1},x_{2},...,x_{n}$ are n+1 distinct numbers and f is a function whose values are given at these numbers, then a unique polynomial $P(x)$ of degree at most $n$ exists with:

This polynomial is given by

Where, for each $k=0,1,2,...,n$

using Plots
using NumericalAnalysis: Polynomial
x = 1:0.01:5
s = Polynomial.Lagrange([2, 11/4, 4], [1/2, 4/11, 1/4])
plot(x, [s.(x) 1 ./ x], title = "nth Lagrange polynomial", label = ["y = p(x)" "y = f(x)"], xlabel="x", ylabel="y")

Neville’s Iterated Interpolation

Let $f$ be defined at $x_{0},x_{1},...,x_{k}$ and let $x_{i}$ and $x_{j}$ be two distinct numbers in this set. Then

x = [1.0, 1.3, 1.6, 1.9, 2.2]
y = [0.7651977, 0.6200860, 0.4554022, 0.2818186, 0.1103623]
Polynomial.Neville(x, y, 1.5, tab=true)

5×5 Array{Float64,2}:
 0.765198  0.0       0.0       0.0       0.0
 0.620086  0.523345  0.0       0.0       0.0
 0.455402  0.510297  0.512471  0.0       0.0
 0.281819  0.513263  0.511286  0.511813  0.0
 0.110362  0.510427  0.513736  0.51183   0.51182

Newton’s Divided-Difference Formula

Suppose that $P_{n}(x)$ is the nth Lagrange polynomial that agrees with the function $f$ at the distinct numbers $x_0 , x_1 , . . . , x_n$ . Although this polynomial is unique, there are alternate algebraic representations that are useful in certain situations. The divided differences of f with respect to $x_0, x_1, . . . , x_n$ are used to express $P_n(x)$ in the form

So

x = [1.0, 1.3, 1.6, 1.9, 2.2]
y = [0.7651977, 0.6200860, 0.4554022, 0.2818186, 0.1103623]
print(Polynomial.NDDF(x, y, backward=true))

0.00182510288066044*x^4 + 0.0574829218106903*x^3 - 0.231035864197514*x^2 - 0.280787281893018*x + 1.21771282139918

Natural Cubic Spline

note: $S(x) = S_j(x) = a_j + b_j(x-x_j)+c_j(x-x_j)^2+d_j(x-x_j)^3$ for $x_j \leq x \leq x_{j+1}$

x = [0,1,2,3]
y = [1, exp(1), exp(2), exp(3)]
st = Polynomial.NCSpline(x, y)
x₁ = 0:0.1:3
function plot_curve(x)
    if 0 ≤ x < 1
        return st[1](x)
    end
    if 1 ≤ x < 2
        return st[2](x)
    end
    if 2 ≤ x ≤ 3
        return st[3](x)
    end
end
plot(x₁, [exp.(x₁) plot_curve.(x₁)], label=["real" "predict"], legend=:topleft)

x = [0,1,2,3]
y = [1, exp(1), exp(2), exp(3)]
Polynomial.NCSpline(x, y, Latex=true)

0.252284214284322*t^3 + 1.46599761417472*t + 1.0,t ∈[0, 1]
2.22285025702769*t + 1.69107137059095*(t - 1)^3 + 0.756852642852966*(t - 1)^2 + 0.495431571431356,t ∈[1, 2]
8.80976965450647*t - 1.94335558487527*(t - 2)^3 + 5.83006675462582*(t - 2)^2 - 10.2304832100823,t ∈[2, 3]

Clamped Cubic Spline

add a endpoint $f'(0) = 1$, and $f'(3) = e^3$.

st1 = Polynomial.CCSpline(x, y, [1, exp(3)])
function plot_curve1(x)
    if 0 ≤ x < 1
        return st1[1](x)
    end
    if 1 ≤ x < 2
        return st1[2](x)
    end
    if 2 ≤ x ≤ 3
        return st1[3](x)
    end
end
scatter(x₁, plot_curve1.(x₁), label="predict", legend=:topleft)
plot!(x₁, exp.(x₁), label="real")

Method

Polynomial

CCSpline(x::Vector, y::Vector, endpoint::Vector; Latex::Bool=false, a::String="t")

Lagrange(X::Vector, Y::Vector; a::String="x")

NCSpline( NCSpline(x::Vector, y::Vector; Latex::Bool=false, a::String="t")

NDDF(x::Vector, y::Vector; a::String="x", simple::Bool=true, tab::Bool=false, backward::Bool=false)

Neville(x::Vector, y::Vector, x₀::Real; tab::Bool=false)