The Regula Falsi Method
Regula Falsi method (or The Method of false position) is a technique to find the roots of algebraic and
transcendental equations of the form `f(x)=0` such as:
`xe^x - 1 = 0`.
Variations of this technique were found to be used by ancient Egyptians and Babylonians. In its modern form it closely resembles the
Bisection method. To find the root of an equation of the form `f(x)=0`, the function `f(x)` must be continuous.
Now we choose two points `x_L` and `x_H` such that `f(x_L)` and `f(x_H)` are of opposite signs. Hence a root must exist between `x_L` and `x_H`.
The equation of the chord joining the points `(x_L,f(x_L))` and `(x_H,f(x_H))` is given by:
`y-f(x_L)=(f(x_L)-f(x_H))/(x_H-x_L)(x-x_L)`.
The first approximation to the root is taken to be the point of intersection of the chord with the X-axis which is obtained by putting ` y=0 ` in
the above equation. Lets denote it by `x_"mid"`.
`x_"mid"=x_L - (f(x_L)(x_H-x_L))/(f(x_H)-f(x_L))`.
or, `x_"mid"=(x_L*f(x_H)-x_H*f(x_L))/(f(x_H)-f(x_L))`.
Now, if `f(x_"mid")` and `f(x_L)` are of opposite sign then the root must lie between the new approximation `x_"mid"` and `x_L`. Hence we replace
`x_H` with `x_"mid"` and obtain the next approximation in the same method we got the first approximation. Conversely, if `f(x_"mid")` and `f(x_L)`
are of same sign then the root must lie between the new approximation `x_"mid"` and `x_H`. Hence we replace
`x_L` with `x_"mid"` and obtain the next approximation. The process is repeated until the difference between two consecutive approximations become
very small.1444
Algorithm:
Step 1: Read `x_L, x_H and epsilon` such that `f(x_L)`is negative and `f(x_H)` is positive.
Step 2: Compute the new approximation: `x_"mid"=x_L - (f(x_L)(x_H-x_L))/(f(x_H)-f(x_L))`
Step 3: `previousX= x_"mid"`
Step 4: If `f(x_L)f(x_"mid")<0, x_H=x_"mid"`
Step 5: If `f(x_L)f(x_"mid")>0, x_L=x_"mid"`
Step 6: Compute new approximation: `x_"mid"=x_L - (f(x_L)(x_H-x_L))/(f(x_H)-f(x_L))`
Step 7: If ` |(previousX-x_"mid")/x_"mid"|>epsilon` go to Step:3
Step 8: OUTPUT :The root is approximately equal to `x_"mid"`
Step 9: Stop
Following are programs in different programming languages to find the root of the equation
`xe^x - 1 = 0`
The program in C was compiled using GNU GCC Compiler and the Fortran program was compiled
using GNU Fortran (gFortran) compiler.
Program in C
/*========================================================================!
!Program to find solutions to equations of the form f(x)=0 using !
!Regula Falsi method (Method of False Position) !
!LANGUAGE :: C (compiler: GNU GCC) !
!========================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double f(double y){
return y*exp(y)-1;
}
double newApprox(double yL,double yH){
return yL-f(yL)*(yH-yL)/(f(yH)-f(yL));
}
int main()
{
double xL,xH,diff,tolerance;
double xMid,prevXMid;
printf("Enter the two numbers xL and xH between which root is to be found\n");
scanf("%lf %lf",&xL,&xH);
printf("\nEnter the tolerance\n");
scanf("%lf",&tolerance);
if (f(xL)==0){
printf("\nThe root is : %lf",xL);
return 0;
}
else if (f(xH)==0){
printf("\nThe root is : %lf",xH);
return 0;
}
else if (f(xL)*f(xH)>0){
printf("\nf(xH) and f(xL) must be of opposite sign");
return 0;
}
xMid = newApprox(xL,xH);
printf("\nxL= %lf \t xH= %lf \t xMid= %lf \t f(xMid)= %lf",xL,xH,xMid,f(xMid));
do{
prevXMid = xMid;
if (f(xMid)*f(xH) < 0){
xL = xMid;
}
else if ( f(xMid)*f(xL) <0 ){
xH = xMid;
}
xMid = newApprox(xL,xH);
diff = fabs((xMid-prevXMid)/xMid);
printf("\nxL= %lf \t xH= %lf \t xMid= %lf \t f(xMid)= %lf",xL,xH,xMid,f(xMid));
}while(diff > tolerance);
printf("\n\nThe solution is %lf\n",xMid);
return 0;
}
/*--------------------- OUTPUT -------------------------------------------
Enter the two numbers xL and xH between which root is to be found
0.1
0.9
Enter the tolerance
0.0000001
xL= 0.100000 xH= 0.900000 xMid= 0.438347 f(xMid)= -0.320500
xL= 0.438347 xH= 0.900000 xMid= 0.534792 f(xMid)= -0.087062
xL= 0.534792 xH= 0.900000 xMid= 0.559236 f(xMid)= -0.021707
xL= 0.559236 xH= 0.900000 xMid= 0.565224 f(xMid)= -0.005294
xL= 0.565224 xH= 0.900000 xMid= 0.566678 f(xMid)= -0.001284
xL= 0.566678 xH= 0.900000 xMid= 0.567031 f(xMid)= -0.000311
xL= 0.567031 xH= 0.900000 xMid= 0.567116 f(xMid)= -0.000075
xL= 0.567116 xH= 0.900000 xMid= 0.567137 f(xMid)= -0.000018
xL= 0.567137 xH= 0.900000 xMid= 0.567142 f(xMid)= -0.000004
xL= 0.567142 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000001
xL= 0.567143 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000000
xL= 0.567143 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000000
xL= 0.567143 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000000
The solution is 0.567143
---------------------------------------------------------------------------*/
Program in Fortran 95
!==================================================================================!
!Program to find solutions to equations of the form f(x)=0 using !
!Regula Falsi method (Method of False Position) !
!LANGUAGE :: FORTRAN 95 (compiler: GNU Fortran Compiler) !
!==================================================================================!
PROGRAM regulaFalsi
IMPLICIT NONE
REAL :: xL,xH,diff,tolerance
REAL :: xMid,prevXMid
WRITE(*,*)'Enter the two numbers xL and xH between which root is to be found'
READ(*,*) xL,xH
WRITE(*,*)'Enter the tolerance'
READ(*,*)tolerance
IF (f(xL)==0) THEN
WRITE(*,* )xL,' is the root'
STOP
ELSEIF (f(xH)==0) THEN
WRITE(*,*)xH,' is the root'
STOP
ELSEIF (f(xL)*f(xH)>0) THEN
WRITE(*,*)'f(xH) and f(xL) must be of opposite sign'
STOP
END IF
xMid = newApprox(xL,xH)
DO
prevXMid = xMid;
IF(f(xMid)*f(xH)<0) THEN
xL = xMid
ELSEIF (f(xMid)*f(xL)<0) THEN
xH = xMid
END IF
xMid = newApprox(xL,xH)
diff=ABS((xMid-prevXMid)/xMid)
WRITE(*,*) 'xL =',xL,' ','xH =',xH,' ','xMId =',xMid
IF (diff < tolerance) EXIT
END DO
WRITE(*,*)'solution is',xMid
CONTAINS
REAL FUNCTION f(y)
REAL y
f = y*exp(y)-1
RETURN
END FUNCTION f
REAL FUNCTION newApprox(yL,yH)
REAL yL,yH
newApprox = yL-f(yL)*(yH-yL)/(f(yH)-f(yL))
RETURN
END FUNCTION newApprox
END PROGRAM
!------------------------ OUTPUT -------------------------------------
! Enter the two numbers xL and xH between which root is to be found
! 0.1
! 0.9
! Enter the tolerance
! 0.0000001
! xL = 0.438347012 xH = 0.899999976 xMId = 0.534791470
! xL = 0.534791470 xH = 0.899999976 xMId = 0.559236407
! xL = 0.559236407 xH = 0.899999976 xMId = 0.565224290
! xL = 0.565224290 xH = 0.899999976 xMId = 0.566678345
! xL = 0.566678345 xH = 0.899999976 xMId = 0.567030668
! xL = 0.567030668 xH = 0.899999976 xMId = 0.567116022
! xL = 0.567116022 xH = 0.899999976 xMId = 0.567136705
! xL = 0.567136705 xH = 0.899999976 xMId = 0.567141712
! xL = 0.567141712 xH = 0.899999976 xMId = 0.567142904
! xL = 0.567142904 xH = 0.899999976 xMId = 0.567143202
! xL = 0.567143202 xH = 0.899999976 xMId = 0.567143261
! xL = 0.567143261 xH = 0.899999976 xMId = 0.567143261
!
! solution is 0.567143261
!-----------------------------------------------------------------------
Program in Scilab
==================================================================================
Program to find solutions to equations of the form f(x)=0 using
Regula Falsi method (Method of False Position)
LANGUAGE :: SCILAB
!==================================================================================
xL = input("Enter number at which f(x) is negative: ")
xH = input("Enter number at which f(x) is positive: ")
tolerance = input("Enter the tolerance: ")
if (f(xL)==0) then
printf("The root is %f",xL )
return
elseif (f(xH)==0) then
printf("The root is %f",xH)
return
elseif (f(xL)*f(xH)>0) then
printf("Error!!f(xH) and f(xL) must be of opposite sign")
return
end
xMid = newApprox(xL,xH)
diffr = tolerance + 1
iteration = 1
while (diffr > tolerance)
prevXMid = xMid;
if(f(xMid)*f(xH)<0) then
xL = xMid
elseif (f(xMid)*f(xL)<0) then
xH = xMid
end
xMid = newApprox(xL,xH)
diffr=abs((xMid-prevXMid)/xMid)
printf("Iteration %d xL= %f xH= %f xMid = %f\n",iteration,xL,xH,xMid)
iteration = iteration+1
end
printf("\nThe root is %f",xMid)
function z = newApprox(yL,yH)
z = yL-f(yL)*(yH-yL)/(f(yH)-f(yL))
endfunction
function x = f(y)
x = y*exp(y)-1
endfunction
===================== OUTPUT ==========================
Enter number at which f(x) is negative: 0.1
Enter number at which f(x) is positive: 0.9
Enter the tolerance: 0.0000001
Iteration 1 xL= 0.438347 xH= 0.900000 xMid = 0.534792
Iteration 2 xL= 0.534792 xH= 0.900000 xMid = 0.559236
Iteration 3 xL= 0.559236 xH= 0.900000 xMid = 0.565224
Iteration 4 xL= 0.565224 xH= 0.900000 xMid = 0.566678
Iteration 5 xL= 0.566678 xH= 0.900000 xMid = 0.567031
Iteration 6 xL= 0.567031 xH= 0.900000 xMid = 0.567116
Iteration 7 xL= 0.567116 xH= 0.900000 xMid = 0.567137
Iteration 8 xL= 0.567137 xH= 0.900000 xMid = 0.567142
Iteration 9 xL= 0.567142 xH= 0.900000 xMid = 0.567143
Iteration 10 xL= 0.567143 xH= 0.900000 xMid = 0.567143
Iteration 11 xL= 0.567143 xH= 0.900000 xMid = 0.567143
Iteration 12 xL= 0.567143 xH= 0.900000 xMid = 0.567143
The root is 0.567143
========================================================
Regula Falsi method (or The Method of false position) is a technique to find the roots of algebraic and transcendental equations of the form `f(x)=0` such as:
`xe^x - 1 = 0`.
Variations of this technique were found to be used by ancient Egyptians and Babylonians. In its modern form it closely resembles the Bisection method. To find the root of an equation of the form `f(x)=0`, the function `f(x)` must be continuous. Now we choose two points `x_L` and `x_H` such that `f(x_L)` and `f(x_H)` are of opposite signs. Hence a root must exist between `x_L` and `x_H`. The equation of the chord joining the points `(x_L,f(x_L))` and `(x_H,f(x_H))` is given by:
`y-f(x_L)=(f(x_L)-f(x_H))/(x_H-x_L)(x-x_L)`.
The first approximation to the root is taken to be the point of intersection of the chord with the X-axis which is obtained by putting ` y=0 ` in the above equation. Lets denote it by `x_"mid"`.
`x_"mid"=x_L - (f(x_L)(x_H-x_L))/(f(x_H)-f(x_L))`.
or, `x_"mid"=(x_L*f(x_H)-x_H*f(x_L))/(f(x_H)-f(x_L))`.
Now, if `f(x_"mid")` and `f(x_L)` are of opposite sign then the root must lie between the new approximation `x_"mid"` and `x_L`. Hence we replace `x_H` with `x_"mid"` and obtain the next approximation in the same method we got the first approximation. Conversely, if `f(x_"mid")` and `f(x_L)` are of same sign then the root must lie between the new approximation `x_"mid"` and `x_H`. Hence we replace `x_L` with `x_"mid"` and obtain the next approximation. The process is repeated until the difference between two consecutive approximations become very small.1444
Algorithm:
Step 1: Read `x_L, x_H and epsilon` such that `f(x_L)`is negative and `f(x_H)` is positive.
Step 2: Compute the new approximation: `x_"mid"=x_L - (f(x_L)(x_H-x_L))/(f(x_H)-f(x_L))`
Step 3: `previousX= x_"mid"`
Step 4: If `f(x_L)f(x_"mid")<0, x_H=x_"mid"`
Step 5: If `f(x_L)f(x_"mid")>0, x_L=x_"mid"`
Step 6: Compute new approximation: `x_"mid"=x_L - (f(x_L)(x_H-x_L))/(f(x_H)-f(x_L))`
Step 7: If ` |(previousX-x_"mid")/x_"mid"|>epsilon` go to Step:3
Step 8: OUTPUT :The root is approximately equal to `x_"mid"`
Step 9: Stop
Following are programs in different programming languages to find the root of the equation
`xe^x - 1 = 0`
The program in C was compiled using GNU GCC Compiler and the Fortran program was compiled using GNU Fortran (gFortran) compiler.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double f(double y){
return y*exp(y)-1;
}
double newApprox(double yL,double yH){
return yL-f(yL)*(yH-yL)/(f(yH)-f(yL));
}
int main()
{
double xL,xH,diff,tolerance;
double xMid,prevXMid;
printf("Enter the two numbers xL and xH between which root is to be found\n");
scanf("%lf %lf",&xL,&xH);
printf("\nEnter the tolerance\n");
scanf("%lf",&tolerance);
if (f(xL)==0){
printf("\nThe root is : %lf",xL);
return 0;
}
else if (f(xH)==0){
printf("\nThe root is : %lf",xH);
return 0;
}
else if (f(xL)*f(xH)>0){
printf("\nf(xH) and f(xL) must be of opposite sign");
return 0;
}
xMid = newApprox(xL,xH);
printf("\nxL= %lf \t xH= %lf \t xMid= %lf \t f(xMid)= %lf",xL,xH,xMid,f(xMid));
do{
prevXMid = xMid;
if (f(xMid)*f(xH) < 0){
xL = xMid;
}
else if ( f(xMid)*f(xL) <0 ){
xH = xMid;
}
xMid = newApprox(xL,xH);
diff = fabs((xMid-prevXMid)/xMid);
printf("\nxL= %lf \t xH= %lf \t xMid= %lf \t f(xMid)= %lf",xL,xH,xMid,f(xMid));
}while(diff > tolerance);
printf("\n\nThe solution is %lf\n",xMid);
return 0;
}
/*--------------------- OUTPUT -------------------------------------------
Enter the two numbers xL and xH between which root is to be found
0.1
0.9
Enter the tolerance
0.0000001
xL= 0.100000 xH= 0.900000 xMid= 0.438347 f(xMid)= -0.320500
xL= 0.438347 xH= 0.900000 xMid= 0.534792 f(xMid)= -0.087062
xL= 0.534792 xH= 0.900000 xMid= 0.559236 f(xMid)= -0.021707
xL= 0.559236 xH= 0.900000 xMid= 0.565224 f(xMid)= -0.005294
xL= 0.565224 xH= 0.900000 xMid= 0.566678 f(xMid)= -0.001284
xL= 0.566678 xH= 0.900000 xMid= 0.567031 f(xMid)= -0.000311
xL= 0.567031 xH= 0.900000 xMid= 0.567116 f(xMid)= -0.000075
xL= 0.567116 xH= 0.900000 xMid= 0.567137 f(xMid)= -0.000018
xL= 0.567137 xH= 0.900000 xMid= 0.567142 f(xMid)= -0.000004
xL= 0.567142 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000001
xL= 0.567143 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000000
xL= 0.567143 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000000
xL= 0.567143 xH= 0.900000 xMid= 0.567143 f(xMid)= -0.000000
The solution is 0.567143
---------------------------------------------------------------------------*/
PROGRAM regulaFalsi
IMPLICIT NONE
REAL :: xL,xH,diff,tolerance
REAL :: xMid,prevXMid
WRITE(*,*)'Enter the two numbers xL and xH between which root is to be found'
READ(*,*) xL,xH
WRITE(*,*)'Enter the tolerance'
READ(*,*)tolerance
IF (f(xL)==0) THEN
WRITE(*,* )xL,' is the root'
STOP
ELSEIF (f(xH)==0) THEN
WRITE(*,*)xH,' is the root'
STOP
ELSEIF (f(xL)*f(xH)>0) THEN
WRITE(*,*)'f(xH) and f(xL) must be of opposite sign'
STOP
END IF
xMid = newApprox(xL,xH)
DO
prevXMid = xMid;
IF(f(xMid)*f(xH)<0) THEN
xL = xMid
ELSEIF (f(xMid)*f(xL)<0) THEN
xH = xMid
END IF
xMid = newApprox(xL,xH)
diff=ABS((xMid-prevXMid)/xMid)
WRITE(*,*) 'xL =',xL,' ','xH =',xH,' ','xMId =',xMid
IF (diff < tolerance) EXIT
END DO
WRITE(*,*)'solution is',xMid
CONTAINS
REAL FUNCTION f(y)
REAL y
f = y*exp(y)-1
RETURN
END FUNCTION f
REAL FUNCTION newApprox(yL,yH)
REAL yL,yH
newApprox = yL-f(yL)*(yH-yL)/(f(yH)-f(yL))
RETURN
END FUNCTION newApprox
END PROGRAM
!------------------------ OUTPUT -------------------------------------
! Enter the two numbers xL and xH between which root is to be found
! 0.1
! 0.9
! Enter the tolerance
! 0.0000001
! xL = 0.438347012 xH = 0.899999976 xMId = 0.534791470
! xL = 0.534791470 xH = 0.899999976 xMId = 0.559236407
! xL = 0.559236407 xH = 0.899999976 xMId = 0.565224290
! xL = 0.565224290 xH = 0.899999976 xMId = 0.566678345
! xL = 0.566678345 xH = 0.899999976 xMId = 0.567030668
! xL = 0.567030668 xH = 0.899999976 xMId = 0.567116022
! xL = 0.567116022 xH = 0.899999976 xMId = 0.567136705
! xL = 0.567136705 xH = 0.899999976 xMId = 0.567141712
! xL = 0.567141712 xH = 0.899999976 xMId = 0.567142904
! xL = 0.567142904 xH = 0.899999976 xMId = 0.567143202
! xL = 0.567143202 xH = 0.899999976 xMId = 0.567143261
! xL = 0.567143261 xH = 0.899999976 xMId = 0.567143261
!
! solution is 0.567143261
!-----------------------------------------------------------------------
xL = input("Enter number at which f(x) is negative: ")
xH = input("Enter number at which f(x) is positive: ")
tolerance = input("Enter the tolerance: ")
if (f(xL)==0) then
printf("The root is %f",xL )
return
elseif (f(xH)==0) then
printf("The root is %f",xH)
return
elseif (f(xL)*f(xH)>0) then
printf("Error!!f(xH) and f(xL) must be of opposite sign")
return
end
xMid = newApprox(xL,xH)
diffr = tolerance + 1
iteration = 1
while (diffr > tolerance)
prevXMid = xMid;
if(f(xMid)*f(xH)<0) then
xL = xMid
elseif (f(xMid)*f(xL)<0) then
xH = xMid
end
xMid = newApprox(xL,xH)
diffr=abs((xMid-prevXMid)/xMid)
printf("Iteration %d xL= %f xH= %f xMid = %f\n",iteration,xL,xH,xMid)
iteration = iteration+1
end
printf("\nThe root is %f",xMid)
function z = newApprox(yL,yH)
z = yL-f(yL)*(yH-yL)/(f(yH)-f(yL))
endfunction
function x = f(y)
x = y*exp(y)-1
endfunction
===================== OUTPUT ==========================
Enter number at which f(x) is negative: 0.1
Enter number at which f(x) is positive: 0.9
Enter the tolerance: 0.0000001
Iteration 1 xL= 0.438347 xH= 0.900000 xMid = 0.534792
Iteration 2 xL= 0.534792 xH= 0.900000 xMid = 0.559236
Iteration 3 xL= 0.559236 xH= 0.900000 xMid = 0.565224
Iteration 4 xL= 0.565224 xH= 0.900000 xMid = 0.566678
Iteration 5 xL= 0.566678 xH= 0.900000 xMid = 0.567031
Iteration 6 xL= 0.567031 xH= 0.900000 xMid = 0.567116
Iteration 7 xL= 0.567116 xH= 0.900000 xMid = 0.567137
Iteration 8 xL= 0.567137 xH= 0.900000 xMid = 0.567142
Iteration 9 xL= 0.567142 xH= 0.900000 xMid = 0.567143
Iteration 10 xL= 0.567143 xH= 0.900000 xMid = 0.567143
Iteration 11 xL= 0.567143 xH= 0.900000 xMid = 0.567143
Iteration 12 xL= 0.567143 xH= 0.900000 xMid = 0.567143
The root is 0.567143
========================================================