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

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

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

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

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

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

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

                                                                             Выполнила:

                                                                                                                                        студентка гр. МИ-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.

     Доказательство. Поскольку , то для приближения в силу предположения 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).

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