table of contents | |
---|---|
- | Lagrange interpolation |
- | Example 1: Linear interporation |
- | Example 2: Quadratic interpolation |
- | Example 3: Cubic interpolation |
- | Uniqueness |
Lagrange interpolation
Let $f(x)$ be an arbitrary real function.
The nth degree polynomial passing through $n + 1$ points
is
, where $L_{j}(x)$ is the nth degree polynomial defined as
. $p(x)$ is called Langrange interporation.
Proof
Let
$$\tag{1}$$be $n+1$ points on a real function $f(x)$, where
Let $p(x)$ be the nth degree polynomial passing through $(1)$. $p(x)$ satisfies
$$\tag{2}$$(See fig. below).
We put $p(x)$ as
$$\tag{3}$$, where $L_{i}(x)$ $(i=0,1, \cdots,n)$ are nth degree polynomials.(The specific form of $L_{i}(x)$ has not been determined at this point.)
If $L_{i}(x)$ satisfy
, $p(x_{0}) = f(x_{0}) $.
If $L_{i}(x)$ satisfy
$p(x_{1}) = f(x_{1}) $.In the same way, we see thatif $L_{i}(x)$ satisfy,
$$\tag{4}$$, $p(x_{j}) = f(x_{j})$ $(j=0,1,\cdots,n)$.
In $(4)$, $L_{0}(x_{i}) = 0$ for $i =1, 2, \cdots, n$.By the factor theorem, $L_{0} (x)$ can be expressed as
, where $\alpha_{0} $ is a constant.By $L_{0}(x_{0}) = 1$, it is derived as
Therefore we obtain
In a similar way, since $L_{1}(x_{i}) = 0$ for $i =0,2,3\cdots,n$, by the factor theorem, we obtain$L_{1}(x)$ can be written as
, where $\alpha_{1} $ is a constant.By $L_{1}(x_{1}) = 1$, it is derived as
. Therefore we obtain
By repeating the same discussion,we can derive $L_{j}(x)$ for $j = 0,1,\cdots, n$ as
. This expression can be written by the symbol $\prod$ as
$$\tag{5}$$
Substituing $(5)$ into $(3)$, we have
It is clear that this function passes through points $(1)$ (that is, it satisfies $(2)$), since $L_{j}(x)$ satisfies $(4)$.
Approximating the original function $f (x)$ with the polynomial function $p (x)$ defined in this way, that is,
is called Lagrange interpolation.
Lagrange's interpolation is a formula for finding a polynomial that approximates the function $f(x)$, but it simply derives a nth degree function passing through $n + 1$ given points.
Example 1: Linear interpolation
Let $f (x)$ be a function that passes through two points
.Find the linear function $p (x)$ that passes through these two points using Lagrange's interpolation formula.
Answer
Lagrange's interpolation formula that gives the linear function passing through two points
is
In this example,
We obtain
Example 2: Quadratic interpolation
Let $f (x)$ be a function that passes through three points
.Find the quadratic function $p (x)$ that passes through these three points using Lagrange's interpolation formula.
Answer
Lagrange's interpolation formula that gives the quadratic function passing through three points
is
In this example,
We obtain
Example 3: Cubic interpolation
Let $f (x)$ be a function that passes through four points
.Find the qubic function $p (x)$ that passes through these four points using Lagrange's interpolation formula.
Answer
Lagrange's interpolation formula that gives the qubic function passing through four points
is
In this example,
We obtain
Uniqueness
A polynomial of degree $n$
that passes through $n+1$ different points
$$\tag{1}$$is unique.There is no polynomial that passes though the different $n+1$ points and that is different from the Lagrange's interporation formula.
Proof
Problems solving a system of linear equations
Let $f(x)$ be a polynomial of degree $n$ defined as
, and that passes through $n+1$ different points,
. We have
$$ \tag{2}$$
Let $X$ be an $(n+1) \times (n+1)$ matrix, and $\mathbf{a}$ and $\mathbf{y}$ be $n$ dimensional vectors defined as
. Equations $(2)$ can be written as
$$\tag{3}$$
Equation $(3)$ ( or $(2)$) isa system of $n+1$ linear equations with $n+1$ unknowns.
$X$ is non-singular
In order for the function $f (x)$ to be unique, each coefficient $a_{0}, a_{1}, \cdots, a_{n}$ must be unique.To be so, the solution of system of linear equations $(2)$, that is $\mathbf{a}$, must be unique.
A necessary and sufficient condition for the system of linear equations whose coefficient matrix is a square matrix to have a single solution is that the coefficient matrix is a non-singular matrix (a matrix having and inverse matrix).Therefore, if it is shown that the coefficient matrix of $(3)$ is a non-singular matrix, it means that the solution of $(3)$ is unique.
Let us focus on the coefficient matrix $X$.The transpose matrix of $X$ is a Vandermonde matrix
It is known that the determinant of the Vandermonde matrix is given as
, where $\prod_{1 \leq i < j \leq n}$ means thatall $( x_{j}- x_{i} )$ are multiplied if $1 \leq i < j \leq n$.Specifically,
In our discussion,every $x_{i}$ is different.If $i \neq j$, $x_{i} \neq x_{j}$.We have
Generally, the determinant of the transposed matrix is equal to the determinant of the original matrix.We have
Since a matrix whose determinant is not $0$ is a non-singular matrix, $X$ is shown to be a non-singular matrix.
Conclusion
As described above, the coefficient matrix $ X $ of the system of linear equations $(3)$ is a non-singular matrix and therefore has the unique solution.Solving $(2)$ gives the unique coeffient $a_{0}, a_{1} \cdots, a_{n}$.The function of $f(x)$ is uniquely determined.Therefore,a function that passes through different $n+1$ points is unique.