‣

Bracketing Methods

Bracketing methods preserve two bounds, $x_a$ and $x_b$ though each iteration. These advantages include certain convergence and easy implementation. The disadvantages include generally slower runtimes, and the runtime’s dependence on the quality of the initial bracket.

Guess Selection

Bisection Method

The bisection method, splits the interval in two by, retaining the appropriate bounds to keep the sign change withing the bracket.

$$ x_c=\frac{x_a+x_b}2 $$

Incremental Method

The incremental method splits the interval into many segments, like the bisection method but with multiple cuts in a single iteration. It retains the appropriate bounds to keep the sign change within the bracket.

False Position Method

The false position method considers the secant through the current boundary values (i.e. the line passing through $(x_a,f_a)$ and $(x_b,f_b)$. It then selects the root of this line as the next guess, retaining the appropriate bounds to keep the sign change within the bracket.

$$ x_c=x_b-f_b\frac{x_a-x_b}{f_a-f_b} $$

Stopping Criteria

Bracketing root finding methods may be designed to stop when a satisfactorily small value is reached, $|f_c|<A$, if a minimum bracket size is reached, $x_b-x_a<B$, or when a the relative approximation is satisfactorily small, $\frac{\max(|x_c-x_a|,~|x_b-x_a|)}{|x_c|}<\varepsilon_a$.

Open Methods

Open methods make guesses on an open interval, though they may still depend on multiple previous values to make each guess. The advantages include fast runtimes. The disadvantages include the risk of very long runtime or error in the event of zero slopes of oscillatory guessing behavior.

Guess Selection Methods

Fixed Point Iteration

This is a general technique in which the root-finding problem is rearranged to render an iterative guessing technique. To be honest no examples were given so I don’t understand what this means.

$$ f(x)=0\Rarr x_i=g(x_{i-1}) $$