Polynomials

A polynomial of degree n in z is a function

where z and the coefficients a_i can be real or complex. Two important application domains are the following:

• 1) Polynomial approximation, including data-fitting, interpolation, and computer representations of functions. One may use either a single polynomial for the whole range of the argument, or a family of polynomials each defined only over a subinterval, with continuity of a specified order of derivative at the junction points ( Spline Functions).
• 2) Many problems, e.g. eigenvalue computation, can be reduced to finding the roots of a polynomial equation P_n(z) = 0. Methods of solving these are of two kinds: global, which find all the roots at once; or simple, which find a single root a and then ``deflate the polynomial by dividing it by z-a before repeating the process.

 also Interpolation, Neville Algorithm, Pade Approximation. Some polynomials are ill-conditioned, i.e. the roots are very sensitive to small changes like truncation errors in the coefficients a_i, or the determination of the a_i suffers from their correlations. The use of orthogonal polynomials can overcome this. For practical fast computation of polynomial expressions, Horner's Rule.