Метод половинного деления отрезка. Методы дихотомии

Существует довольно очевидная теорема: "Если непрерывная функция на концах некоторого интервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но м.б. и несколько)" . На базе этой теоремы построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется дихотомией , т.е. делением отрезка на две части . Обобщенный алгоритм выглядит так:

Пока не будет достигнута нужная точность.

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд .

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

Метод половинного деления известен также как метод бисекции . В данном методе интервал делится ровно пополам.

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

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

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

Метод половинного деления как метод поиска корней функции

Изложение метода

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

Будем считать, что корень функции отделён на отрезке . Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления. Другими словами, требуется найти приближённое значение корня с заданной точностью .

Пусть функция непрерывна на отрезке ,

(Мы не рассматриваем случай, когда корней на отрезке несколько, то есть более одного. В качестве можно взять и другое достаточно малое положительное число, например, .)

Поделим отрезок пополам. Получим точку и два отрезка .

Для того, чтобы найти приближённое значение корня с точностью до 0" alt=" \eps >0">, необходимо остановить процесс половинного деления на таком шаге , на котором и вычислить . Тогда можно взять .

Реализация метода на С++ и числовой пример

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

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

Программа 1. Корень уравнения

#include #include using namespace std; const double epsilon = 1e-2 ; double f(double x) { return 4 - exp (x) - 2 * x^ 2 ; } int main() { double a, b, c; a = 0 ; b = 2 ; while (b - a > epsilon) { c = (a + b) / 2 ; if (f(b) * f(c) < 0 ) a = c; else b = c; } cout << (a + b) / 2 << endl; return 0 ; }

Искомый корень . Вычисления проводились с точностью .

Промежуточные вычисления представлены в таблице ниже.

Метод половинного деления как метод оптимизации

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

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

Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

Запишем словесный алгоритм метода.

Схема алгоритма метода представлена на рис 2.

При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.

Метод хорд

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

Изложение метода

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

При этом в процессе поиска семейство хорд может строиться:

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

• для случая а):

• для случая б):

Процесс поиска продолжается до тех пор, пока не выполнится условие или .

Метод обеспечивает быструю сходимость, если %200" alt="f(z)\cdot f""(z) > 0">, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.

Комбинация метода хорд и метода половинного деления

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

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

Считаем, что отделение корней уравнения f (x ) = 0 проведено и на отрезке [ a , b ] расположен один корень, который необходимо уточнить с погрешностью ε. В качестве начального приближения корня принимаем середину этого отрезка: c 0 = (a + b) / 2 (рис. 4):

Рис. 4. Метод половинного деления.

Затем исследуем значение функции f (x ) на концах отрезков [ a , c 0 ] и [ c 0 , b ] . Тот из отрезков, на концах которого f (x ) принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка [ a 1 , b 1 ] (на рис. 4 это отрезок [ a , c 0 ]). Вторую половину отрезка [ a , b ], на которой f (x ) не меняет знак, отбрасываем. В качестве следующего приближения корня принимаем середину нового отрезка
c 1 = (a 1 + b 1 ) / 2 и т.д. Таким образом, k -е приближение вычисляется как

После каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после k итераций в 2 k раз:

Прекратить итерационный процесс следует, когда будет достигнута заданная точность, т.е. при выполнении условия |x 0 – c k | < ε

Поскольку корень x 0 принадлежит отрезку [ a k , b k ], а c k – середина этого отрезка, то величина |x 0 – c k | всегда будет меньше половины длины от резка [ a k , b k ] (см. рис. 4):

Следовательно, условие |x 0 – c k | < ε будет выполнено, если

| b k – a k | < 2ε

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполнено условие | b k – a k | < 2ε .

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

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

поэтому данный метод является методом с линейной сходимостью.

З а м е ч а н и е . Метод половинного деления не требует знания дополнительной информации о функции на всем интервале [ a , b ]. Например, не требуется, чтобы функция была дифференцируема. Даже для разрывных функций рассмотренный метод обладает гарантированной сходимостью. Если на этом интервале существует несколько корней уравнения, один из корней обязательно будет найден.

Метод хорд

Рассматриваемый метод так же, как и метод половинного деления, предназначен для уточнения корня на интервале [ a , b f (x ) принимает значения разных знаков. Очередное приближение в отличие от метода половинного деления берем не в середине отрезка, а в точке x , где пересекает ось абсцисс прямая линия (хорда), проведенная через точки А и В (рис. 5).

Рис. 5. Метод хорд.

Запишем уравнение прямой, проходящей через точки А и В :

Для точки пересечения прямой с осью абсцисс (x = x 0 , y = 0) получим уравнение

В качестве нового интервала для продолжения итерационного процесса выбираем тот из двух [ a , x 0 ] и [ x 0 , b ], на концах которого функция f (x ) принимает значения разных знаков. Для рассматриваемого случая (рис. 5) выбираем отрезок [ a , x 0 ], так как
f(a) × f(x 0) < 0 . Следующая итерация состоит в определении нового приближения x 1 как точки пересечения хорды AB 1 с осью абсцисс и т.д.

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

x k +1 – x k < ε

З а м е ч а н и е . Метод хорд и метод половинного деления очень похожи. При этом второй их них в ряде случаев дает более быструю сходимость итерационного процесса. Оба метода не требуют знания дополнительной информации о функции на всем интервале [ a , b ]. Например, не требуется, чтобы функция была дифференцируема. Даже для разрывных функций рассмотренные методы обладают гарантированной сходимостью.

Метод Ньютона (метод касательных)

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

Отделяя корни функции, следует учесть, что применение метода Ньютона требует, чтобы функция была монотонна и дважды дифференцируема, причем вторая производная f’’(x) на этом интервале не должна менять знак.

Cходимость итерационной последовательности, получаемой в методе Ньютона, зависит от выбора начального приближения x 0 . В общем случае, если задан интервал [ a , b ], содержащий корень, и известно, что функция f (x ) монотонна на этом интервале, то в качестве начального приближения x 0 можно выбрать ту границу отрезка [ a , b ], где совпадают знаки функции f (x ) и второй производной f’’(x) . Такой выбор начального приближения гарантирует сходимость метода Ньютона при условии монотонности функции на отрезке локализации корня.

Пусть нам известно начальное приближение к корню x 0 . Проведем в этой точке касательную к кривой y = f (x ) (рис. 6). Эта касательная пересечет ось абсцисс в точке, которую будем рассматривать в качестве следующего приближения.

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

Разделим отрезок пополам точкой. Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке (Рис. 3.8), либо на отрезке (Рис. 3.9)

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

Пример 4. Уравнение 5x - 6x -3 = 0 имеет единственный корень на отрезке . Решить это уравнение методом половинного деления.

Решение : Программа на языке Паскаль может быть такой:

function f(x: real): real;

f:=exp(x*ln(5))-6*x-3;

a, b, e, c, x: real;

while abs(b-a)>e do

if f(a)*f(c)<0 then

writeln ("x=",x:3:3," f(x)=",f(x):4:4);

Результат выполнения программы:

e=0.001 x=1.562 f(x)=-0.0047

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

1.Определить новое приближение корня х в середине отрезка [а,b]: х=(а+b)/2.

2.Найти значения функции в точках а и х : F(a) и F(x) .

3.Проверить условие F(a)*F(x) < 0 . Если условие выполнено, то корень расположен на отрезке [а,х] b переместить в точку х (b=х) . Если условие не выполнено, то корень расположен на отрезке [х,b] . В этом случае необходимо точку а переместить в точку х (а=х) .

4.Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие /F(x)/ < e (заданная точность).

21.Метод простой итерации для поиска корней. Геометрическая интерпретация .

Исходное уравнение f(x)=0 эквивалентными преобразованиями приводится к виду с выделением неизвестного в левой части, то есть x=φ(x),где φ(x) – некоторая функция, связанная с исходной функцией f(x). Такая форма записи уравнения позволяет, задаваясь начальным приближением x 0, получить следующее, первое приближение x 1 =φ(x 0), далее получают второе приближение x 2 =φ(x 1) и так далее x n +1 =φ(x n)…. Последовательность {x n }= x 0, x 1, x 2, …, x n ,… называется последовательностью итераций или приближений с начальным значением x 0. Если функция φ(x) на непрерывна и существует предел ξ = lim x n при n→∞, то, переходя к пределу в равенстве x n +1 =φ(x n), найдем, что при n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n), то есть ξ=φ(ξ).Следовательно, если последовательность приближений сходится, то она сходится к корню уравнения (2), а значит и уравнения (1). В силу сходимости итерационного процесса этот корень можно вычислить при достаточно большом n с любой заданной точностью. Однако необходимо определить при каких условиях последовательность {x n }будет сходящейся. Получим связь между погрешностями двух соседних приближений - ε n и ε n +1: x n =ξ+ε n , x n +1 =ξ+ε n +1. Подставим эти представления в x n +1 =φ(x n) и разложим функцию в ряд Тейлора в окрестности корня:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ’(ξ)+(ε n 2 /2!)φ’’(η), где η Î [ξ; ξ+ε n ] Ì .Поскольку ξ - корень, то ξ=φ(ξ) , то получаем: ε n +1 =ε n φ’(ξ)+(φ’’(η)/2)ε n 2 .Так как ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n |ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.

Теорема о сходимости метода простых итераций. Пусть ξ - корень уравнения x=φ(x), функция φ(x) определена и дифференцируема на отрезке , причем для x Î все значения функции φ (x) Î . Тогда, если существует такое положительное число q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ’(х)>-1, то соседние приближения лежат по разную сторону от корня – такую сходимость называют двусторонней (или спиралевидной) – рис.2. Поскольку в этом случае корень заключен в интервале, концами которого являются соседние приближения – ξÎ(x n ,x n +1), то выполнение условия |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.

Чтобы можно было сравнивать итерационные методы по скорости сходимости, вводят следующие понятия:

Определение 1: Сходимость последовательности {x n } к ξ называется линейной (соответственно, итерационный процесс - линейно сходящимся ), если существует такая постоянная CÎ(0,1) и такой номер n 0 , что выполняются неравенства |ξ-x n +1 |≤C|ξ-x n | для n≥n 0.

Для введенных ранее погрешностей это означает |ε n+1 |≤C|ε n |. В методе простой итерации в роли постоянной C выступает значение q, то есть метод сходится линейно.

Определение 2: Последовательность приближений {x n } сходится к ξ по меньшей мере с р -ым порядком (соответственно, итерационный процесс имеет по меньшей мере p -ый порядок), если найдутся такие константы C>0, p ≥1 и n 0 , что для всех n≥n 0 выполняются условия |ξ-x n +1 |≤C|ξ-x n | р (или в других обозначениях |ε n+1 |≤C|ε n | p).

Метод дихотомии имеет свое название от древнегреческого слова, что в переводе означает деление надвое. Именно поэтому данные метод имеет еще второе название: метод половинного деления. Его мы используем довольно часто. Допустим, играя в игру "Угадай число", где один игрок загадывает число от 1 до 100, а другой пытается его отгадать, руководствуясь подсказками "больше" или "меньше". Логично предположить, что первым числом будет названо 50, а вторым в случае если оно меньше - 25, если больше - 75. Таким образом, на каждом этапе (иттерации) неопределенность неизвестного уменьшается в 2 раза. Т.е. даже самый невезучий в мире человек отгадает загаданное число в данном диапазоне за 7 предположений вместо 100 случайных утверждений.

Метод половинного деления в решении уравнения

Правильное решение уравнения методом половинного деления возможно лишь в том случае, если известно, что на заданном интервале имеется корень и он является единственным. Это совсем не означает что метод дихотомии может использоваться только для решения линейных уравнений. Для нахождения корней уравнений более высокого порядка методом половинного деления необходимо сначала отделить корни по отрезкам. Процесс отделения корней осуществляется путем отыскания первой и второй производной от функции и приравнивании их нулю f"(x)=0 и f""(x)=0. Далее определяются знаки f(x) в критических и граничных точках. Интервал, где функция меняет знак |a,b|, где f(a)*f(b)< 0.

Алгоритм метода дихотомии

Алгоритм метода дихотомии очень прост. Рассмотрим отрезок |a,b| в пределах которого имеется один корень x 1

На первой этапе вычисляется x 0 =(a+b)/2

Далее определеяется значение функции в этой точке: если f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.

Вычисления прекращаются, когда разность b-a меньше требуемой погрешности.

В качестве примера использования метода половинного деления найдем корень на интервале уравнения x 3 -3*x+1=0 с точностью в 10 -3

Как видно из таблицы корнем является 0,347. Колличество иттераций равно 10. Условие завершения: a-b=0,0009< 10 -3

Метод половинного деления или метод дихотомии является наиболее простым для решения уравнения в численных методах.

Скачать:

Решение уравнения методом дихотомии - Решение уравнения методом половинного деления в Паскале.

Министерство общего и профессионального образования

Стерлитамакский Государственный Педагогический Институт

кафедра информатики и вычислительной техники

КУРСОВАЯ РАБОТА

«Метод половинного деления в школьном курсе информатики»

Работу выполнили студенты 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 описывается формулами

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

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

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

Следуя нашей задаче, нам требуется найти такое значение угла наклона α, чтобы снаряд, пролетев заданное расстояние 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 , то через десять шагов мы получим отрезок длиной