Biconjugate gradient method

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

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

The Algorithm

edit
  1. Choose initial guess  , two other vectors   and   and a preconditioner  
  2.  
  3.  
  4.  
  5.  
  6. for   do
    1.  
    2.  
    3.  
    4.  
    5.  
    6.  
    7.  
    8.  

In the above formulation, the computed   and   satisfy

 
 

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

 
 

  is the adjoint, and   is the complex conjugate.

Unpreconditioned version of the algorithm

edit
  1. Choose initial guess  ,
  2.  
  3.  
  4.  
  5.  
  6. for   do
    1.  
    2.  
    3.  
    4.  
    5.  
    6.  
    7.  
    8.  

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

 
 

where   using the related projection

 

with

 
 

These related projections may be iterated themselves as

 

A relation to Quasi-Newton methods is given by   and  , where

 

The new directions

 
 

are then orthogonal to the residuals:

 
 

which themselves satisfy

 
 

where  .

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

 
 

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

Properties

edit
  • If   is self-adjoint,   and  , then  ,  , and the conjugate gradient method produces the same sequence   at half the computational cost.
  • The sequences produced by the algorithm are biorthogonal, i.e.,   for  .
  • if   is a polynomial with  , then  . The algorithm thus produces projections onto the Krylov subspace.
  • if   is a polynomial with  , then  .

See also

edit

References

edit
  • Fletcher, R. (1976). Watson, G. Alistair (ed.). "Conjugate gradient methods for indefinite systems". Numerical Analysis. Lecture Notes in Mathematics. 506. Springer Berlin / Heidelberg: 73–89. doi:10.1007/BFb0080109. ISBN 978-3-540-07610-0. ISSN 1617-9692.
  • 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.