Content deleted Content added
m Fixed grammar Tags: Mobile edit Mobile app edit iOS app edit |
Erel Segal (talk | contribs) |
||
Line 75:
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 }}</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 |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>{{Cite journal |last1=Mourrain |first1=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 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 |last=Vrahatis |first=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}}</ref>{{Rp|page=11|___location=Lemma.4.7}} Note that
A fourth method uses an intermediate-value theorem on simplices.<ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=2020 |editor-last=Sergeyev |editor-first=Yaroslav D. |editor2-last=Kvasov |editor2-first=Dmitri E. |title=Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions |url=https://link.springer.com/chapter/10.1007/978-3-030-40616-5_17 |journal=Numerical Computations: Theory and Algorithms |series=Lecture Notes in Computer Science |volume=11974 |language=en |___location=Cham |publisher=Springer International Publishing |pages=223–238 |doi=10.1007/978-3-030-40616-5_17 |isbn=978-3-030-40616-5|s2cid=211160947 }}</ref> Again, no upper bound on the number of queries is given.
== See also ==
| |||