[EM] High Order Numerical Cubature2.0

[Forest Simmons]

This is a slight revision of the original with some clarifications to
prevent all posible misunderstandings! (Sure)

In particular, if G is a set of points and V is a set of vectors, let G+V
be the set obtained by displacing each point of G by every vector of V:

G+V={g+v| (g,v) in G×V)},

where G×V is the Cartesian product of G and V.

So in general (when there are no double representations of points) the
number of points in this kind of sum will be the same as #(G×V), wich is
just (#G)*(#V).

Given a simplex (the convex hull of a finite set of points having affine
> independence) we form a tree whose root node is the average of the vertices
> of the simplex (i.e. the "barycenter" of the simplex), and whose
> descendants become denser in the interior of the simplex with each
> successive generation.
>
> This "space filling" has to be done with sufficient fractal self
> symmetrical regularity to ensure that our method can be highly accurate and
> efficient. Don't worry ... it turned out to be way simpler than I could
> have possibly hoped for!
>
> As we said, the first node of the tree is the baryceenter of the simplex.
> The immediate children of that node are the points precisely half way from
> the barycenter to the respective vertices of the simplex. [The simplex
> itself is the convex hull of these vertices.]
>
> The respective vectors from the barycenter to the vertices form a set V of
> displacement vectors that serve as the only directions needed for finding
> all of the children of every node.
>
> Once we know the directions, the only question that remains is "how far?"
> (in those directions).
>
> Answer: the distance from a parent to a child is half as far as it was in
> the previous generation ... i.e. half as far as from grandparent to parent.
>
> Now, let G(k) represent the set of nodes in the k_th generation down from
> the root node. Then G(1) and G(2), respectively, represent the children and
> grandchildren of the barycenter, while G(0) consists of only the barycenter
> itself.
>

In summary, for each natural number k, the k_th generation is obtained from
the previous generation by the recursive formula G(k)=G(k-1)+V/2^k .

Now let f be a real valued function defined at every node of our tree.
>
> And let A(k) be the average of all of the f values of all of the nodes of
> the set G(k), i.e.
>

A(k)=Sum{f(g)| g in G(k)}/#G(k).

>
> If f is a reasonable function, then as k increases, A(k) approaches the
> average value of f on the simplex, which is defined by calculus as the
> integral of f over the simplex, divided by the d-dimensional capacity of
> the simplex. The "capacity" of a simplex is its length, area, volume, etc
> ... depending on the dimension d of the simplex.
>
> Let's denote the limiting value of A(k) by the Greek letter Alpha(f).
>
> In particular, when f is a density function, Alpha(f) is the average
> density of the simplex, because the integral of density is mass, and mass
> divided by capacity is average density ... in units of g/(cm)^d or kg/m^d,
> where d is the dimension of the simplex.
>
> Similarly, if f represents temperature or pressure, Alpha(f) will be the
> average temperature or pressure experienced by the simplex.
>
> If you need to know the mass of the simplex (when f is its density
> function), just multply its average density Alpha(f) by its capacity.
>
> To get the capacity of a simplex, let M  be a matrix whose rows are the
> respective displacement vectors from one fixed vertex v0 to the others ...
> v1-v0, v2-v0, etc.
>
> The capacity of the d-dimensional simplex is the square root of the
> determinant of the matrix product of M and its transpose M', divided by d.
> In other words...
>
> Capacity=Sqrt(det MM')/d
>

When M is a square matrix this capacity computation is simply

Capacity=|det M|/d.

That's everything ... except the Richardson extrapolation to increase the
> order of convergence from second order to order 2n, where n depends on the
> number of Richardson transformations of the sequence [for more information
> on the rate of convergence or order of accuracy, see the last remark below]:
>
> We start with the sequence
> A(0), A(1), .... A(j), ...
>
> Then transform the A sequence to a B sequence, where ...
>
> B(0)=(4A(1)-A(0))/3 ...
> B(j)=(4A(j+1)-A(j))/3 ...
>
> Then transform the B's to a sequence of C's:
>
> C(j)=(16B(j+1)-B(j))/15 ...
>
> .......
>
> D(j)=(4^3*C(j+1)-C(j))/(4^3-1)
>
> etc.
>
> The suggested order is ..
>
> A0), A(1),B(0), A(2), B(1), C(0), A(3),B(2), C(1), D(0), etc....
>
> At each step go as far down the alphabet as possible, given the results
> needed from the previous steps.
>
> When you reach a new letter, i.e. the zero_th term in a new sequence,
> compare it with the most recent value of the preceding letter to see if the
> approximation is still progressing, or if it has reached a point of
> diminishing returns.
>
> Test it on polynomials: by the time the extrapolation reaches the n_th
> letter of the alphabet, any polynomial function f of degree 2n or less
> should be averaged quite precisely (up to roundoff error).
>

-Forest

>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220205/25b7532c/attachment.html>