ITP method

Given a continuous function $f$ defined from $[a,b]$ to $\backslash mathbb\{R\}$ such that $f(a)f(b)\backslash leq\; 0$, where at the cost of one query one can access the values of $f(x)$ on any given $x$. And, given a pre-specified target precision $\backslash epsilon>0$, a root-finding algorithm is designed to solve the following problem with the least amount of queries as possible:

Problem Definition: Find $\backslash hat\{x\}$ such that $|\backslash hat\{x\}-x^*|\backslash leq\; \backslash epsilon$, where $x^*$ satisfies $f(x^*)\; =\; 0$.

This problem is very common in numerical analysis, computer science and engineering; and, root-finding algorithms are the standard approach to solve it. Often, the root-finding procedure is called by more complex parent algorithms within a larger context, and, for this reason solving root problems efficiently is of extreme importance since an inefficient approach might come at a high computational cost when the larger context is taken into account. This is what the ITP method attempts to do by simultaneously exploiting interpolation guarantees as well as minmax optimal guarantees of the bisection method that terminates in at most $n\_\{1/2\}\backslash equiv\backslash lceil\backslash log\_2((b\_0-a\_0)/2\backslash epsilon)\backslash rceil$ iterations when initiated on an interval $[a\_0,b\_0]$.

Given $\backslash kappa\_1\backslash in\; (0,\backslash infty),\; \backslash kappa\_2\; \backslash in\; \backslash left[1,1+\backslash phi\backslash right)$, $n\_\{1/2\}\; \backslash equiv\; \backslash lceil\backslash log\_2((b\_0-a\_0)/2\backslash epsilon)\backslash rceil$ and $n\_0\backslash in[0,\backslash infty)$ where $\backslash phi$ is the golden ratio $\backslash tfrac\{1\}\{2\}(1+\backslash sqrt\{5\})$, in each iteration $j\; =\; 0,1,2\backslash dots$ the ITP method calculates the point $x\_\{\backslash text\{ITP\}\}$ following three steps:

File:ITPstep1.png

File:ITPstep2.png

File:ITPstep3.png

File:ITPall steps.png

1. [Interpolation Step] Calculate the bisection and the regula falsi points: $x\_\{1/2\}\; \backslash equiv\; \backslash frac\{a+b\}\{2\}$ and $x\_f\; \backslash equiv\; \backslash frac\{bf(a)-af(b)\}\{f(a)-f(b)\}$ ;
2. [Truncation Step] Perturb the estimator towards the center: $x\_t\; \backslash equiv\; x\_f+\backslash sigma\; \backslash delta$ where $\backslash sigma\; \backslash equiv\; \backslash text\{sign\}(x\_\{1/2\}-x\_f)$ and $\backslash delta\; \backslash equiv\; \backslash min\backslash \{\backslash kappa\_1|b-a|^\{\backslash kappa\_2\},|x\_\{1/2\}-x\_f|\backslash \}$ ;
3. [Projection Step] Project the estimator to minmax interval: $x\_\{\backslash text\{ITP\}\}\; \backslash equiv\; x\_\{1/2\}\; -\backslash sigma\; \backslash rho\_k$ where $\backslash rho\_k\; \backslash equiv\; \backslash min\backslash left\backslash \{\backslash epsilon\; 2^\{n\_\{1/2\}+n\_0-j\}\; -\; \backslash frac\{b-a\}\{2\},|x\_t-x\_\{1/2\}|\backslash right\backslash \}$.

The value of the function $f(x\_\{\backslash text\{ITP\}\})$ on this point is queried, and the interval is then reduced to bracket the root by keeping the sub-interval with function values of opposite sign on each end.

The following algorithm (written in pseudocode) assumes the initial values of $y\_a$ and $y\_b$ are given and satisfy

Input: $a,\; b,\; \backslash epsilon,\; \backslash kappa\_1,\; \backslash kappa\_2,\; n\_0,\; f$

Preprocessing: $n\_\{1/2\}\; =\; \backslash lceil\; \backslash log\_2\backslash tfrac\{b-a\}\{2\backslash epsilon\}\backslash rceil$, $n\_\{\backslash max\}\; =\; n\_\{1/2\}+n\_0$, and $j\; =\; 0$;

While ( $b-a>2\backslash epsilon$ )

Calculating Parameters:

$x\_\{1/2\}\; =\; \backslash tfrac\{a+b\}\{2\}$, $r\; =\; \backslash epsilon\; 2^\{n\_\{\backslash max\}\; -\; j\}-(b-a)/2$, $\backslash delta\; =\; \backslash kappa\_1(b-a)^\{\backslash kappa\_2\}$;

Interpolation:

$x\_f\; =\; \backslash tfrac\{y\_ba-y\_a\; b\}\{y\_b-y\_a\}$;

Truncation:

$\backslash sigma\; =\; \backslash text\{sign\}(x\_\{1/2\}-x\_f)$;

If $\backslash delta\backslash leq|x\_\{1/2\}-x\_f|$ then $x\_t\; =\; x\_f+\backslash sigma\; \backslash delta$,

Else $x\_t\; =\; x\_\{1/2\}$;

Projection:

If $|x\_t-x\_\{1/2\}|\backslash leq\; r$ then $x\_\{\backslash text\{ITP\}\}\; =\; x\_t$,

Else $x\_\{\backslash text\{ITP\}\}\; =\; x\_\{1/2\}-\backslash sigma\; r$;

Updating Interval:

$y\_\{\backslash text\{ITP\}\}\; =\; f(x\_\{\backslash text\{ITP\}\})$;

If $y\_\{\backslash text\{ITP\}\}>0$ then $b\; =\; x\_\{ITP\}$ and $y\_b\; =\; y\_\{\backslash text\{ITP\}\}$,

Elseif then $a\; =\; x\_\{\backslash text\{ITP\}\}$ and $y\_a\; =\; y\_\{\backslash text\{ITP\}\}$,

Else $a\; =\; x\_\{\backslash text\{ITP\}\}$ and $b\; =\; x\_\{\backslash text\{ITP\}\}$;

$j\; =\; j+1$;

Output: $\backslash hat\{x\}\; =\; \backslash tfrac\{a+b\}\{2\}$

Suppose that the ITP method is used to find a root of the polynomial $f(x)\; =\; x^3\; -\; x\; -\; 2\; \backslash ,.$ Using $\backslash epsilon\; =\; 0.0005,\; \backslash kappa\_1\; =\; 0.1,\; \backslash kappa\_2\; =\; 2$ and $n\_0\; =\; 1$ we find that:

This example can be compared to {{section link|Bisection method|Example: Finding the root of a polynomial}}. The ITP method required less than half the number of iterations than the bisection to obtain a more precise estimate of the root with no cost on the minmax guarantees. Other methods might also attain a similar speed of convergence (such as Ridders, Brent etc.) but without the minmax guarantees given by the ITP method.

The main advantage of the ITP method is that it is guaranteed to require no more iterations than the bisection method when $n\_0\; =\; 0$. And so its average performance is guaranteed to be better than the bisection method even when interpolation fails. Furthermore, if interpolations do not fail (smooth functions), then it is guaranteed to enjoy the high order of convergence as interpolation based methods.

Because the ITP method projects the estimator onto the minmax interval with a $n\_0$ slack, it will require at most $n\_\{1/2\}+n\_0$ iterations (Theorem 2.1 of ). This is minmax optimal like the bisection method when $n\_0$ is chosen to be $n\_0\; =\; 0$.

Because it does not take more than $n\_\{1/2\}+n\_0$ iterations, the average number of iterations will always be less than that of the bisection method for any distribution considered when $n\_0\; =\; 0$ (Corollary 2.2 of ).

If the function $f(x)$ is twice differentiable and the root $x^*$ is simple, then the intervals produced by the ITP method converges to 0 with an order of convergence of $\backslash sqrt\{\backslash kappa\_2\}$ if $n\_0\; \backslash neq\; 0$ or if $n\_0\; =\; 0$ and $(b-a)/\backslash epsilon$ is not a power of 2 with the term $\backslash tfrac\{\backslash epsilon\; 2^\{n\_\{1/2\}\}\}\{b-a\}$ not too close to zero (Theorem 2.3 of ).

• The itp{{Citation | last= Northrop | first= P. J. | title= itp: The Interpolate, Truncate, Project (ITP) Root-Finding Algorithm | year= 2023 | url= https://CRAN.R-project.org/package=itp}} contributed package in R.

• Bisection method
• Ridders' method
• Regula falsi
• Brent's method

{{notelist}}

{{Reflist}}

• [https://link.growkudos.com/1iwxps83474 An Improved Bisection Method], by [https://info.growkudos.com/ Kudos]

{{root-finding algorithms}}

Category:Root-finding algorithms