HalfStep Root Finding Method 

Introduction


As another example application for the TI89 or 92+, we will now demonstrate the creation of a simple root finding method. The purpose of this example is to demonstrate programming, plotting, lists and a few other things the TIs can do. 

What
is the halfstep method all about?


In the halfstep method, the user supplies an expression f(x), the variable x, a target x*, and a range [x1 .. x2] within which to locate the target value. The algorithm steps into that range, looking for the place where the sign of the function defined by f(x)x* is opposite the one found at x=x1. When such a place is found, the algorithm backs up, reducing its step by half (hence the name), and continues to seek the sign change, but now moving with the reduced step. This process is repeated until an error tolerance (set by the user) is met. The following diagram describes the few first steps of such a process, working on the expression f(x)=x² with a target of x*=4, in the range [0 .. 5].  
As can be seen, this method is not one of the most efficient at all. However, its simplicity, both in application and concept make it one of my favorite methods, whenever complex problems are involved. Furthemore, for educational purposes this will serve us as a very good example.  
What
are the advantages of this method?


There are several useful features of this method.
‡ Even if not given a very close range in which to search for the solution
(in cases when there is only one such solution), the method will converge
in almost the same number of steps. For example, when the solution may be
x*=5 then there will be a difference of only 3 or 4 iterations required,
whether the given range is [0 .. 10], or § Methods like NewtonRaphson or the secant method may sometimes not
succeed in converging to other solutions 

What
are the disadvantages of this method?


As mentioned, there are several disadvanteges:
† This situation may look something like this: 

In such cases the algorithm will eventually find the root (usually the leftmost), but it would take a while until it refines its step enough for it to catch the rapid sign change of the function.  
The
algorithm for the halfstep method


The algorithm for the halfstep method is simple. Here is a nonmathematical description of it: Variables: e  the expression 

? Hmmm... What was that...? A "simple", "straightforward" method? ; ) Ans
It may seem to be a bit cumbersome, but if you'll take a closer look, you'll
notice that only the 

The algorithm in TIBASIC Input: e  the expression 1. Local
initsign, nosol, val 

The
complete program


Clearly, a few crucial aspects are missing from the last algorithm. Namely: a way to stop it through a maximum number of iterations, or when there is no solution in the range, and it tries to catch the change of sign by reducing the step without end. The following is the complete program, plus visual results display and a final graphing of the convergence process. Input: e  the expression 0. halfstep(e, var,
target, range, tol) For your convenience, you can download the program here: TI89, TI92+ 

A
brief discussion of key features used in this program


1.
Use of when( to define functions


As shown in line 3, it is very convenient to use when( when a function
operates on a conditional base. If we had written sgn( in full, we
would have written something like this: sgn(x) Obviously, when a single, simple condition is involved, it is much quicker to define the function using when( 

2.
Turning an expression + variable combination into function(variable)


Sometimes we need the user to enter an expression and a variable to work
with in that expression, such as in this example, or as used in many functions
on the TIs (for example: d(expression, variable) ). For example, the program we've written halfstep( takes an expression e and a variable var. Normally, we would have had to write: e  var = 2 > b every time we wanted to evaluate e when var is 2, and assign it to b. There is a better solution. If we could make a function e(var), then
it would be much easier to write e(2), than all the above. The method
is to write, in the general case, something like this: Here we've simply reused the variable e (line 10), so that it will be local and we wouldn't use memory on another variable (even local variables take memory...) 

3.
Assigning true of false directly without using If .. Then ...
Else ... EndIf


In line 15 we use a short way to assign true or false to the variable nosol. The long, formal way would have been to write: If abs(val) >
tol Then As before, the short way is shorter, and not much remains to be said. 

4.
Appending to a list


In accordance with tip 3.10 in Doug Burkett's The TipList, it is faster to append to the list, rather than to use the function augment(. This is implemented here in line 24. Notice that the first value of x is already stored in the list in line 16, and so we begin appending from index 2, and this is the reason for the i + 1. If the list is started from blank, then we begin from index 1, as this little example shows: {} > list This creates the list {1, 2, 3, 4, 5}. 

5.
Plotting a series of points (x, y) from a program


The command which defines a plot is called NewPlot, and we use it in line 49. The general syntax is: NewPlot n, type, xlist, ylist,,,, mark No, the four commas are not a typo. The reason is that there can appear other options in between, which we ignore here (please consult your manual for a complete description of how to use NewPlot). n is the plot number
(1 for Plot1, 2 for Plot2, etc.) The only catch is this: the lists have to be global variables! In other words,
it wouldn't work to write: 

This is the reason the variable xlist is not a local variable, and likewise ilist isn't, in line 48. After this command, which only defines the plot, the TI does not automatically switch to the graph screen. We do this manually with the ZoomData command in line 50, which adjusts the window limits to those of the data points. 

A
demonstration of the HalfStep program


We will use a simple example here: finding when f(x)=x² is 4, with an error tolerance of 0.001. We first start with a 'good' range: [0 .. 5]. 

Note: use Diamond+ENTER to get a floating point result.  
Quickly tracing the values with F3: Trace, shows us the progress of the algorithm. The last value is, of course, the first value which is within the error tolerance tol.  
We can try the same thing with a 'bad' range: [10 .. 20]. The algorithms prgress would look like this:  
The explanation is obvious: the algorithm couldn't find a sign change between 10 and 20, so it decreases its step size again and again, until the entire range is missed for the 3rd time (this is maxmi). A negative range [5 .. 0] will give the other solution: 

But
what happens when we have absolutely no idea where the solution is? Let's take
an exagerrated range of [100 .. 100]. This is what happens: 

As expected, the algorithm converged to the negative solution (because it is the first, whereas the positive is the second, in terms of the algorithm's progress). Notice the price for our exaggerated large range of [100 .. 100]: only 11 more iterations! 50% more iteartions than when we gave the range [5 .. 0] ! Considering the fact that the range was now 40 times bigger than [5 .. 0], this is remarkable. Let's try an even more exagerrated range: [1000 .. 1000]. How many more iterations will it take this time (the range will be 400 times larger than [5 .. 0])? 

It now took 40 iteartions to converge to a solution! This is twice as much as with [5 .. 0], when the range is 400 times larger! 

Conclusions


Obviously, this method is not the best, when it comes to root finding. We have seen its slowness, even when the range boundaries ware very close to the solution. On the other hand, we have seen it's speed, when the range boundaries are very far from the solution. This example is long enough already, so we will not discuss other, more delicate cases now. For the educational purposes, I rest my case :) 

______________________________________________________________________________________ Created by Andrew Cacovean, March 16, 2002 
