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

                             Федеральное агентство по образованию

                        Государственное образовательное  учреждение

                            Высшего профессионального образования

            Владимирский Государственный Гуманитарный  Университет 
 
 
 
 
 

                 Курсовая работа на тему

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

                                                                             Выполнила:

                                                                                                                                        студентка гр. МИ-41

                                                                                                 Касиванова Н.И.

                                                                                                 Проверила:

                                                                                                 Наумова С.Б. 
 
 

                                                 Владимир 2010

Содержание:

     1. Методы отыскания решений систем  нелинейных уравнений.

            1.1.  Постановка задачи.

            1.2. Основные этапы решения.

            1.3. Корректность и обусловленность  задачи.

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

     3. Метод Ньютона, его реализация  и модификации.

            3.1. Метод Ньютона. 

            3.2. Метод Ньютона с последовательной  аппроксимацией матриц.

            3.3. Разностный метод Ньютона.

            3.4. Обобщение полюсного метода  Ньютона на многомерный случай.

     4. Численный пример.

     5. Листинг программы на языке  Mathcad. 
 
 
 
 
 
 
 
 
 
 
 

    1.Будем считать, что в множестве n-мерных векторов введена некоторая норма, порождающая соответствующую норму для квадратных матриц порядка n (см. § 5.2).

    1. 1. Постановка задачи. Задача отыскания решения системы нелинейных уравнений с n неизвестными вида

                                                                                                   (1)

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

исследованиях интерес представляет, как правило, определение не одного, а 

нескольких параметров (нередко их число доходит до сотен  и тысяч).

Найти точное решение  системы, т.е. вектор  = , удовлетворяющий уравнениям (1), практически невозможно. В отличие от случая решения систем линейных алгебраических уравнений использование прямых методов здесь исключается. Единственно реальный путь решения системы (1) состоит в использовании итерационных методов для получения приближенного решения = , удовлетворяющего при заданном ε > 0 неравенству < ε.

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

    Пример 1.1. Рассмотрим систему уравнений  

Здесь , — неизвестные, t — параметр. Первое уравнение задает на плоскости O эллипс, второе уравнение — параболу. Координаты точек пересечения этих кривых дают решения системы. Если значения параметра t изменяются от -2 до 2, то возможны следующие ситуации (рис. 1):

    а) t = -2 — решений нет;

    б) t = -1 — одно решение;

      в) t = 0 — два решения;

    г) t = 1 — три решения;

    д) t = 2 — четыре решения.

          

    Для дальнейшего удобно использовать сокращенную  векторную 

форму записи систем. Наряду с вектором неизвестных  х = рассмотрим вектор-функцию f = . В этих обозначениях система (1) примет вид

                                             f(x) = 0.                                                                      (2)

    Будем считать функции (x) непрерывно дифференцируемыми в некоторой окрестности решения . Введем для системы функций матрицу Якоби

 (x) = ,                                                                              (3)

которая будет  использована в дальнейшем.

    1.2. Основные этапы решения.

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

которое содержит только одно это решение и расположено  в достаточно малой его окрестности. Часто в качестве такого множества  выступает параллелепипед или шар  в     n-мерном пространстве.

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

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

    На  втором этапе для вычисления решения  с заданной точностью ε используют один из итерационных методов решения  нелинейных систем.

    Пример  1. Произведем локализацию решений системы  

    На  плоскости O построим графики уравнений системы. График первого

уравнения —  это лист Декарта¹ (рис. 1.2, а). График второго уравнения

состоит из луча — биссектрисы первого координатного  угла и кривой, пересекающей эту  биссектрису в точке (рис. 1.2, б).

    Из  рис. 1.3 видно, что эти кривые пересекаются в трех точках А, В, С, т.е. система имеет три решения. Так как оба графика симметричны относительно прямой = , то координаты точки В равны и их легко вычислить: = 4, = 4. В силу этой же симметрии достаточно определить только координаты , точки С, так как точка А имеет координаты =  и = . Из рис. 3 замечаем, что точка С содержится в прямоугольнике П = {(x,y) : 3.5 4,  1.5 2.5} и 3.8, 2.

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

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

  

                                               Рис. 1.2

                                                Рис. 1.3

    Пример 2. Система уравнений  

сводится к  одному нелинейному уравнению = 8  после того, как

из второго  уравнения выражается у = .

     1.3. Корректность и обусловленность задачи.

     Будем считать, что система (1) имеет решение  , причем в некоторой окрестности этого решения матрица Якоби (x) невырождена. Выполнение последнего условия гарантирует, что в указанной окрестности нет других решений

системы (1). Случай, когда в точке  матрица (x)  вырождена, является существенно более трудным и нами рассматриваться не будет. В одномерном случае первая ситуация отвечает наличию простого корня уравнения f(x) = 0, а вторая — кратного корня.

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

      Аналогично, погрешности в вычислении  вектор-функции  f  приводят к появлению области неопределенности D, содержащей решение системы (1) такой, что для всех         х D векторное уравнение f(х) = 0 удовлетворяется с точностью до погрешности. Область D может иметь довольно сложную геометрическую структуру. Мы удовлетворимся только лишь оценкой радиуса этой области.

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

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

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

    f_i(x₁,x₂,...x_n) = 0, i=1,2,..n;

     Приведём  систему уравнений к специальному виду:

      (2.1)

     Или в векторном виде . (2.2)

     Причем  переход к этой системе должен быть только при условии, что 

       является сжимающим отображением.

     Используя некоторое начальное приближение  X⁽⁰⁾= (x₁⁽⁰⁾,x₂⁽⁰⁾,...x_n⁽⁰⁾)

     построим  итерационный процесс X^(k+1) = F (X^(k)). Расчёты продолжаются до выполнения условия . Тогда решением системы уравнений является неподвижная точка отображения .

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

     Приведём  теорему о сходимости, выполнение условий которой приводит к нахождению решения системы.

     Теорема (о сходимости). Пусть

     1). Вектор-функция Ф(х) определена  в области

     

     2). Для  выполняется условие

     

     3). Справедливо неравенство

     

     Тогда в итерационном процессе:

     1.

     2. ,

     где – решение системы уравнений;

     3. ,

     Замечание. Неравенство условия 2) есть условие  Липшица для вектор -функции Ф(х) в области S с константой (условие сжатия). Оно показывает, что Ф является оператором сжатия в области S, т. е. для уравнения (2.2) действует принцип сжатых отображений. Утверждения теоремы означают, что уравнение (2.2) имеет решение в области S, и последовательные приближения сходятся к этому решению со скоростью геометрической последовательности со знаменателем q.