2
$\begingroup$

Suppose we wish to find a simple root of a smooth univariate function $f$ near $x_0$, and that the below methods converge.


Newton's method has an order of convergence of $2$, Halley's method has an order of convergence of $3$, and higher order Householder methods have an order of convergence of $n$, meaning they give $n$ times more digits per iteration.

The problem with these methods is that they require computations of the derivatives of $f$, which can be costly to compute. By approximating the derivative with difference quotients, such as in Steffensen's method, we end up having to evaluate $f$ at a lot of points, which slows down the algorithm.

To determine how fast the algorithm actually runs then, we need to divide by the amount of function evaluations that must be computed per iteration.

This would actually put the Householder methods at an order of convergence of $\sqrt[n]n$, which converges fastest at $n=3$.


Questions:

My first question:

Accounting for the amount of function evaluations per iteration, and using a fixed amount per iteration, is it theoretically possible to have an order of convergence of $2$ or higher?

I know it is possible to achieve an order of convergence arbitrarily close to $2$ using generalizations of the secant method.

Interestingly, all of these generalizations also share the same order of convergence when the same amount of points are used:

When $k$ points are used, they all have order of convergence $\psi$ where $\psi$ is the largest real solution to $\psi^k=\psi^{k-1}+\dots+\psi+1$.

So my second question, supposing the answer to the first question is negative:

Using $k$ points per iteration, can an order of convergence greater than $\psi$ be obtained?

$\endgroup$
1
$\begingroup$

By that measure, also known as Ostrowski index, the secant method is fastest per function evaluation, with order $\phi=\frac{1+\sqrt5}2=1.6..$, followed by Newton with order $\sqrt2=1.4..$. Halley is still close to that, all others rapidly below.

Note the higher order divided difference quotients will be increasingly influenced by catastrophic cancellation or simply accumulation of floating point errors. Better use algorithmic differentiation, where then each derivative costs about 2 function evaluations, so that Newton has order $\sqrt[3]2$ and Halley the order $\sqrt[5]3$.

That's why the (probably misnamed)1 Householder methods of higher orders are not in widespread use.

1: There literally only exists the one source given in the wikipedia article I wrote summarizing it for that name. And that source is more a tech report that could also be called a blog in modern terms.

$\endgroup$
5
  • $\begingroup$ Out of the ones shown here, yes the secant is the best, but there are higher order generalizations of the secant method which only use one new evaluation per iteration. $\endgroup$ – Simply Beautiful Art Jul 3 '20 at 22:05
  • $\begingroup$ I'm not so interested in the latter point concerning the cancellations and floating point errors, being more interested in the case where computing $f$ is the biggest concern. $\endgroup$ – Simply Beautiful Art Jul 3 '20 at 22:09
  • $\begingroup$ If the coefficients have large errors, they are useless in computing the next root approximation to the expected error order. // For methods of sufficiently high convergence order the region-of-interest shrinks so fast that, if one "zooms in" the old iterates are stellar distances away, that is, not of sufficient importance in estimating the local behavior. Building models with a memory of more than 2 or 3 iterates makes only sense if the convergence is linear, or the function is known to be polynomial. $\endgroup$ – Lutz Lehmann Jul 3 '20 at 22:27
  • $\begingroup$ Yeah, that point was also of interest to me, even though extensions of the secant method using polynomial interpolation, inverse polynomial interpolation, and Sidi's method all claimed to give the order of convergence I mentioned in my second question, I had doubts that using more points would actually help since they converged so fast, though I've not seen a source concerning this detail. $\endgroup$ – Simply Beautiful Art Jul 3 '20 at 22:38
  • $\begingroup$ After running tests with methods such as Chandrupatla's method and Brent's method, I've found that often the claimed Ostrowski index does go up to $1.839$ (sometimes at least, due to bracketing requirements) and interpolating with more points likely goes higher. The difference between this and $1.618$ is actually noticeable, even when working to only $16$ significant figures. As far as bracketing methods go though, using an even amount of points actually degenerates down to one less point in the manner you've described, with one point far out. $\endgroup$ – Simply Beautiful Art Aug 28 '20 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.