Численные методы для решения нелинейных уравнений
(2
)
или
,
где
– квадратная
матрица Якоби,
составленная
из частных
производных
первого порядка
функций, а именно
,
вычисленных
точке
.
Для
дальнейшего
нам потребуется
еще одна форма
записи системы
нелинейных
уравнений в
,
а именно:
(3)
или
,
где
.
Операции, с помощью которых осуществляется преобразование системы (2) к системе (3), могут быть любыми, необходимо только, чтобы искомое решение системы (3) удовлетворяло системе (2).
Функции
удовлетворяют
тем же условиям,
что и функции
.
3. Отделение решений
Задача отделения решений систем нелинейных уравнений состоит в определении достаточно малой окрестности (шара малого радиуса, центром которого является решение) около какого-нибудь одного решения и в выборе в этой окрестности начального приближения к решению. Начальное приближение должно попасть при этом в область сходимости метода.
Задача отделения решений не имеет достаточно эффективных методов общего характера. При решении уравнения предполагается знание начальных приближений к изолированному решению из постановки конкретной задачи. Если же таких данных нет, то можно дать лишь некоторые рекомендации для конкретных видов уравнений.
Так,
если дано скалярное
уравнение
,
то его решение
с геометрической
точки зрения
можно рассматривать
как абсциссы
точек пересечения
графика функции
с осью абсцисс.
Построив график
функции y=f
(x), приближенно
определяем
окрестности
изолированных
точек пересечения
графика с
горизонтальной
осью. Сами точки
пересечения
берем за начальные
приближения
к точным решениям.
Безусловно, графические построения имеют большие погрешности, и выбранные начальные приближения могут не попасть в область сходимости применяемого метода.
Тогда нужно провести пробные решения на ЭВМ выбранным методом с исследованием сходимости.
Если приближения сходятся, то начальные приближения выбраны в области сходимости метода и можно получить приближенное решение с заданной точностью.
Если приближения расходятся, следует провести более точные графические построения и выбрать начальное приближение в области сходимости.
Аналогично отделяются решения для системы двух нелинейных уравнений
,
.
В этом
случае на плоскости
x,y строятся
линии уровня
функции двух
переменных
и
.
Координаты
точек пересечения
графиков этих
функций дают
начальные
приближения
изолированных
решений.
4. Методы решения нелинейных уравнений
4.1 Метод простой итерации
Метод простой итерации (см. [1]) применяется для решения систем нелинейных уравнений с любым числом уравнений. Его можно применять как для уточнения найденного решения, так и для первоначального нахождения решения. В последнем случае, однако, метод может не дать результата.
Для применения метода простой итерации система уравнений (2) приводится к виду (3).
Затем,
взяв начальное
приближение
,
которое предполагается
либо известным,
либо произвольным,
строим последовательность
(4)
по следующим формулам
(5)
Замечание. Для приведения системы уравнений (2) к виду (3) можно использовать прием:

где
– релаксационный
параметр,
определяется
методом Зейделя.
4.2 Метод Зейделя
Метод Зейделя отличается от метода простой итерации тем, что вычисления ведутся по формулам:
(6)
Иными
словами, при
вычислении
используются
не
,
как в методе
простой итерации,
а
.
4.3 Метод Ньютона
Этот метод (см.[1], [4]) предложен И.Ньютоном в 1669 году, однако наиболее полное обоснование было сделано советским математиком Л.В.Канторовичем в 1949 году (см.[4]), поэтому в литературе этот метод часто называют методом Ньютона-Канторовича.
Метод Ньютона является одним из итерационных методов, получаемых линеаризацией линейного оператора
,
где
из уравнения
(2).
Так,
для к-го приближения
к точному решению
уравнения (2)
ставится в
соответствие
линеаризованное
уравнение вида
(2
),
а именно:

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

Трудности
построения
алгоритма
метода Ньютона,
связанные с
обращением
производной
(построение
),
обычно преодолеваются
тем, что вместо
методов обращения
матрицы
решают
алгебраическую
систему уравнений
(7) относительно
неизвестных
.
Алгоритмы
решения системы
линейных
алгебраических
уравнений
хорошо отработаны,
для них имеются
стандартные
программы для
ЭВМ и, кроме
того, в результате
решения системы
одновременно
с обращением
матрицы получается
умножение
обратной матрицы
на вектор
.
Итерационная формула метода Ньютона при таком подходе будет иметь вид:
(7)
. (8)
4.4 Модифицированный метод Ньютона
Эта разновидность метода Ньютона строится путем определения производной только в одной точке приближенного решения, т. е. Последовательные приближения (4) строятся по формулам:
,
(9)
где
– начальное
приближение
к точному решению
.
4.5 Метод Зейделя на основе линеаризованного уравнения
Итерационная формула для построения приближенного решения нелинейного уравнения (2) на основе линеаризованного уравнения (7) имеет вид:

4.6 Метод наискорейшего спуска
Методы
спуска (см. [2])
сводят решение
системы (2) к
задаче нахождения
минимума специально
построенного
функционала
(функционал
– отображение
в R), а именно:
,
где
.
Функционал
в конечном
пространстве
Rn
можно рассматривать
как функцию
многих переменных
.
Для
нахождения
точки
,
в которой функционал
f принимает
минимальное
нулевое значение,
выбирают точку
,
находят
и строят итерационную
формулу:
с начальным
приближением
.
В
итерационной
формуле параметр
hk
пока не определен,
выберем его
таким образом,
чтобы выполнилось
условие:
,
начиная с x0,
в предположении,
что f –
монотонный
функционал.
Для
выбора hk
построим функционал,
зависящий от
параметра,
который изменяется
непрерывно:
.
При h=0 имеем, что f (0) – линия уровня функционала, проходящая через точку xk . Для нахождения следующей линии уровня, более близкой к минимуму, будем выбирать h таким образом, чтобы для данного xk
![]()
Это условие минимума по h будем рассматривать как уравнение для получения hk.
Решим
его приближенно,
т.к. ошибка в
несколько
процентов
обычно не влияет
на скорость
сходимости.
Отметим кстати,
что число hk
всегда должно
быть положительным.
Для этого разложим
функцию
в ряд Тейлора
по h в точке
h=0 и возьмем
только линейную
часть этого
разложения
.
Подстановка
линейной части
в условие
,
дает уравнение
для приближенного
определения
.
Решая построенное уравнение относительно h, получим:
или
.
Таким образом, итерационная формула метода наискорейшего спуска имеет вид:
или
,
где производные
вычислены в
точке
.
Метод наискорейшего спуска требует большего количества вычислений, чем другие методы первого порядка. Однако он обладает по сравнению с другими методами важным преимуществом, заключающемся в неизбежной сходимости процесса. При этом нужно помнить, что метод наискорейшего спуска может привести не к решению системы уравнений (2), а к значениям аргумента, дающим относительный экстремум функции
,
т.е.
.
5. Сходимость методов решения нелинейных уравнений
Если
метод сходится,
то есть
,
где
– точное
решение
– k-тое
приближение
к точному решению,
то итерационный
процесс следовало
бы закончить
по достижению
заданной погрешности
,
где e –
заданная точность
(погрешность).
Однако
практически
это условие
выполнить
нельзя, так как
неизвестно,
тогда для окончания
итерационного
процесса можно
воспользоваться
неравенствами
,
или
,
где
и
– заданные
величины.
При
таком окончании
итераций погрешность
может возрасти
по сравнению
с
и, поэтому, чтобы
не увеличивалась,
величины
и
соответственно
уменьшают или
увеличивают
число итераций.
Методы
простой итерации,
Зейделя, модифицированный
метод Ньютона,
метод наискорейшего
спуска (см. [1],
[2], [3], [4]) являются
методами первого
порядка – это
значит, что
имеет место
неравенство
,
k=1, 2, . . . , где
– константа,
своя у каждого
метода, зависящая
от выбора начального
приближения
,
функции fi
, i = 1, 2, . . . ,
n, и их частных
производных
первого и второго
порядков –
точнее их оценок
в некоторой
окрестности
искомого решения,
которой принадлежит
начальное
приближение.
Метод
Ньютона является
методом второго
порядка, то
есть для него
имеет место
неравенство
,
k=1, 2, . . . , где
– константа,
зависящая от
тех же величин,
что и константа
.
А теперь рассмотрим достаточные условия сходимости метода простой итерации и метода Ньютона.
Сходимость
процесса простой
итерации зависит
от двух условий.
Первое условие
состоит в том,
что какая-нибудь
точка
должна оказаться
близкой к исходному
решению
.
Степень необходимой
близости зависит
от функций j1,
j2,
. . . , jn
. Это требование
не относится
к системам
линейных уравнений,
для которых
сходимость
процесса простой
итерации зависит
только от второго
условия.
Второе условие связано с матрицей, составленной из частных производных первого порядка функций j1, j2, . . . , jn – матрицей Якоби
,
вычисленных
в точке
.
В случае,
когда рассматривается
система линейных
алгебраических
уравнений,
матрица M
состоит из
постоянных
чисел – коэффициентов,
стоящих при
неизвестных
в правой части
уравнения (3).
В случае нелинейных
уравнений
элементы
матрицы M
зависят, вообще
говоря, от
.
Для сходимости
процесса простой
итерации достаточно,
чтобы выполнялось
неравенство:
для
из некоторой
окрестности
точного решения
,
которой должно
принадлежать
начальное
приближение
.
Приведем
также достаточные
условия сходимости
метода Ньютона
для системы
уравнений вида
(2) по норме
.
Предположим,
что имеется
начальное
приближение