4.3. Решение системы нелинейных уравнений

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

Метод Ньютона-Рафсона.

Пусть требуется найти значения неизвестных удовлетворяющих алгебраическим уравнениям:

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

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

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

являющейся линейной системой относительно погрешностей

Решив систему линейных алгебраических уравнений (4.3.3), вычислим следующее приближение для искомого решения:

(4.3.4)

Каждое приближение будет отличаться от точного решения, так как мы линеаризовали систему уравнений. Погрешности на каждом приближении будут становиться все меньше и меньше. Мы не будем останавливаться на условиях и скорости сходимости метода Ньютона-Рафсона. Скажем только, что если начальное приближение выбрано достаточно хорошо и матрица системы линейных уравнений (4.3.3) на каждой итерации хорошо обусловлена и имеет обратную матрицу, то метод Ньютона-Рафсона сходится к единственному в данной окрестности решению

Метод Ньютона-Рафсона имеет квадратичную сходимость

(4.3.5)

где М определяется матрицей системы (4.3.3) и удовлетворяет неравенству

Это сравнительно быстрая сходимость — после очередной итерации погрешность каждой неизвестной уменьшается примерно на один или два порядка. Итерационный процесс решения системы нелинейных уравнений (4.3.1) заканчивается, когда на очередной итерации погрешности всех неизвестных становятся меньше заданной величины е:

Запишем систему линейных уравнений (4.3.3) в матричном виде

(4.3.6)

где

F(x) — матрица Якоби, которая одновременно является матрицей системы линейных уравнений (4.3.3), — матрица-столбец значений функций (4.3.1), — матрица-столбец неизвестных на приближении. Запись системы (4.3.3) в матричной форме (4.3.6) похожа на запись

метода Ньютона для одного нелинейного уравнения.

Рекуррентное соотношение для одного нелинейного алгебраического уравнения имеет вид

Рекуррентное соотношение (4.3.4) для системы уравнений (4.3.3) в матричной форме имеет вид

Модифицированный метод Ньютона.

В некоторых случаях для решения системы (4.3.1) применяется модифицированный метод Ньютона, который имеет вид

(4.3.7)

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

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

Метод Ньютона (4.3.6) допускает еще одно видоизменение, которое называется методом Ньютона с параметром и имеет вид

(4.3.8)

где — изменяющийся на каждой итерации параметр. Параметр как бы корректирует правую часть системы (4.3.3), «улучшая» решение на итераций. Для использования метода Ньютона с параметром нужно иметь способ вычислять или оценивать параметр . Оценку параметра можно выполнять по приращениям неизвестных на итерационном шаге. Параметр обычно имеет значения Метод Ньютона с параметром обладает линейной сходимостью.

Метод простой итерации.

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

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

Метод Якоби. Рассмотренные до сих пор методы являлись линейными относительно новой итерации . Существуют и нелинейные методы, когда для вычисления хприходится решать нелинейные уравнения.

Одним из нелинейных методов является метод Якоби, в котором решаются нелинейных уравнений

(4.3.10)

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

Метод Зейделя.

Другим нелинейным методом является метод Зейделя, в котором решаются нелинейных уравнений

(4.3.11)

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

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

Метод градиента.

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

(4.3.12)

или

(4.3.13)

где — элементы некоторой положительно определенной матрицы — матрица-строка и матрица-столбец, элементами которых являются правые части уравнений системы (4.3.1). Функцию (4.3.12) будем считать частным случаем функции (4.3.13). Если есть некоторое решение системы (4.3.1), то . В других точках в силу положительной определенности матрицы А. Таким образом, решение системы (4.3.1) сводится к поиску нулевых минимумов функции

Будем рассматривать функцию как некоторую скалярную функцию -мерного векторного пространства и будем обозначать ее еще и как где искомые величины считаются компонентами -мерного вектора . Производные в этом пространстве являются компонентами вектора

(4.3.14)

для функции (4.3.12):

В матричной записи на итерации градиент (4.3.14) для функции (4.3.12) имеет вид

(4.3.15)

где — транспонированная матрица Якоби , которая определена в (4.3.6). Вектор как градиент скалярной функции, вычисленный при некоторых значениях ортогонален поверхности уровня, для которой , и направлен в сторону возрастания функции в данной точке -мерного пространства. Таким образом, итерационная зависимость для определения экстремума функции имеет вид

(4.3.16)

Остается определить множитель . Для этого подставим новое приближение (4.3.16) в исследуемую функцию и рассмотрим ее как функцию параметра

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

(4.3.17)

где

Функция дает изменение значения функции вдоль нормали к поверхности уровня в точке поэтому значение параметра получим из условия минимума функции как корень уравнения

Возьмем производную по , приравняем ее нулю и получим уравнение для определения

Отсюда получим параметр

где мы использовали равенство (4.3.15) и для краткости обозначили Таким образом, для принятых упрощений равенство (4.3.16) примет вид

(4.3.18)

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

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

Сжимающий оператор.

Все рассмотренные методы решения системы нелинейных уравнений можно записать в виде

(4.3.19)

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

(4.3.20)

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

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

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