Материал: Методичка

2.1. Локализация корней

Локализация корней – это процедура нахождения в области определения функции таких отрезков, на которых уравнение (2.1) имеет только один корень (одно решение). Для локализации корней уравнения (2.1) необходимо иметь критерий, позволяющий убедиться, что, во-первых, на некотором рассматриваемом отрезке числовой оси имеется корень, а, во-вторых, что этот корень единственный на указанном отрезке. Если функция непрерывна на отрезке , а на концах отрезка её значения имеют разные знаки (не равны нулю), то есть , то на этом отрезке расположен по крайней мере один корень (нечетное число корней). Если , то на отрезке либо нет корней, либо их четное число, данный случай рассматриваться не будет.

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

Рис. 2.1. Локализация корней. Функция не монотонна на отрезке .

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

Число называется корнем кратности уравнения (2.1), если при вместе с функцией равны нулю ее производные до порядка : . Корень кратности один называется простым.

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

1. Вычисление первой производной функции .

2. Выявление на области определения функции интервалов монотонности, определяемых точками, в которых или не существует.

3. Выбор среди интервалов монотонности тех, на концах которых значения функции имеют разные знаки, , где и – границы интервалов.

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

Рис. 2.2. Графическая локализация корней уравнения .

Из графиков, представленных на рис. 2.2, видно, что уравнение содержит один корень , расположенный в интервале .

Локализация корней может быть также выполнена табличным способом. Допустим, что корни уравнения (2.1) находятся на отрезке оси . Выбор данного отрезка (интервала поиска корней) может быть сделан, например, на основе анализа конкретной задачи. Будем вычислять значения , начиная с точки , двигаясь вправо с некоторым шагом (рис. 2.3). Получим набор значений функции , . При обнаружении пары соседних значений и , имеющих разные знаки ( ), соответствующие значения аргумента можно считать границами отрезка, содержащего корень.

Рис. 2.3. Табличный подход к локализации корней.

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

Рис 2.4. Наличие нескольких корней при несоблюдении условия монотонности функции: а) ; б) .

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

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

2.2. Уточнение корней

На данном этапе задача состоит в получении приближенного значения корня, принадлежащего отрезку его локализации , с заданной точностью . Это означает, что вычисленное значение корня должно отличаться от точного не более чем на величину : .

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

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

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

, (*)

где и – некоторые числа, конкретные значения которых определяются особенностями используемого метода уточнения корня.

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

2.2.1. Метод половинного деления (бисекции, дихотомии)

Пусть корни уравнения (2.1) локализованы и на некотором отрезке имеется корень, который необходимо уточнить с погрешностью . В качестве его начального приближения примем середину отрезка : (рис. 2.5).

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

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

В результате получим следующую последовательность вложенных отрезков: . Таким образом, очередное приближение с номером при условии вычисляется по формуле

.

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

, (2.2)

откуда . Последовательности и монотонны и ограничены, поэтому существуют пределы и предел разности равен разности пределов . Поэтому , где – корень уравнения.