Some time ago I was asked the question: do you know how to do a change of variables in a multi-dimensional definite integral? I thought I knew, but I was wrong. I only know how to do a change of variable in a multi-dimensional indefinite integral.
This question really intrigued me. Of course, this is such an obvious question, I just started pulling out textbook after textbook off my bookshelf, expecting to find the answer in one of them. Much to my surprise, not a single one of them covered this topic! The indefinite case was covered in detail, but the definite case was either not mentionned or glossed over. But if one is trying to implement an algorithm to perform such a change of variable, the details are crucial! Wikipedia actually has the best coverage that I have found. But it is still nowhere good enough to write a piece of code.
I have been able to figure out some cases (via pen and paper), but anytime I try to generalize my ideas, things fall apart. I won't spell out what I have here (yet), as I think this is kind of a fun mathematical problem that some of you might enjoy puzzling out. I won't even show you the neat counter-examples I have to overly simplistic approaches to the problem. I am rather hoping that no one will crack it too fast! In that case, I think it would be fun if we could work out the details here on primes.
Comments
In my experience
this is one of those subjects of Mathematics that physicists learn in Physics courses (because mathematicians do not teach them). Typically, identify the symmetries of the system and choose coordinates "adapted" to these symmetries so that eg. the dependency of the functions, the components of the vector fields and the limits of the integrals, when transformed to such coordinates, take the simplest form.
No systematic theory is normally used to convey these techniques, but much of it is basically use of invariance under discrete and Lie groups.
Rudin, RCA
Perhaps I do not quite understand the question, but Rudin "Real and Complex Analysis" has it (never liked that great book as a student): Let be f a C^1 function on V, V bounded and open IR^k and phi: W -> V a differentiable homeomorphism (or what notion one prefers), psi its inverse. inv := f -> (f@@(-1)); psi:=inv(phi); (-1) psi := phi Int(f(x),x=`V` ..``) = Int(f(phi(xi))*detJacobi(phi)(xi),xi =`W` ..``); `W`= psi(`V`) ; / / | | | f(x) dx = | f(phi(xi)) detJacobi(phi)(xi) dxi, | | / / V W (-1) W = (phi )(V) where detJacobi is the determinant of the Jacobian. For the 1-dimensional case that equals D, the differential, and it reads as Int(f(x),x=`V` ..``) = Int(f(phi(xi))*detJacobi(phi)(xi),xi =`W` ..``): eval(%, detJacobi=D); / / | | | f(x) dx = | f(phi(xi)) D(phi)(xi) dxi | | / / V W where now V and W can be thought as (an union of) intervals. Now using intervals we write the integrals in the common way I=[`a...b`], `J`= psi(`I`) ; Int(f(x),x=a ..b) = Int(f(x),x=`I` ..``), `...`; (-1) I = [a...b], J = (phi )(I) b / / | | | f(x) dx = | f(x) dx, ... | | / / a I and get Int(f(x),x=a ..b) = Int(f(phi(xi))*diff(phi(xi),xi),xi = psi(a) .. psi(b)); (-1) b (phi )(b) / / | | / d \ | f(x) dx = | f(phi(xi)) |--- phi(xi)| dxi | | \dxi / / / a (-1) (phi )(a) which is the same as using "Int(f(x),x=a ..b); Change(%, x=phi(xi));" getting the ugly 'RootOf' notation. For the Jacobian one would need to know the number of variables to set up a general procedure like the 'D' operator, but I only have a lame way (which works more or less for procedures, but not for functions like 'exp', I would need to re-write it as proc(x) x -> [exp(x)] end proc as vector version). detJ := proc( h::procedure ) local n,X,i,Y, result; [op(eval(h))]; remove(has,%,{arrow,operator}); n:=nops(%); # number of variables of h if(n < 1) then return NULL; elif n=1 then # return D(h) else end if; X:=seq( cat( x, i ), i = 1..n); i:='i': Y:= seq(h(X)[i], i = 1 .. n); i:='i': result:=Student[MultivariateCalculus][Jacobian]([Y], [X], output = matrix); if(1 < n) then result:=LinearAlgebra[Determinant](result) end if; unapply(result, X); end proc; One needs the partial derivatives to commute to use Maple's Jacobian, yes? I have not tried it for product situations.The integration domain
I have both those great books too. And note that there is one thing you are missing (in the n-dimensional case with n>1): How do you write the transformation from domain V to domain W?
In other words, the hard part is to go from a description of a domain V using one set of coordinates and get a description of W in the new coordinates after the change of variables. In the 1-D case, phi^(-1) works fine; in general, you still have W=(phi@@(-1))(V), but the hard part is to make that explicit.
For some classes of phi, I think I know how to make this work.
Invariance under SO(2)
Let us take this example. What needs to be done first is calculate the integral over R^2:
So, a sketch of an algorithm would be:
1. Recognize that the integrand is invariant under SO(2).
2. Verify that the domain R^2 is invariant under SO(2).
3. Identify the polar coordinate system (r,theta) as the orthogonal coordinate system "adapted" to SO(2): the curves of constant r are the orbits of SO(2).
4. Transform the integral to these polar coordinates, factorizing it as a product of an integral on r and and one on theta.
5. Calculate these 1D integrals and multiply them.
May be that someone with an algorithmic mind could transform this sketch into something useful.
Domain given by an inequality
One simple case is when the domain is given by an inequality or a system of inequalities. Something like f(x,y,z)<=0. In this case, if the change of variables is given by formulas x=X(u,v,w), y=Y(u,v,w), and z=Z(u,v,w), then the new domain is defined by an inequality f(X(u,v,w),Y(u,v,w),Z(u,v,w))<=0 in this example. One thing that still has to be checked in addition to that is that the transformation is bijective.
Not talking that multidimensional integrals are not defined in Maple though - except the case of repeated 1-dimensional integrals.
Alec
VectorCalculus:-int
appears to have some "geometric" knowledge, but I have not inspected its code in detail to know whether it just does repeated 1-dimensional integrals or something else.
Repeated
Last Maple version that I used (few years ago) was Maple 10. In that version, if I remember correctly, VectorCalculus:-int provided just a shorthand notation for a repeated integral. Many things could change since then. Especially, as Joe Riel mentioned, in new DifferentialGeometry package. It would be interesting if more general multidimensional integrals were introduced.
An example
Here is an example. Suppose that the integration domain is given by inequality 1<=x^2+y^2<=4. Changing to polar coordinates requires 2 inequality conditions for bijectivity (excluding subsets of measure 0 here and there), r>=0 and, say, 0<=phi<=2 pi. So the new domain is given by 3 inequalities, r>=0, 0<=phi<=2 pi, and 1<= r^2 <=4 which can be reduced to 2 ranges phi=0..2 pi and r=1..2.
Alec
delete
Apparently, it is only possible by asking Will to do it.
[I have not replied to that "duplicated" post so that Will could delete your post and this one]
bijectivity does not hold
for r=0, so, these conditions for bijectivity restrict to r>0, if I understand correctly what you mean.
Excluding some subsets of measure 0
That's why I wrote "excluding some subsets of measure 0". The integration domain should be compact (i.e. closed and bounded) for usual Riemannian integrals, and that can not be achieved by some changes of variables (including polar coordinates.) Another exclution is for phi, it should be either 0<phi<=2 pi or 0<=phi<2 pi. That's the main reason why excluding subsets of measure 0 is a usual part of standard integration theorems.
Alec
Lebesgue integral
is what you mean then?
There are sets that curvilinear coordinate charts do not cover like the origin in spherical coordinates and the axis of symmetry in cylindrical coordinates. You mean to "complete" the chart including them somehow to get a closed integration region?
Lebesgue integral
I was talking about the change of variables in Riemannian integrals.
From computational point of view, there is not a big difference between Riemannian and Lebesgue integral - they give the same value for domains (and functions) on which Riemannian integral is defined (leaving aside such things that for Lebesgue integral, say, on the segment from 1 to 2, the orientation of the segment doesn't make any difference - there are no such things as Lebesgue integral for x from 1 to 2 or from 2 to 1 - it is always "from 1 to 2"). The integral in Maple is not Riemannian and not Lebesgue - it gives 1/2 for the integral of Dirac delta from 0 to infinity which doesn't have sense in any mathematical content.
Repeated integrals, however, represent a different mathematical object which can be correctly defined as integration of differential forms. The practical meaning of it is that the change of variables in the integrals of differential forms and in Riemannian or Lebesgue integrals is done differently - the integrand is multiplied by the Jackobian for differential forms and by the absolute value of the Jackobian for Riemannian or Lebesgue integrals.
For example, for the area of unit square given as int int 1 dxdy over the square and represented in Maple as int((int 1, y=0..1) ,x=0..1), if we change x to u=1-x, then the first integral should change to int int 1 dudy over the same square, but the repeated integral should be changed to int((int -1, y=0..1) ,u=1..0).
That, probably, introduces some additional difficulties to the correct implementation of the change of variables.
Alec
Parity of the transformation
is indeed an additional issue.
However, my question was about the meaning of your statement "subsets of measure 0" in the context of the Riemannian integral, as measure is not a concept used of this integral, as I know it.
Yes, the integral in "Maple sense" is a melange. i would be very happy if it were available a "DistributionTool" package that provides a 'diff and 'int' in distributional sense, so that ordinary 'diff and 'int' behave as expected for ordinary functions.
And I have made efforts to get removed that aberration of 1/2 for the integral of Dirac delta from 0 to infinity, which were unsuccesful up to now.
Riemannian integral
For Lebesgue integral, that may be not true (in case of distributions). For example, while the Lebesgue integral of the Dirac delta over the line is 1, it is 0 for the line without 0. For Riemannian integral, that's how the change of variable theorem is usually formulated - requiring bijectivity (or inversability in other words, or 1-1 and on) of the transformation on some subsets of V and W - so that the most useful cases, such as changing to polar coordinates be covered. And you are right - in usual Calculus courses the Riemannian measure is not defined. Different textbooks use different approaches. One way to define the subset with Riemannian measure 0 is that it can be covered by measurable domains with measure epsilon for any epsilon>0. In this content, the measure means volume in 3d case, or area in 2d case. In good real analysis courses the Riemannian measure should be covered.
Posting twice
For some reason, that was posted twice and I couldn't find the "Delete" button or link. Is it possible to delete your own post here (that doesn't have replies)?
Alec
well ...
2. I am aware that the practical problem is to find appropriate transforms & coordinates.
But that fits into Alejandro Jakubi's answers above :-)
Think in more dimensions
For D>=3 you do not have isomorfism with C. So, in general, you need to think geometrically and you need to identify the coordinate system from knowledge of the symmetry properties. As far as these symmetry properties are computable (I beleive that they are in many cases of interest), there should be no problem to identify the coordinate system.
DifferentialGeometry
The DifferentialGeometry package can be effectively used here, however, that doesn't help with the reparametrization of the domain, which is Jacques' issue (here it is trivial):
formidible challenge
In general, finding W=(phi@@(-1))(V) explicitly is very difficult. It almost seems like an algorithm that could do this would be an algorithm that endows a computer with "visualization" powers.
Think about Matthias Kawski's intdraw3d package for Maple...the first page of this preprint might be relevant to this discussion:
http://math.la.asu.edu/~kawski/preprints/97mapletech.ps
This reminds me of the challange encountered in a complex variables course, where one tries to find an explict one-to-one analytic map from the unit disk to a simply connected proper domain of C (Riemann mapping theorem). In general it is impossible to explicitly compute the map. For certain domains, there are nice techniques.
Breaking it down
It's worth thinking about some special cases. In principle, the general change of variables can be broken down into individual steps, where each step either changes the "inside" variable only or interchanges the order of two integrations. Thus going from int_R f(x,y,z) dx dy dz to an integral ds dt du might be done in the following steps:
dx dy dz -> du dy dz -> dy du dz -> dt du dz -> dt dz du -> dz dt du -> ds dt du
domains
Alejando, Thx for encouraging :-) It's simply that my geometric
thinking ignores group operations ...
Anyway: yes, the general approach may be difficult. But practical
most stuff is done along recipies or proved concepts, even in one-
dimensional cases.
The Wiki examples just show that (ok, they are educational): these
are transforms, where phi^(-1)(V) can be described and turns out to
be useful.
Kawski's article/code on visualization might be of help for more.
However my starting point was: "What is the general formula?"
The point is: in dim=1 (if the transform is bijective [which may
be the first error to do]) the pre-image automatically is an inter-
val (if such is given).
Already for curve integrals and complex variables it is not so clear
what to do to achieve at a simplier task - so why should it be the
case in a general setting?
PS: I like Joe Riel's solution, even it is not quite handy ...
was not aware of this :-(
Moving things along
A few comments on the various posts:
Ok, let's be more specific. Let's consider something simple: a 2D integral over a domain 0..1 X 0..1 and a linear change of coordinates given by a 2x2 matrix A. We know exactly how to change the integrand f(x,y) into f(u,v) *|det(A)| via A. But how does the boundary change? What conditions on A must be imposed for this to make sense? This should generalize to n-dimensional integrals and a linear change of coordinates over an arbitrary rectangle R fairly easily. This should be the first case to be worked out in full detail.
The next case to work out is problably the ``rectifying transformation'', that is a 2D integral like
int(int(f(x,y), x=a(y)..b(y)),y=c..d)
where we try to simultaneously 'straighten' a and b [one definitely needs to impose conditions on a and b for this to be possible!].
Another case to work out in detail is how some particular domains transform under rectangular <-> polar coordinate transforms.
The first part
of this first example seems quite simple and probably, for linear changes of coordinates, it would be not much more complex and profitable to generalize a little bit to regions bounded by segments as straight lines map into straight lines by these transformations.
Eg a quadrilateral figure whose sides are given by equations of the form a_i*x+b_i*y=c_i, i=1..4, such that four pairwise intersections (corners of the quadrilateral exist). Your square is a particular case.
Let X be the column matrix of the coordinates (x,y), U idem for coordinates (u,v), A the transformation matrix such that X=AU, B the matrix of the coefficients (a_i,b_i), C the column matrix of the coefficients c_i, such that BX=C.
Then, the equations for the sides of the transformed quadrilateral are BAU=C. This seems trivial.
In regards to conditions, this needs thinking a bit. A necesary condition for the region to be a quadrilateral is that the triples (a_i,b_i,c_i) are not multiple of each other. A similar conditions should apply replacing with the coefficients of the matrix BA. An additional condition is that no three lines intersect at a point.
Is this what you point to?
Linear changes of coordinates
[Sorry for the wait, I've been crazy-busy; I will be away for most of the next 2 weeks, so expect answers to remain slow]
Your reasoning seems sound, and yet it isn't necessarily useful! The point is that Maple has no well-integrated facility for integration over arbitrary shapes [although it does have some, but they are well hidden]. In other words, the "most useful" problem to solve is how to take an integral of the form int(int(f(x,y),y=a(x)..b(x)),x=c..d) and turn it into int(int(g(u,v),u=a1(v)...a2(v)),v=c1..d1). For quadilaterals which are not axis-aligned, your method is no so straightforward to apply. Working out the details is no hard, but it is nevertheless more subtle than at first appears.
Note that in this way of looking at the problem, the degeneracy conditions are actually a fair bit easier to check!
By a linear changes of coordinates
the domain 0..1 X 0..1that you propose will transform (generically) into a quadrilateral with no side aligned to the (u,v) axes. So, I do not see how to avoid dealing with this issue.
Right
You are quite right. But for a quadrilateral which starts axis-aligned into a general one, the formulas for adjusting the bounds to 'respect' (u,v) axes are not too bad. And this is one of the formulas that really needs figured out.
In a slightly more general case, geometry really kicks in: what if the shape you are integrating over is axis-convex in its original formulation [essentially true by definition], but no longer so after a change of variables? There is then no real way to express the new integral in these new coordinates! However, for convex shapes, it should always work. But isn't that interesting though, that out of seemingly nowhere convexity shows up as a crucial condition? I certainly did not expect that a priori, but only after working on this problem for a while; of course now it seems obvious!
axis-convex
What does it mean?
axis convex
It means convex but only on paths which are aligned with an axis rather than between arbitrary points, ie on straight lines parallel to an axis.
I have no idea if there is standard terminology for this -- there might not be. I just 'invented' "axis convex" as it seemed like the obvious description of what I had in mind.
The standard terminology
The standard terminology for 2-dimensional case is Type I if it's "y-axis convex", and Type II if it is "x-axis convex".
Alec
definition
Last night I searched Google for a definition. There were a couple uses, but no clear definitions. This thumbnail, or what I can glean from it, seems similar to your, "L is said to be axis-convex if each line parallel to its axis which ....; however, the author uses "axis" to indicate an axis of symmetry of the object and not the coordinate axes. The rest, alas, http://www.jstor.org/pss/2154703, requires a subscription to JSTOR.
definition and visualization
Yes, I am asking because a search for definitions and explanations had led me to restricted resources to which I do not have access.
I have yet difficulties to understand this:
as "convex" is used as a property of "curved" lines not stright lines. Could you post or give a link to a picture of something that is axis convex and something that is not? Is there any relation with the pictures in this article? (whose nomenclature I find at least unusual: "A function f is said to be concave if − f is convex.")
examples
Consider the area bounded by the x-axis and [x,y] = [t,t^2+1], t = -1..1. It is y-axis-convex but not x-axis convex. At least that is my understanding. As an example of something that is both x and y axis-convex but not convex, consider an elbow:
Here's link to books.google.com/books that concludes the excerpt I previously posted: "We say that L is axis-convex if each line parallel to its axis that meets it does so in a (possibly degenerate) line segment."
Now I see it
Thank you for these examples. It means then convex in the 1D set sense for a whole family of parallel stright lines crossing the region.
axis convexity
Now that I seem to understand this definition, the issue you pose seems to be start from an axis-convex region for all the n variables (apparently it implies R^n convexity). Transform by a general (but overall smooth) change of coordinates and you may get in the new variables a region that is non axis-convex for at least one coordinate (so it is not R^n convex either).
So, you should first recognize this nonconvexity and then split the region into convex subregions. It does not seem a trivial issue. I see that there is a branch of geometry called Convex geometry.
The first part - Maple form
Perhaps at this point it is useful to put the example in Maple form so as to talk on more concrete terms:
X:=<x,y>;U:=<u,v>;#the coordinate matrices A:=<<alpha|beta>,<gamma|delta>>;#the transformation matrix X=A.U;#ie the transformation "equation" B:=<<a1|b1>,<a2|b2>,<a3|b3>,<a4|b4>>; C:=<c1,c2,c3,c4>;#the matrices of boundary coefficients BX:=B.X=C;#ie the "equations" for the boundaries in (x,y) BU:=B.A.U=C;#the "equations" for the boundaries in (u,v) B1:=eval(B,[a1=1,b1=0,a2=1,b2=0,a3=0,b3=1,a4=0,b4=1]); C1:=eval(C,[c1=0,c2=1,c3=0,c4=1]); BX1:=B1.X=C1;#the boundaries of the unit square in (x,y) BU1:=B1.A.U=C1;#its transformed boundaries zip(`=`,convert((simplify@(lhs-rhs))(BX1),list),0); [x = 0, x - 1 = 0, y = 0, y - 1 = 0] zip(`=`,convert((simplify@(lhs-rhs))(BU1),list),0); [alpha u + beta v = 0, alpha u + beta v - 1 = 0, gamma u + delta v = 0, gamma u + delta v - 1 = 0]recipies
Geometry
My point of view is more close to differential geometry. In Physics it is typical to exploit the symmetries to simplify the calculations: eg look whether a system changes under a rotation or a translation, ie the action of a transformation group on a configuration space.
Certainly the issue here is not invariance or transformations on the solution or jet space of differential equations.
And most probably not algebraic geometry. This is a field of which I have just a vague idea.
To learn by experience which is the best coordinate system for simplifying the calculations is what students do. But for an algorithmic based CAS another approach is needed. In particular if profit is to be get from "nonstandard" coordinate systems.
In applications, many of the integrals that are done analytically can be done because they can be factorized.
What do you mean by "1-dim Fourier problems or periodics"?
In regards to Jacques ``rectifying transformation'', it is within the subject of general coordinate transformations ie differential geometry. Indeed, general coordinate transformations is a big issue.
(periodics)
What I was wondering is: there one passes to Reals/group, the circle,
while in the cases above one does not consider the quotient.
But that would drift of the topic I guess
integration over cylinders?
Other topologies and curved manifolds would come after R^n...
Thanks Learning at the moment
Hi,
You are all very smart people.I am leanring multi variable integration at the momment. This is right on time and very helpful .
Thank you all.
Vladimir Bondarenko
A humorous thing related to that (for people visiting Maple newsgroup occasionally) is that Vladimir Bondarenko developed some new ways of calculating multidimensional integrals (before becoming a Maple integral bug expert.) Being treated more nicely by the company, Maple could have some multidimensional integrals already implemented with his help.