Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 77:
Another criterion is given by a theorem of Kronecker.<ref>{{Cite web |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 |language=EN |doi=10.5555/335947}}</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 by 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 |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 |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>{{Cite journal |last=Mourrain |first=B. |last2=Vrahatis |first2=M. N. |last3=Yakoubsohn |first3=J. C. |date=2002-06-01 |title=On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree |url=https://www.sciencedirect.com/science/article/pii/S0885064X01906363 |journal=Journal of Complexity |language=en |volume=18 |issue=2 |pages=612–640 |doi=10.1006/jcom.2001.0636 |issn=0885-064X}}</ref>{{Rp|page=19--}} It does not require to compute the topological degree - it only requires to compute the signs of function values. The number of required evaluations is <math>\log_2(D/\epsilon)</math>, where ''D'' is the length of the longest edge of the characteristic polyhedron. Note that this number does not depend on the dimension.
== See also ==
| |||