Обчислювальна математика

РЕФЕРАТ



Об'єкт дослідження - система лінійних рівнянь.

Ціль роботи – опис метода Крамера, розробка програми, за допомогою якої методом Крамера можна вирішити систему лінійних рівнянь.

Метод дослідження - вивчення літератури, написання й налагодження програм на комп'ютері. 

Дану програму можна використати для знаходження невідомі системи лінійних рівнянь.

Розроблено одну програму, що демонструє знаходження невідомі системи лінійних рівнянь.

Програму написано мовою С++ у середовищі Visual C++. 

ВИЗНАЧНИК, МІНОР, АЛГЕБРЇЧНЕ ДОПОВНЕННЯ, МАТРИЦЯ, АЛГОРИТМ, ФУНКЦІЇ, ПАРАМЕТРИ, ТИПИ, ОПЕРАТОРИ, ЗАГОЛОВНІ ФАЙЛИ, КРАМЕР, ЗМІННА, ДЕМОНСТРАЦІЙНА ПРОГРАМА.


ЗМІСТ



ВСТУП

1. ВИЗНАЧНИК ТА ЙОГО ВЛАСТИВОСТІ

1.1Визначники другого та третього порядку

1.2 Властивості визначників, теорема розкладання

2. МЕТОД КРАМЕРА

2.1 Теорема Крамера для системи 2 рівнянь із 2 невідомими

2.2 Теорема Крамера для системи 3 рівнянь із 3 невідомими

2.2 Теорема Крамера для системи n рівнянь із n невідомими

3 Програмна реалізація

3.1 Блок схема

3.2 Програма

3.3 Приклад роботи програми 

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ


ВСТУП



	Рішення систем лінійних рівнянь є однієї з важливих обчислювальних задач. Більшість задач обчислювальної практики зводяться до рішення систем лінійних рівнянь. Це задачі з області електротехніки, радіоелектроніки, механіки, статистики. В даній курсовій роботі я описую один із методів рішення систем лінійних рівнянь, а саме метод Крамера. 

Серйозні практичні задачі часто приводять до таких систем, які містять сотні й навіть тисячі лінійних рівнянь. Без допомоги комп'ютера, ці системи вирішити неможливо. Доцільність рішення задачі автоматизованим способом дозволяє скоротити час, витрачений на її рішення в порівнянні з ручним способом, знижується ймовірність допущення помилок, підвищується точність отриманих результатів.

А тому у даній курсовій роботі я представив програму, написану мовою С++, за допомогою якої ми можемо вирішити систему лінійних рівнянь.


1. ВИЗНАЧНИК ТА ЙОГО ВЛАСТИВОСТІ



	Перед тим, як розглядати теорему Крамера необхідно визначити, що називають визначником. Також навести його властивості, та поняття, які стосуються визначника. 



1.1.Визначники другого та третього порядку 



Розглянемо таблицю із чотирьох чисел виду 







Числа в таблиці мають по два індекси. Перший індекс вказує номер рядка, другий - номер стовпця. 

Визначником першого порядку називають вираження виду:



 		(1.1)



Числа а11, …, а22 називають елементами визначника.

Діагональ, утворена елементами а11; а22 називається головною, а діагональ, утворена елементами а12; а21 - побічною.

Таким чином, визначник першого порядку дорівнює різниці добутків елементів головної й побічної діагоналей.

Помітимо, що у відповіді виходить число.

Наприклад. Обчислити:






Визначником третього порядку називається вираження виду:



 (1.2)



Елементи а11; а22; а33 – утворять головну діагональ.

Числа а13; а22; а31 – утворять побічну діагональ.

Зобразимо, схематично, як утворяться доданки із плюсом і з мінусом: 



 

" + " " – "  

Рис.1.1.утворення доданків



Із плюсом входять: добуток елементів на головній діагоналі, інші два доданки є добутком елементів, розташованих у вершинах трикутників з основами, паралельними головній діагоналі.

Доданки з мінусом утворяться по тій же схемі відносно побічної діагоналі.

Це правило обчислення визначника третього порядку називають правилом трикутників.

Наприклад. Обчислити за правилом трикутників: 







	1.2 Властивості визначників, теорема розкладання

	

Наведені далі властивості виконуються для визначників будь-якого порядку. Всі вони можуть бути доведені безпосередньою перевіркою, заснованої на правилах обчислення визначників.

Властивість 1. Величина визначника не зміниться, якщо його рядки поміняти місцями з відповідними стовпцями.



. (1.3)



Розкриваючи обидва визначники, переконуємося у справедливості рівності.

Властивість 1 установлює рівноправність рядків і стовпців визначника. Тому всі подальші властивості визначника будемо формулювати й для рядків і для стовпців.

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



. (1.4)



Властивість 3. Загальний множник елементів рядка (або стовпця) можна виносити за знак визначника.



. (1.5)



Властивість 4. Якщо визначник має два однакові рядки (або стовпця), то він дорівнює	нулю. 



 (1.6)



Це властивість можна довести безпосередньою перевіркою, а можна використати властивість 2. 

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



 = -   2  = 0   = 0



Властивість 5. Якщо всі елементи якогось рядка (або стовпця) дорівнюють нулю, то визначник дорівнює нулю.

Це властивість можна розглядати як окремий випадок властивості 3 при k = 0 

Властивість 6. Якщо елементи двох рядків (або стовпців) визначника пропорційні, то визначник дорівнює нулю.



. (1.7)



Можна довести безпосередньою перевіркою або з використанням властивостей 3 і 4.

Властивість 7. Величина визначника не зміниться, якщо до елементів якого-небудь рядка (або стовпця) додати відповідні елементи іншого рядка (або стовпця), помножені на те саме число.



. (1.8)



Доводиться безпосередньою перевіркою.

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

Для подальшого нам знадобиться поняття мінору й алгебраїчного доповнення.

Мінором даного елемента визначника третього порядку називається визначник другого порядку, отриманий з даного викреслюванням рядка й стовпця, на перетині яких знаходиться даний елемент.

Мінор елемента аi j позначається Мi j . Так для елемента а11 мінор 


 (1.9)



Він вийде, якщо у визначнику третього порядку викреслити перший рядок і перший стовпець.

Алгебраїчним доповненням елемента визначника називають його мінор, помножений на (-1)k , де k - сума номерів рядка й стовпця, на перетині яких знаходиться даний елемент.

Алгебраїчне доповнення елемента аi j позначається Аi j.

Таким чином, Аi j = .

Випишемо алгебраїчні доповнення для елементів а11 і а12.



. (1.10)

. (1.11)



Корисно запам'ятати правило: алгебраїчне доповнення елемента визначника дорівнює його мінору зі знаком плюс, якщо сума номерів рядка й стовпця, у яких стоїть елемент, парна, і зі знаком мінус, якщо ця сума непарна.



Наприклад. Знайти мінори й алгебраїчні доповнення для елементів першого рядка визначника:





Мінори:



Алгебраїчні доповнення:





Ясно, що мінори й алгебраїчні доповнення можуть відрізнятися тільки знаком.

Розглянемо без доказу важливу теорему – теорему розкладання визначника.

Згідно, якій визначник дорівнює сумі добутків елементів якого-небудь рядка або стовпця на їхні алгебраїчні доповнення.

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

. (1.12)



У розгорнутому виді:



. (1.13)



Останню формулу можна використати як основну при обчисленні визначника третього порядку.

Теорема розкладання дозволяє звести обчислення визначника третього порядку до обчислення трьох визначників другого порядку.

Рекомендується розкладати визначник по тому рядку або стовпцю, де є нулі, тому що для нульових елементів не треба знаходити алгебраїчні доповнення.

Теорема розкладання дає другий спосіб обчислення визначників третього порядку.

Наприклад. Обчислити визначник, використовуючи теорему розкладання.







Теорема розкладання дозволяє також обчислювати визначники більше високого порядку, зводячи їх до обчислення декількох визначників третього або другого порядку.

Так, визначник четвертого порядку можна звести до обчислення чотирьох визначників третього порядку.


2.МЕТОД КРАМЕРА



Метод Крамера (Крамера правило) - спосіб рішення систем лінійних алгебраїчних рівнянь із ненульовим визначником основної матриці (причому для таких рівнянь рішення існує і єдино). Створений Габріелем Крамером в 1750 році.



2.1 Теорема Крамера для системи 2 рівнянь із 2 невідомими 



Розглянемо систему двох лінійних рівнянь із двома невідомими.



 	(2.1)	



Тут х1, х2 – невідомі;

а11, …, а22 – коефіцієнти при невідомих, занумерованими двома індексами, де перший індекс означає номер рівняння, а другий індекс – номер невідомого.

b1, b2 – вільні члени.

Нагадаємо, що під рішенням системи розуміється пара значень х1, х2, які при підстановці в обоє рівнянь обертають їх у вірні рівності.

У випадку, коли система має єдине рішення, це рішення можна знайти за допомогою визначників другого порядку.

Визначник, складений з коефіцієнтів при невідомих, називається визначником системи.

Позначимо визначник системи .



 = . (2.2)

У стовпцях визначника  стоять коефіцієнти відповідно при х1 і при, х2.

Уведемо два додаткових визначника, які утворюються із визначника системи заміною одного зі стовпців стовпцем вільних членів:



1 =  2 = . (2.3)



Тепер розглянемо теорему Крамера (для випадку n = 3)

Якщо визначник  системи відмінний від нуля (  0), то система має єдине рішення, що перебуває по формулах: 



 				 (2.4)



Дані формули називаються формулами Крамера.

Наприклад. Вирішити систему за правилом Крамера.







. 



Відповідь: х1 = 3; х2 = -1


2.2 Теорема Крамера для системи 3 рівнянь із 3 невідомими 



Розглянемо систему трьох лінійних рівнянь із трьома невідомими:



 		(2.5)



У випадку єдиного рішення систему можна вирішити за допомогою визначників третього порядку.

Визначник системимає вигляд:



 (2.6)



Уведемо три додаткових визначники: 



. (2.7)



Аналогічно формулюється теорема.

Якщо визначник  системи відмінний від нуля, то система має єдине рішення, що перебуває по формулах:



 (2.8)


Дані формули є формули Крамера.



2.3 Теорема Крамера для системи n рівнянь із n невідомими 



Розглянемо систему n лінійних рівнянь із n невідомими



 (2.9)



Якщо головний визначник системи



 (2.10)



то єдине рішення системи записується у вигляді: 



 (2.11)

	

	Ми i-й стовпець матриці системи заміняється стовпцем вільних членів.

Наприклад:






Визначники:





	



Помітимо, що теорема Крамера застосовна, коли число рівнянь дорівнює числу невідомих і коли визначник системи  відмінний від нуля.

Якщо визначник системи дорівнює нулю, то в цьому випадку система може або не мати рішень, або мати незліченну множину рішень.

	
3 ПРОГРАМНА РЕАЛІЗАЦІЯ



3.1 Блок схема прогами





Ввести матрицю Аij 

   початок

Ввести матрицю Bij 

Kramer (A,B)

кінець

	3.2.Програма

	

	#include <iostream.h>

	#include <math.h>

	

		 double funk1( int z);

		 	double ma_x[100][100];

			 double vol_ch[100];

			double matrix1[100][100];

			double ma_666x[100][100];

			double GL_V_viz;

			double	Viz_d;

			double otveti[100];

			double X;

			 int g,j;

			 double Deter;

	void main (void)

	{

		cout <<" vvedi ckolko y tebia yravneniy v cicteme ";

		int n;

		cin >> n;

		while ( n > 4 ||n < 1)

	 {

	 cout<<"Vu ne mogete vvesti bol'she 4 ili men'she 2 uravneniya, vvedite esche raz ";

	 cin>>n;

	 }

	//ведення кофіцієнтів при невідомих

		int k,m;

	 for ( k =1; k <=n;k++){

			for( m=1; m <=n; m++){

				cout << "Vvedite koficient a [ "<<k<<","<<m<<" ]";

				cin >> ma_666x[k-1][m-1];}}

	//ведення вільного члена

		 for (k=1;k<=n;k++){

				cout<<"Vedite volniy chlen [ "<<k<<" ]";

				cin >>vol_ch[k-1];}

	//якщо 4 рівнянь системи з 4 невідомими

		 if(n==4){

	 cout<<"MATRICA GOLOV-GO VIZ-KA"<<endl;

	 for(int m=0;m<=3;m++){

	 			 cout<<" "<<ma_666x[m][0]<<" "<<ma_666x[m][1]<<" "<<ma_666x[m][2]<<" "<<ma_666x[m][3]<<endl;}

	//знаходимо визначник склавши усі добутки коефіцієнтів на їх алгебраїчне доповнення

		 for (k=0;k<=n-1;k++){ 

	

			 for(int e6=0;e6<=3;e6++){

	 for( g=0;g<=3;g++){

				 ma_x[e6][g]=ma_666x[e6][g];}}

	

		GL_V_viz +=ma_x[1][k] *pow(-1,k+1) * funk1(k); }

	 		 

		 cout<<"GOLOVNIY VIZNACHNIC ="<<GL_V_viz<<endl;

	 cout<<"................................................"<<endl;

		 if(GL_V_viz==0){cout<<"Net resheniy!\n";} 

	//далі знаходимо додаткові визначники і одразу ж невідомі системи

		 if(GL_V_viz!=0){

	 

	 k=0;//k - e ctovpci

		 do	

			 { 

	 for(m=0;m<=3;m++){

	 for( g=0;g<=3;g++){

				 ma_x[m][g]=ma_666x[m][g];}}

	 //підставим у Кий стовпець основої матриці стовпець із вольних членів, утворивши додаткові визначники.

	 for (m=0;m<=3;m++ ){ 

					 ma_x[m][k]=vol_ch[m];} 

		 Viz_d=0;

			/* dali cherez rozkladennia 

		 po 2 riadky znaidem dodatkov viz-k*/

				 for ( m=0;m<=n-1;m++ ){

			Viz_d+= ma_x[1][m]*pow(-1,m+1)*funk1(m);

						 }

		

		cout<<"VIZNACHNIC DODATKOVIY"<<k+1<<"="<< Viz_d<<endl;

			 

				X=Viz_d/GL_V_viz;

				 			 otveti[k]=X;

	

	 cout<<"................................................."<<endl;

				 k++;

			 }

			 while (k<=3);}

		 }

		 else

		 {

		 

	//при 3 ьох рівнянь з 3 невідомими

		 if(n==3)

	

		 {

	//головний визначник

	 for(int e6=0;e6<=2;e6++){

	 for( g=0;g<=2;g++){

			matrix1[e6][g]=ma_666x[e6][g];}}

		 int u;

		 u=666;

		 GL_V_viz=funk1(u);

		cout<<"GOLOVNIY VIZNACHNIC ="<<GL_V_viz<<endl;

	 if(GL_V_viz==0){cout<<"Net resheniy!\n";}

	// додаткові визначники та одразу ж невідомі системи

	

		if(GL_V_viz!=0){

		 k=0;

		 do

		 {

			 for(int e6=0;e6<=2;e6++){

	 for( g=0;g<=2;g++){

			matrix1[e6][g]=ma_666x[e6][g];}}

		 

		 for (m=0;m<=2;m++ ){ 

					 matrix1[m][k]=vol_ch[m];} 

	

	 Viz_d=funk1(u);

	

	 	X=Viz_d/GL_V_viz;

		 otveti[k]=X;

	 	 k++;

		 }

		 while(k<=2);}

	 	 }

		 

		 else{ 

	//при 2 рівнянь з 2 невідомими

	// головний визначник

			 if(n==2)

	 GL_V_viz= ma_666x[0][0]*ma_666x[1][1]-ma_666x[0][1]*ma_666x[1][0];

	 

			 cout<<"GOLOVNIY VIZNACHNIC ="<<GL_V_viz<<endl;

	 

			 if(GL_V_viz==0){cout<<"Net resheniy!\n";}

	// додаткові визначники та одразу ж невідомі системи

			 if(GL_V_viz!=0){

			 k=0;

			 do

		 {

			 for(int e6=0;e6<=1;e6++){

	 for( g=0;g<=1;g++){

			matrix1[e6][g]=ma_666x[e6][g];}}

		 

		 for (m=0;m<=1;m++ ){ 

					 matrix1[m][k]=vol_ch[m];} 

	 Viz_d=matrix1[0][0]*matrix1[1][1]-matrix1[0][1]*matrix1[1][0];;

	 	X=Viz_d/GL_V_viz;

		 otveti[k]=X;

	 	 k++;

		 }

		 while(k<=1);}

	 	 } 

	 

	}

	// для виведення відповіді на екран

		 if(GL_V_viz!=0){

	 cout<<"OTVET: ";

		 for ( m=0;m<=n-2;m++ ){

		 

			 cout<<"X"<<m+1<<"= "<<otveti[m]<<", ";

			 }

		 cout<<"X"<<n<<"= "<<otveti[n-1]<<"."<<endl;}

	 

				 }

	 //функція що утримує нову матрицю, викреслюючи деякий z-ий стовпець та 2 рядок. А потім підраховує визначник нової матриці уже 3 порядку

	 double funk1( int z)

				 {

	// тут функція отримує нову матрицю 3 порядку з матриці 4 го

	

					 if(z!=666)	{

		 for(int e=0;e<1;e++){

	 for( g=0;g<z;g++){

			 matrix1[e][g]=ma_x[e][g];

		 }}

		 for(e=0;e<1;e++){

		 for(g=z+1;g<=3;g++){

			 matrix1[e][g-1]=ma_x[e][g];

			 }}

	

	 for(e=2;e<=3;e++){

			 for(g=0;g<z;g++){

				matrix1[e-1][g]=ma_x[e][g];

			 

					 				 }}

	 for (e=2;e<=3;e++){

		 for(g=z+1;g<=3;g++){

			 matrix1[e-1][g-1]=ma_x[e][g];

				 					}}

					 }

	 //тут рахує визначник отриманої 3 порядку

	//a11a22a33 +a12a23a31 +a13a21a32 -a13a22a31 -a11a23a32 -a12a21a33 

			 		 Deter=matrix1[0][0]*matrix1[1][1]*matrix1[2][2]+matrix1[0][1]*matrix1[1][2]*matrix1[2][0]

	

				 +matrix1[0][2]*matrix1[1][0]*matrix1[2][1]-matrix1[0][2]*matrix1[1][1]*matrix1[2][0]

	

				 -matrix1[0][0]*matrix1[1][2]*matrix1[2][1]-matrix1[0][1]*matrix1[1][0]*matrix1[2][2];

			 

	

			 return Deter;

				 }

	
3.2 Приклад роботи програми

	






СПИСОК ЛІТЕРАТУРИ



Апатенок Р.Ф. Елементи лінійної алгебри й аналітичної геометрії.Мінськ: вища школа,1977 р. - 257 с.

Глушаков С.В. і ін. Мова програмування С++. -харків: Фоліо, 2002. - 500 с. 

ДЕРЖСТАНДАРТ 19.701-90. ЕСПД. Схеми алгоритмів, програм, даних і систем. Умовні позначки й правила виконання.- М.: 1991.

Дейтел Х.М. Дейтел П.Дж. Як програмувати на С++: Пер. с англ. - М.: ЗАТ “Видавництво БІНОМ”, 2000 р. - 1024 с.: іл.

Страуструп Б. Мова програмування С++. Частина 1. - Київ: "Диасофт", 1993. - 264 с.

Страуструп Б. Мова програмування С++. Частина 2. - Київ: "Диасофт", 1993. - 296 с.

Холзнер С. VISUAL C++6: навчальний курс - Спб: Видавництво “ Пітер”, 2000. -576 с.