НТУУ «Киевский политехнический институт»

НТУУ «Киевский политехнический институт»

Факультет Электроники

Кафедра Электронных приборов и устройств

Вычислительная математика

Индивидуальное практическое задание по теме:

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

Выполнил студент гр. ДЕ-72

Прокопчук Александр

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

При программировании желательно иметь программу, решающую не один какой-либо тип уравнений, а по возможности наиболее широкий класс уравнений. Естественно, что фактически выполнить это невозможно, не поступившись чем-нибудь. На практике для решения подобных задач используют так называемые численные методы решения. При этом полученное решение находится не точно, а с какой-либо заранее оговоренной точностью.

Рассмотрим один из численных методов решения уравнений – метод половинного деления. Этот метод имеет свои ограничения на применимость, и, прежде всего, он применим только к алгебраическим уравнениям одного неизвестного.

Причем F(х) – непрерывная на отрезке [а, b] функция, удовлетворяющая условию:

F(a)*F(b) < 0. (*)

Метод основан на том теоретическом факте, что всякое уравнение путем равносильных преобразований можно привести к виду:

F(x) = 0. (1)

При этом если изобразить график функции F(x), то кривая графика будет пересекать ось Ох в точке х, которая и будет являться корнем уравнения (рис.1).

Рисунок 1.

Для нахождения корня отрезок [а, b] делится пополам (рис.2):

Рисунок 2.

х_i = а+(b-а)/2 – и выбирается тот полуинтервал, на концах которого знаки F(х) разные.

Для определения знаков функции достаточно вычислить ее значение в точках a, x_i и b соответственно. Полученные значения сравниваются следующим образом:

1. Если одно из найденных значений равно нулю, т. е.

F(a) = 0 or F(x_i) = 0 or F(b) = 0,

то найден соответствующий корень уравнения. Процесс прекращается.

2. Если (F(a) > 0 end F(x_i) < 0) or (F(a) < 0 end F(x_i) > 0), то корень находится на отрезке [a, x_i].

Примечание

Это сложное условие легко заменяется более простым. А именно, с учетом правил действия со знаками в математике легко записать: если (F(x_n)*F(x_i) < 0), то.... Действительно, при умножении чисел с разными знаками всегда получается отрицательное число. Например: 9*(-2) = -18. Тогда пункт 2:

Если (F(x_i) > 0 end F(b) < 0) or (F(x_i) < 0 end F(b) > 0), то корень находится на отрезке [x_i, b].

Аналогично предыдущему: если (F(x_i)*F(x_k) < 0), то....

Итак, выбираем тот отрезок, на котором находится корень (рис. 2.):

Рисунок 3

Если длина выбранного отрезка еще не стала меньше некоторого наперед заданного числа ε – точности вычислений (т. е. в нашем случае | b-x_i | < ε), то процесс деления отрезка пополам повторяется уже для нового отрезка.

2.3.3. Алгоритм метода половинного деления

Введем обозначения переменных, которые будем использовать в программе:

x_n – начало отрезка по х;

x_k – конец отрезка по х;

x_i – середина отрезка по х;

eps – требуемая точность вычислений.

Таким образом, весь алгоритм можно записать следующим образом (в псевдокоде):

1. Начало.

2. Ввод х_n, x_k, eps.

3. Если F(х_n) = 0, то Вывод (корень уравнения – x_n).

4. Если F(х_k) = 0, то Вывод (корень уравнения – x_k).

5. Пока (F(x_i) <> 0) и |x_k-x_n| > eps повторять:

· x_i:= x_n+(x_k-x_n)/2;

· если (F(x_n)*F(x_i) < 0), то x_k:= x_i;

· если (F(x_i)*F(x_k) < 0), то x_n:= x_i.

6. Вывод (Найден корень уравнения – x_i точности ε).

7. Конец.

Указание

Пример

Рассмотрим применение метода на примере уравнения х³+x²-1 = 0.

Применим метод половинного деления на интервале [0,1]:

F(x) = х³+x²-1.

Разделим интервал изоляции пополам в точке 0,5. Т. е. получим два подотрезка – [0, 0.5] и [0.5, 1].

Вычислим значения функции на концах отрезков. Для первого (левого) подотрезка:

F(0) = 0³+0²-1 = -1.

F(0,5) = 0,5³+0,5²-1 = 0,125+ 0,25-1 = -0,625,

т. е. F(0) < 0 и F(0,5) < 0,

т. е. на данном отрезке знак функции остается неизменным и, следовательно, корень уравнения не принадлежит отрезку [0, 0.5].

Рассмотрим правый отрезок [0.5, 1]:

F(0,5) = -0,625 < 0.

F(1) = 1³+1²-1 = 1+1-1 = 1 > 0,

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

Повторяем метод половинного деления уже для нового отрезка. Середина отрезка получается по формуле – х_i = а+(b-а)/2:

x_центра = 0,5+(1-0,5)/2 = 0,5+0,5/2 = 0,75,

т. е. получим два подотрезка – [0.5, 0.75] и [0.75, 1].

Вычислим значения функции на концах отрезков. Для первого (левого) подотрезка:

F(0,5) = -0,625 < 0.

F(0,75) = 0,75³+0,75²-1 = 0,421875+0,5625-1 = -0,015625 < 0,

т. е. F(0,5) < 0 и F(0,75) < 0,

т. е. на данном отрезке знак функции остается неизменным и, следовательно, корень уравнения не принадлежит отрезку [0, 0.5].

Рассмотрим правый отрезок [0.5, 1]:

F(0,75) = -0,015625 < 0.

F(1) = 1 > 0,

т. е. на данном отрезке знак функции меняется на противоположный и, следовательно, корень уравнения принадлежит отрезку [0.75, 1].

Таким образом, уже на втором повторении метода мы получаем корень уравнения x = 0,75 с точностью 0,25. Если данная точность нас не устраивает, то процесс продолжается до получения корня с лучшей точностью.

1. При программировании желательно иметь программу, решающую не один какой-либо тип уравнений, а по возможности наиболее широкий класс уравнений. Естественно, что фактически выполнить это невозможно, не поступившись чем-нибудь. На практике для решения подобных задач используют так называемые численные методы решения. При этом полученное решение находится не точно, а с какой-либо заранее оговоренной точностью.

2. Один из численных методов решения уравнений – метод половинного деления. Этот метод имеет свои ограничения на применимость, и, прежде всего, он применим только к алгебраическим уравнениям одного неизвестного. Причем F(х) – непрерывная на отрезке [а, b] функция, удовлетворяющая условию:

F(a)*F(b) < 0.

Метод основан на том теоретическом факте, что всякое уравнение путем равносильных преобразований можно привести к виду:

F(x) = 0.

При этом если изобразить график функции F(x), то кривая графика будет пересекать ось Ох в точке х, которая и будет являться корнем уравнения.

Список использованной литературы:

1) Б. П. Демидович, И. А. Марон. Основы вычислительной математики

2) В. Е. Краскевич и др. Численные методы в инжинерных исследованиях. Киев, 1986

3) Ю. П. Боглаев. Вычислительная математика и программирование. Учебное пособие для студентов ВТУЗов.

4) Конспект Лекций

5) www.exponenta.ru

Дата добавления: 2015-09-30