![\[ A^{\prime} A x = A^{\prime} b\]](form_0.png)
for solving the linear least squares problem
![\[ \min_{x} \vert A x - b \vert^2 \]](form_1.png)
. More...
#include <cgnealg.hh>
Inheritance diagram for RVLUmin::CGNEAlg< Scalar >:
Public Member Functions | |
| CGNEAlg (RVL::Vector< Scalar > &x, RVL::LinearOp< Scalar > const &A, RVL::Vector< Scalar > const &rhs, atype &_rnorm, atype &_nrnorm, atype _rtol=100.0 *numeric_limits< atype >::epsilon(), atype _nrtol=100.0 *numeric_limits< atype >::epsilon(), int _maxcount=10, atype _maxstep=numeric_limits< atype >::max(), ostream &_str=cout) | |
| Constructor - basic algorithm. | |
| CGNEAlg (RVL::Vector< Scalar > &x, LinearOp< Scalar > const &A, LinearOp< Scalar > const &M, Vector< Scalar > const &rhs, atype &_rnorm, atype &_nrnorm, atype _rtol=100.0 *numeric_limits< atype >::epsilon(), atype _nrtol=100.0 *numeric_limits< atype >::epsilon(), int _maxcount=10, atype _maxstep=numeric_limits< atype >::max(), ostream &_str=cout) | |
| Constructor - preconditioned algorithm. | |
| ~CGNEAlg () | |
| bool | query () |
| void | run () |
| int | getCount () const |
for solving the linear least squares problem
.
This is Algorithm CGLS as stated in Paige and Saunders, ACM TOMS vol. 8 pp. 43-72 1982 (see p. 57). We use variable names aping Paige and Saunder's notation insofar as possible.
Structure and function: Combines CGNEStep with a Terminator which displays iteration count, residual norm, and normal residual norm on output stream (constructor argument _str), and terminates if iteration count exceeds max or residual norm or normal residual norm fall below threshhold (default = 10*sqrt(macheps)). Also terminates if the length of the solution vector exceeds a specified bound (maxstep argument to constructor). In this latter case, the computed step is projected onto the ball of radius maxstep centered at the initial estimate. This maximum step limit and projection turns the algorithm into an approximate trust region subproblem solver, similar to Steihaug-Toint. The default choice of maxstep is the max Scalar, which effectively turns off the trust region feature.
Usage: construct CGNEAlg object by supplying appropriate arguments to constructor. On return from constructor, solution vector initialized to zero, residual norm to norm of RHS, and normal residual norm to norm of image of RHS under adjoint of operator. Then call run() method. Progress of iteration written on output unit. On return from run(), solution vector stores final estimate of solution, and residual norm and normal residual norm scalars have corresponding values.
Typical Use: see functional test source.
IMPORTANT NOTE: This class is also an RVLAlg::Terminator subclass. Its query() method returns true if the trust region constraint was binding (raw LS solution larger than trust radius), else false.
IMPORTANT NOTE: The solution vector and residual and normal residual scalars are external objects, for which this algorithm stores mutable references. These objects are updated by constructing a CGNEAlg object, and by calling its run() method.
IMPORTANT NOTE: this version of the algorithm initializes the solution vector to zero. To accommodate nontrivial initial guess, modify the right-hand-side vector (argument _rhs) externally.
IMPORTANT NOTE: in order that this algorithm function properly for complex scalar types, a careful distinction is maintained between the main template parameter (Scalar) type and its absolute value type. All of the scalars appearing in the algorithm are actually of the latter type.
See constructor documentation for description of parameters.
Definition at line 378 of file cgnealg.hh.
| RVLUmin::CGNEAlg< Scalar >::CGNEAlg | ( | RVL::Vector< Scalar > & | x, | |
| RVL::LinearOp< Scalar > const & | A, | |||
| RVL::Vector< Scalar > const & | rhs, | |||
| atype & | _rnorm, | |||
| atype & | _nrnorm, | |||
| atype | _rtol = 100.0*numeric_limits<atype>::epsilon(), |
|||
| atype | _nrtol = 100.0*numeric_limits<atype>::epsilon(), |
|||
| int | _maxcount = 10, |
|||
| atype | _maxstep = numeric_limits<atype>::max(), |
|||
| ostream & | _str = cout | |||
| ) |
Constructor - basic algorithm.
| x | - mutable reference to solution vector (external), initialized to zero vector on construction, estimated solution on return from CGNEAlg::run(). | |
| A | - const reference to LinearOp (external) defining problem | |
| rhs | - const reference to RHS or target vector (external) | |
| _rnorm | - mutable reference to residual norm scalar (external), initialized to norm of RHS on construction, norm of estimated residual at solution on return from CGNEAlg::run() | |
| _nrnorm | - mutable reference to normal residual (least squares gradient) norm scalar (external), initialized to morm of image of RHS under adjoint of problem LinearOp on construction, norm of estimated normal residual at solution on return from CGNEAlg::run() | |
| _rtol | - stopping threshold for residual norm, default value = 100.0*macheps | |
| _nrtol | - stopping threshold for normal residual norm, default value = 100.0*macheps | |
| _maxcount | - max number of iterations permitted, default value = 10 | |
| _maxstep | - max permitted step length (trust radius), default value = max absval scalar (which makes the trust region feature inactive) | |
| _str | - output stream |
Definition at line 423 of file cgnealg.hh.
References RVL::Vector< Scalar >::zero().
| RVLUmin::CGNEAlg< Scalar >::CGNEAlg | ( | RVL::Vector< Scalar > & | x, | |
| LinearOp< Scalar > const & | A, | |||
| LinearOp< Scalar > const & | M, | |||
| Vector< Scalar > const & | rhs, | |||
| atype & | _rnorm, | |||
| atype & | _nrnorm, | |||
| atype | _rtol = 100.0*numeric_limits<atype>::epsilon(), |
|||
| atype | _nrtol = 100.0*numeric_limits<atype>::epsilon(), |
|||
| int | _maxcount = 10, |
|||
| atype | _maxstep = numeric_limits<atype>::max(), |
|||
| ostream & | _str = cout | |||
| ) |
Constructor - preconditioned algorithm.
| x | - mutable reference to solution vector (external), initialized to zero vector on construction, estimated solution on return from CGNEAlg::run(). | |
| A | - const reference to LinearOp (external) defining problem | |
| M | - const reference to LinearOp (external) preconditioner = inverse of operator defining inner product in domain space. Only this operator is necessary, not the inner product operator itself. M is assumed to be SPD, else no guarantees about the behaviour of this algorithm | |
| rhs | - const reference to RHS or target vector (external) | |
| _rnorm | - mutable reference to residual norm scalar (external), initialized to norm of RHS on construction, norm of estimated residual at solution on return from CGNEAlg::run() | |
| _nrnorm | - mutable reference to normal residual (least squares gradient) norm scalar (external), initialized to morm of image of RHS under adjoint of problem LinearOp on construction, norm of estimated normal residual at solution on return from CGNEAlg::run() | |
| _rtol | - stopping threshold for residual norm, default value = 100.0*macheps | |
| _nrtol | - stopping threshold for normal residual norm, default value = 100.0*macheps | |
| _maxcount | - max number of iterations permitted, default value = 10 | |
| _maxstep | - max permitted step length (trust radius), default value = max absval scalar (which makes the trust region feature inactive) | |
| _str | - output stream |
Definition at line 497 of file cgnealg.hh.
References RVL::Vector< Scalar >::zero().
| RVLUmin::CGNEAlg< Scalar >::~CGNEAlg | ( | ) |
Definition at line 528 of file cgnealg.hh.
| bool RVLUmin::CGNEAlg< Scalar >::query | ( | ) | [virtual] |
| void RVLUmin::CGNEAlg< Scalar >::run | ( | ) | [virtual] |
Implements RVLAlg::Algorithm.
Definition at line 534 of file cgnealg.hh.
References RVLAlg::CountTerminator::getCount(), RVLAlg::VectorCountingThresholdIterationTable< Scalar >::init(), RVL::Vector< Scalar >::linComb(), RVL::Vector< Scalar >::norm(), RVLAlg::Terminator::query(), RVLAlg::LoopAlg::run(), and RVLUmin::CGNEStep< Scalar >::x.
| int RVLUmin::CGNEAlg< Scalar >::getCount | ( | ) | const |
Definition at line 620 of file cgnealg.hh.
1.4.7