Conjugate gradient squared method: Difference between revisions

Revision as of 22:58, 10 April 2024

Revision as of 21:54, 19 September 2024

Line 4:

== Background ==

A [[system of linear equations]] <math>A{\bold x} = {\bold b}</math> consists of a known [[Matrix (mathematics)|matrix]] <math>A</math> and a known [[Vector (mathematics)|vector]] <math>{\bold b}</math>. To solve the system is to find the value of the unknown vector <math>{\bold x}</math>.<ref name="vorst03" /><ref>{{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 |chapter-url=http://www.matrixanalysis.com/Chapter1.pdf |place= Philadelphia, PA |publisher=SIAM |doi=10.1137/1.9780898719512.ch1 |doi-broken-date=31 January 2024-09-19|archive-date=2004-06-10 }}</ref> A direct method for solving a system of linear equations is to take the inverse of the matrix <math>A</math>, then calculate <math>\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>\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.<ref>{{cite web|title=Iterative Methods for Linear Systems|publisher=[[Mathworks]]|url=https://au.mathworks.com/help/matlab/math/iterative-methods-for-linear-systems.html}}</ref><ref>{{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}}</ref>

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 study|power-flow analysis]], [[hyperparameter optimisation]], and [[facial recognition system|facial recognition]].<ref>{{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}}</ref>