Нахождение численного минимума методом Фибоначи
Мне нужно найти численный минимум функции методом Фибоначчи.
f(x) - g(x) -> min
Функция f(x) это полином n-степени. Значение функции g(x) задается набором точек. Для функции g(x) необходимо выполнить интерполяцию с использованием полиномов Лагранжа.
Код написал, но вот проблема.. Не правильное значение минимума дает. Где я ошибся? Вроде и интерполяция правильная, и метод Фибоначчи..
using System;
using System.Collections.Generic;
using System.Drawing;
public class Program
{
public static void Main()
{
double a = -10;
double b = 20;
double epsilon = 0.00001;
List<Point> g_points = new List<Point>() { new Point(0, 1), new Point(1, 2), new Point(2, 3), new Point(3, 3) };
LagrangePolynomial g = new LagrangePolynomial(g_points);
Polynomial f = new Polynomial(new List<double>() { 1, 0, 2 }); // полином f(x) = x^2 + 2
FunctionDifference diff = new FunctionDifference(f, g);
FibonacciSearch fs = new FibonacciSearch(diff, a, b, epsilon);
double min = fs.FindMinimum();
Console.WriteLine("Minimum: " + min);
}
}
public class FibonacciSearch
{
private readonly double phi = (1 + Math.Sqrt(5)) / 2; // определение золотого сечения
private IFunction function;
private double a, b, epsilon;
public FibonacciSearch(IFunction function, double a, double b, double epsilon)
{
this.function = function;
this.a = a;
this.b = b;
this.epsilon = epsilon;
}
public double FindMinimum()
{
double x1, x2;
while (Math.Abs(b - a) > epsilon)
{
x1 = b - (b - a) / phi;
x2 = a + (b - a) / phi;
if (function.Value(x1) >= function.Value(x2))
a = x1;
else
b = x2;
}
return (a + b) / 2;
}
}
public interface IFunction
{
double Value(double x);
}
public class FunctionDifference : IFunction
{
private IFunction f, g;
public FunctionDifference(IFunction f, IFunction g)
{
this.f = f;
this.g = g;
}
public double Value(double x)
{
return f.Value(x) - g.Value(x);
}
}
public class Polynomial : IFunction
{
private List<double> coefficients;
public Polynomial(List<double> coefficients)
{
this.coefficients = coefficients;
}
public double Value(double x)
{
double result = 0;
for (int i = 0; i < coefficients.Count; i++)
{
result += coefficients[i] * Math.Pow(x, i);
}
return result;
}
}
public class LagrangePolynomial : IFunction
{
private List<Point> points;
public LagrangePolynomial(List<Point> points)
{
this.points = points;
}
public double Value(double x)
{
double result = 0;
for (int i = 0; i < this.points.Count; i++)
{
double basicsPol = 1;
for (int j = 0; j < this.points.Count; j++)
{
if (j != i)
basicsPol *= (x - this.points[j].X) / (this.points[i].X - this.points[j].X);
}
result += basicsPol * this.points[i].Y;
}
return result;
}
}