Solving Nonlinear Equations
Consider a system of nonlinear equations: $f(x) = 0$, $f \in C(\mathbb{R}^n, \mathbb{R}^m)$. Root of zero $\zeta$ of this system is a point that satisfies the equations: $\zeta \in \mathbb{R}^n$, $f(\zeta) = 0$. Multiplicity or order of a zero of this system is the least order of derivative of the function at this zero that is nonsingular: $n = \min\{k \in \mathbb{N}_+ : \forall v \in \mathbb{R}^n \setminus \{0\}, (D^k f)_\zeta (v)_{i \in k} \ne 0 \}$. Simple zero is a zero of multiplicity one. Double zero is a zero of multiplicity two. Multiple zero is a zero of multiplicity at least two.
Figure: Orders of convergence.
Iterative complexity of an iterative method can be characterized effectively by two numbers: order of convergence and rate of convergence. Sublinear convergence of a convergent sequence in a normed space is one such that: $\lim_{n \to \infty} \frac{\|x_{n+1} - \zeta\|}{\|x_n - \zeta\|} = 1$. Typical examples of sublinear convergence are logarithmic rates (sometimes called polynomial rates): $\exists r > 0$, $x_n = \mathcal{O}(n^{-r})$. Linear convergence (sometimes called exponential convergence) of a sequence in a normed space is one such that: $\exists \mu \in (0, 1)$, $\lim_{n \to \infty} \frac{\|x_{n+1} - \zeta\|}{\|x_n - \zeta\|} = \mu$. This type of convergence is called linear because on a plot of iteration versus log relative error the decline would tend to a linear rate. Asymptotic rate of convergence $\rho$ of a linearly convergent sequence is: $\rho = - \log \mu$; this is defined such that $\|x_n - \zeta\| = \mathcal{O}(e^{-\rho n}) \|x_0 - \zeta\|$ and the rate is the absolute slope of decline in a log plot. Asymptotic order of convergence $p$ of a superlinearly convergent sequence in a normed space is a real number such that: $p \in (1, \infty)$, $\exists \mu > 0$, $\lim_{n \to \infty} \frac{\|x_{n+1} - \zeta\|}{\|x_n - \zeta\|^p} = \mu$. Note that order of convergence need not be an interger. Quadratic convergence of a sequence is one whose order of convergence equals two: $p = 2$. Note that for a quadratically convergent sequence: $\|x_n - \zeta\| = \mathcal{O}(e^{-\rho e^n}) \|x_0 - \zeta\|$, with an exponential decline in a log plot.
Methods for root finding:
- bisection method;
- fixed point method, relaxation, Aitken's method;
- secant method (chord method);
- Newton's method (aka method of tangents);