next up previous
Next: Overview of Algorithms Up: `O' notation and Rates Previous: `O' notation and Rates

Rates of Convergence

In this course, we try to create sequences $ \{ x_k \} \subset \mathbb{R}^n$ that converge to some desired point $ x^*$ (most often a local minimizer). The fundamental question is how fast the convergence is.

Definition 3.1.1   $ Q$-linear convergence:
Assume $ \lim_{k \rightarrow \infty} x_k = x^*$. Convergence is $ Q$-linear if there exists a constant $ 0 < r < 1$ such that

$\displaystyle \frac{\vert x_{k+1} - x^*\Vert }{ \Vert x_k - x^*\Vert } \leq r. $

$ r$ is called the rate of convergence.

Example: $ x_k = \frac1{2^k}$. Note $ x_k \rightarrow 0 =: x^*$.
Then,

$\displaystyle \frac{ \Vert x_{k+1} - x^* }{ \vert x_k - x^* \vert } = \frac{ \frac1{2^{k+1}} }{ \frac1{2^k} } = \frac12 $

Hence, we have $ Q$-linear convergence with a convergence rate of $ \frac12$.

Definition 3.1.2   Superlinear convergence:
We say that the convergence of a sequence is $ Q$-superlinear if

$\displaystyle \frac{ \Vert x_{k+1} - x^* \Vert }{ \Vert x_k - x^* \Vert } \rightarrow 0 $

About $ Q$-linear convergence: It could be so bad that numerically we can barely see it; e.g.,

$\displaystyle x_k = 0.99999999^k $

Definition 3.1.3   $ Q$-quadratic Convergence:
We say that convergence is $ Q$-quadratic if

$\displaystyle \frac{ \Vert x_{k+1} - x^*\Vert }{ \Vert x_k - x^* \Vert^2 } \leq M $


Note: $ Q$-quadratic convergence implies $ Q$-superlinear convergence (to see this, multiply both sides of the equation by $ \Vert x_k - x^*\Vert$.

Definition 3.1.4   $ R$-linear Convergence $ \{ x_k \}$ converges to $ x^*$ $ R$-linearly if

$\displaystyle \Vert x_k - x^* \Vert \leq \sigma_k, $

and $ \{ \sigma_k \}$ converges $ Q$-linearly to 0.

We need $ R$-linear convergences for examples like the following:

$\displaystyle x_k = \begin{cases}1 + \frac1{2^k}, & k \text{ even } \\ 1, & k \text{ odd } \end{cases} $

Note that the quotients in the definition of $ Q$-linear convergence gets us in trouble. However,

$\displaystyle \Vert x_k - x^* \Vert \leq \frac1{2^k} =: \sigma_k. $

From our previous example, $ \sigma_k$ converges $ Q$-linearly.

Usually, we will just drop the $ Q$ in $ Q$-linear and say linear.

Friday, 1-28-2005


next up previous
Next: Overview of Algorithms Up: `O' notation and Rates Previous: `O' notation and Rates
Brian Bockelman 2005-06-09