/*
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