Итерациональные методы решения нелинейных уравнений

ГЛАВА 3. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ. 

      Определение 3.1.

      Системами нелинейных уравнений (СНУ) называются системы вида:

                           (3.1)

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

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

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

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

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

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

    §3.1. Метод простых  итераций для решения  систем нелинейных уравнений. 

      От  исходной системы (3.1) путем элементарных преобразований переходим к эквивалентной системе вида:

                             (3.2)

      Итерационный  процесс, определяемый формулами

                  

можно начать, задав начальное приближение  .

      Достаточным условием сходимости итерационного  процесса является выполнение одного из двух условий:

или

.

      Распишем  первое условие:

                  при  ,

                …

                  при  .

      Распишем  второе условие:

                  при  ,

                …

                  при  .

      Рассмотрим  один из способов приведения системы (3.1) к виду (3.2), допускающему сходящийся итерационный процесс.

      Пусть задана система второго порядка  вида:

                                (3.3)

      Требуется привести ее к виду:

                               . (3.4)

      Умножим первое уравнение системы (3.3) на неизвестную  постоянную , второе - на , затем сложим их и прибавим к обеим частям уравнения . Получим первое уравнение преобразованной системы (3.4) в виде

где .

      Далее, умножим первое уравнение системы (3.3) на неизвестную постоянную , второе - на , затем сложим их и прибавим к обеим частям уравнения . Тогда второе уравнение преобразованной системы (3.4) будет иметь вид:

где .

      Неизвестные постоянные определим из достаточных условий сходимости

                       и  .  (3.5)

      Запишем эти условия более подробно:

,

.

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

                            (3.6)

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

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

     Пример 3.1. Построить рабочие формулы метода простых итераций для численного решения СНУ вида:

                          (3.7)

при начальном  приближении

                             . (3.8)

     Заметим, что аналитическим решением СНУ (3.7) являются точки и .

     Для построения рабочих формул метода простых  итераций для численного решения системы необходимо решить СЛАУ (3.6). Для ее решения необходимо вычислить частные производные при начальном приближении (3.8):

                 .

     Тогда СЛАУ (3.6) запишется так:

     Решением  этой системы являются , , . Тогда рабочие формулы метода простых итераций для решения СНУ (3.7) примут вид:

     Для реализации на ЭВМ рабочие формулы  можно переписать так:

           

§3.2. Метод Ньютона  для решения систем нелинейных уравнений.

 

      Пусть требуется решить систему нелинейных уравнений с действительными левыми частями вида (3.1):

      Введем  обозначения.

      Совокупность  аргументов будем рассматривать как -мерный вектор , а совокупность функций - как вектор-функцию . Тогда система (3.1) в матричной форме запишется так:

                               . (3.9)

      Для решения системы (3.9) будем использовать метод последовательных приближений.

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

                             , (3.10)

где - погрешность корня (правка).

      Подставляя (3.10) в (3.9), получим:

                               . (3.11)

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

                      , (3.12)

где - матрица Якоби системы функций относительно переменных .

      Система (3.12) представляет собой линейную систему  относительно правок с матрицей , поэтому формулу (3.12) можно записать в виде:

                          . (3.13)

      Если  матрица  невырожденная, то существует и тогда, умножив обе части соотношения (3.13) на слева, получим

                          . (3.14)

      Следовательно,

                          . (3.15)

      Соотношение (3.15) является итерационной формулой метода Ньютона для решения систем нелинейных уравнений.

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

Недостатки  метода Ньютона:

• нахождение обратной матрицы на каждом итерационном шаге;
• возможность выхода приближения за пределы области и связанная с этим расходимость итерационного процесса.

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

                          . (3.16)

      Формула (3.16) является рабочей формулой модифицированного  метода Ньютона.

      Достоинством  данного метода является то, что  обратная матрица вычисляется один раз. Но ответа на второй вопрос модифицированный метод Ньютона не дает.

      Сходимость  модифицированного процесса (метода) Ньютона исследовалась Л.В. Канторовичем [8].

     Пример 3.2. Построить рабочие формулы метода Ньютона для численного решения СНУ (3.7) при начальном приближении (3.8).

      Для нахождения обратной матрицы в формуле (3.15) необходимо:

      1. Найти матрицу частных производных .

      2. Найти определитель этой матрицы:

                         .

3. Определить  обратную матрицу:

.

      Проведя несложные преобразования с матрицами, получим рабочую формулу метода Ньютона (3.15) в виде: