Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ СВЕРДЛОВСКОЙ ОБЛАСТИ

Государственное автономное профессиональное образовательное учреждение Свердловской области

«Слободотуринский аграрно-экономический техникум»

Контрольная работа

Метод половинного деления (метод дихотомии)

ОП 13. Математическое моделирование

09.02.03 "Программирование в компьютерных системах"

Исполнитель: Федотова В.В.,

Студенты III курса группы 313ПК

Руководитель: Мозырев Д.С., преподаватель

с. Туринская Слобода, 2017

Содержание

Решение алгебраического уравнения. Для численного решения алгебраических уравнений существует множество способов. Среди самых известных можно назвать метод Ньютона, метод Хорд, и «всепобеждающий» метод Половинного Деления. Сразу оговоримся, что любой метод является приближенным, и по сути дела лишь уточняющим значение корня. Однако уточняющим до любой точности, заданной Нами.

Метод половинного деления или дихотомии (дихотомия - сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f(x)=0 состоит в делении пополам отрезка [a; b], где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка [a; b] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [a; b] становится меньше заданной погрешности нахождения корня е, либо функция попадает в полосу шума е1 - значение функции сравнимо с погрешностью расчетов.

Сначала поставим задачу. Дана монотонная, непрерывная функция f(x), которая содержит корень на отрезке [a,b], где b>a. Определить корень с точностью е, если известно, что f(a)*f(b)<0

Дано уравнение вида:

f(x)=0; (1)

необходимо найти удовлетворяющие ему значения x.

Итак, приступим к решению. Первым делом, определимся, что значит f(x)=0. Посмотрите на рис.1. На нем изображен график некоей функции. В некоторых точках этот график пересекает ось абсцисс. Координаты x этих точек нам и нужно найти. Если вид уравнения простой или стандартный, например, квадратное уравнение или линейное, то применять численный метод здесь совершенно ни к чему. Но если уравнение у нас такое:

f(x)=x3-14x2+x+ex; (2)

то ни в каком учебнике вы не найдете метода аналитического решения этого кошмара. Здесь и приходит на помощь непобедимый численный метод. Метод половинного деления. Из самого названия метода можно предположить, что нам понадобится что-то делить пополам.

Ученикам метод половинного деления можно преподнести в виде решения задачи.

1.2 Примеры решения использовать построение формул

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

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

Какие же факторы принять за существенные в этой задаче? Поскольку речь идет о средневековье, то скорость снаряда и дальность полета невелики. Значит можно считать несущественным, что Земля круглая (помните обсуждение в параграфе 27), и пренебречь сопротивлением воздуха. Остается единственный фактор - сила земного притяжения. В этом случае, как вы знаете из физики, горизонтальное (х) и вертикальное (у) смещение снаряда за время t описывается формулами

,

где g - ускорение свободного падения, v - начальная скорость снаряда, б - угол наклона пушки к горизонту. Эти формулы задают математическую модель полета снаряда. Нас же интересует, на какой высоте окажется снаряд, пролетев расстояние S.

Впрочем, это нетрудно найти. Выразим время полета снаряда на расстояние S из первой формулы:

,

и подставим во вторую:

Следуя нашей задаче, нам требуется найти такое значение угла наклона б, чтобы снаряд, пролетев заданное расстояние S, попал на нужную высоту Н.

Математик тут бы сказал, что надо решить уравнение. Мы тоже будем решать, только приближенно и очень похоже на то, как делают настоящие артиллеристы. Они же поступают следующим образом: производят несколько выстрелов, беря цель «в вилку», т.е. одно попадание выше цели, а другое ниже. Затем делят пополам угол между этими выстрелами, и при стрельбе под таким углом снаряд ложится к цели намного ближе. Но если все же не попали, то новую «вилку» снова делят пополам и т.д.

Мы заранее можем указать «вилку» для угла: 0 и р/4 (мы надеемся, что вы помните какой угол имеет радианную меру р/4 и чему приближенно равно р). А дальше будем делить пополам эту «вилку» и смотреть, куда попадает снаряд, пока не добьемся нужного результата.

Как же долго нам придется вести «пристрелку», чтобы получить угол б, с нужной точностью? Чтобы ответить на этот вопрос, отвлечемся от нашей задачи и сформулируем на чисто математическом языке, что и как мы находили.

Нам даны некоторая функция f(x) и отрезок [a;b], причем на концах этого отрезка эта функция принимает значения противоположных знаков. Если функция непрерывна, т.е. ее график - непрерывная линия, то ясно, что график функции пересекает ось абцисс в некоторой точке с отрезка [a;b], как показано на рисунке 1. Иными словами, f(c)=0, т.е. с - корень уравнения f(x)=0.

Как же предлагается находить этот корень? А вот так. Делим отрезок [a;b] пополам, т.е. берем середину отрезка а+b/2. В этой точке вычисляем значение функции f(x) (рис. 2). Если это значение 0, то корень найден; если нет, то оно имеет тот же знак, что и значение на одном из концов отрезка [a;b]. Тогда этот конец заменям точкой а+b/2. Новый отрезок тоже содержит корень уравнения f(x)=0, поскольку на его концах функция f(x) снова имеет разные знаки. Однако этот отрезок в 2 раза короче предыдущего. И самое главное - с ним можно поступить точно так же. со следующим отрезком еще раз проделать то же самое и т.д. поскольку длина отрезка каждый раз уменьшается вдвое, мы можем получить отрезок сколь угодно малой длины, внутри которого содержится корень уравнения f(x)=0. Например, если исходный отрезок был [3;4], т.е. имел длину 1, то через десять шагов мы получим отрезок длиной . Это означает, что концы отрезка дают нам приближенное значение корня с точностью, равной длине отрезка: левый конец отрезка - приближенное значение корня с недостатком, правый конец - приближенное значение корня с избытком.

Фактически мы сейчас сформулировали метод приближенного решения уравнения f(x)=0. Его можно было бы назвать методом артиллерийской пристрелки. Но математики называют его методом половинного деления.

Далее ученикам предлагается записать алгоритм и блок-схему нахождения корня уравнения с помощью метода половинного деления.

Алгоритм:

Найдем середину отрезка [a; b]: c=(a+b)/2;

Вычислим значения функции в точках a и c и найдем произведение полученных значений: d=f(c)Мf(a);

Если d>0, то теперь точкой a станет c: a=c; Если d<0, то точкой b станет c: b=c;

Вычислим разность a и b, сравним ее с точностью е: если |a-b|> е, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;

половинный деление метод дихотомия

Рисунок 1 Иллюстрация метода половинного деления: 1 - интервал, включающий в себя искомый максимум функции после первого этапа (первого деления пополам); 2, 3 - то же соответственно после второго и третьего этапов

Существует и другой вариант алгоритма, заключающийся в следующем. После нахождения середины отрезка (например, точка с₁) в одной из половинок (допустим, в левой) находят среднюю точку (точка с₂ и, сравнивая значения функции в этих точках, определяют, в какой из половинок находится экстремум. Если R(с₁)< R(с₂), то в качестве следующего отрезка выбираем отрезок [а, с₁], если же R(с₁)> R(с₂), то берут новую точку в середине правой половины (точка с₃) и в ней вычисляют функцию. В зависимости от сравнения значений функции в точках с₃ и с₁ выбирают новый отрезок [с₁, b] или [с₂, с₃] и т.д.

Второй вариант метода не имеет с точки зрения эффективности принципиального отличия от первого, так как эффективность принято оценивать по наихудшему варианту (т.е. по двум вычислениям R(x) на каждом шаге). В первом варианте метода есть одна особенность, которая его делает очень эффективным при экспериментальном отыскании экстремума (например, при автоматической настройке технических систем или при практическом поиске наилучших условий деятельности экономического объекта). Малые отклонения от текущей точки обеспечивают в процессе поиска отсутствие "шараханий", сопровождающихся резкими отклонениями состояния системы.

2. Практическая часть

2.1 Описание решения программы

Программа начинается с директив препроцессора, начинающихся с символа #, которые дают указание препроцессору подключить к программе заголовочные файлы с описанием тех или иных библиотечных функций. В данном случае подключается заголовочный файл stdio.h с описанием функций ввода-вывода, заголовочный файл math.h с описанием математических функций и заголовочный файл conio.h с описанием функции ожидания нажатия клавиши getch().

Программа состоит из двух функций: пользовательской функции f(x) и обязательной функции main(). Функция main() не возвращает никаких значений и поэтому она объявляется с ключевым словом void. В отличие от функции main(), функция f(x) возвращает вещественное значение и объявляется с ключевым словом float. Тела функций являются блоками и поэтому ограничены фигурными скобками.

В теле функции main() объявляются вещественные переменные a, b, e, х.

Далее используется оператор цикла while, в котором применяются условные операторы:

if (выражение) оператор 1; else оператор 2; которые позволяют проверить разные ли знаки у концов отрезка.

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

Тело функции main() закрывается фигурной скобкой. На этом программа заканчивается.

Рисунок 2 Скриншот кода программы

Размещено на http://www.allbest.ru/

2.3 Листинг программы

#include <stdio.h> //подключение библиотек

#include <conio.h>

#include <math.h>

float f(float z) // функция для вычисления f(х)

{

return pow(z,3)+6*pow(z,2)+6*z-7; //возвращаемое значение

}

void main() // главная функция

{

float a=-3.0, b=2.0, e=0.001, x; // объявление переменных

while (fabs(a-b)>=e) // цикл

{

if((f(a)>0&&f((a+b)/2)<0)||(f(a)<0&&f((a+b)/2)>0)) // проверка на разные знаки по //концам отрезка

b=(a+b)/2; // переменной b присваиваем значение (a+b)/2

else

if ((f((a+b)/2)>0&&f(b)<0)||(f((a+b)/2)<0&&f(b)>0)) )) // проверка на разные знаки //по концам отрезка

a=(a+b)/2; // переменной а присваиваем значение (a+b)/2

else

{

printf("! Net kornej !"); //выводим нет корней

return;

getch();

}

}

x=(a+b)/2; // вычисление х после завершения цикла

printf("x=%f F(x)=%f |a-b|=%f",x,f(x),fabs(a-b)); // вывод результатов

getch();

}

Размещено на Allbest.ru