Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 41 of 229

PROGRAMMER'S TOOLBOX e Getting serious So I'll make a deal with you. Let's do this thing together. I'll give you an algorithm that seems to work on a limited number of cases. Feel free to try it out and let me know how it works. So I'll make a deal with you. Le t 's do this th ing togeth e r. I'll give you an a lgorithm th at seems to work o n a limited numbe r of cases. Feel free to try it o ut and le t me know how it LISTING I works. If you find pro blems wi th it, get bac k to me, and we' ll fi x it together. Between us, maybe we' ll a rrive at tha t ki ll er solutio n, after a ll. Deal? F.unctions for parabolic fit · . · .:':::i~~·~. ·. · II estimate a minimum via parabolic fit double para_f i t(double xO, double x1, double x2, double yO, double y1, double y2){ double n{) = (y1 - yO) I (x1 - xD>; double m1 = (y2 - y1)1(x2 - x1); double c = (m1 - n{))l (x2 - xD>; return (xQ + x1 - n{)lc>l2.0; } II shrink an interval using parabolic fit void para_shrink(double &xO, double &x1, double &x2, double &yO, double &y1, double &y2){ double x = para_fit(xO, x1, x2, yO, y1, y2); double y = f(x); if(x > x1 ){ swap(xO, x2); swap( yO, y2); swap(x, x1); swap(y, y1); } if(y > y1 ){ xO = x; yO = y; } else { x2 = x1; y2 = y1; x1 = x; y1 = y; } swap(xO, x2); swap(yO, y2 ); } Okay. We've pussyfooted around this issue for long enough. Let's put this sucker to bed. Befo re doing so, how- ever, maybe I should review the bid- ding. We've already seen, months ago, an algorithm that can reliably find a minimum of a single va ria ble by means of bisection. Bisection using the golden ratio turned out to work a li ttle better than halving in tervals. The problem with any bisection method is tha t it ta kes awhile to get the solution . We can expect each step to improve our solution by just half a bit. For improveme nt by a fac- to r of, say, 10,000 (typical fo r mini- mum-finde rs; solution to mach ine accuracy is not feas ible), th at means a ro und 24 to 26 itera tions. No t o ut- rageously ine ffic ie nt (did you catch th e fac t tha t brent . c, from Recipes, too k 19 on my sample pro blem?), but naturally we' d like to d o be tte r. A bette r approach is to use a qua- dra ti c me th od. Such me th ods involve fi tting a quad ratic thro ugh the three sma ll est points, and using tha t to estima te the minimum. A quadratic meth od do ubles the num- ber of signi ficant d igits fo r each ite r- ation . Once it gets near a solution, it homes in like a hound dog afte r a possum. To th e 104 accuracy, we fo und a soluti o n to o ur sample problem in seven ite ratio ns (nine func ti o n evalu atio ns, coun ting setu p of the ini tial conditions). Each approach has its advantages. The bisection method is tl1e workhorse, the bubble sort of minimum fmders. It may be slow, but it's sure. One nice fea- ture of bisection methods is that tl1ey don 't really care if the function in ques- tion is well-behaved or not. For exam- ple, the golde n section search will cheerful ly find the minimum of: (1) Such a function will dtive a quadratic metl1od crazy, because its derivative is discontinuous. Like most higher-order 40 SEPTEMBER 2000 Embedded Systems Programming

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10