# Numerical analysis question

1. Apr 10, 2010

### nhrock3

http://i40.tinypic.com/seyrys.jpg
we cant see what is the pattern of finding s?
what s represents?
in iteration 0 s is found by sum of an and bn
in the 1st 2nd and 3rd iteration its found by their subtraction
in the 4th its neither

??

Last edited: Apr 10, 2010
2. Apr 10, 2010

### justsof

Basically you start with an interval where you think the zero would be (an - bn)(where f(an)>0 and f(bn)<0 or the other way around), determine the middle point in this interval cn, and use f(cn) to determine if your zero is in the left part or the right part of the halved interval. Continue this proces with the either the right or left half interval.
You could check out http://en.wikipedia.org/wiki/Bisection_method it is at least more clearly explained than in your book.

3. Apr 10, 2010

### nhrock3

http://i40.tinypic.com/seyrys.jpg
we cant see what is the pattern of finding s?
what s represents?
in iteration 0 s is found by sum of an and bn
in the 1st 2nd and 3rd iteration its found by their subtraction
in the 4th its neither

??

4. Apr 10, 2010

### D H

Staff Emeritus
On that page, s is -1, the solution of x3-x=0 to which this particular sequence {cn} converges. It is not computed from an, bn, or cn.

The bisection method is very simple -- and very, very slow. Suppose you want to find a point at which some function f(x) is zero, and suppose you have found two points a0 and b0 such that f(a0) and f(b0) have different signs. That the function has different signs at these points means that
1. The function has one or more zero between a0 and b0, or
2. The function has one or more discontinuity between a0 and b0 where the function changes sign across the discontinuity, or
3. Both of the above are true.
If the function is known to be continuous between points a0 and b0 the only possibility is option #1, that the function has one or more zeros between these points.

So how to use this method? Simple. Evaluate the function at the point halfway between a0 and b0. Call this halfway point c0. There are three possibilities for f(c0):
1. f(c0)=0. You have found a solution!
2. f(c0) has the same sign as f(a0). This means a zero exists between points c0 and b0. Simply repeat with a1=c0 and b1=b0.
3. f(c0) has the same sign as f(b0). This means a zero exists between points a0 and c0. Simply repeat with a1=a0 and b1=c0.

The beauty of the midpoint method is that it will always find a point where the function changes sign. It never fails. More powerful methods such as Newton's method can and often do fail. Many zero-finding techniques employ multiple techniques, and many of them use the midpoint method as a method of last resort when all of the more powerful techniques fail.

That they use midpoint as a method of last resort suggests that the midpoint method has some flaws. It is slow. Newton's method, when it converges, will typically double the number of significant digits in the answer with every step. Over three steps (log(10)/log(2) steps) are needed with midpoint method to add one significant digit to the answer. That is slow.

There is another flaw to the technique: You have to somehow find those initial points a0 and b0 before you even start applying the technique. If you cannot find such a pair of points you cannot even start using the midpoint method.

5. Apr 10, 2010

### nhrock3

how to find S in each itiration???
what it represents??
why s=-1?
we have 3 solutions
s=1 s=-1 s=0

how you desided to choose that s=-1

how did you know that it will converge to that root?

Last edited: Apr 10, 2010
6. Apr 10, 2010

### D H

Staff Emeritus
You don't find s in each iteration. Read my previous post instead of asking the same question over and over.

7. Apr 10, 2010

### nhrock3

why s=-1?
we have 3 solutions
s=1 s=-1 s=0

how you desided to choose that s=-1

how did you know that it will converge to that root?

8. Apr 10, 2010

### D H

Staff Emeritus
Forget about s. It is impeding your understanding. The simple answer is that s is -1 in this case because the authors of that book knew ahead of time which of the three solutions this particular choice of bounds (the initial values of a and b) would make the algorithm converge to -1.

In general, you do not know what value the midpoint method will converge to ahead of time. If you did, game over. There would be no need to use any zero-finding method because you already have a zero. What is typically done with any zero-finding technique is to look at the change between the n-1st and nth solutions. Once that difference gets small enough the technique is deemed to have converged. Here is a better presentation of the midpoint method for this particular problem with this particular set of initial bounds, with the iteration stopping when the change in c gets smaller than 0.01:

$$\begin{array}{lllll} n & \phantom{-}a_n & \phantom{-}b_n & \phantom{-}c_n & |\Delta c_n|\\ 0 & -3 & \phantom{-}2 & -0.5 & \text{---} \\ 1 & -3 & -0.5 & -1.75 &1.25\\ 2 & -1.75 & -0.5 & -1.125 &0.625\\ 3 & -1.125 & -0.5 & -0.8125 &0.3125\\ 4 & -1.125 & -0.8125 & -0.96875 &0.15625\\ 5 & -1.125 & -0.96875 & -1.046875 &0.078125\\ 6 & -1.046875 & -0.96875 & -1.0078125 &0.0390625\\ 7 & -1.0078125 & -0.96875 & -0.98828125 &0.01953125\\ 8 & -1.0078125 & -0.98828125 & -0.998046875 &0.009765625 \end{array}$$

Last edited: Apr 10, 2010
9. Apr 10, 2010

### justsof

Respect that you take the time to post such an extensive answer to someone who seems not to care so much since he is copy pasting most of his questions... That's so sad...