Root-finding algorithm

Builds on Continuous function Real sequence Limit of a sequence Rate of convergence

Definition

Let $D \subseteq \R^n$ and let $f \colon D \to \R^n$ be a continuous function; the case $n = 1$ is the most common, and $\C$ may replace $\R$ . A zero (or root) of $f$ is a point $r \in D$ with $f(r) = 0$ . A root-finding algorithm is a procedure that takes $f$ and starting data. It produces a sequence $(x_k)$ in $D$ , or a sequence of nested sets containing a zero. It uses $f$ only through values of $f$ and possibly of its derivatives. It is designed so that $(x_k)$ has a zero of $f$ as its limit, or so that the sets shrink to a zero.

Remarks

Example: the iteration $x_{k+1} = x_k - (x_k^2 - 2)/(2x_k)$ from $x_0 = 1$ gives $1, 1.5, 1.41667, 1.414216, \ldots$ , which tends to the zero $\sqrt{2}$ of $f(x) = x^2 - 2$ . Non-example: the iteration $x_{k+1} = 2/x_k$ from $x_0 = 1$ oscillates between $1$ and $2$ , so it does not tend to a zero of $x^2 - 2$ , although $\sqrt{2}$ is its fixed point. An algorithm is globally convergent on a class of functions if it converges from every admissible start, and locally convergent if it converges from starts close enough to a zero. Its speed is measured by its order of convergence, see rate of convergence.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`8JYC7S28JX`
URI	`m2://8JYC7S28JX`
Kind	definition
Writing	W0 stub
MSC	65H05, 65H04
Defines	Root-finding algorithm
Uses	Continuous function, Real sequence, Limit of a sequence, Rate of convergence

Root-finding algorithm

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here