ConjugateGradient (JMSL Numerical Library)

Overview

Package

Class

Tree

Index

Help

JMSL^TM Numerical Library 6.1

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.imsl.math
Class ConjugateGradient

java.lang.Object
  com.imsl.math.ConjugateGradient

All Implemented Interfaces:: Serializable

public class ConjugateGradient
extends Object
implements Serializable
extends Object
implements Serializable

Solves a real symmetric definite linear system using the conjugate gradient method with optional preconditioning.

Class ConjugateGradient solves the symmetric positive or negative definite linear system using the conjugate gradient method with optional preconditioning. This method is described in detail by Golub and Van Loan (1983, Chapter 10), and in Hageman and Young (1981, Chapter 7).

The preconditioning matrix M is a matrix that approximates A, and for which the linear system Mz=r is easy to solve. These two properties are in conflict; balancing them is a topic of current research. If no preconditioning matrix is specified, is set to the identity, i.e. .

The number of iterations needed depends on the matrix and the error tolerance. As a rough guide,

where n is the order of matrix A.

See the references for details.

Let M be the preconditioning matrix, let b,p,r,x and z be vectors and let be the desired relative error. Then the algorithm used is as follows:

$hspace*{1cm}p_0 = x_0$

$hspace*{1cm}r_1 = b-Ap_0$

$hspace*{2cm}z_k = M^{-1}r_k$

$hspace*{2.5cm}beta_k = 1$

$hspace*{2.5cm}p_k = z_k$

$hspace*{2.5cm}beta_k=(z_k^Tr_k)/(z_{k-1}^Tr_{k-1})$

$hspace*{2.5cm}p_k=z_k+beta_kp_{k-1}$

$hspace*{2cm}alpha_k=(r_{k}^Tz_{k})/(p_k^TAp_k)$

$hspace*{2cm}x_k=x_{k-1}+alpha_kp_k$

$hspace*{2cm}r_{k+1}=r_k-alpha_kAp_k$

$hspace*{2cm}mbox{if }(|Ap_k|_2 leq tau (1-lambda)|x_k|_2) mbox{ then}$

$hspace*{2.5cm}mbox{if }(|Ap_k|_2 leq tau(1-lambda)|x_k|_2)mbox{ exit}$

Here, is an estimate of $lambda_{max}(Gamma)$ , the largest eigenvalue of the iteration matrix $Gamma=I-M^{-1}A$ . The stopping criterion is based on the result (Hageman and Young 1981, pp. 148-151)

$frac{|x_k-x|_M}{|x|_M} leq left(frac{1}{1-lambda_{max}(Gamma)}right)left(frac{|z_k|_M}{|x_k|_M}right),$

where

It is also known that

$lambda_{max}(T_1) leq lambda_{max}(T_2) leq ldots leq lambda_{max}(Gamma) lt 1,$

where the

are the symmetric, tridiagonal matrices

$T_l = left[ begin{array}{ccccc} mu_1 & omega_2 & & & \ omega_2 & mu_2 & omega_3 & & \ & omega_3 & mu_3 & raisebox{-1ex}{ ddots } & \ & & ddots & ddots & omega_l \ & & & omega_l & mu_l end{array} right]$

with

and, for

$mu_k=1-beta_k/alpha_{k-1}-1/alpha_k quad mbox{and} quad omega_k=sqrt{beta_k}/alpha_{k-1}.$

Usually, the eigenvalue computation is needed for only a few of the iterations.

See Also:: Example without preconditioning, Example with different preconditioners, Serialized Form

Nested Class Summary
`static interface`	`ConjugateGradient.Function` Public interface for the user supplied function to `ConjugateGradient`.
`static class`	`ConjugateGradient.NoConvergenceException` The conjugate gradient method did not converge within the allowed maximum number of iterations.
`static class`	`ConjugateGradient.NotDefiniteAMatrixException` The input matrix A is indefinite, that is the matrix is not positive or negative definite.
`static class`	`ConjugateGradient.NotDefiniteJacobiPreconditionerException` The Jacobi preconditioner is not strictly positive or negative definite.
`static class`	`ConjugateGradient.NotDefinitePreconditionMatrixException` The Precondition matrix is indefinite.
`static interface`	`ConjugateGradient.Preconditioner` Public interface for the user supplied function to `ConjugateGradient` used for preconditioning.
`static class`	`ConjugateGradient.SingularPreconditionMatrixException` The Precondition matrix is singular.

Constructor Summary
`ConjugateGradient(int n, ConjugateGradient.Function argF)` Conjugate gradient constructor.

Method Summary
`int`	`getIterations()` Returns the number of iterations needed by the conjugate gradient algorithm.
`double[]`	`getJacobi()` Returns the Jacobi preconditioning matrix.
`int`	`getMaxIterations()` Returns the maximum number of iterations allowed.
`double`	`getRelativeError(double errorRelative)` Returns the relative error used for stopping the algorithm.
`void`	`setJacobi(double[] diagonal)` Defines a Jacobi preconditioner as the preconditioning matrix, that is, M is the diagonal of `A`.
`void`	`setMaxIterations(int maxIterations)` Sets the maximum number of iterations allowed.
`void`	`setRelativeError(double tolerance)` Sets the relative error used for stopping the algorithm.
`double[]`	`solve(double[] b)` Solves a real symmetric positive or negative definite system using a conjugate gradient method with or without preconditioning.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail