Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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

share|improve this question
1  
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

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.