C++ Programming – Program for Method Of False Position

Given a function f(x) on floating number x and two numbers ‘a’ and ‘b’ such that f(a)*f(b) < 0 and f(x) is continuous in [a, b]. Here f(x) represents algebraic or transcendental equation. Find root of function in interval [a, b] (Or find a value of x such that f(x) is 0).

Input: A function of x, for example x3 – x2 + 2.     
       And two values: a = -200 and b = 300 such that
       f(a)*f(b) < 0, i.e., f(a) and f(b) have
       opposite signs.
Output: The value of root is : -1.00
        OR any other value close to root.

We strongly recommend to refer below post as a prerequisite of this post.

In this post The Method Of False Position is discussed. This method is also known as Regula Falsi or The Method of Chords.

[ad type=”banner”]

Similarities with Bisection Method:

1. Same Assumptions: This method also assumes that function is continuous in [a, b] and given two numbers ‘a’ and ‘b’ are such that f(a) * f(b) < 0.
2. Always Converges: like Bisection, it always converges, usually considerably faster than Bisection–but sometimes very much more slowly than Bisection.

Differences with Bisection Method:
It differs in the fact that we make a chord joining the two points [a, f(a)] and [b, f(b)]. We consider the point at which the chord touches the x axis and named it as c.

Steps:

1. Write equation of the line connecting the two points.

   y – f(a) =  ( (f(b)-f(a))/(b-a) )*(x-a)
   
   Now we have to find the point which touches x axis. 
   For that we put y = 0.
   
   so x = a - (f(a)/(f(b)-f(a))) * (b-a)
      x = (a*f(b) - b*f(a)) / (f(b)-f(a)) 
   
   This will be our c that is c = x.

2. If f(c) == 0, then c is the root of the solution.
3. Else f(c) != 0
   1. If value f(a)*f(c) < 0 then root lies between a and c. So we recur for a and c
   2. Else If f(b)*f(c) < 0 then root lies between b and c. So we recur b and c.
   3. Else given function doesn’t follow one of assumptions.

Since root may be a floating point number and may converge very slow in worst case, we iterate for a very large number of times such that the answer becomes closer to the root.

Following is C++ implementation.

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20for%20implementation%20of%20Bisection%20Method%20for%0A%2F%2F%20solving%20equations%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%23define%20MAX_ITER%201000000%0A%20%0A%2F%2F%20An%20example%20function%20whose%20solution%20is%20determined%20using%0A%2F%2F%20Bisection%20Method.%20The%20function%20is%20x%5E3%20-%20x%5E2%20%20%2B%202%0Adouble%20func(double%20x)%0A%7B%0A%20%20%20%20return%20x*x*x%20-%20x*x%20%2B%202%3B%0A%7D%0A%20%0A%2F%2F%20Prints%20root%20of%20func(x)%20in%20interval%20%5Ba%2C%20b%5D%0Avoid%20regulaFalsi(double%20a%2C%20double%20b)%0A%7B%0A%20%20%20%20if%20(func(a)%20*%20func(b)%20%3E%3D%200)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22You%20have%20not%20assumed%20right%20a%20and%20b%5Cn%22%3B%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20double%20c%20%3D%20a%3B%20%20%2F%2F%20Initialize%20result%0A%20%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%20%3C%20MAX_ITER%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20the%20point%20that%20touches%20x%20axis%0A%20%20%20%20%20%20%20%20c%20%3D%20(a*func(b)%20-%20b*func(a))%2F%20(func(b)%20-%20func(a))%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20the%20above%20found%20point%20is%20root%0A%20%20%20%20%20%20%20%20if%20(func(c)%3D%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Decide%20the%20side%20to%20repeat%20the%20steps%0A%20%20%20%20%20%20%20%20else%20if%20(func(c)*func(a)%20%3C%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20b%20%3D%20c%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20a%20%3D%20c%3B%0A%20%20%20%20%7D%0A%20%20%20%20cout%20%3C%3C%20%22The%20value%20of%20root%20is%20%3A%20%22%20%3C%3C%20c%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Initial%20values%20assumed%0A%20%20%20%20double%20a%20%3D-200%2C%20b%20%3D%20300%3B%0A%20%20%20%20regulaFalsi(a%2C%20b)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]

Output:

The value of root is : -1

This method always converges, usually considerably faster than Bisection. But worst case can be very slow.

[ad type=”banner”]