Conjugate gradient squared method

A system of linear equations $A\{\backslash bold\; x\}\; =\; \{\backslash bold\; b\}$ consists of a known matrix $A$ and a known vector $\{\backslash bold\; b\}$. To solve the system is to find the value of the unknown vector $\{\backslash bold\; x\}$.{{Citation |title=Matrix Analysis and Applied Linear Algebra |pages=1–40 |access-date=2023-12-18 |archive-url=https://web.archive.org/web/20040610221137/http://www.matrixanalysis.com/Chapter1.pdf |chapter=Linear equations |date=2000 |chapter-url=http://www.matrixanalysis.com/Chapter1.pdf |place= Philadelphia, PA |publisher=SIAM |doi=10.1137/1.9780898719512.ch1 |doi-broken-date=1 November 2024|isbn=978-0-89871-454-8 |archive-date=2004-06-10 }} A direct method for solving a system of linear equations is to take the inverse of the matrix $A$, then calculate $\backslash bold\; x\; =\; A^\{-1\}\backslash bold\; b$. However, computing the inverse is computationally expensive. Hence, iterative methods are commonly used. Iterative methods begin with a guess $\backslash bold\; x^\{(0)\}$, and on each iteration the guess is improved. Once the difference between successive guesses is sufficiently small, the method has converged to a solution.{{cite web|title=Iterative Methods for Linear Systems|publisher=Mathworks|url=https://au.mathworks.com/help/matlab/math/iterative-methods-for-linear-systems.html}}{{cite web|title=Iterative Methods for Solving Linear Systems|author=Jean Gallier|publisher=UPenn|url=https://www.cis.upenn.edu/~cis5150/cis515-12-sl5.pdf}}

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.{{cite web|title=Conjugate gradient methods|author1=Alexandra Roberts|author2=Anye Shi|author3=Yue Sun|access-date=2023-12-26|publisher=Cornell University|url=https://optimization.cbe.cornell.edu/index.php?title=Conjugate_gradient_methods}}

The algorithm is as follows:{{cite book|author1=R. Barrett|author2=M. Berry|author3=T. F. Chan|author4=J. Demmel|author5=J. Donato|author6=J. Dongarra|author7=V. Eijkhout|author8=R. Pozo|author9=C. Romine|author10=H. Van der Vorst|title=Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition|publisher=SIAM|year=1994|url=https://netlib.org/linalg/html_templates/Templates.html}}

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

• Biconjugate gradient method
• Biconjugate gradient stabilized method
• Generalized minimal residual method

{{Reflist}}

Category:Numerical linear algebra

Category:Gradient methods