Okay, we're moving onto more of what I like to call live solution methods,
we saw using the goal seek and solver tools.
They are really nice for finding the solution to
a problem and for the solver tool you can find the minimum or maximum of a function.
But they're not live.
So in order to use live solutions,
we're going to look at the Bisection Method and then the Golden Section Search Method.
The Bisection Method is used to find the zero of a function.
So let's take a look at how we can implement this.
Shown here, it is a function,
and it crosses the X-axis at just before 2.5.
So, it has a solution between zero and four.
So, the first step in the bisection technique
is to determine the initial low and high bounds.
So I've already chosen this,
I've chosen zero as the low and four as the high.
Next, we bisect the interval and calculate the midpoint.
So the average of zero and four is two.
Next, we calculate the function values at the low and
the middle and we call these f(low) and f(mid).
So, f(low) is down here, f(mid) is here.
Now, the only thing that matters in the bisection technique is the sign.
We don't need to use the value at all.
So we have a negative and we have a negative.
And therefore, we assume that there is only one solution in each interval,
that's an assumption we're making.
So that means that it has to be plus at the upper bound.
The solution lies in the interval where we have a sign change, right?
If we go from negative to positive or positive to
negative that means we have to have the solution in there.
So in this case, we compare f(low) and f(mid),
they have the same sign.
So that means, that the solution has to be between mid and high.
So in this case,
we are going to eliminate everything to the left of
the midpoint because the sign change occurs in the right half.
So now, the midpoint becomes the new low.
So we've zoomed in the midpoint from the previous iteration was two.
Now, that's the low end of our interval.
For the second round of bisection,
we calculate a midpoint,
the midpoint between two and four is three.
We calculate the function values at the low.
Again, all we need is the signs,
so we have negative and we're going to positive at the midpoint.
Therefore, the sign change occurs on
the left half and so we can eliminate everything on the right.
So the midpoint of this iteration becomes the high of the next iteration.
So now, we're zooming in two to three.
We bisect this and calculate the midpoint which is 2.5.
We calculate the function values so at the low we have a negative,
in the middle we have a positive.
Therefore, we know that the solution lies
in the left half and we can eliminate everything on the right half.
So now, we're zooming in between two and 2.5.
The midpoint is 2.25.
We calculate the function values at the low and the middle.
They're both negative.
Therefore, since they're both negative,
we know that the solution lies in the upper half.
And in this case, we eliminate the left half.
Now, we zoom in between 2.25 and 2.5,
the midpoint is 2.375,
we calculate our low and mid function values.
All we need are the signs because there is
no sign change and left half that means the sign change has to be on the right half.
We eliminate the left half and we zoom in between 2.375 and 2.5.
And so, we keep going the midpoint would be here,
which I think has a negative.
We have a negative sign. Therefore, we eliminate the left half and we keep going.
So, just as a summary,
we start with our initial zero to four,
we eliminate left half then we eliminate the right half of the remaining.
Then we eliminate the right half of
the remaining interval and we eliminate that much and that.
So, it turns out even after we've only done six or seven rounds of iteration,
we've removed quite a bit of the initial interval and we're sort of
zooming in on an interval that contains the solution to the problem,
which is where the function crosses the X-axis.
It turns out that after n rounds of bisection,
we have removed one hundred times one minus 0.5 to the n% of the original interval,
which means after one round,
we've removed 50%, 75% after two,
87.5 after three, and after ten rounds we've removed over 99.9% of the initial interval.
And so, we're zooming in on a very small interval that contains our solution,
which means that basically the average of the remaining interval,
we're getting down to such a small interval that we can just kind
of look at the midpoint and say that's our solution to the function.
So, just as a summary, the Bisection Method,
we choose the initial low and high bounds.
We bisect the interval and calculate the midpoint.
Calculate the function values at the low and the mid,
we call that f(low) and f(mid).
All we really need are the signs.
We compare the signs of f(low) with f(mid).
If they have opposite signs,
that means that the solution is found in the left half of our interval.
If that's the case, if they have opposite signs then that means the
new high for the next interval is the old mid.
So we're zooming in on the left half.
However, if the signs for f(low) and f(mid) are the same,
they're either both positive or both negative,
then that means the solution crosses in the upper half of our interval.
In that case, the new low is the old mid.
So now, the last step is to return to step two and repeat.
And so, this is an iterative process,
we do this maybe 10 to 20 times to zoom in on an appropriate solution to the problem.
Now, I want to show you how we can solve this in Excel.
So the function in the screencast has been x cube + x - 17.
So, you have to know the function that you're working with.
And you have to know what initial low initial high.
So, you have to kind of assume or choose the initial low and high.
The midpoint is just the average of low and high.
So, I can type in a formula for that.
Next, we can calculate the f the function of low,
so I'm just going to plug zero into this function.
So we have our function.
It's a relative reference,
so when I press enter I can just do Ctrl C
and I can paste for the f(mid) and I can paste here.
Now, this is the tricky part,
we're trying to calculate the low for the next iteration,
if the product of f(low) times f(mid) is
negative then that means we get to go from negative to positive or positive to negative.
And that means, that the solution lies in the left interval.
If the product is positive,
that means that in the lower half we do not have the solution.
Now, this is going to take some time for you to absorb.
But I'm using an IF statement in Excel there's an IF function.
So, if f(low) times f(mid) is negative,
if this is true,
the second argument in the function is what should you put in the cell if that's true.
So if that's true, then I want the low because I'm working in the low column here.
Then that means that our solution is in
the left half and we want the low to be the previous low.
If this is false,
that means that the solutions in the upper half
and that case we want the new low to be the old mid.
So I put mid as a third argument.
So if this condition is true,
this is what you do if it's true,
this is what you do if it's false.
So you might want to pause this and take a little bit of time to chew this.
So in this case, because the solution is between f(mid) and f(high),
we go from a -7 to +51.
That means that the new low is going to be the old mid.
Similarly, for the new high,
we can compare f(low) to f(mid),
if f(low) times f(mid) is negative,
then that means the solutions on the left half.
If that's the case,
so if this is true we have the solution on
the left half and the new high is going to be the old mid.
So I put a pointer formula to the old mid on the previous iteration.
Otherwise, if that's false that means the solution is on
the upper half and the high is going to be the old high.
So again, pause this and take some time to absorb this.
Now, everything else is just I can copy down,
so I can take this row copy that down,
take this row copy it down.
Now, what I can do is I can take the second row,
only the second row,
and I'm going to drag this all the way down to my 10 iterations and it'll go through,
it should calculate this.
At the end of 10 iterations,
the midpoint and that is then the solution.
If you wanted to, you could drag it down another 10 iterations,
which is really easy to do in Excel.
So this is how you can implement the Bisection Method in Excel.
And in the next screencast,
we're going to take this technique in Excel and we're going to implement it into
our fuel storage tank problem and we're going to make it into a live solution.
Charlie NuttelmanInstructor
