Bisection method - Revision history

Vipul: /* Covariance under affine transformations on the domain */

2014-05-01T21:27:18Z

Covariance under affine transformations on the domain

← Older revision		Revision as of 21:27, 1 May 2014
Line 155:		Line 155:
	===Covariance under affine transformations on the domain===		===Covariance under affine transformations on the domain===

	Consider a function <math>f</math> and a a function <math>x \mapsto f(mx + c)</math> for <math>m \ne 0</math> and <math>c \in \R</math>. The functions behave the same way with respect to the bisection method, provided that we adjust the values of <math>x</math> by the same scalar multiple. In other words, the nested intervals for the second function would correspond to the interval with endpoints at <math>1/m (x - c)</math> for an interval endpoint <math>x</math> for the function <math>f</math>. Note that in the case that <math>m</math> is negative, the roles of left and right would also get switched.		Consider a function <math>f</math> and a a function <math>x \mapsto f(mx + c)</math> for <math>m \ne 0</math> and <math>c \in \R</math>. The functions behave the same way with respect to the bisection method, provided that we adjust the values of <math>x</math> by the same scalar multiple. In other words, the nested intervals for the second function would correspond to the interval with endpoints at <math>(1/m) (x - c)</math> for an interval endpoint <math>x</math> for the function <math>f</math>. Note that in the case that <math>m</math> is negative, the roles of left and right would also get switched.

	==The case of polynomials==		==The case of polynomials==

Vipul: /* Covariance under affine transformations on the domain */

2014-05-01T21:03:52Z

Covariance under affine transformations on the domain

← Older revision		Revision as of 21:03, 1 May 2014
Line 155:		Line 155:
	===Covariance under affine transformations on the domain===		===Covariance under affine transformations on the domain===

	Consider a function <math>f</math> and a a function <math>x \mapsto f(mx + c)</math> for <math>m \ne 0</math> and <math>c \in \R</math>. The functions behave the same way with respect to the bisection method, provided that we adjust the values of <math>x</math> by the same scalar multiple. In other words, the nested intervals for the second function would correspond to the interval with endpoints at <math>1/m</math> ~~of the nested intervals~~ for the ~~first~~ function. Note that in the case that <math>m</math> is negative, the roles of left and right would also get switched.		Consider a function <math>f</math> and a a function <math>x \mapsto f(mx + c)</math> for <math>m \ne 0</math> and <math>c \in \R</math>. The functions behave the same way with respect to the bisection method, provided that we adjust the values of <math>x</math> by the same scalar multiple. In other words, the nested intervals for the second function would correspond to the interval with endpoints at <math>1/m (x - c)</math> for an interval endpoint <math>x</math> for the function <math>f</math>. Note that in the case that <math>m</math> is negative, the roles of left and right would also get switched.

	==The case of polynomials==		==The case of polynomials==

Vipul: /* Covariance under scalar multiplication on the domain */

2014-05-01T21:03:16Z

Covariance under scalar multiplication on the domain

← Older revision		Revision as of 21:03, 1 May 2014
Line 153:		Line 153:
	The qualitative behavior of the bisection method (and in particular, the sequence of nested intervals obtained while running the method) is invariant under scalar multiplication of the function by a constant. In other words, the functions <math>f</math> and <math>x \mapsto \lambda f(x)</math>, for a constant <math>\lambda \ne 0</math>, behave the same way. This is modulo the caveat about numerical precision. Note, however, that given a particular function, multiplying it by a constant can never ''improve'' the precision (because we cannot get more information than already exists) so the key point remains that replacing the function by a scalar multiple doesn't help.		The qualitative behavior of the bisection method (and in particular, the sequence of nested intervals obtained while running the method) is invariant under scalar multiplication of the function by a constant. In other words, the functions <math>f</math> and <math>x \mapsto \lambda f(x)</math>, for a constant <math>\lambda \ne 0</math>, behave the same way. This is modulo the caveat about numerical precision. Note, however, that given a particular function, multiplying it by a constant can never ''improve'' the precision (because we cannot get more information than already exists) so the key point remains that replacing the function by a scalar multiple doesn't help.

	===Covariance under ~~scalar multiplication~~ on the domain===		===Covariance under affine transformations on the domain===

	Consider a function <math>f</math> and a a function <math>x \mapsto f(~~\lambda x~~)</math> for <math>~~\lambda~~ \ne 0</math>. The functions behave the same way with respect to the bisection method, provided that we adjust the values of <math>x</math> by the same scalar multiple. In other words, the nested intervals for the second function would correspond to the interval with endpoints at <math>1/~~\lambda~~</math> of the nested intervals for the first function.		Consider a function <math>f</math> and a a function <math>x \mapsto f(mx + c)</math> for <math>m \ne 0</math> and <math>c \in \R</math>. The functions behave the same way with respect to the bisection method, provided that we adjust the values of <math>x</math> by the same scalar multiple. In other words, the nested intervals for the second function would correspond to the interval with endpoints at <math>1/m</math> of the nested intervals for the first function. Note that in the case that <math>m</math> is negative, the roles of left and right would also get switched.

	==The case of polynomials==		==The case of polynomials==

Vipul: /* Sensitivity to the form in which the function is presented */

2014-05-01T20:56:53Z

Sensitivity to the form in which the function is presented

← Older revision		Revision as of 20:56, 1 May 2014
Line 151:		Line 151:
	===Invariance under scalar multiplication===		===Invariance under scalar multiplication===

	The qualitative behavior of the bisection method (and in particular, the sequence of nested intervals obtained while running the method) is invariant under scalar multiplication of the function by a constant. In other words, the functions <math>f</math> and <math>x \mapsto \lambda f(x)</math>, for a constant <math>\lambda</math>, behave the same way. This is modulo the caveat about numerical precision. Note, however, that given a particular function, multiplying it by a constant can never ''improve'' the precision (because we cannot get more information than already exists) so the key point remains that replacing the function by a scalar multiple doesn't help.		The qualitative behavior of the bisection method (and in particular, the sequence of nested intervals obtained while running the method) is invariant under scalar multiplication of the function by a constant. In other words, the functions <math>f</math> and <math>x \mapsto \lambda f(x)</math>, for a constant <math>\lambda \ne 0</math>, behave the same way. This is modulo the caveat about numerical precision. Note, however, that given a particular function, multiplying it by a constant can never ''improve'' the precision (because we cannot get more information than already exists) so the key point remains that replacing the function by a scalar multiple doesn't help.

			===Covariance under scalar multiplication on the domain===

			Consider a function <math>f</math> and a a function <math>x \mapsto f(\lambda x)</math> for <math>\lambda \ne 0</math>. The functions behave the same way with respect to the bisection method, provided that we adjust the values of <math>x</math> by the same scalar multiple. In other words, the nested intervals for the second function would correspond to the interval with endpoints at <math>1/\lambda</math> of the nested intervals for the first function.

	==The case of polynomials==		==The case of polynomials==

Vipul: /* Selection of root found and sensitivity to interval choice */

2014-05-01T20:48:44Z

Selection of root found and sensitivity to interval choice

@@ Line 125: / Line 125: @@
 * If <math>6 < a < 10</math>, then the first iteration yields the interval <math>[a/2,a]</math>, with <math>a/2 > 3</math>, and therefore we converge to the root 5 (which is the only root in the interval).
 * More  generally, if <math>5 \cdot 2^n < a < 6 \cdot 2^n</math> for <math>n</math> a nonnegative integer, we converge to the root 1. On the other hand, if <math>6 \cdot 2^n < a < 10 \cdot 2^n</math> for <math>n</math> a nonnegative integer, we converge to the root 5.
 ===The qualitative behavior depends purely on the signum of the function===
@@ Line 138: / Line 149: @@
 Modulo this computational caveat, two functions that are positive at the same places and negative at the same places would exhibit the same behavior with respect to the bisection method. In particular, if <math>q(x) = (p(x))^3</math>, <math>p</math> and <math>q</math> behave identically under the bisection method.
-The following follows:
+===Invariance under scalar multiplication===
-* The qualitative behavior of the bisection method (and in particular, the sequence of nested intervals obtained while running the method) is invariant under scalar multiplication of the function by a constant. In other words, the functions <math>f</math>
+The qualitative behavior of the bisection method (and in particular, the sequence of nested intervals obtained while running the method) is invariant under scalar multiplication of the function by a constant. In other words, the functions <math>f</math> and <math>x \mapsto \lambda f(x)</math>, for a constant <math>\lambda</math>, behave the same way. This is modulo the caveat about numerical precision. Note, however, that given a particular function, multiplying it by a constant can never ''improve'' the precision (because we cannot get more information than already exists) so the key point remains that replacing the function by a scalar multiple doesn't help.
 ==The case of polynomials==

Vipul: /* The qualitative behavior depends purely on the signum of the function */

2014-05-01T20:46:42Z

The qualitative behavior depends purely on the signum of the function

← Older revision		Revision as of 20:46, 1 May 2014
Line 131:		Line 131:

	<math>(\operatorname{sgn} \circ f)(x) := \left \lbrace \begin{array}{rl} 1, & \mbox{ if } f(x) > 0 \\ -1, & \mbox{ if } f(x) < 0 \\ 0, & \mbox{ if } f(x) = 0\\\end{array}\right.</math>		<math>(\operatorname{sgn} \circ f)(x) := \left \lbrace \begin{array}{rl} 1, & \mbox{ if } f(x) > 0 \\ -1, & \mbox{ if } f(x) < 0 \\ 0, & \mbox{ if } f(x) = 0\\\end{array}\right.</math>

			Further, it is also invariant under the flipping of ''all'' signs. So it is dependent on the signum of the function, up to global sign.

	From the computational perspective, there is an important caveat to the above: what matters for the signum function is not whether the actual value of <math>f</math> is positive, negative, or zero, but rather, whether the value as computed is definitely positive, definitely negative, or numerically indistinguishable from zero.		From the computational perspective, there is an important caveat to the above: what matters for the signum function is not whether the actual value of <math>f</math> is positive, negative, or zero, but rather, whether the value as computed is definitely positive, definitely negative, or numerically indistinguishable from zero.

	Modulo this computational caveat, two functions that are positive at the same places and negative at the same places would exhibit the same behavior with respect to the bisection method. In particular, if <math>q(x) = (p(x))^3</math>, <math>p</math> and <math>q</math> behave identically under the bisection method.		Modulo this computational caveat, two functions that are positive at the same places and negative at the same places would exhibit the same behavior with respect to the bisection method. In particular, if <math>q(x) = (p(x))^3</math>, <math>p</math> and <math>q</math> behave identically under the bisection method.

			The following follows:

			* The qualitative behavior of the bisection method (and in particular, the sequence of nested intervals obtained while running the method) is invariant under scalar multiplication of the function by a constant. In other words, the functions <math>f</math>

	===The process sacrifices smart use of information about the function for a guaranteed convergence rate===		===The process sacrifices smart use of information about the function for a guaranteed convergence rate===

Vipul: /* Convergence rate for best guess point estimate */

2014-04-26T17:04:08Z

Convergence rate for best guess point estimate

← Older revision		Revision as of 17:04, 26 April 2014
Line 61:		Line 61:
	===Convergence rate for best guess point estimate===		===Convergence rate for best guess point estimate===

	At stage <math>i</math>, we can define our ''best guess'' <math>c_i</math> as the midpoint <math>(~~a_i~~ + ~~b_i~~)/2</math>.		At stage <math>n</math>, we can define our ''best guess'' <math>c_i</math> as the midpoint <math>(a_n + b_n)/2</math>.

	The sequence <math>(c_n)</math> converges to a root, say <math>\alpha</math>. We need to determine the [[rate of convergence]].		The sequence <math>(c_n)</math> converges to a root, say <math>\alpha</math>. We need to determine the [[rate of convergence]].
Line 73:		Line 73:
	Equivalently:		Equivalently:

	<math>\|~~c_i~~ - \alpha\| < \frac{~~b_i~~ - ~~a_i~~}{2}</math>		<math>\|c_n - \alpha\| < \frac{b_n - a_n}{2}</math>

	Thus, we can define a sequence:		Thus, we can define a sequence:

Vipul: /* Rate of decline in guaranteed interval size */

2014-04-26T17:02:47Z

Rate of decline in guaranteed interval size

← Older revision		Revision as of 17:02, 26 April 2014
Line 51:		Line 51:
	We have the relationship:		We have the relationship:

	<math>b_{i+1} - a_{i+1} ~~= \frac{b_i - a_i~~}{2}</math>		<math>b_n - a_n= \frac{b_{n-1} - a_{n-1}}{2}</math>

	Thus, we obtain that:		Thus, we obtain that:

	<math>b_n - a_n = \frac{b - a}{2^n}</math>		<math>b_n - a_n = \frac{b_0 - a_0}{2^n} = \frac{b - a}{2^n}</math>

	In particular, the size of each interval is a linear multiple of the size of the preceding one, with a fixed constant of proportionality 1/2, and the overall interval size decays exponentially with <math>n</math>. This fits the paradigm of [[linear convergence]].		In particular, the size of each interval is a linear multiple of the size of the preceding one, with a fixed constant of proportionality 1/2, and the overall interval size decays exponentially with <math>n</math>. This fits the paradigm of [[linear convergence]].

Vipul: /* Iterative step */

2014-04-26T17:02:03Z

Iterative step

← Older revision		Revision as of 17:02, 26 April 2014
Line 31:		Line 31:
	Let <math>a_0 = a, b_0 = b</math>.		Let <math>a_0 = a, b_0 = b</math>.

	At stage <math>i</math> for <math>i</math> a ~~nonnegative~~ integer.		At stage <math>n</math> for <math>n</math> a positive integer.

	'''Prior knowledge''':		'''Prior knowledge''':

	* <math>f(~~a_i~~)</math> and <math>f(~~b_i~~)</math> are both numerically distinguishable from zero (so they have defined signs, positive or negative) and they have opposite signs.		* <math>f(a_{n-1})</math> and <math>f(b_{n-1})</math> 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 <math>f</math> is a continuous function, the [[intermediate value theorem]] tells us that <math>f</math> has a root on <math>[~~a_i~~,~~b_i~~]</math>.		* Combining that with the fact that <math>f</math> is a continuous function, the [[intermediate value theorem]] tells us that <math>f</math> has a root on <math>[a_{n-1},b_{n-1}]</math>.

	'''Iterative step''':		'''Iterative step''':

	* Compute <math>f((~~a_i~~ + ~~b_i~~)/2)</math>.		* Compute <math>f((a_{n - 1} + b_{n - 1})/2)</math>.
	* If it is equal to (or numerically indistinguishable from) zero, then return <math>(~~a_i~~ + ~~b_i~~)/2</math> as the root and terminate the algorithm.		* If it is equal to (or numerically indistinguishable from) zero, then return <math>(a_{n-1} + b_{n-1})/2</math> as the root and terminate the algorithm.
	* If <math>f((~~a_i~~ + ~~b_i~~)/2)</math> has sign opposite to <math>f(~~a_i~~)</math> (and therefore the same as <math>f(~~b_i~~)</math>), then choose <math>a_{i+1} ~~= a_i~~</math> and <math>b_{i+1} ~~= (a_i + b_i~~)/2</math>, so the new interval (for the next iteration) is <math>[a_{i+1},b_{i+1}~~] = [a_i, (a_i+b_i~~)/2]</math>.		* If <math>f((a_{n-1} + b_{n-1})/2)</math> has sign opposite to <math>f(a_{n-1})</math> (and therefore the same as <math>f(b_{n-1})</math>), then choose <math>a_n = a_{n - 1}</math> and <math>b_n = (a_{n-1} + b_{n-1})/2</math>, so the new interval (for the next iteration) is <math>[a_n,b_n] = [a_{n-1}, (a_{n-1}+b_{n-1})/2]</math>.
	* If <math>f((~~a_i~~ + ~~b_i~~)/2)</math> has sign opposite to <math>f(~~b_i~~)</math> (and therefore the same as <math>f(~~a_i~~)</math>), ~~the nchoose~~ <math>a_{i+1} ~~= (a_i + b_i~~)/2</math> and <math>b_{i+1} ~~= b_i~~</math>, so the new interval (for the next iteration) is <math>[a_{i+1},b_{i+1}~~] = [(a_i+b_i~~)/2, ~~b_i~~]</math>.		* If <math>f((a_{n-1} + b_{n-1})/2)</math> has sign opposite to <math>f(b_{n-1})</math> (and therefore the same as <math>f(a_{n-1})</math>), then choose <math>a_n = (a_{n-1} + b_{n-1})/2</math> and <math>b_n = b_{n-1}</math>, so the new interval (for the next iteration) is <math>[a_n,b_n] = [(a_{n-1}+b_{n-1})/2, b_{n-1}]</math>.

	==Convergence rate==		==Convergence rate==

Vipul: /* Convergence rate */

2014-04-26T16:41:12Z

Convergence rate

@@ Line 46: / Line 46: @@
 ==Convergence rate==
 At stage <math>i</math>, we can define our ''best guess'' <math>c_i</math> as the midpoint <math>(a_i + b_i)/2</math>.
-We can measure the convergence rate by looking at the size of the interval within which a root is guaranteed, and how this changes with time. We notice that the interval size halves at each stage, so that <math>|b_n - a_n| = |b - a|/2^n</math>. The distance between <math>c_i</math> and the location of an actual root is bounded from above by half the interval length, so this also asymptotically halves with each iteration (at worst, and on average).
+The sequence <math>(c_n)</math> converges to a root, say <math>\alpha</math>. We need to determine the [[rate of convergence]].
-This is a form of [[linear convergence]].
+Clearly, the sequence <math>\varepsilon_n</math> has [[linear convergence]] to zero, threfore the original sequence of point has R-linear convergence to zero.
 ==Computational tools needed==