{"id":26312,"date":"2017-10-26T20:59:20","date_gmt":"2017-10-26T15:29:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26312"},"modified":"2017-10-26T20:59:20","modified_gmt":"2017-10-26T15:29:20","slug":"c-programming-program-bisection-method","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-program-bisection-method\/","title":{"rendered":"C++ Programming – Program for Bisection Method"},"content":{"rendered":"

Given a function f(x) on floating number x and two numbers \u2018a\u2019 and \u2018b\u2019 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).<\/p>\n

Input: A function of x<\/strong>, for example x3<\/sup> - x2<\/sup> + 2.     \r\n       And two values: a<\/strong> = -200 and b<\/strong> = 300 such that\r\n       f(a)*f(b) < 0, i.e., f(a) and f(b) have\r\n       opposite signs.\r\nOutput: The value of root is : -1.0025\r\n        OR any other value with allowed\r\n        deviation from root.\r\n<\/pre>\n
What are Algebraic and Transcendental functions?<\/strong>
\nAlgebraic function are the one which can be represented in the form of polynomials like f(x) = a1<\/sub>x3<\/sup> + a2<\/sub>x2<\/sup> + \u2026.. + e where aa1<\/sub>, a2<\/sub>, \u2026 are constants and x is a variable.
\nTranscendental function are non algebraic functions, for example f(x) = sin(x)*x \u2013 3 or f(x) = ex<\/sup> + x2<\/sup> or f(x) = ln(x) + x \u2026.<\/p>\n[ad type=\u201dbanner\u201d]\n
What is Bisection Method?<\/strong>
\nThe method is also called the interval halving method, the binary search method or the dichotomy method. This method is used to find root of an equation in a given interval that is value of \u2018x\u2019 for which f(x) = 0 .<\/p>\n
The method is based on The Intermediate Value Theorem<\/strong> which states that if f(x) is a continuous function and there are two real numbers a and b such that f(a)*f(b) < 0. Then f(x) has at least one zero between a and b. If for a function (f(a) < 0 and f(b) > 0) or (f(a) > 0 and f(b) < 0), then it is guaranteed that it has at least one root between them.<\/p>\n
Assumptions:<\/strong><\/p>\n
    \n
  1. f(x) is a continuous function in interval [a, b]<\/li>\n
  2. f(a) * f(b) < 0<\/li>\n<\/ol>\n
    Steps:<\/strong><\/p>\n
      \n
    1. Find middle point c<\/strong>= (a + b)\/2 .<\/li>\n
    2. If<\/strong> f(c) == 0, then c is the root of the solution.<\/li>\n
    3. Else<\/strong> f(c) != 0\n
        \n
      1. If<\/strong> value f(a)*f(c) < 0 then root lies between a and c. So we recur for a and c<\/li>\n
      2. Else If<\/strong> f(b)*f(c) < 0 then root lies between b and c. So we recur b and c.<\/li>\n
      3. Else<\/strong> given function doesn\u2019t follow one of assumptions.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
        Since root may be a floating point number, we repeat above steps while difference between a and b is less than a value \u03b5 (A very small value).\"Bisection\"<\/p>\n
        \u00a0<\/p>\n
        Below is C++ implementation of above steps.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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%20EPSILON%200.01%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)%20with%20error%20of%20EPSILON%0Avoid%20bisection(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%0A%20%20%20%20while%20((b-a)%20%3E%3D%20EPSILON)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20middle%20point%0A%20%20%20%20%20%20%20%20c%20%3D%20(a%2Bb)%2F2%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Check%20if%20middle%20point%20is%20root%0A%20%20%20%20%20%20%20%20if%20(func(c)%20%3D%3D%200.0)%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%20bisection(a%2C%20b)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
        Output:<\/p>\n
        The value of root is : -1.0025\r\n<\/pre>\n
        Time complexity :-<\/strong> Time complexity of this method depends on the assumed values and the function.<\/p>\n
        What are pros and cons?<\/strong>
        \nAdvantage of the bisection method is that it is guaranteed to be converged. Disadvantage of bisection method is that it cannot detect multiple roots.<\/p>\n
        In general, Bisection method is used to get an initial rough approximation of solution. Then faster converging methods are used to find the solution.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
        C++ Programming – Program for Bisection Method – Mathematical Algorithms – The method is also called the interval halving method, the binary search method<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1,74058],"tags":[78271,78273,78304,77752,78298,77009,78270,78293,78286,77015,78300,78297,78268,78281,78291,78278,78294,78290,77000,77001,78267,78305,78282,78269,78280,78279,78306,78285,78296,78274,78301,77005,78303,78289,78277,78283,78266,78276,78288,78284,76990,78295,78292,78302,78275,78299,76998,77011,78272,78287],"class_list":["post-26312","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-mathematical-algorithms","tag-algorithm-of-bisection-method","tag-bisection-method","tag-bisection-method-algorithm-pdf","tag-bisection-method-c-program","tag-bisection-method-code-in-c","tag-bisection-method-example","tag-bisection-method-example-ppt","tag-bisection-method-fortran-90-code","tag-bisection-method-fortran-code","tag-bisection-method-in-c","tag-bisection-method-in-c-code","tag-bisection-method-in-c-using-for-loop","tag-bisection-method-in-fortran","tag-bisection-method-in-java","tag-bisection-method-java","tag-bisection-method-ppt","tag-bisection-method-program-in-matlab","tag-bisection-method-python-code","tag-bisection-method-solved-examples","tag-bisection-method-solved-examples-pdf","tag-bisection-program-in-c","tag-c-code-for-bisection-method","tag-c-program-for-bisection-method","tag-c-program-of-bisection-method","tag-convergence-of-bisection-method","tag-flowchart-for-bisection-method","tag-flowchart-of-bisection-method","tag-fortran-program-for-bisection-method","tag-matlab-program-for-bisection-method","tag-newton-raphson-method-formula","tag-numerical-bisection-method","tag-numerical-methods-bisection-method","tag-numerical-methods-bisection-method-pdf","tag-numerical-methods-c-programs","tag-numerical-methods-in-c","tag-numerical-methods-in-c-programming","tag-numerical-methods-programs-in-c","tag-numerical-methods-using-c-programming","tag-numerical-methods-with-programs-in-c","tag-numerical-programming-in-c","tag-program-of-bisection-method-in-c-language","tag-program-of-newton-raphson-method-in-c","tag-programs-in-c-language-solved","tag-python-bisection-method","tag-regula-falsi-method","tag-regula-falsi-method-program-in-c","tag-secant-method-example-solved","tag-secant-method-formula","tag-simple-c-program-for-bisection-method","tag-write-an-algorithm-for-the-bisection-method"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26312","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26312"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26312\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26312"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26312"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26312"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}