Глава 4. МЕТОДЫ ОТЫСКАНИЯ РЕШЕНИЙ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

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

§ 4.1. Постановка задачи. Основные этапы решения

1. Постановка задачи.

Задача отыскания корней нелинейного уравнения с одним неизвестным вида

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

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

Корень х уравнения (4.1) называется простым, если противном случае (т. е. в случае корень х называется кратным. Целое число назовем кратностью корня х, если для Геометрически корень х соответствует точке пересечения графика функции с осью Корень х является простым, если график пересекает ось под ненулевым углом, и кратным, если пересечение происходит под нулевым углом. Функция график который изображен на рис. 4.1, имеет четыре корня. Корни простые, кратные.

Рис. 4.1

Задача отыскания простых корней является существенно более простой (и чаще встречающейся), чем задача отыскания кратных корней. В действительности большинство методов решения уравнения (4.1) ориентировано именно на вычисление простых корней.

2. Уточнение постановки задачи.

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

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

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

уравнений пятой и более высоких степеней таких формул не существует. Этот замечательный факт, известный как теорема Абеля, был установлен в 30-е годы XIX в. Н. Абелем и Э. Галуа.

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

Пример 4.1. Предположим, что исследование некоторого явления привело к необходимости решить уравнение

Воспользовавшись формулами (3.2) для корней квадратного уравнения, получим значения Найдены ли нами точные значения параметра Очевидно, нет. Скорее всего коэффициенты уравнения (4.3) известны приближенно и в лучшем случае они представляют округленные значения "истинных" коэффициентов. В действительности можно лишь утверждать, что

Предположим теперь, что "истинный" вид уравнения (4.3) таков: Тогда точные значения параметра можно вычислить по формуле Однако она лишь указывает на то, какие операции и в каком порядке следует выполнить. В данном случае точное вычисление по формуле невозможно, так как она содержит операцию извлечения квадратного корня. Вычисленные по ней значения неизбежно окажутся приближенными.

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

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

3. Основные этапы решения.

Решение задачи отыскания корней нелинейного уравнения осуществляют в два этапа. Первый этап называется этапом локализации (или отделения) корней, второй — этапом итерационного уточнения корней.

Локализация корней. Отрезок содержащий только один корень х уравнения (4.1), называют отрезком локализации корня х. Цель этапа локализации считают достигнутой, если для каждого из подлежащих определению корней удалось указать отрезок локализации (его длину стараются по возможности сделать минимальной).

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

Способы локализации корней многообразны, и указать универсальный метод не представляется возможным. Иногда отрезок локализации известен либо он определяется из физических соображений. В простых ситуациях хороший результат может давать графический метод (см. пример 4.2). Широко применяют построение таблиц значений функций вида При этом способе локализации о наличии на отрезке корня судят по перемене знака функции на концах отрезка (см. пример 4.3). Основанием для применения указанного способа служит следующая хорошо известная теорема математического анализа.

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

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

Дело в том, что в малой окрестности такого корня (например, корня на рис. 4.1) функция имеет постоянный знак.

Важно подчеркнуть, что далеко не всегда для успешного отыскания

корня х уравнения (4.1) необходимо полное решение задачи локализации. Часто вместо отрезка локализации достаточно найти хорошее начальное приближение к корню х. Пример 4.2. Локализуем корни уравнения

Для этого преобразуем уравнение к виду и построим графики функций (рис. 4.2). Абсциссы точек пересечения этих графиков являются корнями данного уравнения. Из рис. 4.2 видно, что уравнение имеет два корня и расположенные на отрезках и [0, 1]. Убедимся, что функция принимает на концах указанных отрезков значения разных знаков. Действительно, Следовательно, в силу теоремы 4.1 на каждом из отрезков и [0, 1] находится по крайней мере один корень.

Рис. 4.2

Пример 4.3. Локализуем корни уравнения

Для этого составим таблицу значений функции на отрезке с шагом 0.4.

Таблица 4.1 (см. скан)

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

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

Общее представление об итерационных методах и основные определения были даны в § 3.3. Введем дополнительно некоторые определения.

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

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

Как нетрудно видеть, из оценки (4.5) действительно вытекает сходимость метода.

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

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

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

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

Заметим, что принадлежность окрестности является следствием неравенства (4.7). В самом деле, так как то Сходимость также вытекает из (4.7).

Справедливость неравенства (4.7) установим методом индукции. При оно переходит в очевидное: Пусть неравенство (4.7) выполнено при Тогда

т. е. неравенство выполнено и при

Лемма 4.2. Пусть -шаговый итерационный метод в некоторой -окрестности корня х имеет порядок сходимости. Выберем так, чтобы выполнялись неравенства где С — постоянная из неравенства (4.6). Тогда при любом выборе начального приближения из -окрестности корня х итерационная последовательность выходит за пределы этой окрестности, метод сходится и справедлива оценка

где

Заметим, что принадлежность окрестности является следствием неравенства (4.8). В самом деле, так как то из (4.8) вытекает, что Сходимость также следует из (4.8).

Справедливость неравенства (4.8) установим методом индукции. При оно переходит в очевидное: Пусть неравенство (4.8) выполнено при Докажем, что оно верно и при Используя условие (4.6), получаем

С помощью доказанных лемм исследование сходимости итерационных методов сводится только к получению оценки (4.6).