Jump to content

Biconjugate gradient method

From Wikipedia, the free encyclopedia

In mathematics, more specifically in numerical linear algebra, the biconjugate gradient method is an algorithm to solve systems of linear equations

Ax=b.

Unlike the conjugate gradient method, this algorithm does not require the matrix A to be self-adjoint, but instead one needs to perform multiplications by the conjugate transpose A*.

The Algorithm

[edit]
  1. Choose initial guess x0, two other vectors x0∗ and b∗ and a preconditioner M
  2. r0←b−Ax0
  3. r0∗←b∗−x0∗A∗
  4. p0←M−1r0
  5. p0∗←r0∗M−1
  6. for k=0,1,… do
    1. αk←rk∗M−1rkpk∗Apk
    2. xk+1←xk+αk⋅pk
    3. xk+1∗←xk∗+αk‾⋅pk∗
    4. rk+1←rk−αk⋅Apk
    5. rk+1∗←rk∗−αk‾⋅pk∗A∗
    6. βk←rk+1∗M−1rk+1rk∗M−1rk
    7. pk+1←M−1rk+1+βk⋅pk
    8. pk+1∗←rk+1∗M−1+βk‾⋅pk∗

In the above formulation, the computed rk and rk∗ satisfy

rk=b−Axk,
rk∗=b∗−xk∗A∗

and thus are the respective residuals corresponding to xk and xk∗, as approximate solutions to the systems

Ax=b,
x∗A∗=b∗;

x∗ is the adjoint, and α‾ is the complex conjugate.

Unpreconditioned version of the algorithm

[edit]
  1. Choose initial guess x0,
  2. r0←b−Ax0
  3. r̂0←b̂−x̂0A∗
  4. p0←r0
  5. p̂0←r̂0
  6. for k=0,1,… do
    1. αk←r̂krkp̂kApk
    2. xk+1←xk+αk⋅pk
    3. x̂k+1←x̂k+αk⋅p̂k
    4. rk+1←rk−αk⋅Apk
    5. r̂k+1←r̂k−αk⋅p̂kA∗
    6. βk←r̂k+1rk+1r̂krk
    7. pk+1←rk+1+βk⋅pk
    8. p̂k+1←r̂k+1+βk⋅p̂k

Discussion

[edit]

The biconjugate gradient method is numerically unstable[citation needed] (compare to the biconjugate gradient stabilized method), but very important from a theoretical point of view. Define the iteration steps by

xk:=xj+PkA−1(b−Axj),
xk∗:=xj∗+(b∗−xj∗A)PkA−1,

where j<k using the related projection

Pk:=𝐮k(𝐯k∗A𝐮k)−1𝐯k∗A,

with

𝐮k=[u0,u1,…,uk−1],
𝐯k=[v0,v1,…,vk−1].

These related projections may be iterated themselves as

Pk+1=Pk+(1−Pk)uk⊗vk∗A(1−Pk)vk∗A(1−Pk)uk.

A relation to Quasi-Newton methods is given by Pk=Ak−1A and xk+1=xk−Ak+1−1(Axk−b), where

Ak+1−1=Ak−1+(1−Ak−1A)uk⊗vk∗(1−AAk−1)vk∗A(1−Ak−1A)uk.

The new directions

pk=(1−Pk)uk,
pk∗=vk∗A(1−Pk)A−1

are then orthogonal to the residuals:

vi∗rk=pi∗rk=0,
rk∗uj=rk∗pj=0,

which themselves satisfy

rk=A(1−Pk)A−1rj,
rk∗=rj∗(1−Pk)

where i,j<k.

The biconjugate gradient method now makes a special choice and uses the setting

uk=M−1rk,
vk∗=rk∗M−1.

With this particular choice, explicit evaluations of Pk and A−1 are avoided, and the algorithm takes the form stated above.

Properties

[edit]
  • If A=A∗ is self-adjoint, x0∗=x0 and b∗=b, then rk=rk∗, pk=pk∗, and the conjugate gradient method produces the same sequence xk=xk∗ at half the computational cost.
  • The sequences produced by the algorithm are biorthogonal, i.e., pi∗Apj=ri∗M−1rj=0 for i≠j.
  • if Pj′ is a polynomial with deg⁡(Pj′)+j<k, then rk∗Pj′(M−1A)uj=0. The algorithm thus produces projections onto the Krylov subspace.
  • if Pi′ is a polynomial with i+deg⁡(Pi′)<k, then vi∗Pi′(AM−1)rk=0.

See also

[edit]

References

[edit]
  • Fletcher, R. (1976). "Conjugate gradient methods for indefinite systems". In Watson, G. Alistair (ed.). Numerical analysis : proceedings of the Dundee Conference on Numerical Analysis. Lecture Notes in Mathematics. Vol. 506. Springer. pp. 73–89. doi:10.1007/BFb0080116. ISBN 978-3-540-07610-0.
  • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 2.7.6". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Biconjugate_gradient_method&oldid=1318896101"