Лекция 2
2016/2017 уч. г.
Тема 3. Методы уточнения корней нелинейных уравнений
(Лк –2 ч., ПЗ – 4 ч., СРС – 8 ч.).
1. Постановка задачи уточнения корней. Метод половинного деления и алгоритм реализации метода.
2. Метод итерации уточнения корня, условие сходимости итерационного процесса.
3. Метод Ньютона, геометрическая интерпретация метода.
4. Общие замечания по применению методов уточнения корней уравнений.
Литература.
1. Данилина Н.И. и др. Вычислительная математика: Учеб. пособие для техникумов. – М.: Высш. шк., 1985, с. 174-207.
2. Демидович Б.П. Основы вычислительной математики: Учеб. пособие для высш. техн. учеб. заведений. М.: ФИЗМАТЛИТ, 1960, с. 118-148.
3. Турчак Л.И., Плотников П.В. Основы численных методов: Учеб. пособие. – М.: ФИЗМАТЛИТ, 2005, с. 145-154.
Постановка задачи уточнения корней. Метод половинного деления и алгоритм его реализации.
Постановка задачи уточнения корней
Пусть найден отрезок [ a, b ], в котором существует один и только один корень уравнения f (x) = 0. Тогда любую точку этого отрезка можно принять за приближенное значение корня. Погрешность такого приближенного значения корня не превосходит длины отрезка [ a, b ]. Следовательно, задача отыскания корня уравнения f (x) = 0 с заданной точностью ε сводится к нахождению такого отрезка [ a, b ], который содержит только один корень и длина этого отрезка не превосходит ε, т. е. 
. Такую задачу обычно называют задачей уточнения корня уравнения f (x) = 0.
Наиболее часто для решения задачи уточнения корня применяют метод половинного деления, метод касательных (метод Ньютона) и метод итераций. Общим для всех методов уточнения корня является процесс, в котором производится последовательное, шаг за шагом, уточнение первоначально взятого грубого, приближенного значения искомого корня. Каждый шаг такого процесса называется итерацией. Поэтому все методы уточнения корня уравнения называются итерационными.
Метод половинного деления и алгоритм его реализации
Идея метода заключается в сужении исходного интервала [ a, b ] до величины ε путем последовательного деления его и получающихся частей, содержащих искомый корень, пополам. Один из возможных вариантов уточнения корня методом половинного деления выполняется следующим образом (рис. 1, а).
 |
1. Задается нулевое приближение для искомого корня, равное значению a нижней границы исходного интервала, и вычисляется значение y 1 функции f (x) в этой точке (блок 4).
2. Делится интервал [ a, b ] существования корня пополам 
и вычисляется значение y 2 функции f (x) в этой точке 
(блок 5).
3. Возможен случай, когда значение y 2 функции f (x) в точке c деления интервала [ a, b ] пополам принимает нулевое значение (рис. 1, б), т. е. 
. Тогда корень уравнения найден, задача решена. Для выявления этого случая в схеме алгоритма предусмотрена проверка условия 
(блок 6, рис. 1, а).
4. Возможна ситуация, когда на предыдущем шаге уточнения корня был получен интервал [ a, b ] длиной меньше ε, т. е. (рис. 1, д). Тогда за значение корня, вычисленного с точностью ε, можно принять любую точку отрезка [ a, b ] (желательно его середину) и прекратить процесс уточнения корня. Выявление такой ситуации осуществляется проверкой условия (блок 7).
5. Если ни одно из условий 
и не выполняется, процесс уточнения корня должен быть продолжен. Для этого необходимо установить, в каком из полученных после деления интервала [ a, b ] отрезков [ a, c ] или [ c, b ] содержится искомый корень (рис.1, в, г). Согласно теореме о существовании корня, это выявляется путем проверки условия 
(блок 8, рис. 1, а).
6. Вычисляются границы суженного интервала существования корня, полученного после деления исходного интервала пополам. Если условие 
не выполняется (рис. 1, г), то искомый корень находится на отрезке [ c, b ]. Поэтому за значение a нижней границы нового, более узкого интервала [ a, b ] принимается значение c (блок 9), а за значение 
функции f (x) в этой границе значение 
, вычисленное на предыдущей итерации.
7. Если условие выполняется (рис. 1, в), то искомый корень принадлежит отрезку [ a, c ]. Следовательно, для выполнения следующего шага процесса уточнения корня необходим в качестве значения b верхней границы нового интервала [ a, b ] принять значение c (блок 10).
8. Осуществляется переход к повторному выполнению процесса уточнения корня, начиная с п.2 (блок 5).