# A Generalized Regula Falsi Method for Finding Zeros and Extrema of Real Functions

Authors: Abel Gomes; José Morgado
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Many zero-finding numerical methods are based on the Intermediate Value Theorem, which states that a zero of a real functionf:ℝ→ℝ is bracketed in a given interval A,B⊂ℝ if fA and fB have opposite signs; that is, fA·fB<0. But, some zeros cannot be bracketed this way because they do not satisfy the precondition fA·fB<0. For example, local minima and maxima that annihilate f may not be bracketed by the Intermediate Value Theorem. In this case, we can always use a numerical method for bracketing extrema, checking then whether it is a zero of f or not. Instead, this paper introduces a single numerical method, called generalized regula falsi (GRF) method to determine both zeros and extrema of a function. Consequently, it differs from the standard regula falsi method in that it is capable of finding any function zero in a given interval A,B⊂ℝ even when the Intermediate Value Theorem is not satisfied.


---

## Body

## 1. Introduction

Numerical methods such asbisection method [1, 2], secant method [3–6], regula falsi method [7, 8], and Newton-Raphson method [9, 10], amongst others, are known as zero-finding algorithms. They are used for bracketing a zero. We say that a zero is bracketed in the interval [A,B] if f(A) and f(B) have opposite signs; that is, f(A)·f(B)<0. In this paper, a zero of this sort is called a crossing zero, as illustrated in Figure 1(a).The generalized regula falsi method for (a) zeros and (b) extrema.
(a)
(b)Although this class of methods satisfying the Intermediate Value Theorem succeeds in finding most zeros (i.e., crossing zeros), they fail to bracket zeros that are also extrema, here calledextremal zeros. We say that an extremum is bracketed in the interval [A,B] if f(A) and f(B), but not their derivatives, have identical signs; that is, f(A)·f(B)>0 and f′(A)·f′(B)<0. If f(A)>0 and f(B)>0, “go downhill, taking steps of increasing size, until your function starts back uphill” [4]. At this point, we have only to check that such a minimum is a zero. Analogously, if f(A)<0 and f(B)<0, basically, “go uphill, taking steps of increasing size, until your function starts back downhill” [4]. Then, we have only to check that such a maximum is a zero.Despite the existence of algorithms for finding extrema (maxima and minima) of functions in the numerical analysis literature, there is no single iterative formula to find both crossing and extremum zeros of a real function. Such a method is described in the next section and is calledgeneralized regula falsi method.


## 2. Generalized Regula Falsi Method

The generalized regula falsi (GRF) method is based on the ratio of similar triangles. Its main novelty is that it can be used to compute both zeros and extrema through a single interpolation formula.Let us consider the interval[A,B], as illustrated in Figures 1(a) and 1(b), being |f(A)| and |f(B)| the absolute values of the function at A and B, respectively. The endpoints of the interval [A,B] work as two distinct estimates for a zero of f(x)=0. The next estimate X is the intersection point of the straight-line segments (A,0)(B,0)¯ and (A,|f(A)|)(B,|f(B)|)¯, which is given by
(1)X=A+|f(A)||f(A)|+|f(B)|·(B-A).As known, the vectorial equation of the line that passes through the pointsA and B is given by
(2)X(t)=A+t·(B-A)
with A=X(0) and B=X(1). Thus, the next estimate X occurs at t=|f(A)|/(|f(A)|+|f(B)|), a result due to the following equality of triangles:
(3)|f(A)|t=|f(B)|1-t.Remarkably, as explained below, the iterative formula (1) applies to both zeros and extrema.


### 2.1. Zeros

The computation of a zero is illustrated in Figure1(a). Let us assume that f(A)·f(B)<0, with f(A)<0. By replacing |f(A)|=-f(A) and |f(B)|=f(B) into (1), we obtain
(4)X=A-f(A)f(B)-f(A)·(B-A),
that is, the interpolation formula of the well-known regula falsi method [1]. It is used to determine crossing zeros.


### 2.2. Extrema

The computation of a local extremum is done exactly in the same way for minima and maxima. Let us first consider a local minimum as illustrated in Figure1(b). In this case, f(A)·f(B)>0, with f(A)>0. By replacing |f(A)|=f(A) and |f(B)|=f(B) into (1), we obtain
(5)X=A+f(A)f(B)+f(A)·(B-A),that is, the next estimate X of a local minimum.Let us now consider that a reflection takes place across thex-axis in Figure 1(b). In this case, we have a function with a local maximum; that is, f(A)·f(B)>0, with f(A)<0. Again, by replacing |f(A)|=-f(A) and |f(B)|=-f(B) into (1), we obtain the next estimate X through (5).Thus, formula (5) works equally well for local minima and maxima, independently of whether f(A) and f(B) are either positive or negative. In fact, looking at (4) and (5), we see that it is enough to change the sign of either f(A) or f(B) to determine the next estimate X of an extremum through the regula falsi technique.However, the conditionf(A)·f(B)>0 only indicates that there may be an extremum between A and B. We have to evaluate the finite difference d(x)=(f(x+h)-f(x))/h, with an infinitesimal h, at A and B and test whether they have opposite signs, that is, d(A)·d(B)<0, to guarantee that an extremum exists in [A,B]. We use the finite difference—the discrete counterpart of the derivative—of a function at a given point for two main reasons.(i)
Consistency: the regula falsi method does not use derivatives. So, the generalized regula falsi method does not use them for consistency either.(ii)
Differentiability: there are zeros and extrema at which derivatives do not exist. For example, f(x)=|x|1/3 in Figure 3(f) has a cusp at x=0 that is also a minimum. Derivatives cannot be used in this case because the program would break down.Therefore, we have to check whether the finite differenced(X) of the estimate X is very close to zero. If so, we have an extremum at X approximately. Besides, if f(X)≈0, with an accuracy of 10-6, then X is a zero.In short, in the literature, we find numerical methods for calculating zeros and extrema. The main novelty of the method introduced in this paper is its ability to compute zeros and extrema by means of a single interpolation formula (cf. formula (1)), that is, using the same formula.


### 2.3. Convergence Analysis

The convergence of the GRF method is guaranteed by the following theorem.Theorem 1.
Letf be a continuous real function on [A,B]⊂ℝ and f(A)·f(B)<0 or d(A)·d(B)<0. If P is the only zero (i.e.,f(P)=0) or extremum (i.e.,d(P)=0) in [A,B], then the GRF method generates a sequence {Pn}n=1+∞ converging to P for two initial approximations P1=A and P2=B.Proof.
Without loss of generality, that is equivalent to prove the existence of a sequence{In}n=1+∞ of intervals In=[Pn,Pn+1] converging to P, with P∈In for all n.
Letl(In) be the length of the interval In so that l(I1)=|P2-P1|, l(I2)=|P3-P2|, and
(6)l(I2)l(I1)=|P3-P2||P2-P1|.
Now, from (1) we obtain
(7)l(I2)l(I1)=|P2+(|f(P2)|/(|f(P1)|+|f(P2)|))·(P1-P2)-P2||P2-P1|=|f(P2)||f(P1)|+|f(P2)|
or
(8)l(I2)=l(I1)·|f(P2)||f(P1)|+|f(P2)|.
In general, we can write(9)l(In)=l(In-1)·|f(Pn)||f(Pn-1)|+|f(Pn)|.
Taking into account that(10)0<|f(Pn)||f(Pn-1)|+|f(Pn)|<1
we havel(In)<l(In-1) for all n. Thus, the sequence {l(In)}n=1+∞ is monotone decreasing. In addition, it is bounded because 0≤l(In)≤|B-A|. So, by the Monotone Convergence Theorem we can conclude that {l(In)}n=1+∞ is convergent. Taking into account that P∈In for all n, we conclude that the GRF method converges to P, being P a zero or an extremum of f.It is known that the zero-finding regula falsi method converges linearly [9]. Intuitively, we expect that the GRF method also converges linearly because it uses the same interpolation formula and bracketing strategy for both zeros and extrema.Theorem 2.
The GRF method has linear convergence.Proof.
LetP0,P1,P2,…,Pn,… be a sequence of approximations to either a zero or an extremum P produced by the GRF method, where limn→∞Pn=P. Let ϵn=Pn-P be the error in the nth iterate.
By (1), the successive iterations are
(11)Pn+1=Pn+|f(Pn)||f(Pn)|+|f(Pn-1)|·(Pn-1-Pn).
To determine the speed of convergence subtractP and divide by ϵn=Pn-P to get(12)ϵn+1ϵn=1+|f(Pn)||f(Pn)|+|f(Pn-1)|·(Pn-1-P)-(Pn-P)Pn-P=1+(Pn-1-PPn-P-1)·|f(Pn)||f(Pn)|+|f(Pn-1)|=1+(ϵn-1ϵn-1)·|f(Pn)||f(Pn)|+|f(Pn-1)|.
Sincelimn→∞(ϵn+1/ϵn)=limn→∞(ϵn/ϵn-1) and limn→∞Pn-1=limn→∞Pn=P, we obtain
(13)limn→∞ϵn+1ϵn=1+(1limn→∞(ϵn+1/ϵn)-1)·12
from where we conclude that limn→∞(ϵn+1/ϵn)=1. This concludes the proof.


### 2.4. GRF Implementation

The C function that implements the generalized regula falsi method returns either a zero or an extremum bracketed in a given interval[A,B] (see Algorithm 1).Algorithm 1
#
i
nclude  <math.h>
#define  ACY  1.0E–6   accuracy  for  estimates,  function,  and  finite  difference  values
#define  h  1.0E–7              infinitesimal  for  finite  diferences
double  GRF(float(*func)(double),  double  A,  doubleB,  int  n)
{
double  X,fX,dX,A,fA,dA,B,fB,dB,a,fa,da,b,fb,db;
while((fabs(B-A)>ACY)&&(–n>0))
{
doublefA=(*func)(A);
doubledA=((*func)(A+h)-(*func)(A))/h;
if((fabs(fA)<ACY)||(fabs(dA)<ACY))//zeroorextremum
returnA;
fB=(*func)(B);
dB=((*func)(B+h)-(*func)(B))/h;
if((fabs(fB)<ACY)||(fabs(dB)<ACY))//zeroorextremum
returnB;
X=A+fabs(fA)/(fabs(fA)+fabs(fB))*(B-A);
fX=(*func)(X);
dX=((*func)(X+h)-(*func)(X))/h;
if((fabs(fX)<ACY)||(fabs(dX)<ACY))//zeroorextremum
returnX;
if((fA*fX<0)||(dA*dX<0))
B=X;
else
if((fX*fB<0)||(dX*dB<0))
A=X;
}
}Note that, for the sake of convenience, we have used the settingh=1.0E-7 for evaluating finite differences, but this is clearly prone to cancellation errors. A better choice to h would be ϵX, where ϵ denotes the machine precision, which is typically of the order 2.2×10-16 for doubles on a 32-bit computer.


## 2.1. Zeros

The computation of a zero is illustrated in Figure1(a). Let us assume that f(A)·f(B)<0, with f(A)<0. By replacing |f(A)|=-f(A) and |f(B)|=f(B) into (1), we obtain
(4)X=A-f(A)f(B)-f(A)·(B-A),
that is, the interpolation formula of the well-known regula falsi method [1]. It is used to determine crossing zeros.


## 2.2. Extrema

The computation of a local extremum is done exactly in the same way for minima and maxima. Let us first consider a local minimum as illustrated in Figure1(b). In this case, f(A)·f(B)>0, with f(A)>0. By replacing |f(A)|=f(A) and |f(B)|=f(B) into (1), we obtain
(5)X=A+f(A)f(B)+f(A)·(B-A),that is, the next estimate X of a local minimum.Let us now consider that a reflection takes place across thex-axis in Figure 1(b). In this case, we have a function with a local maximum; that is, f(A)·f(B)>0, with f(A)<0. Again, by replacing |f(A)|=-f(A) and |f(B)|=-f(B) into (1), we obtain the next estimate X through (5).Thus, formula (5) works equally well for local minima and maxima, independently of whether f(A) and f(B) are either positive or negative. In fact, looking at (4) and (5), we see that it is enough to change the sign of either f(A) or f(B) to determine the next estimate X of an extremum through the regula falsi technique.However, the conditionf(A)·f(B)>0 only indicates that there may be an extremum between A and B. We have to evaluate the finite difference d(x)=(f(x+h)-f(x))/h, with an infinitesimal h, at A and B and test whether they have opposite signs, that is, d(A)·d(B)<0, to guarantee that an extremum exists in [A,B]. We use the finite difference—the discrete counterpart of the derivative—of a function at a given point for two main reasons.(i)
Consistency: the regula falsi method does not use derivatives. So, the generalized regula falsi method does not use them for consistency either.(ii)
Differentiability: there are zeros and extrema at which derivatives do not exist. For example, f(x)=|x|1/3 in Figure 3(f) has a cusp at x=0 that is also a minimum. Derivatives cannot be used in this case because the program would break down.Therefore, we have to check whether the finite differenced(X) of the estimate X is very close to zero. If so, we have an extremum at X approximately. Besides, if f(X)≈0, with an accuracy of 10-6, then X is a zero.In short, in the literature, we find numerical methods for calculating zeros and extrema. The main novelty of the method introduced in this paper is its ability to compute zeros and extrema by means of a single interpolation formula (cf. formula (1)), that is, using the same formula.


## 2.3. Convergence Analysis

The convergence of the GRF method is guaranteed by the following theorem.Theorem 1.
Letf be a continuous real function on [A,B]⊂ℝ and f(A)·f(B)<0 or d(A)·d(B)<0. If P is the only zero (i.e.,f(P)=0) or extremum (i.e.,d(P)=0) in [A,B], then the GRF method generates a sequence {Pn}n=1+∞ converging to P for two initial approximations P1=A and P2=B.Proof.
Without loss of generality, that is equivalent to prove the existence of a sequence{In}n=1+∞ of intervals In=[Pn,Pn+1] converging to P, with P∈In for all n.
Letl(In) be the length of the interval In so that l(I1)=|P2-P1|, l(I2)=|P3-P2|, and
(6)l(I2)l(I1)=|P3-P2||P2-P1|.
Now, from (1) we obtain
(7)l(I2)l(I1)=|P2+(|f(P2)|/(|f(P1)|+|f(P2)|))·(P1-P2)-P2||P2-P1|=|f(P2)||f(P1)|+|f(P2)|
or
(8)l(I2)=l(I1)·|f(P2)||f(P1)|+|f(P2)|.
In general, we can write(9)l(In)=l(In-1)·|f(Pn)||f(Pn-1)|+|f(Pn)|.
Taking into account that(10)0<|f(Pn)||f(Pn-1)|+|f(Pn)|<1
we havel(In)<l(In-1) for all n. Thus, the sequence {l(In)}n=1+∞ is monotone decreasing. In addition, it is bounded because 0≤l(In)≤|B-A|. So, by the Monotone Convergence Theorem we can conclude that {l(In)}n=1+∞ is convergent. Taking into account that P∈In for all n, we conclude that the GRF method converges to P, being P a zero or an extremum of f.It is known that the zero-finding regula falsi method converges linearly [9]. Intuitively, we expect that the GRF method also converges linearly because it uses the same interpolation formula and bracketing strategy for both zeros and extrema.Theorem 2.
The GRF method has linear convergence.Proof.
LetP0,P1,P2,…,Pn,… be a sequence of approximations to either a zero or an extremum P produced by the GRF method, where limn→∞Pn=P. Let ϵn=Pn-P be the error in the nth iterate.
By (1), the successive iterations are
(11)Pn+1=Pn+|f(Pn)||f(Pn)|+|f(Pn-1)|·(Pn-1-Pn).
To determine the speed of convergence subtractP and divide by ϵn=Pn-P to get(12)ϵn+1ϵn=1+|f(Pn)||f(Pn)|+|f(Pn-1)|·(Pn-1-P)-(Pn-P)Pn-P=1+(Pn-1-PPn-P-1)·|f(Pn)||f(Pn)|+|f(Pn-1)|=1+(ϵn-1ϵn-1)·|f(Pn)||f(Pn)|+|f(Pn-1)|.
Sincelimn→∞(ϵn+1/ϵn)=limn→∞(ϵn/ϵn-1) and limn→∞Pn-1=limn→∞Pn=P, we obtain
(13)limn→∞ϵn+1ϵn=1+(1limn→∞(ϵn+1/ϵn)-1)·12
from where we conclude that limn→∞(ϵn+1/ϵn)=1. This concludes the proof.


## 2.4. GRF Implementation

The C function that implements the generalized regula falsi method returns either a zero or an extremum bracketed in a given interval[A,B] (see Algorithm 1).Algorithm 1
#
i
nclude  <math.h>
#define  ACY  1.0E–6   accuracy  for  estimates,  function,  and  finite  difference  values
#define  h  1.0E–7              infinitesimal  for  finite  diferences
double  GRF(float(*func)(double),  double  A,  doubleB,  int  n)
{
double  X,fX,dX,A,fA,dA,B,fB,dB,a,fa,da,b,fb,db;
while((fabs(B-A)>ACY)&&(–n>0))
{
doublefA=(*func)(A);
doubledA=((*func)(A+h)-(*func)(A))/h;
if((fabs(fA)<ACY)||(fabs(dA)<ACY))//zeroorextremum
returnA;
fB=(*func)(B);
dB=((*func)(B+h)-(*func)(B))/h;
if((fabs(fB)<ACY)||(fabs(dB)<ACY))//zeroorextremum
returnB;
X=A+fabs(fA)/(fabs(fA)+fabs(fB))*(B-A);
fX=(*func)(X);
dX=((*func)(X+h)-(*func)(X))/h;
if((fabs(fX)<ACY)||(fabs(dX)<ACY))//zeroorextremum
returnX;
if((fA*fX<0)||(dA*dX<0))
B=X;
else
if((fX*fB<0)||(dX*dB<0))
A=X;
}
}Note that, for the sake of convenience, we have used the settingh=1.0E-7 for evaluating finite differences, but this is clearly prone to cancellation errors. A better choice to h would be ϵX, where ϵ denotes the machine precision, which is typically of the order 2.2×10-16 for doubles on a 32-bit computer.


## 3. Moving GRF Method

As illustrated in Figure2(a), the regula falsi method may converge slowly to a zero, spending many iterations in pulling distant bounds closer. For example, the crossing zero of the function f4(x)=tan(x)tan(x)-103 on [1.3,1.4] (Figure 3(d)) was found after 222 iterations. Likewise, the crossing zero of the function f5(x)=xex-10 on [-10.0,10.0] (Figure 3(e)) was only found after 999 iterations. The reason behind the slow convergence to some zeros is due to the fact that GRF method always retains a fixed endpoint of interval [A,B].The mGRF method.
(a)
(b)
(c)Graphs of six real functions: (a)f1 has 2 local maxima, 1 local minimum, 2 zeroed minima, and 2 crossing zeros; (b) f2 has an alternate sequence of local maxima and zeroed minima; (c) f3 has a single crossing zero; (d) f4 has a single crossing zero; (e) f5 has also a single crossing zero; (f) f6 has a zeroed minimum that is a cusp.
(a)
(b)
(c)
(d)
(e)
(f)The leading idea of speeding up the convergence of the GRF method is then moving the fixed point as well. To achieve that we replace the fixed endpoint of the interval[A,B] by the abscissa of a point Q that results from intersecting the tangents at the bound points (A,f(A)) and (B,f(B)) as shown in Figures 2(b) and 2(c). That is, the abscissa Q is the solution x of the following system of equations:
(14)y-f(A)=d(A)·(x-A)y-f(B)=d(B)·(x-B)
which yields
(15)Q=f(B)-f(A)+A·d(A)-B·d(B)d(A)-d(B),whered(A) and d(B) are the finite differences at A and B, respectively. Note that the estimate Q may be closer to the solution than the estimate produced by Newton's method that results from the intersection between a single tangent and the x-axis (Algorithm 2).Algorithm 2
d
ouble mGRF(float (*func)(double), double A, double B, int n)
{
double X, fX, dX, A, fA, dA, B, fB, dB, a, fa, da, b, fb, db;
while ( (fabs(B-A)>ACY) && (–n>0) )
{
fA=(*func)(A);
dA=((*func)(A+h)-(*func)(A))/h;
if ((fabs(fA)< ACY) || (fabs(dA)< ACY)) // zero or extremum
return A;
fB=(*func)(B);
dB=((*func)(B+h)-(*func)(B))/h;
if ((fabs(fB)< ACY) || (fabs(dB)< ACY)) // zero or extremum
return B;
X=A+fabs(fA)/(fabs(fA)+fabs(fB))*(B-A);
fX=(*func)(X);
dX=((*func)(X+h)-(*func)(X))/h;
if ((fabs(fX)< ACY) || (fabs(dX)< ACY)) // zero or extremum
return X;
if ((fA*fX<0) || (dA*dX<0))
{
B = X;
fB=(*func)(B);   dB=((*func)(B+h)-(*func)(B))/h;
a =(fB-fA+A*dA-B*dB)/(dA-dB); // moving fixed point
fa=(*func)(a); da=((*func)(a+h)-(*func)(a))/h;
if ((a>A) && (a<B))      // bracketing moving point
if ((fa*fA<0) || (da*dA<0))
B=a;
else
A=a;
}
else if ((fX*fB<0) || (dX*dB<0))
{
A = X;
fA=(*func)(A); dA=((*func)(A+h)-(*func)(A))/h;
b =(fA-fB+B*dB-A*dA)/(dB-dA); // moving fixed point
fb=(*func)(b); db=((*func)(b+h)-(*func)(b))/h;
if ((b>A) && (b<B))     // bracketing moving point
if ((fb*fB<0) || (db*dB<0))
A=b;
else
B=b;
}
}
}So, the C function that implements the moving generalized regula falsi (mGRF) method differs from GRF in that we have to include statements concerning the calculation of the moving fixed pointQ that results from intersecting tangents at A and B, as well as some statements to make sure that Q remains bracketed in the interval.


### 3.1. Convergence of mGRF Method

The convergence of the mGRF method is stated by the following theorem.Theorem 3.
Letf be a continuous real function on [A,B]⊂ℝ and f(A)·f(B)<0 or d(A)·d(B)<0. If X∈[A,B] is such that f(X)=0 or d(X)=0, then the mGRF method generates two sequences {Ai}i=1+∞ and {Bj}j=1∞ converging to X for two initial approximations A1=A and B1=B.Proof.
The mGRF method uses two preliminary estimatesA and B (i.e., the endpoints of the interval [A,B]) to generate two sequences of estimates, {Ai} and {Bi}, that supposedly march towards the solution X.
Without loss of generality, we can say that the GRF method generates the sequence{Ai}i=1∞ converging to X, as proved by Theorem 1.
It remains to prove that the sequence{Bj}j=1∞ generated by the computation of Q (cf. formula (15)) also converges to X. Without loss of generality, let us assume that d(Bj-2)>0 and d(Bj-1)<0 so that |d(Bj-2)|=d(Bj-2) and |d(Bj-1)|=-d(Bj-1). Now, formula (15) can be rewritten as follows:
(16)Bj=f(Bj-1)-f(Bj-2)+Bj-2·|d(Bj-2)|+Bj-1·|d(Bj-1)||d(Bj-2)|+|d(Bj-1)|
or, equivalently
(17)Bj=Bj-1+t·(Bj-2-Bj-1)
which is the vectorial equation of the line defined by the points Bj-1 and Bj-2, being
(18)t=f(Bj-1)-f(Bj-2)(|d(Bj-1)|+|d(Bj-2)|)·(Bj-2-Bj-1)+|d(Bj-2)||d(Bj-1)|+|d(Bj-2)|.
Letl(Ij) be the length of the interval Ij so that l(Ij)=|Bj-Bj-1|, l(Ij-1)=|Bj-1-Bj-2|. Now, from (17) we obtain
(19)l(Ij)l(Ij-1)=|Bn-Bj-1||Bj-1-Bj-2|=|Bj-1+t·(Bj-2-Bj-1)-Bj-1||Bj-1-Bj-2|=t.
But, as said before, the new estimateBi is only taken into account in the convergence process if it lies in the interval ]Bj-2,Bj-1[; otherwise, Bj equals to the estimate Aj∈]Bj-2,Bj-1[ determined by the GRF method; that is, Bj=Aj. From (17) and (19), this implies that 0<t<1 and l(Ij)<l(Ij-1) for all j. Thus, the sequence {l(Ij)}j=1+∞ is monotone decreasing. In addition, it is bounded because 0<l(Ij)≤|B-A|. So, by the Monotone Convergence Theorem we can conclude that {l(Ij)}j=1+∞ is convergent. Taking into account that X∈Ij for all j, we can also conclude that the mGRF method converges because the sequence {Bi}j=1∞ converges to X, being X a zero or an extremum of f.


## 3.1. Convergence of mGRF Method

The convergence of the mGRF method is stated by the following theorem.Theorem 3.
Letf be a continuous real function on [A,B]⊂ℝ and f(A)·f(B)<0 or d(A)·d(B)<0. If X∈[A,B] is such that f(X)=0 or d(X)=0, then the mGRF method generates two sequences {Ai}i=1+∞ and {Bj}j=1∞ converging to X for two initial approximations A1=A and B1=B.Proof.
The mGRF method uses two preliminary estimatesA and B (i.e., the endpoints of the interval [A,B]) to generate two sequences of estimates, {Ai} and {Bi}, that supposedly march towards the solution X.
Without loss of generality, we can say that the GRF method generates the sequence{Ai}i=1∞ converging to X, as proved by Theorem 1.
It remains to prove that the sequence{Bj}j=1∞ generated by the computation of Q (cf. formula (15)) also converges to X. Without loss of generality, let us assume that d(Bj-2)>0 and d(Bj-1)<0 so that |d(Bj-2)|=d(Bj-2) and |d(Bj-1)|=-d(Bj-1). Now, formula (15) can be rewritten as follows:
(16)Bj=f(Bj-1)-f(Bj-2)+Bj-2·|d(Bj-2)|+Bj-1·|d(Bj-1)||d(Bj-2)|+|d(Bj-1)|
or, equivalently
(17)Bj=Bj-1+t·(Bj-2-Bj-1)
which is the vectorial equation of the line defined by the points Bj-1 and Bj-2, being
(18)t=f(Bj-1)-f(Bj-2)(|d(Bj-1)|+|d(Bj-2)|)·(Bj-2-Bj-1)+|d(Bj-2)||d(Bj-1)|+|d(Bj-2)|.
Letl(Ij) be the length of the interval Ij so that l(Ij)=|Bj-Bj-1|, l(Ij-1)=|Bj-1-Bj-2|. Now, from (17) we obtain
(19)l(Ij)l(Ij-1)=|Bn-Bj-1||Bj-1-Bj-2|=|Bj-1+t·(Bj-2-Bj-1)-Bj-1||Bj-1-Bj-2|=t.
But, as said before, the new estimateBi is only taken into account in the convergence process if it lies in the interval ]Bj-2,Bj-1[; otherwise, Bj equals to the estimate Aj∈]Bj-2,Bj-1[ determined by the GRF method; that is, Bj=Aj. From (17) and (19), this implies that 0<t<1 and l(Ij)<l(Ij-1) for all j. Thus, the sequence {l(Ij)}j=1+∞ is monotone decreasing. In addition, it is bounded because 0<l(Ij)≤|B-A|. So, by the Monotone Convergence Theorem we can conclude that {l(Ij)}j=1+∞ is convergent. Taking into account that X∈Ij for all j, we can also conclude that the mGRF method converges because the sequence {Bi}j=1∞ converges to X, being X a zero or an extremum of f.


## 4. Experimental Results

We have carried out a number of the convergence tests on computer in order to assess the convergence of the superlinear version of generalized regula falsi (GRF) method. For that purpose, we have used a MacBook Pro laptop powered by a 2.33 GHz Intel Core 2 Duo processor, with 3 GB 667 MHz DDR2 SDRAM, running Mac OS X operating system (version 10.6.8).


### 4.1. Functions, Zeros, and Extrema

We have used a number of real analytic functions in testing of the method convergence, including algebraic (or polynomial) and transcendental functions, some of which are depicted in Figure3; for example, f1 and f3 are algebraic functions, but not f2 and f4 which are transcendental functions. These functions have been chosen because they cover most types of zeros and (local) extrema, namely, as shown in what follows.(i)
Crossing Zeros (cZ): a crossing zero is a point at which the function graph crosses the x-axis. We find 5 crossing zeros in Figure 3. More specifically, f1 has 2 crossing zeros in the interval [1.5,3.5], f3 has 1 crossing zero in the interval [-2.0,-1.0], f4 has 1 crossing zero in the interval [1.3,1.4], and f5 has 1 crossing zero in the interval [1.5,2.5].(ii)
Minima (m): we find 1 minimum in Figure 3; f1 has 1 local minimum in the interval [2.0,3.0].(iii)
Maxima (M): we have 4 maxima in Figure 3; f1 has 2 local maxima in the interval [-1.0,2.0], while f2 possesses 2 local maxima, the first in the interval [1.0,2.0] and the second in the interval [4.0,5.0].(iv)
Zeroed Minima (Zm): a local zeroed minimum is a point at which the function takes on the value 0 and has a local minimum; that is, the function graph touches but does not cross the x-axis. We have 5 zeroed minima in Figure 3. In particular, f1 has 2 local zeroed minima in the interval [-1.0,1.0], f2 also possesses 2 local zeroed minima, the first at x=0 and the second in the interval [3.0,4.0], whereas f6 has 1 local minimum at x=0 that is a cusp.(v)
Zeroed Maxima (ZM): a local zeroed maximum is a point at which the function takes on the value 0 and has a local maximum.For the purpose of testing, we carried out the convergence experiments for crossing zeros and extrema separately, as described below.


### 4.2. Convergence to Crossing Zeros

The experimental results shown in Table1 put in evidence how different GRF and mGRF methods are in terms of convergence to crossing zeros. According to Theorem 2, the GRF has linear convergence. But, following the results shown in Figure 4(top), mGRF seems to have superlinear convergence.Table 1
Experimental convergence results for zeros using GRF and mGRF methods.
Function
f
1
f
2
f
3
f
4
f
5
f
6
Estimate  type
cZ
—
cZ
cZ
cZ
—
Interval
[
3.0,3.3
]
—
[
-
3.0,2.0
]
[
1.3,1.4
]
[
-
10,10
]
—
GRF iterations
11
—
19
222
999
—
mGRF iterations
4
—
5
9
15
—Figure 4
Semilogarithmic graphs relative to convergence to zeros and extrema.As known, the GRF converges very slowly to a crossing zero when the slope of the function graph changes very fast near to such a zero, as it is the case of those shown in Figures3(d)-3(e). For example, in Figure 3(d), the crossing zero of f4 on the narrow interval ]1.3,1.4[ was found after 222 iterations, while that one of f5 in Figure 3(e) was found after 999 iterations, though in the bigger interval [-10,10] (cf. Table 1).As explained above, the mGRF is faster than GRF because both endpoints of the bracketing interval converge to the solution, while GRF keeps one of the endpoints fixed. The mGRF convergence rate seems to be at least quadratic because the estimates produced by (15) are usually closer to the solution than those produced by Newton’s method. This is confirmed by the error semilogarithmic graphs versus number of iterations shown in Figure 4(top). The convergence curve in black concerns the crossing zero of f1 in the interval [3.0,3.3], while the red, blue, and green curves represent the convergence to zero crossings of f3, f4, and f5 (cf. Table 1).


### 4.3. Convergence to Extrema

Unlike the numerical methods found in the literature, the GRF and mGRF methods are capable of computing both zeros and extrema of a real function through a single interpolation formula.However, as shown in Figure4(bottom), the convergence rate for extrema is lower than for crossing zeros and tends to be linear. This is explained by the fact that some estimates of the lateral sequence {Ai}i=1+∞ jump to the sequence {Bj}j=1∞, and vice versa.The data shown in Table2 concerns some extrema of f1, f2, and f6, whose convergence curves are plotted in Figure 4(bottom); the red curve concerns the minimum of f1 in the interval [2.0,3.0], the magenta curve has to do with the convergence to the maximum f2 in the interval [1,1.8], and the cyan curve refers to zeroed minimum (cusp) of f6 in the interval [-0.5,1.5]. This latter case shows that the method proposed in this paper is also capable of calculating a zero at which f is not differentiable. These semilogarithmic graphs suggest that mGRF has linear convergence for extrema. Nevertheless, the red convergence curve associated to the local maximum of f1 in the interval [-0.9,-0.4] may suggest that we can possibly obtain superlinear convergence for extrema too, but that would require redesigning the algorithm somehow.Table 2
Experimental convergence results for extrema using GRF and mGRF methods.
Function
f
1
f
2
f
3
f
4
f
5
f
6
Estimate  type
m
M
—
—
—
Zm
Interval
[
2.0,3.0
]
[
1,1.8
]
—
—
—
[
-
0.5,1.5
]
GRF iterations
23
19
—
—
—
18
mGRF iterations
10
10
—
—
—
10


## 4.1. Functions, Zeros, and Extrema

We have used a number of real analytic functions in testing of the method convergence, including algebraic (or polynomial) and transcendental functions, some of which are depicted in Figure3; for example, f1 and f3 are algebraic functions, but not f2 and f4 which are transcendental functions. These functions have been chosen because they cover most types of zeros and (local) extrema, namely, as shown in what follows.(i)
Crossing Zeros (cZ): a crossing zero is a point at which the function graph crosses the x-axis. We find 5 crossing zeros in Figure 3. More specifically, f1 has 2 crossing zeros in the interval [1.5,3.5], f3 has 1 crossing zero in the interval [-2.0,-1.0], f4 has 1 crossing zero in the interval [1.3,1.4], and f5 has 1 crossing zero in the interval [1.5,2.5].(ii)
Minima (m): we find 1 minimum in Figure 3; f1 has 1 local minimum in the interval [2.0,3.0].(iii)
Maxima (M): we have 4 maxima in Figure 3; f1 has 2 local maxima in the interval [-1.0,2.0], while f2 possesses 2 local maxima, the first in the interval [1.0,2.0] and the second in the interval [4.0,5.0].(iv)
Zeroed Minima (Zm): a local zeroed minimum is a point at which the function takes on the value 0 and has a local minimum; that is, the function graph touches but does not cross the x-axis. We have 5 zeroed minima in Figure 3. In particular, f1 has 2 local zeroed minima in the interval [-1.0,1.0], f2 also possesses 2 local zeroed minima, the first at x=0 and the second in the interval [3.0,4.0], whereas f6 has 1 local minimum at x=0 that is a cusp.(v)
Zeroed Maxima (ZM): a local zeroed maximum is a point at which the function takes on the value 0 and has a local maximum.For the purpose of testing, we carried out the convergence experiments for crossing zeros and extrema separately, as described below.


## 4.2. Convergence to Crossing Zeros

The experimental results shown in Table1 put in evidence how different GRF and mGRF methods are in terms of convergence to crossing zeros. According to Theorem 2, the GRF has linear convergence. But, following the results shown in Figure 4(top), mGRF seems to have superlinear convergence.Table 1
Experimental convergence results for zeros using GRF and mGRF methods.
Function
f
1
f
2
f
3
f
4
f
5
f
6
Estimate  type
cZ
—
cZ
cZ
cZ
—
Interval
[
3.0,3.3
]
—
[
-
3.0,2.0
]
[
1.3,1.4
]
[
-
10,10
]
—
GRF iterations
11
—
19
222
999
—
mGRF iterations
4
—
5
9
15
—Figure 4
Semilogarithmic graphs relative to convergence to zeros and extrema.As known, the GRF converges very slowly to a crossing zero when the slope of the function graph changes very fast near to such a zero, as it is the case of those shown in Figures3(d)-3(e). For example, in Figure 3(d), the crossing zero of f4 on the narrow interval ]1.3,1.4[ was found after 222 iterations, while that one of f5 in Figure 3(e) was found after 999 iterations, though in the bigger interval [-10,10] (cf. Table 1).As explained above, the mGRF is faster than GRF because both endpoints of the bracketing interval converge to the solution, while GRF keeps one of the endpoints fixed. The mGRF convergence rate seems to be at least quadratic because the estimates produced by (15) are usually closer to the solution than those produced by Newton’s method. This is confirmed by the error semilogarithmic graphs versus number of iterations shown in Figure 4(top). The convergence curve in black concerns the crossing zero of f1 in the interval [3.0,3.3], while the red, blue, and green curves represent the convergence to zero crossings of f3, f4, and f5 (cf. Table 1).


## 4.3. Convergence to Extrema

Unlike the numerical methods found in the literature, the GRF and mGRF methods are capable of computing both zeros and extrema of a real function through a single interpolation formula.However, as shown in Figure4(bottom), the convergence rate for extrema is lower than for crossing zeros and tends to be linear. This is explained by the fact that some estimates of the lateral sequence {Ai}i=1+∞ jump to the sequence {Bj}j=1∞, and vice versa.The data shown in Table2 concerns some extrema of f1, f2, and f6, whose convergence curves are plotted in Figure 4(bottom); the red curve concerns the minimum of f1 in the interval [2.0,3.0], the magenta curve has to do with the convergence to the maximum f2 in the interval [1,1.8], and the cyan curve refers to zeroed minimum (cusp) of f6 in the interval [-0.5,1.5]. This latter case shows that the method proposed in this paper is also capable of calculating a zero at which f is not differentiable. These semilogarithmic graphs suggest that mGRF has linear convergence for extrema. Nevertheless, the red convergence curve associated to the local maximum of f1 in the interval [-0.9,-0.4] may suggest that we can possibly obtain superlinear convergence for extrema too, but that would require redesigning the algorithm somehow.Table 2
Experimental convergence results for extrema using GRF and mGRF methods.
Function
f
1
f
2
f
3
f
4
f
5
f
6
Estimate  type
m
M
—
—
—
Zm
Interval
[
2.0,3.0
]
[
1,1.8
]
—
—
—
[
-
0.5,1.5
]
GRF iterations
23
19
—
—
—
18
mGRF iterations
10
10
—
—
—
10


## 5. Conclusions

The experimental results presented in the previous section show us the following.(i)
It is feasible to have a single numerical method to determine both zeros and extrema of a real function.(ii)
The algorithm (m)GRF works well even under conditions of lack of differentiability. So, singular zeros such as cusps and corners can be also computed.(iii)
It is also feasible to compute inflection points. For that, the algorithm must include the computation of the second finite differences.This algorithm has been designed and implemented to solve a difficult problem in computer graphics and geometric modeling, which has to do with rendering sign-invariant components of implicit curves. For example, the circle described by functionf(x,y)=(x2+y2-1)2=0 in ℝ2 cannot be sampled and, thus, rendered by algorithms that make usage of the Intermediate Value Theorem because the function is positive everywhere, with the exception of the curve points on which the function takes on the value 0; that is, all the circle points are extrema.



---

*Source: 394654-2013-07-30.xml*