GATE Mathematics Interpolation Syllabus

How is the $n$-th divided difference related to the $n$-th derivative of $f$?

There exists $\xi$ in the interval spanning the nodes with $$f[x_0,\dots,x_n]=\frac{f^{(n)}(\xi)}{n!}.$$

Define the forward difference operator $\Delta$.

$\Delta f(x_i)=f(x_{i+1})-f(x_i)=f_{i+1}-f_i$. Higher orders: $\Delta^{k}f_i=\Delta^{k-1}f_{i+1}-\Delta^{k-1}f_i$.

State the Newton's forward difference interpolation formula for equally spaced nodes with step $h$ and $s=\frac{x-x_0}{h}$.

$$P(x)=f_0+\sum_{k=1}^{n}\binom{s}{k}\Delta^{k}f_0,\quad \binom{s}{k}=\frac{s(s-1)\cdots(s-k+1)}{k!}.$$

State Newton's backward difference interpolation formula with $s=\frac{x-x_n}{h}$.

$$P(x)=f_n+\sum_{k=1}^{n}\binom{s+k-1}{k}\nabla^{k}f_n,$$ where $\nabla f_i=f_i-f_{i-1}$ is the backward difference.

For equally spaced nodes, relate the divided difference to the forward difference.

$$f[x_0, x_1, \dots, x_k]=\frac{\Delta^{k} f_0}{k!\,h^{k}},$$ where $h$ is the constant spacing.

When is Newton's forward difference formula preferred over the backward formula?

Forward differences are best for interpolating near the beginning of the table (small $x$, near $x_0$); backward differences are best near the end of the table (near $x_n$).

State the interpolation error formula for a polynomial of degree $\leq n$ interpolating $f$ at nodes $x_0, \dots, x_n$.

$$f(x)-P(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x-x_i),$$ for some $\xi$ in the smallest interval containing $x$ and the nodes.

In the interpolation error formula, what is the node polynomial and how is it denoted?

$\omega_{n+1}(x)=\prod_{i=0}^{n}(x-x_i)$, a monic polynomial of degree $n+1$ that vanishes at all interpolation nodes.

What conditions are required for the standard interpolation error formula to hold?

$f$ must be $(n+1)$-times continuously differentiable on the interval containing all the nodes and the evaluation point $x$ (i.e. $f \in C^{n+1}$).

Express the interpolation error in terms of divided differences including the point $x$.

$$f(x)-P(x)=f[x_0, x_1, \dots, x_n, x]\prod_{i=0}^{n}(x-x_i).$$

Give an upper bound for the magnitude of the interpolation error.

$$|f(x)-P(x)| \leq \frac{M_{n+1}}{(n+1)!}\Big|\prod_{i=0}^{n}(x-x_i)\Big|,\quad M_{n+1}=\max_{t}|f^{(n+1)}(t)|.$$

What is Runge's phenomenon?

For high-degree polynomial interpolation on equally spaced nodes, large oscillations of the error appear near the ends of the interval, and the error can grow as $n$ increases (e.g. for $f(x)=\frac{1}{1+25x^{2}}$ on $[-1,1]$).

How can Runge's phenomenon be mitigated?

Use non-uniform nodes clustered toward the endpoints — especially Chebyshev nodes — or use piecewise (spline) interpolation instead of a single high-degree polynomial.

What choice of interpolation nodes minimizes the maximum of $|\omega_{n+1}(x)|$ on $[-1,1]$?

The Chebyshev nodes, the roots of the Chebyshev polynomial $T_{n+1}$: $$x_k=\cos\!\left(\frac{2k+1}{2(n+1)}\pi\right),\quad k=0,\dots,n,$$ which minimize the node-polynomial sup norm (equioscillation).

For Chebyshev nodes on $[-1,1]$, what is the minimized maximum value of the monic node polynomial $|\omega_{n+1}(x)|$?

$$\max_{x\in[-1,1]}|\omega_{n+1}(x)|=\frac{1}{2^{n}},$$ achieved by the monic Chebyshev polynomial $2^{-n}T_{n+1}(x)$.

State the linear interpolation error bound for step size $h$ between two nodes.

For linear ($n=1$) interpolation on $[x_0,x_1]$ with $h=x_1-x_0$: $$|f(x)-P_1(x)| \leq \frac{h^{2}}{8}\max|f''(\xi)|,$$ since $\max|(x-x_0)(x-x_1)|=h^{2}/4$.

What is Hermite interpolation?

Interpolation that matches not only function values $f(x_i)$ but also derivative values $f'(x_i)$ (and possibly higher derivatives) at the nodes; with $n+1$ nodes matching value and first derivative, the polynomial has degree $\leq 2n+1$.

What is the degree of the Hermite interpolating polynomial matching $f$ and $f'$ at $n+1$ nodes?

Degree at most $2n+1$, since there are $2(n+1)=2n+2$ interpolation conditions to satisfy.

Compare Lagrange and Newton forms in terms of computational efficiency for evaluation.

Newton's form, evaluated by nested (Horner-like) multiplication, costs $O(n)$ per point after $O(n^2)$ setup of divided differences. Lagrange's barycentric form is also $O(n)$, but the naive Lagrange form is $O(n^2)$ per evaluation point.

Write the (first form) barycentric Lagrange interpolation formula with weights $w_i$.

$$P(x)=\omega(x)\sum_{i=0}^{n}\frac{w_i}{x-x_i}y_i,\quad w_i=\frac{1}{\prod_{j\neq i}(x_i-x_j)},\ \omega(x)=\prod_{i}(x-x_i).$$

Write the second (true) barycentric form of the Lagrange interpolant.

$$P(x)=\frac{\displaystyle\sum_{i=0}^{n}\frac{w_i}{x-x_i}y_i}{\displaystyle\sum_{i=0}^{n}\frac{w_i}{x-x_i}},\quad w_i=\frac{1}{\prod_{j\neq i}(x_i-x_j)}.$$

What is the divided difference $f[x_i]$ of order zero?

The function value itself: $f[x_i]=f(x_i)=y_i$. These form the first column of the divided-difference table.

Distinguish interpolation from extrapolation.

Interpolation estimates values at points inside the range of the data nodes $[x_0, x_n]$; extrapolation estimates outside that range and is far less reliable, with rapidly growing error.

How does the interpolation error formula simplify when interpolating a polynomial of degree $\leq n$?

If $f$ is itself a polynomial of degree $\leq n$, then $f^{(n+1)}\equiv 0$, so the error is exactly zero — polynomial interpolation reproduces such $f$ exactly.

In a divided-difference table, what does each successive column represent?

Each column holds divided differences of one higher order: column $0$ is $f[x_i]$, column $1$ is $f[x_i,x_{i+1}]$, column $2$ is $f[x_i,x_{i+1},x_{i+2}]$, and so on up to $f[x_0,\dots,x_n]$.

What is inverse interpolation and what is it used for?

Inverse interpolation interpolates $x$ as a function of $y$ (swapping roles of independent and dependent variables), commonly used to estimate the value of $x$ giving a target $y$, e.g. finding a root where $y=0$.

State the error term for Newton's forward difference interpolation formula.

$$E(x)=\binom{s}{n+1}h^{n+1}f^{(n+1)}(\xi)=\frac{s(s-1)\cdots(s-n)}{(n+1)!}h^{n+1}f^{(n+1)}(\xi),\quad s=\frac{x-x_0}{h}.$$

For the quadratic interpolant ($n=2$), write the Lagrange form through three points.

$$P(x)=y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}+y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}.$$

What is the relationship between the leading coefficient of the interpolating polynomial and a divided difference?

The leading (degree-$n$) coefficient of the unique interpolant equals the top divided difference $f[x_0, x_1, \dots, x_n]$.

Why is piecewise (spline) interpolation often preferred over a single high-degree global polynomial?

Low-degree piecewise polynomials (e.g. cubic splines) avoid Runge's oscillations, are numerically stable, give smooth fits, and keep error controlled locally, whereas a single high-degree interpolant can oscillate wildly between nodes.

Summarize how interpolation error depends on the number of nodes and smoothness of $f$.

Error scales with $\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod(x-x_i)$: more nodes raise the order (smaller $\frac{1}{(n+1)!}$ and node spacing) but require higher derivatives to stay bounded. For smooth $f$ with well-chosen (Chebyshev) nodes, error decreases rapidly; for limited smoothness or equispaced nodes it may grow (Runge).