User's Guide

Up: General Classes Next: Complex Numbers Previous: Function Delegates Contents

Numerical Algorithms Support Classes

Many of the algorithms used in numerical computing follow common patterns. They may also have common properties. This section discusses classes and enumeration types defined in the Extreme.Mathematics namespace that support these algorithm patterns. They serve primarily to support the algorithms in the Extreme Optimization Mathematics Library for .NET. You can also use them as a framework for your own algorithm implementations.

Iterative algorithms

Iteration is the process by which a procedure is executed repeatedly until a certain condition is reached. In numerical computing, the most common usage is in approximating the result of a calculation with increasing accuracy until a certain threshold is reached. If the desired accuracy is achieved, the algorithm is said to converge.

Iterative algorithms are among the most common in numerical computing. The functionality is encapsulated in the IterativeAlgorithm abstract base class. Many classes in the Extreme Optimization Mathematics Library for .NET inherit from IterativeAlgorithm, including EquationSolver and its descendants, and many of the numerical integrators.

The ManagedIterativeAlgorithm class provides additional functionality. It contains a driver method that manages the iteration process. Specific algorithms are implemented by overriding a series of protected methods.

Termination Criteria

Iterative algorithms must end. You must specify the condition that must be satisfied for the algorithm to be successful. In most cases, success means that the difference between some quantity and its actual value is within a certain tolerance. This difference or estimated error can be interpreted in two ways:

The absolute error is the difference in value between the result and the actual value. For example: if the result is 40.5 and the actual value is 40, then the absolute error is 0.5.
The relative error is the difference in value between the result and the actual value relative to the size of the result. For example: if the result is 40.5 and the actual value is 40, then the absolute error is 0.0125.

A convergence test calculates an estimate for the error, and signals termination of the algorithm when the error is below a specified tolerance. Convergence tests are implemented by the ConvergenceTest class.

Convergence Test Properties

The tolerance is set through the Tolerance property. The MachineConstants class provides some constants that may help you to obtain meaningful values for the tolerances. In nearly all cases, round-off error will prevent an algorithm from obtaining a result within a tolerance equal to the machine precision MachineConstants.Epsilon. A small multiple may be more reasonable. In some cases, however, a much larger or much smaller tolerance must be used.

Note also that there is a trade-off between accuracy and execution time. The lower the tolerance, the longer it will take for the algorithm to obtain a result within that tolerance. The tolerance should be set to the highest value that is allowed in order for successive calculations to still reach their accuracy targets. Most algorithms in the Extreme Mathematics Library for .NET have a default value of MachineConstants.SqrtEpsilon . This gives slightly less than 8 digits of accuracy.

The ConvergenceCriterion property lets you specify under what condition the algorithm is assumed to converge. The following table lists the possible values for the ConvergenceCriterion enumeration type

Value	Description
`WithinAbsoluteTolerance`	The absolute error should be within the tolerance.
`WithinRelativeTolerance`	The relative error should be within the tolerance.
`WithinAnyTolerance`	Either the absolute or the relative error should be within the tolerance.
`NumberOfIterations`	Convergence should be expected at the specified number of iterations. The estimated error is ignored.

Table 1. ConvergenceCriterion values.

The Active property indicates whether the test is used in the algorithm. This property makes it possible to selectively ignore certain convergence tests. If no convergence tests are active, then other termination criteria, mentioned below, are used.

After an algorithm has been run, the Error property returns the estimated error used in the convergence test.

Types of Convergence Tests

The SimpleConvergenceTest is used to test if a value is close to zero or very small compared to another value. For example, a search for the root of an equation will terminate if the absolute value of the function value is below the specified tolerance.

The VectorConvergenceTest is used to test convergence of vectors. This class has two additional properties. The Norm property specifies which norm is to be used when calculating the size of the vector. It is of type VectorConvergenceNorm The options are as follows:

Value	Description
`EuclidianNorm`	The Euclidian norm is used.
`Maximum`	The maximum of the absolute values of the components is used.
`SumOfAbsoluteValues`	The sum of the absolute values of the components is used.

Table 2. VectorConvergenceNorm values.

The ErrorMeasure property specifies how the error is to be measured. It is of type VectorConvergenceErrorMeasure A value of VectorConvergenceErrorMeasure.Norm indicates that the norm of the vector is used as the measure. A value of VectorConvergenceErrorMeasure.Componentwise indicates that the error of each component is calculated separately, and the norm of the vector of all error components is used.

Finally, the ConvergenceTestCollection class is used to represent a combination of tests. The Quantifier property is a ConvergenceTestQuantifier value that specifies how the tests in the collection are to be combined. A value of ConvergenceTestQuantifier.Any indicates that the test is successful if at least one of the tests in the collection succeeds. The status and error are those of the first test in the collection that indicates termination. A value of ConvergenceTestQuantifier.All indicates that all the tests in the collection must succeed for the combined test to be successful. Only tests whose Active property is set to true are included.

Other Termination Criteria

If the algorithm cannot achieve the desired accuracy, the algorithm still has to end. This can be achieved in two ways. The MaxIterations property sets an absolute boundary on the number of iterations that may be performed. The default value of this property depends on the algorithm. Alternatively, the MaxEvaluations property sets an absolute boundary on the number of function evaluations that may be performed. What constitutes a 'function evaluation' is determined by the implementation.

Algorithm Status

The Status property indicates how the algorithm terminated. Its possible values, enumerated by the AlgorithmStatus enumeration type. The TestConvergence method of the ConvergenceTest class returns a value of this type. The available options and their meaning are listed below.

Value	Description
`NoResult`	The algorithm has not been executed.
`Busy`	The algorithm is still executing.
`Converged`	The algorithm ended normally. The desired accuracy has been achieved.
`IterationLimitExceeded`	The number of iterations needed to achieve the desired accuracy is greater than MaxIterations.
`EvaluationLimitExceeded`	The number of function evaluations needed to achieve the desired accuracy is greater than MaxEvaluations.
`RoundOffError`	Round-off prevented the algorithm from achieving the desired accuracy.
`BadFunction`	Bad behavior of the target function prevented the algorithm from achieving the desired accuracy.
`Divergent`	The algorithm diverges.
`ConvergedToFalseSolution`	The algorithm has converged but the obtained solution is not a solution to the problem.

Table 3. AlgorithmStatus values.

Note: The IterationResultCode property and enumeration from previous versions have been deprecated. They are still available for backward compatibility. However, all new code should use the techniques in this section. The AbsoluteTolerance and RelativeTolerance properties, now still used for equation solving and numerical integration algorithms, will also be phased out in a future release and replaced with the ConvergenceTest class.

Other properties

After the iteration terminates, the Status should be inspected to verify that the algorithm terminated normally. Alternatively, you can set the ThrowExceptionOnFailure to true. This will make the algorithm throw an exception unless it terminates normally.

The Result property returns the result of the algorithm. This property contains the best available estimate, even if the desired accuracy was not obtained. The EstimatedError property returns the best estimate for the accuracy of the result. The IterationsNeeded property returns the number of iterations required to obtain the result. The EvaluationsNeeded property returns the number of function evaluations.

The AlgorithmHelper Class

This class provides several static methods that are useful in implementing numerical algorithms. If a class inherits from IterativeAlgorithm , the methods in this class may be useful.

At present, there are just two methods for convergence testing. The IsValueWithinTolerance method determines whether a value is close to another value to within an algorithm's requested tolerance. The IsIntervalWithinTolerance method determines whether an interval is within an algorithm's requested tolerance.