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 and Extreme.Mathematics.Algorithms namespaces that support these algorithm patterns. They serve primarily to support the algorithms in Extreme Numerics.NET. You can also use them as a framework for your own algorithm implementations.

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 ManagedIterativeAlgorithm<T> abstract base class. Many classes in the Extreme Optimization Numerical Libraries for .NET inherit from IterativeAlgorithm, including Extreme.Mathematics.EquationSolvers and its descendants, and many of the Optimization classes.

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.

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 relative error is 0.0125.

• 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 relative 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<T> 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 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 Extreme Numerics.NET have a default value of 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

The Enabled 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<T> 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:

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<T> 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.

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.

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 Status 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.