Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Comparison of scalar scipy.optimze.zeros.newton from v1.0.0 with proposed vectorized version from pr #8357
from __future__ import division, print_function, absolute_import
from math import sqrt, exp, sin, cos
import warnings
import numpy as np
# Newton-Raphson method
def scalar_newton(func, x0, fprime=None, args=(), tol=1.48e-8, maxiter=50,
fprime2=None):
"""
Find a zero using the Newton-Raphson or secant method.
Find a zero of the function `func` given a nearby starting point `x0`.
The Newton-Raphson method is used if the derivative `fprime` of `func`
is provided, otherwise the secant method is used. If the second order
derivate `fprime2` of `func` is provided, parabolic Halley's method
is used.
Parameters
----------
func : function
The function whose zero is wanted. It must be a function of a
single variable of the form f(x,a,b,c...), where a,b,c... are extra
arguments that can be passed in the `args` parameter.
x0 : float
An initial estimate of the zero that should be somewhere near the
actual zero.
fprime : function, optional
The derivative of the function when available and convenient. If it
is None (default), then the secant method is used.
args : tuple, optional
Extra arguments to be used in the function call.
tol : float, optional
The allowable error of the zero value.
maxiter : int, optional
Maximum number of iterations.
fprime2 : function, optional
The second order derivative of the function when available and
convenient. If it is None (default), then the normal Newton-Raphson
or the secant method is used. If it is given, parabolic Halley's
method is used.
Returns
-------
zero : float
Estimated location where function is zero.
See Also
--------
brentq, brenth, ridder, bisect
fsolve : find zeroes in n dimensions.
Notes
-----
The convergence rate of the Newton-Raphson method is quadratic,
the Halley method is cubic, and the secant method is
sub-quadratic. This means that if the function is well behaved
the actual error in the estimated zero is approximately the square
(cube for Halley) of the requested tolerance up to roundoff
error. However, the stopping criterion used here is the step size
and there is no guarantee that a zero has been found. Consequently
the result should be verified. Safer algorithms are brentq,
brenth, ridder, and bisect, but they all require that the root
first be bracketed in an interval where the function changes
sign. The brentq algorithm is recommended for general use in one
dimensional problems when such an interval has been found.
Examples
--------
>>> def f(x):
... return (x**3 - 1) # only one real root at x = 1
>>> from scipy import optimize
``fprime`` and ``fprime2`` not provided, use secant method
>>> root = optimize.newton(f, 1.5)
>>> root
1.0000000000000016
Only ``fprime`` provided, use Newton Raphson method
>>> root = optimize.newton(f, 1.5, fprime=lambda x: 3 * x**2)
>>> root
1.0
``fprime2`` provided, ``fprime`` provided/not provided use parabolic
Halley's method
>>> root = optimize.newton(f, 1.5, fprime2=lambda x: 6 * x)
>>> root
1.0000000000000016
>>> root = optimize.newton(f, 1.5, fprime=lambda x: 3 * x**2,
... fprime2=lambda x: 6 * x)
>>> root
1.0
"""
if tol <= 0:
raise ValueError("tol too small (%g <= 0)" % tol)
if maxiter < 1:
raise ValueError("maxiter must be greater than 0")
if fprime is not None:
# Newton-Rapheson method
# Multiply by 1.0 to convert to floating point. We don't use float(x0)
# so it still works if x0 is complex.
p0 = 1.0 * x0
fder2 = 0
for iter in range(maxiter):
myargs = (p0,) + args
fder = fprime(*myargs)
if fder == 0:
msg = "derivative was zero."
warnings.warn(msg, RuntimeWarning)
return p0
fval = func(*myargs)
if fprime2 is not None:
fder2 = fprime2(*myargs)
if fder2 == 0:
# Newton step
p = p0 - fval / fder
else:
# Parabolic Halley's method
discr = fder ** 2 - 2 * fval * fder2
if discr < 0:
p = p0 - fder / fder2
else:
p = p0 - 2*fval / (fder + np.sign(fder) * sqrt(discr))
if abs(p - p0) < tol:
return p
p0 = p
else:
# Secant method
p0 = x0
if x0 >= 0:
p1 = x0*(1 + 1e-4) + 1e-4
else:
p1 = x0*(1 + 1e-4) - 1e-4
q0 = func(*((p0,) + args))
q1 = func(*((p1,) + args))
for iter in range(maxiter):
if q1 == q0:
if p1 != p0:
msg = "Tolerance of %s reached" % (p1 - p0)
warnings.warn(msg, RuntimeWarning)
return (p1 + p0)/2.0
else:
p = p1 - q1*(p1 - p0)/(q1 - q0)
if abs(p - p1) < tol:
return p
p0 = p1
q0 = q1
p1 = p
q1 = func(*((p1,) + args))
msg = "Failed to converge after %d iterations, value is %s" % (maxiter, p)
raise RuntimeError(msg)
# Newton-Raphson method
def array_newton(func, x0, fprime=None, args=(), tol=1.48e-8, maxiter=50,
fprime2=None):
"""
Find a zero using the Newton-Raphson or secant method.
Find a zero of the function `func` given a nearby starting point `x0`.
The Newton-Raphson method is used if the derivative `fprime` of `func`
is provided, otherwise the secant method is used. If the second order
derivate `fprime2` of `func` is provided, parabolic Halley's method
is used.
Parameters
----------
func : function
The function whose zero is wanted. It must be a function of a
single variable of the form f(x,a,b,c...), where a,b,c... are extra
arguments that can be passed in the `args` parameter.
x0 : float
An initial estimate of the zero that should be somewhere near the
actual zero.
fprime : function, optional
The derivative of the function when available and convenient. If it
is None (default), then the secant method is used.
args : tuple, optional
Extra arguments to be used in the function call.
tol : float, optional
The allowable error of the zero value.
maxiter : int, optional
Maximum number of iterations.
fprime2 : function, optional
The second order derivative of the function when available and
convenient. If it is None (default), then the normal Newton-Raphson
or the secant method is used. If it is given, parabolic Halley's
method is used.
Returns
-------
zero : float
Estimated location where function is zero.
See Also
--------
brentq, brenth, ridder, bisect
fsolve : find zeroes in n dimensions.
Notes
-----
The convergence rate of the Newton-Raphson method is quadratic,
the Halley method is cubic, and the secant method is
sub-quadratic. This means that if the function is well behaved
the actual error in the estimated zero is approximately the square
(cube for Halley) of the requested tolerance up to roundoff
error. However, the stopping criterion used here is the step size
and there is no guarantee that a zero has been found. Consequently
the result should be verified. Safer algorithms are brentq,
brenth, ridder, and bisect, but they all require that the root
first be bracketed in an interval where the function changes
sign. The brentq algorithm is recommended for general use in one
dimensional problems when such an interval has been found.
Examples
--------
>>> def f(x):
... return (x**3 - 1) # only one real root at x = 1
>>> from scipy import optimize
``fprime`` and ``fprime2`` not provided, use secant method
>>> root = optimize.newton(f, 1.5)
>>> root
1.0000000000000016
Only ``fprime`` provided, use Newton Raphson method
>>> root = optimize.newton(f, 1.5, fprime=lambda x: 3 * x**2)
>>> root
1.0
``fprime2`` provided, ``fprime`` provided/not provided use parabolic
Halley's method
>>> root = optimize.newton(f, 1.5, fprime2=lambda x: 6 * x)
>>> root
1.0000000000000016
>>> root = optimize.newton(f, 1.5, fprime=lambda x: 3 * x**2,
... fprime2=lambda x: 6 * x)
>>> root
1.0
"""
if tol <= 0:
raise ValueError("tol too small (%g <= 0)" % tol)
if maxiter < 1:
raise ValueError("maxiter must be greater than 0")
if fprime is not None:
# Newton-Rapheson method
# Multiply by 1.0 to convert to floating point. We don't use float(x0)
# so it still works if x0 is complex.
p0 = 1.0 * np.asarray(x0) # convert to ndarray
for iter in range(maxiter):
myargs = (p0,) + args
fder = np.asarray(fprime(*myargs)) # convert to ndarray
if (fder == 0).any():
msg = "derivative was zero."
warnings.warn(msg, RuntimeWarning)
return p0
fval = np.asarray(func(*myargs)) # convert to ndarray
if fprime2 is None:
# Newton step
p = p0 - fval / fder
else:
fder2 = np.asarray(fprime2(*myargs)) # convert to ndarray
# Halley's method
# https://en.wikipedia.org/wiki/Halley%27s_method
p = p0 - 2 * fval * fder / (2 * fder ** 2 - fval * fder2)
if np.abs(p - p0).max() < tol:
return p
p0 = p
else:
# Secant method
p0 = np.asarray(x0)
dx = np.finfo(float).eps**0.33
dp = np.where(p0 >= 0, dx, -dx)
p1 = p0 * (1 + dx) + dp
q0 = np.asarray(func(*((p0,) + args)))
q1 = np.asarray(func(*((p1,) + args)))
for iter in range(maxiter):
divide_by_zero = (q1 == q0)
if divide_by_zero.any():
tolerance_reached = (p1 != p0)
if (divide_by_zero & tolerance_reached).any():
msg = "Tolerance of %s reached" % np.sqrt(sum((p1 - p0)**2))
warnings.warn(msg, RuntimeWarning)
return (p1 + p0)/2.0
else:
p = p1 - q1*(p1 - p0)/(q1 - q0)
if np.abs(p - p1).max() < tol:
return p
p0 = p1
q0 = q1
p1 = p
q1 = np.asarray(func(*((p1,) + args)))
msg = "Failed to converge after %d iterations, value is %s" % (maxiter, p)
raise RuntimeError(msg)
def test_newton(method):
f1 = lambda x: x**2 - 2*x - 1
f1_1 = lambda x: 2*x - 2
f1_2 = lambda x: 2.0 + 0*x
f2 = lambda x: exp(x) - cos(x)
f2_1 = lambda x: exp(x) + sin(x)
f2_2 = lambda x: exp(x) + cos(x)
for f, f_1, f_2 in [(f1, f1_1, f1_2), (f2, f2_1, f2_2)]:
x = method(f, 3, tol=1e-6)
x = method(f, 3, fprime=f_1, tol=1e-6)
x = method(f, 3, fprime=f_1, fprime2=f_2, tol=1e-6)
def test_newton_array(method):
"""test newton with array"""
def f1(x, *a):
b = a[0] + x * a[3]
return a[1] - a[2] * (np.exp(b / a[5]) - 1.0) - b / a[4] - x
def f1_1(x, *a):
b = a[3] / a[5]
return -a[2] * np.exp(a[0] / a[5] + x * b) * b - a[3] / a[4] - 1
def f1_2(x, *a):
b = a[3] / a[5]
return -a[2] * np.exp(a[0] / a[5] + x * b) * b ** 2
args = (5.32725221, 7.0, 1e-09, 0.004, 10, 0.27456)
x0 = 7.0
x = method(f1, x0, f1_1, args)
# test halley's
x = method(f1, x0, f1_1, args, fprime2=f1_2)
# test secant
x = method(lambda y, z: z - y ** 2, 4.0, args=(15.0,))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.