itp: The Interpolate, Truncate, Project (ITP) Root-Finding Algorithm version 1.2.1

itp 1.2.1

Bug fixes and minor improvements

• The issue described at RcppCore/Rcpp#1287 has been fixed to avoid WARNINGs from CRAN checks on some platforms. Thank you to Dirk Eddelbuettel for providing the fix so quickly!

itp: The Interpolate, Truncate, Project (ITP) Root-Finding Algorithm version 1.2.0

itp 1.2.0

New features

• The function itp_c, which implements the ITP algorithm entirely in C++.

itp: The Interpolate, Truncate, Project (ITP) Root-Finding Algorithm version 1.1.0

itp 1.1.0

New features

• The argument f to the function itp() can now be either an R function or an external pointer to a C++ function. In the latter case, itp() makes use of the Passing user-supplied C++ functions framework offered by the Rcpp package. For the simple examples given in the itp package only a modest improvement in speed is observed (and expected). However, being able to call itp() on the C++ side may have benefits in more challenging problems.
• The package vignette and README file include examples based on external pointers to a C++ function.
• A plot method is provided, which plots the function f provided to itp over the input interval (a, b).

Bug fixes and minor improvements

• Explicit examples of passing arguments to the input function f have been added.

itp: The Interpolate, Truncate, Project (ITP) Root-Finding Algorithm version 1.0.1

itp 1.0.1

Bug fixes and minor improvements

• A bug in the part of itp() in which the bracketing interval has been fixed. It caused incorrect results in cases where the function is locally decreasing.
• Tests have been added to check the correction of this bug.

itp: The Interpolate, Truncate, Project (ITP) Root-Finding Algorithm version 1.0.0

itp

The Interpolate, Truncate, Project (ITP) root-finding algorithm

The itp package implements the Interpolate, Truncate, Project (ITP) root-finding algorithm of Oliveira and Takahashi (2021). Each iteration of the algorithm results in a bracketing interval for the root that is narrower than the previous interval. It’s performance compares favourably with existing methods on both well-behaved functions and ill-behaved functions while retaining the worst-case reliability of the bisection method. For details see the authors’ Kudos summary and the Wikipedia article ITP method.

Examples

We use three examples from Section 3 of Oliveira and Takahashi (2021) to illustrate the use of the itp function. Each of these functions has a root in the interval .

library(itp)

A continuous function

The Lambert function is continuous.

The itp function finds an estimate of the root, that is, for which is (approximately) equal to 0. The algorithm continues until the length of the interval that brackets the root is smaller than , where is a user-supplied tolerance. The default is .

# Lambert
lambert <- function(x) x * exp(x) - 1
itp(lambert, c(-1, 1))
#>       root     f(root)  iterations  
#>     0.5671   2.048e-12           8

A discontinuous function

The staircase function is discontinuous.

The itp function finds the discontinuity at at which the sign of the function changes. The value of 0.5 returned for the root res$root is the midpoint of the bracketing interval [res$a, res$b] at convergence.

# Staircase
staircase <- function(x) ceiling(10 * x - 1) + 1 / 2
res <- itp(staircase, c(-1, 1))
print(res, all = TRUE)
#>       root     f(root)  iterations           a           b         f.a  
#>  7.404e-11         0.5          31           0   1.481e-10        -0.5  
#>        f.b   precision  
#>        0.5   7.404e-11

A function with multiple roots

The Warsaw function has multiple roots.

When the initial interval is the itp function finds the root . There are other roots that could be found from different initial values.

# Warsaw
warsaw <- function(x) ifelse(x > -1, sin(1 / (x + 1)), -1)
itp(warsaw, c(-1, 1))
#>       root     f(root)  iterations  
#>    -0.6817  -5.472e-11          11

Installation

To get the current released version from CRAN:

install.packages("itp")

Vignette

See vignette("itp-vignette", package = "itp") for an overview of the
package.