Newton Class Reference

#include <Newton.h>

Inheritance diagram for Newton:

[legend]List of all members.

---

Detailed Description

The main Newton algorithm class.

This module searches an N-dimensional Box for roots of an equation. It does this by first employing a simple subdivision to get rid of regions of space that definitely don't contain roots. It then subdivides those regions that might contain roots into small enough pieces to be handled by a Newton's Method solver. So there are two parts of the search algorithm that you must concern yourself with: subdivision and equation solving.

This module solves N equations in N variables, over a given bounding box, and is guaranteed to find all solutions within that bounding box because it uses interval arithmetic. Basically, it finds all of the roots of a set of equations.

In matrix notation, this class solves A*(Y - Xc) - b = 0 where A is an an NxN IMatrix (ie. a matrix of intervals), Xc is an N-dimensional vector (of doubles), and b and Y are N-dimensional Boxes (ie. vectors of intervals). Xc represents an initial guess for the root, ie. the center of the interval used in Newton's method. Y represents the variable we are solving for since we are trying to find a Box containing a root. The tricky part is that YOU must provide A and b. These values are set in the NewtonEquation() method. You will have to override this method if you want to do something other than the default here (which is nothing).

HOW TO USE THIS CLASS AND WHAT METHODS TO OVERRIDE

(1) NewtonSubdivisionBreak() is called on a given Box region during the simple subdivision phase. This method should return true if you know for sure that there is NOT a root in that region, false if there might be a root in the region. Since the default NewtonSubdivisionBreak() method always returns false, the root finding won't stop until the Box size has reached fWidthTolerance.

(2) NewtonEquation() is called during the Newton's Method phase to set the variables A and b in the equation A(Y-Xc) = b. So if you want to use Newton's method to refine the root finding once the Box size has reached fNewtonTolerance, be sure to override this method and return true.

(3) NewtonBreak() is called on the Box in ALL phases of the root finding process to see if we can stop searching for roots in the Box. The default method performs two checks: 1: Have we found the maximum number of roots allowed? 2: Is the box small enough to say that two roots in the box can be considered as a single root, and if so does this box already contain a root? If either of these tests is true, then we return true to indicate that we want to stop searching this box for more roots. You may want to override this behavior if you have additional information on the Box in question (for example, using the gradient can we determine if there is definitely no root in the Box in question).

(4) NewtonOutput() is called every time we find a root. This method in turn calls NewtonPostProcess() which allows you to take action on the root in question prior to actually saving it. You may want to override NewtonOutput() if you want to store the roots someplace other than the default location fRoots, a list of Points.

(5) NewtonPostProcess() is called by NewtonOutput() and allows you to take action on the root in question prior to actually saving it. You could override this method if you have more conditions that the root must meet if it will be stored. The default method prevents duplicates roots from being output.

(6) FindZeros() is the method you call to actually find roots over an initial domain. Simple subdivision is used down to a resolution of fNewtonTolerance, and then Newton's method takes over, which provides quadratic convergence for most cases.

Definition at line 101 of file Newton.h.

Public Member Functions
	Newton ()
	Default constructor.
void	FindZeros (Box< double > &IX)
	Front end for finding zeros.
Public Attributes
double	fWidthTolerance
	Maximum error of final roots (width of the bounding box).
double	fSameTolerance
	Two roots this close together are considered the same.
unsigned int	fMaxRoots
	The maximum number of roots we are allowed to save.
int	fUseNewton
	Flag for FindZeros to use Newton iteration.
double	fNewtonTolerance
	FindZeros uses subdivision on large intervals, then hones in using Newton when the interval is smaller than fNewtonTolerance.
PointList	fRoots
	List of roots saved by NewtonOutput().
PointList::iterator	plIter
	Convenient iterator over PointList.
Static Public Attributes
const double	STANDARD_WIDTH_TOLERANCE = 0.0001
	How wide the divisions can be before quitting.
const int	STANDARD_MAX_ROOTS = 20
	Maximum number of roots we can find - prevents problems with degenerates.
Protected Member Functions
virtual bool	NewtonSubdivisionBreak (Box< double > &X)
	During the subdivsion phase, this method should return true if you know for sure that there isn't a root in this box and you want to exclude it from further searching during the subdivision phase.
virtual bool	NewtonEquation (Box< double > &X, IMatrix &A, Box< double > &b)
	Setup the system of equations to solve for during the Newton's Method phase.
virtual bool	NewtonPostProcess (Box< double > &X)
	This method is called just before we call NewtonOutput and allows you to do extra stuff to the root (in the Box) before it gets output.
virtual void	NewtonOutput (Box< double > &X)
	Outputs a root found during the search.
virtual bool	NewtonBreak (Box< double > &X)
	User definable test to determine if root search in current interval can be terminated.
bool	SameRoot (Box< double > &IX)
	Determins if root already found before.
void	AddRoot (Box< double > IX)
	Add a root to the found root list.
Private Member Functions
void	FindZerosDivide (Box< double > &IX)
	This method iterates through the given Box region looking for roots.
void	NewtonDriver ()
	Performs the Newton zero search on whatever is in the stack.
NewtonResult	INewton (Box< double > &IX)
	Interval newton method for solving simultaneous equations of the form A*(Y-XC) - b = 0.
int	SolveSeidel (Box< double > &X, Point Xc, IMatrix &M, Box< double > &b, int *unique)
	Solve the interval matrix problem M(Y-Xc) + b = 0 for Y.
int	GaussSeidelRow (Box< double > &X, Point &Xc, IMatrix &M, Box< double > &b, int row, int *unique)
	Perform a step in the Gauss-Seidel iteration for a given row.
Private Attributes
std::stack< Box< double > >	boxes
	Stack of boxes used when root finding requires subdivision.

---

Constructor & Destructor Documentation

Newton::Newton (   )

Default constructor. It initializes the algorithm variables. Definition at line 26 of file Newton.cpp. References fMaxRoots, fNewtonTolerance, fSameTolerance, fUseNewton, fWidthTolerance, STANDARD_MAX_ROOTS, and STANDARD_WIDTH_TOLERANCE.

---

Member Function Documentation

void Newton::AddRoot (  Box< double >  IX  )  [protected]

Add a root to the found root list. Parameters: IX  small interval around newly found root Definition at line 65 of file Newton.cpp. References Box< Float >::center(), and fRoots. Referenced by NewtonOutput().

void Newton::FindZeros (  Box< double > &  X  )

Front end for finding zeros. This is the method to call when you want to look for roots in the given region Box. Parameters: X  Box in which to find zeros. Definition at line 362 of file Newton.cpp. References FindZerosDivide(), fRoots, and X. Referenced by SearchDegenerate::search(), and SearchCritical::search().

void Newton::FindZerosDivide (  Box< double > &  X  )  [private]

This method iterates through the given Box region looking for roots. It first uses a simple subdivision method to search for roots. If fUseNewton is set, it switches over to Newton's Method when the Box is sufficiently small (set by fNewtonTolerance). Parameters: X  Box region to search for roots (zeros). Definition at line 322 of file Newton.cpp. References boxes, fNewtonTolerance, fUseNewton, fWidthTolerance, NewtonBreak(), NewtonDriver(), NewtonOutput(), NewtonPostProcess(), NewtonSubdivisionBreak(), and X. Referenced by FindZeros().

int Newton::GaussSeidelRow (  Box< double > &  X, Point &  Xc, IMatrix &  M, Box< double > &  b, int  row, int *  unique )  [private]

Perform a step in the Gauss-Seidel iteration for a given row. Parameters: X  Domain of root finding (ie. the Box used) Xc  Initial guess (ie. the midpoint of the Box) M  Interval matrix = A in the matrix equation Ax = b b  Interval vector = b in the matrix equation Ax = b row  Current row to work on. unique  Set to true if interval contains at most one root. Undefined if no solutions found. Returns: False if there are no solutions here. True if X contains at least one box to be further processed. Note: All values here are Interval values Definition at line 85 of file Newton.cpp. References boxes, IDinf(), ISPLIT, and X. Referenced by SolveSeidel().

NewtonResult Newton::INewton (  Box< double > &  X  )  [private]

Interval newton method for solving simultaneous equations of the form A*(Y-XC) - b = 0. Parameters: X  Box in which to find roots. Returns: NO_ROOTS if there is no solution in IX UNIQUE_ROOT if IX contains a unique solution KEEP_TRYING if not sure, but IX is getting smaller NO_PROGRESS if not sure, but IX is not getting smaller BAD_INVERSE if Jc cannot be inverted See also: NewtonEquation() for setting up A and b in the matrix equation Ax=b. Definition at line 213 of file Newton.cpp. References KEEP_TRYING, NewtonEquation(), NewtonResult, NO_PROGRESS, NO_ROOTS, SolveSeidel(), UNIQUE_ROOT, Box< Float >::width(), and X. Referenced by NewtonDriver().

virtual bool Newton::NewtonBreak (  Box< double > &  X  )  [inline, protected, virtual]

User definable test to determine if root search in current interval can be terminated. The default method performs the following checks: Have we found the maximum number of roots allowed? Is the box small enough to say that two roots in the box can be considered as a single root (change fSameTolerance to set this size), and if so does this box already contain a root? If either of these tests is true, then we return true to indicate that we want to stop searching this box for more roots. You may want to add more conditions to this method (by overriding it) if you have more information on the function/Box. Parameters: X  Current Box being searched. Returns: True if the Box cannot possibly contain any roots and thus we should stop looking any further. False if the Box should be searched for roots. Definition at line 225 of file Newton.h. References fMaxRoots, fRoots, fSameTolerance, SameRoot(), and X. Referenced by FindZerosDivide(), and NewtonDriver().

void Newton::NewtonDriver (   )  [private]

Performs the Newton zero search on whatever is in the stack. Definition at line 247 of file Newton.cpp. References BAD_INVERSE, boxes, fWidthTolerance, INewton(), KEEP_TRYING, NewtonBreak(), NewtonOutput(), NewtonPostProcess(), NewtonResult, NO_PROGRESS, NO_ROOTS, UNIQUE_ROOT, and X. Referenced by FindZerosDivide().

virtual bool Newton::NewtonEquation (  Box< double > &  X, IMatrix &  A, Box< double > &  b )  [inline, protected, virtual]

Setup the system of equations to solve for during the Newton's Method phase. X is the input N-dimensional Box that you want to use when finding roots. Newton's method phase. You must set values for the parameters A and b. Also, you must return true if you want Newton solver to actually do anything. If you return false, then it assumes that you haven't set up A and b and insteads uses simple subdivision for the entire process. Parameters: X  The input Box (N-dimensional interval vector) to search for roots. A  The interval matrix to be returned for solving the equation. b  The interval vector to be returned for solving the equation. Returns: True if you have set A and b and want to use Newtons' method. False to indicate no processing is necessary. Reimplemented in NewtonCritical, and NewtonDegenerate. Definition at line 167 of file Newton.h. Referenced by INewton().

virtual void Newton::NewtonOutput (  Box< double > &  X  )  [inline, protected, virtual]

Outputs a root found during the search. The input point (actually a Box which gets converted to a point using the Box::center()) is checked against the current list of roots (fRoots). If it is not found in the list, then it is added to the list. Parameters: X  A Box which is converted to a point for adding to the fRoot list. Note: This method defaults to adding the root to the internal solution list. Override it if you want to maintain this list yourself. Definition at line 204 of file Newton.h. References AddRoot(), and X. Referenced by FindZerosDivide(), and NewtonDriver().

virtual bool Newton::NewtonPostProcess (  Box< double > &  X  )  [inline, protected, virtual]

This method is called just before we call NewtonOutput and allows you to do extra stuff to the root (in the Box) before it gets output. If you return false from here, NewtonOutput will NOT be called, in effect not saving the root. So if you want to save the root, be sure to return true. The default method checks to see if the box in question has already been output. If so, then we return false since we don't want it added again. Parameters: X  The Box containing the root to process just before we call NewtonOutput(). Returns: True if the root (Box) is okay and we should call NewtonOutput(). False if you want to throw the Box away. Reimplemented in SearchCritical, and SearchDegenerate. Definition at line 185 of file Newton.h. References SameRoot(), and X. Referenced by FindZerosDivide(), and NewtonDriver().

virtual bool Newton::NewtonSubdivisionBreak (  Box< double > &  X  )  [inline, protected, virtual]

During the subdivsion phase, this method should return true if you know for sure that there isn't a root in this box and you want to exclude it from further searching during the subdivision phase. Parameters: X  The Box to search for roots. Returns: True if we should stop searching for roots in this box. False if we should search the Box for roots. Reimplemented in NewtonCritical, and NewtonDegenerate. Definition at line 148 of file Newton.h. Referenced by FindZerosDivide().

bool Newton::SameRoot (  Box< double > &  IX  )  [protected]

Determins if root already found before. The "sameness" is determined by the member fSameTolerance which is related to fWidthTolerance. Parameters: IX  Small Box interval surrounding newly found root. Returns: True if nearby root already found, false otherwise. Definition at line 41 of file Newton.cpp. References Box< Float >::center(), fRoots, fSameTolerance, and plIter. Referenced by NewtonBreak(), SearchDegenerate::NewtonPostProcess(), SearchCritical::NewtonPostProcess(), and NewtonPostProcess().

int Newton::SolveSeidel (  Box< double > &  X, Point  Xc, IMatrix &  M, Box< double > &  b, int *  unique )  [private]

Solve the interval matrix problem M(Y-Xc) + b = 0 for Y. Set X = Intersection(X,Y). Split X and push a sub-box if necessary. Parameters: X  Domain of the iteration (ie. the Box used) Xc  Seed point of the iteration (ie. the center of Box) M  Interval matrix = A in the matrix equation Ax = b b  Interval vector = b in the matrix equation Ax = b *unique  True if X contains a single root Returns: False if there are no solutions here. True if X contains a box to be further processed. if return==true && *unique==true, then X contains a unique root Note: : All values here are Interval values Definition at line 163 of file Newton.cpp. References GaussSeidelRow(), and X. Referenced by INewton().

---

Member Data Documentation

std::stack< Box<double> > Newton::boxes [private]

Stack of boxes used when root finding requires subdivision. Definition at line 259 of file Newton.h. Referenced by FindZerosDivide(), GaussSeidelRow(), and NewtonDriver().

unsigned int Newton::fMaxRoots

The maximum number of roots we are allowed to save. Definition at line 117 of file Newton.h. Referenced by Newton(), NewtonBreak(), SearchDegenerate::NewtonPostProcess(), SearchCritical::NewtonPostProcess(), SearchDegenerate::search(), and SearchCritical::search().

double Newton::fNewtonTolerance

FindZeros uses subdivision on large intervals, then hones in using Newton when the interval is smaller than fNewtonTolerance. Definition at line 128 of file Newton.h. Referenced by FindZerosDivide(), Newton(), SearchDegenerate::search(), and SearchCritical::search().

PointList Newton::fRoots

List of roots saved by NewtonOutput(). Definition at line 130 of file Newton.h. Referenced by AddRoot(), SearchCritical::classify(), CriticalPointInterrogator::cleanup(), SearchCritical::display(), FindZeros(), NewtonBreak(), SearchDegenerate::NewtonPostProcess(), SearchCritical::NewtonPostProcess(), SearchDegenerate::print(), SearchCritical::print(), and SameRoot().

double Newton::fSameTolerance

Two roots this close together are considered the same. Definition at line 114 of file Newton.h. Referenced by Newton(), NewtonBreak(), SearchDegenerate::NewtonPostProcess(), SearchCritical::NewtonPostProcess(), SameRoot(), SearchDegenerate::search(), and SearchCritical::search().

int Newton::fUseNewton

Flag for FindZeros to use Newton iteration. If false, then FindZeros uses simple subdivision for the entire root finding process. Definition at line 123 of file Newton.h. Referenced by CriticalPointInterrogator::findCriticalPoints(), FindZerosDivide(), CriticalMesh::initialMesh(), and Newton().

double Newton::fWidthTolerance

Maximum error of final roots (width of the bounding box). Definition at line 111 of file Newton.h. Referenced by FindZerosDivide(), Newton(), and NewtonDriver().

PointList::iterator Newton::plIter

Convenient iterator over PointList. Definition at line 132 of file Newton.h. Referenced by SearchCritical::display(), SearchDegenerate::print(), SearchCritical::print(), and SameRoot().

const int Newton::STANDARD_MAX_ROOTS = 20 [static]

Maximum number of roots we can find - prevents problems with degenerates. Definition at line 22 of file Newton.cpp. Referenced by Newton().

const double Newton::STANDARD_WIDTH_TOLERANCE = 0.0001 [static]

How wide the divisions can be before quitting. Definition at line 21 of file Newton.cpp. Referenced by Newton().

---

The documentation for this class was generated from the following files:

• Newton.h
• Newton.cpp

---