448,617 Members | 1,600 Online
Need help? Post your question and get tips & solutions from a community of 448,617 IT Pros & Developers. It's quick & easy.

# maxima & minima

 P: n/a Hello group Is there a library which can help in doing the task below or do I need to write something up? I need to get the index of the relative “local” maximas and minimas in a sequence or real numbers. That is when the derivative is zero and there is a change in direction. Thanks Jul 23 '05 #1
9 Replies

 P: n/a * Baloff: Is there a library which can help in doing the task below or do I need to write something up? It's almost guaranteed to be less work to write your own code than to find, install and figure out a library. I need to get the index of the relative “local” maximas and minimas in a sequence or real numbers. The indices, surely? That is when the derivative is zero and there is a change in direction. Uhm, a sequence doesn't have a derivate, but taking that as a figure of speech: just loop over the numbers and note every change and zero in the first difference. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Jul 23 '05 #2

 P: n/a "Baloff" wrote in message news:42********@news.iprimus.com.au... Hello group Is there a library which can help in doing the task below or do I need to write something up? I need to get the index of the relative “local” maximas and minimas in a sequence or real numbers. That is when the derivative is zero and there is a change in direction. Thanks You can iterate over the sequence of values and calculate the derivate easily using the finite difference formula. Then just observe a change in the sign of two consecutive derivates and you have you minimum or maximum. However, if you want to classify them you'll have to calculate the 2nd derivate too and in this case I'd suggest to calculate the derivate not using a linear connection of two points but rather a parabola fitted with three points of your sequence. Cheers Chris Jul 23 '05 #3

 P: n/a "Baloff" wrote in message news:42********@news.iprimus.com.au Hello group Is there a library which can help in doing the task below or do I need to write something up? I need to get the index of the relative “local” maximas and minimas in a sequence or real numbers. That is when the derivative is zero and there is a change in direction. Thanks Just for fun, I have written some quick code to solve your problem. It seems to work, but I suggest you test it more thoroughly than I have. It defines a template class Optima. The template parameter is a pointer or iterator of the type needed to traverse the container storing the real numbers. You declare an instance of this class and supply to its constructor two arguments: 1. A pointer/iterator to the first real number to be tested. 2. A pointer/iterator to one past the last real number to be tested or a count of the number of objects to be tested. The second alternative only works with pointers/random access iterators. The constructor creates two vectors of pointers/iterators. The members of the first vector point to the elements that are minima. The members of the second vector point to the elements that are maxima. References to these two vectors can be retrieved from an Optima object with the member functions MinIndices() and MaxIndices(). The class and a sample use are given below. It is assumed that the real numbers are stored as doubles. #include #include #include #include #include using namespace std; enum OptType {MIN, MAX}; template class Optima { public: Optima(Iterator a_start, int size) : start(a_start), finish(a_start+size) { FindAllOptima(); } Optima(Iterator a_start, Iterator a_finish) : start(a_start), finish(a_finish) { FindAllOptima(); } const vector & MinIndices() { return optIndex[MIN]; } const vector & MaxIndices() { return optIndex[MAX]; } private: Iterator it, itnext, start, finish; vector optIndex[2]; void FindAllOptima(); void FindFirstOptima(); template void FindNextOptima(); void FindNextMin() { FindNextOptima > ();} void FindNextMax() { FindNextOptima > ();} }; /////////// Use of class (member definitions come later) /////////// const int size = 200; double g_array[size]; typedef double * ItType; int main() { for(int i=0; i opt(itstart, itfinish); // print out the results; const vector& maxIndices = opt.MaxIndices(); const vector& minIndices = opt.MinIndices(); size_t imax=0, imin=0; for(ItType it = itstart; it != itfinish; ++it) { // first the number cout << setw(7) << *it; // now show if it's a local max if(it == maxIndices[imax]) { cout << " Max"; if(imax < maxIndices.size()-1) ++imax; } // now show if it's a local min if(it == minIndices[imin]) { cout << " Min"; if(imin < minIndices.size()-1) ++imin; } cout << endl; } } ///// Member function definitons //////////////////////// template void Optima::FindFirstOptima() { // first check for boundary min/max if(*it < *itnext) optIndex[MIN].push_back(it); else if(*it > *itnext) optIndex[MAX].push_back(it); else // constant section initially { // get past the constant section while(itnext != finish && *it == *itnext) { ++it, ++itnext; } if(itnext == finish) // constant to the end { for(Iterator k = start; k != itnext; ++k) { optIndex[MIN].push_back(k); optIndex[MAX].push_back(k); } } else if(*it < *itnext) // constant then increasing => min { for(Iterator k = start; k != itnext; ++k) { optIndex[MIN].push_back(k); } } else // constant then decreasing => max { for(Iterator k = start; k != itnext; ++k) { optIndex[MAX].push_back(k); } } } } template template void Optima::FindNextOptima() { static Comparison comp; // get past changing section while(itnext != finish && comp(*itnext, *it)) { ++it, ++itnext; } if(itnext == finish) // changing section lasts to the end optIndex[ot].push_back(it); // record boundary optimum else // reach a constant section { // first optimum index Iterator localStart = it; // get to end of constant section while(itnext != finish && *itnext == *it) { ++it, ++itnext; } if(itnext == finish // constant to the end || comp(*it, *itnext)) // sign reversal in differences { for(Iterator k = localStart; k != itnext; ++k) optIndex[ot].push_back(k); } // else differences revert to previous value so it's an inflection } } template void Optima::FindAllOptima() { it = start; itnext = start; ++itnext; FindFirstOptima(); while(itnext != finish) { if(*it < *itnext) FindNextMax(); else FindNextMin(); } } -- John Carson Jul 23 '05 #4

 P: n/a "Baloff" wrote in message news:42********@news.iprimus.com.au... Hello group Is there a library which can help in doing the task below or do I need to write something up? I need to get the index of the relative local maximas and minimas in a sequence or real numbers. That is when the derivative is zero and there is a change in direction. Thanks As Alf mentioned, there is no derivative of a sequence. You'd first need to compute a formula for an equation which satisfies the sequence before you could compute a derivative. And there are an infinite number of functions which satisfy any given sequence of points, so there may be any number of local maximas and minimas. Besides, it's really redundant to state that the derivative must be zero, because, given any continuous function of x which maps to the sequence, then any time the y direction changes, at at least one location within the sequence of three points used to detect a direction change, the derivative must equal zero. Consider the values 4,2,3 (at x values of 1,2,3, let's say). The function is tending downward from 4 to 2, then upward from 2 to 3. So, at at least one location, if the function is continuous, the curve must have changed directions, and thus has a derivative of zero. But there's no way of telling *where* any of those possible changes occurred. However, since you are asked only to find the index, you can at least narrow it down to "somewhere in the vicinity of x=2". It could actually be arbitrarily close to x=1 or x=3, but since you have no way to tell without a formula for the function, you might as well choose the "inflection" point, or x=2. As a general rule, then, simply check every set of three consecutive points, and report the value of x for every x for which both its neighbors are either greater or smaller: for (int x = 1; x < (N-1); ++x) if ((f[x-1] < f[x]) && (f[x] > f[x+1])) ReportLocalMaxima(x,f[x]); else if ((f[x-1] > f[x]) && (f[x] < f[x+1])) ReportLocalMinima(x,f[x]); -Howard Jul 23 '05 #5

 P: n/a Howard wrote: As a general rule, then, simply check every set of three consecutive points, and report the value of x for every x for which both its neighbors are either greater or smaller: But take care to report a sequence such as 4, 2, 2, 3 as a local minimum! In other words: just by looking at only 3 points in sequence, you will miss some minima/maxima. -- Karl Heinz Buchegger kb******@gascad.at Jul 23 '05 #6

 P: n/a "Karl Heinz Buchegger" wrote in message news:42***************@gascad.at... Howard wrote: As a general rule, then, simply check every set of three consecutive points, and report the value of x for every x for which both its neighbors are either greater or smaller: But take care to report a sequence such as 4, 2, 2, 3 as a local minimum! In other words: just by looking at only 3 points in sequence, you will miss some minima/maxima. -- Karl Heinz Buchegger kb******@gascad.at Ooh! Good point! Blows my simple loop out of the water, huh? :-) But if the above is allowed, then what would you report as the index of the minimum? I think that question needs to be addressed to whoever made the spec's in the first place. (A college instructor?) -Howard Jul 23 '05 #7

 P: n/a "Howard" wrote in message news:X9*******************@bgtnsc04-news.ops.worldnet.att.net "Karl Heinz Buchegger" wrote in message news:42***************@gascad.at... But take care to report a sequence such as 4, 2, 2, 3 as a local minimum! In other words: just by looking at only 3 points in sequence, you will miss some minima/maxima. -- Karl Heinz Buchegger kb******@gascad.at Ooh! Good point! Blows my simple loop out of the water, huh? :-) But if the above is allowed, then what would you report as the index of the minimum? I think that question needs to be addressed to whoever made the spec's in the first place. (A college instructor?) There is nothing to say that a local maximum or minimum must be a *strict* local maximum/minimum even when a continuous function domain is being considered. Functions can easily have horizontal sections in which you have a continuum of optima, with all points interior to the horizontal section having the same value as all points in a sufficiently small neighbourhood of them. In the case of 4, 2, 2, 3, the indices of both '2's should be recorded. -- John Carson Jul 23 '05 #8

 P: n/a "John Carson" wrote in message news:d7**********@otis.netspace.net.au The constructor creates two vectors of pointers/iterators. The members of the first vector point to the elements that are minima. The members of the second vector point to the elements that are maxima. I did this for generality. If you are working with C-style arrays or C++ vectors and want indices, then you can get them as follows. If working with pointers, then you can get indices from the pointers by simply subtracting the pointer to the zero element from the pointer to the element of interest, e.g., int indexOfMax = ptrToMax - ptrToZeroElement; If you are working with vectors from the standard library and the associated iterators, say: vector vec(N); vector::iterator itr; then if itr points to a maximum, the associated index is int indexOfMax = itr - vec.begin(); -- John Carson Jul 23 '05 #9

 P: n/a Baloff wrote: Hello group Is there a library which can help in doing the task below or do I need to write something up? I need to get the index of the relative â€ślocalâ€ť maximas and minimas in a sequence or real numbers. That is when the derivative is zero and there is a change in direction. Thanks Look at GNU Scientific Library. Jul 23 '05 #10

### This discussion thread is closed

Replies have been disabled for this discussion.