POS-KSC (Учебное пособие по численным методам), страница 3

Задача делится на 2 этапа:

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

2. Уточнение положения корня на интервале локализации.

Свойства функции на интервале локализации [a, b]:

1. непрерывна на [a, b]

2. монотонна на [a, b] , т.е. или , что обуславливает единственность корня

3. меняет знак на [a, b], , т.е. корень существует.

4. не имеет точек перегиба, т.е. или .

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

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

(3.1)

Для этого необходимо, чтобы процесс итераций сходился. Рассмотрим несколько итерационных процедур.

3.1. Метод простой итерации для решения нелинейных и трансцендентных уравнений

Уравнение преобразуется к виду

(3.1.1)

и, если выполняется условие

, (3.1.2)

то итерационный процесс:

(3.1.3)

сходится к точному значению. Действительно, , из теоремы о среднем следует оценка: , т.е., расстояние между точками последовательности уменьшается, если - ( = q – знаменатель сходимости). По теореме о неподвижной точке в этом случае существует предел - решение уравнения. Начальная точка - любая точка интервала локализации корня. Знаменатель сходимости зависит от вида . Уравнение может быть преобразовано к итерационному виду (3.1.1) множеством различных способов – модификаций одношагового стационарного метода простой итерации (см. также 3.3), выбором которых можно добиться минимума знаменателя сходимости.

Например, исходное уравнение эквивалентно следующему: . Достаточное условие сходимости (3.1.2) выполняется, если , где

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

На интервале заменим линейным интерполяционным полиномом, проходящем через точки и :

.

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

. (3.2.1)

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

Если не имеет точки перегиба на , то один из концов множества хорд неподвижен. Условие неподвижной точки:

(3.2.2)

Анализ позволяет определить неподвижную точку c и для нахождения использовать итерационную формулу:

, (3.2.3) причем .

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

(3.2.4)

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

3.3. Метод касательных

(Метод Ньютона)

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

Из точки проводится новая касательная и т. д., до достижения заданной точности (3.1).

Уравнение касательной в точке имеет вид:

, ,

отсюда следует итерационный процесс:

. (3.3.1)

Выражение для начальной точки совпадает с (3.2.2).

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

< (3.3.2)

Из 3.3.2 следует, что чем меньше область локализации корня, тем меньше знаменатель сходимости метода Ньютона и в пределе при . Таким образом, при достаточно малой области локализации корня сходимость метода Ньютона безусловная.

1. Скорость сходимости итерационных методов

Введем обозначения: , . Для оценки скорости сходимости необходимо определить зависимость между и .

Если в процессе итераций, начиная с некоторого , выполняется

, где , (3.4.1)

то скорость сходимости итерационного процесса определяется показателем . При скорость сходимости линейная, при – квадратичная, при – сверхлинейная. Если (3.4.1) устанавливается при , то скорость сходимости называется асимптотической.

В случае метода простых итераций:

или ,

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

(3.4.2)

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

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

(3.4.3)

Оценка (3.8) с учетом того, что расстояние между точками и меньше длины интервала изоляции дает:

, (3.4.4)

то есть скорость сходимости линейная.

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

.

Подставляя полученное из него выражение для в (3.4.3), получим для степеней r и t :

, и , , .

Таким образом, сходимость метода секущих сверхлинейная.

Для метода касательных, вычитая из левой и правой части (3.3.1) значение корня и разлагая функцию в ряд, получим:

Откуда:

, (3.4.4)

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

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

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

1. Условие выхода из вычислительного процесса по заданной точности в методах простой итерации

Формула (3.1) выхода из процесса итераций не всегда пригодна для практического использования. Она, например, не выполняется, если функция имеет корень в точке локального минимума. Кроме того, если алгоритм вычисления функции является плохо обусловленным (см. ), относительная ошибка результата вычисления функции возле её корня может значительно превосходить машинную константу , а также желаемую точность определения корня. В этом случае критерий (3.1) не обеспечивает остановку итерационного процесса при достижении заданной величины . Заметим при этом, что в тех методах, в которых выбор текущего интервала основан на вычислении знакопеременности функции на его концах (метод дихотомии, метод хорд и т.п.), применение другого критерия не уменьшает уже возникшую в такой ситуации ошибку, а приводит лишь к выходу из процесса вычислений.

Покажем практический способ выхода из процесса итераций гарантирующий достижение заданной точности вычислений в общем случае простой итерации со знаменателем . Считается, что корень на -ой итерации вычислен с точностью , если . Контролю же в процессе вычислений поддаётся величина . Установив связь между этими величинами, мы получим возможность проводить вычисления с заданной точностью. Заметим, что при . Далее, учитывая неравенство треугольника и (3.4.2)

При получаем

Таким образом, требование

(3.5.1)