In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, more specifically in
numerical linear algebra, the biconjugate gradient method is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
to solve
systems of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variables.
For example,
: \begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in ...
:
Unlike the
conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-semidefinite. The conjugate gradient method is often implemented as an it ...
, this algorithm does not require the
matrix
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the m ...
to be
self-adjoint
In mathematics, an element of a *-algebra is called self-adjoint if it is the same as its adjoint (i.e. a = a^*).
Definition
Let \mathcal be a *-algebra. An element a \in \mathcal is called self-adjoint if
The set of self-adjoint elements ...
, but instead one needs to perform multiplications by the
conjugate transpose
In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \mathbf is an n \times m matrix obtained by transposing \mathbf and applying complex conjugation to each entry (the complex conjugate ...
.
The Algorithm
# Choose initial guess
, two other vectors
and
and a
preconditioner
#
#
#
#
# for
do
##
##
##
##
##
##
##
##
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
In mathematics, the complex conjugate of a complex number is the number with an equal real part and an imaginary part equal in magnitude but opposite in sign. That is, if a and b are real numbers, then the complex conjugate of a + bi is a - ...
.
Unpreconditioned version of the algorithm
# Choose initial guess
,
#
#
#
#
# for
do
##
##
##
##
##
##
##
##
Discussion
The biconjugate gradient method is
numerically unstable (compare to the
biconjugate gradient stabilized method), but very important from a theoretical point of view. Define the iteration steps by
:
:
where
projection
Projection or projections may refer to:
Physics
* Projection (physics), the action/process of light, heat, or sound reflecting from a surface to another in a different direction
* The display of images by a projector
Optics, graphics, and carto ...
:
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
Properties
* If
A= A^*\, is
self-adjoint
In mathematics, an element of a *-algebra is called self-adjoint if it is the same as its adjoint (i.e. a = a^*).
Definition
Let \mathcal be a *-algebra. An element a \in \mathcal is called self-adjoint if
The set of self-adjoint elements ...
,
x_0^*= x_0 and
b^*=b, then
r_k= r_k^*,
p_k= p_k^*, and the
conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-semidefinite. The conjugate gradient method is often implemented as an it ...
produces the same sequence
x_k= x_k^* at half the computational cost.
* The sequences produced by the algorithm are
biorthogonal, i.e.,
p_i^*Ap_j=r_i^*M^r_j=0 for
i \neq j.
* if
P_\, is a polynomial with
\deg\left(P_\right)+j, then r_k^*P_\left(M^A\right)u_j=0. The algorithm thus produces projections onto the Krylov subspace.
* if P_\, is a polynomial with i+\deg\left(P_\right), then v_i^*P_\left(AM^\right)r_k=0.
See also
*
Biconjugate gradient stabilized method (BiCG-Stab)
*
Conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-semidefinite. The conjugate gradient method is often implemented as an it ...
(CG)
*
Conjugate gradient squared method (CGS)
References
*
*
{{Numerical linear algebra
Numerical linear algebra
Gradient methods