МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Методичні вказівки до лабораторної роботи № 3 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації", 6.170103 "Управління інформаційною безпекою" Затверджено на засіданні кафедри «Безпека інформаційних технологій» Протокол № 12 від 12.05.2011р. Львів – 2011 Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь: Методичні вказівки до лабораторної роботи №3 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації", 6.170103 "Управління інформаційною безпекою" / Укл.: Л.В. Мороз, А.Я. Горпенюк, Н.М. Лужецька - Львів: Видавництво НУ“ЛП”, 2011..- 12 с. Укладачі: Л.В. Мороз, к.т.н., доц. А.Я. Горпенюк, к.т.н., доц. Н.М. Лужецька, асист. Відповідальний за випуск: В.М. Максимович, д.т.н., проф. Рецензент: В.В. Хома, д.т.н., проф. А.Е. Лагун, к.т.н., доц., Мета роботи – ознайомлення з ітераційними методами розв’язування систем лінійних алгебраїчних рівнянь. Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь До ітераційних методів належать: метод простої ітерації, метод Зейделя, метод верхньої релаксації та інші. Метод простої ітерації. Нехай задано лінійну систему (1) Розглянемо матриці
Тоді систему (1) можна записати у вигляді матричного рівняння (2) Будемо вважати, що діагональні коефіцієнти (і = 1, 2,…, n). Розв’яжемо перше рівняння системи (1) відносно , друге відносно і т.д. Тоді одержимо еквівалентну систему (3) де , при ; , при ; ; ; Кажуть, що система (3) зведена до нормального вигляду. Введемо матриці ( та (
Систему (3) запишемо у вигляді (4) Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів . Далі послідовно будуємо матриці-стовпці наступних наближень розв’язку системи (4): – перше наближення – друге наближення і т.д. Будь-яке (k + 1)-е наближення обчислюється за формулою: , (k = 0, 1, 2, …) (5) В розгорнутому вигляді . Якщо послідовність наближень має границю , (6) то ця границя є розв’язком системи (3). На практиці ітераційний процес припиняють, коли , де ( – гранична абсолютна похибка. Приклад. Розв’язати систему методом простої ітерації: . Зведемо систему до нормального вигляду (7) або в матричній формі (8) За нульові наближення коренів системи приймаємо вектор вільних членів: . Підставляємо ці значення в праві частини системи (7). Одержимо перші наближення коренів
Далі знаходимо другі і треті наближення коренів
Умови збіжності ітераційного процесу Нехай задано зведена до нормального вигляду система лінійних рівнянь
Умова збіжності: якщо сума модулів елементів рядків або модулів елементів стовпців матриці ? менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень. Наприклад задано систему:
Зведена до нормального виду система:
Матриця заданої системи:
Cума модулів коефіцієнтів по стовпцях:
Таким чином умова збіжності ітераційного процесу для заданої системи виконується. Аналогічно можна було б перевірити виконання умови збіжності, беручи суми модулів елементів рядків матриці . Наведена вище умова є достатньою, але не є необхідною. Це означає, що якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним. Для системи лінійних рівнянь, заданих у вигляді (2) умова збіжності ітераційного методу формулюється так. Ітераційний метод розв’язування системи (2) збігається, якщо модулі діагональних коефіцієнтів для кожного рівняння системи більші, ніж суми модулів всієї решти коефіцієнтів даного рівняння (не враховуючи вільних членів). Приклад: Умова збіжності: (9) Задана система: (10) Перевірка умови: (11) У випадку, якщо для заданої системи умова збіжності не виконується і ітераційний процес методу є розбіжним, необхідно добитися виконання умови збіжності шляхом лінійних перетворень заданої системи (перестановка рядків, стовпців матриці коефіцієнтів, домноження рівнянь на деякий коефіцієнт, додавання, віднімання рівнянь, тощо). Дещо простішій програмній реалізації піддається наступна формула методу простих ітерацій: (12) Звідки вона береться? Відомо, що при зведенні системи до вигляду кожне представляється у вигляді або . Якщо зняти обмеження j ( i, то цю формулу можна переписати у такому вигляді . Звідси випливає, що . Метод Зейделя Задано систему лінійних алгебраїчних рівнянь, що зведена до нормального вигляду . Тоді за методом Зейделя, вибираючи вектор початкових наближень
(як правило, це стовпець вільних членів ), уточнення значень невідомих проводять наступним чином: 1) перше наближення:
2) k + 1 наближення
k = 0, 1, 2, … . Таким чином ітераційний процес подібний до методу простих ітерацій, однак уточнені значення одразу ж підставляються в наступні рівняння: – формула методу Зейделя. Іншими словами, метод Зейделя відрізняється від методу простої ітерації тим, що при обчисленні на “k+1”-му кроці враховуються значення , , , обчислені на цьому самому кроці. З метою економії пам’яті при програмуванні методу Зейделя недоцільно напряму застосовувати подану формулу методу. На відміну від методу простої ітерації в методі Зейделя немає необхідності зберігати в пам’яті повністю вектор попередніх наближень розв’язку. Можна застосовувати один вектор, в якому будуть зберігатися останні наближення розв’язків. При цьому для контролю умови завершення ітераційного процесу по кожному з розв’язків можна застосовувати одну й ту саму допоміжну змінну для тимчасового зберігання попереднього наближення чергового розв’язку. Слід сподіватись, що ітерації за методом Зейделя дадуть при тому ж числі кроків більш точні результати, ніж за методом простої ітерації. Або така ж точність буде досягнута за менше число кроків, оскільки чергові значення невідомих визначаються тут більш точно ітераційний процес припиняється. Наприклад, якщо задано систему
для якої точний розв’язок
Обчислення проведемо згідно формул: . За початкове наближення вибираємо вектор
Результати обчислень наведемо в таблиці: Ітерації Метод простої ітерації Метод Зейделя
Достатні умови збіжності ітераційного методу Зейделя для всіх і якщо хоча б для одного і ця нерівність строга . 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. Який з методів забезпечує більш точні результати і чому?
СПИСОК ЛІТЕРАТУРИ Корн Г., Корн Т. Справочник по математике для инженеров и научных работников. – М.: Наука, 1974. – 830 с. Маликов В.Т., Кветный Р.Н. Вычислительные методы и применение ЭВМ: Учеб. пособие. – Киев: Выща шк., Головное изд-во, 1989. – 213 с. Щуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 1982. – 235 с. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. – М.: Мир, 1998. –570 с. 5. Джон Г. Мэтьюз, Куртис Д. Финк Численные методы. Использование Matlab. Издательский дом «Вильямс» Москва – Санкт-Петербург – Киев, 2001.
НАВЧАЛЬНЕ ВИДАННЯ ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Методичні вказівки до лабораторної роботи № 3 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації", 6.170103 "Управління інформаційною безпекою" Укладачі: Мороз Леонід Васильович Горпенюк Андрій Ярославович Лужецька Наталія Миколаївна Редактор Комп’ютерне верстання
