Rate of convergence estimate of the speed with which a given sequence or iteration approaches its limit, often measured by the number of terms or evaluations involved in obtaining a given accuracy. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of successive approximations for an iterative method, as then typically fewer iterations are needed to yield a useful approximation if the rate of convergence is higher. This may even make the difference between needing ten or a million iterations.
Rate of convergence is measured in terms of rate at which the relative error decreases between successive approximations. There are mainly two type of convergence: linear and quadratic.
Convergence of a sequence subject to the condition, for p > 1, that
as n increases is called pth-order convergence; for example, quadratic convergence when p = 2. One similarly speaks of logarithmic convergence or exponential convergence.
In mathematics, the bisection method is a root-finding algorithm which repeatedly bisects an interval then selects a subinterval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow. The bisection method is simple, robust, and straight-forward: take an interval [a, b] such that f(a) and f(b) have opposite signs, find the midpoint of [a, b], and then decide whether the root lies on [a, (a + b)/2] or [(a + b)/2, b]. Repeat until the interval is sufficiently small.
The bisection method, suitable for implementation on a computer allows to find the roots of the equation f (x) = 0, based on the following theorem:
Theorem: If f is continuous for x between a and b and if f (a) and f(b) have opposite signs, then there exists at least one real root of f (x) = 0 between a and b.
Procedure: Suppose that a continuous function f is negative at x = a and positive at x = b, so that there is at least one real root between a and b. (As a rule, a and b may be found from a graph of f.) If we calculate f ((a +b)/2), which is the function value at the point of bisection of the interval a< x < b, there are three possibilities:
f ((a + b)/2) = 0, in which case (a + b)/2 is the root;
f ((a + b)/2) <0, in which case the root lies between (a + b)/2 and b;
f ((a + b)/2) > 0, in which case the root lies between a and (a + b)/2.
The bisection method is always convergent. Since the method brackets the root, the method is guaranteed to converge.
As iterations are conducted, the interval gets halved. So one can guarantee the decrease in the error in the solution of the equation.
The convergence of bisection method is slow as it is simply based on halving the interval.
If one of the initial guesses is closer to the root, it will take larger number of iterations to reach the root.
If a function is such that it just touches the x-axis (Figure 3.8) such as
it will be unable to find the lower guess, , and upper guess, , such that
For functions where there is a singularity and it reverses sign at the singularity, bisection method may converge on the singularity (Figure 3.9).
An example include
and, are valid initial guesses which satisfy
However, the function is not continuous and the theorem that a root exists is also not applicable.
Figure.3.8. Function has a single root at that cannot be bracketed.
Figure.3.9. Function has no root but changes sign.
The false-position method is a modification on the bisection method. The false position method or regula falsi method is a root-finding algorithm that combines features from the bisection method and the secant method. If it is known that the root lies on [a, b], then it is reasonable that we can approximate the function on the interval by interpolating the points (a, f(a)) and (b, f(b)). The method of false position dates back to the ancient Egyptians. It remains an effective alternative to the bisection method for solving the equation f(x) = 0 for a real root between a and b, given that f (x) is continuous and f (a) and f(b) have opposite signs. The algorithm is suitable for automatic computation
The curve y = f(x) is not generally a straight line. However, one may join the points (a,f(a)) and (b,f(b)) by the straight line
Thus straight line cuts the x-axis at (X, 0) where
so that
Suppose that f(a) is negative and f(b) is positive. As in the bisection method, there are the three possibilities :
f(X) = 0, when case X is the root ;
f(X) < 0, when the root lies between X and b ;
f(X)>0, when the root lies between X and a.
Again, in Case 1, the process is terminated, in either Case 2 or Case 3, the process can be repeated until the root is obtained to the desired accuracy.
Source code for False Position Method:
C code was written for clarity instead of efficiency. It was designed to solve the same problem as solved by the Newton’s method and secant method code: to find the positive number x where cos(x) = x3. This problem is transformed into a root-finding problem of the form
f(x) = cos(x) – x3 = 0.
#include
#include
double f(double x)
return cos(x) – x*x*x;
double FalsiMethod(double s, double t, double e, int m)
int n,side=0;
double r,fr,fs = f(s),ft = f(t);
for (n = 1; n <= m; n++)
r = (fs*t – ft*s) / (fs – ft);
if (fabs(t-s) < e*fabs(t+s)) break;
fr = f(r);
if (fr * ft > 0)
t = r; ft = fr;
if (side==-1) fs /= 2;
side = -1;
else if (fs * fr > 0)
s = r; fs = fr;
if (side==+1) ft /= 2;
side = +1;
return r;
int main(void)
printf(“%0.15fn”, FalsiMethod(0, 1, 5E-15, 100));
return 0;
After running this code, the final answer is approximately 0.865474033101614
Consider finding the root of f(x) = x2 – 3. Let εstep = 0.01, εabs = 0.01 and start with the interval [1, 2].
Table 1. False-position method applied to f(x) = x2 – 3.
1.0
2.0
-2.00
1.00
1.6667
-0.2221
a = c
0.6667
1.6667
2.0
-0.2221
1.0
1.7273
-0.0164
a = c
0.0606
1.7273
2.0
-0.0164
1.0
1.7317
0.0012
a = c
0.0044
Thus, with the third iteration, we note that the last step 1.7273 → 1.7317 is less than 0.01 and |f(1.7317)| < 0.01, and therefore we chose b = 1.7317 to be our approximation of the root.
Note that after three iterations of the false-position method, we have an acceptable answer (1.7317 where f(1.7317) = -0.0044) whereas with the bisection method, it took seven iterations to find a (notable less accurate) acceptable answer (1.71344 where f(1.73144) = 0.0082)
Consider finding the root of f(x) = e-x(3.2 sin(x) – 0.5 cos(x)) on the interval [3, 4], this time with εstep = 0.001, εabs = 0.001.
Table 2. False-position method applied to f(x) = e-x(3.2 sin(x) – 0.5 cos(x)).
3.0
4.0
0.047127
-0.038372
3.5513
-0.023411
b = c
0.4487
3.0
3.5513
0.047127
-0.023411
3.3683
-0.0079940
b = c
0.1830
3.0
3.3683
0.047127
-0.0079940
3.3149
-0.0021548
b = c
0.0534
3.0
3.3149
0.047127
-0.0021548
3.3010
-0.00052616
b = c
0.0139
3.0
3.3010
0.047127
-0.00052616
3.2978
-0.00014453
b = c
0.0032
3.0
3.2978
0.047127
-0.00014453
3.2969
-0.000036998
b = c
0.0009
Thus, after the sixth iteration, we note that the final step, 3.2978 → 3.2969 has a size less than 0.001 and |f(3.2969)| < 0.001 and therefore we chose b = 3.2969 to be our approximation of the root.
In this case, the solution we found was not as good as the solution we found using the bisection method (f(3.2963) = 0.000034799) however, we only used six instead of eleven iterations.
Source code for Bisection method
#include
#include
#define epsilon 1e-6
main()
double g1,g2,g,v,v1,v2,dx;
int found,converged,i;
found=0;
printf(” enter the first guessn”);
scanf(“%lf”,&g1);
v1=g1*g1*g1-15;
printf(“value 1 is %lfn”,v1);
while (found==0)
printf(“enter the second guessn”);
scanf(“%lf”,&g2);
v2=g2*g2*g2-15;
printf(” value 2 is %lfn”,v2);
if (v1*v2>0)
{found=0;}
else
found=1;
printf(“right guessn”);
i=1;
while (converged==0)
printf(“n iteration=%dn”,i);
g=(g1+g2)/2;
printf(“new guess is %lfn”,g);
v=g*g*g-15;
printf(“new value is%lfn”,v);
if (v*v1>0)
g1=g;
printf(“the next guess is %lfn”,g);
dx=(g1-g2)/g1;
else
g2=g;
printf(“the next guess is %lfn”,g);
dx=(g1-g2)/g1;
if (fabs(dx)’less than’ epsilon
{converged=1;}
i=i+1;
printf(“nth calculated value is %lfn”,v);
Consider finding the root of f(x) = x2 – 3. Let εstep = 0.01, εabs = 0.01 and start with the interval [1, 2].
Table 1. Bisection method applied to f(x) = x2 – 3.
1.0
2.0
-2.0
1.0
1.5
-0.75
a = c
0.5
1.5
2.0
-0.75
1.0
1.75
0.062
b = c
0.25
1.5
1.75
-0.75
0.0625
1.625
-0.359
a = c
0.125
1.625
1.75
-0.3594
0.0625
1.6875
-0.1523
a = c
0.0625
1.6875
1.75
-0.1523
0.0625
1.7188
-0.0457
a = c
0.0313
1.7188
1.75
-0.0457
0.0625
1.7344
0.0081
b = c
0.0156
1.71988
1.7344
-0.0457
0.0081
1.7266
-0.0189
a = c
0.0078
Thus, with the seventh iteration, we note that the final interval, [1.7266, 1.7344], has a width less than 0.01 and |f(1.7344)| < 0.01, and therefore we chose b = 1.7344 to be our approximation of the root.
Consider finding the root of f(x) = e-x(3.2 sin(x) – 0.5 cos(x)) on the interval [3, 4], this time with εstep = 0.001, εabs = 0.001.
Table 1. Bisection method applied to f(x) = e-x(3.2 sin(x) – 0.5 cos(x)).
3.0
4.0
0.047127
-0.038372
3.5
-0.019757
b = c
0.5
3.0
3.5
0.047127
-0.019757
3.25
0.0058479
a = c
0.25
3.25
3.5
0.0058479
-0.019757
3.375
-0.0086808
b = c
0.125
3.25
3.375
0.0058479
-0.0086808
3.3125
-0.0018773
b = c
0.0625
3.25
3.3125
0.0058479
-0.0018773
3.2812
0.0018739
a = c
0.0313
3.2812
3.3125
0.0018739
-0.0018773
3.2968
-0.000024791
b = c
0.0156
3.2812
3.2968
0.0018739
-0.000024791
3.289
0.00091736
a = c
0.0078
3.289
3.2968
0.00091736
-0.000024791
3.2929
0.00044352
a = c
0.0039
3.2929
3.2968
0.00044352
-0.000024791
3.2948
0.00021466
a = c
0.002
3.2948
3.2968
0.00021466
-0.000024791
3.2958
0.000094077
a = c
0.001
3.2958
3.2968
0.000094077
-0.000024791
3.2963
0.000034799
a = c
0.0005
Thus, after the 11th iteration, we note that the final interval, [3.2958, 3.2968] has a width less than 0.001 and |f(3.2968)| < 0.001 and therefore we chose b = 3.2968 to be our approximation of the root.
Like the bisection method, the method of false position has almost assured convergence, and it may converge to a root faster. Finally, note that bisection is rather slow; after n iterations the interval containing the root is of length (b – a)/2n. However, provided values of f can be generated readily, as when a computer is used, the rather large number of iterations which can be involved in the application of bisection is of relatively little consequence.
The false position method would be better i.e. converges to the root more rapidly as it takes into account the relative magnitudes of f(b) and f(a) unlike bisection which just uses the midpoint of a and b, where [a,b] is the interval over which the root occurs. Following is the example of the convergence rate of bisection method and false position method for the similar equation which shows that rate of convergence of false position method is faster than that of the bisection method.
Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.
You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.
Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.
Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.
Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.
Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.
Read more