LabVIEW
VI of the Day (9/22/2009) - Find All Zeros of f(x).vi
Today we get to put a few things together to tackle a common problem: root finding. The VI for today is "Find All Zeros of f(x).vi". The first thing that you notice (in LV2009) when you put this VI on the BD is that you have a pulldown menu, I always recommend using the 'f(x) is VI' option. As I mentioned in the 'Eval y=f(x).vi' VIOTD, I like to use formula strings in certain situations, this is one situation where I try to avoid it. If performance and efficiency matters in your application, you are better of using the VI version. If you don't have LV2009 yet, do what I did, implement your own version. It helps to remind you what goes on during the root finding algorithm which can greatly reduce the number of problems you encounter.
Speaking of efficiency, there are two choices of algorithm with this VI, the classic Newton Raphson method and Ridders method. Each of these is also available in a simpler VI to find a single root. Since the NR method is taught in most calculus classes and is familiar, it is often the one reached for first. Very simple idea, find the intercept of the line which passes through f(x) with slope f'(x) and use that as the next guess for the root. Obviously when f'(x) is close to zero, your guess can shoot off to oblivion. I have a problem with the current implementation still, although f(x) can be given by a VI, f'(x) is still found by finite difference, a method prone to roundoff error and requiring two evaluations of f(x). If you like this algorithm, I would still suggest writing your own version where f'(x) can be given by the same VI as f(x). When you are able to calculate f'(x) it is much better to do that, when you can't I say use another algorithm.
Ridders method is less well known, but one that I a use much more often that NR. It finds an exponential curve that passes through the endpoints of the search region as well as the midpoint. It is robust and shares most of the convergence properties people like about NR. In practice, you may not notice much difference between the two methods, but for certain functions which are expensive to calculate, the difference can be quite significant.
Now let's find some roots. The key to any algorithm's success is preparation, in this case, bracketing the roots. The better your initial bracketing, the better your results. The Find All Zeros VI evaluates the function with small steps, looking for sign changes. Each small change is then searched using the algorithm of choice to fine-tune the root. I have posted an example which finds the roots of Bessel functions of integer order, a common problem.
As you can see, we combine Ramp, Call By Reference, as well as To Variant. I use variant data to pass the order of the Bessel function to my VI which calculates Jn(x). The For Loop is there to graph the function. You can see from the graph that the routine works quite well, and is fairly fast for this simple function.
VIOTD groundrules here.
