Home page


Using Newton-Raphson to solve polynomials

Updated June 2011

Introduction

The "Newton-Raphson" method is an algorithm for finding the roots of differentiable equations. See Wolfram or Wikipedia

This page allows you to download a python script that will find the roots of a polynomial with real coefficients.

Usage

The Newton-Raphson method can be applied to any differentiable equation y = f(x), but the python code presented here is designed to work with polynomials:

 y = P0xn + P1xn-1 + ... + Pn        

which in the Python code are represented as vectors [P0, P1, ..., Pn]. The derivative of a single polynomial term, Pxn is nPxn-1, and the derivative of the whole polynomial is [nP0, (n-1)P1, ..., Pn-1].

 Derivative (x3 + x2 + x + 1) = 3x2 + 2x + 1

 becomes

 Derivative ([1,1,1,1]) = [3,2,1] 

Note: the derivative has one fewer terms than the original polynomial.

So, to solve a polynomial, say x6 + 2x5 + 3x4 + 4x3 + 5x2 + 6x + 7 = 0, you first have to convert it to a vector, in this case [1,2,3,4,5,6,7].

Now you can load the python script and call the "FindRoots" method.

>>> import Polynomial
>>> Polynomial.FindRoots ([1,2,3,4,5,6,7])
[(-1.3078697439524358+0.59329470741458734j),
(-1.3078697439524358-0.59329470741458734j),
(-0.40250912536027966+1.3416668277593837j),
(-0.40250912536027966-1.3416668277593837j),
(0.71037886931271566+1.1068452983838484j),
(0.71037886931271566-1.1068452983838484j)]
>>> 

All six roots of this polynomial are complex and come in three conjugate pairs: (-1.308 ± 0.593i), (-0.403 ± 1.342i) and (0.710 ± 1.107i).

(c) John Whitehouse 2010