Distance from non-uniform linear acceleration

[duncanhall]

I have an object at rest which accelerates at a variable rate before coming to rest again. At any given point I can determine it's linear acceleration, accounted for gravity.

I would like to determine the distance traveled between the 2 resting points.

I understand some of the pieces involved here but have a very rudimentary understanding of calculus. I'm approaching this from a computer-science background.

If anyone's able to provide any help on this, or knows any good learning resources, it'd be much appreciated.

 

[DrewD]

Do you have a function $a(t)$ for the object? If you have the function, then you integrate the acceleration to get a velocity function $v(t)=\int_{t_1}^ta(x)\,dx$ and then integrate that again from $t_1$ to $t_2$. If the function $a(t)$ is not a simple function, it may be easier to use an approximation method.

Is this on track or am I not really getting at your question?

 

[boneh3ad]

Presumably he doesn't have a function but instead a bunch of measurements throughout a given time. That can still be numerically integrated, though. I'd also suggest that rather than using any of the quadrature-type integration methods like the trapezoid rule, use FFT to compute the integral.

 

[olivermsun]

Why do you suggest using the FFT?

 

[boneh3ad]

There is a very simple relationship between the FFT of a function and its integral, and the method is substantially more accurate than just using trapezoids.

Let \hat{f} be the Fourier transform of f. It is pretty easy to show that for the nth derivative of f, or f^{(n)}, there exists the following relationship:
\widehat{f^{(n)}} = (ik)^n\hat{f}.
So if you compute the FFT of your function, in his case acceleration, you can integrate it by dividing the FFT by ik however many times you want to integrate it. Then you just run the inverse FFT on the result and you have the nth integral of your original function. This is substantially more accurate than doing trapezoids. You need far fewer points to get the "correct" answer.

Of course, it is a Fourier transform so it assumes the function is periodic (which is a decent assumption when the function goes to zero at the start and finish). The consequence is that if you don't have all derivatives going to zero at the boundaries, you will see Gibb's phenomenon near the edges, but it's pretty easy to tell what is and isn't a result of Gibb's phenomenon, and you can mitigate that as well in a number of ways (though that is probably getting too complicated for this post).

Of course if it turns out that the function just doesn't behave well (and it's hard to say without knowing more about the original function in question), you can just go back and use trapezoids and get a decent answer.

 

[olivermsun]

There is a very simple relationship between the FFT of a function and its integral...This is substantially more accurate than doing trapezoids. You need far fewer points to get the "correct" answer.

I understand the relationship. I'm asking why this approach is recommended for the OP, who admits a "very rudimentary understanding of calculus." Some simple numerical integration scheme would probably be easier for the OP to understand and would also be easy to implement programmatically.

As an aside, I'm not sure it's true that FFT method requires fewer points than a trapezoid (or even a Riemann sum) to achieve a given precision for the integral of an arbitrary function.

 

[boneh3ad]

In my opinion, there is no scheme that is easier to implement than using the FFT method anyway provided that your programming language of choice includes an FFT routine of some kind, and most languages do have some kind of package that includes FFT. The great thing about the method is that it really doesn't involve any calculus as long as you already have an FFT routine. It is just multiplication or division. Of course, understanding how it works requires calculus, but not actual implementation.

Of course, it all comes down to the requirements of the problem I suppose. The FFT method is usually several orders of magnitude more accurate for the same number of sample points than the trapezoid method, but maybe the trapezoid method is completely acceptable for the OP's purposes. It's hard to say given the original post. I made my suggestion based on ease of implementation and on accuracy, not east of understanding. I admit that it is more complicated to understand than trapezoids.

 

[jtbell]

At this point, we'd better wait for duncanhall to come back and clarify whether he has a formula that gives him a(t), or instead, a set of measurements at various values of t, before continuing on what might turn out to be an irrelevant tangent.

 

[olivermsun]

In my opinion, there is no scheme that is easier to implement than using the FFT method anyway provided that your programming language of choice includes an FFT routine of some kind, and most languages do have some kind of package that includes FFT.

All right, let's accept for the moment that the programming language provides an FFT but no numerical summation or higher-order quadrature functions. What should the OP do with the point at k = 0?

 

[olivermsun]

At this point, we'd better wait for duncanhall to come back and clarify whether he has a formula that gives him a(t), or instead, a set of measurements at various values of t, before continuing on what might turn out to be an irrelevant tangent.

Moreover the OP doesn't specify whether he/she wants to calculate this for some practical application, learn how this works conceptually, or some other thing entirely. That's why I questioned the suggestion to jump straight into FFTs.

 

[boneh3ad]

All right, let's accept for the moment that the programming language provides an FFT but no numerical summation or higher-order quadrature functions. What should the OP do with the point at k = 0?

Unless the length of sample is infinity, then the FFT won't resolve a k=0 component anyway.

 

[olivermsun]

Umm. What do you think the k=0 bin in your FFT output represents?

 

[duncanhall]

Wow, thanks for all the responses so far. Even if I'm still far from grasping what I need to do to implement this, it's much appreciated.

For some extra information, I do actually want to solve this for a real world application. Ultimately, accuracy is my main aim, but will settle for understanding the most simple of implementations for now. I have some exposure to FFT from previously working with audio samples, although the actual FFT implementation I used was 'off-the-shelf'. I can more or less get near as many sample points as I want, down to around 2 Microseconds between each sample. Each sample will contain a timestamp and the linear acceleration at that point. I am only interested in, and have isolated, the linear acceleration along one axis. If any further information can help, let me know.

So, as for my understanding, perhaps I didn't make that 'very' bold enough. I can just about read DrewD's original reply with enough vocabulary to make it sound like I might understand it, but ultimately don't. I have more or less zero understanding of you would go about actually implementing that solution.

I realize "teach me calculus" is well beyond the scope of some forum posts, but if you can go any way to putting me on the right path, that would be great.

 

[DrewD]

So, as for my understanding, perhaps I didn't make that 'very' bold enough. I can just about read DrewD's original reply with enough vocabulary to make it sound like I might understand it, but ultimately don't. I have more or less zero understanding of you would go about actually implementing that solution.

I realize "teach me calculus" is well beyond the scope of some forum posts, but if you can go any way to putting me on the right path, that would be great.

Since you will have discrete values for the acceleration, you don't need my answer. Do you want this to update in "real time" or is this a calculation after gathering all of the information? Do you want to understand what the program is doing, or are you happy to put the info into a black box?

If a black box is okay, you can use Matlab, gsl, or scipy to help with the calculation. If you want to write it yourself and understand it, I would recommend starting simple with the trapazoid rule which we can easily explain (or you can look it up on wiki).

 

[duncanhall]

Thanks Drew. A real time value might be a nice to have in the future, but for now a calculated value after the object comes to rest would be more than great.

I'd love to understand the logic behind the solution if I can. Also, although the value will be calculated after all inputs have been entered, the application that accepts the acceleration values, and the application that calculates the distance value, are one in the same - ie, the application which I will be writing.

I'm definitely going to go and have a look at the trapezoid rule, thanks. Hopefully any questions I have will then be more specific.

 

[boneh3ad]

Umm. What do you think the k=0 bin in your FFT output represents?

You are, of course, correct. It serves me right for writing a quick post while eating my breakfast without thinking too much about what I am saying. I was, of course, jumping ahead a bit in my head to the concept of using FFT for power spectra where your lowest meaningful frequency is tied to your sampling time, not the FFT itself.

Carry on.

 

[olivermsun]

I'd love to understand the logic behind the solution if I can.

The distance traveled is "the area under the curve," i.e. the integral of the velocity. One usual way to explain this is by breaking up the curve into little pieces:

Suppose you have the graph of velocity measured each second (for easy units), v(1), v(2), v(3), ... So say during the first second you're traveling at (about) v(1) = 3 m/s, then you've traveled 3 m/s * 1 s = 3 m, which is the area of a rectangle v(1) tall * 1 s wide. During the 2nd second (!) you're going v(2) = 5 m/s so that's 5 m, and so on. Add up all the areas and you have an approximation of the total area, hence the total distance traveled. The units work out because you're adding up speed * time = distance/time * time = distance.

Unless your velocity is "steppy" and the rectangles cover the graph perfectly, there will be some error in the above estimate. The trapezoidal rule seeks to improve this by covering the area with trapezoids whose tops connects the successive points. As it happens this takes very little extra work compared to using rectangles so it's a quick standby. Then there's Simpson's rule, which uses quadratic shapes (parabolas) to achieve much better precision but is surprisingly still easy to implement, and many others.

If you look up Numerical integration, you'll find that the pictures explain it much better than I can in words.

So the main concern is that, if you're using this for an inertial navigation type application, aka "dead reckoning," then you are often integrating over a very long time, so you would want to use a very, very precise integration technique (without much regard for computing expense). So maybe the trapezoidal rule wouldn't be the best method for this after all. But hey it's a start. And as DrewD mentions, most of the standard methods are available in libraries, Matlab, scipy, etc., so ultimately you won't need to worry too much about implementation.

 

[rcgldr]

With a sample period around 2 micro seconds, there won't be much change in acceleration between time steps and trapezoid rule will probably be ok with that small of a time step. The precision of the readouts from the accelerometer will probably be the limiting factor on accuracy with such a small time step.

 

[boneh3ad]

With a sample period around 2 micro seconds, there won't be much change in acceleration between time steps and trapezoid rule will probably be ok with that small of a time step. The precision of the readouts from the accelerometer will probably be the limiting factor on accuracy with such a small time step.

I wouldn't assume that to be true. That depends entirely on what is being measured. If you are measuring, for example, vibrations, you could get much higher frequencies than that.

 

[rcgldr]

With a sample period around 2 micro seconds, there won't be much change in acceleration between time steps and trapezoid rule will probably be ok with that small of a time step. The precision of the readouts from the accelerometer will probably be the limiting factor on accuracy with such a small time step.

I wouldn't assume that to be true. That depends entirely on what is being measured. If you are measuring, for example, vibrations, you could get much higher frequencies than that.

I was thinking along the lines of a larger object, like a model car or real car. Something small vibrating at high speed could be an issue, but with a 500,000 hz sampling rate, frequencies up to around 25,000 hz shouldn't be much of a problem. I don't know if there is a limit on how high a frequency or how much jerk (rate of change of acceleration) an accelerometer can measure accurately.

 

[boneh3ad]

I was thinking along the lines of a larger object, like a model car or real car. Something small vibrating at high speed could be an issue, but with a 500,000 hz sampling rate, frequencies up to around 25,000 hz shouldn't be much of a problem. I don't know if there is a limit on how high a frequency or how much jerk (rate of change of acceleration) an accelerometer can measure accurately.

I have no idea what the OP's accelerometers can measure, but the ones I have at work are good to somewhere between 5 and 7 kHz. I am sure there exist accelerometers that have a higher frequency response. In terms of sampling, you can capture the frequency content of a signal up to half of your sampling frequency (the Nyquist frequency).

 

[rcgldr]

Link to a pdf file showing rectcangle, trapezoidal, and parabolic methods for integrating a set of data points:

numerical_integration.pdf