4
$\begingroup$

Consider linear equation $Au = f$.

We want to solve it with iterative method (assuming $A$ is good). First order iterative method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f), $$ The second degree method is: $$ u^{k+1} = u^k - \alpha_{k+1}(Au^k - f) - \beta(u^k - u^{k-1}). $$

For both methods we can define iteration parameters $\alpha_k$, $\beta_k$ via minimax problem which solution is Chebyshev polynomials.

This is good, but it seems to me, that convergence speed is the same for both cases and is $$ \|\varepsilon^{k}\| \leq \frac{2\sigma^k}{1+\sigma^{2k}}\|\varepsilon^{0}\|, $$
where $u - u^k = \varepsilon^{k}$ approximation error after the $k$-th iteration and $\sigma$ is constant dependent on operator spectrum.

The only idea I have, that first order iterations optimal for chosen $k$ for which coefficients are computed, while second-order iteration is optimal on every step.

I would greatly appreciate any work on this to clear-up those details.

$\endgroup$

2 Answers 2

1
$\begingroup$

Late to the party by 7 years but here goes. This is easiest to analyze in the case where $A$ is symmetric and positive-definite. What you're describing is the difference between using the steepest descent method and the conjugate gradient method and the convergence rate is very different between the two methods. The steepest descent method has a convergence rate bounded by $$\rho_{\text{SD}} = \frac{1 - \kappa(A)}{1 + \kappa(A)}$$ where $\kappa(A) = \|A\|\cdot\|A^{-1}\|$ is the condition number of the matrix. The conjugate gradient method, on the other hand, has a convergence rate that is bounded by $$\rho_{\text{CG}} = \frac{1 - \sqrt{\kappa(A)}}{1 + \sqrt{\kappa(A)}}$$ which is much more favorable. This bound comes from the realization that the conjugate gradient method minimizes the $\|\cdot\|_A$-norm of the error over the Krylov subspace at each iteration, which you can then connect to the norm of polynomials on the spectrum of $A$ and finally to Chebyshev polynomials. The story is essentially the same if we use some preconditioning matrix $M$, only you replace $A$ by $M^{-1}A$ in the formulas above.

The simplest derivation that I know of CG, although incomplete in some respects, is from the book Control Perspectives on Numerical Algorithms by Bhaya and Kaszkurewicz. They consider the steepest descent method to be analogous to a proportional feedback controller with $\{\alpha_k\}$ as the controls. You can then think of the CG algorithm as using proportional-derivative feedback control with both $\{\alpha_k\}$ and $\{\beta_k\}$ as the controls. The critical question is what you use as a control-Lyapunov function. Granted this is only part of the story -- there's the whole Lanczos / Chebyshev polynomial side of things, for which you can consult Greenbaum or Saad.

For symmetric but indefinite problems, e.g. from saddle-point problems, there is still an algorithm with a 3-term recurrence (MINRES). For general matrices, methods relying on a 3-term recurrence don't work nearly as well and the usual recourse is to methods like GMRES.

$\endgroup$
1
  • $\begingroup$ Thank you! I forgot why I even asked this, but your replay is very informative! $\endgroup$
    – Moonwalker
    Dec 6, 2023 at 19:17
0
$\begingroup$

I think that the difference between the two method isn't the degree, however the first method is a one-step method while the second one is a two-step method; therefor the convergence speed can be similar or the same; the choice depend by the advantage required.

$\endgroup$
2
  • $\begingroup$ What kind of advantage the two step method has? It has the same convergence speed and I cannot see any other difference. $\endgroup$
    – Moonwalker
    Aug 7, 2016 at 22:20
  • 1
    $\begingroup$ You have to study the stability of these method to find the differences. In numerical analysis of ode and pde they are often used es. link. $\endgroup$
    – user96954
    Aug 9, 2016 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.