Adapt Or Try – a.k.

Over the last few months we have been looking at how we might approximate the solutions to ordinary differential equations, or ODEs, which define the derivative of one variable with respect to another with a function of them both. Firstly with the first order Euler method, then with the second order midpoint method and finally with the generalised Runge-Kutta method.
Unfortunately all of these approaches require the step length to be fixed and specified in advance, ignoring any information that we might use to adjust it during the iteration in order to better trade off the efficiency and accuracy of the approximation. In this post we shall try to automatically modify the step lengths to yield an optimal, or at least reasonable, balance.

A Kutta Above The Rest – a.k.

We have recently been looking at ordinary differential equations, or ODEs, which relate the derivatives of one variable with respect to another to them with a function so that we cannot solve them with plain integration. Whilst there are a number of tricks for solving such equations if they have very specific forms, we typically have to resort to approximation algorithms such as the Euler method, with first order errors, and the midpoint method, with second order errors.
In this post we shall see that these are both examples of a general class of algorithms that can be accurate to still greater orders of magnitude.

Finding The Middle Ground – a.k.

Last time we saw how we can use Euler's method to approximate the solutions of ordinary differential equations, or ODEs, which define the derivative of one variable with respect to another as a function of them both, so that they cannot be solved by direct integration. Specifically, it uses Taylor's theorem to estimate the change in the first variable that results from a small step in the second, iteratively accumulating the results for steps of a constant length to approximate the value of the former at some particular value of the latter.
Unfortunately it isn't very accurate, yielding an accumulated error proportional to the step length, and so this time we shall take a look at a way to improve it.

Out Of The Ordinary – a.k.

Several years ago we saw how to use the trapezium rule to approximate integrals. This works by dividing the interval of integration into a set of equally spaced values, evaluating the function being integrated, or integrand, at each of them and calculating the area under the curve formed by connecting adjacent points with straight lines to form trapeziums.
This was an improvement over an even more rudimentary scheme which instead placed rectangles spanning adjacent values with heights equal to the values of the function at their midpoints to approximate the area. Whilst there really wasn't much point in implementing this since it offers no advantage over the trapezium rule, it is a reasonable first approach to approximating the solutions to another type of problem involving calculus; ordinary differential equations, or ODEs.

Finally On An Ethereal Orrery – student

Over the course of the year, my fellow students and I have been experimenting with an ethereal orrery which models the motion of heavenly bodies using nought but Sir N-----'s laws of gravitation and motion. Whilst the consequences of those laws are not generally subject to solution by mathematical reckoning, we were able to approximate them with a scheme that admitted errors of the order of the sixth power of the steps in time by which we advanced the positions of those bodies.
We have thus far employed it to model the solar system itself, uniformly distributed bodies of matter and the accretion of bodies that are close to Earth's orbit about the Sun. Whilst we were most satisfied by its behaviour, I should now like to report upon an altogether more surprising consequence of its engine's action.

Further Still On An Ethereal Orrery – student

Recently, my fellow students and I constructed a mathematical orrery which modelled the motion of heavenly bodies employing Sir N-----'s laws of gravitation and motion, rather than clockwork, as its engine. Those laws state that bodies are attracted toward each other with a force proportional to the product of their masses divided by the square of the distance between them, that a body will remain at rest or in constant motion unless a force acts upon it, that if a force acts upon it then it will be accelerated in the direction of that force at a rate proportional to its strength divided by its mass and that, if so, it will reciprocate with an opposing force of equal strength.
Its operation was most satisfactory, which set us to wondering whether we might use its engine to investigate the motions of entirely hypothetical arrangements of heavenly bodies and I should now like to report upon our progress in doing so.

Further On An Ethereal Orrery – student

Last time we met we spoke of my fellow students' and my interest in constructing a model of the motion of heavenly bodies using mathematical formulae in the place of brass. In particular we have sought to do so from first principals using Sir N-----'s law of universal gravitation, which states that the force attracting two bodies is proportional to the product of their masses divided by the square of the distance between them, and his laws of motion, which state that a body will remain at rest or in constant motion unless a force acts upon it, that it will be accelerated in the direction of that force at a rate proportional to its magnitude divided the body's mass and that a force acting upon it will be met with an equal force in the opposite direction.
Whilst Sir N----- showed that a pair of bodies traversed conic sections under gravity, being those curves that arise from the intersection of planes with cones, the general case of several bodies has proved utterly resistant to mathematical reckoning. We must therefore approximate the equations of motion and I shall now report on our first attempt at doing so.

On An Ethereal Orrery – student

My fellow students and I have lately been wondering whether we might be able to employ Professor B------'s Experimental Clockwork Mathematical Apparatus to fashion an ethereal orrery, making a model of the heavenly bodies with equations rather than brass.
In particular we have been curious as to whether we might construct such a model using nought but Sir N-----'s law of universal gravitation, which posits that those bodies are attracted to one another with a force that is proportional to the product of their masses divided by the square of the distance between them, and laws of motion, which posit that a body will remain at rest or move with constant velocity if no force acts upon it, that if a force acts upon it then it will be accelerated at a rate proportional to that force divided by its mass in the direction of that force and that it in return exerts a force of equal strength in the opposite direction.

A Measure Of Borel Weight – a.k.

In the last few posts we have implemented a type to represent Borel sets of the real numbers, which are the subsets of them that can be created with countable unions of intervals with closed or open lower and upper bounds. Whilst I would argue that doing so was a worthwhile exercise in its own right, you may be forgiven for wondering what Borel sets are actually for and so in this post I shall try to justify the effort that we have spent on them.

A Borel Universe – a.k.

Last time we took a look at Borel sets of real numbers, which are subsets of the real numbers that can be represented as unions of countable sets of intervals Ii. We got as far as implementing the ak.borelInterval type to represent an interval as a pair of ak.borelBound objects holding its lower and upper bounds.
With these in place we're ready to implement a type to represent Borel sets and we shall do exactly that in this post.

A Decent Borel Code – a.k.

A few posts ago we took a look at how we might implement various operations on sets represented as sorted arrays, such as the union, being the set of every element that is in either of two sets, and the intersection, being the set of every element that is in both of them, which we implemented with ak.setUnion and ak.setIntersection respectively.
Such arrays are necessarily both finite and discrete and so cannot represent continuous subsets of the real numbers such as intervals, which contain every real number within a given range. Of particular interest are unions of countable sets of intervals Ii, known as Borel sets, and so it's worth adding a type to the ak library to represent them.

Finally On A Calculus Of Differences – student

My fellow students and I have spent much of our spare time this past year investigating the similarities between the calculus of functions and that of sequences, which we have defined for a sequence sn with the differential operator

  Δ sn = sn - sn-1

and the integral operator
  n
  Δ-1 sn = Σ si
  i = 1
where Σ is the summation sign, adopting the convention that terms with non-positive indices equate to zero.

We have thus far discovered how to differentiate and integrate monomial sequences, found product and quotient rules for differentiation, a rule of integration by parts and figured solutions to some familiar-looking differential equations, all of which bear a striking resemblance to their counterparts for functions. To conclude our investigation, we decided to try to find an analogue of Taylor's theorem for sequences.

Further Still On A Calculus Of Differences – student

For some time now my fellow students and I have been whiling away our spare time considering the similarities of the relationships between sequences and series and those between the derivatives and integrals of functions. Having defined differential and integral operators for a sequence sn with

  Δ sn = sn - sn-1

and
  n
  Δ-1 sn = Σ si
  i = 1
where Σ is the summation sign, we found analogues for the product rule, the quotient rule and the rule of integration by parts, as well as formulae for the derivatives and integrals of monomial sequences, being those whose terms are non-negative integer powers of their indices, and higher order, or repeated, derivatives and integrals in general.

We have since spent some time considering how we might solve equations relating sequences to their derivatives, known as differential equations when involving functions, and it is upon our findings that I shall now report.

Further On A Calculus Of Differences – student

As I have previously reported, my fellow students and I have found our curiosity drawn to the calculus of sequences, in which we define analogues of the derivatives and integrals of functions for a sequence sn with the operators

  Δ sn = sn - sn-1

and
  n
  Δ-1 sn = Σ si
  i = 1
respectively, where Σ is the summation sign, for which we interpret all non-positively indexed elements as zero.

I have already spoken of the many and several fascinating similarities that we have found between the derivatives of sequences and those of functions and shall now describe those of their integrals, upon which we have spent quite some mental effort these last few months.

Further On A Calculus Of Differences – student

As I have previously reported, my fellow students and I have found our curiosity drawn to the calculus of sequences, in which we define analogues of the derivatives and integrals of functions for a sequence sn with the operators

  Δ sn = sn - sn-1

and
  n
  Δ-1 sn = Σ si
  i = 1
respectively, where Σ is the summation sign, for which we interpret all non-positively indexed elements as zero.

I have already spoken of the many and several fascinating similarities that we have found between the derivatives of sequences and those of functions and shall now describe those of their integrals, upon which we have spent quite some mental effort these last few months.

On A Calculus Of Differences – student

The interest of my fellow students and I has been somewhat piqued of late by a curious similarity of the relationship between sequences and series to that between the derivatives and integrals of functions. Specifically, for a function f taking a non-negative argument x, we have
  x
  F(x) = f(x) dx
  0
  f(x) = d F(x)
  dx

and for a sequence s having terms

  s1, s2, s3, ...

we can define a series S with terms
  n
  Sn = s1 + s2 + s3 + ... + sn = Σ si
  i = 1
where Σ is the summation sign, from which we can recover the terms of the sequence with

  sn = Sn - Sn-1

using the convention that S0 equals zero.
This similarity rather set us to wondering whether we could employ the language of calculus to reason about sequences and series.

On A Calculus Of Differences – student

The interest of my fellow students and I has been somewhat piqued of late by a curious similarity of the relationship between sequences and series to that between the derivatives and integrals of functions. Specifically, for a function f taking a non-negative argument x, we have
  x
  F(x) = f(x) dx
  0
  f(x) = d F(x)
  dx

and for a sequence s having terms

  s1, s2, s3, ...

we can define a series S with terms
  n
  Sn = s1 + s2 + s3 + ... + sn = Σ si
  i = 1
where Σ is the summation sign, from which we can recover the terms of the sequence with

  sn = Sn - Sn-1

using the convention that S0 equals zero.
This similarity rather set us to wondering whether we could employ the language of calculus to reason about sequences and series.

Integration, Quasi Mode – a.k.

Last time we saw how it was possible to use uniformly distributed random variables to approximate the integrals of univariate and multivariate functions, being those that take numbers and vectors as arguments respectively. Specifically, since the integral of a univariate function is equal to the net area under its graph within the interval of integration it must equal its average height multiplied by the length of that interval and, by definition, the expected value of that function for a uniformly distributed random variable on that interval is the average height and can be approximated by the average of a large number of samples of it. This is trivially generalised to multivariate functions with multidimensional volumes instead of areas and lengths.
We have also seen how quasi random sequences fill areas more evenly than pseudo random sequences and so you might be asking yourself whether we could do better by using the former rather than the latter to approximate integrals.

Clever you!

Integration, Quasi Mode – a.k.

Last time we saw how it was possible to use uniformly distributed random variables to approximate the integrals of univariate and multivariate functions, being those that take numbers and vectors as arguments respectively. Specifically, since the integral of a univariate function is equal to the net area under its graph within the interval of integration it must equal its average height multiplied by the length of that interval and, by definition, the expected value of that function for a uniformly distributed random variable on that interval is the average height and can be approximated by the average of a large number of samples of it. This is trivially generalised to multivariate functions with multidimensional volumes instead of areas and lengths.
We have also seen how quasi random sequences fill areas more evenly than pseudo random sequences and so you might be asking yourself whether we could do better by using the former rather than the latter to approximate integrals.

Clever you!