Conjugate gradient squared method: Difference between revisions

Revision as of 03:17, 5 November 2023

Revision as of 03:20, 5 November 2023

Line 9:

{{AfC topic|stem}}

In [[numerical linear algebra]], the '''conjugate gradient squared method (CGS)''' is an [[iterative method|iterative]] algorithm for solving [[systems of linear equations]] of the form <math>AxA{\bold x} = {\bold b}</math>, particularly in cases where computing the [[transpose]] <math>A^T</math> is impractical.<ref>{{cite web|title=Conjugate Gradient Squared Method|author1=Noel Black|author2=Shirley Moore|publisher=[[MathWorld|Wolfram Mathworld]]|url=https://mathworld.wolfram.com/ConjugateGradientSquaredMethod.html}}</ref> The CGS method was developed as an improvement to the [[Biconjugate gradient method]].<ref>{{cite web|title=cgs|author=Mathworks|url=https://au.mathworks.com/help/matlab/ref/cgs.html}}</ref><ref>{{cite book|author=[[Henk van der Vorst]]|title=Iterative Krylov Methods for Large Linear Systems|chapter=Bi-Conjugate Gradients|year=2003|publisher=Cambridge University Press |isbn=0-521-81828-1}}</ref><ref>{{cite journal|title=CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems|author=Peter Sonneveld|journal=SIAM Journal on Scientific and Statistical Computing|volume=10|issue=1|pages=36–52|date=1989|url=https://www.proquest.com/docview/921988114|url-access=limited|doi=10.1137/0910004|id={{ProQuest|921988114}} }}</ref>

As with other methods for solving matrix-vector equations, the CGS method can be used to solve optimisation problems, such as power-flow analysis.

== Background ==

A system of linear equations <math>AxA{\bold x} = {\bold b}</math> consists of a known [[Matrix (mathematics)|matrix]] <math>A</math> and a known vector <math>{\bold b}</math>. To solve the system is to find the value of the unknown vector <math>{\bold x}</math>.

== The Algorithm ==

Line 20:

The algorithm is as follows:<ref>{{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}}</ref>

# Choose an initial guess <math>x_0{\bold x}_0</math>

# <math>r_0 = b - Ax_0A{\bold x}_0</math>

# Choose <math>\tilde r_0 = r_0</math>

# For <math>i = 1, 2, 3, \dots</math> do:

Line 37:

## <math>q_i = u_i - \alpha_i\hat v</math>

## Solve <math>M\hat u = u_i + q_i</math>

## <math>x_i{\bold x}_i = x_{\bold x}_{i-1} + \alpha_i \hat u</math>

## <math>\hat q = A\hat u</math>

## <math>r_i = r_{i-1} - \alpha_i\hat q</math>