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)[source]#
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: # 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
>>> 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