Conjugate gradient squared method

From HandWiki
Short description: Algorithm for solving matrix-vector equations

In numerical linear algebra, the conjugate gradient squared method (CGS) is an iterative algorithm for solving systems of linear equations of the form [math]\displaystyle{ A{\bold x} = {\bold b} }[/math], particularly in cases where computing the transpose [math]\displaystyle{ A^T }[/math] is impractical.[1] The CGS method was developed as an improvement to the biconjugate gradient method.[2][3][4]

Background

A system of linear equations [math]\displaystyle{ A{\bold x} = {\bold b} }[/math] consists of a known matrix [math]\displaystyle{ A }[/math] and a known vector [math]\displaystyle{ {\bold b} }[/math]. To solve the system is to find the value of the unknown vector [math]\displaystyle{ {\bold x} }[/math].[3][5] A direct method for solving a system of linear equations is to take the inverse of the matrix [math]\displaystyle{ A }[/math], then calculate [math]\displaystyle{ \bold x = A^{-1}\bold b }[/math]. However, computing the inverse is computationally expensive. Hence, iterative methods are commonly used. Iterative methods begin with a guess [math]\displaystyle{ \bold x^{(0)} }[/math], and on each iteration the guess is improved. Once the difference between successive guesses is sufficiently small, the method has converged to a solution.[6][7]

As with the conjugate gradient method, biconjugate gradient method, and similar iterative methods for solving systems of linear equations, the CGS method can be used to find solutions to multi-variable optimisation problems, such as power-flow analysis, hyperparameter optimisation, and facial recognition.[8]

Algorithm

The algorithm is as follows:[9]

  1. Choose an initial guess [math]\displaystyle{ {\bold x}^{(0)} }[/math]
  2. Compute the residual [math]\displaystyle{ {\bold r}^{(0)} = {\bold b} - A{\bold x}^{(0)} }[/math]
  3. Choose [math]\displaystyle{ \tilde {\bold r}^{(0)} = {\bold r}^{(0)} }[/math]
  4. For [math]\displaystyle{ i = 1, 2, 3, \dots }[/math] do:
    1. [math]\displaystyle{ \rho^{(i-1)} = \tilde {\bold r}^{T(i-1)}{\bold r}^{(i-1)} }[/math]
    2. If [math]\displaystyle{ \rho^{(i-1)} = 0 }[/math], the method fails.
    3. If [math]\displaystyle{ i=1 }[/math]:
      1. [math]\displaystyle{ {\bold p}^{(1)} = {\bold u}^{(1)} = {\bold r}^{(0)} }[/math]
    4. Else:
      1. [math]\displaystyle{ \beta^{(i-1)} = \rho^{(i-1)}/\rho^{(i-2)} }[/math]
      2. [math]\displaystyle{ {\bold u}^{(i)} = {\bold r}^{(i-1)} + \beta_{i-1}{\bold q}^{(i-1)} }[/math]
      3. [math]\displaystyle{ {\bold p}^{(i)} = {\bold u}^{(i)} + \beta^{(i-1)}({\bold q}^{(i-1)} + \beta^{(i-1)}{\bold p}^{(i-1)}) }[/math]
    5. Solve [math]\displaystyle{ M\hat {\bold p}={\bold p}^{(i)} }[/math], where [math]\displaystyle{ M }[/math] is a pre-conditioner.
    6. [math]\displaystyle{ \hat {\bold v} = A\hat {\bold p} }[/math]
    7. [math]\displaystyle{ \alpha^{(i)} = \rho^{(i-1)} / \tilde {\bold r}^T \hat {\bold v} }[/math]
    8. [math]\displaystyle{ {\bold q}^{(i)} = {\bold u}^{(i)} - \alpha^{(i)}\hat {\bold v} }[/math]
    9. Solve [math]\displaystyle{ M\hat {\bold u} = {\bold u}^{(i)} + {\bold q}^{(i)} }[/math]
    10. [math]\displaystyle{ {\bold x}^{(i)} = {\bold x}^{(i-1)} + \alpha^{(i)} \hat {\bold u} }[/math]
    11. [math]\displaystyle{ \hat {\bold q} = A\hat {\bold u} }[/math]
    12. [math]\displaystyle{ {\bold r}^{(i)} = {\bold r}^{(i-1)} - \alpha^{(i)}\hat {\bold q} }[/math]
    13. Check for convergence: if there is convergence, end the loop and return the result

See also

References

  1. ↑ "Conjugate Gradient Squared Method". Wolfram Mathworld. https://mathworld.wolfram.com/ConjugateGradientSquaredMethod.html. 
  2. ↑ Mathworks. "cgs". https://au.mathworks.com/help/matlab/ref/cgs.html. 
  3. ↑ 3.0 3.1 Henk van der Vorst (2003). "Bi-Conjugate Gradients". Iterative Krylov Methods for Large Linear Systems. Cambridge University Press. ISBN 0-521-81828-1. 
  4. ↑ Peter Sonneveld (1989). "CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems". SIAM Journal on Scientific and Statistical Computing 10 (1): 36–52. doi:10.1137/0910004. ProQuest 921988114. https://www.proquest.com/docview/921988114. 
  5. ↑ "Linear equations", Matrix Analysis and Applied Linear Algebra, Philadelphia, PA: SIAM, pp. 1-40, doi:10.1137/1.9780898719512.ch1, http://www.matrixanalysis.com/Chapter1.pdf, retrieved 2023-12-18 
  6. ↑ "Iterative Methods for Linear Systems". Mathworks. https://au.mathworks.com/help/matlab/math/iterative-methods-for-linear-systems.html. 
  7. ↑ Jean Gallier. "Iterative Methods for Solving Linear Systems". UPenn. https://www.cis.upenn.edu/~cis5150/cis515-12-sl5.pdf. 
  8. ↑ "Conjugate gradient methods". Cornell University. https://optimization.cbe.cornell.edu/index.php?title=Conjugate_gradient_methods. 
  9. ↑ R. Barrett; M. Berry; T. F. Chan; J. Demmel; J. Donato; J. Dongarra; V. Eijkhout; R. Pozo et al. (1994). Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM. https://netlib.org/linalg/html_templates/Templates.html. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Conjugate_gradient_squared_method&oldid=3357632"