GATE Mathematics Interpolation Flashcards

24 sample cards from the Interpolation deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. 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.

2. 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}$).

3. 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).$$

4. 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)|.$$

5. 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]$).

6. 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.

7. 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).

8. 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)$.

9. 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$.

10. 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$.

11. 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.

12. 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.

13. 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).$$

14. 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)}.$$

15. 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.

16. 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.

17. 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.

18. 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]$.

19. 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$.

20. 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}.$$

21. 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)}.$$

22. 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]$.

23. 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.

24. 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).

What this deck covers

Interpolation flashcards FAQ