Методы отыскания решений систем нелинейных уравнений. Постановка задачи. Этапы решения. Метод простой итерации.

     Доказательство. Поскольку , то для приближения в силу предположения 3) имеем . Это значит, что . Покажем, что , k=2,3,… причём для соседних приближений выполняется неравенство

      (2.3)

     Будем рассуждать по индукции. При  утверждение справедливо, т.к. и . Допустим, что приближения принадлежат S, и неравенство (2.3) выполнено для . Поскольку , то для с учётом условия 2) теоремы имеем

      .

     По  индуктивному предположению 

      .

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

      ,

     т.е. неравенcтво (2.3) справедливо для . Покажем, что . Учитывая свойство (2.3) при , получаем

     

     Итак, , и первое утверждение теоремы доказано.

     Покажем, что последовательность является сходящейся. С этой целью проверим признак сходимости Коши (покажем, что последовательность является фундаментальной).

     По  аналогии с предыдущим для любых  р=1,2,… имеем

     

     Поскольку , то , поэтому для найдётся такой номер , что для будет

     

     Это означает выполнение признака Коши, что  гарантирует сходимость последовательности . Обозначим . Утверждение 2) теоремы доказано.

     Для доказательства последнего утверждения  воспользуемся полученным выше неравенством

       

     Перейдём  здесь к пределу при  . Учитывая непрерывность функции и тот факт, что , получаем требуемый результат – утверждение 3).

     Замечание 2. В условиях теоремы решение  уравнения (2.2) в области S является единственным.

     Действительно, пусть имеются два решения  , причём . Тогда

      ,

     Получили  противоречие, что и требовалось  доказать.

     Обсудим условие 2) доказанной теоремы. Рассмотрим уравнение (2.2) в покомпонентной записи

     

     и предположим, что функции  непрерывно-дифференцируемы в области S (т.е. существуют и непрерывны в S частные производные

      ).

     Теперь  выясним достаточное условие  выполнения неравенства 2) в этом случае.

     Образуем  матрицу Якоби системы функций 

      .

     Далее, будем использовать обобщенную теорему  о среднем (обобщение на случай вектор- функции формулы конечных приращений Лагранжа)

     

     Здесь матричная норма согласована  с векторной, , – точка отрезка, соединяющего х, у.

     Поскольку S – выпуклое множество, то . Предположим, что имеет место оценка

      , причём  . (2.4)

     Тогда согласно предыдущему выполняется  условие 2) теоремы

      .

     Таким образом, в случае дифференцируемости условие (2.4) на матрицу Якоби  гарантирует условие сжатия для вектор- функции  
 
 
 
 

3. МЕТОД НЬЮТОНА, ЕГО РЕАЛИЗАЦИИ И МОДИФИКАЦИИ

3.1. МЕТОД НЬЮТОНА

Пусть ( ) — некоторая последовательность невырожденных вещественных n x n-матриц. Тогда, очевидно, последовательность задач

,    k = 0,1,2,...

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

,  k = 0,1,2,...                        (3.1.1)

имеющий вид  метода простых итераций (4.2.1b) при  . В случае - это действительно МПИ с линейной сходимостью последовательности ( ) Если же различны при разных k, то формула (3.1.1) определяет большое семейство итерационных методов с матричными параметрами . Рассмотрим некоторые из методов этого семейства.

Положим , где

— матрица Якоби  вектор-функции F(x). Подставив это в (3.1.1), получаем явную формулу метода Ньютона

,                                           (3.1.2)

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

.                                          (3.1.3)

Применение (3.1.3) предполагает при каждом k = 0,1,2,... решение линейной алгебраической системы

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

.

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

Сравнивая (3.1.3) с формальным разложением F(x) в ряд Тейлора

,

видим, что последовательность ( ) в методе Ньютона получается в результате подмены при каждом k=0,1,2,... нелинейного уравнения F(x) = 0 или, что то же (при достаточной гладкости F(x)), уравнения

линейным уравнением

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

Новым, по сравнению  со скалярным случаем, фактором, осложняющим  применение метода Ньютона к решению n-мерных систем, является необходимость  решения n-мерных линейных задач на каждой итерации (обращения матриц в (3.1.2) или решения СЛАУ в (3.1.3)), вычислительные затраты на которые растут с ростом n, вообще говоря, непропорционально быстро. Уменьшение таких затрат — одно из направлений модификации метода Ньютона.

3.2. МОДИФИЦИРОВАННЫЙ  МЕТОД НЬЮТОНА

Если матрицу  Якоби F'(х) вычислить и обратить лишь один раз — в начальной точке , то от метода Ньютона (3.1.2) придем к модифицированному методу Ньютона

                                     (3.2.1)

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

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

Например, простое  чередование основного (3.1.2) и модифицированного (3.2.1) методов Ньютона приводит к  итерационной формуле

                                (3.2.2)

где k = 0,1,2,… За здесь принимается результат последовательного применения одного шага основного, а затем одного шага модифицированного метода, т.е. двухступенчатого процесса

                                     (3.2.3)

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

3.3. МЕТОД НЬЮТОНА  С ПОСЛЕДОВАТЕЛЬНОЙ  АППРОКСИМАЦИЕЙ МАТРИЦ

Задачу обращения  матриц Якоби на каждом k-м шаге метода Ньютона (3.1.2) можно попытаться решать не точно, а приближенно. Для этого можно применить, например, итерационный процесс Шульца, ограничиваясь минимумом — всего одним шагом процесса второго порядка, в котором за начальную матрицу принимается матрица, полученная в результате предыдущего  (k-1)-го шага. Таким образом приходим к методу Ньютона с последовательной аппроксимацией  обратных матриц:                             (3.3.1)

где k = 0,1,2,…, а и - начальные вектор и матрица ( ). Этот метод (будем называть его более коротко ААМН — аппроксимаиионный аналог метода Ньютона) имеет простую схему вычислений — поочередное выполнение векторных в первой строке и матричных во второй строке его записи (3.3.1) операций. Скорость его сходимости почти так же высока, как и у метода Ньютона. Последовательность ( ) может квадратично сходиться к решению уравнения F(x)=0 (при этом матричная последовательность ( ) также квадратично сходится к , т.е. в нормально развивающемся итерационном процессе (3.3.1) должна наблюдаться достаточно быстрая сходимость ( ) к нулю).

Применение той  же последовательной аппроксимации  обратных матриц к простейшему рекурсивному методу Ньютона (3.2.2) или, что то же, к  двухступенчатому процессу (3.2.3) определяет его аппроксимацирнный аналог

                         (3.3.2)

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

3.4. РАЗНОСТНЫЙ МЕТОД  НЬЮТОНА

На базе метода Ньютона (3.1.2) можно построить близкий  к нему по поведению итерационный процесс, не требующий вычисления производных. Сделаем это, заменив частные  производные в матрице Якоби  J(x) разностными отношениями, т.е. подставив в формулу (3.1.1) вместо матрицу где

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

3.5. ОБОБЩЕНИЕ ПОЛЮСНОГО  МЕТОДА НЬЮТОНА НА МНОГОМЕРНЫЙ СЛУЧАЙ

Переложим вывод  одномерного полюсного метода Ньютона (5.36) на векторную основу. Будем при  этом руководствоваться геометрическими  соображениями, опирающимися на рис. 5.12, и пользоваться теми же обозначениями.

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

                                             (3.5.1)

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

                                 (3.5.2)

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

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