Bisection method-numerical analysis

  • Context: MHB 
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Analysis
Click For Summary

Discussion Overview

The discussion revolves around the Bisection method in numerical analysis, specifically focusing on the termination criteria of the method, which include the conditions \left |x_{k}-x_{k-1} \right | < ε and \left | f(x_{k})\right | < ε. Participants seek clarification on these criteria, their implications, and related coding practices.

Discussion Character

  • Exploratory
  • Technical explanation
  • Homework-related

Main Points Raised

  • Some participants question why the conditions \left |x_{k}-x_{k-1} \right | < ε and \left | f(x_{k})\right | < ε are used as termination criteria in the Bisection method.
  • Others explain that the first condition ensures the approximation is close to the real root, while the second condition verifies that the function value at the approximation is close to zero.
  • A participant seeks clarification on whether x_{k-1} is considered the real root, to which others clarify that the real root lies between x_{k-1} and x_{k}.
  • There is a discussion about the interpretation of the variables a and b in the context of the algorithm, with some participants confirming their roles as x_{k} and x_{k-1} respectively.
  • One participant inquires about alternative expressions for the condition |x_{k}-x_{k-1}|<ε, leading to a discussion on the equivalence of different formulations.
  • Another participant raises a question about the output of the algorithm, specifically whether to print the last approximation when certain conditions are met.
  • There are mentions of different implementations of the Bisection method, including variations in termination criteria based on the average of the interval endpoints.
  • Some participants express uncertainty about which x_{k} to use for evaluating the function f(x_{k}) in the termination criteria.

Areas of Agreement / Disagreement

Participants generally express uncertainty regarding the interpretation of the termination criteria and the roles of the variables involved. Multiple competing views exist about the best practices for implementing the Bisection method and the conditions under which to print results.

Contextual Notes

There are unresolved questions about the equivalence of different formulations of the termination criteria and the implications of using various approximations in the algorithm.

Who May Find This Useful

This discussion may be useful for students and practitioners of numerical analysis, particularly those interested in the Bisection method and its implementation in programming contexts.

  • #31
Could you explain it further to me?
Because I found this:
When the interval is [a_{k-1},b_{k-1}]

x_{k-1}=\frac{a_{k-1}+b_{k-1}}{2}

when the interval is [a_{k},b_{k}]

x_{k}=\frac{a_{k-1}+\frac{a_{k-1}+b_{k-1}}{2}}{2}=\frac{3a_{k-1}+b_{k-1}}{4}

So,|x_{k}-x_{k-1}|=|\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})|=|\frac{a_{k-1}-b_{k-1}}{4}|

But |a_{k}-b_{k}|=|\frac{a_{k-1}-b_{k-1}}{2}|

so they are not equal..what have I done wrong?
 
Physics news on Phys.org
  • #32
evinda said:
Could you explain it further to me?
Because I found this:
When the interval is [a_{k-1},b_{k-1}]

x_{k-1}=\frac{a_{k-1}+b_{k-1}}{2}

when the interval is [a_{k},b_{k}]

x_{k}=\frac{a_{k-1}+\frac{a_{k-1}+b_{k-1}}{2}}{2}=\frac{3a_{k-1}+b_{k-1}}{4}

So,|x_{k}-x_{k-1}|=|\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})|=|\frac{a_{k-1}-b_{k-1}}{4}|

But |a_{k}-b_{k}|=|\frac{a_{k-1}-b_{k-1}}{2}|

so they are not equal..what have I done wrong?

I see nothing wrong.
That looks entirely correct! ;)

What you have matches with what I wrote:
I like Serena said:
$$| x_k - x_{k-1} | = \frac{b_{k-1} - a_{k-1}}{4} = \frac{b_{k} - a_{k}}{2} = b_{k+1} - a_{k+1}$$
 
  • #33
I like Serena said:
I see nothing wrong.
That looks entirely correct! ;)

What you have matches with what I wrote:
|x_{k}-x_{k-1}|=|\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})|=|\frac{a_{k-1}-b_{k-1}}{4}|

|a_{k}-b_{k}|=|\frac{a_{k-1}-b_{k-1}}{2}|

How can they be equal?I don't understand :confused::(:confused:
 
  • #34
evinda said:
|x_{k}-x_{k-1}|=|\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})|=|\frac{a_{k-1}-b_{k-1}}{4}|

|a_{k}-b_{k}|=|\frac{a_{k-1}-b_{k-1}}{2}|

How can they be equal?I don't understand :confused::(:confused:

They are not equal.
|x_{k}-x_{k-1}| is half of |a_{k}-b_{k}|.

If you want equality, pick |a_{k+1}-b_{k+1}|.
 
  • #35
So,if they are not equal,why do we use the termination criteria |a-b|<TOL?I don't get it... :(
 
  • #36
evinda said:
So,if they are not equal,why do we use the termination criteria |a-b|<TOL?I don't get it... :(

We don't.
See your previous post:

evinda said:
Nice.. :o And..something else..I found implementations of the bisection method and there the termination criteria is
Code: 
 while(fabs((b-a)/2)>TOL)
.

Why is it like that?? :confused:

See?
 
  • #37
So,is it wrong when I write fabs(b-a)<TOL?
 
  • #38
evinda said:
So,is it wrong when I write fabs(b-a)<TOL?

Depends on the rest of your algorithm.
If you return (a+b)/2, then your result will still be within TOL.
So then it is right!
 
  • #39
Could you give me an example for this condition?
If for example the maximum number of iterations is 15,TOL is 0.001
and the initial interval is [0,2]

what is equal to the first

$\big|x_k-x_{k-1}\big|$ we have to use? :confused: :confused::confused:
 

Similar threads

MHB Newton's method-numerical analysis
  • · Replies 15 ·
Replies
15
Views
4K
MHB Hayldiburasomas' question via email about Secant Method
  • · Replies 1 ·
Replies
1
Views
10K
MHB Numerical analysis,results of methods
  • · Replies 1 ·
Replies
1
Views
2K
MHB Solving Equations Using Bisection, Newton, and Secant Methods
  • · Replies 8 ·
Replies
8
Views
3K
MATLAB Bisection method and numerical integration
  • · Replies 2 ·
Replies
2
Views
3K
MHB Implementation of numerical method
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Error bounds for Newton's Method
  • · Replies 13 ·
Replies
13
Views
3K
Undergrad Why is (a+b)/2 not recommended in the Bisection method?
  • · Replies 6 ·
Replies
6
Views
1K
Undergrad Why fixed point iteration of ##x^3 = 1-x^2## doesn't converge when ##x_0= 0##
  • · Replies 16 ·
Replies
16
Views
1K
Mathematica How can I optimize Mathematica computation time for functional definitions?
  • · Replies 2 ·
Replies
2
Views
2K