1 /* 2 Copyright (C) 2018-2021, Dirk Krause 3 SPDX-License-Identifier: BSD-3-Clause 4 */ 5 6 /* 7 WARNING: This file was generated by the dkct program (see 8 http://dktools.sourceforge.net/ for details). 9 Changes you make here will be lost if dkct is run again! 10 You should modify the original source and run dkct on it. 11 Original source: dk4iter.ctr 12 */ 13 14 #ifndef DK4ITER_H_INCLUDED 15 /** Avoid multiple inclusions. */ 16 #define DK4ITER_H_INCLUDED 1 17 18 19 /** @file dk4iter.h Iteration algorithms for root finding. 20 21 This module implements the following root finding iteration algorithms: 22 - Bisection 23 - Regula falsi (primitive form, Illinois, Pegasus, Anderson-Bjoerck) 24 - Newton 25 - fix point 26 27 The function to iterate must be implemented as dk4_iter_fct_t. 28 This function type returns an integer value (non-zero to indicate a 29 successful calculation, 0 to indicate an error). 30 The function expects the following arguments: 31 - Result address<br> 32 Address of a variable or an array to store the calculation result. 33 Functions for Newton iteration algorithm store 2 values: Function value 34 and value of the first derivative. 35 - X position<br> 36 The x value you want a function value for. 37 - Address of parameter set. 38 Additional parameters probably required by the function. I.e. for a 39 polynomial calculation function you may specify the coefficients here. 40 This parameter is optional. 41 42 Details for an iteration may be specified in an iteration context. 43 The dk4iter_ctx_open() creates such a context and returns a pointer. 44 Use dk4iter_ctx_close() to release the context when done with it. 45 Alternatively use a automatic/static variable of the dk4_iter_ctx_t type 46 and initialize it using the dk4iter_ctx_init() function. 47 48 The dk4iter_ctx_set_algorithm() function chooses the iteration method. 49 50 For Newton and fixpoint the context may specify an x interval the 51 iteration must not leave. Leaving the interval results in abort. 52 The dk4iter_ctx_set_min(), dk4iter_ctx_set_exclusive_min(), 53 dk4iter_ctx_set_max() and dk4iter_ctx_set_exclusive_max() functions can 54 be used to set closed and open interval borders. 55 56 Tolerance values (epsilon) may be specified for 57 - y direction unless fixpoint is used and/or 58 - x direction. 59 Use dk4iter_ctx_set_eps_y() and dk4iter_ctx_set_eps_x() to set the 60 tolerances. 61 Use 0.0 or negative tolerances to skip one check (not both!). 62 63 Once the iteration reached allowed y difference you can decide 64 to stop when the x difference is in allowed tolerance range too or 65 to continue until full machine precision is reached (new x is exactly 66 the same as previous x). 67 I do not recommend attempts to iterate to full machine precision as this 68 (a) may fail for some functions resulting in an oscillation and 69 (b) uses a larger number of iteration passes and. 70 Use dk4iter_ctx_set_exact() to control this. 71 72 The dk4iter_ctx_set_maxpass() function sets the maximum number of 73 iteration passes (iteration steps). The iteration is aborted if there 74 is no success within this maximum number of passes. 75 Although you can use 0 to set an unlimited number of passes I do not recommend 76 to do so. 77 78 The dk4iter_interval() function runs an iteration for a specified interval. 79 80 The dk4iter_start_point() function runs an iteration if just one 81 starting x value is specified. 82 83 If no context is specified the following defaults are used: 84 85 Option | Default 86 :----: | :------ 87 Algorithm | DK4_ITER_ALG_RF_ANDERSON_BJOERCK for dk4iter_interval(), DK4_ITER_ALG_NEWTON for dk4iter_start_point(). 88 Max passes | 256. 89 Y tolerance | 1.0e-8 90 X tolerance | 1.0e-8 91 Full machine precision | No. 92 Restricted x interval | None. 93 94 */ 95 96 97 98 /** Border values for maximum number of iteration passes. 99 */ 100 enum { 101 /** Number of passes for average cases. 102 */ 103 DK4_ITER_PASSES_REGULAR = 256 , 104 105 /** Do not set a limit on the number of passes. 106 Warning: Might result in an endless loop! 107 */ 108 DK4_ITER_PASSES_UNLIMITED = 0 109 }; 110 111 112 113 /** Iteration algorithms. 114 */ 115 enum { 116 /** Interval bisection. 117 */ 118 DK4_ITER_ALG_BISECTION = 0 , 119 120 /** Primitive from of regula falsi. 121 */ 122 DK4_ITER_ALG_RF_PRIMITIVE , 123 124 /** Regula falsi, Illinois variant. 125 */ 126 DK4_ITER_ALG_RF_ILLINOIS , 127 128 /** Regula falsi, Pegasus variant. 129 */ 130 DK4_ITER_ALG_RF_PEGASUS , 131 132 /** Regula falsi, Anderson-Bjoerck variant. 133 */ 134 DK4_ITER_ALG_RF_ANDERSON_BJOERCK , 135 136 /** Newton algorithm. 137 The function must place 2 elements 138 in the array specified by pointer: 139 Function value and derivative value. 140 */ 141 DK4_ITER_ALG_NEWTON , 142 143 /** Fix point algorithm. 144 The function must be the phi(x) 145 function from the 146 phi(x) = x equation. 147 */ 148 DK4_ITER_ALG_FIX_POINT 149 }; 150 151 152 153 /** Iteration result. 154 */ 155 enum { 156 /** Iteration succeeded. 157 */ 158 DK4_ITER_RESULT_SUCCESS = 1 , 159 160 /** Error: Too many passes without success. 161 */ 162 DK4_ITER_RESULT_E_PASSES = 0 , 163 164 /** Error: Infinite value or NaN in calculation. 165 */ 166 DK4_ITER_RESULT_E_INFINITE = -1 , 167 168 /** Error: X left initial interval. 169 Can happen with Newton and fix point 170 algorithm. 171 */ 172 DK4_ITER_RESULT_E_OOR = -2 , 173 174 /** Error: Not converging. 175 Fix point algorithm: Interval was enlarging. 176 */ 177 DK4_ITER_RESULT_E_CONV = -3 , 178 179 /** Function calculation failed. 180 */ 181 DK4_ITER_RESULT_E_FCT = -4 , 182 183 /** Invalid arguments passed to function call. 184 */ 185 DK4_ITER_RESULT_E_ARGS = -5 186 }; 187 188 189 190 /** Function to iterate. 191 @param d Destination address. One element for all algorithms 192 except DK4_ITER_ALG_NEWTON which saves function value and derivative 193 value in a 2 elements array. 194 @param x X position to calculate the function value for. 195 @param ps Parameter set, may be NULL. 196 @return Non-zero value on success, 0 on error. 197 */ 198 typedef int dk4_iter_fct_t(double *d, double x, const void *ps); 199 200 201 /** Iteration context. 202 */ 203 typedef struct { 204 double xmin; /**< Minimum of x interval. */ 205 double xmax; /**< Maximum of x interval. */ 206 double eps_x; /**< Epsilon for x change. */ 207 double eps_y; /**< Epsilon for absolute y value. */ 208 unsigned long maxpass; /**< Maximum number of passes. */ 209 int exact; /**< Flag: End only if there is no x change. */ 210 int algo; /**< Iteration algorithm to use. */ 211 int minmax; /**< Flags: min(1), max(2) set. */ 212 } dk4_iter_ctx_t; 213 214 215 216 #ifdef __cplusplus 217 extern "C" { 218 #endif 219 220 /** Open new iteration context. 221 Allocate memory for new iteration context, set up default value. 222 A context allocated by this function must be released after 223 use by the dk4iter_ctx_close() function. 224 @return Valid pointer to new context on success, NULL on error. 225 */ 226 227 dk4_iter_ctx_t * 228 dk4iter_ctx_open(void); 229 230 231 /** Initialize a context to default values. 232 @param ctx Context to initialize. 233 */ 234 235 void 236 dk4iter_ctx_init(dk4_iter_ctx_t *ctx); 237 238 239 /** Close iteration context. 240 Release memory assigned to the context. 241 @param ctx Context created by dk4iter_ctx_open(). 242 */ 243 244 void 245 dk4iter_ctx_close(dk4_iter_ctx_t *ctx); 246 247 248 /** Set epsilon value for x change. 249 @param ctx Context to modify. 250 @param eps Epsilon value for x change. 251 */ 252 253 void 254 dk4iter_ctx_set_eps_x(dk4_iter_ctx_t *ctx, double eps); 255 256 257 /** Set maximum absolute y value. 258 @param ctx Context to modify. 259 @param eps Maximum absolute y value. 260 */ 261 262 void 263 dk4iter_ctx_set_eps_y(dk4_iter_ctx_t *ctx, double eps); 264 265 266 /** Set maximum number of passes (iteration steps). 267 @param ctx Context to modify. 268 @param passes Maximum number of passes, 0 or negative values indicate 269 an unlimited number of steps. 270 */ 271 272 void 273 dk4iter_ctx_set_maxpass(dk4_iter_ctx_t *ctx, unsigned long passes); 274 275 276 /** Set flag for exact iteration. 277 If the flag is activated, iteration is continued until there is 278 no longer any change in the x value. For some functions you can 279 retrieve a result in machine precision using this flag, for other 280 functions the iteration may fail. 281 @param ctx Context to modify. 282 @param flag New flag value, 0=inactive, other=active. 283 The recommended value is 0. 284 */ 285 286 void 287 dk4iter_ctx_set_exact(dk4_iter_ctx_t *ctx, int flag); 288 289 290 /** Set up iteration algorithm. 291 @param ctx Context to modify. 292 @param algorithm Algorithm to use. 293 */ 294 295 void 296 dk4iter_ctx_set_algorithm(dk4_iter_ctx_t *ctx, int algorithm); 297 298 299 /** Set interval minimum. 300 The allowed interval is only used for Newton and fixed point 301 algorithm. 302 @param ctx Context to modify. 303 @param xmin Minimum x value allowed. 304 */ 305 306 void 307 dk4iter_ctx_set_min(dk4_iter_ctx_t *ctx, double xmin); 308 309 310 /** Set exlusive interval minimum (open interval border). 311 The allowed interval is only used for Newton and fixed point 312 algorithm. 313 @param ctx Context to modify. 314 @param xmin Minimum x value allowed. 315 */ 316 317 void 318 dk4iter_ctx_set_exclusive_min(dk4_iter_ctx_t *ctx, double xmin); 319 320 321 /** Set interval maximum. 322 The allowed interval is only used for Newton and fixed point 323 algorithm. 324 @param ctx Context to modify. 325 @param xmax Maximum x value allowed. 326 */ 327 328 void 329 dk4iter_ctx_set_max(dk4_iter_ctx_t *ctx, double xmax); 330 331 332 /** Set exclusive interval maximum (open interval border). 333 The allowed interval is only used for Newton and fixed point 334 algorithm. 335 @param ctx Context to modify. 336 @param xmax Maximum x value allowed. 337 */ 338 339 void 340 dk4iter_ctx_set_exclusive_max(dk4_iter_ctx_t *ctx, double xmax); 341 342 343 /** Run iteration. 344 The algorithm in the context must be one from: 345 DK4_ITER_ALG_BISECTION, DK4_ITER_ALG_RF_PRIMITIVE, DK4_ITER_ALG_RF_ILLINOIS, 346 DK4_ITER_ALG_RF_PEGASUS DK4_ITER_ALG_RF_ANDERSON_BJOERCK. 347 Without a context DK4_ITER_ALG_RF_ANDERSON_BJOERCK is used as default. 348 @param d Address of result variable. 349 @param pp Address of variable to store number of passes, may be NULL. 350 @param fct Function to find root for. 351 @param ps Parameter set for function, may be NULL. 352 @param a One interval border. 353 @param b Other interval border. 354 @param ctx Iteration context. 355 @return DK4_ITER_RESULT_SUCCESS on success, one from 356 DK4_ITER_RESULT_E_PASSES, DK4_ITER_RESULT_E_INFINITE, 357 DK4_ITER_RESULT_E_OOR, DK4_ITER_RESULT_E_CONV or 358 DK4_ITER_RESULT_E_FCT on error. 359 */ 360 361 int 362 dk4iter_interval( 363 double *d, 364 unsigned long *pp, 365 dk4_iter_fct_t *fct, 366 void const *ps, 367 double a, 368 double b, 369 dk4_iter_ctx_t const *ctx 370 ); 371 372 373 /** Run iteration. 374 The algorithm in the context must be one from: 375 DK4_ITER_ALG_NEWTON, DK4_ITER_ALG_FIX_POINT. 376 Without a context, DK4_ITER_ALG_NEWTON is used as default. 377 @param d Address of result variable. 378 @param pp Address of variable to store number of passes, may be NULL. 379 @param fct Function to find root for. 380 For Newton iteration this function must set two values 381 in the destination array: function value and derivative value. 382 For fixpoint iteration the function calculates the 383 phi(x) part of phi(x)=x. 384 @param ps Parameter set for function, may be NULL. 385 @param x0 Start point. 386 @param ctx Iteration context. 387 @return DK4_ITER_RESULT_SUCCESS on success, one from 388 DK4_ITER_RESULT_E_PASSES, DK4_ITER_RESULT_E_INFINITE, 389 DK4_ITER_RESULT_E_OOR, DK4_ITER_RESULT_E_CONV or 390 DK4_ITER_RESULT_E_FCT on error. 391 */ 392 393 int 394 dk4iter_start_point( 395 double *d, 396 unsigned long *pp, 397 dk4_iter_fct_t *fct, 398 void const *ps, 399 double x0, 400 dk4_iter_ctx_t const *ctx 401 ); 402 403 404 #ifdef __cplusplus 405 } 406 #endif 407 408 /* vim: set ai sw=4 ts=4 : */ 409 410 411 #endif 412