Solved

Interpolating a minimum??

Posted on 2006-11-15
5
263 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:Kdo
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:Kdo
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

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Device to warm up the nose 12 176
Word Problem 4 62
Triangle - calculating angles 9 56
Triangles - Calculating angles 7 55
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…
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
This video discusses moving either the default database or any database to a new volume.
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.

747 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now