False position method: Difference between revisions
Line 8: | Line 8: | ||
The exploratory phase of the false position method involves finding a pair of input values at which the function has opposite signs. This could be done by running the usual [[secant method]] and evaluating at each stage until we get to opposite signs, ''or'' by some other means. Once we have found two points in the domain at which the function value has opposite signs, we are ready to begin the false position method ''proper''. | The exploratory phase of the false position method involves finding a pair of input values at which the function has opposite signs. This could be done by running the usual [[secant method]] and evaluating at each stage until we get to opposite signs, ''or'' by some other means. Once we have found two points in the domain at which the function value has opposite signs, we are ready to begin the false position method ''proper''. | ||
In the point estimate version of the iterative step, we will label these two initial guesses as <math>x_0</math> and <math>x_1</math> (so that <math>f(x_0)</math> and <math>f(x_1)</math> have opposite sign). In the nested interval version, we will label the smaller of them as <math>a_0</math> and the larger as <math>b_0</math>. | |||
==Iterative step== | ==Iterative step== |
Revision as of 17:11, 26 April 2014
This article is about a root-finding algorithm. See all root-finding algorithms
Definition
False position method is a root-finding algorithm that is qualitative similar to the bisection method in that it uses nested intervals based on opposite signs at the endpoints to converge to a root, but is computationally based on the secant method.
Initial exploratory phase
The exploratory phase of the false position method involves finding a pair of input values at which the function has opposite signs. This could be done by running the usual secant method and evaluating at each stage until we get to opposite signs, or by some other means. Once we have found two points in the domain at which the function value has opposite signs, we are ready to begin the false position method proper.
In the point estimate version of the iterative step, we will label these two initial guesses as and (so that and have opposite sign). In the nested interval version, we will label the smaller of them as and the larger as .
Iterative step
At stage , for , we find the largest for which has sign opposite to . We then define:
More details are below.
Prior knowledge: Prior to beginning stage :
- We have a previous set of guesses .
- We know that and have opposite sign to each other (this is the initial condition). Therefore, among the values , we know that there are both positive and negative values.
Iterative step:
- We find the largest such that and have opposite sign.
- We compute:
Iterative step in nested interval description
We start with an initial interval (here is the smaller of and from the original setup, and is the larger of them).
At stage for a positive integer
Prior knowledge:
- and are both numerically distinguishable from zero (so they have defined signs, positive or negative) and they have opposite signs.
- Combining that with the fact that is a continuous function, the intermediate value theorem tells us that has a root on .
Iterative step:
- Compute:
Note that since and have opposite signs, this is a convex combination, and therefore .
- In the case that has opposite sign to (and therefore the same sign as ), the new interval . Explicitly, and .
- In the case that has opposite sign to (and therefore the same sign as ), the new interval . Explicitly, and .
The values of as obtained here are the same as the values of in the preceding description. The main advantage of this description is that we are storing the intervals as we construct them rather than merely the point estimates, so that some aspects of how the procedure works are more transparent.