Метод поділу відрізка навпіл

Метод бісекції чи метод поділу відрізка навпіл – простий чисельний метод для вирішення нелінійних рівнянь виду 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();
    }
}