HOME

TheInfoList



OR:

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 ...
:A x= b.\, 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 ...
A 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 x_0\,, two other vectors x_0^* and b^*\, and a preconditioner M\, # r_0 \leftarrow b-A\, x_0\, # r_0^* \leftarrow b^*-x_0^*\, A^* # p_0 \leftarrow M^ r_0\, # p_0^* \leftarrow r_0^*M^\, # for k=0, 1, \ldots do ## \alpha_k \leftarrow \, ## x_ \leftarrow x_k + \alpha_k \cdot p_k\, ## x_^* \leftarrow x_k^* + \overline\cdot p_k^*\, ## r_ \leftarrow r_k - \alpha_k \cdot A p_k\, ## r_^* \leftarrow r_k^*- \overline \cdot p_k^*\, A^* ## \beta_k \leftarrow \, ## p_ \leftarrow M^ r_ + \beta_k \cdot p_k\, ## p_^* \leftarrow r_^*M^ + \overline\cdot p_k^*\, In the above formulation, the computed r_k\, and r_k^* satisfy :r_k = b - A x_k,\, :r_k^* = b^* - x_k^*\, A^* and thus are the respective residuals corresponding to x_k\, and x_k^*, as approximate solutions to the systems :A x = b,\, :x^*\, A^* = b^*\,; x^* is the adjoint, and \overline 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 x_0\,, # r_0 \leftarrow b-A\, x_0\, # \hat_0 \leftarrow \hat - \hat_0A^* # p_0 \leftarrow r_0\, # \hat_0 \leftarrow \hat_0\, # for k=0, 1, \ldots do ## \alpha_k \leftarrow \, ## x_ \leftarrow x_k + \alpha_k \cdot p_k\, ## \hat_ \leftarrow \hat_k + \alpha_k \cdot \hat_k\, ## r_ \leftarrow r_k - \alpha_k \cdot A p_k\, ## \hat_ \leftarrow \hat_k- \alpha_k \cdot \hat_k A^* ## \beta_k \leftarrow \, ## p_ \leftarrow r_ + \beta_k \cdot p_k\, ## \hat_ \leftarrow \hat_ + \beta_k \cdot \hat_k\,


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 :x_k:=x_j+ P_k A^\left(b - A x_j \right), :x_k^*:= x_j^*+\left(b^*- x_j^* A \right) P_k A^, where j using the related
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 ...
:P_k:= \mathbf_k \left(\mathbf_k^* A \mathbf_k \right)^ \mathbf_k^* A, with :\mathbf_k=\left _0, u_1, \dots, u_ \right :\mathbf_k=\left _0, v_1, \dots, v_ \right These related projections may be iterated themselves as :P_= P_k+ \left( 1-P_k\right) u_k \otimes . A relation to Quasi-Newton methods is given by P_k= A_k^ A and x_= x_k- A_^\left(A x_k -b \right), where :A_^= A_k^+ \left( 1-A_k^A\right) u_k \otimes . The new directions :p_k = \left(1-P_k \right) u_k, :p_k^* = v_k^* A \left(1- P_k \right) A^ are then orthogonal to the residuals: :v_i^* r_k= p_i^* r_k=0, :r_k^* u_j = r_k^* p_j= 0, which themselves satisfy :r_k= A \left( 1- P_k \right) A^ r_j, :r_k^*= r_j^* \left( 1- P_k \right) where i,j. The biconjugate gradient method now makes a special choice and uses the setting :u_k = M^ r_k,\, :v_k^* = r_k^* \, M^.\, With this particular choice, explicit evaluations of P_k and are avoided, and the algorithm takes the form stated above.


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