Министерство общего и профессионального образования
Стерлитамакский Государственный Педагогический Институт
кафедра информатики и вычислительной техники
КУРСОВАЯ РАБОТА
«Метод половинного деления в школьном курсе информатики»
Работу выполнили студенты 42 группы ФМФ: Дубовицкий Сергей и Волков Антон
Руководитель: доцент Хусаинова Г.Я.
Стерлитамак 2001
Введение
Метод половинного деления................................................................................................................................................... 4
Задача......................................................................................................................................................................................................... 4
Алгоритм................................................................................................................................................................................................... 6
Блок схема................................................................................................................................................................................................. 7
Заключение............................................................................................................................................................................................... 8
Литература................................................................................................................................................................................................. 9
Целью данной курсовой работы является раскрытие содержания темы «Метод половинного деления» и дальнейшее ее закрепление путем выполнения лабораторной работы и практических заданий.
Одной из главных задач в обучении является развитие творческих и исследовательских способностей учащихся. На уроках информатики применение компьютеров позволяет учащимся заниматься исследовательской работой при решении задач из различных областей (например, физические, математические, экономические задачи). При этом они должны научиться четко формулировать задачу, решать ее и оценивать полученный результат.
Использование новых информационных технологий позволяет решать некоторые задачи нетрадиционными способами, а также решать прикладные задачи, которые ранее не могли рассматриваться в силу сложности математического аппарата. Так, в школьном курсе математики учащиеся рассматривают уравнения, которые имеют точные решения. Однако в реальной практике решение большинства уравнений не может быть записано в явном виде. Их решение находится только приближенными методами. Ранее способы решения таких уравнений рассматривались после изучения одного из алгоритмических языков. Во-первых, разрабатывали алгоритм метода решения (например, итерации, половинного деления). Во-вторых, составляли программу и использовали ее для получения решения и его исследования. Труднее было при изучении темы "Моделирование", когда рассматривали задачи оптимизации. Задачи должны были быть довольно простыми, допускающими только одну поисковую переменную.
В школьном курсе информатики метод половинного деления изучается в 11 классе на 42 уроке при изучении раздела «Компьютерное моделирование», закрепляется тема на 43 уроке в виде Лабораторной работы.
Решение алгебраического уравнения. Для численного решения алгебраических уравнений существует множество способов. Среди самых известных можно назвать метод Ньютона, метод Хорд, и «всепобеждающий» метод Половинного Деления. Сразу оговоримся, что любой метод является приближенным, и по сути дела лишь уточняющим значение корня. Однако уточняющим до любой точности, заданной Нами.
Метод половинного деления или дихотомии (дихотомия - сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f (x)=0 состоит в делении пополам отрезка [ a; b ] , где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка [ a; b ] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [ a; b ] становится меньше заданной погрешности нахождения корня ε , либо функция попадает в полосу шума ε 1 – значение функции сравнимо с погрешностью расчетов.
Сначала поставим задачу. Дана монотонная, непрерывная функция f(x) , которая содержит корень на отрезке , где b>a . Определить корень с точностью ε , если известно, что f(a)*f(b)<0
Дано уравнение вида:
f(x)=0 ; (1)
необходимо найти удовлетворяющие ему значения x .
Итак, приступим к решению. Первым делом, определимся, что значит f(x)=0 . Посмотрите на рис.1. На нем изображен график некоей функции. В некоторых точках этот график пересекает ось абсцисс. Координаты x этих точек нам и нужно найти. Если вид уравнения простой или стандартный, например, квадратное уравнение или линейное, то применять численный метод здесь совершенно ни к чему. Но если уравнение у нас такое:
f(x)=x3-14x2+x+ex ; (2)
то ни в каком учебнике вы не найдете метода аналитического решения этого кошмара. Здесь и приходит на помощь непобедимый численный метод. Метод половинного деления. Из самого названия метода можно предположить, что нам понадобится что-то делить пополам.
Ученикам метод половинного деления можно преподнести в виде решения задачи.
Задача
Идет осада неприятельской крепости. На некотором расстоянии от нее установили новую пушку. Под каким углом к горизонту надо стрелять из этой пушки, чтобы попасть в заданный участок крепостной стены.
Над моделью этой задачи физики изрядно поработали. Оно и понятно: ведь многие научные задачи, как и эта, возникали прежде всего в военном деле. И решение этих задач почти всегда считалось приоритетным.
Какие же факторы принять за существенные в этой задаче? Поскольку речь идет о средневековье, то скорость снаряда и дальность полета невелики. Значит можно считать несущественным, что Земля круглая (помните обсуждение в параграфе 27), и пренебречь сопротивлением воздуха. Остается единственный фактор – сила земного притяжения. В этом случае, как вы знаете из физики, горизонтальное (х) и вертикальное (у) смещение снаряда за время t описывается формулами
,![](https://i0.wp.com/mirznanii.com/images/24/47/9324724.png)
где g – ускорение свободного падения, v – начальная скорость снаряда, α – угол наклона пушки к горизонту. Эти формулы задают математическую модель полета снаряда. Нас же интересует, на какой высоте окажется снаряд, пролетев расстояние S .
Впрочем, это нетрудно найти. Выразим время полета снаряда на расстояние S из первой формулы:
,и подставим во вторую:
![](https://i1.wp.com/mirznanii.com/images/26/47/9324726.png)
Следуя нашей задаче, нам требуется найти такое значение угла наклона α, чтобы снаряд, пролетев заданное расстояние S , попал на нужную высоту Н .
Математик тут бы сказал, что надо решить уравнение. Мы тоже будем решать, только приближенно и очень похоже на то, как делают настоящие артиллеристы. Они же поступают следующим образом: производят несколько выстрелов, беря цель «в вилку», т.е. одно попадание выше цели, а другое ниже. Затем делят пополам угол между этими выстрелами, и при стрельбе под таким углом снаряд ложится к цели намного ближе. Но если все же не попали, то новую «вилку» снова делят пополам и т.д.
Мы заранее можем указать «вилку» для угла: 0 и π/4 (мы надеемся, что вы помните какой угол имеет радианную меру π/4 и чему приближенно равно π ). А дальше будем делить пополам эту «вилку» и смотреть, куда попадает снаряд, пока не добьемся нужного результата.
Как же долго нам придется вести «пристрелку», чтобы получить угол α , с нужной точностью? Чтобы ответить на этот вопрос, отвлечемся от нашей задачи и сформулируем на чисто математическом языке, что и как мы находили.
Нам даны некоторая функция f(x) и отрезок , причем на концах этого отрезка эта функция принимает значения противоположных знаков. Если функция непрерывна, т.е. ее график – непрерывная линия, то ясно, что график функции пересекает ось абцисс в некоторой точке с отрезка , как показано на рисунке 1. Иными словами, f(c) =0 , т.е. с - корень уравнения f(x)=0 .
Как же предлагается находить этот корень? А вот так. Делим отрезок пополам, т.е. берем середину отрезка а+ b/2 . В этой точке вычисляем значение функции f(x) (рис. 2). Если это значение 0, то корень найден; если нет, то оно имеет тот же знак, что и значение на одном из концов отрезка . Тогда этот конец заменям точкой а+ b/2 . Новый отрезок тоже содержит корень уравнения f(x)=0 , поскольку на его концах функция f(x) снова имеет разные знаки. Однако этот отрезок в 2 раза короче предыдущего. И самое главное – с ним можно поступить точно так же . со следующим отрезком еще раз проделать то же самое и т.д. поскольку длина отрезка каждый раз уменьшается вдвое, мы можем получить отрезок сколь угодно малой длины, внутри которого содержится корень уравнения f(x)=0 . Например, если исходный отрезок был , т.е. имел длину 1 , то через десять шагов мы получим отрезок длиной
![](https://i2.wp.com/mirznanii.com/images/27/47/9324727.png)
Нелинейные уравнения можно разделить на 2 класса - алгебраические и трансцендентные. Алгебраическими уравнениями называют уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и другие) называются трансцендентными.
Методы решения нелинейных уравнений делятся на две группы:
- точные методы ;
- итерационные методы .
Точные методы позволяют записать корни в виде некоторого конечного соотношения (формулы). Из школьного курса алгебры известны такие методы для решения тригонометрических, логарифмических, показательных, а также простейших алгебраических уравнений.
Как известно, многие уравнения и системы уравнений не имеют аналитических решений. В первую очередь это относится к большинству трансцендентных уравнений. Доказано также, что нельзя построить формулу, по которой можно было бы решить произвольное алгебраическое уравнение степени выше четвертой. Кроме того, в некоторых случаях уравнение содержит коэффициенты, известные лишь приблизительно, и, следовательно, сама задача о точном определении корней уравнения теряет смысл. Для их решения используются итерационные методы с заданной степенью точности.
Пусть дано уравнение
- Функция f (x ) непрерывна на отрезке [a, b ] вместе со своими производными 1-го и 2-го порядка.
- Значения f (x ) на концах отрезка имеют разные знаки (f (a ) * f (b ) < 0).
- Первая и вторая производные f" (x ) и f"" (x ) сохраняют определенный знак на всем отрезке.
Условия 1) и 2) гарантируют, что на интервале [a, b ] находится хотя бы один корень, а из 3) следует, что f (x ) на данном интервале монотонна и поэтому корень будет единственным.
Решить уравнение (1) итерационным методом значит установить, имеет ли оно корни, сколько корней и найти значения корней с нужной точностью.
Всякое значение , обращающее функцию f (x ) в нуль, т.е. такое, что:
называется корнем уравнения (1) или нулем функции f (x ).
Задача нахождения корня уравнения f (x ) = 0 итерационным методом состоит из двух этапов:
- отделение корней - отыскание приближенного значения корня или содержащего его отрезка;
- уточнение приближенных корней - доведение их до заданной степени точности.
Процесс отделения корней начинается с установления знаков функции f (x ) в граничных x = a и x = b точках области ее существования.
Пример 1. Отделить корни уравнения:
f(x ) є x 3 - 6х + 2 = 0. |
Составим приблизительную схему:
Следовательно, уравнение (2) имеет три действительных корня, лежащих в интервалах [-3, -1], и .
Приближенные значения корней (начальные приближения ) могут быть также известны из физического смысла задачи, из решения аналогичной задачи при других исходных данных, или могут быть найдены графическим способом.
В инженерной практике распространен графический способ определения приближенных корней.
Принимая во внимание, что действительные корни уравнения (1) - это точки пересечения графика функции f (x ) с осью абсцисс, достаточно построить график функции f (x ) и отметить точки пересечения f (x ) с осью Ох, или отметить на оси Ох отрезки, содержащие по одному корню. Построение графиков часто удается сильно упростить, заменив уравнение (1) равносильным ему уравнением:
Уравнение (4) удобно переписать в виде равенства:
Отсюда ясно, что корни уравнения (4) могут быть найдены как абсциссы точек пересечения логарифмической кривой y = lg x и гиперболы y = . Построив эти кривые, приближенно найдем единственный корень уравнения (4) или определим его содержащий отрезок .
Итерационный процесс состоит в последовательном уточнении начального приближения х 0 . Каждый такой шаг называется итерацией . В результате итераций находится последовательность приближенных значений корня х 1 , х 2 , ..., х n . Если эти значения с увеличением числа итераций n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится .
Для нахождения корня уравнения (1), принадлежащего отрезку [a, b ], делим этот отрезок пополам. Если f = 0 , то x = является корнем уравнения. Если f не равно 0 (что, практически, наиболее вероятно), то выбираем ту из половин или , на концах которой функция f (x ) имеет противоположные знаки. Новый суженный отрезок [ а 1 , b 1] снова делим пополам и производим те же самые действия.
Метод половинного деления практически удобно применять для грубого нахождения корня данного уравнения, метод прост и надежен, всегда сходится.
Пример 3. Методом половинного деления уточнить корень уравнения
f(x ) = x 4 + 2 x 3 - x - 1 = 0
лежащий на отрезке [ 0, 1] .
Последовательно имеем:
f(0) = - 1; f (1) = 1; f (0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;
f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;
f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;
f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;
f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;
f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043 и т. д.
Можно принять
x = (0,859 + 0,875) = 0,867
В данном методе процесс итераций состоит в том, что в качестве приближений к корню уравнения (1) принимаются значения х 1 , х 2 , ..., х n точек пересечения хорды АВ с осью абсцисс (Рисунок 3). Сначала запишем уравнение хорды AB :
.
Для точки пересечения хорды AB с осью абсцисс (х = х 1 , y = 0) получим уравнение:
Пусть для определенности f"" (x ) > 0 при а х b (случай f"" (x ) < 0 сводится к нашему, если записать уравнение в виде - f (x ) = 0). Тогда кривая у = f (x ) будет выпукла вниз и, следовательно, расположена ниже своей хорды АВ . Возможны два случая: 1) f (а ) > 0 (Рисунок 3, а ) и 2) f (b ) < 0 (Рисунок 3, б ).
Рисунок 3, а, б.
В первом случае конец а неподвижен и последовательные приближения: x 0 = b ;x , где функция f (х ) имеет знак, противоположный знаку ее второй производной f"" (х ).
Итерационный процесс продолжается до тех пор, пока не будет обнаружено, что
| x i - x i - 1 |< e ,
где e - заданная предельная абсолютная погрешность.
Пример 4. Найти положительный корень уравнения
f(x ) = x 3 - 0,2 x 2 - 0,2 х - 1,2 = 0
с точностью e = 0,01.
Прежде всего, отделяем корень. Так как
f (1) = -0,6 < 0 и f (2) = 5,6 > 0,
то искомый корень x лежит в интервале . Полученный интервал велик, поэтому разделим его пополам. Так как
f (1,5) = 1,425 > 0, то 1< x < 1,5.
Так как f"" (x ) = 6 x - 0,4 > 0 при 1 < х < 1,5 и f (1,5) > 0, то воспользуемся формулой (5) для решения поставленной задачи:
= 1,15;
| x 1 - x 0 | = 0,15 > e ,
следовательно, продолжаем вычисления;
f (х 1) = -0,173;
= 1,190;
|x 2 - x 1 | = 0,04 > e ,
f (х 2) = -0,036;
= 1,198;
| x 3 - x 2 | = 0,008 < e .
Таким образом, можно принять x = 1,198 с точностью e = 0,01.
Заметим, что точный корень уравнения x = 1,2.
Иванов Иван
При прохождении темы численные методы учащиеся уже умеют работать с электронными таблицами и составлять программы на языке паскаль. Работа комбинированного характера.Расчитана на 40 минут. Цель работы повторить и закрепить навыки паботы с программами EXCEL, ABCPascal. Материал содержит 2 файла. Один содержит теоретический материал, так как он и предлагается ученику. Во 2-м файле пример работы ученика Иванова Ивана.
Скачать:
Предварительный просмотр:
Решение уравнений
Аналитическое решение некоторых уравнений, содержащих, например тригонометрические функции может быть получено лишь для единичных частных случаев. Так, например, нет способа решить аналитически даже такое простое уравнение, как cos x=x
Численные методы позволяют найти приближенное значение корня с любой заданной точностью.
Приближённое нахождение обычно состоит из двух этапов:
1) отделение корней, т.е. установление возможно точных промежутков , в которых содержится только один корень уравнения;
2) уточнение приближённых корней, т.е. доведение их до заданной степени точности.
Мы будем рассматривать решения уравнений вида f(x)=0. Функция f(x) определена и непрерывна на отрезке [а.Ь]. Значение х 0 называется корнем уравнения если f(х 0 )=0
Для отделения корней будем исходить из следующих положений:
- Если f(a)* f(b] \a, b\ существует, по крайней мере, один корень
- Если функция y = f(x) непрерывна на отрезке , и f(a)*f(b) и f "(x) на интервале (a, b) сохраняет знак, то внутри отрезка [а, b] существует единственный корень уравнения
Приближённое отделение корней можно провести и графически. Для этого уравнение (1) заменяют равносильным ему уравнением р(х) = ф(х), где функции р(х) и ф(х] более простые, чем функция f(x). Тогда, построив графики функций у = р(х) и у = ф(х), искомые корни получим, как абсциссы точек пересечения этих графиков
Метод дихотомии
Для уточнения корня разделим отрезок [а, b] пополам и вычислим значение функции f(х) в точке x sr =(a+b)/2. Выбираем ту из половин или , на концах которых функция f(x) имеет противоположные знаки.. Продолжаем процесс деления отрезка пополам и проводим то же рассмотрение до тех пор, пока. длина станет меньше заданной точности . В последнем случае за приближённое значение корня можно принять любую точку отрезка (как правило, берут его середину). Алгоритм высокоэффективен, так как на каждом витке (итерации) интервал поиска сокращается вдвое; следовательно, 10 итераций сократят его в тысячу раз. Сложности могут возникнуть с отделением корня у сложных функций.
Для приближенного определения отрезка на котором находится корень можно воспользоваться табличным процессором, построив график функции
ПРИМЕР : Определим графически корень уравнения . Пусть f1(х) = х , a и построим графики этих функций. (График). Корень находится на интервале от 1 до 2. Здесь же уточним значение корня с точностью 0,001(на доске шапка таблицы)
Алгоритм для программной реализации
- а:=левая граница b:= правая граница
- m:= (a+b)/2 середина
- определяем f(a) и f(m)
- если f(a)*f(m)
- если (a-b)/2>e повторяем, начиная с пункта2
Метод хорд.
Точки графика функции на концах интервала соединяются хордой. Точка пересечения хорды и оси Ох (х*) и используется в качестве пробной. Далее рассуждаем так же, как и в предыдущем методе: если f(x a ) и f(х*) одного знака на интервале, нижняя граница переносится в точку х*; в противном случае – переносим верхнюю границу. Далее проводим новую хорду и т.д.
Осталось только уточнить, как найти х*. По сути, задача сводится к следующей: через 2 точки с неизвестными координатами (х 1 , у 1 ) и (х 2 , у 2 ) проведена прямая; найти точку пересечения этой прямой и оси Ох.
Запишем уравнение прямой по двум точках:
В точке пересечения этой прямой и оси Ох у=0, а х=х*, то есть
Откуда
процесс вычисления приближённых значений продолжается до тех пор, пока для двух последовательных приближений корня х„ и х п _1 не будет выполняться условие abs(xn-x n-1 ) е - заданная точность
Сходимость метода гораздо выше предыдущего
Алгоритм различается только в пункте вычисления серединной точки- пересечения хорды с осью абсцисс и условия останова (разность между двумя соседними точками пересечения)
Уравнения для самостоятельного решения: (отрезок в excel ищем самостоятельно)
- sin(x/2)+1=x^2 (х=1,26)
- x-cosx=0 (х=0,739)
- x^2+4sinx=0 (х=-1,933)
- x=(x+1) 3 (х=-2,325)
Пусть f (x ) – непрерывная функция на [a ; b ], .
![](https://i1.wp.com/studfiles.net/html/2706/38/html_Za90bBDl5T.GXB8/img-Hhu1dt.png)
Метод Ньютона (метод касательных)
Пусть
f
(x
)
– дважды непрерывно дифференцируемая
функция на отрезке [a
;
b
],
,
и
не меняют знак на [a
;
b
].
Обозначим
через
тот конец отрезка, где знаки
и
совпадают. Последовательные приближения
к точному корнюc
находим по формуле
для
.
Тогда
является точным корнем уравнения (1).
Вычислительный
процесс обычно останавливают, когда
оказывается меньше заданной точностиε
.
Однако это условие не может строго
гарантировать, что заданная точность
достигнута. Для полной гарантии можно
выполнить проверку точности, как было
указано в начале раздела. Если точность
не достигнута, то нужно повторить
итерации еще несколько раз.
Метод секущих
Пусть
есть какое-то начальное приближение
.
Получим еще одну точку по формуле
,
гдеh
– небольшое число. Будем считать, что
мы выполнили несколько шагов метода, и
к данному моменту у нас есть два
последовательных приближения
и
к точному корню (на начальном этапе –
это
и
).
Тогда следующее приближение находим
по формуле
,
Процесс останавливается по такому же критерию, как и в методе Ньютона.
Метод итераций
В
методе итераций исходное уравнение (1)
преобразуется в равносильное уравнение
.
Выбирается начальное приближение
.
Каждое следующее приближение получается
по формуле
,
Процесс останавливается по тому же
критерию, что и в методе Ньютона. Метод
будет сходиться, т.е. предел
равен точному значению корня, если в
окрестности корня выполнено неравенство
и начальное приближение находится
достаточно близко к корню.
Преимущества и недостатки методов
Метод половинного деления требует отделения корня, и для достижения высокой точности приходится вычислять функцию много раз. Достижение заданной точности в этом методе гарантировано.
Метод Ньютона обладает очень быстрой сходимостью (квадратичная сходимость), т.е.
,
где c – точное значение корня; M – некоторая константа, зависящая от функции. Грубо говоря, начиная с некоторой итерации, число верных знаков после запятой станет удваиваться на каждой итерации.
Для гарантии сходимости метода Ньютона требуется выполнение довольно многих условий. Вообще говоря, начать вычисления по методу Ньютона можно и без проверки этих условий, но тогда сходимость может не наблюдаться.
Метод секущих обеспечивает для гладких функций скорость сходимости, близкую к скорости сходимости метода Ньютона. Он не требует вычисления производной функции. Если начальная точка взята далеко от корня, то сходимость может отсутствовать.
Метод
итераций дает скорость сходимости
значительно меньшую, чем метод Ньютона.
При наличии сходимости действует оценка
,
где
– числа,
,
;c
–точное значение корня. Величины M
,
q
зависят от функции и не зависят от
номера итерации. Если же
близок к 1, тоq
тоже близко к 1 и сходимость метода будет
медленной. Счет по методу итераций можно
начать без проверки условий на
и
.
В этом случае процесс может оказаться
расходящимся, и тогда ответ не будет
получен.
Существует
много методов нахождения корней
нелинейного уравнения, отличных от
перечисленных. В MATHCAD
функция root
в формате
использует метод секущих, а если он не
приводит к желаемым результатам, то –
метод Мюллера. В последнем, в отличие
от метода секущих, на каждом шаге берутся
две дополнительные точки, график функции
заменяется параболой, проходящей через
три точки, и за следующее приближение
берется точка пересечения параболы с
осьюOx
.
В функции root
в формате root(f
(x
),
x
,
a
,
b
)
используются методы Риддера и Брента.
Для нахождения корней многочлена в
MATHCAD
используется метод Лагерра.
Метод половинного деления
(другие названия: метод бисекций
, метод дихотомии
) для решения уравнения f
(x
) = 0 заключается в следующем . Пусть известно, что функция непрерывна и принимает на концах отрезка
[a
, b
] значения разных знаков, тогда корень содержится в интервале (a
, b
). Разделим интервал на две половины и дальше будем рассматривать ту половину, на концах которой функция принимает значения разных знаков. Этот новый отрезок снова делим на две равные части и выбираем из них ту, которая содержит корень. Этот процесс продолжается до тех пор, пока длина очередного отрезка не станет меньше требуемой величины погрешности. Более строгое изложение алгоритма метода половинного деления:
1) Вычислим x = (a + b )/2; вычислим f (x );
2) Если f (x ) = 0, то переходим к пункту 5;
3) Если f (x )∙ f (a ) < 0, то b = x , иначе a = x ;
4) Если |b – a | > ε, переходим к пункту 1;
5) Выводим значение x ;
Пример 2.4. Уточнить методом бисекций с точностью до 0,01 корень уравнения (x – 1) 3 = 0, принадлежащий отрезку .
Решение в программе Excel :
1) В ячейках A 1:F 4 введем обозначения, начальные значения и формулы, как показано в таблице 2.3.
2) Каждую формулу скопируем в нижние ячейки маркером заполнения до десятой строки, т.е. B 4 - до B 10, C 4 - до C 10, D 3 - до D 10, E 4 - до E 10, F 3 - до F 10.
Таблица 2.3
A | B | C | D | E | F | |
f(a)= | =(1-B3)^3 | |||||
k | a | x | f(x) | b | b-a | |
0,95 | =(B3+E3)/2 | =(1-C3)^3 | 1,1 | =E3-B3 | ||
=ЕСЛИ(D3=0;C3; ЕСЛИ(C$1*D3<0;B3;C3)) | =ЕСЛИ(C$1*D3>0; E3;C3) |
Результаты расчетов приведены в табл. 2.4. В столбце F проверяем значения длины интервала b – a . Если значение меньше чем 0,01, то в данной строке найдено приближенное значение корня с заданной погрешностью. Потребовалось 5 итераций для достижения требуемой точности. Приближенное значение корня с точностью до 0,01 после округления до трех знаков равно 1,0015625 ≈ 1,00.
Таблица 2.4
A | B | C | D | E | F | |
f(a)= | 0,000125 | |||||
k | a | x | f(x) | b | b-a | |
0,95 | 1,025 | -2E-05 | 1,1 | 0,15 | ||
0,95 | 0,9875 | 2E-06 | 1,025 | 0,075 | ||
0,9875 | 1,00625 | -2E-07 | 1,025 | 0,0375 | ||
0,9875 | 0,996875 | 3,1E-08 | 1,00625 | 0,0187 | ||
0,996875 | 1,0015625 | -4E-09 | 1,00625 | 0,0094 | ||
0,996875 | 0,9992188 | 4,8E-10 | 1,0015625 | 0,0047 | ||
0,99921875 | 1,0003906 | -6E-11 | 1,0015625 | 0,0023 | ||
0,99921875 | 0,9998047 | 7,5E-12 | 1,000390625 | 0,0012 |
Приведенный алгоритм учитывает возможный случай «попадания в корень», т.е. равенство f (x ) нулю на очередном этапе. Если в примере 2.3 взять отрезок , то на первом же шаге попадаем в корень x = 1. Действительно, запишем в ячейке B 3 значение 0,9. Тогда таблица результатов примет вид 2.5 (приведены только 2 итерации).
Таблица 2.5
A | B | C | D | E | F | |
f(a)= | 0,001 | |||||
k | a | x | f(x) | b | b-a | |
0,9 | 1,1 | 0,2 | ||||
Создадим в программе Excel пользовательские функции f(x) и bisect(a, b, eps) для решения уравнения методом половинного деления, пользуясь встроенным языком Visual Basic . Их описания приведены ниже:
Function f(Byval x)
Function bisect(a, b, eps)
1 x = (a + b) / 2
If f(x) = 0 Then GoTo 5
If f(x) * f(a) < 0 Then
If Abs(a - b) > eps Then GoTo 1
Функция f(x) определяет левую часть уравнения, а функция
bisect(a, b, eps) вычисляет методом половинного деления корень уравнения f
(x
) = 0. Обратим внимание на то, что в функции bisect(a, b, eps) используется обращение к функции f(x). Приведем алгоритм создания пользователькой функции:
1) Выполним команду меню «Сервис - Макрос - Редактор Visual Basic ». Откроется окно «Microsoft Visual Basic ». Если в данном файле программы Excel ещё не были созданы макросы или пользовательские функции или процедуры, это окно будет иметь вид, изображенный на рис.2.4.
2) Выполним команду меню «Insert - Module» и вводим тексты программ-функции, как показано на рис 2.5.
Теперь в ячейках листа программы Excel можно в формулах использовать созданные функции. Например, введем в ячейку D 18 формулу
Bisect(0,95;1;0,00001),
то получим значение 0,999993896.
Чтобы решить другое уравнение (с другой левой частью) нужно перейти в окно редактора с помощью команды «Сервис - Макрос - Редактор Visual Basic » и просто переписать описание функции f(x). Например, найдем с точностью до 0,001 корень уравнения sin5x + x 2 – 1 = 0, принадлежащий интервалу (0,4; 0,5). Для этого изменим описание функции
на новое описание
f = Sin(5 * x) + x ^ 2 - 1
Тогда в ячейке D 18 получим значение 0,441009521 (сравните этот результат со значением корня из интервала (0,4; 0,5), найденным в примере 2.3!).
Для решения уравнения методом половинного деления в программе Mathcad создадим подпрограмму-функцию bisec (f , a , b , ε), где:
f - имя функции, соответствующее левой части уравнения f (x ) = 0;
a , b - левый и правый концы отрезка [a , b ];
ε - точность приближенного значения корня.
Решение примера в программе Mathcad :
1) Запускаем программу Mathcad. Введем определение функции bisec (f , a , b , ε). Для этого с помощью клавиатуры и панели инструментов «Греческие символы» набираем bisec (f , a , b , ε):=. После знака присваивания «:=» на панели инструментов «Программирование» указателем мыши щелкаем левой кнопкой «Add line». После знака присваивания появится вертикальная линия. Далее вводим текст программы, который приведен ниже, используя панель инструментов «Программирование» для ввода знака «←», оператора цикла while , оператора break и условного оператора if otherwise .
2) Введем определение функции f
(x
):=sin(5*x)+x^2–1, а затем вычислим значение корня с помощью функции bisec
при заданных значениях:
bisec
(f
, –0.8,–0.7,0.0001)=. После знака «=» автоматически появится вычисленное программой значение корня –0,7266601563. Аналогично вычислим остальные корни.
Ниже приведен лист Mathcad с определением функции bisec (f , a , b , ε) и расчетами:
Приведем программу на языке C ++ для решения уравнения f (x ) = 0 методом половинного деления:
#include
#include
double f(double x);
typedef double (*PF)(double);
double bisec(PF f,double a, double b,double eps);
double a, b, x, eps;PF pf;
cout << "\n a = "; cin >> a;
cout << "\n b = "; cin >> b;
cout << "\n eps = "; cin >> eps;
x = bisec(pf,a,b,eps); cout << "\n x = " << x;
cout << "\n Press any key & Enter "; cin >> a;
double f(double x){
r = sin(5*x)+x*x-1;
double bisec(PF f, double a, double b,double eps){
do{ x = (a + b)/2;
if (f(x) == 0) break;
if (f(x)*f(a)<0) b = x;
}while (fabs(b-a) > eps);
В программе функция f (x ) определена для решения уравнения
sin5x + x 2 – 1 = 0
из примера 2.3. Результат работы программы для определения корня из интервала (0,4; 0,5) с точностью 0,00001 представлен ниже (экран компьютера):
Press any key & Enter
Последняя строка нужна для организации паузы для просмотра результата.