%!PS % FITTING A PARABOLA TO THREE DATA POINTS. % FINDING THE MINIMUM OF A PARABOLA GIVEN THREE POINTS. % ======================================================== % by Don Lancaster % Copyright c 2001 by Don Lancaster & Synergetics, Box 809, Thatcher, AZ, 85552 % (928) 428-4073 Email: don@tinaja.com Website: http://www.tinaja.com % Consulting services available http://www.tinaja.com/info01.html % All commercial rights and all electronic media rights ~fully~ reserved. % Linking usually welcome. Reposting expressly forbidden. Version 2.5 % Fitting three points to a parabola can be useful for graphics smoothing % or seeking the minimum of a math function. You can always fit three % points to a parabola so long as they are not in a straight line. % Given three points x1,y1 x2,y2 x3,y3, find x0, y0 the minimum of the % parabola they fit on. % y3 = Ax3^2 + Bx3 + C % general quadratic equations made specific % y2 = Ax2^2 + Bx2 + C % y1 = Ax1^2 + Bx1 + C % Solving these using algebra or web resources... % A = (y3-y2)/(x3-x2)(x3-x1) - (y1-y2)/(x1-x2)(x3-x1) % B = ( y1 - y2 + A(x2^2 - x1^2) )/(x1-x2) % C = y1 - Ax1^2 - Bx1 % Note that ABSOLUTE x values are not required. Only the DIFFERENCE between % x1, x2, and x3 is used. This might be a constant test spacing. % The minimum (assuming an up pointing parabola) will occur by setting the % first derivative slope to zero. % minimum at 2Ax + B = 0 x = -B/2A % Also follows from the quadratic equation x = (- b +- sqrt (b2 - 4ac))/2A % has a single paired solution only when b2 - 4AC = 0, leaving x = -B/2A. % To find the minimum of a complex function assumed to be following a parabolic % error curve near a solution, evaluate the function at a point x near the minimum % (often a good guess), x+deltax and x-deltax. The new x0 should be much closer % to the true solution. If not truly parabolic, several passes should converge. % If not mostly parabolic, the technique does not work. % demo using PostScript... /x1 4 7 add store /y1 16 5 add store /x2 5 7 add store /y2 25 5 add store /x3 6 7 add store /y3 36 5 add store /A { y3 y2 sub x3 x2 sub x3 x1 sub mul div y1 y2 sub x1 x2 sub x3 x1 sub mul div sub} def /B { y1 y2 sub x2 dup mul x1 dup mul sub A mul add x1 x2 sub div} def /C { y1 x1 dup mul A mul sub x1 B mul sub } def /xmin {B neg A 2 mul div} def /ymin {xmin dup mul A mul xmin B mul add C add } def A == B == C == xmin == ymin == %% Send to Distiller. Should return minimum of x = 7 and y = 5 to log file. %% EOF