1

I have a list of n points(2D): P1(x0,y0), P2(x1,y1), P3(x2,y2) … Points satisfy the condition that each point has unique coordinates and also the coordinates of each point xi, yi> 0 and xi,yi are integers.

The task is to write an algorithm which make approximation of these points

  • to the curve y = | Acos (Bx) | with the best fit (close or equal to 100%)
  • and so that the coefficients A and B were as simple as possible.

I would like to write a program in C # but the biggest problem for me is to find a suitable algorithm. Has anyone would be able to help me with this?

Spektre
  • 49,595
  • 11
  • 110
  • 380
MerryJane
  • 66
  • 6
  • 1
    What did you try? Why did it fail? – amit Apr 08 '15 at 07:49
  • something like http://www.codeproject.com/Articles/25237/Bezier-Curves-Made-Simple ? – Florian Schmidinger Apr 08 '15 at 07:50
  • I tried method of least squares but I'm stuck.. – MerryJane Apr 08 '15 at 07:51
  • 1
    This seems more like a Math problem then a c# problem. – Zohar Peled Apr 08 '15 at 07:52
  • Post your code for the method of least squares so we can start there. Instead of coming up with a new solution its easier to work on solutions that have already some work done onto. I recently had to write this for my math class in university so I might be able to give you a C++ solution. – Christo S. Christov Apr 08 '15 at 07:52
  • Maybe you should ask this on http://math.stackexchange.com/ – Matthew Watson Apr 08 '15 at 07:56
  • I think it's not good idea cuz my code doesnt work correctly and I think that I'm far away from good solution.My code look like one big sh** now ;/ I want to hear about your ideas to solve these problem. – MerryJane Apr 08 '15 at 08:01
  • @Chris I know C++ so you can give c++ solution :) I'll be very grateful. – MerryJane Apr 08 '15 at 08:04
  • Okay, I will have it for you tonight cause I'm at work right now – Christo S. Christov Apr 08 '15 at 08:04
  • 1
    Are you sure about the absolute value ? Please show us your points. –  Apr 08 '15 at 08:45
  • Given the non-linearity of the problem, I am afraid you can't avoid Levenberg-Marquardt (http://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm). –  Apr 08 '15 at 08:46
  • You can take any Points you want, example: P1(1,1), P2(2,5), P3(4, 14), P4(8, 10). I think that it’s no matter if you take y=Acos(Bx) or y=|Acos(Bx)|. Look that as bigger B you take then you will come closer and closer to create a good approximation to points. – MerryJane Apr 08 '15 at 09:09
  • What is the rationale behind this question ? –  Apr 08 '15 at 10:19
  • 1. without example points to test on is this very hard to answer correctly. because it is unclear is the points match the curve `y = | Acos (Bx) |` or not, 2. what does mean close or equal to 100% (y value of fitted curve `y` cannot be bigger then original curve ?) 3. what does mean keep A,B as simple as they can be (are they scalar or polynomial from equations they look scalar to me but that statement suggest otherwise?) – Spektre Apr 09 '15 at 06:47
  • If you do not have any math equations or rules for the A,B computation then use Genere and Test approach: loop through all possible A,B (with some heuristics like CCD or any other approximation/iteration to avoid almost infinite loops) compute the difference of each tried solution and source points remember the best solution (recursively increase accuracy around last solution by decreasing step and range and loop again ...) ... look here http://stackoverflow.com/q/29166819/2521214 something very very similar: fit to a bit more complex transcendent curve in C++ I am dealing with these days... – Spektre Apr 09 '15 at 07:00
  • Hi @MerryJane you can find a solution here = http://codesam.blogspot.com/2011/06/least-square-linear-regression-of-data.html – Christo S. Christov Apr 09 '15 at 12:11

2 Answers2

0

Taking B as an independent parameter, you can solve the fitting for A using least-squares, and compute the fitting residual.

The residue function is complex, with numerous minima of different value, and an irregular behavior. Anyway, if the Xi are integer, the function is periodic, with a period related to the LCM of the Xi.

The plots below show the fitting residue for B varying from 0 to 2 and from 0 to 10, with the given sample points.

enter image description here enter image description here

0

Based on How approximation search works I would try this in C++:

// (global) input data
#define _n 100
double px[_n]; // x input points
double py[_n]; // y input points

// approximation
int ix;
double e;
approx aa,ab;
//            min  max   step  recursions  ErrorOfSolutionVariable
for (aa.init(-100,+100.0,10.00,3,&e);!aa.done;aa.step())
for (ab.init(-0.1,+  0.1, 0.01,3,&e);!ab.done;ab.step())
    {
    for (e=0.0,ix=0;ix<_n;ix++) // test all measured points (e is cumulative error)
        {
        e+=fabs(fabs(aa.a*cos(ab.a*px[ix]))-py[ix]);
        }
    }
// here aa.a,ab.a holds the result A,B coefficients

It uses my approx class from the question linked above

  • you need to set the min,max and step ranges to match your datasets
  • can increase accuracy by increasing the recursions number
  • can improve performance if needed by
    • using not all points for less accurate recursion layers
    • increasing starting step (but if too big then it can invalidate result)

You should also add a plot of your input points and the output curve to see if you are close to solution. Without more info about the input points it is hard to be more specific. You can change the difference computation e to match any needed approach this is just sum of abs differences (can use least squares or what ever ...)

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380