Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2007
Тип роботи:
Інструкція та методичні настанови
Предмет:
Комп’ютерні методи дослідження інформаційних процесів та систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
Інструкція
до лабораторної роботи № 3
з курсу
" Комп’ютерні методи дослідження інформаційних процесів та систем "
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № __ від __________ p.
Львів – 2007
Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь: Інструкція до лабораторної роботи №3 з курсу " Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека " / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М. Іванюк - Львів: НУЛП, 2007.- 12 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Віталій Миколайович Іванюк, асистент
Відповідальний за випуск: І.Я. Тишик, ст.викл.
Рецензент: В.В.Хома, д.т.н., проф..
В.М.Максимович, к.т.н., доц.
Мета роботи – ознайомлення з ітераційними методами розв’язування систем лінійних алгебраїчних рівнянь.
Ітераційні методи розв’язування систем лінійних
алгебраїчних рівнянь EMBED Equation.3
До ітераційних методів належать: метод простої ітерації, метод Зейделя, метод верхньої релаксації та інші.
Метод простої ітерації.
Нехай дано лінійну систему
EMBED Equation.3 (1)
Розглянемо матриці
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
Тоді систему (1) можна записати у вигляді матричного рівняння
EMBED Equation.3 (2)
Будемо вважати, що діагональні коефіцієнти EMBED Equation.3 (і = 1, 2,…, n).
Розв’яжемо перше рівняння системи (1) відносно EMBED Equation.3 , друге відносно EMBED Equation.3 і т.д. Тоді одержимо еквівалентну систему
EMBED Equation.3 (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
Іноді кажуть, що система (3) зведена до нормального вигляду.
Введемо матриці та
EMBED Equation.3 EMBED Equation.3
Систему (3) запишемо у вигляді
EMBED Equation.3 (4)
Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів EMBED Equation.3 . Далі послідовно будуємо матриці-стовпці:
EMBED Equation.3 – перше наближення
EMBED Equation.3 – друге наближення і т.д.
Будь-яке (k + 1)-е наближення обчислюється за формулою:
EMBED Equation.3 , (k = 0, 1, 2, …) (5)
В розгорнутому вигляді EMBED Equation.3 .
Якщо послідовність наближень EMBED Equation.3 має границю
EMBED Equation.3 , (6)
то ця границя є розв’язком системи (3).
На практиці ітераційний процес припиняють, коли EMBED Equation.3 , де – гранична абсолютна похибка.
Приклад. Розв’язати систему методом простої ітерації:
EMBED Equation.3 .
Зведемо систему до нормального вигляду
EMBED Equation.3 (7)
або в матричній формі
EMBED Equation.3 (8)
За нульові наближення коренів системи приймаємо
EMBED Equation.3 .
Підставляємо ці значення в праві частини рівняння (7). Одержимо перші наближення коренів
EMBED Equation.3
Далі знаходимо другі і треті наближення коренів
EMBED Equation.3
EMBED Equation.3
Умови збіжності ітераційного процесу
Нехай задано зведена до нормального вигляду система лінійних рівнянь
EMBED Equation.3
Умова збіжності: якщо сума модулів елементів рядків або модулів елементів стовпців матриці α менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень.
Для системи
EMBED Equation.3
або EMBED Equation.3 ,
де EMBED Equation.3 – сума модулів по стовпцях
EMBED Equation.3
Аналогічно можна було б перевірити виконання умови збіжності, беручи суми модулів елементів рядків.
Наведена вище умова являється достатньою, але не необхідною. Це означає, що якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним.
Для системи лінійних рівнянь, заданих у вигляді
EMBED Equation.3 ,
метод простої ітерації збігається, якщо модулі діагональних коефіцієнтів EMBED Equation.3 для кожного рівняння системи більші, ніж суми модулів всієї решти коефіцієнтів (не враховуючи вільних членів).
Приклад:
EMBED Equation.3 (9)
EMBED Equation.3 (10)
EMBED Equation.3 (11)
Дещо простішій програмній реалізації піддається наступна формула методу простих ітерацій:
EMBED Equation.3 (13)
Звідки вона береться? Відомо, що при зведенні системи EMBED Equation.3 до вигляду EMBED Equation.3 кожне EMBED Equation.3 представляється у вигляді
EMBED Equation.3 або EMBED Equation.3 EMBED Equation.3 .
Якщо зняти обмеження j i, то цю формулу можна переписати у такому вигляді
EMBED Equation.3 .
Звідси випливає, що
EMBED Equation.3 .
Метод Зейделя
Є система лінійних алгебраїчних рівнянь, що зведена до нормального вигляду
EMBED Equation.3 .
Тоді за методом Зейделя, вибираючи вектор початкових наближень
EMBED Equation.3
(як правило, це стовпець вільних членів EMBED Equation.3 ), уточнення значень невідомих проводять наступним чином:
1) перше наближення:
EMBED Equation.3
2) k + 1 наближення
EMBED Equation.3
k = 0, 1, 2, … .
Таким чином ітераційний процес подібний до методу простих ітерацій, однак уточнені значення EMBED Equation.3 одразу ж підставляються в наступні рівняння:
EMBED Equation.3 – метод Зейделя.
Іншими словами, метод Зейделя відрізняється від методу простої ітерації тим, що при обчисленні EMBED Equation.3 на “k+1”-му кроці враховуються значення 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 .
2.ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ
Розв’язати систему лінійних алгебраїчних рівнянь методами простої ітерації або Зейделя.
EMBED Equation.3
EMBED Equation.3 , EMBED Equation.3
EMBED Equation.3 EMBED Equation.3
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.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора