МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" МЕТОД ГАУССА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Інструкція до лабораторної роботи № 2 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека" Затверджено на засіданні кафедри «Захист інформації» Протокол № ___ від __________. Львів – 2007 Метод Гаусса для розв’язування систем лінійних алгебраїчних рівнянь: Інструкція до лабораторної роботи №2 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем " для студентів спеціальності 6.1601 "Інформаційна безпека" / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М.Іванюк - Львів: НУЛП, 2007.- 14 с. Укладачі: Леонід Васильович Мороз, к.т.н., доц. Зеновій Михайлович Стрілецький, к.т.н., доц. Віталій Миколайович Іванюк , асистент. Відповідальний за випуск: І.Я. Тишик, ст.в. Рецензент: В.В. Хома, д.т.н., проф., В.М. Максимович, к.т.н., доц. . Мета роботи – ознайомлення з прямими методами розв’язування систем лінійних алгебраїчних рівнянь. Методи розв’язування систем лінійних алгебраїчних рівнянь
Ці методи поділяються на дві групи : прямі та ітераційні. 1) Прямі методи зводяться до скінчених алгоритмів для обчислення коренів рівнянь (тобто розв’язки шукають за певними формулами). Вони дають розв’язки після виконання відомого для даного n (n – порядок) числа арифметичних операцій. Іншими словами, прямим методом розв’язування лінійної системи називають будь-який метод, котрий дозволяє знайти елементи вектора з допомогою скінченого числа елементарних математичних операцій: додавання, віднімання, ділення, множення, та, можливо, кореня квадратного. Оцінити ефективність будь-якого методу можна за допомогою двох – трьох важливих характеристик: числа операцій, необхідних для реалізації даного методу; об’єму пам’яті; чутливості до переносу похибок заокруглення (або обчислювальної стійкості). Практично всі прямі методи розв’язування систем базуються на зведені матриці А до матриці більш простішої структури – діагональної (тоді розв’язок очевидний) або трикутної – та методів розв’язування таких систем. До групи прямих методів розв’язування систем лінійних алгебраїчних рівнянь належать: – метод Гаусса та його різновиди: а) класичний метод Гаусса із зведенням матриці А до верхньої трикутної матриці і одержанням розв’язків з допомогою обернених підстановок. Число операцій (вартість методу) – операцій сумування, множення та операцій ділення (можна ними знехтувати в порівнянні з ). б) метод Гаусса з вибором головного елемента (частковим або повним). Число арифметичних операцій при цьому складає ~ сумувань та ~ множень. Саме цим визначається повна вартість методу, оскільки вартість розв’язку вже самої трикутної системи незначна в порівнянні з вартістю зведення матриці до трикутного вигляду. – LU-розклад (lower-upper –нижній-верхній)
Якщо використовувати алгоритм Краута, то число операцій складе . З точки зору об’єму обчислень методу LU- розкладу еквівалентний методу Гаусса з частковим вибором головного елемента; його переваги – це можливість роботи з різними векторами вільних членів та з транспонованими матрицями (рівняння – розв’язок знаходиться за тим же LU-розкладом). – метод Халецького (схема). При розкладі симетричних матриць можна зменшити число операцій і об’єм пам’яті. Повна вартість складає половині вартості методу Гаусса + n обчислень квадратного кореня. Метод чисельно стійкий. – метод Жордана (роблять діагональну матрицю замість трикутної). Досить рідко використовується на практиці. До прямих методів відносяться також методи для кліткових та розріджених матриць. 2) Ітераційні (або наближені) методи – це методи послідовних наближень. В них необхідно задати деякий наближений розв’язок – так зване початкове наближення. Після цього з допомогою деякого алгоритму проводиться один цикл обчислень, котрий називається ітерацією. В результаті ітерації знаходять нове наближення. Ітерації проводять до тих пір, доки не одержать розв’язок із заданою похибкою. Об’єм обчислень при цьому наперед не відомий. Чому виникла потреба в ітераційних методах? Чим не влаштовують прямі методи? Основний недолік прямих методів – це нагромадження похибок в процесі розв’язування, оскільки обчислення на будь-якому етапі використовують результати (з похибками) попередніх операцій. Це особливо небезпечно для великих систем ( і більше) – наростає число операцій, а також для погано обумовлених систем () (малі похибки обчислень або вхідних даних можуть породити значні похибки в розв’язку). Тому прямі методи використовують для відносно невеликих () систем з густо заповненою матрицею та . Перевагою ітераційних методів над прямими є те, що окремі похибки, що виникають при обчисленнях, не впливають на кінцевий результат (ітерації закінчуються тільки тоді, коли одержано розв’язок із наперед заданою точністю), а ведуть лише до збільшення числа необхідних ітерацій. Крім того, розв’язування систем ітераційними методами спрощується ще й тому, що на кожній ітерації розв’язується система з одними і тими ж матрицями. До ітераційних належить: метод простої ітерації, метод Зейделя, метод верхньої релаксації, та інші. Прямі методи розв’язування систем лінійних алгебраїчних рівнянь Класичний метод Гаусса. Розглянемо систему рівнянь четвертого порядку:
(1) Зауважимо, що елементи вектора-стовпчика вільних членів занесені в матрицю коефіцієнтів А. Будемо вважати, що . З першого рівняння знаходимо х1: , (2) де , . З допомогою рівняння (2) можна виключити з решти рівнянь, для чого достатньо підставити (2) для в друге, третє і четверте рівняння системи. Це і є першим кроком – кроком виключення невідомого .
, Перехід від початкової системи
до новоствореної
відбувається за такою формулою:
Другий крок – виключення невідомого відбувається аналогічно:
Третій крок – виключення невідомого
,
; Останнє рівняння можна переписати у вигляді: або . Отже, в результаті прямого ходу одержимо систему рівнянь:
Знаходження невідомих проводиться в оберненому ході методу Гаусса шляхом зворотніх підстановок. Якщо п – кількість рівнянь (порядок) системи, то програмування обчислювального процесу проводиться так: L – кількість кроків виключення ; j – позначення другого індексу при визначенні ? ; і – номер рядка системи ; k – номер стовпця. Можна записати, що для всіх
Обернений хід: , . Отже, обчислювальна схема прямого ходу методу Гаусса має вигляд: Для Для
Для Для
i піддається спрощенню. Початкове обчислення всіх коефіцієнтів ? не є обов’язковим. Це випливає з наступного. Наприклад, перехід від початкової системи коефіцієнтів до наступної відбувається так:
Наприклад, коефіцієнти першого чи другого стовпця нової системи утворюються за правилом , або Отже, визначивши, наприклад ?12 зразу ж можна переходити до визначення коефіцієнтів нової системи і т.п. Таким чином цикли по J i по K можна об’єднати (оскільки, що J i K змінюються в однакових межах). Якщо замінити на та цикли по J та по K об’єднати в один (тобто J на K), то одержимо загальну форму методу виключення Гаусса із стовпцевою формою розкладу матриці А до трикутного вигляду)
В кінці цих перетворень одержимо:
Метод Гаусса (рядкова і стовпцева форми розкладу матриці А до трикутного вигляду). Розглянемо систему лінійних рівнянь (1) з невиродженою матрицею А розміру. Більшу частину всього обчислювального процесу поглинає зведення матриці А до трикутного вигляду. Можливі дві форми розкладу (зведення) матриці А до трикутного вигляду – рядкова або стовпцева. Як ми вже знаємо, стовпцева форма розкладу зображується наступною обчислювальною схемою: Для до Для до (2) Для до
Права частина системи (1) також може оброблятися в ході зведення матриці А до трикутного вигляду. Тому можна приєднати до і-го рядка (член ) – як ми й робили раніше (в такому випадку в циклі "k" верхня межа зростає до ). Можна залишити на місці, не вносячи в масив А. В цьому випадку в результаті виконання (якщо не вносити) прямого ходу методу Гаусса одержується система рівнянь:
. Стовпчикову форму розкладу можна продемонструвати наступним прикладом: Перехід, наприклад, від матриці А початкових коефіцієнтів при невідомих при n=4: (4) до матриці коефіцієнтів після першого етапу перетворень (5) відбувається наступним чином: обчислюються послідовно
; формуються елементи стовпця
; ; . Обернений хід при стовпчиковій формі розкладу описується загальною формулою: , (6) Розглянемо тепер рядкову форму розкладу матриці А. Вона базується на зведенні системи лінійних рівнянь до трикутного вигляду. Для цього спочатку нормують перше рівняння, ділячи його на а11(0), тобто роблять коефіцієнт при х1 рівним 1. Потім це перше рівняння домножують відповідно на коефіцієнт аі,1(0) при х1 всіх інших рівнянь і послідовно віднімають від усієї решти рівнянь. В результаті х1 буде виключене із всіх рівнянь, крім першого. На другому кроці виключають х2 з третього, четвертого, ..., п –го рівнянь. Цю процедуру повторюють до тих пір, доки вся система не буде зведена до такого трикутного вигляду
Рядкова форма зображається наступною обчислювальною схемою: Для до Для до (7) Для до
Тут перехід від матриці (4) до матриці (5) відбувається так:
Тобто, на відміну від стовпчикової форми, обчислення коефіцієнтів нової матриці відбувається по рядках. Результат же одержується той самий. Стовпчикова форма: Рядкова форма: При (обертанні) обчисленні оберненої матриці доцільно використовувати розклад матриці А до трикутного вигляду за рядковою формою. Метод Гаусса з вибором головного елемента. При прямому ході потрібно виконувати ділення на . Якщо в системі лінійних алгебраїчних рівнянь вважати, що аіі = 0, то в цьому випадку метод Гаусса використовувати не можна. Елемент, на який потрібно ділити, називається головним (провідним) або центральним і ділення на нульовий провідний елемент неможливе. Великі похибки заокруглень також виникають тоді, коли головний елемент не дорівнює нулю, але є малим числом. Наприклад, для системи з трьох рівнянь з трьома невідомими:
метод Гаусса дає наступні результати:
(5 значущих цифр), що добре узгоджується з точним розв’язком . Тепер поміняємо місцями друге і третє рівняння системи і знову розв’яжемо її методом Гаусса. В цьому випадку розв’язок буде мати наступний вигляд:
Причина такої відмінності полягає в тому, що в першому випадку після першого етапу провідним елементом є , а в другому (після перестановки) – , що і дає таку розбіжність (при обмеженій розрядності чисел (точності обчислень)). Для усунення такого роду неприємностей проводять вибір головного елементу таким чином – за головний вибирають елемент з максимальним абсолютним значенням. Причому використовують різні варіанти вибору – по рядку, по стовпцю або по всій матриці. Якщо вибір проводиться по стовпцю (наприклад, при ) – то це так званий частковий вибір провідного елемента. Якщо вибирати максимальний елемент з усієї матриці, то такий вибір головного елемента називають повним. 2. ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ Розв’язати систему лінійних алгебраїчних рівнянь методом Гаусса.
2.1. Домашня підготовка до роботи 1. Ознайомитися з основними теоретичними відомостями. 2. Розробити блок-схему алгоритму методу. 3.Написати програму, яка забезпечить розв’язок та виведення на екран результатів роботи. Варіанти завдань беруть за вказівкою викладача. 2.2. Робота в лабораторії 1. Ввести в комп'ютер програму, згідно з отриманим завданням. 2. Здійснити відладку введеної програми, виправивши виявлені компілятором помилки. 3. Виконати програму. Текст відлагодженої програми та отримані результати оформити у звіт з лабораторної роботи. 3. ЗМIСТ ЗВIТУ 1. Мета роботи. 2. Короткі теоретичні відомості. 3. Повний текст завдання. 4. Блок-схему алгоритму програми. 5. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення. 6. Остаточно відлагоджений текст програми згідно з отриманим завданням. 7. Результати виконання програми. 8. Висновок. Контрольні запитання 1 На які групи поділяються методи розв’язування систем лінійних алгебраїчних рівнянь? 2. Параметри оцінки ефективності методів розв’язування систем лінійних алгебраїчних рівнянь. 3. В чому полягає відмінність між ітераційними та Гауссівськими методами розв’язування систем лінійних алгебраїчних рівнянь. Назвіть основні переваги та недоліки. 4. Який з методів дозволяє контролювати точність результату? 5. Назвати основні етапи розв’язування систем лінійних алгебраїчних рівнянь методом Гауссса. 6. Назвати основні етапи розв’язування систем лінійних алгебраїчних рівнянь методом LU – розкладу. Література Корн Г., Корн Т. Справочник по математике для инженеров и научных работников. – М.: Наука, 1974. – 830 с. Маликов В.Т., Кветный Р.Н. Вычислительные методы и применение ЭВМ: Учеб. пособие. – Киев: Выща шк., Головное изд-во, 1989. – 213 с. Щуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 1982. – 235 с. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. – М.: Мир, 1998. –570 с. Джон Г. Мэтьюз, Куртис Д. Финк Чисельнные методы. Использование Matlab. Издательский дом «Вильямс» Москва – Санкт-Петербург – Киев, 2001.
