This package provides methods for finding roots of a function using only calls to the derivatives of the function, never the function itself.
This can be useful when:
- Only local measurements are available. E.g., when climbing a mountain, one may not have access to an elevation device, but one can measure the local slope; Many fundamental physical quantities cannot be measured directly (entropy, energy, etc.) but their derivatives can -- e.g., temperature, tension, etc.
- When a numerical derivative function is provided, but access to the function itself requires a costly numerical integration. This can occur in applications involving the integration of differential equations.
Available strategies:
- Inchworm method: This gradually inches towards a root, at each step attempting to reduce the function by a constant amount. This method is preferred for highly curved functions, as it avoids "overshooting".
- Approximate Newton method: This method runs more quickly than the inchworm in our current python implementation, but can fail for highly curved functions.
[0] J. Landy and Y. Jho. Root finding via local measurement (2023) [link].
from inchwormrf import inchworm, newton
# goal: find fifth root of 3
y_function = lambda x: x ** 5 - 3
# derivatives -- note: accuracy improves w/ derivative count supplied
derivatives = [
lambda x: 5 * x ** 4, # 1st derivative of y_function
lambda x: 20 * x ** 3, # 2nd ...
lambda x: 60 * x ** 2, # 3rd ...
]
# call the inchworm root finder
inchworm_root = inchworm(
x0=2.0, # initial x value for search
y0=y_function(2.0), # function value at x0
N=10 ** 2, # inchworm steps to take
derivatives=derivatives, # ordered derivatives of y
newton_pass=True # final newton hop to reduce error
)
# call the approximate Newton root finder
newton_root = newton(
x0=2.0, # initial x value for search
y0=y_function(2.0), # function value at x0
N=10 ** 2, # derivative sample count
iterations=10, # newton hops to take
derivatives=derivatives, # ordered derivatives of y
)
print(inchworm_root, newton_root, 3 ** 0.2)
>> (1.2457309311200724, 1.2457309395803384, 1.2457309396155174)For an example where Newton's method fails but the inchworm does not, check
out (the highly-curved) y = |x|^(1/4) [0].
The package can be installed using pip, from pypi
pip install inchwormrf
or from github
pip install git+git://github.com/efavdb/inchwormrf.git
The test file contains many additional call examples. To run the tests, call the following from the root directory:
python setup.py test
This project is licensed under the terms of the MIT license.
Whereas most root finding methods (e.g., Newton's method, binary search, etc.)
attempt to iteratively refine a current best guess for a root of a function
y, the inchworm algorithm only generates a single root estimate at its
termination. It works by "inching" towards the root: If we start at a point
(x0, y0), and we ask to run the algorithm over N steps, the worm will
attempt to move downhill by dy = y0 / N with each step. It does this by
looking at the local geometry of the function at its current position -- the
slope, curvature, etc. [more formally: the worm evaluates the derivatives
passed to it, inverts the Taylor series for y that results, and then uses the
inverted series to estimate how far it needs to move in x to drop the
function by dy]. After completing N steps like this, the worm sits close
to a root (see figure).
Figure, example inching process: Our worm seeks a root in 4 steps. At
each step, the worm measures the local slope, and uses this to estimate how far
it must move in x to drop y by dy. The worm overshoots a bit here. Its
accuracy could be improved by (1) increasing the step count, (2) utilizing
higher derivative information, or (3) ending with an approximate Newton hop to
refine the estimate.
Newton's method involves iteratively fitting a line to a function at a current
location, and then moving to the root of this line, x -> x - y / y'. In this
way -- assuming convergence -- we can often reduce the error in the root
estiamte exponentially fast. Here, we intentionally do not allow calls to the
function itself, and so cannot read out the y value in the above formula. To
proceed, we need to get an estimate y_est for y. We get this by
approximating the integral of y' over the region we've covered so far. The
accuracy of this approimation improves with the number of derivatives we have
available. Our inchworm method makes use of the Newton hop method at the end
of its process -- when asked -- and the newton code exclusively applies this
process.
If k derivatives are passed, and we take N steps, the inching process will
return a root estimate whose error scales asymptotically like N^-k. This
means that we can improve our acccuracy by either increasing N or k.
If the optional, final Newton hop is taken, the root estimate returned will
scale asymptotically like N^-(2 * (k // 2) + 2). E.g., when k = 1
derivative is passed, this will give an error scaling as N^-2 -- a big gain
over the N^-1 scaling that we get without the hop. Running the approximate
Newton method on its own results in this same scaling.
We have written the inchworm method to be fully general -- it can accept any
number of derivatives. Unfortunately, this flexibility causes the code to run
somewhat slower than a method that is "hard-coded" for a particular number of
derivatives. This slowdown occurs mainly due to repeated list lookups that
occur within the algorithm's inching-process for loop.
To alleviate this issue, we have "hard-coded" the for loop for some of the
first simple cases here (for cases where up to 8 derivatives are passed). Our
main inchworm program farms out to these when requested. Directly calling
the hard-coded programs can give a modest, additional boost to speed. See the
tests for example calls to these methods.
To max out the speed of the inversion approach, one should hard code the method in a compiled language for the function of interest. Our code here should be relatively easy to port over.
Jonathan Landy - EFavDB
YongSeok Jho - Gyeongsang National University
We thank S. Landy and P. Pincus for helpful feedback.