Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 46 of 229

e PROGRAMMER'S TOOLBOX methods, the quadratic method is more twitchy and more easily confused. Another thing I like about bisec- tion methods is the cri terion we use to halt. Beginning with two points strad- dling the solutio n, a bisection me thod pulls both ends inward. We don't real- ly have to test the solution itself; we stop when the distance between end points is below some epsilo n distance. By contrast, with quadratic me th- ods we get a predicted location for the minimum and compare that with pre- vious values. This makes me a bit ner- vous, since we've already seen how cer- tain combinations of inputs can yield the same predicted minima, eve n though neither is anywhe re close to the true value. I a lso noticed th a t quadrati c methods tend to ha ng on to end po ints longe r tha n bisection me th- ods. Bisection methods have n o choice; tha t range is going to be reduced by ro ughly 25% (a bit more with the golde n section) n o matter what. Quadratic me thods don 't real- ly care whi ch points th ey use , as lo ng as they're ro ugh ly centered on the solution. The thing that a ttracted me to Brent's method was that it seems to be a near-optimal mix of golden section and quadratic searches. If it can get what it regards as a good quadra tic fit, that's what it wi ll use . If not, it rej ects the step and uses a golden section instead. But what ma kes me nervous about Brent's method- o th e r than that I can ' t get an yone to explain it to me-is th at it will sometimes use quadratics exclusively, if it 's satisfied with certain conditions. Because I've see n the quadratic method s hang o n to end po ints too lo ng, I suspect that the inte rval be tween the end points doesn't d ecrease as rapidly as I'd like. How d o we make the two po ints draw together? I have n ' t a clue. Short of forcing bisection to bring them together, I'm not sure we can guarantee tha t th e bracke ting inter- How do we make the two points draw together? I haven't a clue. Short of forcing bisection to bring them together, I'm not sure we can guarantee that the bracketing interval ever gets small. val ever gets small. And if it doesn't get small a t a rate faster than bisec- tio n would produce , we have no ho pe of speeding the convergen ce. LISTING 4 void main(voidH double xO = 0; double x2 = 1; double x1 = gold

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10