Root-finding algorithm: Difference between revisions

Revision as of 20:45, 10 October 2024

Revision as of 20:09, 5 November 2024

Line 36:

=== Secant method ===

Replacing the derivative in Newton's method with a [[finite difference]], we get the [[secant method]]. This method does not require the computation (nor the existence) of a derivative, but the price is slower convergence (the order of convergence is the [[golden ratio]], approximately 1.62<ref>{{Cite web |last=Chanson |first=Jeffrey R. |date=October 3, 2024 |title=Order of Convergence |url=https://math.libretexts.org/Bookshelves/Applied_Mathematics/Numerical_Methods_(Chasnov)/02%3A_Root_Finding/2.04%3A_Order_of_Convergence |url-status=live |access-date=October 3, 2024 |website=LibreTexts Mathematics}}</ref>). A generalization of the secant method in higher dimensions is [[Broyden's method]].

=== Steffensen's method ===

Line 75:

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 <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 |url=https://www.sciencedirect.com/science/article/pii/S0166864119304420 |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.

== See also ==