# Roots of Nonlinear Functions

 Home Roots Home Secant Methods Home Secant Method Regula Falsi Method Illinois Algoritm

## Regula Falsi

The regula falsi method is a variant of the secant method.  Given a continuous real-valued function of a real-variable, f(x), in which one wants to approximate the location of at least one root the regula falsi method proceeds after finding two values such that the function evaluated at the two values has opposite signs, i.e. if a and b are two numbers such that f(a)·f(b) < 0 then a zero of f(x) exists on the interval (min(a,b), max(a,b)).

The fact that a zero of f(x) exists in the interval (a,b) is a consequence of the intermediate value theorem of elementary analysis or from topology using the lemma that the continuous image of a connected set is connected as well as the lemma that a subset of R,(with the usual topology) with more than two points is connected if and only if it is an interval.

The regula falsi iterative procedure uses two estimates as in the secant method to estimate a new estimate, but the estimate which is replaced is the one for which the sign of the function is the same as the sign of the function for the new estimate. The regula falsi method is guaranteed to converge, but convergence may be extremely slow. The iterative process is continued until the halted. In the implementation given below the process is either terminated by the user, or when there is no machine representable number between the two endpoints, or when the function evaluates to zero at the new estimate.

It is best to avoid using the regula falsi method for final convergence to a root. It can be used as a good starting method. The restriction that the two estimates bracket the root such that the function evaluated at the two estimates has opposite signs means that regula falsi avoids the problems associated with having local extrema since it is no longer possible to attempt to divide by zero as in the secant method. Since regula falsi requires initial estimates in which the function evaluated at the initial estimates has opposite signs, it is impossible to use regula falsi to find the zeros of strictly nonnegative functions or nonpositive functions.

There are several comments which should be made in locating a zero of a continuous real-valued function of a real-variable f(x):
• If α is any non-zero real number, then f(x) and α f(x) have the same roots. I.e. you can scale the function f(x) without modifying the location of the roots.

• When the regula falsi method terminates, the final interval is guaranteed to contain a zero of the function. But the final interval could also contain more than one zero of the function, in fact it could contain an uncountably infinite number of zeros.

### Function List

• int Regula_Falsi( double (*f)(double), double *a, double *fa,
double *b, double *fb, void *data[],
int (*verify_setup)(double, double, double, double, void**, int*),
int (*terminate)(double, double, double, double, unsigned int, void**,int*),
int *msg)

Locate at least one root of f(x) in the interval ( min(*a,*b), max(*a, *b) ) where *fa = f(*a), *fb = f(*b) and *fa · *fb < 0. The procedure terminates when the user supplied routine terminate() returns a 1 in which case the Regula_Falsi returns a 2. Regula_Falsi returns a 1 if the user supplied routine verify_setup() returns a 0 which signifies that the initial setup has an error. If the user supplied routine verify_setup() returns a 1 or non-zero then the iteration process is started. Regula_Falsi can also terminate with different return values, see the table below.

An example of a user supplied terminate() routine and a user supplied verify_setup() is given below in the routines Regula_Falsi_Terminate and Regula_Falsi_Verify_Setup respectively. Also included below is a routine to setup the array data called Regula_Falsi_Setup.

The return values for the Regula_Falsi are:  Return Values Description 0 At least one of the pointer arguments is NULL. 1 The user supplied verify_setup() function returned a 0. The user specified error code should be stored at *msg. 2 The user supplied terminate() function returned a 1. The user specified termination code should be stored at *msg. 3 There is no machine representable number between the two endpoints. 4 The function evaluates to zero at the intersection of the secant and the x-axis.

The arguments to Regula_Falsi are:  Argument Description f A real-valued function of a real-variable, i.e. a function with an argument of type double which returns a double. a A pointer to one end of the interval for which the function at the endpoints has opposite signs. When Regula_Falsi is invoked, *a is the initial value of an endpoint, on return *a is the final value of the endpoint. fa A pointer to the value of f evaluated at *a, i.e. *fa = f(*a). When Regula_Falsi is invoked, *fa is the user supplied value of f(*a) where *a is the initial value at that endpoint, on return *fa is the final value of f(*a) where *a is the final value at that endpoint. b A pointer to the other end of the interval for which the function at the endpoints has opposite signs. When Regula_Falsi is invoked, *b is the initial value of an endpoint, on return *b is the final value of the endpoint. fb A pointer to the value of f evaluated at *b, i.e. *fb = f(*b). When Regula_Falsi is invoked, *fb is the user supplied value of f(*b) where *b is the initial value at that endpoint, on return *fb is the final value of f(*b) where *b is the final value at that endpoint. data An array of pointers of the type void*. The array data is not used by Regula_Falsi directly but only passed to the user supplied verify_setup() and terminate() routines. This allows the user to pass additional information to the terminate() routine so it can determine whether or not to terminate the iteration. The user supplied verify_setup() routine generally only checks that data has no obvious flaws. verify_setup() A user supplied routine to verify that the input data to Regula_Falsi and to the user supplied terminate() routine met the requirements that both routines function correctly. For a description of the arguments to verify_setup(), see the Regula_Falsi_Verify_Setup routine below which is an example of a user supplied verify_setup() routine. If verify_setup() detects an error, it can store an error code at *msg thus allowing the user to determine the reason for the error. terminate() A user supplied routine to terminate or continue iterating. For a description of the arguments to terminate(), see the Regula_Falsi_Terminate routine below which is an example of a user supplied terminate() routine. If terminate() returns 1 halt, it can store a halt code at *msg thus allowing the user to determine the reason for the halting. msg A pointer to an integer. This address is passed to the user supplied routines so that they can return error codes or halt codes.

• int Regula_Falsi_Terminate( double a, double fa, double b, double fb, unsigned int iteration_count, void *data[], int *halt_code)

Regula_Falsi_Terminate() is an example of a user supplied terminate() routine. This function returns a 0 if the process is to continue and a 1 if the iterating process is to halt. The arguments a, fa, b, fb of Regula_Falsi_Terminate() correspond to the dereferenced arguments a, fa, b, fb of the routine Regula_Falsi(), while data is the same, halt_code corresponds to argument msg of Regula_Falsi() and iteration_count is internal to Regula_Falsi().

The return values for the Regula_Falsi_Terminate are:  Return Values Description 0 Continue iterating. 1 Terminate iterating.

For this routine the data array consists of four pointers: Data Array Index Description 0 A (double *) pointer, cast as (void*), to the relative tolerance. 1 A (double *) pointer, cast as (void*), to the absolute tolerance. 2 A (double *) pointer, cast as (void*), to the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine convergence. 3 A (double *) pointer, cast as (void*), to the upper bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine convergence. 4 An (unsigned int*) pointer, cast as (void*), to the maximum number of iterations allowed.

If a 1 is returned (halt the iteration) then *halt_code is set to the following values: Halt Code Meaning 0 The process converges using the relative tolerance test, i.e. |b - a| / min(|a|,|b|) ≤ relative_tolerance, where both a and b must have the same sign. 1 The process converges using the absolute tolerance test, i.e. |b - a| ≤ absolute_tolerance. 2 The function vanishes at one or both of the endpoints. 3 The number of iterations meets or exceeds the maximum allowable number of iterations without converging.

• int Regula_Falsi_Verify_Setup( double a, double fa, double b, double fb, void *data[], int *err)

Regula_Falsi_Verify_Setup() is an example of a user supplied verify_setup() routine. This function returns a 0 if an error was detected and a 1 if no error was detected, i.e. start the iteration process. The arguments a, fa, b, fb of Regula_Falsi_Verify_Setup() correspond to the dereferenced arguments a, fa, b, fb of the routine Regula_Falsi(), while data is the same and err corresponds to argument msg of Regula_Falsi().

For this routine the data array consists of five pointers:  Index Description 0 A (double *) pointer to the relative tolerance. 1 A (double *) pointer to the absolute tolerance. 2 A (double *) pointer to the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine whether to halt the iteration or not. 3 A (double *) pointer to the upper bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to whether to halt the iteration or not. 4 An (unsigned int *) pointer to the maximum number of iterations allowed.

If a 0 is returned (an error was detected) then *err is set to the following values:  Number Meaning 1 The endpoints agree i.e. a = b. 2 The function evaluated at the endpoints has the same sign. In case the function vanishes at an endpoint, the terminate() procedure will terminate the iteration. 3 The address of the data array is 0. 4 The address of an element of the data array is 0. 5 The relative tolerance is non-positive. 6 The absolute tolerance is non-positive. 7 The lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test is not negative. 8 The upper bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test is not positive.

• int Regula_Falsi_Setup( double *rel_tolerance, double *abs_tolerance, double *test_region_lower_bound, double *test_region_upper_bound, unsigned int *max_number_of_iterations, void *data[])

Regula_Falsi_Setup() is an example of a program to populate the array data for use in both Regula_Falsi_Verify_Setup() and Regula_Falsi_Terminate() routines after being passed to Regula_Falsi(). In particular,
data[0] = (void *)rel_tolerance,
data[1] = (void *)abs_tolerance,
data[2] = (void *)test_region_lower_bound,
data[3] = (void *)test_region_upper_bound, and
data[4] = (void *)max_number_of_iterations,
where *rel_tolerance is the relative tolerance, *abs_tolerance is the absolute tolerance, *test_region_lower_bound is the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine whether to halt the iteration or not, *test_region_upper_bound is the lower bound of the region which determines whether to use the relative tolerance test or the absolute tolerance test to determine whether to halt the iteration or not and *max_number_of_iterations is the maximum number of iterations to try before terminating the iteration. The array data must be dimensioned at least 5 in the calling routine.

The function, Regula_Falsi_Setup(), returns a 0 if at least one of the arguments is NULL, otherwise the function returns a 1.