Finding the Zero: f(x)= F'(x)

Initial step f(a) f(b) <0

Methods:
bisection: no additional assumptions. x1= 1/2 (a+ b) + a, then x1 replaces either  a  or  b.
Convergence: reducing the interval: rate 2^N.
Negative: the values of functions are not count.

Newton method. Assume that f(x) is close to linear. Then f(x(k+1)) = f(xk) + f'(xk) (x(k+1) - xk)=0
and we obtain: x{k+1} = x{k} - f(x{k}/f'(x{k}).
f(x)= x^2- a then 1/2(x{k} + a/x{k})
Difficulty: iteration may diverge.

Secant method: f'(x{k} is rewplaced by (f{k} - f{k-1})/x{k} - x{k-1})
Pro: do not use derivative, use already computed function.
Negative: divergence.

Method of false position or "regula falsi"
Compute the sign f{k+1} f{k} and f{k} f{k-1}
Replace either x{k} or x{k-1} depending ofn the sign.
Convergence rate may be low Ex: f=-3 + x^(1/4).

Saveguarded algorithms:
Combination of bisectrion and Newton or Secand methods.
Use Newton or Secand, if the step is "reasonable":
x{k+1} in [a, b]
if the step is too large, relace it with bisection
If the step is too small, enlarge it to a fixed number delta.
 
 
 

Methods for one-dimensional search for optimum.

Optimal Fibonacci) search.
 

Golden mean as an asymptotics.
 

Gradient-based methods. "Suspicious points". Equivalence of the search for the null
of the function (derivative) and the search for extremum.
Gradient method. Choice of the length of the step.
Newton method.
Approximation method. (Secant method)
Modifications. Saveguard measures.

Global search.