1.3 Метод половинного деления (метод дихотомии)
Метод половинного деления основан на последовательном делении отрезка локализации корня пополам.
Для этого выбирается начальное приближение к отрезку [a, b], такое, что f(a)×f(b)<0, затем определяется знак функции в точке 
— середине отрезка [a, b]. Если он противоположен знаку функции в точке a, то корень локализован на отрезке [a, c], если же нет – то на отрезке [c, b]. Схема метода дихотомии приведен на рисунке 2.
Рисунок 2. Последовательное деление отрезка пополам и приближение к корню 
Алгоритм метода дихотомии можно записать так:
1. представить решаемое уравнение в виде 
2. выбрать a, b и вычислить 
3. если f(a)×f(с)<0, то a=a; b = c иначе a = c; b=b
4. если критерий сходимости не выполнен, то перейти к п. 2
Пример решения уравнения методом дихотомии
Найти решение заданного уравнения методом дихотомии с точностью до 10 -5 .
Пример создания расчетной схемы на основе метода дихотомии на примере уравнения: 
на отрезке [1, 2]
Данный метод заключается в проверке на каждой итерации условия:
если f(a)×f(с)<0
и выбор соответствующего отрезка для следующей итерации.
Рисунок 3. Последовательность итераций метода дихотомии при поиске корня уравнения 
на отрезке [1, 2]
a) схема расчета (зависимые ячейки); b) режим отображения формул;
Для нашего примера итерационная последовательность для нахождения решения принимает вид:
Точность до пятой значащей цифры достигается за 20 итераций.
Скорость сходимости этого метода является линейной.
При выполнении начального условия он сходится к решению всегда.
Метод половинного деления удобен при решении физически реальных уравнений, когда заранее известен отрезок локализации решения уравнения.
2 Решение уравнений, используя “Подбор параметра”
Используя возможности Excel можно находить корни нелинейного уравнения вида f(x)=0 в допустимой области определения переменной. Последовательность операций нахождения корней следующая:
Производится табулирование функции в диапазоне вероятного существования корней;
По таблице фиксируются ближайшие приближения к значениям корней;
Используя средство Excel Подбор параметра, вычисляются корни уравнения с заданной точностью.
При подборе параметра Excel использует итерационный (циклический) процесс. Количество итераций и точность устанавливаются в меню Сервис/Параметры/вкладка Вычисления. Если Excel выполняет сложную задачу подбора параметра, можно нажать кнопку Пауза в окне диалога Результат подбора параметра и прервать вычисление, а затем нажать кнопку Шаг, чтобы выполнить очередную итерацию и просмотреть результат. При решении задачи в пошаговом режиме появляется кнопка Продолжить — для возврата в обычный режим подбора параметра.
2.1 Пример решения уравнения, используя “Подбор параметра”
Например, найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3].
Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3; 3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня.
Рисунок 4. Поиск приближенных значений корней уравнения
Выполните команду меню Сервис/Параметры, во вкладке Вычисления установите относительную погрешность вычислений E=0,00001, а число итераций N=1000, установите флажок Итерации.
Выполните команду меню Сервис/Подбор параметра. В диалоговом окне (рисунок 9) заполните следующие поля:
Установить в ячейке: в поле указывается адрес ячейки, в которой записана формула правой части функции;
Значение: в поле указывается значение, которое должен получить полином в результате вычислений, т.е. правая часть уравнения (в нашем случае 0);
Изменяя значение: в поле указывается адрес ячейки (где записано начальное приближение), в которой будет вычисляться корень уравнения и на которую ссылается формула.
Рисунок 5. Диалоговое окно Подбор параметра для поиска первого корня
После щелчка на ОКполучим значение первого корня-1,65793685.
Выполняя последовательно операции аналогичные предыдущим, вычислим значения остальных корней: -0,35913476 и 2,05170101.
Метод половинного деления. Алгоритм
Решение алгебраического уравнения. Для численного решения алгебраических уравнений существует множество способов. Среди самых известных можно назвать метод Ньютона, метод Хорд, и «всепобеждающий» метод Половинного Деления. Сразу оговоримся, что любой метод является приближенным, и по сути дела лишь уточняющим значение корня. Однако уточняющим до любой точности, заданной Нами.
Метод половинного деления или дихотомии (дихотомия — сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f(x)=0 состоит в делении пополам отрезка [a; b], где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка [a; b] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [a; b] становится меньше заданной погрешности нахождения корня ?, либо функция попадает в полосу шума ?1 — значение функции сравнимо с погрешностью расчетов.
Сначала поставим задачу. Дана монотонная, непрерывная функция f(x), которая содержит корень на отрезке [a,b], где b>a. Определить корень с точностью ?, если известно, что f(a)*f(b)<0
Дано уравнение вида:
необходимо найти удовлетворяющие ему значения x.
Итак, приступим к решению. Первым делом, определимся, что значит f(x)=0. Посмотрите на рис.1. На нем изображен график некоей функции. В некоторых точках этот график пересекает ось абсцисс. Координаты x этих точек нам и нужно найти. Если вид уравнения простой или стандартный, например, квадратное уравнение или линейное, то применять численный метод здесь совершенно ни к чему. Но если уравнение у нас такое:
то ни в каком учебнике вы не найдете метода аналитического решения этого кошмара. Здесь и приходит на помощь непобедимый численный метод. Метод половинного деления. Из самого названия метода можно предположить, что нам понадобится что-то делить пополам.
Ученикам метод половинного деления можно преподнести в виде решения задачи.
Задача
Идет осада неприятельской крепости. На некотором расстоянии от нее установили новую пушку. Под каким углом к горизонту надо стрелять из этой пушки, чтобы попасть в заданный участок крепостной стены.
Над моделью этой задачи физики изрядно поработали. Оно и понятно: ведь многие научные задачи, как и эта, возникали прежде всего в военном деле. И решение этих задач почти всегда считалось приоритетным.
Какие же факторы принять за существенные в этой задаче? Поскольку речь идет о средневековье, то скорость снаряда и дальность полета невелики. Значит можно считать несущественным, что Земля круглая (помните обсуждение в параграфе 27), и пренебречь сопротивлением воздуха. Остается единственный фактор — сила земного притяжения.
Математик тут бы сказал, что надо решить уравнение. Мы тоже будем решать, только приближенно и очень похоже на то, как делают настоящие артиллеристы. Они же поступают следующим образом: производят несколько выстрелов, беря цель «в вилку», т.е. одно попадание выше цели, а другое ниже. Затем делят пополам угол между этими выстрелами, и при стрельбе под таким углом снаряд ложится к цели намного ближе. Но если все же не попали, то новую «вилку» снова делят пополам и т.д.
Мы заранее можем указать «вилку» для угла: 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. Его можно было бы назвать методом артиллерийской пристрелки. Но математики называют его методом половинного деления.
Далее ученикам предлагается записать алгоритм и блок-схему нахождения корня уравнения с помощью метода половинного деления.
Алгоритм
1) Найдем середину отрезка [a; b]: c=(a+b)/2;
2) Вычислим значения функции в точках a и c и найдем произведение полученных значений: d=f(c)?f(a);
3) Если d>0, то теперь точкой a станет c: a=c; Если d<0, то точкой b станет c: b=c;
4) Вычислим разность a и b, сравним ее с точностью ?: если |a-b|> ?, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;
Определить корни уравнения x2 -3.2×2 -2.5x -5.4=0 аналетически и уточните их метдом половинного деления с точностью до 0.01
Численные методы решения нелинейных уравнений
где f(x) — заданная алгебраическая или трансцендентная функция.
Решить уравнение — значит найти все его корни, то есть те значения x , которые обращают уравнение в тождество.
Если уравнение достаточно сложно, то задача точного определения корней является в некоторых случаях нерешаемой. Поэтому ставится задача найти такое приближенное значение корня xПP , которое отличается от точного значения корня x* на величину, по модулю не превышающую указанной точности (малой положительной величины) ε , то есть
Величину ε также называют допустимой ошибкой , которую можно задать по своему усмотрению.
Этапы приближенного решения нелинейных уравнений
Приближенное решение уравнения состоит из двух этапов:
- Отделение корней, то есть нахождение интервалов из области определения функции f(x) , в каждом из которых содержится только один корень уравнения f(x)=0 .
- Уточнение корней до заданной точности.
Отделение корней
Отделение корней можно проводить графически и аналитически.
Для того чтобы графически отделить корни уравнения, необходимо построить график функции f(x) . Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения.
Для примера рассмотрим задачу решения уравнения 
где угол x задан в градусах. Указанное уравнение можно переписать в виде 
Для графического отсечения корней достаточно построить график функции 
Из рисунка видно, что корень уравнения лежит в промежутке x∈(6;8) .
Аналитическое отделение корней
Аналитическое отделение корней основано на следующих теоремах.
Теорема 1 . Если непрерывная функция f(x) принимает на концах отрезка [a; b] значения разных знаков, т.е. 
то на этом отрезке содержится по крайней мере один корень уравнения.
Теорема 2 . Если непрерывная на отрезке [a; b] функция f(x) принимает на концах отрезка значения разных знаков, а производная f'(x) сохраняет знак внутри указанного отрезка, то внутри отрезка существует единственный корень уравнения f(x) = 0 .
Уточнение корней
Для уточнения корней может использоваться один из следующих методов:
Метод последовательных приближений (метод итераций)
Метод итерации — численный метод решения математических задач, используемый для приближённого решения алгебраических уравнений и систем. Суть метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным). Метод позволяет получить решение с заданной точностью в виде предела последовательности итераций. Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения решения.
Функциональное уравнение может быть записано в виде 
Функцию f(x) называют сжимающим отображением .
Последовательность чисел x0, x1 ,…, xn называется итерационной , если для любого номера n>0 элемент xn выражается через элемент xn-1 по рекуррентной формуле 
а в качестве x0 взято любое число из области задания функции f(x) .
Реализация на C++ для рассмотренного выше примера
Уравнение может быть записано в форме 
Результат выполнения 
Метод Ньютона (метод касательных)
Если известно начальное приближение x0 корня уравнения f(x)=0, то последовательные приближения находят по формуле 
Графическая интерпретация метода касательных имеет вид 
Реализация на C++
Для заданного уравнения 
производная будет иметь вид 
Результат выполнения 
Метод секущих (метод хорд)
Если x0 , x1 — приближенные значения корня уравнения f(x) = 0 и выполняется условие
то последующие приближения находят по формуле 
Методом хорд называют также метод, при котором один из концов отрезка закреплен, т.е. вычисление приближения корня уравнения f(x) = 0 производят по формулам: 
Геометрическая интерпретация метода хорд: 
Реализация на C++
В отличие от двух рассмотренных выше методов, метод хорд предполагает наличие двух начальных приближений, представляющих собой концы отрезка, внутри которого располагается искомый корень.
Результат выполнения 
Метод половинного деления (метод дихотомии)
Если x0 , x1 — приближенные значения корня уравнения f(x) = 0 и выполняется условие 
то последующие приближения находятся по формуле 
и вычисляется f(xi) . Если f(xi)=0 , то корень найден. В противном случае из отрезков выбирается тот, на концах которого f(x) принимает значения разных знаков, и проделывается аналогичная операция. Процесс продолжается до получения требуемой точности.
Геометрическая интерпретация метода дихотомии 
Реализация на C++
Результат выполнения 
Для численного поиска решения также можно использовать генетические алгоритмы.
ПРИБЛИЖЕННОЕ РЕШЕНИЕ УРАВНЕНИЙ (метод половинного деления)
Урок проводятся в 11-м физико-математическом классе. Предлагаемый материал неизменно вызывает интерес у учащихся, так как особенностью учеников данного профиля является повышенный интерес к предметам физико-математического цикла. Содержание данного урока дает возможность учащимся заглянуть «вглубь» себя и еще раз задуматься о своей дальнейшей профессиональной судьбе.
Просмотр содержимого документа
«ПРИБЛИЖЕННОЕ РЕШЕНИЕ УРАВНЕНИЙ (метод половинного деления)»
Войнова Ирина Викторовна, учитель информатики муниципального общеобразовательного бюджетного учреждения «Лицей №1» г. Оренбурга
Решение нелинейных уравнений методом половинного деления
Планируемые образовательные результаты (ключевые компетеции)
Метапредметные
Умение составлять алгоритмы управления исполнителями и записывать их на выбранном алгоритмическом языке (языке программирования);
умение формально выполнять алгоритмы, описанные с использованием алгоритмических конструкций.
умение создавать и выполнять программы для решения алгоритмических задач в выбранной среде программирования;
умение использовать готовые прикладные компьютерные программы и сервисы в выбранной специализации, умение работать с описаниями программ и сервисами;
навыки выбора способа представления данных в зависимости от постановленной задачи.
умение самостоятельно определять цели своего обучения, ставить и формулировать для себя новые задачи в учёбе и познавательной деятельности, развивать мотивы и интересы своей познавательной деятельности;
владение основами самоконтроля, самооценки, принятия решений и осуществления осознанного выбора в учебной и познавательной деятельности;
умение определять понятия, создавать обобщения, устанавливать аналогии, классифицировать, самостоятельно выбирать основания и критерии для классификации, устанавливать причинно-следственные связи, строить логическое рассуждение, умозаключение и делать выводы;
умение создавать, применять и преобразовывать модели и схемы для решения учебных и познавательных задач;
формирование и развитие компетентности в области использования информационно-коммуникационных технологий.
формирование ответственного отношения к учению, готовности и способности обучающихся к саморазвитию и самообразованию на основе мотивации к обучению и познанию;
формирование целостного мировоззрения, соответствующего современному уровню развития науки и общественной практики;
развитие осознанного и ответственного отношения к собственным поступкам;
формирование коммуникативной компетентности в процессе образовательной, учебно-исследовательской, творческой и других видов деятельности.
Решаемые учебные проблемы
обучающая – научить учащихся решать нелинейные уравнения в среде электронных таблиц MS Excel и среде программирования Pascal;
развивающая – познакомить учащихся с применением компьютеров в качестве помощников при решении уравнений;
воспитательная – выработать у учащихся умение рационально использовать время и возможности компьютерных технологий при решении задач.
Основные понятия, изучаемые на уроке
Учащиеся знакомятся с понятием «Итерация»
Необходимое и достаточное условие существования корня на выбранном участке.
Алгоритм решения уравнений методом половинного деления.
Привлечение понятий и фактов из предметной области математика для расширения возможностей практического применения теории, изучаемой в данном предмете средствами ИКТ. Использование практических умений и навыков, полученных на уроках информатики, для получения новых экспериментальных данных.
Вид, используемых на уроке средств ИКТ
Компьютеры с OS MS Windows;
Программа Microsoft Excel;
Программа Turbo Pascal;
Презентация по теме, выполненная в программе Power Point.
Цель урока: использование компьютерных технологий в решении нелинейных уравнений и практическое применение соответствующих умений и навыков.
Тип урока: комбинированный – урок изучения нового материала и практическое закрепление полученных знаний, умений и навыков.
Вид урока: сдвоенный, продолжительность – 1,5 часа.
1 урок. В данном уроке особое внимание уделено визуальному представлению информации – в ходе урока с помощью проектора демонстрируются слайды, подготовленные в пакете презентационной графики Microsoft Power Point.
Организационный момент
Учитель объявляет тему и цели урока.
Актуализация знаний, умений и навыков учащихся
Учащиеся знакомятся с понятием «Итерация» указанным методом с помощью слайдов, подготовленных в пакете презентационной графики Microsoft Power Point.
Условия существования корня на отрезке [a:b]:
На концах отрезка [a; b] функция f(x) имеет разные знаки f(a) · f(b)
Производная f ‘(x) непрерывна и сохраняет знак на отрезке [a; b]:
Суть метода (записать условия существования корня, изобразить в тетради)
Практическая работа «Решение уравнений с использованием программы Microsoft Excel»
Практическое задание
Найти решение уравнения y=x 3 – cos(x) с точностью =0,001.
Постановка задачи.
Дано: f(x) – функция;
f ‘(x) – производная заданной функции;
— требуемая точность;
a, b – границы интервала поиска корня.
Найти: приближенный корень уравнения f(x)=0 на отрезке [-1,4; 1,4].
Метод решения.
Построить график функции в программе MS Excel и проверить единственность корня на заданном отрезке.
Учащиеся выполняют построение таблицы значений переменной x на отрезке [-1,4; 1,4] и заполняют в таблице строку со значениями переменной y для функции y=x 3 – cos(x).
По графику учащиеся определяют, что на выбранном отрезке корень существует и является единственным.
Составить расчетную таблицу для поиска решения уравнения на указанном отрезке:
f(a) значение функции в точке а
f(в) значение функции в точке в
с – координата середины отрезка [a; b]:
Проверить условия, при которых можно применять выбранный метод:
определить знаки функции f(x) на концах отрезка [a; b]: f(a) · f(b)
определить знаки производной f ‘(x) на концах отрезка [a; b]:
Составить таблицу значений для проверки существования корня на выбранном отрезке:
Составить расчетную таблицу:
Решение уравнения с использованием оператора цикла с предусловием (разбор задания с использованием презентации, запись программы по блок-схеме);
Решение уравнения с использованием оператора цикла с постусловием (разбор задания с использованием презентации, запись программы по блок-схеме);
Подведение итогов урока.
Учитель подчеркивает важную роль алгоритма при решении различных задач и предлагает учащимся сделать вывод, ответив на следующие вопросы:
Какая компьютерная технология оказалась более рациональной и почему при решении уравнения выбранным методом?
В какой технологии более наглядно представлен метод итерации при организации обработки данных?
Какое количество итераций оказалось необходимо выполнить, чтобы получить решение с точностью ε.
Каков результат вашей собственной деятельности и анализ приобретенного опыта решения поставленной задачи.
Домашнее задание.
Найти корни уравнений с точностью 0,000001
Cos(x)=x-1; (используя программу Pascal)
Sin(x)+0,5=x. (используя программу Microsoft Excel)
В качестве достигнутых результатов урока, можно подчеркнуть не только выполнение поставленных образовательной, воспитательной и развивающей задач, но и большую активизирующую и мотивационную функцию урока. Надеюсь, что данный урок побуждает учащихся к более осмысленному восприятию компьютерных и материальных объектов моделирования.
Реализация содержания урока связана с выбором элементов следующих технологий
Создание учебной ситуации через использование проблемных вопросов, целей- векторов урока (проблемное обучение)
Реализация исследовательского обучения
Использование информационных технологий в обучении
Компетентностный подход в обучении и воспитании
Выстраивание субъект — субъектных отношений (личностно — ориентированное обучение.
Приближенное рещение уравнений
Л
окализация корня — ______________________________________________________________________________________________________________________________________________________________________________
Итерация — это ______________________________________________________________ некоторой математической операции или действия при организации обработки данных, при котором используется _____________________________________________________ такой же операции или действия.
|xn– xn+1|. 
ε— ______________________________
N–_____________________________
xn–_____________________________
xn+1- _____________________________
И
нтервал изоляции корня — _______________________________________________________________________________________
Необходимое условие существования корня уравнения на отрезке [a,b]:_______________________
_____________________________________________________________________________
Д
остаточное условие единственностикорняна отрезке [a,b]:_________________________________________________________________________
Определить наличие корня уравнения y=x 3 – cos(x) на отрезке [-1,4; 1,4]
проверка условия существования корня на заданном отрезке
f(a)∙f(b)и f / (a)∙ f / (b)0
Решение уравнений методом половинного деления (Бисекции,дихотомии)
Итерационная формула метода бисекции:
Механизм метода бисекции, который больше известен под названием метода половинного деления, очень прост и заключается в том, что полученный при локализации отрезок на каждой итерации делится пополам. Из двух половинок выбирается та, на концах которой функция принимает значения противоположных знаков, т.е. f(a) · f(b)
То есть проверяется то же условие, что и при методе сканирования. Процесс заканчивается, когда длина полученного интервала становится меньше некоторого приближения Ɛ (в нашем случае Ɛ=0,001). Фактически этот метод исключает возможность появления ошибки. «Аварийная» ситуация может быть вызвана лишь тем, что граница полученного на итерации отрезка попадет в точку разрыва функции. Метод половинного деления наиболее универсальный среди всех итерационных методов. Но, как всегда, бочка меда не обходится без ложки дегтя – для бисекции характерна очень низкая скорость сходимости.
Решить уравнение x3-cosx=0, e=0,001
Определяем интервал изоляции корня
Необходимое и Достаточное условие единственности корня на отрезке [a,b], если f(a)∙f(b)
f / (a)∙f / (b)0