ITP method

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: "ITP method" – news · newspapers · books · scholar · JSTOR (November 2024) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "ITP method" – news · newspapers · books · scholar · JSTOR (January 2021) (Learn how and when to remove this message) The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "ITP method" – news · newspapers · books · scholar · JSTOR (May 2024) (Learn how and when to remove this message) (Learn how and when to remove this message)

In numerical analysis, the ITP method, short for Interpolate Truncate and Project, is the first root-finding algorithm that achieves the superlinear convergence of the secant method^[1] while retaining the optimal^[2] worst-case performance of the bisection method.^[3] It is also the first method with guaranteed average performance strictly better than the bisection method under any continuous distribution.^[3] In practice it performs better than traditional interpolation and hybrid based strategies (Brent's Method, Ridders, Illinois), since it not only converges super-linearly over well behaved functions but also guarantees fast performance under ill-behaved functions where interpolations fail.^[3]

The ITP method follows the same structure of standard bracketing strategies that keeps track of upper and lower bounds for the location of the root; but it also keeps track of the region where worst-case performance is kept upper-bounded. As a bracketing strategy, in each iteration the ITP queries the value of the function on one point and discards the part of the interval between two points where the function value shares the same sign. The queried point is calculated with three steps: it interpolates finding the regula falsi estimate, then it perturbes/truncates the estimate (similar to Regula falsi § Improvements in regula falsi) and then projects the perturbed estimate onto an interval in the neighbourhood of the bisection midpoint. The neighbourhood around the bisection point is calculated in each iteration in order to guarantee minmax optimality (Theorem 2.1 of ^[3]). The method depends on three hyper-parameters ${\displaystyle \kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)}$ and ${\displaystyle n_{0}\in [0,\infty )}$ where ${\displaystyle \phi }$ is the golden ratio ${\displaystyle {\tfrac {1}{2}}(1+{\sqrt {5}})}$: the first two control the size of the truncation and the third is a slack variable that controls the size of the interval for the projection step.^[a]

Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).