# Understanding the “rate of convergence” for iterative methods

According to Wikipedia the rate of convergence is expressed as a specific ratio of vector norms. I'm trying to understand the difference between "linear" and "quadratic" rates, at different points of time (basically, "at the beginning" of the iteration, and "at the end"). Could it be stated that:

• with linear convergence, the norm of the error $e_{k+1}$ of the iterate $x_{k+1}$ is bounded by $\|e_k\|$

• with quadratic convergence, the norm of the error $e_{k+1}$ of the iterate $x_{k+1}$ is bounded by $\|e_k\|^2$

Such interpretation would mean that, with a few (small number of) iterates of linearly convergent algorithm A1 (random initialization assumed), smaller error would be achieved that with a few iterates of quadraticaly convergent algorithm A2. However, since the error diminishes, and due to squaring, later iterates would mean smaller error with A2.

Is the above interpretation valid? Note that it disregards the rate coefficient $\lambda$.

• It is also possible that your quadratically converging algorithm starts with a larger error than your linearly converging algorithm, which can make your A1 algorithm more "accurate" for a given number of iterations... – FrenchKheldar Nov 28 '12 at 22:07

In practice, yes. While $e_k$ is still large, the rate coefficient $\lambda$ will dominate the error rather than the q-rate. (Note that these are asymptotic rates, so the statements you linked to only hold for the limit as $k\to\infty$.)
In addition to Christian's answer, it's also worth noting that for linear convergence you have $e_{k+1} \le \lambda_1 e_k$ where you have $\lambda_1<1$ if the method converges. On the other hand, for quadratic convergence you have $e_{k+1} \le \lambda_2 e_k^2$ and the fact that a method converges does not necessarily imply that $\lambda_2$ must be smaller than one. Rather, the condition for convergence is that $\lambda_2 e_1<1$ -- i.e., that your starting guess is close enough. This is commonly observed behavior: that quadratically convergent algorithms need to be started "close enough" from the solution to converge whereas linearly convergent algorithms are typically more robust. This is another reason why one often starts with a few steps of a linearly convergence algorithm (e.g., the steepest descent method) before switching to more efficient ones (e.g., Newton's method).