Refine polynomial roots using Newton–Raphson

This is an implementation of the Newton–Raphson algorithm to approximate roots of complex polynomials. The implementation is based on interval arithmetic

AUTHORS:

• Carl Witty (2007-11-18): initial version

sage.rings.polynomial.refine_root.refine_root(ip, ipd, irt, fld)

We are given a polynomial and its derivative (with complex interval coefficients), an estimated root, and a complex interval field to use in computations. We use interval arithmetic to refine the root and prove that we have in fact isolated a unique root.

If we succeed, we return the isolated root; if we fail, we return None.

EXAMPLES:

Sage

sage: # needs sage.symbolic
sage: from sage.rings.polynomial.refine_root import refine_root
sage: x = polygen(ZZ)
sage: p = x^9 - 1
sage: ip = CIF['x'](p); ip
x^9 - 1
sage: ipd = CIF['x'](p.derivative()); ipd
9*x^8
sage: irt = CIF(CC(cos(2*pi/9), sin(2*pi/9))); irt
0.76604444311897802? + 0.64278760968653926?*I
sage: ip(irt)
0.?e-14 + 0.?e-14*I
sage: ipd(irt)
6.89439998807080? - 5.78508848717885?*I
sage: refine_root(ip, ipd, irt, CIF)
0.766044443118978? + 0.642787609686540?*I

Python

>>> from sage.all import *
>>> # needs sage.symbolic
>>> from sage.rings.polynomial.refine_root import refine_root
>>> x = polygen(ZZ)
>>> p = x**Integer(9) - Integer(1)
>>> ip = CIF['x'](p); ip
x^9 - 1
>>> ipd = CIF['x'](p.derivative()); ipd
9*x^8
>>> irt = CIF(CC(cos(Integer(2)*pi/Integer(9)), sin(Integer(2)*pi/Integer(9)))); irt
0.76604444311897802? + 0.64278760968653926?*I
>>> ip(irt)
0.?e-14 + 0.?e-14*I
>>> ipd(irt)
6.89439998807080? - 5.78508848717885?*I
>>> refine_root(ip, ipd, irt, CIF)
0.766044443118978? + 0.642787609686540?*I

Sage Live

# needs sage.symbolic
from sage.rings.polynomial.refine_root import refine_root
x = polygen(ZZ)
p = x^9 - 1
ip = CIF['x'](p); ip
ipd = CIF['x'](p.derivative()); ipd
irt = CIF(CC(cos(2*pi/9), sin(2*pi/9))); irt
ip(irt)
ipd(irt)
refine_root(ip, ipd, irt, CIF)

Make live