summaryrefslogtreecommitdiff
path: root/support/dktools/dk4iter.h
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2020-09-20 03:03:26 +0000
committerNorbert Preining <norbert@preining.info>2020-09-20 03:03:26 +0000
commit1f457376b478257b88d4a857f5ec1b6155442dd7 (patch)
tree2a06a60551dea362cf8cb0cb0ba66c78608717c4 /support/dktools/dk4iter.h
parentac690ca29ad5bf8a5203a65fd6252f7b564f4727 (diff)
CTAN sync 202009200303
Diffstat (limited to 'support/dktools/dk4iter.h')
-rw-r--r--support/dktools/dk4iter.h413
1 files changed, 413 insertions, 0 deletions
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<br>
+ 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<br>
+ 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