Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОД ГАУССА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
Кафедра Захист інформації
З В І Т
До лабораторної роботи №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 для розв’язування систем лінійних алгебраїчних рівнянь.методом Гаусса з вибором головного елемента матриці.
16.01.2013 12:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора