Created
March 1, 2018 23:42
-
-
Save mikofski/4026cb11c0f91a24028940fdd9b01921 to your computer and use it in GitHub Desktop.
Comparison of scalar scipy.optimze.zeros.newton from v1.0.0 with proposed vectorized version from pr #8357
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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