For a given set of data points (t_i, y_i), i = 1, ..., n, rank the following thr

Question

For a given set of data points (t_i, y_i), i = 1, ..., n, rank the following three methods for polynomial interpolation according to the cost of determining the interpolant (i.e., determining the coefficients of the basis functions), from 1 for the cheapest to 3 for the most expensive: Monomial basis Lagrange basis Newton basis (b) Which of the three methods has the best-conditioned basis matrix A, where a_ij = Phi_j(t_i)? (c) For which of the three methods is evaluating the resulting interpolant at a given point the most expensive?

Explanation / Answer

Actually computing with it requires huge numbers and catastrophic cancellations. In floating point arithmetic this is very bad. It does have some small advantages: for instance, the Lagrange approach amounts to diagonalizing the problem of finding the coefficients, so it takes only linear time to find the coefficients. This is good if you need to use the same set of points repeatedly. But all of these advantages do not make up for the problems associated with trying to actually evaluate a Lagrange interpolating polynomial.

With Newton interpolation, you get the coefficients reasonably fast (quadratic time), the evaluation is much more stable (roughly because there is usually a single dominant term for a given xx), the evaluation can be done quickly and straightforwardly using Horner's method, and adding an additional node just amounts to adding a single additional term. It is also fairly easy to see how to interpolate derivatives using the Newton framework

(a) Monomial basis (3), Newton basis(2), Lagrange basis (1)

(b) Newton

(c) Lagrange

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.