Downhill Simplex Method for the HP-41
Overview
"DHS" employs the downhill simplex method to minimize a function of
n variables f ( x1 , x2 , ...... , xn
) 1 < n < 16
This program is very slow and a good emulator like V41 in turbo mode
is recommended !
Program Listing
-The method is described, for example, in references [1] & [2]
-Before executing "DHS", store the function name in R00 and the initial
guesses in R01 thru Rnn
-The accuracy is controlled by the display setting.
-Avoid FIX 9 which could lead to an infinite loop
Data Registers: • R00 = function name ( R00 and R01 to Rnn are to be initialized before executing "DHS" )
• R01 = x1 • R02 = x2 ...........
• Rnn = xn
R21 = f ( x1 , x2 , ...... , xn )
Rn+1 to R21+4n+n^2: temp
Flags: /
Subroutine: A program which computes
f ( x1 , x2 , ...... , xn ) assuming x1
is in R01 , x2 is in R02 , ............ , xn is in
Rnn
| 01 LBL "DHS"
02 X<>Y 03 STO 20 04 X<>Y 05 STO 16 06 STO 17 07 ST+ X 08 22 09 + 10 RCL 16 11 E3 12 / 13 STO 18 14 + 15 E3 16 / 17 1 18 + 19 ISG 17 20 LBL 01 21 REGMOVE 22 RCL 18 23 + 24 DSE 17 25 GTO 01 26 RCL 16 27 X^2 28 LASTX 29 3 30 * 31 STO 18 32 + 33 21 34 + 35 STO 17 36 .1 37 % 38 22 39 + 40 RCL 18 41 + 42 RCL 16 43 1 44 + 45 E5 46 / 47 + 48 SIGN 49 CLX 50 RCL 20 51 LBL 18 52 ST+ IND L 53 ISG L 54 GTO 18 55 LBL 41 56 RCL 16 57 STO 18 58 21.02 59 + 60 STO 19 61 RCL 17 62 STO 20 63 LBL 02 64 RCL IND 20 65 STO IND 18 66 DSE 20 |
67 DSE 18
68 GTO 02 69 XEQ IND 00 70 STO IND 19 71 RCL 16 72 STO 18 73 DSE 19 74 GTO 02 75 LBL 16 76 RCL 16 77 21.02 78 + 79 STO L 80 RCL IND X 81 ENTER 82 DSE L 83 LBL 04 84 CLX 85 RCL IND L 86 X>Y? 87 GTO 04 88 X<>Y 89 CLX 90 LASTX 91 STO Z 92 LBL 04 93 DSE L 94 GTO 04 95 RCL 21 96 X<> IND T 97 STO 21 98 R^ 99 INT 100 19 101 - 102 RCL 16 103 * 104 22 105 + 106 .1 107 % 108 RCL 16 109 ST+ X 110 + 111 22 112 + 113 RCL 16 114 E6 115 / 116 + 117 REGSWAP 118 RCL 16 119 21.02 120 + 121 STO L 122 RCL IND X 123 ENTER 124 DSE L 125 LBL 05 126 CLX 127 RCL IND L 128 X<Y? 129 GTO 05 130 X<>Y 131 CLX 132 LASTX |
133 STO Z
134 LBL 05 135 DSE L 136 GTO 05 137 X<> Z 138 RCL 16 139 21 140 + 141 RCL IND Y 142 X<> IND Y 143 STO IND Z 144 X<> Z 145 INT 146 19 147 - 148 RCL 16 149 * 150 22 151 + 152 .1 153 % 154 RCL 16 155 ST+ Y 156 ST+ Y 157 X^2 158 + 159 22 160 + 161 RCL 16 162 E6 163 / 164 + 165 REGSWAP 166 RCL 16 167 20.02 168 + 169 STO L 170 RCL IND X 171 ENTER 172 DSE L 173 LBL 06 174 CLX 175 RCL IND L 176 X<Y? 177 GTO 06 178 X<>Y 179 CLX 180 LASTX 181 STO Z 182 LBL 06 183 DSE L 184 GTO 06 185 X<> Z 186 RCL 16 187 20 188 + 189 RCL IND Y 190 X<> IND Y 191 STO IND Z 192 X<> Z 193 INT 194 19 195 - 196 RCL 16 197 * 198 22 |
199 +
200 .1 201 % 202 RCL 16 203 ST+ Y 204 X^2 205 + 206 22 207 + 208 RCL 16 209 E6 210 / 211 + 212 REGSWAP 213 VIEW 21 214 RCL 16 215 ST+ X 216 21 217 + 218 .1 219 % 220 + 221 RCL 16 222 + 223 RCL 17 224 STO 18 225 CLX 226 LBL 13 227 RCL IND Y 228 RCL IND 18 229 - 230 ABS 231 X>Y? 232 X<>Y 233 RDN 234 DSE 18 235 DSE Y 236 GTO 13 237 RND 238 X=0? 239 GTO 99 240 22 241 RCL 16 242 ST+ Y 243 ST+ X 244 21 245 + 246 E3 247 / 248 + 249 STO 18 250 LBL 08 251 RCL 18 252 INT 253 .1 254 % 255 + 256 RCL 16 257 X^2 258 + 259 RCL 16 260 E5 261 / 262 + 263 ENTER 264 CLX |
265 LBL 09
266 RCL IND Y 267 + 268 DSE Y 269 GTO 09 270 RCL 16 271 / 272 STO IND Y 273 ISG 18 274 GTO 08 275 RCL 16 276 STO 18 277 RCL 17 278 RCL 16 279 ST+ X 280 21 281 + 282 LBL 10 283 RCL IND X 284 ST+ X 285 RCL IND Z 286 - 287 STO IND 18 288 RDN 289 DSE X 290 DSE Y 291 DSE 18 292 GTO 10 293 XEQ IND 00 294 STO 18 295 RCL 21 296 X>Y? 297 GTO 11 298 CLX 299 RCL 16 300 20 301 + 302 X<>Y 303 RCL IND Y 304 X<=Y? 305 GTO 15 306 RCL 16 307 21 308 + 309 RCL 18 310 STO IND Y 311 LBL 17 312 RCL 17 313 1 314 + 315 RCL 16 316 ST- Y 317 E3 318 / 319 + 320 .1 321 % 322 1 323 + 324 REGMOVE 325 GTO 16 326 LBL 11 327 RCL 17 328 1 329 + 330 RCL 16 |
331 E3
332 / 333 + 334 E3 335 / 336 1 337 + 338 REGMOVE 339 RCL 16 340 ENTER 341 ST+ X 342 21 343 + 344 LBL 07 345 RCL IND Y 346 ST+ X 347 RCL IND Y 348 - 349 STO IND Z 350 RDN 351 DSE X 352 DSE Y 353 GTO 07 354 XEQ IND 00 355 STO 19 356 RCL 18 357 X>Y? 358 GTO 11 359 RCL 16 360 21 361 + 362 X<>Y 363 STO IND Y 364 RCL 17 365 1 366 + 367 STO Y 368 RCL 16 369 - 370 E3 371 / 372 + 373 RCL 16 374 E6 375 / 376 + 377 REGMOVE 378 GTO 16 379 LBL 11 380 RCL 16 381 21 382 + 383 RCL 19 384 STO IND Y 385 GTO 17 386 LBL 15 387 RCL 16 388 STO 20 389 ENTER 390 ST+ X 391 21 392 + 393 RCL 17 394 LBL 12 395 RCL IND Y 396 RCL IND Y |
397 +
398 2 399 / 400 STO IND 20 401 RDN 402 DSE X 403 DSE Y 404 DSE 20 405 GTO 12 406 XEQ IND 00 407 STO 18 408 RCL 16 409 21 410 + 411 X<>Y 412 RCL IND Y 413 X<=Y? 414 GTO 11 415 X<>Y 416 STO IND Z 417 GTO 17 418 LBL 11 419 RCL 16 420 STO 18 421 RCL 17 422 STO 19 423 LBL 14 424 RCL 16 425 3 426 * 427 21 428 + 429 STO 20 430 LBL 00 431 RCL IND 20 432 RCL IND 19 433 + 434 2 435 / 436 STO IND 19 437 DSE 19 438 DSE 20 439 DSE 18 440 GTO 00 441 RCL 16 442 ST+ 18 443 RCL 19 444 RCL 20 445 X#Y? 446 GTO 14 447 GTO 41 448 LBL 99 449 RCL 16 450 .1 451 % 452 ISG X 453 LASTX 454 % 455 22 456 + 457 RCL 16 458 ST+ X 459 + 460 REGMOVE 461 RCL 21 462 END |
( 767 bytes / SIZE 22+4n+n^2 )
| STACK | INPUTS | OUTPUTS |
| Y | h | / |
| X | n | fmin |
Where n = number of variables and h = initial increment
Example:
-Let's solve the overdetermined system: x2 +
y2 + z2 = 4 ; x2 - y2
+ z = 2 ; x + y + z2 = 1 ; x - y - z = 0
by the least-squares method ( the system itself has no
solution )
-Let f(x,y,z) = ( x2 + y2 + z2
- 4 )2 + ( x2 - y2 + z - 2 )2
+ ( x + y + z2 - 1 )2 + ( x - y - z )2
| 01 LBL "T"
02 RCL 01 03 X^2 04 RCL 02 05 X^2 06 + 07 RCL 03 |
08 X^2
09 + 10 4 11 - 12 X^2 13 RCL 01 14 X^2 |
15 RCL 02
16 X^2 17 - 18 RCL 03 19 + 20 2 21 - |
22 X^2
23 + 24 RCL 01 25 RCL 02 26 + 27 RCL 03 28 X^2 |
29 +
30 1 31 - 32 X^2 33 + 34 RCL 01 35 RCL 02 |
36 -
37 RCL 03 38 - 39 X^2 40 + 41 RTN 42 END |
"T" ASTO 00 CLX STO 01 STO 02 STO 03 if we choose x = y = z = 0 as initial guesses
-SIZE 043 ( at least )
-For example FIX 4
-If you choose h = 1 and since there are 3 variables:
1 ENTER^
3 XEQ "DHS" >>>>
the HP41 displays the successive f-approximations and finally, we get:
fmin = 1.4344 = R21
and we have in R01-R02-R03: x = 1.1055 y = -0.9168 z = 1.2629
-With FIX 6, it yields: fmin = 1.434377
x = 1.105450 y = -0.916829 z = 1.262964
Note:
-It may be wise to execute the program a second time to check or to
improve the precision of the results...
References:
[1] Press , Vetterling , Teukolsky , Flannery - "Numerical Recipes
in C++" - Cambridge University Press - ISBN 0-521-75033-4
[2] https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method