From 1f457376b478257b88d4a857f5ec1b6155442dd7 Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Sun, 20 Sep 2020 03:03:26 +0000 Subject: CTAN sync 202009200303 --- support/dktools/dk4iter.h | 413 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 413 insertions(+) create mode 100644 support/dktools/dk4iter.h (limited to 'support/dktools/dk4iter.h') diff --git a/support/dktools/dk4iter.h b/support/dktools/dk4iter.h new file mode 100644 index 0000000000..9ad4f544c3 --- /dev/null +++ b/support/dktools/dk4iter.h @@ -0,0 +1,413 @@ +/* +Copyright (C) 2018-2020, Dirk Krause +SPDX-License-Identifier: BSD-3-Clause +*/ + +/* + WARNING: This file was generated by the dkct program (see + http://dktools.sourceforge.net/ for details). + Changes you make here will be lost if dkct is run again! + You should modify the original source and run dkct on it. + Original source: dk4iter.ctr +*/ + +#ifndef DK4ITER_H_INCLUDED +/** Avoid multiple inclusions. */ +#define DK4ITER_H_INCLUDED 1 + + +#line 8 "dk4iter.ctr" + +/** @file dk4iter.h Iteration algorithms for root finding. + +This module implements the following root finding iteration algorithms: +- Bisection +- Regula falsi (primitive form, Illinois, Pegasus, Anderson-Bjoerck) +- Newton +- fix point + +The function to iterate must be implemented as dk4_iter_fct_t. +This function type returns an integer value (non-zero to indicate a +successful calculation, 0 to indicate an error). +The function expects the following arguments: +- Result address
+ Address of a variable or an array to store the calculation result. + Functions for Newton iteration algorithm store 2 values: Function value + and value of the first derivative. +- X position
+ The x value you want a function value for. +- Address of parameter set. + Additional parameters probably required by the function. I.e. for a + polynomial calculation function you may specify the coefficients here. + This parameter is optional. + +Details for an iteration may be specified in an iteration context. +The dk4iter_ctx_open() creates such a context and returns a pointer. +Use dk4iter_ctx_close() to release the context when done with it. +Alternatively use a automatic/static variable of the dk4_iter_ctx_t type +and initialize it using the dk4iter_ctx_init() function. + +The dk4iter_ctx_set_algorithm() function chooses the iteration method. + +For Newton and fixpoint the context may specify an x interval the +iteration must not leave. Leaving the interval results in abort. +The dk4iter_ctx_set_min(), dk4iter_ctx_set_exclusive_min(), +dk4iter_ctx_set_max() and dk4iter_ctx_set_exclusive_max() functions can +be used to set closed and open interval borders. + +Tolerance values (epsilon) may be specified for +- y direction unless fixpoint is used and/or +- x direction. +Use dk4iter_ctx_set_eps_y() and dk4iter_ctx_set_eps_x() to set the +tolerances. +Use 0.0 or negative tolerances to skip one check (not both!). + +Once the iteration reached allowed y difference you can decide +to stop when the x difference is in allowed tolerance range too or +to continue until full machine precision is reached (new x is exactly +the same as previous x). +I do not recommend attempts to iterate to full machine precision as this +(a) may fail for some functions resulting in an oscillation and +(b) uses a larger number of iteration passes and. +Use dk4iter_ctx_set_exact() to control this. + +The dk4iter_ctx_set_maxpass() function sets the maximum number of +iteration passes (iteration steps). The iteration is aborted if there +is no success within this maximum number of passes. +Although you can use 0 to set an unlimited number of passes I do not recommend +to do so. + +The dk4iter_interval() function runs an iteration for a specified interval. + +The dk4iter_start_point() function runs an iteration if just one +starting x value is specified. + +If no context is specified the following defaults are used: + +Option | Default +:----: | :------ +Algorithm | DK4_ITER_ALG_RF_ANDERSON_BJOERCK for dk4iter_interval(), DK4_ITER_ALG_NEWTON for dk4iter_start_point(). +Max passes | 256. +Y tolerance | 1.0e-8 +X tolerance | 1.0e-8 +Full machine precision | No. +Restricted x interval | None. + +*/ + + + +/** Border values for maximum number of iteration passes. +*/ +enum { + /** Number of passes for average cases. + */ + DK4_ITER_PASSES_REGULAR = 256 , + + /** Do not set a limit on the number of passes. + Warning: Might result in an endless loop! + */ + DK4_ITER_PASSES_UNLIMITED = 0 +}; + + + +/** Iteration algorithms. +*/ +enum { + /** Interval bisection. + */ + DK4_ITER_ALG_BISECTION = 0 , + + /** Primitive from of regula falsi. + */ + DK4_ITER_ALG_RF_PRIMITIVE , + + /** Regula falsi, Illinois variant. + */ + DK4_ITER_ALG_RF_ILLINOIS , + + /** Regula falsi, Pegasus variant. + */ + DK4_ITER_ALG_RF_PEGASUS , + + /** Regula falsi, Anderson-Bjoerck variant. + */ + DK4_ITER_ALG_RF_ANDERSON_BJOERCK , + + /** Newton algorithm. + The function must place 2 elements + in the array specified by pointer: + Function value and derivative value. + */ + DK4_ITER_ALG_NEWTON , + + /** Fix point algorithm. + The function must be the phi(x) + function from the + phi(x) = x equation. + */ + DK4_ITER_ALG_FIX_POINT +}; + + + +/** Iteration result. +*/ +enum { + /** Iteration succeeded. + */ + DK4_ITER_RESULT_SUCCESS = 1 , + + /** Error: Too many passes without success. + */ + DK4_ITER_RESULT_E_PASSES = 0 , + + /** Error: Infinite value or NaN in calculation. + */ + DK4_ITER_RESULT_E_INFINITE = -1 , + + /** Error: X left initial interval. + Can happen with Newton and fix point + algorithm. + */ + DK4_ITER_RESULT_E_OOR = -2 , + + /** Error: Not converging. + Fix point algorithm: Interval was enlarging. + */ + DK4_ITER_RESULT_E_CONV = -3 , + + /** Function calculation failed. + */ + DK4_ITER_RESULT_E_FCT = -4 , + + /** Invalid arguments passed to function call. + */ + DK4_ITER_RESULT_E_ARGS = -5 +}; + + + +/** Function to iterate. + @param d Destination address. One element for all algorithms + except DK4_ITER_ALG_NEWTON which saves function value and derivative + value in a 2 elements array. + @param x X position to calculate the function value for. + @param ps Parameter set, may be NULL. + @return Non-zero value on success, 0 on error. +*/ +typedef int dk4_iter_fct_t(double *d, double x, const void *ps); + + +/** Iteration context. +*/ +typedef struct { + double xmin; /**< Minimum of x interval. */ + double xmax; /**< Maximum of x interval. */ + double eps_x; /**< Epsilon for x change. */ + double eps_y; /**< Epsilon for absolute y value. */ + unsigned long maxpass; /**< Maximum number of passes. */ + int exact; /**< Flag: End only if there is no x change. */ + int algo; /**< Iteration algorithm to use. */ + int minmax; /**< Flags: min(1), max(2) set. */ +} dk4_iter_ctx_t; + + + +#ifdef __cplusplus +extern "C" { +#endif + +/** Open new iteration context. + Allocate memory for new iteration context, set up default value. + A context allocated by this function must be released after + use by the dk4iter_ctx_close() function. + @return Valid pointer to new context on success, NULL on error. +*/ + +dk4_iter_ctx_t * +dk4iter_ctx_open(void); + + +/** Initialize a context to default values. + @param ctx Context to initialize. +*/ + +void +dk4iter_ctx_init(dk4_iter_ctx_t *ctx); + + +/** Close iteration context. + Release memory assigned to the context. + @param ctx Context created by dk4iter_ctx_open(). +*/ + +void +dk4iter_ctx_close(dk4_iter_ctx_t *ctx); + + +/** Set epsilon value for x change. + @param ctx Context to modify. + @param eps Epsilon value for x change. +*/ + +void +dk4iter_ctx_set_eps_x(dk4_iter_ctx_t *ctx, double eps); + + +/** Set maximum absolute y value. + @param ctx Context to modify. + @param eps Maximum absolute y value. +*/ + +void +dk4iter_ctx_set_eps_y(dk4_iter_ctx_t *ctx, double eps); + + +/** Set maximum number of passes (iteration steps). + @param ctx Context to modify. + @param passes Maximum number of passes, 0 or negative values indicate + an unlimited number of steps. +*/ + +void +dk4iter_ctx_set_maxpass(dk4_iter_ctx_t *ctx, unsigned long passes); + + +/** Set flag for exact iteration. + If the flag is activated, iteration is continued until there is + no longer any change in the x value. For some functions you can + retrieve a result in machine precision using this flag, for other + functions the iteration may fail. + @param ctx Context to modify. + @param flag New flag value, 0=inactive, other=active. + The recommended value is 0. +*/ + +void +dk4iter_ctx_set_exact(dk4_iter_ctx_t *ctx, int flag); + + +/** Set up iteration algorithm. + @param ctx Context to modify. + @param algorithm Algorithm to use. +*/ + +void +dk4iter_ctx_set_algorithm(dk4_iter_ctx_t *ctx, int algorithm); + + +/** Set interval minimum. + The allowed interval is only used for Newton and fixed point + algorithm. + @param ctx Context to modify. + @param xmin Minimum x value allowed. +*/ + +void +dk4iter_ctx_set_min(dk4_iter_ctx_t *ctx, double xmin); + + +/** Set exlusive interval minimum (open interval border). + The allowed interval is only used for Newton and fixed point + algorithm. + @param ctx Context to modify. + @param xmin Minimum x value allowed. +*/ + +void +dk4iter_ctx_set_exclusive_min(dk4_iter_ctx_t *ctx, double xmin); + + +/** Set interval maximum. + The allowed interval is only used for Newton and fixed point + algorithm. + @param ctx Context to modify. + @param xmax Maximum x value allowed. +*/ + +void +dk4iter_ctx_set_max(dk4_iter_ctx_t *ctx, double xmax); + + +/** Set exclusive interval maximum (open interval border). + The allowed interval is only used for Newton and fixed point + algorithm. + @param ctx Context to modify. + @param xmax Maximum x value allowed. +*/ + +void +dk4iter_ctx_set_exclusive_max(dk4_iter_ctx_t *ctx, double xmax); + + +/** Run iteration. + The algorithm in the context must be one from: + DK4_ITER_ALG_BISECTION, DK4_ITER_ALG_RF_PRIMITIVE, DK4_ITER_ALG_RF_ILLINOIS, + DK4_ITER_ALG_RF_PEGASUS DK4_ITER_ALG_RF_ANDERSON_BJOERCK. + Without a context DK4_ITER_ALG_RF_ANDERSON_BJOERCK is used as default. + @param d Address of result variable. + @param pp Address of variable to store number of passes, may be NULL. + @param fct Function to find root for. + @param ps Parameter set for function, may be NULL. + @param a One interval border. + @param b Other interval border. + @param ctx Iteration context. + @return DK4_ITER_RESULT_SUCCESS on success, one from + DK4_ITER_RESULT_E_PASSES, DK4_ITER_RESULT_E_INFINITE, + DK4_ITER_RESULT_E_OOR, DK4_ITER_RESULT_E_CONV or + DK4_ITER_RESULT_E_FCT on error. +*/ + +int +dk4iter_interval( + double *d, + unsigned long *pp, + dk4_iter_fct_t *fct, + void const *ps, + double a, + double b, + dk4_iter_ctx_t const *ctx +); + + +/** Run iteration. + The algorithm in the context must be one from: + DK4_ITER_ALG_NEWTON, DK4_ITER_ALG_FIX_POINT. + Without a context, DK4_ITER_ALG_NEWTON is used as default. + @param d Address of result variable. + @param pp Address of variable to store number of passes, may be NULL. + @param fct Function to find root for. + For Newton iteration this function must set two values + in the destination array: function value and derivative value. + For fixpoint iteration the function calculates the + phi(x) part of phi(x)=x. + @param ps Parameter set for function, may be NULL. + @param x0 Start point. + @param ctx Iteration context. + @return DK4_ITER_RESULT_SUCCESS on success, one from + DK4_ITER_RESULT_E_PASSES, DK4_ITER_RESULT_E_INFINITE, + DK4_ITER_RESULT_E_OOR, DK4_ITER_RESULT_E_CONV or + DK4_ITER_RESULT_E_FCT on error. +*/ + +int +dk4iter_start_point( + double *d, + unsigned long *pp, + dk4_iter_fct_t *fct, + void const *ps, + double x0, + dk4_iter_ctx_t const *ctx +); + + +#ifdef __cplusplus +} +#endif + +/* vim: set ai sw=4 ts=4 : */ + + +#endif -- cgit v1.2.3