Методы численного решения систем нелинейных уравнений

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

Сибирская государственная автомобильно-дорожная академия

(СибАДИ) 

Факультет   Информационные системы в управление

Специальность  КОИБАС

Кафедра   Информационная безопасность 
 
 
 
 
 
 
 
 

Пояснительная записка

к курсовой работе 

по дисциплине   Вычислительная математика и программирование 

      Методы  численного решения систем нелинейных уравнений 
 
 
 
 
 
 
 

Выполнил:

студент группы БИ06-И2

Кобков  В.А. 

Руководитель: Епифанцева М. Я. 
 
 
 
 
 
 
 

Омск - 2008 г.

Содержание 

1. Графическое отделение корней 4

1.1 Графическое решение 5

2. Обзор методов решения систем нелинейных уравнений 6

2.1 Решение систем нелинейных уравнений 6

2.1.1 Метод простых итераций 6

2.1.2 Решение систем нелинейных уравнений методом Ньютона 7

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

3. Разработка и отладка программы 10

4. Блок-схема рабочей программы 11

5. Листинг программы 14

6. Решение контрольного примера 16

7. Список литературы 17 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Аннотация

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

Метод Зейделя  является частным случаем, метода простой итерации. Точность данных методов e= 0,001. Программа разработана на языке Borland Pascal 7.0

 

1. Графическое отделение корней

 

Решение уравнения  f_n(x_n)=0 из системы уравнений F(x_n)=0 состоит из двух этапов:  

1) Отделение корней, то есть отыскание достаточно малых областей, в каждой из которых заключен ровно один корень системы уравнений.  

2) Вычисление каждого отделенного корня с заданной точностью.  

Отделение корней можно произвести графически. [2] 

Дана система  нелинейных уравнений

 

Необходимо построить  графики этих функций, далее преобразуем систему для решения

Проверяем условие  сходимости

Находим:

Определяем область  сходимости G. [5] 

Граница области  сходимости определится при решении  системы, полученной в ходе предыдущих действий. На графике уравнений строим область сходимости G.

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

1.1 Графическое решение

 

Кривые, определяемые уравнением (*) изображены на рис. (1а). Эти кривые пересекаются в двух точках ξ₁ и ξ₂. Возьмем в качестве начального значения (графическое решение) . [3]

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Обзор методов решения систем нелинейных уравнений

 

2.1 Решение систем нелинейных уравнений

Дана система  нелинейных уравнений

или

Необходимо решить эту систему, т.е. найти вектор , удовлетворяющий системе (1) с точностью .

Вектор  определяет точку в n-мерном Евклидовом пространстве, т.е. этому пространству и удовлетворяет всем уравнениям системы (1).

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

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

Выбор начальной  точки  во многом определяется интуицией и опытом специалиста. [5] 

2.1.1 Метод простых итераций

Для применения этого метода исходная система  (1) должна быть преобразована к виду

или

Далее, выбрав начальное  приближение  и используя систему (2), строим итерационный процесс поиска по схеме:

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

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

При этом условие  (3) должно выполняться одновременно по всем переменным.

Метод простых итераций используется для решения таких систем нелинейных уравнений, в которых выполняется условие сходимости итерационного процесса поиска, а именно:

т.е. сумма абсолютных величин частных производных  всех преобразованных уравнений  системы (2) по j-ой переменной меньше единицы. [5]

 

2.1.2 Решение систем нелинейных уравнений методом Ньютона

Дана система  нелинейных уравнений

или

Необходимо решить эту систему, т.е. найти вектор , удовлетворяющий систему (5) с точностью .

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

В основе метода Ньютона лежит идея линеаризации всех нелинейных уравнений системы  (5). Сообщим всей системе (5) малые приращения h_j и разложим каждое уравнение системы (5) в ряд Тейлора:

где

h_j- приращение по каждой x_j;

R_i - остаточные нелинейные члены второго и более высоких порядков каждого ряда Тейлора.

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

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

где

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

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

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

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

или

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

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

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

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

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

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

а частная производная  по координате х_j определится как

где .

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

3. Разработка и отладка программы

 

1.  Будем  представлять систему (*) в виде: