МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
Кафедра інформатики
КУРСОВА РОБОТА
Тема: «Рішення системи лінійних рівнянь модифікованим методом Гауса (метод головних елементів), Холецького, методом простих ітерацій і методом Зейделя. Порівняння методів.»
з дисципліни «Програмування»
ПОЯСНЮВАЛЬНА ЗАПИСКА
Керівник Руденко Д.О.
(підпис) (прізвище, ініціали)
Кобилін О.А.
(підпис) (прізвище, ініціали)
Яковлева О.В.
(підпис) (прізвище, ініціали)
Студентка гр. Москвіна О.Л.
КІУКІу-22-2 (підпис) (прізвище, ініціали)
Харків 2023
РЕФЕРАТ
Записка пояснювальна до курсової роботи: 26 с., 19 рисункiв, 2 таблицi, 4 розділи, 2 додатка.
Мета роботи – необхідно реалізувати інтерфейс для знаходження коротшого шляху на графі, чиї ребра вводяться з клавіатури. Результат повинен відображатися на екрані.
Метод вирішення задачі - використання алгоритмів Дейкстри, Беллмана-Форда, Флойда-Воршелла, та Джонсона.
Розроблено програму, яка шукає найкоротший шлях у графі за допомогою алгоритмів Дейкстри, Беллмана-Форда, Флойда-Воршелла, Джонсона.
Програму складено мовою C++ у середовищі програмування Vіsual C++.
МЕТОД ГАУСА, МЕТОД ХОЛЕЦЬКОГО, МЕТОД ПРОСТИХ ІТЕРАЦІЙ, МЕТОД ЗЕЙДЕЛЯ, ПОРІВНЯННЯ
ЗМІСТ
ВСТУП 4
2 ТЕОРЕТИЧНА ЧАСТИНА 7
2.1 Метод Гауса (метод головних елементів) 7
2.2 Метод Холецького 9
2.3 Метод простих ітерацій 11
2.4 Метод Зейделя 13
3 ПРОГРАМНА РЕАЛІЗАЦІЯ 15
3.1 Опис використовуваних бібліотек 15
3.2 Опис розроблених функцій 15
3.3 Інтерфейс користувача 15
4. ІНСТРУКЦІЯ КОРИСТУВАЧА 17
ВИСНОВКИ 19
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 20
ДОДАТОК А 21
ВСТУП
Досягнення сучасної елементної бази відкрило нові можливості для розвитку високопродуктивних обчислювальних систем. Це досягається завдяки розпаралелюванню обчислювального процесу. Збільшення обчислювальної потужності мотивується в основному числовими моделюваннями складних систем для таких прикладних областей, як: передбачення погоди, клімату, та глобальних змін в атмосфері; структурна біологія; генетика людини; астрономія; розпізнавання та синтез мови; розпізнавання зображень. Незважаючи на належність названих задач до різних предметних областей і розходження в прийнятих способах опису явищ і термінологій, методи розв’язання їх на ЕОМ подібні [1-6]. Необхідними, як правило, є алгоритми формування матриць спеціального виду, об’єднання, переформування матриць і виконання певного набору алгебраїчних операцій, зокрема, розв’язання систем лінійних алгебраїчних рівнянь (СЛАР). Тому розробка високопродуктивних спеціалізованих процесорів для розв’язання матричних задач лінійної алгебри, зокрема, розв’язання СЛАР високих порядків в реальному часі, є актуальною
1 ПОСТАНОВКА ЗАДАЧІ
Рішення систем лінійних рівнянь алгебри – одне з основних завдань обчислювальної лінійної алгебри. Хоча завдання рішення системи лінійних рівнянь порівняно рідко представляє самостійний інтерес для додатків, від уміння ефективно вирішувати такі системи часто залежить сама можливість математичного моделювання найрізноманітніших процесів із застосуванням ЕОМ. Значна частина чисельних методів рішення різних (особливо – нелінійних) задач включає рішення систем лінійних рівнянь як елементарний крок відповідного алгоритму.
Одна з труднощів практичного рішення систем великої розмірності зв’язана з обмеженістю оперативної пам'яті ЕОМ. Хоча об’єм оперативної пам'яті новостворюваних обчислювальних машин росте дуже швидко, проте, ще швидше зростають потреби практики в рішенні завдань все більшій розмірності. В значній мірі обмеження на розмірність вирішуваних систем можна зняти, якщо використовувати для зберігання матриці зовнішні пристрої, що запам'ятовують. Проте в цьому випадку багато разів зростають як витрати машинного часу, так і складність відповідних алгоритмів. Тому при створенні обчислювальних алгоритмів лінійної алгебри велику увагу приділяють способам компактного розміщення елементів матриць в пам'яті ЕОМ.
На щастя, додатки дуже часто приводять до матриць, в яких число ненульових елементів багато менше загального числа елементів матриці. Такі матриці прийнято називати розрідженими. Одним з основних джерел розріджених матриць є математичні моделі технічних пристроїв, що складаються з великого числа елементів, зв'язки між якими локальні. Прості приклади таких пристроїв – складні будівельні конструкції і великі електричні ланцюги.
Відомі приклади вирішених останніми роками задач, де число невідомих досягало сотень тисяч. Природно, це було б неможливо, якби відповідні матриці не були розрідженими (матриця системи з 100 тис. рівнянь у форматі подвійної точності зайняла б близько 75 Гбайт).
2 ТЕОРЕТИЧНА ЧАСТИНА
2.1 Метод Гауса (метод головних елементів)
Стандартний метод Гауса може стати чисельно нестійким, якщо серед діагональних елементів
(головний елемент), на які проводиться ділення, виявляються дуже малі, по абсолютній величині, числа, хоча і відмінні від нуля (не говорячи вже про нульові значення).Тоді при діленні на них отримуються великі числа з великими абсолютними погрішностями. В результаті цього, отриманий розв’язок сильно відрізнятиметься від дійсного розв’язку, тобто метод Гауса буде нестійким до помилок обчислень.
Щоб цього уникнути, на практиці застосовують метод виключення Гауса з вибором головного елемента. Якщо головний елемент
, по абсолютній величині, близький до нуля, то у відповідному 
-му стовпці можна знайти максимальний за модулем елемент і переставити рядки місцями так, щоб цей елемент став головним.Але така перестановка теж не завжди забезпечує стійкість. Тому при програмній реалізації, зазвичай, вибирають максимальний за модулем елемент не в
-му стовпці, а в усій матриці, що залишилася.Потрібно зазначити, що якщо доводиться переставляти місцями стовпці матриці, то ці перестановки потрібно запам’ятовувати, а потім (після отримання розв’язку) проводити їх у зворотному порядку вже у векторі отриманого розв’язку.
Сенс вибору головного елемента полягає в тому, щоб зробити якомога меншими, по абсолютній величині, числа
та 
і, тим самим, зменшити погрішність обчислень та округлень.Тому, для реалізації методу Гауса на комп’ютері, зазвичай, використовують саме схему з вибором головного елемента.
Нехай дана система лінійних рівнянь виду (1), для якої потрібно знайти чисельний розв’язок:
Рисунок 2.1.1 – Система лінійних рівнянь
Розглянемо розширену прямокутну матрицю, що складається з коєфіціентів системи (1) та її вільних членів:
Рисунок 2.1.2 – Розширена прямокутна матриця
Для даної матриці, згідно з алгоритмом методу Гауса з вибором головного елемента, виберемо ненульовий, як правило, найбільший за модулем елемент, який не належить стовпцю вільних членів, тобто .
Нехай це буде елемент
(даний елемент, як уже зазначалося вище, називають головним елементом).Далі, для кожного рядка матриці (2), крім рядка під номером
,обчислюємо множники:
Рисунок 2.1.3 – Формула множника
На наступному кроці виконуємо наступні дії: до кожного неголовного рядка розширеної матриці (2) додаємо головний рядок (
-й рядок матриці 
) помножений на відповідний для нього множник 
:
Рисунок 2.1.4 – Додавання головного рядку
В результаті отримаємо нову матрицю,
-й стовпець якої складається з нульових елементів.Викреслюючи даний стовпець і
-й (головний) рядок, отримаємо матрицю 
, яка складається з меншого на одиницю числа рядків та стовпців.Над матрицею
повторюємо ті ж операції, після чого отримаємо деяку матрицю 
. Продовжуючи обчислювальний процес далі, отримуємо послідовність матриць 
, остання з яких є матрицею-рядком, яка складається з двох елементів. Відмітимо, що даний рядок також вважатиметься головним.Для визначення невідомих
, об’єднуємо в систему, починаючи з останнього, який входить в матрицю 
, всі головні рядки. Далі провівши відповідну перестановку рядків, отримаємо систему з трикутною матрицею, за допомогою якої, знаходимо розв’язок системи рівнянь (1).Зауваження: метод виключення Гауса з вибором головного елемента застосовується для систем лінійних рівнянь, головний визначник яких являється відмінним від нуля.
2.2 Метод Холецького
Нехай потрібно вирішити систему лінійних рівнянь алгебри
з симетричною позитивно визначеною матрицею А. Лінійні системи такого типу часто зустрічаються в додатках (наприклад, задач оптимізації, при вирішенні рівнянь математичної фізики та ін). Для їх вирішення часто застосовується метод Холецького (інша назва — метод квадратного коріння). [7]В основі методу лежить алгоритм побудови спеціального LU-розкладання матриці А, внаслідок чого вона наводиться до вигляду
Рисунок 2.2.1 – спеціальний LU-розклад матриці А
У розкладанні (5.64) нижня трикутна матриця
Рисунок 2.2.2 – Розкладання нижньої матриці
Вже не обов’язково повинна мати на головній діагоналі одиниці, як це було в методі Гауса, а потрібно лише, щоб діагональні елементи були позитивними.
Якщо розкладання (5.64) отримано, то рішення системи (5.63) зводиться до послідовного вирішення двох систем із трикутними матрицями:
Рисунок 2.2.3 – Розкладання матриці
Для вирішення систем (5.66) потрібно виконання приблизно арифметичних операцій.
Знайдемо елементи матриці. Для цього обчислимо елементи матриці та прирівняємо їх відповідним елементам матриці А. В результаті отримаємо систему рівнянь
Рисунок 2.2.4 – Знаходження елементів матриці
Вирішуючи систему (5.67), послідовно знаходимо
Рисунок 2.2.5 – Послідовне знаходження
Зауважимо, що з обчислення діагональних елементів використовується операція вилучення квадратного кореня. Тому метод Холецького називають ще й методом квадратного коріння. Доведено, що позитивність відповідних підкорених виразів наслідком позитивної визначеності матриці А.
2.3 Метод простих ітерацій
Для використання методу простих ітерацій (послідовних наближень) замінимо рівняння еквівалентним йому рівнянням. [8]
(1.1)Рисунок 2.3.1 – Перша формула
Виберемо деяке наближення кореня і підставимо його у праву частину рівняння (1.1). Одержимо. Далі обчислюємо за формулою:
(1.2)Рисунок 2.3.2 – Друга формула
Отримуємо послідовність наближень {} до кореня, що у випадку її збіжності до кореня може дати наближене його значення із заданою точністю . Необхідною і достатньою умовою існування границі послідовності є вимога: такий, що . З цієї причини шукаємо наближення (ітерації), які б задовольняли вищезазначену умову.
Рисунок 2.3.3 – Ілюстрація методу простих ітерацій
Перейти від рівняння до еквівалентного йому можна багатьма способами. Але оптимальним є той, що задовольнить достатню умову збіжності методу простої ітерації .
При виконанні умови збіжності за початкове наближення можна взяти довільне значення з інтервалу
2.4 Метод Зейделя
Метод Зейделя представляє собою модифікацію методу ітерації, основна ідея якого полягає в тому, що при обчисленні
-го наближення невідомої , враховуються вже обчислені -ші наближення невідомих 
.[9]Одним з плюсів методу є те, що він дає кращу збіжність ніж метод простої ітерації, а недоліком є більш громіздкий процес обчислень.
Зазначимо, що метод Зейделя може збігатися навіть у тому випадку, коли процес ітерації розбіжний. Однак це буває не завжди.
Бувають також випадки, коли процес Зейделя збігається повільніше від процесу простої ітерації. Більше того, бувають випадки, коли процес ітерації збігається, а процес Зейделя розбіжний.
Нехай дано систему лінійних рівнянь виду:
Рисунок 2.3.4 – Система лінійних рівнянь
Довільним чином, виберемо початкові наближення розв’язку
, намагаючись, щоб вони якоюсь мірою відповідали шуканим невідомим 
/Далі, припускаючи, що
-те наближення коренів
відоме, відповідно до методу Зейделя, будемо шукати -ше наближення за наступними формулами:
Рисунок 2.3.5 – Формули для розрахунку
Ітераційний процес методу Зейделя необхідно продовжувати до тих пір, поки не буде виконуватись умова
, де 
задана точність обчислювального процесу.Зауваження: умова, що стосується збіжності ітераційного процесу методу простої ітерації залишається актуальною і для ітерації методом Зейделя.
3 ПРОГРАМНА РЕАЛІЗАЦІЯ
3.1 Опис використовуваних бібліотек
iostream – iostream означає стандартний потік введення-виведення. Цей файл заголовка містить визначення таких об’єктів, як cin, cout, cerr тощо.
cmath – (math.h) заголовний файл стандартної бібліотеки мови програмування, розроблений для виконання простих математичних операцій. Більшість функцій залучають використання чисел із плаваючою точкою. C++ також реалізує дані функції для забезпечення сумісності, всі вони містяться в заголовному файлі cmath.
3.2 Опис розроблених функцій
vector
vector
vector
vector
3.3 Інтерфейс користувача
Для зручності користування програмою було розроблено користувацький інтерфейс.
Рисунок 3.4.1 – інтерфейс програми
Реалізована можливість обирання пункту меню за допомогою цифр від 1 до 3. Спочатку за допомогою функції cin зчитуємо введену цифру, далі аналізуємо введення і в залежності від нього виконуємо дію. Якщо натиснути клавішу, дія на яку не призначена, то користувач після вводу графа отримує повідомлення про помилку та має спробу обрати дію ще раз.
Рисунок 3.4.2 – помилка при спробі вибору невірної дії
4. ІНСТРУКЦІЯ КОРИСТУВАЧА
1. Запустити програму;
2. Обрати алгоритм пошуку в меню за допомогою клавіш від 1 до 3, де 1 – метод Гауса, 2 – метод Холецького, 3 – Метод Зейделя;
Рисунок 4.1 – Зустрiчальний інтерфейс програми Пошук графа
3. Наступним кроком треба через пробіл ввести матрицю;
Рисунок 4.2 – Меню обирання дiї
4. Збільшена матриця;
Рисунок 4.3 – Введена матриця
5. Після збільшеної матриці на екран буде виведено корені.
Рисунок 4.5 – Матриця найкоротших шляхів
6. Після того, як буде отримано результат, буде змога продовжити (1) чи припинити (0) роботу;
Рисунок 4.6 – Меню вибору
7. Після вибору продовження роботи (y) буде надано початкове меню (рисунок 4.1), після обрання припинення роботи (n) програма завершується.
ВИСНОВКИ
У процесі виконання роботи було реалізовано завдання з вирішення системи лінійних рівнянь. Під час підготовки були проведені досліди роботи щодо рішення матриць СЛАУ-методами. Реалізовано програму мовою C++ для знаходження шляху у графі та розроблено інтерфейс для зручної роботи з програмою.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
[1] Демидович Г.Е., Марон Г.А. Основы вычислительной математики. – М.: Наука, 1970. – 664с.
[2] Пухов Г.Е. и др. Вычислительные устройства на скаляторах. – Киев: Техніка, 1983. – 144с.
[3] Гофман М.А. Многоканальний поиск информации в некогерентных оптических системах памяти // Автометрия. – 1976. – №6. –С.48-54.
[4] Колфилд Дж. и др. Оптические нейронные сети // ТИИЭР. – Т.77. – №10. –1989. – С.193-202.
[5] Кожемяко В.П., Красиленко В.Г., Заболотная Н.И., Билык В.И. Анализ быстродействующих цифрових методов и устройств вычисления площадей бинарных дискретизированых изображений // В кн.: Оптоелектронные методы и средства обработки информации. – Винница, 1988. – С.50-54.
[6] Райс Дж. Матричные вычисления и математическое обеспечение. – М.: Мир, 1984. – 264 с
[7] https://scask.ru/i_book_clm.php?id=46
[8] https://vuzlit.com/858448/metod_prostih_iteratsiy
[9] https://www.mathros.net.ua/nablyzhene-rozvjazannja-systemy-linijnyh-rivnjan-metodom-zejdelja.html
ДОДАТОК А
Текст програми
#include
#include
using namespace std;
#define M 10
void Seiden(int n, int flag) {
int count = 0;
double** a = new double* [n];
for (int i = 0; i < n; i++) {
a[i] = new double[n + 1];
}
double* x = new double[n];
double eps, y;
cout << "\nEnter the elements of the augmented matrix row-wise:\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n; j++) {
cin >> a[i][j];
}
}
eps = 0.0001;
for (int i = 0; i < n; i++)
for (int k = i + 1; k < n; k++)
if (abs(a[i][i]) < abs(a[k][i]))
for (int j = 0; j <= n; j++)
{
double temp = a[i][j];
a[i][j] = a[k][j];
a[k][j] = temp;
}
do
{
for (int i = 0; i < n; i++)
{
y = x[i];
x[i] = a[i][n];
for (int j = 0; j < n; j++)
{
if (j != i)
x[i] = x[i] - a[i][j] * x[j];
}
x[i] = x[i] / a[i][i];
if (abs(x[i] - y) <= eps)
flag++;
}
count++;
} while (flag < n);
cout << "\nThe solution is as follows:\n";
for (int i = 0; i < n; i++) {
cout << "x" << i << " = " << x[i] << endl;
}
}
void PrintMatrix(float a[][M], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n; j++)
cout << a[i][j] << " ";
cout << endl;
}
cout << endl;
}
int PerformOperation(float a[][M], int n)
{
int i, j, k = 0, c, flag = 0, m = 0;
float pro = 0;
for (i = 0; i < n; i++)
{
if (a[i][i] == 0)
{
c = 1;
while ((i + c) < n && a[i + c][i] == 0)
c++;
if ((i + c) == n) {
flag = 1;
break;
}
for (j = i, k = 0; k <= n; k++)
swap(a[j][k], a[j + c][k]);
}
for (j = 0; j < n; j++) {
if (i != j) {
float pro = a[j][i] / a[i][i];
for (k = 0; k <= n; k++)
a[j][k] = a[j][k] - (a[i][k]) * pro;
}
}
}
return flag;
}
void PrintResult(float a[][M], int n, int flag)
{
cout << "Result is : " << endl;
if (flag == 2)
cout << "Infinite Solutions Exists" << endl;
else if (flag == 3)
cout << "No Solution Exists" << endl;
else {
for (int i = 0; i < n; i++) {
cout << "x" << i << " = " << a[i][n] / a[i][i] << endl;
}
cout << endl;
}
}
int CheckConsistency(float a[][M], int n, int flag)
{
int i, j;
float sum;
flag = 3;
for (i = 0; i < n; i++)
{
sum = 0;
for (j = 0; j < n; j++)
sum = sum + a[i][j];
if (sum == a[i][j])
flag = 2;
}
return flag;
}
void menu() {
bool run = true;
while (run) {
int choice_metod;
char y_n;
float a[M][M];
int n, flag = 0;
try_choice:
cout << "1) Gauss method" << endl;
cout << "2) Halet method" << endl;
cout << "3) Seiden method" << endl;
cout << "Choice method: ";
cin >> choice_metod;
switch (choice_metod)
{
case 1:
cout << "Enter matrix size: ";
cin >> n;
cout << "Enter matrix values:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n + 1; j++) {
cin >> a[i][j];
}
}
flag = PerformOperation(a, n);
if (flag == 1) {
flag = CheckConsistency(a, n, flag);
}
cout << "Final Augmented Matrix is : " << endl;
PrintMatrix(a, n);
cout << endl;
PrintResult(a, n, flag);
break;
case 2:
cout << "Halet method" << endl;
break;
case 3:
cout << "Enter matrix size: ";
cin >> n;
Seiden(n, 0);
break;
default:
goto try_choice;
break;
}
cout << "Continue? [y/n]: ";
cin >> y_n;
if (y_n == 'y' || y_n == 'Y') {
goto try_choice;
}
else if (y_n == 'n' || y_n == 'N') {
run = false;
}
else {
run = false;
}
}
}
int main()
{
menu();
}