Методы решения нелинейных уравнений. Общая информация

Если приращения   таковы, что переменные  принимают значения близкие к корню, то будем считать, что левые части уравнений системы (3.2) обращаются в нули. Тогда отбросив R_i сведем задачу решения системы нелинейных уравнений (3.1) к решению системы линейных уравнений, в которой неизвестными являются приращения ,  , :

                       (3.3)

Система (3.3) – система  линейных уравнений с неизвестными  j= j. Запишем (3.3) в матричной форме

,

где      

матрица коэффициентов системы (3.3),

  - вектор свободных членов,

= - вектор неизвестных системы (3.3).

 

 Матрица А, составленая  из частных производных  ; ;  j= ,  называется матрицей Якоби или Якобианом.

Метод Ньютона состоит  из двух этапов:

На первом этапе реализации метода Ньютона необходимо построить  систему (3.3).

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

       (3.4)

 или           j= j.

Итерационный процесс  прекращается, как только выполнится условие 

 j=                                                     (3.5)

по всем приращениям одновременно.

1.1 Определение матрицы Якоби

В методе Ньютона на каждом шаге итерационного процесса поиска необходимо формировать матрицу  Якоби, при этом каждый элемент матрицы  можно определить:

1) аналитически, как  частную производную ,

2) методом численного  дифференцирования, как отношение  приращения функции   к приращению  аргумента, т.е. 

В результате частная производная  по первой координате  х₁ определится как   , а частная производная по  координате  х_j определится как        

 

,

где .

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

На рисунке 3.1 представлена укрупнённая схема алгоритма (блок-схема) метода Ньютона. На рисунках 3.2 и 3.3 представлены схемы алгоритмов метода Ньютона  с различными способами определения  матрицы Якоби.

Рис.3.1. Блок-схема алгоритма  метода Ньютона

 

 

Рис.3.2. Схема алгоритма  метода Ньютона

(аналитическое определение  матрицы Якоби)

 

 

 

 

 

 

 

 

 

Рис.3.3. Схема алгоритма  метода Ньютона 

(определение матрицы  Якоби с помощью численного  дифференцирования)

2.3.3 Модификации метода Ньютона

1. Вычисления в методе Ньютона  гораздо сложнее, чем при простых  итерациях, т.к. на каждой итерации  требуется находить матрицу производных  и решать систему линейных  уравнений. Поэтому рекомендуется  такой приём: матрица Якоби  вычисляется только на начальном  приближении. Однако сходимость  при этом видоизменении становится  линейной, причём обычно не с  малой константой, ибо матрица  производных на начальной итерации  может заметно отличаться от  окончательной. Поэтому скорость  сходимости заметно уменьшается  и требуемое сисло итераций  возрастает.

2. В ещё одной модификации  итерационную формулу метода  Ньютона вводится параметр  следующим образом

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

(3.6)

Проведём обоснование такой  процедуры в евклидовой норме.

Ведём в рассмотрение функцию-невязку  для уравнения (3.1)

Найдём градиент , используя представление

С этой целью выделим главный  член приращения

Следовательно, по определению 

Обозначим и найдём производную функции в точке по направлению :

если  .

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

 

2.3.4 Квазиньютоновкие методы

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

Рассмотрим  первый из классов, где матрица В_к с размерами п х п аппроксимирует матрицу . Перед началом итераций задают начальную точку а матрицу В_о обычно получают, или допуская, что она является единичной, или аппроксимируя конечно-разностными формулами. Потом для k = 0, 1.... вычисляют

 

 

 

Где — n- мерный вектор, который является параметром рассматриваемого класса методовв. Если взять таким, что равняется ,то будем иметь первый метод Бройдена. Выбор соответствует методу Пирсона, а — симметрическому методу первого ранга.

Во втором из рассматриваемых здесь классов  квазиньютоновских методов матрица  с размерами п х п аппроксимирует матрицу . Перед началом итерации задают начальную точку х^{0) и матрицу , которая обычно или равна единичной, или является обратной к конечно-разностной аппроксимации . Потом вычисляют

 

 

где — n-мерный вектор, который является параметром рассматриваемого класса методов. Конкретный вид вектора отвечает соответствующему методу: например, — второму методу Бройдена, — методу Мак-Кормика.

Заметим, что если задать то можно вести перерасчет не В_к, а матриц по формуле

(3.11)

эквивалентной (3.27). Это требует порядка 0(п²) арифметических действий вместо 0(п³), необходимых для решения системы линейных уравнений .

Как видно  из (3.11), между формулами (3.8) и (3.10) имеет место определенная связь. Так.если , то при . Таким образом, один и тот же метод может реализоваться двумя разными формулами (3.8) и (3.10), которые эквивалентные теоретически, но их численная реализация может отличаться по эффективности.

Рассмотрим, например, первый метод Бройдена. Его  можно реализовать по формуле (3.8) так, что это потребует в общем 0(n³) арифметических действий. Это оказывается возможным, если подать матрицу В_к в виде произведения , где — ортогональная, а — верхняя треугольная матрица. Действительно, в этом случае решение системы нуждается в только 0(n³) арифметических действий. Имея , на представление матрицы В_к+1, которая удовлетворяет (3.8) в виде , необходимо 0(п²) арифметических действий. Важное преимущество формулы (3.8) перед (3.39) заключается в том, что в (3.8) нет необходимости умножения матрицы на вектор, поскольку

Существуют  квазиньютоновские методы, которые  учитывают симметричность матрицы  Якоби и вырабатывают последовательность симметричных матриц В_к, (или ). Эти методы также можно разделить на два класса. В первом из них матрица В_к аппроксимирует F(х). В отличие от описанного выше класса, который задается формулами (3.7) и (3.8), здесь нужна симметричность матрицы Во, и вместо (3.8) используется формула

где значение параметра  отвечает симметричному варианту Пауелла методу Бройдена, а — методу Давидона - Флечера - Пауелла.

Во втором из рассматриваемых классов квазиньютоновских  методов матрица Н_к аппроксимирует матрицу . Здесь матрица Н_о должна быть симметричной, а вместо (3.10) используется формула

Где соответствует методу Бройдена-Флечера-Голвдфарба-Шенно, что является одним из наилучших (с вычислительной точки зрения), который учитывает симметричность матрицы Якоби.

Описанные выше квазиньютоновские методы сходятся лишь при достаточно хорошом начальном  приближении х⁽⁰⁾. Для расширения области их сходимости можно использовать прием, который имеет название одномерного поиска.

Пусть имеем  квазиньютоновское направление  (или ). Используем длину шага = 1 и проверим неравенство

(3.12)

где - евклидовая норма. Если оно выполняется, то заканчиваем одномерный поиск и считаем

(3.13)

т.е. уменьшаем длину шага (устанавливая, например, ), пока не выполнится (3.12). На этом заканчиваем одномерный поиск и переходим к формуле (3.13).

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