Talk:Bisection method
Number of iterations for certain Tolerance
I think a little more should be added to this page about the number of iterations of the Bisection Method is needed to get the function within a certain Tolerance. By modeifying Theorem 2.1 from Numerical Analysis 8th edition, a quick bound approximation to the error can be found. Even know the actual error can be much smaller, it gives a good estimate of how long a function will take to converge by the Bisection Method. I would like to add info about this Sc920505 (talk) 13:07, 30 September 2008 (UTC)
Hmm, my textbook give the formula for the absolute error as (b-a)/2^n. Whereas the one here is (b-a)/2^(n+1). I don't know which one is correct... can someone clarify for me?
- Its (b-a)/2^(n+1). Think about it... Let n=0. then if it was (b-a)/2^n then the error would be b-a, which would extend beyond the limits of b and a, a ___domain in which we know MUST contain the target. Strange though, that a textbook had it wrong....
- Also, I would like to tell readers of this article that bisection can break down if f is non-continous or is not monotonic or not a function. It is too much of an unnecessary complication for the article, but worth mentioning.
- I don't think that f needs to be monotone (why do you think so?), but it indeed needs to be a continuous function. -- Jitse Niesen (talk) 12:11, 13 November 2005 (UTC)
- just put a note that the function must be differentiable along the section wanting to be root searched. —The preceding unsigned comment was added by Mikefadock (talk • contribs) .
- Please explain why you think it needs to be differentiable. -- Jitse Niesen (talk) 02:20, 3 March 2006 (UTC)
- The error is |b-a|/2^n. His text had it right. After 1 subdivision (n=1), the error is at most half the original interval, not 1/4. |b-a| doesn't extend beyond the ___domain in which we know must contain the target -- it's exactly equal to it. I also added the missing absolute value. 165.189.91.148 20:46, 20 April 2006 (UTC)
- It depends on what you take to be the approximation to the root. If you use the midpoint of the interval, the error is |b-a|/2^(n+1); if you use either endpoint, the error is |b-a|/2^n. Which formula is used, is not very important, in my opinion. -- Jitse Niesen (talk) 02:26, 21 April 2006 (UTC)
- Agreed, and I've edited the section to reflect the "controversy". The problem arises because the method doesn't give a single estimate for the root's ___location, and the concepts of "absolute error" and "length of the interval" are easily confused. The actual formula indeed isn't important, save in Calculus 1 classes where it's fairly often an exam question. Majromax (talk) 22:38, 19 November 2007 (UTC)
Pseudo Code completion
The Pseudo Code presented in this article needs to be made more accurate. As of right now, it does not account for the possibility of encoutering the 0 exactily on xL or xR. A theird condition needs to be added.
- No. Bisection method will happily converge to a root even if it occurs at the endpoint. It will just converge to the endpoint with the root. The given pseudocde is proper in that it will consider an interval beginning or ending at 0 to have a sign change. Admittedly, this isn't exactly an efficient approach, but it certainly gives clear code without extraneous conditions. Majromax (talk) 22:38, 19 November 2007 (UTC)
Visual Basic Code
state which version. Visual Basic.net is not backward compatible with previous versions anymore —Preceding unsigned comment added by 192.197.54.27 (talk) 14:10, 2 October 2007 (UTC)
- Although in general the two are not compatible, this code runs in both VB.net and the older VisualBasic. CRGreathouse (t | c) 21:32, 2 April 2008 (UTC)
- Anyway, Visual Basic isn't, it would be wiser to write the pseudocode in Python or Java. --74.210.230.96 (talk) 01:29, 26 November 2008 (UTC)
enumeration
- If f has several roots in the interval [a, b], then the bisection method finds the odd-numbered roots with equal, non-zero probability and the even-numbered roots with zero probability (Corliss 1977).
with respect to which enumeration??? --Philtime (talk) 08:28, 11 May 2008 (UTC) PS: what if there are is an infinite and/or uncountable amount of roots? --Philtime (talk) 08:28, 11 May 2008 (UTC)
- I think by even-numbered it means double etc. So looking at something like
- which has a double root at -1 and a triple root at 0, it is saying that 0 would almost always be found rather than -1. --Rumping (talk) 17:44, 30 August 2008 (UTC)
- I looked through Corliss' article and added some details to the article. The roots are enumerated according to their order. I don't know what happens if there are infinitely many roots; it makes sense to assume they all have probability zero, but perhaps the axioms of probability theory do not work in this case. -- Jitse Niesen (talk) 15:51, 20 September 2008 (UTC)
supplement on "convergence linearly"
Convergence
Hi, I have a question on the "convergence linearly" . Since the absolute error of bisection convergence is |b-a|/2^n, so the rate of convergence is O(1/2^n) which means the growth of error is exponential. I think it is more precise to use this information instead of the phrase "convergence linearly"! —Preceding unsigned comment added by 132.235.37.166 (talk) 13:24, 3 October 2008 (UTC)