Отделение корней

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

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

Существует несколько основных методов уточнения корней уравнений.

1. Метод деления пополам (метод дихотомии, метод бисекций)

Это наиболее надежный алгоритм, особенно когда о поведении известно только, что - функция действительной переменной x и известен интервал , на котором меняет знак (рис.1.3). Следовательно, между и существует точка, в которой функция обращается в нуль. Если разделить интервал пополам и узнать, больше

Рис.1.1 – иллюстрация к отделению корней

нуля или меньше нуля функция в точке деления, то можем указать подынтервал, в котором функция меняет знак. Последующим делением указываемых подынтервалов можно сколь угодно близко подойти к корню: например, за 10 шагов интервал с корнем будет уменьшен в 1024 раза. При заданной абсолютной точности e алгоритм метода деления пополам состоит из следующих шагов (рис.1.4).

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

2. Если знаки и не совпадают, т.е. , и , то нужно заменить на и перейти к п.1.

3. Если же при , следует прекратить вычисления, т.к. достигнута заданная точность.

4. Если , и , то нужно заменить на и перейти к п.1; в противном случае - прекратить вычисления, так как достигнута заданная точность. Любой из концов отрезка , а лучше его середина, может быть использована в качестве корня уравнения .

Отметим основные достоинства метода деления пополам: 1) абсолютно надежен; 2) скорость сходимости не зависит от вида .

Рис.1.2 – алгоритм отделения корней

2. Метод хорд

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

Геометрически способ линейной интерполяции эквивалентен замене кривой хордой, проходящей через точки и

Рис.1.3а, б – иллюстрации к методу деления пополам

Уравнение хорды:

Полагая и получаем приближение к корню:

. (1)

Алгоритм метода хорд (рис.1.6):

1. Вычислить и

2. Вычислить по формуле (1) и

3. Если знаки и совпадают, т.е. то конец неподвижен. В этом случае приняты: если . Затем перейти к п.2. В противном случае, т.е. при вычисления завершены, т.к. заданная точность достигнута.

4. Если неподвижен конец . В случае : Затем перейти к п.2. Иначе – вычисления завершены. Значение используется как корень уравнения.

Достоинства метода хорд: 1) абсолютно надежен; 2) в большинстве случаев имеет более быструю сходимость, чем метод деления пополам.

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

Рис.1.4 – алгоритм метода деления пополам

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

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

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

.

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

Иллюстрация к методу касательных представлена на рис.1.7, а алгоритм метода – на рис.1.8.

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

Рис.1.5 – иллюстрация к методу хорд

4. Метод секущих

Данный метод заменяет производную первой разностью, найденной по двум последним итерациям. Итерационная формула метода имеет вид

В этом алгоритме начинают с двумя исходными числами и На каждом шаге получают как единственный нуль секущей прямой к функции проходящей через точки с абсциссами и (рис.1.9). Алгоритм метода секущих приведен на рис.1.10.

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

Рис.1.6 – алгоритм метода хорд

5. Метод итераций

Уравнение заменяют равносильным Выбирают каким-либо способом приближенное значение корня и по нему находят Повторяя процесс, получают последовательность чисел:

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

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

Поэтому в методе итераций при переходе от уравнения к уравнению следует выбирать такое представление , при котором что является условием сходимости метода. Чем меньше , тем быстрее последовательные приближения сходятся к корню . Иллюстрации к методу итераций даны на рис.1.11, алгоритм – на рис.1.12

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

5. Комбинированные методы решений нелинейных уравнений

Методы комбинируют для повышения эффективности: комбинированный метод должен обеспечить при той же величине ошибки меньшие затраты машинного времени по сравнению с любым из комбинируемых методов. Примеры алгоритмов комбинированных методов представлены на рис.1.13 и 1.14.