Метод деления отрезка пополам

Метод бисекции или метод деления отрезка пополам – простой численный метод для решения нелинейного уравнения вида f(x) = 0.

Описание алгоритма

Метод применим для численного решения уравнения f(x) = 0 для действительной переменной x, где f(x) – непрерывная функция, определенная на интервале [a, b], а f(a) и f(b) имеют противоположные знаки. В этом случае говорят, что a и b заключают в скобки корень, поскольку по теореме о промежуточном значении непрерывная функция f(x) должна иметь хотя бы один корень в интервале (a, b).

На каждом шаге метод делит интервал на две части, вычисляя среднюю точку t = (a + b) / 2 интервала и значение функции f(t) в этой точке. Если только t не является корнем (что очень маловероятно, но возможно), теперь есть только две возможности: либо f(a) и f(t) имеют противоположные знаки и скобки для корня, либо f(t) и f(b) иметь противоположные знаки и заключать в скобки корень. Метод выбирает подинтервал, который гарантированно будет скобкой, в качестве нового интервала, который будет использоваться на следующем шаге. Таким образом, интервал, содержащий ноль f(x), уменьшается по ширине на 50% на каждом шаге. Процесс продолжается до тех пор, пока интервал не станет достаточно малым.

Если f(a) и f(t) имеют противоположные знаки, тогда метод устанавливает t как новое значение для b, а если f(b) и f(t) имеют противоположные знаки, то метод устанавливает t как новое значение а. Если f(t) = 0, то t может быть принято как решение, и процесс останавливается. В обоих случаях новые f(a) и f(b) имеют противоположные знаки, поэтому метод применим к этому меньшему интервалу.

Реализация алгоритма

using System;

class Program
{
    /// <summary>
    /// Модуль числа
    /// </summary>
    /// <param name="x">Число</param>
    /// <returns>Абсолютное значение числа</returns>
    static double Abs(double x)
    {
        return (x < 0) ? -x : x;
    }

    /// <summary>
    /// Знак числа
    /// </summary>
    /// <param name="x">Число</param>
    /// <returns>-1 если число отрицательное, 1 - если положительное</returns>
    static int Sign(double x)
    {
        return (x < 0) ? -1 : 1;
    }

    /// <summary>
    /// Метод бисекции(деления отрезка пополам)
    /// </summary>
    /// <param name="function">Функция</param>
    /// <param name="a">Начало отрезка</param>
    /// <param name="b">Конец отрезка</param>
    /// <param name="precision">Точность вычислений</param>
    /// <returns></returns>
    static double BisectionMethod(Func<double, double> function, double a, double b, double precision = 1e-10)
    {
        while (true)
        {
            var t = (a + b) / 2;

            if (function(t) == 0.0 || Abs(b - a) < Abs(precision))
            {
                return t;
            }

            if (Sign(function(t)) == Sign(function(a)))
            {
                a = t;
            }
            else
            {
                b = t;
            }
        }
    }

    static void Main(string[] args)
    {
        //локальная функция
        double f(double x) => 3 * Math.Pow(x, 2) - 6 * x + 1;

        Console.WriteLine("Метод бисекции для функции 3x^2 - 6x + 1");
        Console.Write("Введите начало отрезка: ");
        var a = double.Parse(Console.ReadLine());
        Console.Write("Введите конец отрезка: ");
        var b = double.Parse(Console.ReadLine());
        Console.Write("Введите точность вычислений: ");
        var eps = double.Parse(Console.ReadLine());

        var result = BisectionMethod(f, a, b, eps);
        Console.WriteLine("x = {0}\r\nf({0}) = {1}", result, f(result));
        Console.WriteLine("Для выхода нажмите клавишу Enter...");
        Console.ReadKey();
    }
}