What is the Pattern for Finding s in Iterative Calculations?

[nhrock3]

in this page
http://i40.tinypic.com/seyrys.jpg
we can't 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

??

 

[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.

 

[nhrock3]

in this page
http://i40.tinypic.com/seyrys.jpg
we can't 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

??

 

[D H]

On that page, s is -1, the solution of x³-x=0 to which this particular sequence {c_n} converges. It is not computed from a_n, b_n, or c_n.

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 a₀ and b₀ such that f(a₀) and f(b₀) have different signs. That the function has different signs at these points means that

1. The function has one or more zero between a₀ and b₀, or
2. The function has one or more discontinuity between a₀ and b₀ 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 a₀ and b₀ 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 a₀ and b₀. Call this halfway point c₀. There are three possibilities for f(c₀):

1. f(c₀)=0. You have found a solution!
2. f(c₀) has the same sign as f(a₀). This means a zero exists between points c₀ and b₀. Simply repeat with a₁=c₀ and b₁=b₀.
3. f(c₀) has the same sign as f(b₀). This means a zero exists between points a₀ and c₀. Simply repeat with a₁=a₀ and b₁=c₀.

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 a₀ and b₀ before you even start applying the technique. If you cannot find such a pair of points you cannot even start using the midpoint method.

 

[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?

 

[D H]

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

 

[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?

 

[D H]

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-1^st and n^th 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}<br /> n & \phantom{-}a_n & \phantom{-}b_n & \phantom{-}c_n & |\Delta c_n|\\<br /> 0 & -3 & \phantom{-}2 & -0.5 & \text{---} \\<br /> 1 & -3 & -0.5 & -1.75 &1.25\\<br /> 2 & -1.75 & -0.5 & -1.125 &0.625\\<br /> 3 & -1.125 & -0.5 & -0.8125 &0.3125\\<br /> 4 & -1.125 & -0.8125 & -0.96875 &0.15625\\<br /> 5 & -1.125 & -0.96875 & -1.046875 &0.078125\\<br /> 6 & -1.046875 & -0.96875 & -1.0078125 &0.0390625\\<br /> 7 & -1.0078125 & -0.96875 & -0.98828125 &0.01953125\\<br /> 8 & -1.0078125 & -0.98828125 & -0.998046875 &0.009765625<br /> \end{array}$$

 

[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...