C #: loop to find function minima

Question

I currently have this function:

public double Max(double[] x, double[] y) { //Get min and max of x array as integer int xMin = Convert.ToInt32(x.Min()); int xMax = Convert.ToInt32(x.Max()); // Generate a list of x values for input to Lagrange double i = 2; double xOld = Lagrange(xMin,x,y); double xNew = xMax; do { xOld = xNew; xNew = Lagrange(i,x,y); i = i + 0.01; } while (xOld > xNew); return i; } 

This will find the minimum value on the curve with decreasing slope ... however , given this curve , I need to find three minimums.

How to find three minimums and display them as an array or separate variables? This curve is just an example - it can be inverted - regardless, I need to find several variables. Therefore, as soon as the first mine is discovered, he needs to know how to overcome the inflection point and find the next ...: /

* Lagrange function is here . ** For all practical purposes, the Lagrange function will give me f (x) when I enter x ... visually, this means the curve provided by tungsten alpha.

* The mathematical part of this puzzle can be found here . **

Possible Solution? Create an input array, for example x [1,1,1,1,2,1,3,1,4 ...], return the array from the Lagrange function. Then find the three smallest values ​​of this function? Then get the keys matching the values? How can I do it?

Answer 1

Assuming that you are simply trying to “power-search” to calculate this at a certain level of prcision, you need your algorithm to basically find any value where both neighbors are greater than the current value of your cycle.

To simplify this, let me say that you have an array of numbers and you want to find the indices of the three local minima. Here is a simple algorithm for this:

 public void Test() { var ys = new[] { 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 4, 5, 4 }; var indices = GetMinIndices(ys); } public List<int> GetMinIndices(int[] ys) { var minIndices = new List<int>(); for (var index = 1; index < ys.Length; index++) { var currentY = ys[index]; var previousY = ys[index - 1]; if (index < ys.Length - 1) { var neytY = ys[index + 1]; if (previousY > currentY && neytY > currentY) // neighbors are greater minIndices.Add(index); // add the index to the list } else // we're at the last index { if (previousY > currentY) // previous is greater minIndices.Add(index); } } return minIndices; } 

So basically, you pass in the function (ys) functions that you calculated for the input array (xs) (not shown) to your result array. What you get from this function are the minimal indexes. So, in this example, you return 8, 14, and 17.

Answer 2

It's been a while since I took the class of numerical methods, so bear with me. In short, there are several ways to find the root of a function, and depending on your function (continuous? Differentiable?), You need to choose the one that fits.

For your problem, I'll probably start by trying to use the Newton Method to find the roots of the second degree Lagrange polynomial for your function. I have not tested this library, but there is a set of C # based numerical methods on CodePlex that implements the Newton method, which is open source. If you want to dig a code, you could.

Most root lookup methods have cousins ​​in the broader CS "search" topic. If you want a very quick and dirty approach or you have a very large search space, consider something like Simulated Annealing . Finding all of your lows is not guaranteed, but it's quick and easy to code.