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

Казанский Государственный  Технический Университет им. А.Н.Туполева

 

Кафедра автоматики и управления

 

 

 

 

 

 

 

Курсовая работа по дисциплине: «Информатика»

 на тему:

«Решение системы нелинейных уравнений  методом итерации»

 

 

 

 

 

 

 

 

 

Выполнил:

студент группы 3206

Султанов Б.Ф.

 

Руководитель: Кренев В.А.

 

 

 

 

 

 

 

 

Казань 2011

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Аннотация

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

Метод Зейделя является частным случаем, метода простой итерации. Точность данных методов 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.  Будем представлять систему (*) в виде:

2. Представим правые части уравнения в виде:

 
Для метода простой итерации

 

Для метода Зейделя

3. Для поиска коэффициентов λ_iј решим систему

 

4. Далее будем использовать систему на рис. (13) для поиска корней уравнения. В программе g₁(x₁,x₂)=y1 и g₂(x₁,x₂)=y2. [3]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

При разработке программы

использовались методы

простой итерации и Зейделя. На вход

подаются начальные значения корней

x1 и x2, просчитанные при

помощи графического решения рис. (1а).

Так же необходимо привести систему

уравнений (1) к системе вида (13) вручную,

для использование ее в программе.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Блок-схема  метода простой итерации

 

 

 

 

 

 

 

Блок-схема  метода Зейделя

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

uses crt;

var

d,e,x1,x2,y1,y2:real;

c,k,p:integer;

ch:char;

function f1(x1,x2:real):real;

begin

f1:=x1*sin(x1)-x2;

end;

function f2(x1,x2:real):real;

begin

f2:=x1*x1+x2*x2-1;

end;

procedure fun_y1_1_y2;

begin

y1:= x1-f1(x1,x2)/2+f2(x1,x2)/8;

y2:= x2+f1(y1,x2)/2-f2(x1,x2)/2;

end;

procedure fun_y1_y2;

begin

y1:= x1-f1(x1,x2)/2+f2(x1,x2)/8;

y2:= x2+f1(x1,x2)/2-f2(x1,x2)/2;

end;

procedure outputofresult;

begin

clrscr;

writeln('Korni uravnenia:');

writeln('x1 = ', y1:1:5);

writeln('x2 = ', y2:1:5);

writeln('Pogreshnosty priblegenia = ', d:1:7);

writeln;

writeln('Kolichestwo iteraziy = ',k);

writeln('Dlia prodolgenia nagmite lubui klavishu...');

repeat ch:= readkey until ch <> '';

k:=k+1;

end;

begin

repeat

k:=0; e:=0.001;

clrscr;

writeln('Reshenie sistem nelineinyh uravneni');

writeln('');

writeln('1 - Metod prostoiq iterazy');

writeln('2 - Metod Zeydely');

writeln('0 - Exit');

writeln('');

write('Enter: ');

readln(p);

c:=0;

if p=1 then c:=1;

if p=2 then c:=2;

if p=0 then c:=0;

case c of

0:begin

exit;

end;

1:begin

writeln('Vvedite nachalnoe priblegenie:');

write('x1 = ');

readln(x1);

write('x2 = ');

readln(x2);

repeat

fun_y1_y2;

d:= abs(y1-x1);

if abs(y2-x2)>d then d:= abs(y2-x2);

outputofresult;

x1:= y1; x2:= y2;

until d<e;

end;

2:begin

writeln('Vvedite nachalnoe priblegenie:');

write('x1 = ');

readln(x1);

write('x2 = ');

readln(x2);

repeat

fun_y1_1_y2;

d:= abs(y1-x1);

if abs(y2-x2)>d then d:= abs(y2-x2);

outputofresult;

x1:= y1; x2:= y2;

until d<e;

end;

end;

until (p<1) or (p>2);

end.

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

 

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

 

Начальное приближение

x1 = 0.9

x2 = 0.6

 

Корни уравнения

x1 = 0.80992

x2 = 0.58662

Погрешность приближения  = 0.0006517

Количество итераций = 4

 

Метод Зейделя:

 

Начальное приближение

x1 = 0.9

x2 = 0.6

 

Корни уравнения

x1 = 0.80928

x2 = 0.58648

Погрешность приближения = 0.0006042

 

Количество итераций =11

 

Проверка:

 

0.80928*sin(0.80928) - 0.58648 0

(0.58648)² + (0.80928)² -1 0

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1. И.В. Сухно, В.А. Волынкин, В.Ю. Бузько «Численные методы и программирвоание», Краснодар 2002
2. А.А. Самарский, А.В. Гулин «Численные методы», М. 1989
3. В.И. Ракитин, В.Е. Первушин «Практическое руководство по методам вычисления», М. 1998
4. Н.С.Бахвалов,  «Численные методы»,  М. 1975г.
5. Ю.В. Губарь, «Введение в математическое моделирование, курс лекций», М. 2007