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

 

     При вычисления следует прекратить, и после округления получим .

     Сравнение результатов итераций со значением  показывает, что приближения содержат 1, 3, 6 верных значащих цифр соответственно. Это подтверждает отмеченный ранее факт, что при каждой итерации метода Ньютона число верных значащих цифр примерно удваивается. 
 

     Пример 2.

     Используя метод Ньютона, укажем итерационный процесс вычисления , где , - натуральное число.

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

      .                          (1.10)

 

     

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

2.1. ОПИСАНИЕ МЕТОДА.

 

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

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

                                                     (*)

каждую  из функций  линейной частью её разложения по формуле Тейлора в точке :

     

.

     В результате придём к системе линейных алгебраических уравнений: 

     

,

     

,

     .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

     

, 

имеющей в матричной форме записи вид: 

      .                                        (2.1)

     Здесь - матрица Якоби. .

     Предположим, что матрица  невырожденная, т.е. существует обратная матрица . Тогда система (2.1) имеет единственное решение, которое принимается за очередное приближение к решению . Таким образом, приближение удовлетворяет равенству:

      ,                                   (2.2)

     выражая из которого , выводим итерационную формулу метода Ньютона:

      .                                   (2.3)

     Замечание.

     Формула (2.3) предполагает использование трудоёмкой операции обращения матрицы, поэтому  непосредственное её использование  для вычисления в большинстве случаев нецелесообразно. Обычно вместо этого решают эквивалентную системе (2.2) систему линейных алгебраических уравнений:

                                                   (2.4)

относительно  поправки . Затем полагают:

                                                            (2.5) 
 

2.2. СХОДИМОСТЬ МЕТОДА.

 

     Сформулируем  основную теорему о сходимости метода Ньютона. 
 

     Теорема 3.

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

     

,      . 

     Эта оценка означает, что метод сходится с квадратичной скоростью.

     Квадратичная  скорость сходимости метода Ньютона  позволяет использовать простой  практический критерий окончания:

      .                                                (2.6)

     Пример 3.

     Используя метод Ньютона, найдём с точностью  решение , системы .

     Возьмём , и будем вести вычисления по формулам (2.4), (2.5), в которых

     

,       .

     Результаты  вычислений с шестью знаками мантиссы приведены в табл. 2.

     Табл. 2

      

     При критерий окончания выполняется и можно положить , . 

2.3. ТРУДНОСТИ ИСПОЛЬЗОВАНИЯ.

 

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

 

     

3. МОДЕФИКАЦИЯ МЕТОДА  НЬЮТОНА.

 

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

     Однако  при оценке общеё трудоёмкости метода следует учитывать, что на каждой итерации требуется выполнение следующей  дополнительной работы:

     1) вычисление  компонент вектора ;

     2) вычисление  компонент матрицы Якоби ;

     3) решение системы линейных алгебраических уравнений (2.4).

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

3.1. УПРОЩЁННЫЙ МЕТОД  НЬЮТОНА.

 

     Заменим в расчётных формулах метода Ньютона (2.4), (2.5) матрицу  , зависящую от , постоянной матрицы . В результате получим расчётные формулы упрощённого метода Ньютона:

      ,                                        (3.1)

      .                                           (3.2)

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

     По  сравнению с методом Ньютона  число итераций, необходимое для  достижения заданной точности , существенно возрастает. Тем не менее общие вычислительные затраты могут оказаться меньше. Причины этого состоят в следующем. Во-первых, вычисление матрицы Якоби производится здесь только один раз; во-вторых при использовании упрощённого метода Ньютона (3.1), (3.2) многократно решается система линейных уравнений с фиксированной матрицей и различными правыми частями. Это означает, что при решении систем (3.1) методом Гаусса возможно применение LU – разложения матрицы , которое резко уменьшает число операций, необходимых для вычисления .

3.2. ИСПОЛЬЗОВАНИЕ ФОРМУЛ  ЧИСЛЕННОГО ДИФФЕРЕНЦИРОВАНИЯ.

 

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

     Например, можно использовать следующую конечно-разностную аппроксимацию производной:

      .

     Параметры - это конечно-разностные шаги.

     Если  в расчётных формулах метода Ньютона (2.4), (2.5) заменить матрицу  аппроксимирующей её матрицей с элементами , то получим следующий итерационный метод:

       ,                                           (3.3)

      .                                           (3.4)

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

     Следующие три метода можно рассматривать как варианты метода (3.3), (3.4), в которых реализованы специальные подходы к вычислению вектора . Для того чтобы приведённые ниже рассуждения были формально корректными, в формуле (3.3) положим ,  если оказалось, что .

3.3. МЕТОД ЛОЖНОГО  ПОЛОЖЕНИЯ.

 

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

3.4. МЕТОД СЕКУЩИХ.

 

     Можно связать задание последовательности с какой-либо сходящейся к нулю векторной последовательностью, например, с последовательность невязок или поправок . Так, полагая , где j=1,…n, a k=1,2,…, приходим к простейшему методу секущих — обобщению скалярного метода секущих:

      ,                                    (3.5)

где

     

    ,

k=1,2,3,… .

     Этот  метод является двухшаговым и  требует задания двух начальных  точек  и . При п = 1 сходимость метода (3.5) имеет порядок . Можно рассчитывать на такую же скорость и в многомерном случае.

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

       из (3.5).

3.5. МЕТОД СТЕФФЕНСЕНА.

 

     Вычисления по методу Стеффенсена производят по формулам (3.3), (3.4), где .

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

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