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

Решение нелинейных уравнений

Методы решения нелинейных уравнений – редкий пример задачи, которая ([3], стр. 85): может быть сравнительно полно исследована элементарными средствами; допускает наглядное геометрическое истолкование; проблемы, возникающие при отыскании корней нелинейных уравнений – типичны; некоторые методы их решения (например – простой итерации и метод Ньютона) допускают широкие обобщения и играют в вычислительной математике фундаментальную роль.

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

Пусть задано уравнение:

. (4.1)

Корнем уравнения (или решением) уравнения (4.1) называется значение , при котором .

Корень уравнения (4.1) называется простым, если , в противном случае, т.е. когда, , корень уравнения (4.1) называется кратным. Натуральное число m называется кратностью корня , если ([3], стр. 85). Иногда простой корень называют корнем кратности 1.

С геометрической точки зрения, корень уравнения (4.1) соответствует точке пересечения графика функции с осью ОХ. Причем, если корень - простой, то график функции пересекает ось абсцисс под ненулевым углом, а если - кратный корень, то – под нулевым углом.

Наиболее часто встречающимися и соответственно разработанными (на данном этапе) являются методы отыскания простых корней.

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

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

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

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

Решение задачи отыскания корней нелинейного уравнения (4.1) осуществляют в два этапа ([3], стр. 87):

1 этап – локализация (отделение) корней;

2 этап – итерационное уточнение корней.

Рассмотрим более подробно каждый из данных этапов.

Отрезком локализации корня уравнения (4.1) называется отрезок [a, b], содержащий только один корень данного уравнения ([3], стр. 88).

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

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

Наиболее простыми способами выяснения вопроса о существовании корней являются: графический и табличный.

Графический способ: исходное уравнение (4.1) представляют в эквивалентном виде (4.2):

, (4.2)

затем строят графики функций и , находят точки пересечения этих графиков. Абсциссы точек пересечения – корни соответствующего уравнения.

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

Теорема 4.1 ([7], стр. 247) Если функция непрерывна на отрезке [ a, b ] и принимает на концах отрезка значения разных знаков, т.е. , то найдется точка , такая что .

Однако табличный метод имеет существенные недостатки:

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

2) даже с помощью очень подробной таблицы не удастся выявить корни четной кратности, так как в окрестности таких корней функция имеет постоянный знак ([3], стр. 88);

3) он не обеспечивает локализацию (единственность) корней.

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

Теорема 4.2 ([6], стр. 16) Если функция непрерывна на [ a, b ] и дифференцируема на (a, b), принимает на концах отрезка значения разных знаков (), или , то найдется единственная точка , такая что .

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

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

(4.3)

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

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

В настоящее время известно достаточно много различных алгоритмов построения соответствующих последовательностей приближений, среди которых выделяются ([3], стр. 90):

· одношаговые – когда для построения очередного приближения используется только одно предыдущее значение ,

· к – шаговые – когда для построения приближения используются к предшествующих значений .

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

Сходимость последовательности к называется линейной (соответственно, итерационный процесс – линейно сходящимся), если найдутся постоянная и номер , такой что , и сверхлинейной, если существует такая положительная последовательность , что и ([5], стр. 201).

Последовательность сходится к по меньшей мере с р-м порядком (соответственно, итерационный процесс имеет по меньшей мере р-й порядок) если найдутся постоянные и , и номер , такой что ([5], стр. 201).

К линейной сходимости применяют также термин «сходимость со скоростью геометрической прогрессии» ([5], стр. 201). В [3], стр. 90 дается более строгое определение сходимости со скоростью геометрической прогрессии:

метод сходится со скоростью геометрической прогрессии, знаменатель которой , если для всех n справедлива оценка .

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

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

Если функция f (x) в уравнении (4.1) является непрерывной, то для точек из окрестности корня выполняется следующее свойство:

. (4.4)

Интервал называется интервалом неопределенности, а - радиус интервала неопределенности ([3], стр. 93).

Если - простой корень, то используя разложение по формуле Тейлора второго порядка (с остаточным членом в форме Пеано или Лагранжа), можно получить, что

,

,

,

,

откуда следует, что интервал неопределенности и радиус неопределенности определяются по формулам (4.5):

, ; (4.5)

абсолютное число обусловленности задачи отыскания простого корня уравнения (4.1) равно:

. (4.6)

Из формул (4.3) следует, что радиус интервала неопределенности пропорционален погрешности вычисления значения f и погрешность возрастает с уменьшением , т.е. с уменьшением модуля угла, при котором график функции пересекает ось абсцисс.

Если - корень кратности m, то, применяя формулу Тейлора уже порядка , получаем:

,

,

,

,

откуда следует, что интервал неопределенности и радиус неопределенности определяются по формулам (4.7):

, . (4.7)

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

Исследователи ([3], стр. 94) отмечают, что в реальных расчетах оценить значение и порядок радиуса интервала неопределенности достаточно сложно. Однако знать о его существовании необходимо, так как:

1) не имеет смысла ставить задачу о поиске решения с точностью ;

2) любое число из интервала неопределенности с одной и той же степенью достоверности можно принимать за приближенное решение уравнения (4.1);

3) нельзя требовать от алгоритмов отыскания корня получения достоверных результатов после того, как очередное приближение попало в интервал неопределенности или оказалось достаточно близко от него, поэтому рекомендуется расчеты прекращать и считать, что результат соответствует максимально возможному.

Поиск по сайту: