.. _sphx_glr_api_gallery_numerical_analysis_polynomials:

Polynomials
-----------

Evaluating polynomials efficiently with Horner's scheme, and how
sensitive their roots can be to tiny changes in the coefficients.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Horner&#x27;s 1819 scheme rewrites a_n x^n + \dots + a_0 as nested multiplications, using n multiplications instead of the 2n - 1 of the term-by-term form. Its intermediate values are the coefficients of the quotient p(x) / (x - x_0), which gives the derivative for Newton&#x27;s method and lets a found root be divided out (&quot;deflation&quot;). This script finds all roots of a quartic that way and compares operation counts.">

.. only:: html

  .. image:: /api/gallery/numerical_analysis/polynomials/images/thumb/sphx_glr_plot_01_horner_method_thumb.png
    :alt:

  :doc:`/api/gallery/numerical_analysis/polynomials/plot_01_horner_method`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Horner's method: evaluation, derivative, and deflation</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="w(x) = (x - 1)(x - 2) \cdots (x - 20) has well separated integer roots, yet James Wilkinson found that subtracting 2^{-23} from its x^{19} coefficient, -210, sends ten of the roots far into the complex plane. The root condition numbers explain why: the roots near 16 amplify a relative change in that coefficient by a factor of about 3 \times 10^{10}.">

.. only:: html

  .. image:: /api/gallery/numerical_analysis/polynomials/images/thumb/sphx_glr_plot_02_wilkinson_polynomial_thumb.png
    :alt:

  :doc:`/api/gallery/numerical_analysis/polynomials/plot_02_wilkinson_polynomial`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Wilkinson's perfidious polynomial</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/numerical_analysis/polynomials/plot_01_horner_method
   /api/gallery/numerical_analysis/polynomials/plot_02_wilkinson_polynomial