Editing Polynomial interpolation (section)

=== Vandermonde Algorithms ===
The [[Vandermonde matrix]] in the second proof above may have large [[condition number]],<ref>{{cite journal |last=Gautschi |first=Walter |year=1975 |title=Norm Estimates for Inverses of Vandermonde Matrices |journal=Numerische Mathematik |volume=23 |issue=4 |pages=337–347 |doi=10.1007/BF01438260 |s2cid=122300795}}</ref> causing large errors when computing the coefficients {{math|''a<sub>i</sub>''}} if the system of equations is solved using [[Gaussian elimination]].

Several authors have therefore proposed algorithms which exploit the structure of the Vandermonde matrix to compute numerically stable solutions in O(''n''<sup>2</sup>) operations instead of the O(''n''<sup>3</sup>) required by Gaussian elimination.<ref>{{cite journal |last=Higham |first=N. J. |year=1988 |title=Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials |journal=IMA Journal of Numerical Analysis |volume=8 |issue=4 |pages=473–486 |doi=10.1093/imanum/8.4.473}}</ref><ref>{{cite journal |last=Björck |first=Å |author2=V. Pereyra |year=1970 |title=Solution of Vandermonde Systems of Equations |journal=Mathematics of Computation |publisher=American Mathematical Society |volume=24 |issue=112 |pages=893–903 |doi=10.2307/2004623 |jstor=2004623}}</ref><ref>{{cite journal |last1=Calvetti |first1=D. |author1-link=Daniela Calvetti |last2=Reichel |first2=L. |year=1993 |title=Fast Inversion of Vandermonde-Like Matrices Involving Orthogonal Polynomials |journal=BIT |volume=33 |issue=3 |pages=473–484 |doi=10.1007/BF01990529 |s2cid=119360991}}</ref> These methods rely on constructing first a [[Newton polynomial|Newton interpolation]] of the polynomial and then converting it to a [[monomial form]].