Newton's method without a derivative

Where Newton’s method goes instead ran the method from every starting point at once and coloured each point by the root it reached; a cubic method that is Newton’s in disguise added a second derivative and got Halley’s method, which cubes its error where Newton squares it. Both methods spend derivatives. Each step of Newton’s method evaluates the function and its slope at the current guess and follows the tangent line down to the axis, and a method that uses more derivatives converges faster per step and costs more per step.

The secant method goes the other way. It keeps no derivative at all. It remembers the last two guesses, draws the chord through the two points of the graph above them, and follows that chord down to the axis:

$$x_2 = x_1 - f(x_1)\,\frac{x_1 - x_0}{f(x_1) - f(x_0)}.$$

The chord is a tangent made from finite differences, and the method is what Newton’s becomes when the slope is estimated rather than computed. Its ancestor, the rule of double false position, is in the Chinese Nine Chapters two thousand years ago. The cost of dropping the derivative is a second starting value, and the second starting value changes the geometry of the method completely. A Newton step is a map of the line to itself; a secant step is a map of pairs, $(x_0, x_1) \mapsto (x_1, x_2)$, and its basins are regions of a plane.

A plane of starting pairs #

The cubic $x^3 - x$ has three roots, $-1$, $0$ and $1$, and the hero runs the secant method from each of 32,400 starting pairs and records where it ends, to within $10^{-12}$. The plane is shared out unevenly: 36.9% of the pairs reach 0, 31.4% reach each of $\pm 1$ — the two shares equal because the cubic is odd, so the pair $(x_0, x_1)$ and the pair $(-x_0, -x_1)$ go to opposite roots — and 0.4% reach nothing, either because a chord comes out horizontal and the next step is undefined, or because the iterates run off to infinity.

The regions are large and their boundaries are not. Where two basins meet the boundary winds through the plane in tangled curves, and near them a starting pair that moves by a fraction of a grid square changes the root it reaches — the same sensitivity at the boundary that Newton’s method showed on its line, now spread along curves instead of concentrated at points. The basins are also not symmetric under swapping the two starting values: $(x_0, x_1)$ and $(x_1, x_0)$ draw the same chord, but the method remembers $x_1$ as the more recent guess and keeps it, so the next pair differs. The plane has a preferred direction, and the picture is not symmetric about its diagonal.

The diagonal itself is special. When $x_0 = x_1$ the chord is undefined, but as $x_0$ approaches $x_1$ it approaches the tangent at $x_1$, and the secant step approaches the Newton step. Newton’s method is the limit of the secant method on the line $x_0 = x_1$, and the line’s own basins — the intervals of starting points that Newton sends to each root — are the diagonal slice of the plane in the hero, seen at a resolution the plane’s grid cannot show.

Where a chord goes flat #

Newton’s method fails where the tangent is horizontal, at the points where $f' = 0$ — for $x^3 - x$, at $\pm 1/\sqrt 3$ — and then at the points that land there after one step, two steps, and so on. Those failures are isolated points on the line. The secant method fails where the chord is horizontal, where $f(x_0) = f(x_1)$ with $x_0 \ne x_1$, and for this cubic that is a curve. Subtracting,

$$x_0^3 - x_0 - (x_1^3 - x_1) = (x_0 - x_1)(x_0^2 + x_0x_1 + x_1^2 - 1),$$

so apart from the diagonal the first chord is flat exactly on the ellipse $x_0^2 + x_0x_1 + x_1^2 = 1$, tilted along the line $x_0 = -x_1$. The figure marks the grid squares where the first chord is nearly flat, and they trace the ellipse drawn dashed over them.

The second step fails where the pair after one step lands on the ellipse, which is the ellipse’s preimage under the secant map: the blue curves, which leave the ellipse’s neighbourhood in four arcs reaching out to the corners of the square. The third step fails on the preimages of those, the green curves, and so on for ever. Each preimage is a curve that the map folds onto the one before, and the union of all of them is the skeleton along which the basins of the hero meet. Newton’s method has countably many bad points on its line; the secant method has countably many bad curves in its plane, which is what a map of two variables makes of the same failure.

Errors that multiply #

Near a simple root $r$ the secant method converges fast, and the way it does so is the arithmetic heart of the method. Write $e_k = x_k - r$ for the errors. Expanding $f$ about the root to second order and substituting into the secant formula, the first-order terms cancel and what remains is

$$e_2 \approx C\,e_1 e_0, \qquad C = \frac{f''(r)}{2f'(r)}.$$

Each error is the constant $C$ times the product of the two errors before it. Newton’s method has $e_1 \approx C e_0^2$, the square of one error; the secant method has the product of two different ones, because its chord is built from two points. Take logarithms and the product becomes a sum: the number of correct digits at each step is about the sum of the numbers at the two steps before, less a fixed amount from $C$. That is the Fibonacci recurrence.

The figure runs the method on $x^2 - 2$ from the starting pair 1 and 2, carrying every iterate exactly to 3,000 decimal digits, and counts the correct digits of $\sqrt 2$ at each step: 0, 0, 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 288, 466, 755, 1,222, 1,977. Each is close to the sum of the two before it, and within a few of twice a Fibonacci number less one — $2 \cdot 55 - 1 = 109$, $2 \cdot 89 - 1 = 177$ — the small drift coming from $C = 1/(2\sqrt 2)$, which costs about half a digit at every step. The ratios of successive counts settle on $1.618$, the golden ratio $\varphi$: the order of the secant method is $\varphi$, because the Fibonacci numbers grow by $\varphi$, which the rectangle that eats itself defined as the ratio that reproduces itself when a square is cut off.

A constant that does not move #

The relation $e_2 \approx C e_1 e_0$ is a prediction with a number in it, and the figure tests the number. For three functions it runs the secant method in 3,000-digit arithmetic and divides each error by the product of the two before: for $x^2 - 2$ near $\sqrt 2$, where $C = 1/(2\sqrt 2) = 0.3536$; for $x^3 - 2$ near $\sqrt[3]2$, where $C = 2^{-1/3} = 0.7937$; and for $x^3 - x$ near 1, where $f'(1) = 2$ and $f''(1) = 6$ give $C = 1.5$. Each ratio settles on its level within four or five steps and then holds it, to three decimals, for a dozen steps more, until the errors pass the 3,000 digits carried.

The constancy is what makes the golden ratio exact. If the errors satisfied $e_2 = C e_1 e_0$ exactly, then $\log e_k$ would satisfy a linear recurrence whose solutions grow like $\varphi^k$ — the characteristic equation is $\lambda^2 = \lambda + 1$ — and the order would be $\varphi$ precisely. The approximation is only second order, but the corrections shrink as fast as the errors do, and the measured ratio of 1.6178 after fourteen steps is the golden ratio to four places. The constant $C$ is the same one that governs Newton’s method, whose error is $C e^2$: both methods see the same curvature of the function at the root, and differ only in which two errors they multiply.

Cheaper per digit than Newton #

How fast the staircase arrives quoted the order of the secant method as the golden ratio and noted, without deriving it, that it can beat Newton’s method in practice. The digits figure shows why, by counting evaluations rather than steps. Newton’s method squares its error at each step, doubling its correct digits — 1, 2, 5, 11, 24, 48, 97, 195, 391, 783, 1,567 in the figure — but each step evaluates both $f$ and $f'$. The secant method multiplies its digits by $\varphi$ per step and each step evaluates $f$ once, since the second point of the chord is the one evaluated the step before.

Per evaluation, then, Newton’s method multiplies its digits by $\sqrt 2 \approx 1.414$ and the secant method by $\varphi \approx 1.618$. Alexander Ostrowski called this the efficiency index, the order raised to one over the number of evaluations, and by it the secant method wins whenever a derivative costs about as much as the function itself. In the figure the secant method has 1,977 correct digits after seventeen evaluations, while Newton’s method, after eighteen, has 391. Newton’s method catches up only if the derivative is much cheaper than the function — when, for example, $f$ and $f'$ share most of their computation — and a method that uses Halley’s second derivative, with order 3 for three evaluations, has efficiency $3^{1/3} \approx 1.442$, between the two.

Newton’s line inside the secant’s plane #

The last figure makes the diagonal relation visible by taking slices of the plane parallel to it. The top row is Newton’s method on the line, each starting point shaded by the root it reaches: three long intervals around the three roots, separated by narrow zones near $\pm 0.45$ where the colours alternate rapidly, the cubic version of the chaos on the line between two roots. Below it, the secant method is started from the pairs $(x, x + h)$, close to the diagonal when $h$ is small.

At $h = 0.01$ the secant method agrees with Newton at 94.6% of the starting points, the disagreements concentrated in the narrow zones where Newton’s own basins are finely mixed and any perturbation changes the outcome. At $h = 0.1$ it agrees at 94.0%, at $h = 0.5$ at 82.0%, and at $h = 1$ at only 59.1%: the slices move off the diagonal into the parts of the plane where the basins have their own shapes, unrelated to Newton’s. The plane contains Newton’s line, and the farther from that line the starting pair, the less the secant method remembers that it began as an approximation to Newton’s.

Keeping the root bracketed, and what it costs #

The secant method’s speed comes with a hazard the figures make plain: nothing keeps its iterates near the root. The chord through two points on the same side of the root can point anywhere, and the hero’s blank pairs and long excursions are what that freedom costs. The older rule, false position — regula falsi — removes the hazard by insisting that the two points always straddle the root, one where $f$ is positive and one where it is negative, and replacing whichever has the same sign as the new point. The root is then trapped in a shrinking interval for ever, as in bisection.

The price is the speed. For a function that bends the same way across the bracket, one end of the interval never moves: every new point lands on the same side, the other end stays where it started, and every chord is drawn from that fixed, distant point. The method then converges only linearly, gaining a fixed fraction of a digit at each step, because the product $e_1 e_0$ in the secant relation now has one factor stuck at a constant. Keeping the bracket throws away exactly the multiplication of two shrinking errors that produced the Fibonacci recurrence.

The repair used in practice is a small cheat. The Illinois method halves the stored function value at the stuck end whenever it has been kept twice in a row, which tilts the next chord towards the far side and forces the stuck end to move. That restores superlinear convergence, with order $3^{1/3} \approx 1.442$ per evaluation, while keeping the bracket. Between bisection’s guarantee and the secant method’s golden ratio lies a whole family of compromises, and Brent’s method, the one most root-finding libraries use, switches among bisection, secant steps and a quadratic version of them according to how the last steps went. All of them are attempts to keep the secant method’s multiplication of errors without its excursions into the blank parts of the plane.

Why a map of pairs is harder #

The secant map is a map of the plane, and the small Mandelbrot sets among the cubics do not come with it. For Newton’s method on a polynomial, the dynamics is controlled by the critical points of the Newton map, and a single free critical point decides a whole family’s behaviour. A map of two variables has no critical points in that sense; its folding happens along curves, the curves where its derivative matrix is singular, and the theory that explains Newton’s basins through one point’s orbit has no direct counterpart. What is known about the secant map’s dynamics on the complex pairs — a map of $\mathbb{C}^2$, a four-dimensional space — is recent and partial; Eric Bedford and Pierre Frigge began describing it as a dynamical system in 2015, starting with quadratic polynomials, and the cubic case is largely unexplored.

The question an area that never finishes asked of Newton’s method — whether the set of starting points that never reach a root has positive area — becomes, for the secant method, a question about a set of pairs in the plane. For real cubics the hero suggests that set is small, 0.4% of the grid, but a grid cannot distinguish a thin set of positive area from a union of curves of area nought, and nobody has proved which it is.

What the computation establishes #

The basins are computed from every grid pair with an exact test of arrival at a root and a cap of eighty steps, and they are only as fine as the grid; the curves of flat chords are drawn from a tolerance on the chord’s slope, and the ellipse is derived algebraically and drawn exactly over them. The digit counts and error ratios are exact up to the 3,000 digits carried, which is why each run stops when its errors pass that precision — the last step of each, where the arithmetic runs out, is left off the plots.

The pictures do not prove that the order is the golden ratio; the expansion of the secant formula about a simple root does, and the figures confirm that the constant in that expansion is what the expansion says. Nor do they show what happens at a multiple root, where a double root halves the error for Newton and the secant method slows to linear convergence too, with a ratio of $1/\varphi$ per step rather than $\tfrac12$ — a fact the same Fibonacci argument predicts and none of these functions tests.

Still open: the secant map in two complex variables #

For Newton’s method the dynamics on the whole complex plane is understood: the basins, their boundaries, the role of the critical points, and how to choose starting points that are guaranteed to find every root. For the secant method the analogous questions live in a space of two complex variables, and most are open. Does every root have a basin whose boundary is a fractal of the same kind as Newton’s, and what is its dimension? Can the secant map have attracting cycles that trap open sets of starting pairs, as Newton’s map can for some cubics? Is there a finite set of starting pairs, as there is a finite set of starting points for Newton’s method, from which every root of every polynomial of a given degree is found?

There is also a practical question with no complete answer. Codes that find roots in practice combine the secant method with bisection, falling back on the slow, safe method whenever the fast one strays — Brent’s method is the standard — and the guarantees for such hybrids are worst-case. How often the fallback is actually needed, for a random starting bracket and a random function in some natural family, depends on exactly the geometry of the basins in the plane of pairs that the hero shows, and nobody has measured it in general.

A tangent replaced by a chord #

The secant method follows the chord through its last two guesses instead of Newton’s tangent, needs no derivative, and acts on pairs: its basins for $x^3 - x$ are regions of a plane whose diagonal is Newton’s line, meeting along curves where a chord goes flat — at the first step exactly the ellipse $x_0^2 + x_0x_1 + x_1^2 = 1$. Near a root each error is the constant $f''/2f'$ times the product of the two before, so the correct digits add like Fibonacci numbers — 1, 3, 5, 9, 15, 25, 41, 67, 109 for $\sqrt 2$ — and grow by the golden ratio each step. Per evaluation of the function that beats Newton’s $\sqrt 2$, and a method that throws away the derivative ends up the faster of the two.