Understanding the "rate of convergence" for iterative methods

Question

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$.

Answer 1

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).

Answer 2

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$.)

For example, for first order methods in optimization you often observe an initially fast decrease in error, which then levels out. For Newton's method on the other hand, it can take a while before superlinear (or quadratic) convergence kicks in (it's only locally superlinearly convergent after all). For that reason, it is common to either start with a few gradient steps to get going before switching to a Newton method, or use homotopy or quasi-Newton methods which behave as first order methods initially and turn into a Newton method as you approach the target.

Answer 3

The interpretation is qualitatively correct.

Note that linear and quadratic convergence are with respect to the worst case, the situation in a particular algorithm can be better than what you get from the worst case analysis given by Wolfgang Bangerth, though the qualitative situation usually corresponds to this analysis.

In concrete algorithms (e.g., in optimization) it makes often sense to first iterate with a cheap but only linearly convergent method until progress gets slow, and then finish with a quadratically (or at least superlinearly) convergent method. In practice, superlinear convergence tends to be as good as quadratic convergence just because the initial, slowly converging part tends to dominate the overall work.