Методы решения систем нелинейных уравнений
Постановка задачи
Дана система нелинейных уравнений с неизвестными:
где , — нелинейные функции, определенные и непрерывные в некоторой области , или в векторном виде (где )
Требуется найти такой вектор , который при подстановке в систему (3.22) превращает каждое уравнение в верное числовое равенство.
Замечания
1. Проблема решения системы (3.22) возникает при решении многих прикладных задач, например, поиска безусловного экстремума функций многих переменных с помощью необходимых условий, при применении неявных методов интегрирования обыкновенных дифференциальных уравнений и т.д.
2. Задача нахождения комплексных корней может быть сведена к проблеме решения двух уравнений с двумя неизвестными. Для этого следует положить и выделить действительную и мнимую части функции:
Отсюда получаем систему которая может быть решена одним из рассматриваемых в данном разделе методов:
3. Для всех рассматриваемых далее методов требуется находить начальное приближение . В случае это можно сделать графически, определив координаты точки пересечения кривых, описываемых уравнениями и .
4. Задача решения системы (3.22) может быть сведена к задаче поиска минимума функции . Так как функция неотрицательная, ее минимальное значение, равное нулю, достигается в точке , являющейся решением системы (3.22). Для поиска минимума функции можно применить различные методы поиска безусловного экстремума функций многих переменных (первого, второго, нулевого порядков).
Далее рассмотрим основные методы решения задачи (3.22).
Метод простых итераций для решения нелинейных систем
Для применения метода требуется привести систему (3.22) к равносильному виду:
 (3.24) или в векторной форме  (3.25)
где , функции определены и непрерывны в окрестности изолированного решения системы (3.24).
Алгоритм метода простых итераций для систем
1. Задать начальное приближение и малое положительное число (точность). Положить .
2. Вычислить по формуле
 (3.26) или  (3.27)
3. Если , процесс завершен и . Если , то положить и перейти к п.2.
Замечания
1. Итерационный процесс, реализуемый согласно (3.27), соответствует параллельному итерированию, так как для вычисления (k+1)-го приближения всех неизвестных учитываются вычисленные ранее их k-е приближения.
2. Система (3.22) может быть преобразована к виду (3.24) различными способами, например, с помощью выражения переменных , таким образом, чтобы выполнялось условие сходимости.
Другой способ заключается в замене системы системой , где — неособенная матрица. В качестве матрицы можно использовать, например, , если , где
 — матрица Якоби.
В случае, если , следует выбрать другое начальное приближение. Заметим, что при таком выборе метод простых итераций совпадает с упрощенным методом Ньютона.
3. В качестве можно использовать различные нормы векторов.
Теорема 3.13 (о достаточном условии сходимости метода простых итераций). Пусть функции и , непрерывны в области , причем выполнено неравенство (где — некоторая постоянная)
 (3.28)
Если последовательные приближения не выходят из области , то процесс последовательных приближений сходится: и вектор является в области единственным решением системы (3.25).
Замечания
1. Вместо условия (3.28) можно также использовать
 (3.29)
2. Условия (3.28), (3.29) выполняются, если для любого справедливы неравенства соответственно, где
Пример 3.17. Найти корни нелинейной системы уравнений расположенные в первом квадранте, методом простых итераций с точностью 
Решение
Преобразуем систему к виду (3.24) так, чтобы выполнялось условие сходимости: Найдем частные производные: Здесь принято . Далее воспользуемся методикой решения задачи. 1. Для выбора начального приближения найдем координаты точек пересечения кривых, соответствующих первому и второму уравнениям (рис. 3.17). Находим приближенные значения координат решения (по условию задачи нас интересуют только корни с положительными координатами): . Проверим выполнение условий сходимости. Будем рассматривать окрестность найденной точки  Тогда Следовательно, можно получить оценки: Очевидно, условие (3.28) выполняется. Если последовательные приближения не будут выходить из области , то согласно теореме 3.13 итерационный процесс будет сходящимся. В поставленной задаче . 2,3. Выполним расчеты по формулам (3.27): а результаты поместим в табл. 3.17. Заметим, что величина при увеличении номера итерации уменьшается, что характерно для любого сходящегося процесса. Найдено приближенное решение: . При этом .
Метод Зейделя для решения нелинейных систем уравнений
Метод Зейделя предназначен для решения систем, записанных в форме (3.24). Этот метод является модификацией метода простых итераций, где после задания начального приближения вместо параллельного итерирования производится последовательное итерирование, причем на каждой итерации в каждое последующее уравнение подставляются значения неизвестных, полученных из предыдущих уравнений.
Алгоритм метода Зейделя для решения нелинейных систем
1. Задать начальное приближение и малое положительное число (точность). Положить .
2. Вычислить по формулам
где прямоугольниками отмечены значения, которые берутся из предшествующих уравнений на текущей итерации.
3. Если , процесс завершить и положить . Если , то положить и перейти к п.2.
Пример 3.18. Найти корни системы расположенные в первом квадранте, методом Зейделя с точностью 
Решение
Преобразование системы к виду (3.24) и поиск начального приближения описаны в примере 3.17. 1. Зададим начальное приближение . В поставленной задаче . 2, 3. Выполним расчеты по формулам (3.30): а результаты поместим в табл. 3.18. Найдено приближенное решение . При этом .
Метод Ньютона для решения нелинейных систем уравнений
Метод используется для решения систем вида (3.22) или (3.23). Формула для нахождения решения является естественным обобщением формулы (3.14):
 (3.31)
где — матрица Якоби.
Так как процесс вычисления обратной матрицы является трудоемким, преобразуем (3.31) следующим образом:
где — поправка к текущему приближению .
Умножим последнее выражение слева на матрицу Якоби 
В результате получена система линейных алгебраических уравнений относительно поправки . После ее определения вычисляется следующее приближение .
Алгоритм метода Ньютона для решения нелинейных систем
1. Задать начальное приближение и малое положительное число (точность). Положить .
2. Решить систему линейных алгебраических уравнений относительно поправки 
 (3.32)
3. Вычислить следующее приближение: .
4. Если , процесс закончить и положить . Если , то положить и перейти к пункту 2.
Достаточные условия сходимости метода Ньютона для систем
Теорем а 3.14 (о достаточных условиях сходимости метода Ньютона). Пусть функция непрерывно дифференцируема в открытом выпуклом множестве . Предположим, что существуют и , такие, что , и существует , причем и . Тогда существует такое, что для всех последовательность , порождаемая соотношением (3.31), сходится к и удовлетворяет неравенству
Здесь использованы следующие обозначения: — открытая окрестность радиуса с центром в точке ; запись означает, что непрерывна по Липшицу, где — константа Липшица, то есть
Замечания
1. Теорема 3.14 свидетельствует о локальной квадратичной сходимости метода Ньютона. 2. К недостаткам метода Ньютона следует отнести: – необходимость задавать достаточно хорошее начальное приближение; – отсутствие глобальной сходимости для многих задач; – необходимость вычисления матрицы Якоби на каждой итерации; – необходимость решения на каждой итерации системы линейных уравнений, которая может быть плохо обусловленной.
Достоинством метода является квадратичная сходимость из хорошего начального приближения при условии невырожденности матрицы Якоби.
▼ Примеры 3.19-3.21
Пример 3.19. Решить систему методом Ньютона с точностью 
Решение
Пример 3.20. Найти решение системы расположенное в первом квадранте с точностью 
Решение
1. Выберем начальное приближение . В поставленной задаче . Положим . 2°. Составим систему (3.32). Так как  то Отсюда с помощью метода Гаусса единственного деления находим . 3°. Вычислим . Этот же результат может быть непосредственно получен по формуле (3.31): 4°. Так как , то положим и перейдем к пункту 2. 2(1). Составим систему (3.32): . Применяя метод Гаусса единственного деления, получаем 3.1. Вычислим . 4(1). Так как , то положим и продолжим решение по алгоритму. Результаты дальнейших расчетов приведены в табл. 3.20. Из сопоставления полученных результатов с табл. 3.17 следует, что по методу простых итераций точность достигается за четыре итерации, а методом Ньютона точность достигнута всего за три приближения.
Пример 3.21. Найти решение системы методом Ньютона с точностью 
Решение
1. Выберем в качестве начального приближения . В поставленной задаче . Положим . 2(0), 3(0). Воспользуемся формулой (3.31). Матрица Якоби имеет вид В точке справедливо В результате 4(0). Так как , то положим и перейдем к пункту 2. 2(1). В точке справедливо Составим и решим систему С помощью метода Гаусса единственного деления получаем 3(1). Вычислим 4(1). Так как , то положим и перейдем к пункту 2. 2(2). Составим и решим систему Применяя метод Гаусса, находим 3(2). Вычислим 4(2).Так как , то процесс завершен и .
Упрощенный метод Ньютона для нелинейных систем
В этом методе в отличие от метода Ньютона (3.31) обратная матрица ищется только один раз в начальной точке 
 (3.33)
Заметим, что при решении одного уравнения упрощенным методом Ньютона производная функции вычисляется также один раз в начальной точке.
Методика решения задачи аналогична изложенной в предыдущем разделе, где вместо (3.32) используется система
матрица которой не изменяется от итерации к итерации.
Очевидно, сходимость упрощенного метода Ньютона в общем случае хуже по сравнению со сходимостью процесса (3.31).
Пример 3.22. Найти положительное решение системы упрощенным методом Ньютона с точностью 
Решение
1. Выберем начальное приближение. Из рис. 3.18 следует, что для нахождения положительного решения системы можно принять . В поставленной задаче . Положим . 2(0), 3(0). Так как , то для выполнения вычислений по формуле (3.33) найдем обратную матрицу  Поэтому 4(0). Так как , то положим и перейдем к п.2. 2(1), 3(1). По формуле (3.33) получаем 4(1). Так как , то положим и перейдем к пункту 2. 2(2), 3(2). По формуле (3.33) получаем 4(2). Поскольку , то положим и перейдем к пункту 2. 2(3), 3(3). По формуле (3.33) имеем 4(3).Поскольку , то процесс завершен и .
Метод секущих для решения нелинейных систем уравнений
Идея метода секущих (метода Бройдена) заключается в аппроксимации матрицы Якоби с использованием уже вычисленных значений функций, образующих систему (сравните с методом секущих для уравнения , изложенным ранее).
Алгоритм метода секущих для нелинейных систем1. Задать начальное приближение  и малое положительное число е. 2. Положить  и  , где  — матрица Якоби. 3. Решить систему линейных алгебраических уравнений  относительно  — поправки к текущему приближению. 4. Вычислить  . 5. Если  , процесс завершить и положить  . Если  , вычислить положить  и перейти к п.3.
Замечания
1. Можно доказать, что если достаточно близко к корню , где матрица Якоби не вырождена, и если достаточно близка к , то последовательность итераций сходится к сверхлинейно.
2. Когда метод секущих сходится к сверхлинейно, нельзя предполагать, что последняя из аппроксимаций якобиана будет приблизительно равняться , хотя часто это именно так.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|