Differentiating a function at a point yields the slope of the
graph of the function at that point. Therefore, a rough first
calculation of f'(x) will be obtained by
the following function:
easydiff f x h = (f(x+h) - f x) / h
This function will return a good approximation when the value of
h is very small. However, when h is very small,
f(x+h)and f x are very close together and the rounding error in
subtracting them may hopelessly distort the result. The strategy
taken here is to start with relatively big initial value of
h, then to repeat the calculation of easydiff with smaller
and smaller values of h and to stop this calculation at the
first occurrence of two consecutive results within the desired
tolerance. For convenience we'll be using h/2 in each new
step of these calculations.
First we must define a function which computes the sequence:
differentiate h0 f x = map (easydiff f x) (repeat halve h0)
where halve x = x/2
where h0 is the initial value for h and its
successive new values are obtained by repeated halving.
From the sequence thus obtained, we can compute the derivative
at any point x by simply applying the within function
like this:
within eps (differentiate h0 f x)
It turns out that even this solution is not perfect because of
the slow speed of convergence of the sequence. Some math [1]
can help in showing that the values of the sequence contain
an error term, which is proportional to a power of h. Simple
calculations, which we are not reproducing here show that the
correct answer A can be obtained by the following formula:
a(i+1)*(2**n) - a(i)
A =
--------------------
2**n - 1
Because the error is only roughly proportional to a power of
h, the above result is also approximate, but it is a much
better approximation.
We can apply this to all successive pairs of approximations
using the function
elimerror n (a:b:rest) = ((b*(2**n)-a)/(2**n-1)):(elimerror n1 (b:rest)))
Thus we obtain another sequence with error "eliminated" (in
reality just much reduced), which converges much more rapidly. The
only problem is that we do not know the value for n
and n1. Again, we are using a function for the estimation of
n, from [1].
order (a:b:c:rest) = round(log2((a-c)/(b-c) - 1))
Then we can finally define the function, which takes a sequence
(list) generated with progressively halving h, and improves
it:
improve as = elimerror (order as) as
And the derivative of the function will then be computed more
precisely by:
within eps (improve differentiate h0 f x)
We must note here that improve only works on sequences of
approximations computed using a parameter h, which is halved
before the computation of each approximation. Remarkably, the
result of improve is again such a sequence! And this
effectively allows us to "improve improve":
within eps (improve (improve (improve (differentiate h0 f x))))
One could even go further and define:
super s = map second (repeat improve s)
where
second (x, y) = y
This repeatedly constructs more and more improved sequences of
approximations from one another, then constructs a final sequence,
taking every second element (John Hughes states they are the best [1]) from each improved sequence.
Finally, from this super-sequence we get the first element
within our defined tolerance:
within eps (super (differentiate h0 f x))
Can these functions be implemented in XSLT? The answer is
"yes".
Because in the definition of super above an infinite list
is passed as an argument to the map function, we need to
implement one more XSLT function that simulates Haskell's lazy
evaluation. The buildListWhileMap function simulates two
infinite lists -- a list of parameter values, the latest of which
is calculated in the last iteration, and a list of "result" values,
that are calculated from the list of parameter values. It is passed
3 functions as parameters -- a generator function, which produces the new list of
parameters and the new list of results from the previous ones by using the
mapping function, which generates a value from
every element of the list of parameters. In this way the list of
parameters and the list of results will grow infinitely and this is only
avoided by having a controller
function implement the check for a stop criterion. Below is the
code of the buildListWhileMap function followed by a test example
that uses it to implement the differentiate function as defined
above.
buildListWhileMap
<xsl:stylesheet version = "1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:msxsl="urn:schemas-microsoft-com:xslt" exclude-result-prefixes = "xsl msxsl" >
<xsl:template name = "buildListWhileMap" > <xsl:param name = "pGenerator" select = "/.." /> <xsl:param name = "pParam0" select = "/.." /> <xsl:param name = "pController" select = "/.." /> <xsl:param name = "pContollerParam" select = "/.." /> <xsl:param name = "pMap" select = "/.." /> <xsl:param name = "pMapParams" select = "/.." /> <xsl:param name = "pElementName" select = "'el'" /> <xsl:param name = "pList" select = "/.." /> <xsl:param name = "pBaseList" select = "/.." />
<xsl:if test = "not($pController)" > <xsl:message terminate = "yes" >[buildListWhileMap]Error:
No pController specified: would cause infinite processing.
</xsl:message> </xsl:if>
<xsl:variable name = "vNewBaseListElement" > <xsl:if test = "$pMap" > <xsl:element name = "{$pElementName}" > <xsl:apply-templates select = "$pGenerator" > <xsl:with-param name = "pParams" select = "$pParam0" /> <xsl:with-param name = "pList" select = "$pBaseList" /> </xsl:apply-templates> </xsl:element> </xsl:if> </xsl:variable>
<xsl:variable name = "vElement" > <xsl:element name = "{$pElementName}" > <xsl:choose> <xsl:when test = "not($pMap)" >
<xsl:apply-templates select = "$pGenerator" > <xsl:with-param name = "pParams" select = "$pParam0" /> <xsl:with-param name = "pList" select = "$pList" /> </xsl:apply-templates>
</xsl:when> <xsl:otherwise>
<xsl:apply-templates select = "$pMap" > <xsl:with-param name = "pParams" select = "$pMapParams" /> <xsl:with-param name = "pDynParams" select = "msxsl:node-set($vNewBaseListElement)/*" /> <xsl:with-param name = "pList" select = "$pList" /> </xsl:apply-templates>
</xsl:otherwise> </xsl:choose> </xsl:element> </xsl:variable>
<xsl:variable name = "newList" > <xsl:copy-of select = "$pList" /> <xsl:copy-of select = "msxsl:node-set($vElement)/*" /> </xsl:variable>
<xsl:variable name = "newRTFBaseList" > <xsl:copy-of select = "$pBaseList" /> <xsl:copy-of select ="msxsl:node-set($vNewBaseListElement)/*" /> </xsl:variable>
<xsl:variable name = "vResultList" select = "msxsl:node-set($newList)/*" />
<xsl:variable name = "vResultBaseList" select = "msxsl:node-set($newRTFBaseList)/*" />
<xsl:variable name = "vAccept" > <xsl:apply-templates select = "$pController" > <xsl:with-param name = "pList" select = "$vResultList" /> <xsl:with-param name = "pParams" select = "$pContollerParam" /> </xsl:apply-templates> </xsl:variable>
<xsl:choose> <xsl:when test = "not(string($vAccept))" > <xsl:copy-of select = "$pList" /> </xsl:when> <xsl:otherwise>
<xsl:call-template name = "buildListWhileMap" > <xsl:with-param name = "pGenerator" select = "$pGenerator" /> <xsl:with-param name = "pParam0" select = "$pParam0" /> <xsl:with-param name = "pController" select = "$pController" /> <xsl:with-param name = "pContollerParam" select = "$pContollerParam" /> <xsl:with-param name = "pMap" select = "$pMap" /> <xsl:with-param name = "pMapParams" select = "$pMapParams"
/> <xsl:with-param name = "pElementName" select = "$pElementName"
/> <xsl:with-param name = "pList" select = "$vResultList"
/> <xsl:with-param name = "pBaseList" select = "$vResultBaseList"
/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
</xsl:stylesheet>
|
easyDiffList
<xsl:stylesheet version = "1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:msxsl="urn:schemas-microsoft-com:xslt" xmlns:myHalve="myHalve"
xmlns:myEasyDiffMap="myEasyDiffMap"
xmlns:myWithinController="myWithinController"
exclude-result-prefixes
= "xsl msxsl myHalve
myEasyDiffMap myWithinController"
>
<xsl:import href = "buildListWhileMap.xsl"
/>
<myHalve:myHalve/>
<myWithinController:myWithinController/>
<myEasyDiffMap:myEasyDiffMap/>
<xsl:template name = "easyDiffList"
> <xsl:param name = "pFun" select = "/.."
/> <xsl:param name = "pX"
/> <xsl:param name = "pH0" select = "0.1"
/> <xsl:param name = "pEps" select = "0.01"
/>
<xsl:variable name = "vMyHalveGenerator" select = "document('')/*/myHalve:*[1]"
/>
<xsl:variable name = "vmyWithinController" select = "document('')/*/myWithinController:*[1]"
/>
<xsl:variable name = "vmyEasyDiffMap"
select
= "document('')/*/myEasyDiffMap:*[1]"
/>
<xsl:variable name = "fx"
> <xsl:apply-templates select = "$pFun"
> <xsl:with-param name = "pParam" select = "$pX"
/> </xsl:apply-templates> </xsl:variable>
<xsl:variable name = "vrtfMapParams"
> <xsl:copy-of select = "$pFun"
/> <param> <xsl:value-of select = "$pX"
/> </param> <param> <xsl:value-of select = "$fx"
/> </param> </xsl:variable>
<xsl:variable name = "vMapParams"
select = "msxsl:node-set($vrtfMapParams)/*"
/>
<xsl:call-template name = "buildListWhileMap"
> <xsl:with-param name = "pGenerator"
select = "$vMyHalveGenerator"
/> <xsl:with-param name = "pParam0" select = "$pH0"
/> <xsl:with-param name = "pController"
select = "$vmyWithinController"
/> <xsl:with-param name = "pContollerParam" select = "$pEps"
/> <xsl:with-param name = "pMap" select = "$vmyEasyDiffMap"
/> <xsl:with-param name = "pMapParams" select = "$vMapParams"
/> </xsl:call-template> </xsl:template>
<xsl:template name = "myHalveGenerator"
match
= "*[namespace-uri()='myHalve']"
> <xsl:param name = "pParams" select = "/.."
/> <xsl:param name = "pList" select = "/.."
/>
<xsl:choose> <xsl:when test = "not($pList)"
> <xsl:value-of select = "$pParams"
/> </xsl:when> <xsl:otherwise> <xsl:value-of select = "$pList[last()] div 2"
/> </xsl:otherwise> </xsl:choose> </xsl:template>
<xsl:template name = "myWithinController"
match
= "*[namespace-uri()='myWithinController']"
> <xsl:param name = "pParams" select = "/.."
/> <xsl:param name = "pList" select = "/.."
/>
<xsl:variable name = "vLastDiff" select
= "$pList[last()] - $pList[last() - 1]"
/>
<xsl:choose> <xsl:when
test="not($vLastDiff < $pParams and $vLastDiff > (0 - $pParams)) and count($pList) <= 40 "
>1</xsl:when> </xsl:choose> </xsl:template>
<xsl:template name = "myEasyDiffMap"
match
= "*[namespace-uri()='myEasyDiffMap']"
> <xsl:param name = "pParams" select = "/.."
/> <xsl:param name = "pDynParams" select = "/.."
/> <xsl:param name = "pList" select = "/.."
/>
<xsl:variable name = "x" select = "$pParams[2]"
/>
<xsl:variable name = "h" select = "$pDynParams[1]"
/>
<xsl:choose> <xsl:when test = "not($h = 0)"
> <xsl:variable name = "fx_plus_h"
> <xsl:apply-templates select
= "$pParams[1]"
> <xsl:with-param name = "pParam" select = "$x + $h"
/> </xsl:apply-templates> </xsl:variable>
<xsl:variable name = "fx"
> <xsl:choose> <xsl:when test = "count($pParams) >= 3"
> <xsl:value-of select = "$pParams[3]"
/> </xsl:when> <xsl:otherwise> <xsl:apply-templates select
= "$pParams[1]"
> <xsl:with-param name = "pParam" select = "$x"
/> </xsl:apply-templates> </xsl:otherwise> </xsl:choose> </xsl:variable>
<xsl:value-of select = "($fx_plus_h - $fx) div $h"
/> </xsl:when> <xsl:otherwise> <xsl:value-of select = "$pList[last()]"
/> </xsl:otherwise> </xsl:choose> </xsl:template>
</xsl:stylesheet>
|
Let's now define the elimerror function. The
code bellow also contains an implementation for the auxiliary function
getOrder, which
calculates the order n that must be used in the elimination of
errors formula. This is the only place, where we're using essentially an
extension function in order to calculate round(log2(x)). In the current implementation
a Javascript extension function is used.
elimerror
<xsl:stylesheet version
= "1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:roundLog2="roundLog2">
<xsl:import href = "roundLog2.xsl"
/>
<xsl:template name = "elimError"
> <xsl:param name = "pList" select = "/.."
/> <xsl:param name = "pOrder" select = "-9999999"
/> <xsl:param name = "pv2__N" select = "0"
/>
<xsl:choose> <xsl:when test = "count($pList) < 3"
> <xsl:copy-of select = "$pList"
/> </xsl:when> <xsl:otherwise>
<xsl:variable name = "vOrder"
> <xsl:choose> <xsl:when test = "$pOrder < -9999998"
> <xsl:call-template name = "getOrder"
> <xsl:with-param name = "pList"
select = "$pList"
/> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:value-of select = "$pOrder"
/> </xsl:otherwise> </xsl:choose> </xsl:variable>
<xsl:variable name = "v2__N"
> <xsl:choose> <xsl:when test = "$pv2__N = 0"
> <xsl:call-template name = "pow"
> <xsl:with-param name = "base" select = "2"
/> <xsl:with-param name = "pow"
select = "$vOrder"
/> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:value-of select = "$pv2__N"
/> </xsl:otherwise> </xsl:choose> </xsl:variable>
<xsl:element name = "{name($pList[1])}"
> <xsl:value-of
select = "($pList[2] * $v2__N - $pList[1]) div ($v2__N - 1)"
/> </xsl:element>
<xsl:variable name = "vNewList"
select = "$pList[position() > 1]"
/>
<xsl:variable name = "vNewOrder"
> <xsl:call-template name = "getOrder"
> <xsl:with-param name = "pList" select = "$vNewList"
/> </xsl:call-template> </xsl:variable>
<xsl:call-template name = "elimError"
> <xsl:with-param name = "pList" select = "$vNewList"
/> <xsl:with-param name = "pOrder" select = "$vNewOrder"
/> <xsl:with-param name = "pv2__N" select = "$v2__N"
/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
<xsl:template name = "getOrder"
> <xsl:param name = "pList" select = "/.."
/>
<xsl:choose> <xsl:when test = "count($pList) < 3"
>1</xsl:when> <xsl:otherwise>
<xsl:variable name = "v1"
select = "($pList[1] - $pList[3])
div ($pList[2] - $pList[3])
- 1"
/>
<xsl:variable name = "v2"
>
<xsl:choose> <xsl:when test = "$v1 > 0"
> <xsl:value-of select = "$v1"
/> </xsl:when> <xsl:when test = "$v1 < 0"
> <xsl:value-of select = "(-1) * $v1"
/> </xsl:when> <xsl:otherwise>1</xsl:otherwise> </xsl:choose> </xsl:variable>
<xsl:value-of select = "roundLog2:roundLog2(string($v2))"
/> </xsl:otherwise> </xsl:choose> </xsl:template>
<xsl:template name = "pow"
> <xsl:param name = "base" select = "1"
/> <xsl:param name = "pow" select = "0"
/> <xsl:param name = "tmpResult" select = "1"
/>
<xsl:variable name = "result"
> <xsl:choose> <xsl:when test = "$pow >= 0"
> <xsl:value-of select = "$tmpResult * $base"
/> </xsl:when> <xsl:otherwise> <xsl:value-of select = "$tmpResult div $base"
/> </xsl:otherwise> </xsl:choose> </xsl:variable>
<xsl:variable name = "incr"
> <xsl:choose> <xsl:when test = "$pow >= 0"
> <xsl:value-of select = "- 1"
/> </xsl:when> <xsl:otherwise> <xsl:value-of select = "1"
/> </xsl:otherwise> </xsl:choose> </xsl:variable>
<xsl:choose> <xsl:when test = "$pow = 0"
> <xsl:value-of select = "$tmpResult"
/> </xsl:when> <xsl:otherwise> <xsl:call-template name = "pow"
> <xsl:with-param name = "base" select = "$base"
/> <xsl:with-param name = "pow" select = "$pow + $incr"
/> <xsl:with-param name = "tmpResult" select = "$result"
/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
</xsl:stylesheet> |
It is easy now to define the improve function.
improve
<xsl:stylesheet version = "1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:import href = "elimError.xsl"
/>
<xsl:template name = "improve"
> <xsl:param name = "pList" select = "/.."
/>
<xsl:variable name = "vOrder"
> <xsl:call-template name = "getOrder"
> <xsl:with-param name = "pList" select = "$pList"
/> </xsl:call-template> </xsl:variable>
<xsl:variable name = "v1Order"
> <xsl:choose> <xsl:when test = "$vOrder = 0"
>1</xsl:when> <xsl:otherwise> <xsl:value-of select = "$vOrder"
/> </xsl:otherwise> </xsl:choose> </xsl:variable>
<xsl:call-template name = "elimError"
> <xsl:with-param name = "pList" select = "$pList"
/> <xsl:with-param name = "pOrder" select = "$v1Order"
/> </xsl:call-template> </xsl:template>
</xsl:stylesheet> |
Finally, the improvedDiff function uses improve to
calculate the final improved derivative of a function f at point x. We are
producing a list of successively improved lists of values for f' and taking every second element of
these lists, until our tolerance criterion has been satisfied.
improvedDiff
<xsl:stylesheet version = "1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:msxsl="urn:schemas-microsoft-com:xslt" xmlns:myImproveGenerator="myImproveGenerator"
xmlns:myImproveController="myImproveController"
exclude-result-prefixes = "xsl msxsl myImproveGenerator myImproveController"
>
<xsl:import href = "improve.xsl"
/> <xsl:import href = "takeWhile.xsl"
/> <xsl:import href = "easyDiffList.xsl"
/>
<myImproveGenerator:myImproveGenerator/> <myImproveController:myImproveController/>
<xsl:output indent = "yes" omit-xml-declaration = "yes"
/>
<xsl:template name = "improvedDiff"
> <xsl:param name = "pFun" select = "/.."
/> <xsl:param name = "pX"
/> <xsl:param name = "pH0" select = "0.1"
/> <xsl:param name = "pEpsRough" select = "0.0001"
/> <xsl:param name = "pEpsImproved" select = "0.0000001"
/>
<xsl:variable name = "vMyImproveGenerator"
select = "document('')/*/myImproveGenerator:*[1]"
/>
<xsl:variable name = "vMyImproveController"
select = "document('')/*/myImproveController:*[1]"
/>
<xsl:variable name = "vrtfRoughResults"
> <xsl:call-template name = "easyDiffList"
> <xsl:with-param name = "pFun" select = "$pFun"
/> <xsl:with-param name = "pX" select = "$pX"
/> <xsl:with-param name = "pH0" select = "$pH0"
/> <xsl:with-param name = "pEps" select = "$pEpsRough"
/> </xsl:call-template> </xsl:variable>
<xsl:variable name = "vrtfResults"
> <xsl:call-template name = "takeWhile"
> <xsl:with-param name = "pGenerator"
select = "$vMyImproveGenerator"
/> <xsl:with-param name = "pParam0"
select = "msxsl:node-set($vrtfRoughResults)/*"
/> <xsl:with-param name = "pController"
select = "$vMyImproveController"
/> <xsl:with-param name = "pContollerParam"
select = "$pEpsImproved"
/> </xsl:call-template> </xsl:variable>
<xsl:variable name = "vResults"
select = "msxsl:node-set($vrtfResults)/*"
/>
<xsl:value-of select = "$vResults[last()]/*[2]"
/> </xsl:template>
<xsl:template name = "myImproveGenerator"
match
= "*[namespace-uri()='myImproveGenerator']"
>
<xsl:param name = "pList" select = "/.."
/> <xsl:param name = "pParams" select = "/.."
/>
<xsl:choose> <xsl:when test = "not($pList)"
> <xsl:call-template name = "improve"
> <xsl:with-param name = "pList" select = "$pParams"
/> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:call-template name = "improve"
> <xsl:with-param name = "pList" select = "$pList[last()]/*"
/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
<xsl:template name = "MyImproveController"
match
= "*[namespace-uri()='myImproveController']"
> <xsl:param name = "pList" select = "/.."
/> <xsl:param name = "pParams" select = "0.01"
/>
<xsl:choose> <xsl:when test = "count($pList) < 2"
>1</xsl:when> <xsl:otherwise>
<xsl:variable name = "vDiff"
select = "$pList[last()]/*[2] - $pList[last() - 1]/*[2]"
/>
<xsl:if test = "not($vDiff < $pParams
and $vDiff > (0 - $pParams))
and count($pList) <= 5 "
>1</xsl:if> </xsl:otherwise> </xsl:choose> </xsl:template>
</xsl:stylesheet> |
And here's a small example of using improvedDiff.
testImprovedDiff.xsl:
<xsl:stylesheet version = "1.0"   xmlns:xsl="http://www.w3.org/1999/XSL/Transform"   xmlns:myFunction="myFunction"   exclude-result-prefixes = "xsl myFunction"
>
<xsl:import href = "improvedDiff.xsl"
/>
<myFunction:myFunction/>
<xsl:output indent = "yes" omit-xml-declaration = "yes"
/>
<xsl:template match = "/"
> <xsl:variable name = "vMyFun" select
= "document('')/*/myFunction:*[1]"
/> f = x^2
x = 15
h0 = 0.1
EpsRough = 0.0001
EpsImproved = 0.000000000001
f'(x) = <xsl:text/>
<xsl:call-template name = "improvedDiff"
> <xsl:with-param name = "pFun" select = "$vMyFun"
/> <xsl:with-param name = "pX" select = "15"
/> <xsl:with-param name = "pH0" select = "0.1"
/> <xsl:with-param name = "pEpsRough" select = "0.0001"
/> <xsl:with-param name = "pEpsImproved" select = "0.000000000001"
/> </xsl:call-template>
f = x^2
x = 0.5
h0 = 0.1
EpsRough = 0.0001
EpsImproved = 0.0000000000001
f'(x) = <xsl:text/>
<xsl:call-template name = "improvedDiff"
> <xsl:with-param name = "pFun" select = "$vMyFun"
/> <xsl:with-param name = "pX" select = "0.5"
/> <xsl:with-param name = "pH0" select = "0.1"
/> <xsl:with-param name = "pEpsRough" select = "0.0001"
/> <xsl:with-param name = "pEpsImproved" select = "0.0000000000001"
/> </xsl:call-template>
f = x^2
x = 6
h0 = 0.1
EpsRough = 0.0001
EpsImproved = 0.0000000000001
f'(x) = <xsl:text/>
<xsl:call-template name = "improvedDiff"
> <xsl:with-param name = "pFun" select = "$vMyFun"
/> <xsl:with-param name = "pX" select = "6"
/> <xsl:with-param name = "pH0" select = "0.1"
/> <xsl:with-param name = "pEpsRough" select = "0.0001"
/> <xsl:with-param name = "pEpsImproved" select = "0.0000000000001"
/> </xsl:call-template></xsl:template>
<xsl:template name = "myFunction"
match
= "*[namespace-uri()='myFunction']"
> <xsl:param name = "pParam" select = "/.."
/> <xsl:value-of select = "$pParam * $pParam"
/> </xsl:template>
</xsl:stylesheet>
|
Results:
f = x^2 x = 15 h0 = 0.1 EpsRough = 0.0001 EpsImproved = 0.000000000001 f'(x) = 30.00000000000057
f = x^2 x = 0.5 h0 = 0.1 EpsRough = 0.0001 EpsImproved = 0.0000000000001 f'(x) = 0.9999999999999998
f = x^2 x = 6 h0 = 0.1 EpsRough = 0.0001 EpsImproved = 0.0000000000001 f'(x) = 12.000000000001286 |