davidbau.com

Tutorial: Root Finder

A basic similar triangle problem: solve for x₂.

Because the two triangles are similar we know that the ratios of the lengths are the same:

Multiplying through and solving for x₂, we get:

This formula is the core of an ancient idea for solving arbitrary equations.

Getting out of Algebra Homework

In an effort to make an algebra-homework-solver, Anthony recently built a simple root-finder on his own that probed values at constant 0.1-separated values of x, looking for sign changes.

After he worked on it for a long time, he came to me trying to explain the idea, and showing me that it did not work that well because it was too coarse.

So I showed him the secant method, and we coded it up as a javascript example here.

The Secant Method

Suppose we have already made two incorrect guesses while searching for a zero of a function, and at those two values, the function passes through the points (x₀, y₀) and (x₁, y₁). We could continue making more guesses by crawling along the number line, looking for a sign change or for a point with y values closer to zero.

But the secant method tries to jump straight to the answer by drawing a straight line between the two observations and calculating the point x₂ where that line crosses zero, as above.

If the initial guesses are close enough, the method converges very quickly and makes mincemeat out of polynomial root finding.

Hopefully Anthony will continue to work on his algebra homework by hand anyway.

History of the Regula Falsi

The secant method is similar to Newton's method but does not require knowledge of derivatives or other calculus. It is sometimes described as a finite-difference approximation to Newton's method. However, it actually predates Newton.

Joanna Papakonstantinou has unearthed evidence that the secant method was being used by Babylonians and Egyptians in 18th century BC to solve linear relationships and by Chinese scholars to approximate nonlinear relationships in the 2nd century BC. The idea of drawing a line between two incorrect answers to make a correct answer was called "the rule of too much and not enough;" "the method of double false positions;" "the method of scales;" or "Regula Falsi." It made appearances around the world in 9th century Arabic, 11th century European, 12th century Indian, and 13th century African mathematical texts.

Cardano documented the modern idea of iterating the method to increase precision arbitrarily. He used it to solve cubics in his 1545 Ars Magna, one hundred years before Newton was born. Posted by David at June 20, 2010 12:18 AM