False position method - Revision history

Vipul at 17:41, 28 April 2014

2014-04-28T17:41:15Z

← Older revision		Revision as of 17:41, 28 April 2014
Line 14:		Line 14:

	==Iterative step==		==Iterative step==

			===Point estimate version===

	At stage <math>n</math>, for <math>n \ge 2</math>, we find the largest <math>k</math> for which <math>f(x_k)</math> has sign opposite to <math>f(x_{n-1})</math>. We then define:		At stage <math>n</math>, for <math>n \ge 2</math>, we find the largest <math>k</math> for which <math>f(x_k)</math> has sign opposite to <math>f(x_{n-1})</math>. We then define:
Line 33:		Line 35:
	<math>x_n := \frac{x_kf(x_{n-1}) - x_{n-1}f(x_k)}{f(x_{n-1}) - f(x_k)}</math>		<math>x_n := \frac{x_kf(x_{n-1}) - x_{n-1}f(x_k)}{f(x_{n-1}) - f(x_k)}</math>

	==~~Iterative step in nested~~ interval ~~description~~==		===Nested interval version===

	We start with an initial interval <math>[a_0,b_0]</math> (here <math>a_0</math> is the smaller of <math>x_0</math> and <math>x_1</math> from the original setup, and <math>b_0</math> is the larger of them).		We start with an initial interval <math>[a_0,b_0]</math> (here <math>a_0</math> is the smaller of <math>x_0</math> and <math>x_1</math> from the original setup, and <math>b_0</math> is the larger of them).

Vipul at 17:15, 26 April 2014

2014-04-26T17:15:20Z

← Older revision		Revision as of 17:15, 26 April 2014
Line 4:		Line 4:

	'''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]].		'''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]].

			Unless otherwise specified, the function will be denoted <math>f</math>.

	==Initial exploratory phase==		==Initial exploratory phase==
Line 49:		Line 51:

	Note that since <math>f(a_{n-1})</math> and <math>f(b_{n-1})</math> have opposite signs, this is a convex combination, and therefore <math>x_n \in [a_{n-1},b_{n-1}]</math>.		Note that since <math>f(a_{n-1})</math> and <math>f(b_{n-1})</math> have opposite signs, this is a convex combination, and therefore <math>x_n \in [a_{n-1},b_{n-1}]</math>.
			* In the case that <math>f(x_n) = 0</math> (or is numerically indistinguishable from zero), we declare that as the root and terminate the algorithm.
			* In the case that <math>f(x_n)</math> has opposite sign to <math>f(a_{n-1})</math> (and therefore the same sign as <math>f(b_{n-1})</math>), the new interval <math>[a_n,b_n] = [a_{n-1},x_n]</math>. Explicitly, <math>a_n = a_{n-1}</math> and <math>b_n = x_n</math>.
			* In the case that <math>f(x_n)</math> has opposite sign to <math>f(b_{n-1})</math> (and therefore the same sign as <math>f(a_{n-1})</math>), the new interval <math>[a_n,b_n] = [x,b_{n-1}]</math>. Explicitly, <math>a_n = x_n</math> and <math>b_n = b_{n-1}</math>.

			The values of <math>x_n</math> as obtained here are the same as the values of <math>x_n</math> 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.

	* In the case that <math>f(x)</math> has opposite sign to <math>f(a_{n-1})</math> (and therefore the same sign as <math>f(b_{n-1})</math>), the new interval <math>[a_n,b_n] = ~~[a_{n-1},x_n]</math>. Explicitly, <math>a_n~~ = ~~a_{n-1}</math> and <math>b_n~~ = ~~x_n</math>.~~		==Convergence rate==
	* In the case that <math>f(x)</math> has opposite sign to <math>f(b_{n-1})</math> (and therefore the same sign as <math>f(a_{n-1})</math>), the new interval <math>[a_n,b_n] = ~~[x,b_{n-1}]</math>. Explicitly, <math>a_n = x_n</math> and <math>b_n = b_{n-1}</math>.~~

	~~The values of <math>x_n</math> as obtained here are~~ the ~~same as the values of~~ <math>~~x_n~~</math> ~~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~~.		===Convergence for linear functions===

			In the case that <math>f</math> is linear, we reach the root in one iteration after we have found values where the function has opposite signs. In fact, even if we applied the [[secant method]] directly, we would terminate in one step.

			===Convergence for twice differentiable functions===

			{{fillin}}

Vipul: /* Initial exploratory phase */

2014-04-26T17:11:28Z

Initial exploratory phase

← Older revision		Revision as of 17:11, 26 April 2014
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==

Vipul: /* Iterative step in nested interval description */

2014-04-26T17:10:22Z

Iterative step in nested interval description

← Older revision		Revision as of 17:10, 26 April 2014
Line 51:		Line 51:
	* In the case that <math>f(x)</math> has opposite sign to <math>f(b_{n-1})</math> (and therefore the same sign as <math>f(a_{n-1})</math>), the new interval <math>[a_n,b_n] = [x,b_{n-1}]</math>. Explicitly, <math>a_n = x_n</math> and <math>b_n = b_{n-1}</math>.		* In the case that <math>f(x)</math> has opposite sign to <math>f(b_{n-1})</math> (and therefore the same sign as <math>f(a_{n-1})</math>), the new interval <math>[a_n,b_n] = [x,b_{n-1}]</math>. Explicitly, <math>a_n = x_n</math> and <math>b_n = b_{n-1}</math>.

	The values of <math>x_n</math> as obtained here are the same as the values of <math>x_n</math> in the preceding description.		The values of <math>x_n</math> as obtained here are the same as the values of <math>x_n</math> 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.

Vipul: /* Iterative step */

2014-04-26T17:09:34Z

Iterative step

@@ Line 11: / Line 11: @@
 ==Iterative step==
-At stage <math>n</math>, we find the largest <math>k</math> for which <math>f(x_k)</math> has sign opposite to <math>f(x_{n-1})</math>. We then define:
+At stage <math>n</math>, for <math>n \ge 2</math>, we find the largest <math>k</math> for which <math>f(x_k)</math> has sign opposite to <math>f(x_{n-1})</math>. We then define:
 <math>x_n := \frac{x_kf(x_{n-1}) - x_{n-1}f(x_k)}{f(x_{n-1}) - f(x_k)}</math>

Vipul at 16:46, 26 April 2014

2014-04-26T16:46:10Z

← Older revision		Revision as of 16:46, 26 April 2014
Line 3:		Line 3:
	==Definition==		==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]]. The ~~idea is to use~~ the secant method to ~~make successive point estimates~~, ~~and provide the nested interval estimate based on the most recent point and~~ the ~~most recent point prior to that where~~ the function value has opposite sign.		'''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''.

			==Iterative step==

			At stage <math>n</math>, we find the largest <math>k</math> for which <math>f(x_k)</math> has sign opposite to <math>f(x_{n-1})</math>. We then define:

			<math>x_n := \frac{x_kf(x_{n-1}) - x_{n-1}f(x_k)}{f(x_{n-1}) - f(x_k)}</math>

Vipul: /* Definition */

2014-04-24T01:35:10Z

Definition

← Older revision		Revision as of 01:35, 24 April 2014
Line 3:		Line 3:
	==Definition==		==Definition==

	'''False position method''' is a [[root-finding algorithm]] that is qualitative similar to [[bisection ~~search~~]] 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]]. The idea is to use the secant method to make successive point estimates, and provide the nested interval estimate based on the most recent point and the most recent point prior to that where the function value has opposite sign.		'''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]]. The idea is to use the secant method to make successive point estimates, and provide the nested interval estimate based on the most recent point and the most recent point prior to that where the function value has opposite sign.

Vipul: Created page with "{{root-finding algorithm}} ==Definition== '''False position method''' is a root-finding algorithm that is qualitative similar to bisection search in that it uses nes..."

2014-04-24T01:34:46Z

Created page with "{{root-finding algorithm}} ==Definition== '''False position method''' is a root-finding algorithm that is qualitative similar to bisection search in that it uses nes..."

New page

{{root-finding algorithm}}

==Definition==

'''False position method''' is a [[root-finding algorithm]] that is qualitative similar to [[bisection search]] 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]]. The idea is to use the secant method to make successive point estimates, and provide the nested interval estimate based on the most recent point and the most recent point prior to that where the function value has opposite sign.