Is 2 the maximum order of convergence when finding roots?

Question

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?

Answer 1

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)¹ 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.}