13.3 Another Linear Method

Another easy method to apply is to pick two arguments, x₀ and x_0' that you hope are near the solution you want, evaluate the function at them and assume that the straight line defined by the two values and arguments is reasonable approximation to f. You can then find where that straight line meets the x axis, and use it to replace one of the two initial values.

In doing this there are two cases; one in which the value of f has the same sign at both points. This means that their straight line will not meet the x axis between your guesses, and then you might as well use the new point to replace the one of the two others furthest from it.

If, on the other hand, the values of f at your two arguments have the opposite sign, you should replace the old argument at which f has the same sign as it has at the new one, so that the values of f will have the opposite sign on the next turn as well.

This method has the advantage over Newton's that once you find arguments whose values of f have the opposite sign, you must home in on a solution between those arguments. (A solution being a point at which f changes sign; for a continuous f this is a point at which f is 0; functions like tan x change signs at arguments at which they are infinite (or more properly, undefined) as well as those at which they are 0.)

It has the disadvantage that there are functions for which the true derivative between your guesses is far from a straight line, and you gain very little in each iteration. It can then be painfully slow to converge.

The equation used for finding x_{i + 1} given the two values x_i and say x_i' that you use to compute it is

If you compare this with the previous method, this corresponds to approximating the derivative in Newton's method by using values at the previous two guesses, rather than by the last guess and it plus d, as in Poor Man's Newton.

This equation can be solved and we can find a new x_i easily as before. With a small amount of effort we can figure out which of the old arguments to discard; the following setup does it:

In s2 and t2 put your initial guesses. In u2 put "= f(s2)"' and copy that into v2.
Now put "= s2 -(s2-t2)*u2/(u2-v2)"in s3, and "= if(abs(s3-t2)<abs(s3-s2),t2,s2)" in w2. (This puts the old argument closer to the new one in w2.)

Copy s3 and u2 down, and now put "= if(u2*v2>0,w2,if(u2*u3>0,t2,s2))" in t3 and copy t3, w2, and v2 down.

This last horrible instruction makes t3 hold the nearer old argument to s3 if u2 and v2 had the same sign, and otherwise puts the old argument whose value of f has the opposite sign to u3 in t3.

Exercise 13.8 How does this scheme compare to the others on your examples? Try it on the various examples of the previous exercises.