Метод половинного деления

Апрель 26, 2009 / Автор AlexR / Рубрики Статьи, Численные методы / Комментировать

Теоретическая часть

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

Разделим отрезок [a, b] пополам точкой x1=(a+b)/2. Eсли f(x1)!=0(что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a, x1] (Рис. 1), либо на отрезке [x1, b] (Рис. 2).

Рисунок 1

Рисунок 1

Рисунок 2

Рисунок 2

Выбирая в каждом случае тот отрезок, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.

Оценка погрешности: После n делений, очевидно, что погрешность можно оценить следующим образом:|ksi - xn|<=(b-a)/2^n, так как она при каждом последующем делении уменьшается на 2, то
|ksi-x{n+1}|<=0.5*|ksi-xn|, поэтому ?=1, а c=0,5 (скорость сходимости), где ? — точное значение функции.

Подготовка к решению задачи

Алгоритм:

  1. Вводим a,b (левый край промежутка и правый) и e (относительная погрешность);
  2. Считаем функцию в точке a и в точке b;
  3. Если f(a)*f(b)
  4. Считаем x=0.5*(a+b);
  5. Если f(a)*f(b)>0 тогда a=x, иначе b=x;
  6. Считаем погрешность d=(b-a)/|x|;
  7. Если d>e тогда переходим к п. 3) иначе к п.8);
  8. Выводим на экран сообщение: «Ответ:», выводим х, считаем f(x), выводим f(x);
  9. Завершаем алгоритм.

Описание входной информации: a — левая граница промежутка, b — правая граница промежутка, e — относительная погрешность.

Описание выходной информации: x — приближенное значение корня, F — значение функции в найденном корне, n — количество итераций.

Ссылки для скачивания:
Метод половинного деления на MatLab7
Метод половинного деления на Pascal ABC

Вернуться назад

12 комментариев к “Метод половинного деления”

Комментарии

  1. Александр

    Жаль, и еще раз спасибо за помощь)

  2. Не за что, рад, что помог. Метода Хорд у меня, к сожалению, нет. Не помню, делал ли я реализацию в прошлом или нет.

  3. Александр

    Спасибо большое за помощь и быстрый ответ, другой бы на вашем месте за такой срок уже забросил сайт)
    Хотел бы задать вам еще один вопрос. После того, как нашел вашу реализацию метода половинного деления на матлабе, начал писать писать реализацию метода хорд, все, вроде получается, но столкнулся с проблемой вывода ответа, программа либо зацикливается, либо выдает ответ по установленному мной ограничению на итерации, и вот хотел бы спросить есть ли у вас тема подобная данной по методу хорд? Она бы мне очень помогла. Заранее спасибо.

  4. Строки 7 и 8 только для того, чтобы построить график. 14, 15, 23, из теории, нам нужно «прыгать» вокруг корня уравнения, пока не будет достигнут нужный уровень погрешности, d как раз за это и отвечает.

  5. Александр

    Код на MatLab, строки 14,15,23, не пойму, что за переменная d

  6. Александр

    Код на MatLab, строки 7, 8, 14,15

  7. Александр, какой код смотрите: Pascal или MatLab? Еще я не могу понять какие именно строки, отсчитайте с самого начала файла. Спасибо.

  8. Александр

    Здравствуйте, разбираюсь в вашем коде, пара строк остается для меня загадкой, если не сложно, объясните пожалуста, что происходит в строках кода 5, 6, 12,13, номера строк считал не включая комментариев. Заранее спасибо.

  9. Починил, теперь файл можно загрузить без проблем.

  10. Гаухар

    как получить доступ на скачивание?

  11. AlexR

    Не за что
    =)

  12. AIdos ertaev

    SPS BOLWOOOOOOOOOOOOOOOOOOOOOOOOOOOOOEEEEE ELE NAWEL ETOT METOD !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Комментарии