Editing Polynomial interpolation (section)

=== Non-Vandermonde algorithms ===
To find the interpolation polynomial ''p''(''x'') in the vector space ''P''(''n'') of polynomials of degree {{mvar|n}}, we may use the usual [[monomial basis]] for ''P''(''n'') and invert the Vandermonde matrix by Gaussian elimination, giving a [[Computational complexity|computational cost]] of O(''n''<sup>3</sup>) operations. To improve this algorithm, a more convenient basis for ''P''(''n'') can simplify the calculation of the coefficients, which must then be translated back in terms of the [[monomial basis]].

One method is to write the interpolation polynomial in the [[Newton form]] (i.e. using Newton basis) and use the method of [[divided differences]] to construct the coefficients, e.g. [[Neville's algorithm]]. The cost is [[Big O notation|O(''n''<sup>2</sup>)]] operations. Furthermore, you only need to do O(''n'') extra work if an extra point is added to the data set, while for the other methods, you have to redo the whole computation.

Another method is preferred when the aim is not to compute the ''coefficients'' of ''p''(''x''), but only a ''single value'' ''p''(''a'') at a point ''x = a'' not in the original data set. The [[Lagrange form]] computes the value ''p''(''a'') with complexity O(''n''<sup>2</sup>).<ref>R.Bevilaqua, D. Bini, M.Capovani and O. Menchi (2003). ''Appunti di Calcolo Numerico''. Chapter 5, p. 89. Servizio Editoriale Universitario Pisa - Azienda Regionale Diritto allo Studio Universitario.</ref>

The [[Bernstein form]] was used in a constructive proof of the [[Weierstrass approximation theorem]] by [[Sergei Natanovich Bernstein|Bernstein]] and has gained great importance in computer graphics in the form of [[Bézier curve]]s.