Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОД ГАУССА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2007
Тип роботи:
Інструкція та методичні настанови
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОД ГАУССА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
Інструкція
до лабораторної роботи № 2
з курсу
"Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № ___ від __________.
Львів – 2007
Метод Гаусса для розв’язування систем лінійних алгебраїчних рівнянь: Інструкція до лабораторної роботи №2 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем " для студентів спеціальності 6.1601 "Інформаційна безпека" / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М.Іванюк - Львів: НУЛП, 2007.- 14 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Віталій Миколайович Іванюк , асистент.
Відповідальний за випуск: І.Я. Тишик, ст.в.
Рецензент: В.В. Хома, д.т.н., проф.,
В.М. Максимович, к.т.н., доц.
.
Мета роботи – ознайомлення з прямими методами розв’язування систем лінійних алгебраїчних рівнянь.
Методи розв’язування систем лінійних алгебраїчних рівнянь
EMBED Equation.3
Ці методи поділяються на дві групи : прямі та ітераційні.
1) Прямі методи зводяться до скінчених алгоритмів для обчислення коренів рівнянь (тобто розв’язки шукають за певними формулами). Вони дають розв’язки після виконання відомого для даного n (n – порядок) числа арифметичних операцій.
Іншими словами, прямим методом розв’язування лінійної системи EMBED Equation.3 називають будь-який метод, котрий дозволяє знайти елементи вектора EMBED Equation.3 з допомогою скінченого числа елементарних математичних операцій: додавання, віднімання, ділення, множення, та, можливо, кореня квадратного.
Оцінити ефективність будь-якого методу можна за допомогою двох – трьох важливих характеристик:
числа операцій, необхідних для реалізації даного методу;
об’єму пам’яті;
чутливості до переносу похибок заокруглення (або обчислювальної стійкості).
Практично всі прямі методи розв’язування систем базуються на зведені матриці А до матриці більш простішої структури – діагональної (тоді розв’язок очевидний) або трикутної – та методів розв’язування таких систем.
До групи прямих методів розв’язування систем лінійних алгебраїчних рівнянь належать:
– метод Гаусса та його різновиди:
а) класичний метод Гаусса із зведенням матриці А до верхньої трикутної матриці і одержанням розв’язків з допомогою обернених підстановок. Число операцій (вартість методу) – EMBED Equation.3 операцій сумування, множення та EMBED Equation.3 операцій ділення (можна ними знехтувати в порівнянні з EMBED Equation.3 ).
б) метод Гаусса з вибором головного елемента (частковим або повним). Число арифметичних операцій при цьому складає ~ EMBED Equation.3 сумувань та ~ EMBED Equation.3 множень.
Саме цим визначається повна вартість методу, оскільки вартість розв’язку вже самої трикутної системи незначна в порівнянні з вартістю зведення матриці до трикутного вигляду.
– LU-розклад (lower-upper –нижній-верхній)
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Якщо використовувати алгоритм Краута, то число операцій складе EMBED Equation.3 .
З точки зору об’єму обчислень методу LU- розкладу еквівалентний методу Гаусса з частковим вибором головного елемента; його переваги – це можливість роботи з різними векторами вільних членів EMBED Equation.3 та з транспонованими матрицями EMBED Equation.3 (рівняння EMBED Equation.3 – розв’язок знаходиться за тим же LU-розкладом).
– метод Халецького (схема).
При розкладі симетричних матриць можна зменшити число операцій і об’єм пам’яті. Повна вартість складає половині вартості методу Гаусса + n обчислень квадратного кореня. Метод чисельно стійкий.
– метод Жордана (роблять діагональну матрицю замість трикутної). Досить рідко використовується на практиці.
До прямих методів відносяться також методи для кліткових та розріджених матриць.
2) Ітераційні (або наближені) методи – це методи послідовних наближень. В них необхідно задати деякий наближений розв’язок – так зване початкове наближення. Після цього з допомогою деякого алгоритму проводиться один цикл обчислень, котрий називається ітерацією. В результаті ітерації знаходять нове наближення. Ітерації проводять до тих пір, доки не одержать розв’язок із заданою похибкою. Об’єм обчислень при цьому наперед не відомий.
Чому виникла потреба в ітераційних методах? Чим не влаштовують прямі методи?
Основний недолік прямих методів – це нагромадження похибок в процесі розв’язування, оскільки обчислення на будь-якому етапі використовують результати (з похибками) попередніх операцій. Це особливо небезпечно для великих систем ( EMBED Equation.3 і більше) – наростає число операцій, а також для погано обумовлених систем ( EMBED Equation.3 ) (малі похибки обчислень або вхідних даних можуть породити значні похибки в розв’язку). Тому прямі методи використовують для відносно невеликих ( EMBED Equation.3 ) систем з густо заповненою матрицею та EMBED Equation.3 .
Перевагою ітераційних методів над прямими є те, що окремі похибки, що виникають при обчисленнях, не впливають на кінцевий результат (ітерації закінчуються тільки тоді, коли одержано розв’язок із наперед заданою точністю), а ведуть лише до збільшення числа необхідних ітерацій.
Крім того, розв’язування систем ітераційними методами спрощується ще й тому, що на кожній ітерації розв’язується система з одними і тими ж матрицями.
До ітераційних належить: метод простої ітерації, метод Зейделя, метод верхньої релаксації, та інші.
Прямі методи розв’язування систем лінійних алгебраїчних рівнянь
Класичний метод Гаусса.
Розглянемо систему рівнянь четвертого порядку:
EMBED Equation.3
EMBED Equation.3 (1)
Зауважимо, що елементи вектора-стовпчика вільних членів EMBED Equation.3 занесені в матрицю коефіцієнтів А.
Будемо вважати, що EMBED Equation.3 . З першого рівняння знаходимо х1:
EMBED Equation.3 , (2)
де EMBED Equation.3 , EMBED Equation.3 .
З допомогою рівняння (2) можна виключити EMBED Equation.3 з решти рівнянь, для чого достатньо підставити (2) для EMBED Equation.3 в друге, третє і четверте рівняння системи. Це і є першим кроком – кроком виключення невідомого EMBED Equation.3 .
EMBED Equation.3
EMBED Equation.3 , EMBED Equation.3
Перехід від початкової системи
EMBED Equation.3
до новоствореної
EMBED Equation.3
відбувається за такою формулою:
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
Другий крок – виключення невідомого EMBED Equation.3 відбувається аналогічно:
EMBED Equation.3
EMBED Equation.3 EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
Третій крок – виключення невідомого EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 , EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 ; EMBED Equation.3
Останнє рівняння можна переписати у вигляді:
EMBED Equation.3 або EMBED Equation.3 .
Отже, в результаті прямого ходу одержимо систему рівнянь:
EMBED Equation.3
Знаходження невідомих проводиться в оберненому ході методу Гаусса шляхом зворотніх підстановок.
Якщо п – кількість рівнянь (порядок) системи, то програмування обчислювального процесу проводиться так:
L – кількість кроків виключення ;
j – позначення другого індексу при визначенні α ;
і – номер рядка системи ;
k – номер стовпця.
Можна записати, що для всіх
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора