June 20, 2010Tutorial: Root FinderA basic similar triangle problem: solve for x_{2}. Because the two triangles are similar we know that the ratios of the lengths are the same:
Multiplying through and solving for x_{2}, 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 algebrahomeworksolver, Anthony recently built a simple rootfinder on his own that probed values at constant 0.1separated 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 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_{2} 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 finitedifference 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
Comments
Post a comment

Copyright 2010 © David Bau. All Rights Reserved. 