I'm trying to write a program that uses Golden-section search method to find the maximum area of a triangle inside an ellipse that is generated by the function (x^2 / 4) (y^2 / 9) = 1 but haven't had any luck. Managed to get the program to compile but the output I got was "-nan"
Here is what I tried:
#include <stdio.h>
#include <math.h>
// As the ellipse is given by the function (x^2 / 4) (y^2 / 9) = 1 which can be rewritten as y = sqrt(9(1 - (x^2 / 4)))
// Thus, it can deduced that max(x) = 2, min(x) = -2, max(y) = 3 and min(y) = -3
double triangleArea(double base, double height) { // Calculates the area of one of the triangles that make up a half of the full triangle. The result will later be multiplied with 2 in order to get the area of the full triangle.
double area = (base * height) / 2;
return area;
}
double goldenSearch_Max (double xLower, double xUpper) {
double goldenRatio = 0.5 * (sqrt(5) - 1.0); // Initialising Golden Ratio.
double x1 = xUpper - (xUpper - xLower) / goldenRatio;
double x2 = xLower (xUpper - xLower) / goldenRatio;
while (fabs(x2 - x1) > 0.00001) {
if ((triangleArea(x1, sqrt(9 * (1 - (x1 * x1 / 4))))) > (triangleArea(x2, sqrt(9 * (1 - (x2 * x2 / 4)))))) {
xUpper = x2;
}
else {
xLower = x1;
}
x1 = xUpper - (xUpper - xLower) / goldenRatio;
x2 = xLower (xUpper - xLower) / goldenRatio;
}
return (xUpper xLower);
}
int main() {
double goldenRatio = 0.5 * (sqrt(5) - 1.0); // Initialising Golden Ratio.
//double triangleBase = 2 x; // The elliptical equation's max(x) was 2 and the base of the two halves of the triangle is located on the x axis. So the base of one of the halves is 2 x, x being the extra length after the 2 units of the x axis.
//double triangleHeight = sqrt(1 - (x * x) / 4) * 3; // As the elliptical equation can also be written as y = sqrt(9(1 - (x^2 / 4))) after changing the places of the y terms and the result.
double xNew = goldenSearch_Max(0, 2);
printf("%f", (triangleArea(xNew, sqrt(9 * (1 - (xNew * xNew / 4))))));
return 0;
}
Any help would be appreciated.
CodePudding user response:
I can spot a couple of problems:
double goldenRatio = 0.5 * (sqrt(5) - 1.0);
That's the inverse of the Golden Ratio. Which is fine, as long as it's used accordingly:
double const inv_golden_ratio = 0.5 * (sqrt(5) - 1.0);
double x1 = xUpper - (xUpper - xLower) * inv_golden_ratio;
// ^
// ...
return (xUpper xLower);
Shouldn't be better to return the value corresponding to the actual max (or min)?
The average of the points could be fine, too, but the plain sum is wrong.
return (x1 x2) * 0.5;