Root-finding algorithm - Revision history

2001:818:EB41:FC00:9EA2:28F2:C537:1780: /* Bracketing methods */ not notable; this method has some well-known issues and there has been little research on it;

2025-05-04T15:10:55Z

Bracketing methods: not notable; this method has some well-known issues and there has been little research on it;

← Previous revision		Revision as of 15:10, 4 May 2025
Line 19:		Line 19:

	False position is similar to the [[secant method]], except that, instead of retaining the last two points, it makes sure to keep one point on either side of the root. The false position method can be faster than the bisection method and will never diverge like the secant method. However, it may fail to converge in some naive implementations due to roundoff errors that may lead to a wrong sign for {{math\|''f''(''c'')}}. Typically, this may occur if the [[derivative]] of {{mvar\|f}} is large in the neighborhood of the root.		False position is similar to the [[secant method]], except that, instead of retaining the last two points, it makes sure to keep one point on either side of the root. The false position method can be faster than the bisection method and will never diverge like the secant method. However, it may fail to converge in some naive implementations due to roundoff errors that may lead to a wrong sign for {{math\|''f''(''c'')}}. Typically, this may occur if the [[derivative]] of {{mvar\|f}} is large in the neighborhood of the root.

	=== ITP method ===
	The [[ITP Method\|ITP method]] is the only known method to bracket the root with the same worst case guarantees of the bisection method while guaranteeing a superlinear convergence to the root of smooth functions as the secant method. It is also the only known method guaranteed to outperform the bisection method on the average for any continuous distribution on the location of the root (see [[ITP Method#Analysis]]). It does so by keeping track of both the bracketing interval as well as the minmax interval in which any point therein converges as fast as the bisection method. The construction of the queried point c follows three steps: interpolation (similar to the regula falsi), truncation (adjusting the regula falsi similar to [[Regula falsi#Improvements in ''regula falsi''\|Regula falsi § Improvements in ''regula falsi'']]) and then projection onto the minmax interval. The combination of these steps produces a simultaneously minmax optimal method with guarantees similar to interpolation based methods for smooth functions, and in practice will outperform both the bisection method and interpolation based methods applied to both smooth and non-smooth functions.

	== Interpolation ==		== Interpolation ==

Joyous!: Reverted 1 edit by 144.48.118.113 (talk) to last revision by WinstonWolfie

2025-04-29T03:58:34Z

Reverted 1 edit by 144.48.118.113 (talk) to last revision by WinstonWolfie

← Previous revision		Revision as of 03:58, 29 April 2025
Line 50:		Line 50:
	:<math> x_{n+1}=x_n^2+2x_n-1 </math>, or		:<math> x_{n+1}=x_n^2+2x_n-1 </math>, or
	:<math> x_{n+1}=\pm \sqrt{1-x_n} </math>.		:<math> x_{n+1}=\pm \sqrt{1-x_n} </math>.
	:< I Love You>

	=== Inverse interpolation ===		=== Inverse interpolation ===

144.48.118.113: /* Fixed point iteration method */

2025-04-29T03:55:59Z

Fixed point iteration method

← Previous revision		Revision as of 03:55, 29 April 2025
Line 50:		Line 50:
	:<math> x_{n+1}=x_n^2+2x_n-1 </math>, or		:<math> x_{n+1}=x_n^2+2x_n-1 </math>, or
	:<math> x_{n+1}=\pm \sqrt{1-x_n} </math>.		:<math> x_{n+1}=\pm \sqrt{1-x_n} </math>.
			:< I Love You>

	=== Inverse interpolation ===		=== Inverse interpolation ===

WinstonWolfie: /* Bisection method */

2025-04-12T14:59:46Z

Bisection method

← Previous revision		Revision as of 14:59, 12 April 2025
Line 12:		Line 12:

	=== Bisection method ===		=== Bisection method ===
	The simplest root-finding algorithm is the [[bisection method]]. Let {{math\|''f''}} be a [[continuous function]] for which one knows an interval {{math\|[''a'', ''b'']}} such that {{math\|''f''(''a'')}} and {{math\|''f''(''b'')}} have opposite signs (a bracket). Let {{math\|1=''c'' = (''a'' +''b'')/2}} be the middle of the interval (the midpoint or the point that bisects the interval). Then either {{math\|''f''(''a'')}} and {{math\|''f''(''c'')}}, or {{math\|''f''(''c'')}} and {{math\|''f''(''b'')}} have opposite signs, and one has divided by two the size of the interval. Although the bisection method is robust, it gains one and only one [[bit]] of accuracy with each iteration. Therefore, the number of function evaluations required for finding an ''ε''-approximate root is <math>\log_2\frac{b-a}{\varepsilon}</math>. Other methods, under appropriate conditions, can gain accuracy faster.		The simplest root-finding algorithm is the [[bisection method]]. Let {{math\|''f''}} be a [[continuous function]] for which one knows an interval {{math\|[''a'', ''b'']}} such that {{math\|''f''(''a'')}} and {{math\|''f''(''b'')}} have opposite signs (a bracket). Let {{math\|1=''c'' = (''a'' + ''b'')/2}} be the middle of the interval (the midpoint or the point that bisects the interval). Then either {{math\|''f''(''a'')}} and {{math\|''f''(''c'')}}, or {{math\|''f''(''c'')}} and {{math\|''f''(''b'')}} have opposite signs, and one has divided by two the size of the interval. Although the bisection method is robust, it gains one and only one [[bit]] of accuracy with each iteration. Therefore, the number of function evaluations required for finding an ''ε''-approximate root is <math>\log_2\frac{b-a}{\varepsilon}</math>. Other methods, under appropriate conditions, can gain accuracy faster.

	=== False position (''regula falsi'') ===		=== False position (''regula falsi'') ===

133.86.227.82: /* Further reading */

2024-12-24T07:53:29Z

AnomieBOT: Dating maintenance tags: {{Page needed}}

2024-12-16T20:24:00Z

Dating maintenance tags: {{Page needed}}

← Previous revision		Revision as of 20:24, 16 December 2024
Line 71:		Line 71:
	The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.		The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.

	Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|last1=Ortega \|first1= James M. \|last2=Rheinboldt \|first2=Werner C. \|title=Iterative solution of nonlinear equations in several variables \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.		Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|last1=Ortega \|first1= James M. \|last2=Rheinboldt \|first2=Werner C. \|title=Iterative solution of nonlinear equations in several variables \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed\|date=December 2024}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.

	A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.		A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.

Jacobolus: /* Finding roots in higher dimensions */ should include author names though

2024-12-16T20:03:16Z

Finding roots in higher dimensions: should include author names though

← Previous revision		Revision as of 20:03, 16 December 2024
Line 71:		Line 71:
	The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.		The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.

	Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|title=Iterative solution of nonlinear equations in several variables \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.		Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|last1=Ortega \|first1= James M. \|last2=Rheinboldt \|first2=Werner C. \|title=Iterative solution of nonlinear equations in several variables \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.

	A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.		A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.

Jacobolus: /* Finding roots in higher dimensions */ oh wait, this url doesn't have the content online. let's just skip it

2024-12-16T20:02:13Z

Finding roots in higher dimensions: oh wait, this url doesn't have the content online. let's just skip it

← Previous revision		Revision as of 20:02, 16 December 2024
Line 71:		Line 71:
	The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.		The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.

	Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|title=Iterative solution of nonlinear equations in several variables ~~\|url=https://dl.acm.org/doi/abs/10.5555/335947 \|url-access=subscription~~ \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.		Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|title=Iterative solution of nonlinear equations in several variables \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.

	A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.		A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.

Jacobolus: /* Finding roots in higher dimensions */ apparently this DOI didn't work

2024-12-16T20:00:36Z

Finding roots in higher dimensions: apparently this DOI didn't work

← Previous revision		Revision as of 20:00, 16 December 2024
Line 71:		Line 71:
	The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.		The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.

	Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|title=Iterative solution of nonlinear equations in several variables \|~~doi~~=10.5555/335947 \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.		Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|title=Iterative solution of nonlinear equations in several variables \|url=https://dl.acm.org/doi/abs/10.5555/335947 \|url-access=subscription \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.

	A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.		A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.

Jacobolus: citing a 500 page book for this claim makes it hard to verify

2024-12-16T19:58:41Z

citing a 500 page book for this claim makes it hard to verify

← Previous revision		Revision as of 19:58, 16 December 2024
Line 71:		Line 71:
	The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.		The [[Poincaré–Miranda theorem]] gives a criterion for the existence of a root in a rectangle, but it is hard to verify because it requires evaluating the function on the entire boundary of the rectangle.

	Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|title=Iterative solution of nonlinear equations in several variables \|~~url~~=~~https://dl.acm.org/doi/abs/~~10.5555/335947 \|~~access-~~date=~~2023-04-16 \|website=Guide books \|date=February~~ 2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 ~~\|language=EN~~ }}</ref> It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.		Another criterion is given by a theorem of [[Leopold Kronecker\|Kronecker]].<ref>{{Cite book \|title=Iterative solution of nonlinear equations in several variables \|doi=10.5555/335947 \|date=2000 \|publisher=Society for Industrial and Applied Mathematics \|isbn=978-0-89871-461-6 }}</ref>{{Page needed}} It says that, if the [[Degree of a continuous mapping\|topological degree]] of a function ''f'' on a rectangle is non-zero, then the rectangle must contain at least one root of ''f''. This criterion is the basis for several root-finding methods, such as those of Stenger<ref>{{Cite journal \|last=Stenger \|first=Frank \|date=1975-03-01 \|title=Computing the topological degree of a mapping inRn \|url=https://doi.org/10.1007/BF01419526 \|journal=Numerische Mathematik \|language=en \|volume=25 \|issue=1 \|pages=23–38 \|doi=10.1007/BF01419526 \|s2cid=122196773 \|issn=0945-3245}}</ref> and Kearfott.<ref>{{Cite journal \|last=Kearfott \|first=Baker \|date=1979-06-01 \|title=An efficient degree-computation method for a generalized method of bisection \|url=https://doi.org/10.1007/BF01404868 \|journal=Numerische Mathematik \|volume=32 \|issue=2 \|pages=109–127 \|doi=10.1007/BF01404868 \|s2cid=122058552 \|issn=0029-599X}}</ref> However, computing the topological degree can be time-consuming.

	A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.		A third criterion is based on a ''characteristic polyhedron''. This criterion is used by a method called Characteristic Bisection.<ref name=":0" />{{Rp\|page=19--}} It does not require computing the topological degree; it only requires computing the signs of function values. The number of required evaluations is at least <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron.<ref name=":2">{{Cite journal \|last1=Vrahatis \|first1=M. N. \|last2=Iordanidis \|first2=K. I. \|date=1986-03-01 \|title=A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations \|url=https://doi.org/10.1007/BF01389620 \|journal=Numerische Mathematik \|language=en \|volume=49 \|issue=2 \|pages=123–138 \|doi=10.1007/BF01389620 \|issn=0945-3245 \|s2cid=121771945}}</ref>{{Rp\|page=11\|location=Lemma.4.7}} Note that Vrahatis and Iordanidis <ref name=":2" /> prove a lower bound on the number of evaluations, and not an upper bound.

← Previous revision		Revision as of 07:53, 24 December 2024
Line 96:		Line 96:
	{{reflist}}		{{reflist}}
	== Further reading ==		== Further reading ==
			* Victor Yakovlevich Pan: "Solving a Polynomial Equation: Some History and Recent Progress", SIAM Review, Vol.39, No.2, pp.187-220 (June, 1997).
	* John Michael McNamee: ''Numerical Methods for Roots of Polynomials - Part I'', Elsevier, ISBN 978-0-444-52729-5 (2007).		* John Michael McNamee: ''Numerical Methods for Roots of Polynomials - Part I'', Elsevier, ISBN 978-0-444-52729-5 (2007).
	* John Michael McNamee and Victor Yakovlevich Pan: ''Numerical Methods for Roots of Polynomials - Part II'', Elsevier, ISBN 978-0-444-52730-1 (2013).		* John Michael McNamee and Victor Yakovlevich Pan: ''Numerical Methods for Roots of Polynomials - Part II'', Elsevier, ISBN 978-0-444-52730-1 (2013).