Root-finding algorithm: Difference between revisions

Revision as of 03:55, 29 April 2025

Latest revision as of 08:18, 15 July 2025

(2 intermediate revisions by 2 users not shown)

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.

=== 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 ==

Line 50 ⟶ 47:

:<math> x_{n+1}=x_n^2+2x_n-1 </math>, or

:<math> x_{n+1}=\pm \sqrt{1-x_n} </math>.

:< I Love You>

=== Inverse interpolation ===

Line 72 ⟶ 68:

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|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|url-access=subscription }}</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|url-access=subscription }}</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|url-access=subscription }}</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 fourth method uses an [[intermediate value theorem]] on simplices.<ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=2020-04-15 |title=Intermediate value theorem for simplices for simplicial approximation of fixed points and zeros |journal=Topology and Its Applications |language=en |volume=275 |pages=107036 |doi=10.1016/j.topol.2019.107036 |s2cid=213249321 |issn=0166-8641|doi-access=free }}</ref> Again, no upper bound on the number of queries is given.