If we have a linear equation, such as 5x - 3 = 0, there is a straightforward procedure for solving it. You apply "the golden rule of equations": do unto the left side exactly what you do unto the right side. And you do it until all you have on the left is x.
Thus with this example you would add 3 to both sides, getting rid of the -3 on the left, and then divide by 5, with the result, .
Suppose however, we have a more complicated equation, such as
sin(x) - exp(x) + 2 = 0
Our task here is to find a solution , or all the solutions of such an equation.
First note that it is always a good idea to plot the left hand side here and observe, crudely, where it changes sign or comes very near to 0. This will tell you roughly where it becomes 0.
In the old days this was an extremely tedious task, in general, and people tried to solve equations without plotting, which is a bit like flying blind. Its OK if you can do it, but why try if you don't have to do so?
The standard technique for solving such equations apparently goes back to Newton. And here it is.
You start with a guess of an argument, call it x0. You then find the linear
approximation to your function, f, at argument x0, and solve the equation that
this linear approximation is 0. Call the argument for which the linear approximation
is 0 x1.
Now you do exactly the same thing, starting at x1: you find the linear approximation to f at x1 and solve the equation that this linear approximation is 0 to determine x2. And you continue this as long as you need to.
In the old days this was an extremely tedious thing to do, for any function. Finding xj+1 from xj is quite easy, but doing it over and over again is a real bore.
Now with a spreadsheet, you can set this up and find solutions, with practice, in under a minute. You only have to do each step once, and copy.
First let's see how to get xj+1 from xj.
The linear approximation to f at xj is
f(xj) + (x-xj) f '(xj)
If we set this to 0 at argument xj+1 we get
f(xj) + (xj+1 - xj) f '(xj) = 0
which has solution, obtained by dividing and subtracting from both sides appropriately
So what do I do on a spreadsheet?
Suppose we put our first guess in box A1. We will put it and subsequent guesses in column A starting say, with 3. (just to leave room for labels.)
We can then put f in column B and f ' in column C.
To do this we need make the following entries:
A3 = A1 (this puts starting guess x0 in A3)
B3 = f(A3) (this computes f(x0))
C3 = f'(A3) (this computes f '(x0))
A4 = A3 – B3/C3 (this applies the algorithm to get the new guess)
If you now copy A4 (not A3!) and B3 and C3 down the A, B and C columns, you have implemented the algorithm.
You can change your starting guess by changing A1, and change your function by changing B3 and C3 appropriately, and copying the results down.
Does this really work?
This method converges very rapidly most of the time. If you start near a 0 of f, and are on "the good side" it will always converge. Otherwise it stands a good chance of doing so, but strange things can happen.
What is the "good side"?
Suppose you start above the solution, call the solution z, so x0 is greater than z. Then if f and the second derivative of f is positive between z and x0, you are on the good side.
Because the second derivative of f is positive, between z and x0, we know that the first derivative of f is increasing between z and x0, which means that the slope of f is biggest between z and x0 right at x0.
All this means that the linear approximation to f at x0 will dive down to 0 faster than f does, so that x1 will lie somewhere between z and x0. And each successive xj will lie between z and the previous one. As we get closer to z, f will look more and more like a straight line, which will mean it will look more and more like its linear approximation, so you will get closer and closer to z faster and faster.
11.1 Suppose f is negative at x0 which is bigger than z. What condition of f " between z and x0 will mean you are on the good side? What is the condition when f is positive at x0 but x0 is less than z for you to be on the good side as discussed here?
11. 2 What will happen if f " has the wrong sign but the same sign between your guess and z?
Still and all, the method can do bizarre things. If f '= 0 at a guess, the iteration won't even make sense because you will divide by 0 in it. If f ' is very near 0, the new guess will be very far from the old one, and it can zip around weirdly.
The following applet allows you to plot and view the method just by entering the function. (which is only slightly simpler than starting from scratch with a spreadsheet).
11.3 What happens if you look for the solution to , and you try to use this method directly? How about tan x = 1?
11 4 Find all solutions to sin (x) - exp(x) + 2 = 0 for x positive,
accurate to ten decimal places.
Do I have to differentiate f to apply this algorithm?
No!. you can choose a value of d that is very small relative to the scale of your function and put =(f(a3+d)-f(a3-d))/(2*d) in C3 instead of =f '(a3). This will do just about as well as the regular Newton's method, practically always.
Exercise 11.5 Redo exercise 4 us this entry in C3. How is your answer affected?
For more thoughts on solving equations look at Chapter 13 of the 18.013A notes.