Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Interpolating a minimum??

Posted on 2006-11-15
5
278 Views
Last Modified: 2006-11-18
Here's a problem I can't quite figure out:

I'm auto-correlating some data with itself to find the periodicity.   I slide the data over itself and compute the differencves.

So I end up with an array with values like these:
(0, 423179422, 828300948, 1212609754, 1580431328, 1927976212, 2261045098, 2576547366, 2880291562, 3170884920, 3448407680, 3712453192, 3963129656, 4202858738, 4428796224, 4642141464, 4838897098, 5022294960, 5189647866, 5336120170, 5468966802, 5573601410, 5661172944, 5722015070, 5764204226, 5784805298, 5795386094, 5794255268, 5783184466, 5761355708, 5725745692, 5678340672, 5612707394, 5527855798, 5421991904, 5296806718, 5153282668, 4992479880, 4816736914, 4627262472, 4424397458, 4211164230, 3987799654, 3757131960, 3516443192, 3266828654, 3006790876, 2731835909, 2460333151, 2202466559, 1938545198, 1667642709, 1389832004, 1109712475, 824855728, 588591149, 546361448, 811857393, 1161263940, 1500909693, 1830265354, 2141064765, 2442071178, 2727283919, 3004764138, 3268936897, 3523042222, 3765280899, 3994320860, 4213529495, 4419602464, 4616188975, 4796605032, 4965570485, 5121258994, 5255613245, 5377713032, 5469986089, 5551080124, 5603396265, 5641398544, 5658406913, 5668274054, 5665748491, 19636457355401828, 5047136332677536, 14, 0, 94816986516684800, 2105652297, 60130717272, 94816986516684801, 4785076709733484, 94818019412627324, 9034993454800879124, 4785074604081690, 205958216012529665, 201399947, 47953384, 31244160501548260, 13511005043490927)

In case you're not good at reading number without commans, here's the interesting part:

54:    824,855,728
55:    588,591,149
56:    546,361,448
57:    811,857,393

The values hit a minimum at element 56.

Now that's swell, but if you notice the value at 56 is a heck of a lot closer to #55 than to #57.  If we assume a kinda normal and continuous function goes through these points, it sure would be nice to estimate the actual minimum.

I'd like to make an educated guess as to where the actual minimum is, but I can't figure out the math!  Dang.

Any formulas appreciated.


0
Comment
Question by:grg99
  • 2
  • 2
5 Comments
 
LVL 45

Expert Comment

by:Kent Olsen
ID: 17946504

Hi grg99,

Have you tried a very primitive straight-line approach?  The numbers would appear to be from a curve, but that's more math than I can take on this morning.

Take the values to the left of #56 and plot their general slope.  Take the values to the right and do the same.  Where the lines intersect is the approximate minimum.

Disregard smoothing and start with points 54,55.  They're defined as (54, 824,855,728) and (55, 588,591,149).  
Define points at 57,58 as (57, 811,857,393) and (58, 1,161,263,940).

Where the lines intersect is your target.  I'd then refine the process by varying the "outer" points (53, 55) & (57, 59), (52, 55) & (57, 60) to guage the curve.


Kent
0
 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
ID: 17946637
If you fit a cubic to the points:
                   first differences
54:    824,855,728                  second differences
                          -236264579                  third differences
55:    588,591,149                        194034878
                           -42229701                  113690768
56:    546,361,448                        307725646
                           265495945
57:    811,857,393

assume third differences = constant
second differences = 194034878 + 113690768*y
first differences = -236264579 + 194034878*x + 113690768*x*(x-1)/2
=  -236264579 + (194034878-113690768/2)*x + 113690768*x*x/2
the max occurs when first differences = 0
solving the quadratic
x = (-(194034878-113690768/2) +- sqrt((194034878-113690768/2)^2 - 4*113690768/2*-236264579))/113690768
= -1.20668983430563 +- 2.36904349875658
we want the solution in between 55: (x=.5) and 57: (x=2.5)
so x=1.16235366445
since we started with x=0 at 54.5:
that corresponds to  55.66235366445:
0
 
LVL 84

Expert Comment

by:ozo
ID: 17946744
But isn't the minimum between the 14 and the  94816986516684800?
15047136332677536, 14, 0, 94816986516684800,
0
 
LVL 45

Expert Comment

by:Kent Olsen
ID: 17946962
The curve near the curve's mimimum near 56 is very erratic.  This "table" shows a bit more of what ozo pointed out.  (The columns are point #, value, difference between this point and previous, difference of the differences.)

  50:   1938545198    -263921361      -6054769
  51:   1667642709    -270902489      -6981128
  52:   1389832004    -277810705      -6908216
  53:   1109712475    -280119529      -2308824
  54:    824855728    -284856747      -4737218
  55:    588591149    -236264579      48592168
  56:    546361448     -42229701     194034878
  57:    811857393     265495945     307725646
  58:   1161263940     349406547      83910602
  59:   1500909693     339645753      -9760794
  60:   1830265354     329355661     -10290092

For points 1 - 40 the last column (second difference) varies but is about -1.7E7.  For points 50 - 52 it's about -6.6E6.  Then all hell breaks loose as just past the minimum, the second difference is 1.94E9, then 3.0E9.  By point 60 the second difference again stablizies near 1.xE7.

With so few data points near this anomly, it's impossible to graph the curve.  Ozo's answer is as good as any, but most any answer between 55 and 57 can be justified.  My gut feeling is that it's between 55 and 56, hence the small difference between those points.  And son-of-a-gun, Ozo's answer of 55.66 is right where I'd expect it.


Kent
0
 
LVL 22

Author Comment

by:grg99
ID: 17948201
Thanks all,  I should have mentioned the general shape of the curve is like a bouncing ball's trajectory, and we want to find the point of impact.

I think I follow ozo's idea-- you take first differences, that gives you the slope, then the second differences give you the rate of change of the slope, which is particularly low as the ball is going down and up, but high when the ball bounces.

Then you write the quadratic  equation that goes through those points and solve for the minimum value.


Thanks.



0

Featured Post

Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Q1. Magnets and Electromagnetism 33 116
Relative Frequency Distribution 4 36
Independent Events 4 83
One Standard Deviation from the Mean 2 30
A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

837 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question