МЕТОД ГАУССА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ. Звіт до лабораторної роботи з Комп’ютерні методи дослідження інформаційних процесів та систем . Робота № 518522

МЕТОД ГАУССА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКТА

Факультет:

Не вказано

Кафедра:

Захист інформації

Інформація про роботу

Рік:

2013

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Комп’ютерні методи дослідження інформаційних процесів та систем

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІКТА Кафедра Захист інформації З В І Т До лабораторної роботи №2 з курсу: „ Комп’ютерні методи дослідження інформаційних процесів та систем ” на тему: „ МЕТОД ГАУССА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ” Варіант 18 Львів – 2010 Мета роботи - ознайомлення з прямими методами розв’язування систем лінійних алгебраїчних рівнянь. Короткі теоретичні відомості Методи розв’язування систем лінійних алгебраїчних рівнянь поділяються на дві групи : прямі та ітераційні. 1) Прямі методи зводяться до скінчених алгоритмів для обчислення коренів рівнянь (тобто розв’язки шукають за певними формулами). Вони дають розв’язки після виконання відомого для даного n (n – порядок) числа арифметичних операцій. Іншими словами, прямим методом розв’язування лінійної системи називають будь-який метод, котрий дозволяє знайти елементи вектора з допомогою скінченого числа елементарних математичних операцій: додавання, віднімання, ділення, множення, та, можливо, кореня квадратного. Оцінити ефективність будь-якого методу можна за допомогою двох – трьох важливих характеристик: числа операцій, необхідних для реалізації даного методу; об’єму пам’яті; чутливості до переносу похибок заокруглення (або обчислювальної стійкості). Практично всі прямі методи розв’язування систем базуються на зведені матриці А до матриці більш простішої структури – діагональної (тоді розв’язок очевидний) або трикутної – та методів розв’язування таких систем. До групи прямих методів розв’язування систем лінійних алгебраїчних рівнянь належать: – метод Гаусса та його різновиди: а) класичний метод Гаусса із зведенням матриці А до верхньої трикутної матриці і одержанням розв’язків з допомогою обернених підстановок. Число операцій (вартість методу) – операцій сумування, множення та операцій ділення (можна ними знехтувати в порівнянні з ). б) метод Гаусса з вибором головного елемента (частковим або повним). Число арифметичних операцій при цьому складає ~ сумувань та ~ множень. Саме цим визначається повна вартість методу, оскільки вартість розв’язку вже самої трикутної системи незначна в порівнянні з вартістю зведення матриці до трикутного вигляду. – LU-розклад (lower-upper –нижній-верхній) Якщо використовувати алгоритм Краута, то число операцій складе . З точки зору об’єму обчислень методу LU- розкладу еквівалентний методу Гаусса з частковим вибором головного елемента; його переваги – це можливість роботи з різними векторами вільних членів та з транспонованими матрицями (рівняння – розв’язок знаходиться за тим же LU-розкладом). – метод Халецького (схема). При розкладі симетричних матриць можна зменшити число операцій і об’єм пам’яті. Повна вартість складає половині вартості методу Гаусса + n обчислень квадратного кореня. Метод чисельно стійкий. – метод Жордана (роблять діагональну матрицю замість трикутної). Досить рідко використовується на практиці. До прямих методів відносяться також методи для кліткових та розріджених матриць. 2) Ітераційні (або наближені) методи – це методи послідовних наближень. В них необхідно задати деякий наближений розв’язок – так зване початкове наближення. Після цього з допомогою деякого алгоритму проводиться один цикл обчислень, котрий називається ітерацією. В результаті ітерації знаходять нове наближення. Ітерації проводять до тих пір, доки не одержать розв’язок із заданою похибкою. Об’єм обчислень при цьому наперед не відомий. Чому виникла потреба в ітераційних методах? Чим не влаштовують прямі методи? Основний недолік прямих методів – це нагромадження похибок в процесі розв’язування, оскільки обчислення на будь-якому етапі використовують результати (з похибками) попередніх операцій. Це особливо небезпечно для великих систем ( і більше) – наростає число операцій, а також для погано обумовлених систем () (малі похибки обчислень або вхідних даних можуть породити значні похибки в розв’язку). Тому прямі методи використовують для відносно невеликих () систем з густо заповненою матрицею та . Метод Гаусса з вибором головного елемента. Запишемо розширену прямокутну матрицю коефіцієнтів системи з рівнянь. Серед елементів матриці вибираємо найбільший за модулем елемент, який називається головним елементом. Нехай ним буде . Рядок з номером називається головним рядком. Обчислюємо множники для всіх . Далі перетворюємо матрицю наступним чином: з кожного го неголовного рядка віднімаємо почленно головний рядок, домножений на . Отримаємо матрицю, у якої всі елементи го стовпця за винятком , дорівнюють нулю. Відкидаючи цей стовпець і головний рядок, отримуємо нову матрицю з меншою на одиницю кількістю рядків та стовпців. Над матрицею повторюємо такі ж дії й тримаємо матрицю і т.д. Ці перетворення продовжуємо доки не отримаємо матрицю, що містить один рядок з двох елементів, який вважаємо головним. Об’єднаємо всі головні рядки починаючи з останнього. Після перестановки вони утворять трикутну матрицю, еквівалентну початковій матриці . Цей етап називають прямим ходом обчислень. Розв’язавши систему з отриманою трикутною матрицею коефіцієнтів, знайдемо послідовно невідомі . Цей етап обчислень називають зворотним ходом. Усі описані обчислення провадять аналогічно до методу Гауса. Сенс вибирання головного елемента полягає в тому, щоб зробити як найменшими числа і завдяки цьому зменшити похибку обчислень. Завдання Розв’язати систему лінійних алгебраїчних рівнянь методом Гаусса. S=0.2*k, k=3; b=0.2*p, p=1. Список індентифікаторів, змінних, функцій, використаних у блок-схемі алгоритму і програмі, та їх пояснення Math – клас, в якому визначено стандартні математичні функції; double – тип з плаваючою точкою подвійної точності; if-else - умовний оператор; Main() – головна функція; Abs (x)- повертає абсолютне значення x; this – змінна, яка посилається на даний об’єкт класу чи структури; for-оператор покрокового циклу; public – модифікатор доступу, члени якого доступні з будь-якого місця програми ; private - модифікатор доступу, члени доступні лише з поточного класу ; int – тип з 32-бітовим цілим числом з знаком. Текст програми using System; using System.Collections.Generic; using System.Data; namespace кмд2 { public class GaussSolutionNotFound : Exception { public GaussSolutionNotFound(string msg) : base("Розв'язок не може бути знайдено: \r\n" + msg) { } } public class LinearSystem { private double[,] initial_a_matrix; private double[,] a_matrix; private double[] x_vector; private double[] initial_b_vector; private double[] b_vector; private double eps; private int size; public LinearSystem(double[,] a_matrix, double[] b_vector) : this(a_matrix, b_vector, 0.0001) { } public LinearSystem(double[,] a_matrix, double[] b_vector, double eps) { if (a_matrix == null || b_vector == null) throw new ArgumentNullException("Один з даних рівне null."); int b_length = b_vector.Length; int a_length = a_matrix.Length; if (a_length != b_length * b_length) throw new ArgumentException(@"Кількість рядків і стовпців в матриці A повинна співпадати с кількістю елементів у векторі B."); this.initial_a_matrix = a_matrix; this.a_matrix = (double[,])a_matrix.Clone(); this.initial_b_vector = b_vector; this.b_vector = (double[])b_vector.Clone(); // this.x_vector = new double[b_length]; this.u_vector = new double[b_length]; this.size = b_length; this.eps = eps; GaussSolve(); } public double[] XVector { get { return x_vector; } } private int[] InitIndex() { int[] index = new int[size]; for (int i = 0; i < index.Length; ++i) index[i] = i; return index; } private double FindR(int row, int[] index) { int max_index = row; double max = a_matrix[row, index[max_index]]; double max_abs = Math.Abs(max); for (int cur_index = row + 1; cur_index < size; ++cur_index) { double cur = a_matrix[row, index[cur_index]]; double cur_abs = Math.Abs(cur); if (cur_abs > max_abs) { max_index = cur_index; max = cur; max_abs = cur_abs; } } if (max_abs < eps) { if (Math.Abs(b_vector[row]) > eps) throw new GaussSolutionNotFound("Система рівнянь несумісна."); else throw new GaussSolutionNotFound("Система рівнянь має безліч розв'язків."); } int temp = index[row]; index[row] = index[max_index]; index[max_index] = temp; return max; } private void GaussSolve() { int[] index = InitIndex(); GaussForwardStroke(index); GaussBackwardStroke(index); GaussDiscrepancy(); } private void GaussForwardStroke(int[] index) { for (int i = 0; i < size; ++i) { double r = FindR(i, index); for (int j = 0; j < size; ++j) a_matrix[i, j] /= r; b_vector[i] /= r; for (int k = i + 1; k < size; ++k) { double p = a_matrix[k, index[i]]; for (int j = i; j < size; ++j) a_matrix[k, index[j]] -= a_matrix[i, index[j]] * p; b_vector[k] -= b_vector[i] * p; a_matrix[k, index[i]] = 0.0; } } } private void GaussBackwardStroke(int[] index) { for (int i = size - 1; i >= 0; --i) { double x_i = b_vector[i]; for (int j = i + 1; j < size; ++j) x_i -= x_vector[index[j]] * a_matrix[i, index[j]]; x_vector[index[i]] = x_i; } } } } Виконання програми / Висновок На цій лабораторній роботі я ознайомився з прямими методами розв’язування систем лінійних алгебраїчних рівнянь. Я склав програму мовою C# у середовищі Windows Forms для розв’язування систем лінійних алгебраїчних рівнянь.методом Гаусса з вибором головного елемента матриці.

Звіт до лабораторної роботи Комп’ютерні методи дослідження інформаційних процесів та систем

proffboss

16.01.2013 12:21

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись