Issue link: http://dc.ee.ubm-us.com/i/71837

PROGRAMMER'S TOOLBOX On to parabolas Now that we remembe r how to do the golden section search, let's see what we can do with parabolic fits. In my column "A Simulator's Paradise," (Apri l 2000, p. 11 ), I worked o ut the formulas for fitting a parabola through three points, and estima ting the minimum. The ma th goes: Xmin =2 x, +x2 -~ I ( where: c = m,- mo x 2 -x1 and rn0 and m1 are the two slopes: 0.4 -- JJ.· m2 = Y1- Yo x 1 -x0 m, = Y2 - Y1 x 2 -x1 (4) (5) ot again that the algorithm doesn 't real ly care whether the .xs increase to the left 01· the right, so anything we do in terms of swapping ends will not affect tJ1e r ult. Using Equations 2 through 5, we can write a function that estimates the min- imum by means of parabolic fit. This is shown as para_fit( ) in Listing 3. Looking at this code, I think, "Gee, it sure doesn't bear much resemblance to Brent's p, q, r, x, w, v, d, and e, does it?" Never mind. I'm sure the two par- abolic fits are equivalent-it's pretty hard to get that part wrong-but I'm not currently incl ined to prove the equivalence. I understand what I've got, and that's enough for me. Once we have an estimated X,11 ;n from the parabolic fit, we sti ll have to decide what to do with it. Clearly, if it's outside the interval Xo·· X2· it's no good and we must discard it. However, tl1is should never happen. Our fundamen- 0 .001 )( e 0.0001 0.0001 0 .0000001 ~ 0.000001 ! 1 ! I -o- xo ( ---a--- x, J I · - -.Q.-- X2 I; 3 4 5 6 ' FIGURE J 0 .2 - ··=:o- ~~--1 ....:.- 3 4 5 6 7 8 9 10 11 Iteration m o) (2) I'm sure the two parabolic fits are equivalent-it's pretty hard to get that part wrong-but I'm not currently inclined to prove the equivalence. I understand what I've got, and that's enough for me. tal assumption is that: Yo> y , < Y2 (6) We assume that th is is true going into the algorithm, and we take steps to (3) e )( 0.6 i ! -- ·ll·-- x, ! - ! i o ~~---·-~---,-- - -- ------=-=====::;:;;:;;;;:::::;:::::==-==-:::.:':=:.·::::D 2 12 " i - x2 J i! ji . ' - \ . '.: ·a-_:_- a. : " , ' ,, - ~ ., : \ ' ' I ' :--- .. , -~ ~ ' ~- .. ~-' - -. ~- - .; .... \ ,- ' : .. '\ : \ !\\ '· · ' ' ,~a.. .:.. .c. ,: ·-c< -- ,. -., 7 8 9 10 Iteration ' A ~ :_"l:Jr ..,.. -.1)- ,- ooll - '- 11 12 .. "1 . - ~ I !I -! I· "'l l ll !1 ~ ---,-..,:--· ·:··:_ .. :- ·:····-··=· ='==='==::;:;;:;:::;:;;;;:;;:::::=== ................ ~ 2 ll li i· Embedded Systems Programming SEPTEMBER 2000 47

- September001
- September002
- September003
- September004
- September005
- September006
- September007
- September008
- September009
- September010
- September011
- September012
- September013
- September014
- September015
- September016
- September017
- September018
- September019
- September020
- September021
- September022
- September023
- September024
- September025
- September026
- September027
- September028
- September029
- September030
- September031
- September032
- September033
- September034
- September035
- September036
- September037
- September038
- September039
- September040
- September041
- September042
- September043
- September044
- September045
- September046
- September047
- September048
- September049
- September050
- September051
- September052
- September053
- September054
- September055
- September056
- September057
- September058
- September059
- September060
- September061
- September062
- September063
- September064
- September065
- September066
- September067
- September068
- September069
- September070
- September071
- September072
- September073
- September074
- September075
- September076
- September077
- September078
- September079
- September080
- September081
- September082
- September083
- September084
- September085
- September086
- September087
- September088
- September089
- September090
- September091
- September092
- September093
- September094
- September095
- September096
- September097
- September098
- September099
- September100
- September101
- September102
- September103
- September104
- September105
- September106
- September107
- September108
- September109
- September110
- September111
- September112
- September113
- September114
- September115
- September116
- September117
- September118
- September119
- September120
- September121
- September122
- September123
- September124
- September125
- September126
- September127
- September128
- September129
- September130
- September131
- September132
- September133
- September134
- September135
- September136
- September137
- September138
- September139
- September140
- September141
- September142
- September143
- September144
- September145
- September146
- September147
- September148
- September149
- September150
- September151
- September152
- September153
- September154
- September155
- September156
- September157
- September158
- September159
- September160
- September161
- September162
- September163
- September164
- September165
- September166
- September167
- September168
- September169
- September171
- September172
- September173
- September174
- September175
- September176
- September177
- September178
- September179
- September180
- September181
- September182
- September183
- September184
- September185
- September186
- September187
- September188
- September189
- September190
- September191
- September192
- September193
- September194
- September195
- September196
- September197
- September198
- September199
- September200
- September201
- September202
- September203
- September204
- September205
- September206
- September207
- September208
- September209
- September210
- September211
- September212
- September213
- September214
- September215
- September216
- September217
- September218
- September219
- September220
- September221
- September222
- September223
- September224
- September225
- September226
- September227
- September228
- September229
- September230
- September231