<< Chapter < Page | Chapter >> Page > |
Lagrange's interpolation method is a simple and clever way of finding the unique $L$ th-order polynomial that exactly passes through $L+1$ distinct samples of a signal. Once the polynomial is known, its value can easily be interpolated at any pointusing the polynomial equation. Lagrange interpolation is useful in many applications, including Parks-McClellan FIR Filter Design .
Given an $L$ th-order polynomial $$P(x)={a}_{0}+{a}_{1}x+\mathrm{...}+{a}_{L}x^{L}=\sum_{k=0}^{L} {a}_{k}x^{k}$$ and $L+1$ values of $P({x}_{k})$ at different ${x}_{k}$ , $k\in \{0, 1, \mathrm{...}, L\}$ , ${x}_{i}\neq {x}_{j}$ , $i\neq j$ , the polynomial can be written as $$P(x)=\sum_{k=0}^{L} P({x}_{k})\frac{(x-{x}_{1})(x-{x}_{2})\mathrm{...}(x-{x}_{k-1})(x-{x}_{k+1})\mathrm{...}(x-{x}_{L})}{({x}_{k}-{x}_{1})({x}_{k}-{x}_{2})\mathrm{...}({x}_{k}-{x}_{k-1})({x}_{k}-{x}_{k+1})\mathrm{...}({x}_{k}-{x}_{L})}$$ The value of this polynomial at other $x$ can be computed via substitution into this formula, or by expanding this formula to determine the polynomial coefficients ${a}_{k}$ in standard form.
Note that for each term in the Lagrange interpolation formula above, $$\prod_{i=0,i\neq k}^{L} \frac{x-{x}_{i}}{{x}_{k}-{x}_{i}}=\begin{cases}1 & \text{if $x={x}_{k}$}\\ 0 & \text{if $(x={x}_{j})\land (j\neq k)$}\end{cases}$$ and that it is an $L$ th-order polynomial in $x$ . The Lagrange interpolation formula is thus exactly equal to $P({x}_{k})$ at all ${x}_{k}$ , and as a sum of $L$ th-order polynomials is itself an $L$ th-order polynomial.
It can be shown that the Vandermonde matrix $$\begin{pmatrix}1 & {x}_{0} & {x}_{0}^{2} & \mathrm{...} & {x}_{0}^{L}\\ 1 & {x}_{1} & {x}_{1}^{2} & \mathrm{...} & {x}_{1}^{L}\\ 1 & {x}_{2} & {x}_{2}^{2} & \mathrm{...} & {x}_{2}^{L}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & {x}_{L} & {x}_{L}^{2} & \mathrm{...} & {x}_{L}^{L}\\ \end{pmatrix}\left(\begin{array}{c}{a}_{0}\\ {a}_{1}\\ {a}_{2}\\ \vdots \\ {a}_{L}\end{array}\right)=\left(\begin{array}{c}P({x}_{0})\\ P({x}_{1})\\ P({x}_{2})\\ \vdots \\ P({x}_{L})\end{array}\right)$$ has a non-zero determinant and is thus invertible, so the $L$ th-order polynomial passing through all $L+1$ sample points ${x}_{j}$ is unique. Thus the Lagrange polynomial expressions, as an $L$ th-order polynomial passing through the $L+1$ sample points, must be the unique $P(x)$ .
Notification Switch
Would you like to follow the 'Digital filter design' conversation and receive update notifications?