NumericalMath`InterpolateRoot`
The function FindRoot is useful for finding a root of a function. It is fairly robust and will almost always find a root if it is given a sufficiently close starting value and the root is simple (or if it is multiple and the option DampingFactor is appropriately set). To achieve this robustness FindRoot makes compromises and is not particularly conservative about the number of function evaluations it uses. There are cases, however, where you know that the function is very well behaved, but evaluating it is extremely expensive, particularly for very high precision. In such cases InterpolateRoot may be more efficient.
InterpolateRoot looks at previous evaluations of the function, say , , , and and forms the interpolating polynomial which passes through the points , , , and . The algorithm gets the next approximation for the root of by evaluating the interpolating polynomial at . It turns out that using all of the previous data is not the best strategy. While the convergence rate increases with the use of additional data points, the rate is never greater than quadratic. Further, the more data points used, the less robust the algorithm becomes. InterpolateRoot uses only the previous four data points since there is almost no benefit to using more.
Root finding with InterpolateRoot.
Options for InterpolateRoot.
The Automatic choice for AccuracyGoal means that the AccuracyGoal will be chosen to be digits less than the WorkingPrecision. It should be noted that AccuracyGoal as used in InterpolateRoot is different from AccuracyGoal in FindRoot. FindRoot is a much more general function that works for systems of equations. Trying to justify an accuracy in the value of the root itself is too difficult. FindRoot merely stops when the value of the function is sufficiently small. InterpolateRoot is much more specialized. It only works for a single function of a single variable at simple roots and assumes that the function is very well behaved. In such cases it is quite easy to justify an accuracy in the value of the root itself.
This loads the package.
In[1]:= <<NumericalMath`InterpolateRoot`
Set up a function whose root we wish to find, with a counter to determine the number of evaluations.
In[2]:= f[x_?NumberQ] := (n++; Exp[x]  2)
This uses FindRoot to find Log[2].
In[3]:= n = 0; FindRoot[f[x], {x, 0, 1}, WorkingPrecision > 800, AccuracyGoal > 795]
Out[3]=
Here is the number of function evaluations to get the result.
In[4]:= n
Out[4]=
InterpolateRoot requires fewer function evaluations to get the same result.
In[5]:= n = 0; InterpolateRoot[f[x], {x, 0, 1}, WorkingPrecision > 800, AccuracyGoal > 795]; n
Out[5]=
You can observe how the approximations converge to the root.
In[6]:= InterpolateRoot[Exp[x] == 2, {x, 0, 1}, ShowProgress > True, WorkingPrecision > 40]
Out[6]=
