Interval evaluation and Taylor remainder

The procedure Auto_Diff addresses two main problems:

1. when dealing with large or complex expression the compilation time of the C++ program that is needed to interval evaluate the expression may be quite large
2. for some problem it may be interesting to have a procedure that computes the Taylor remainder of a given expression. But this remainder may have a very large expression and the first item apply

The syntax of this procedure is

 
Auto_Diff(Func,Vars,N,REM)

where N is the order of the Taylor remainder (if N is set to 0 this remainder is the expression itself) and REM is a string that will be the name of the C++ program that will compute the remainder (the program is written in the file REM.c). Note that REM is a procedure using MakeF format.

As the remainder may be a very large expression but which includes multiple occurrences of the same elementary components Auto_Diff uses the Decompose_Diff procedure to reduce the number of interval evaluation of the same elementary components.

Consider the expression

$$(sin(x)^2+cos(x)^3)/x+x*(sin(x)^2+cos(x)^3)$$

and apply Auto_Diff for the evaluation of this expression

 
Auto_Diff((sin(x)^2+cos(x)^3)/x+x*(sin(x)^2+cos(x)^3),[x],0,"REM");
           (ALIAS_B4 + ALIAS_B5) ALIAS_B1 + x (ALIAS_B4 + ALIAS_B5)

This indicates that the terms $\sin(x)^2, \cos(x)^3, 1/x$ will be calculated only once and affected to the dummy interval ALIAS_B4, ALIAS_B5, ALIAS_B1.

The calculation of these dummy variables is done in the procedure ALIAS_DIFF.C:

 
#include <fstream.h>
#include "Functions.h"
#include "Vector.h"
#include "IntervalVector.h"
#include "IntervalMatrix.h"
#include "IntervalMatrix.h"
#include "IntegerVector.h"
#include "IntegerMatrix.h"
INTERVAL_VECTOR ALIAS_DIFF(INTERVAL_VECTOR &v_IS)
{
INTERVAL_VECTOR B(3);
INTERVAL_VECTOR AD(5);
Clear(AD);
B(1)=Sqr(Sin(v_IS(1)));
B(2)=Power(Cos(v_IS(1)),3);
B(3)=1/v_IS(1);
AD(1)=B(3);
AD(2)=B(1);
AD(3)=B(2);
AD(4)=B(1);
AD(5)=B(2);
return AD;
}

Note that ALIAS_DIFF.C is a self-contained program that can be compiled independently. The code for REM.c is

 
INTERVAL_VECTOR ALIAS_DIFF(INTERVAL_VECTOR &v_IS);
#include "ALIAS_REM.c"
INTERVAL_VECTOR REM(int l1,int l2,INTERVAL_VECTOR & v_IS)
{
INTERVAL_VECTOR V(1),X(5),XX(6);
int i;
//computation of the elementary components
X=ALIAS_DIFF(v_IS);
for(i=1;i<=1;i++)XX(i)=v_IS(i);
for(i=1;i<=5;i++)XX(i+1)=X(i);
//XX contains the unknowns and then the elementary components
V=ALIAS_REM(1,1,XX);
return V;
}

Here the interval vector XX contains first the variable and then the dummy variables. The calculation of the expression is then performed by the ALIAS_REM procedure:

 
INTERVAL_VECTOR ALIAS_REM(int l1, int l2, INTERVAL_VECTOR & v_IS) {
        INTERVAL_VECTOR V(1);
next1:
        if (l1<=1 && 1<=l2)
        {
        V(1)=(v_IS(5)+v_IS(6))*v_IS(2)+v_IS(1)*(v_IS(5)+v_IS(6));
        }
next2: ;
        return V;
}

For a remainder let's use

 
Auto_Diff((sin(x)^2+cos(x)^3)/x+x*(sin(x)^2+cos(x)^3),[x],1,"REM");

which returns

 
(ALIAS_B4 ALIAS_B3 + ALIAS_B7 + ALIAS_B8 + ALIAS_B4 ALIAS_B2
     + (ALIAS_B7 + ALIAS_B8) ALIAS_B1 + x (ALIAS_B3 + ALIAS_B2)) W_x_1

Here W_x_1 represents $x-h$ where $h$ is the expansion point (W_x_2 will represent $(x-h)^2$ and so on). This terms is calculated in the program ALIAS_DIAM.C.

Note that Auto_Diff try to improve the interval evaluation by using a Horner form. But it can be seen that it does not always provide the best one. In the previous example

 
((ALIAS_B7 + ALIAS_B8)(1+ ALIAS_B1) + (x+ALIAS_B4) (ALIAS_B3 + ALIAS_B2)) W_x_1

will have been optimal.