Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютеризовані системи
Кафедра:
Комп'ютеризовані системи автоматики
Інформація про роботу
Рік:
2007
Тип роботи:
Інші
Предмет:
Комп’ютерні методи дослідження систем керування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
ПРЯМІ ТА ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРИЧНИХ РІВНЯНЬ
Інструкція до лабораторної роботи № 2
з курсу “Комп’ютерні методи дослідження систем керування”
для студентів базового напрямку 6.0914
“Комп’ютеризовані системи, автоматика і управління”
Затверджено
на засiданнi кафедри
“Комп’ютеризовані
системи автоматики»
Протокол № від . .2007
Львів 2007
Прямі та ітераційні методи розв’язування систем лінійних алгебричних рівнянь: Інструкція до лабораторної роботи № 2 з курсу “Комп’ютерні методи дослідження систем керування” для студентів базового напрямку 6.0914 “Комп’ютеризовані системи, автоматика і управління” / Укл.: У.Ю. Дзелендзяк, А.Г. Павельчак, В.В. Самотий – Львів: НУЛП, 2007.- 36 с.
Укладачі: У.Ю. Дзелендзяк, к.т.н., доцент
А.Г. Павельчак, асистент
В.В. Самотий, д.т.н., професор
Відповідальний за випуск
А.Й. Наконечний, д.т.н., професор
Рецензент: , д.т.н., професор
Мета роботи: вивчити найпоширеніші прямі та ітераційні методи розв’язування систем лінійних алгебричних рівнянь та способи їх застосування для обчислення визначників і обертання матриць.
1. Загальна характеристика методів
розв’язування систем лінійних алгебричних рівнянь
До числових методів лінійної алгебри відносяться числові методи розв’язування систем лінійних алгебричних рівнянь, обертання матриць, обчислення визначників та знаходження власних чисел і власних векторів матриць. У цій лабораторній роботі ми детально розглянемо першу задачу та побічно вирішимо другу та третю.
1.1. Системи лінійних рівнянь.
Лінійні системи в обчисленнях відіграють дуже значну роль, оскільки до них може бути приведений наближений розв’язок широкого кола задач. Основними джерелами виникнення систем лінійних алгебричних рівнянь є теорія електричних кіл, рівняння балансів та збереження у механіці, гідравліці тощо.
Система n лінійних рівнянь з n невідомими може бути представлена у такому вигляді:
, (1.1)
або у матричній формі
, (1.2)
де – матриця коефіцієнтів системи (1.1), – вектор невідомих, – вектор вільних членів, які, відповідно, приймають такі значення
, , .
У числових алгоритмах вираз (1.2) переважно записують так
, . (1.3)
Відомо, що якщо визначник матриці рівний нулю, тобто , то система лінійних рівнянь або не має розв’язку, або має їх безмежну кількість. Якщо ж , тоді система має розв’язок, та до того ж єдиний. У подальшому ми будемо розглядати лише останній випадок.
Всі ці випадки є добре геометрично проілюстровані на системі двох рівнянь (рис.1). Кожному рівнянню відповідає пряма у площині x, y, а крапка перетину цих прямих є розв’язком системи. Якщо , то нахили прямих рівні, і вони або паралельні, або співпадають. У іншому випадку прямі мають єдину крапку перетину.
1.2. Види матриць.
Ефективність обчислень у лінійній алгебрі часто залежить від вміння використовувати спеціальну структуру та властивості задіяних матриць.
а) Матриці, більшість елементів яких нулі, називають розрідженими. Одне із визначень розрідженої матриці таке: матриця розміром вважається розрідженою, якщо число її ненульових елементів . Наприклад, при та число ненульових елементів 31622 (загальне число елементів ). Розрідженість матриць є цінною властивістю, оскільки об’єм інформації, який необхідно обробляти та зберігати в пам’яті обчислювальної машини, для таких матриць навіть дуже значного розміру може виявитися не надто великим. Одним із основних джерел розріджених матриць є математичні моделі технічних пристроїв, що складаються із великої кількості елементів з локальними зв’язками. Найпростіший приклад – великі електричні кола. Інше важливе джерело розрідженості – метод кінцевих різниць та метод кінцевих елементів, що використовуються для розв’язування рівнянь математичної фізики.
б) Стрічкові матриці. Багато задач приводять до матриць, які не тільки розріджені, але й мають стрічкову структуру ненульових елементів. Матриця називається стрічковою з напівшириною стрічки рівній , якщо для . Усі ненульові елементи такої матриці розташовані на найближчих до головної діагоналях матриці; число прийнято називати шириною стрічки. Схематично стрічкова матриця представлена на рис. 2. Частковим випадком стрічкової матриці при є трьохдіагональна матриця, яка виникає при розв’язуванні систем лінійних алгебричних рівнянь у задачах побудови інтерполяційних сплайнів, різницевих методах розв’язування крайових задач для диференціальних рівнянь
. (1.4)
в) Важливу роль у числовому аналізі відіграють трикутні матриці. Квадратна матриця називається нижньою трикутною, якщо всі її елементи, що розміщені вище головної діагоналі, рівні нулю ( для ). Якщо ж рівні нулю всі елементи матриці, що розміщені нижче головної діагоналі ( для ), то вона називається верхньою трикутною.
Нижня та верхня трикутні матриці мають відповідно такий вигляд:
, . (1.5)
Трикутні матриці володіють рядом чудових властивостей. Наприклад, для таких матриць визначник легко обчислюється за формулою
. (1.6)
1.3. Методи розв’язування.
Одним з тривіальних методів розв’язування системи лінійних алгебричних рівнянь є метод з використанням зворотної матриці. Насправді, при умові існує зворотна матриця . Домножуючи обидві частини рівняння (1.2) зліва на матрицю , отримуємо
або
. (1.7)
Пошук оберненої матриці здійснюється за формулами Крамера. Однак для великих розмірів матриці такий підхід є достатньо громіздкою операцією і на практиці не використовується. Натомість є розроблено ряд значно ефективніших та простіших методів.
Методи розв’язування систем лінійних алгебричних рівнянь в основному поділяють на дві групи:
а) точні або прямі методи – алгоритми, що дають можливість точно (без округлень) розв’язати систему за скінчене число арифметичних дій (метод Гауса, метод LU-розкладу, метод прогону).
б) ітераційні методи, які дають можливість отримати корені системи з заданою точністю шляхом збіжних нескінченних процесів (метод простої ітерації, метод Зейделя, метод релаксації).
Внаслідок неминучих заокруглень результати навіть точних методів є наближеними, до того ж оцінити похибки коренів у загальному випадку є не просто. При використанні ітераційних процесів, крім цього, добавляється ще й похибка методу. Зазначимо, що ефективне використання ітераційних методів суттєво залежить від вдалого вибору початкового наближення та швидкості збіжності процесу.
Для систем невеликого порядку застосовують, як правило, тільки прямі методи. Ітераційні методи є вигідними для систем спеціального виду з слабо заповненою матрицею дуже високого порядку . Метод прогону використовують для розв’язування важливого класу спеціальних систем лінійних рівнянь з трьохдіагональною матрицею, що виникають у ряді задач.
2. Метод Гауса
Суть методу полягає у послідовному виключенню невідомих, в результаті чого дана система рівнянь перетворюється до еквівалентної системи з верхньою трикутною матрицею, розв’язування якої не представляє труднощів. Розглянемо цей метод детально.
Метод Гауса для розв’язування системи (1.1) полягає у послідовному вилученні невідомих з цієї системи.
Нехай (головний елемент). Поділивши перше рівняння на , отримаємо
, (2.1)
де , .
Розглянемо тепер рівняння системи (1.1), що залишилися
. (2.2)
Почергово, помножимо (2.1) на та отримане рівняння віднімемо з відповідного і-го () рівняння системи (2.2).
У результаті отримаємо таку систему рівнянь
. (2.3)
де , , .
У системі (2.3) невідоме міститься лише у першому рівнянні, тому у подальшому достатньо мати справу з скороченою системою рівнянь:
. (2.4)
У такий спосіб ми здійснили перший крок методу Гауса. Коли (головний елемент другого кроку), то з системи (2.4) аналогічно можна вилучити невідоме і отримати систему, еквівалентну (1.1), з матрицею такої структури:
, (2.5)
де хрестиками позначені ненульові елементи. При цьому перше рівняння системи (2.3) залишається без змін.
Вилучаючи таким ж чином невідомі , остаточно приходимо до системи рівнянь виду
, (2.6)
що еквівалентна початковій системі (1.1).
Матриця цієї системи є верхньою трикутною
. (2.7)
Побудова системи (2.6) складає прямий хід методу Гауса. Зворотний хід полягає у відшукуванні невідомих з систе ми (2.6), починаючи з до . Це здійснити просто, оскільки матриця має трикутний вигляд. Дійсно,
, ...
Загальні форми зворотного ходу мають вигляд
, . (11)
При реалізації на персональному комп’ютерові прямого ходу методу Гауса немає необхідності діяти із змінними . Досить вказати алгоритм, за яким початкова матриця А перетворюється до трикутного вигляду (2.7), та вказати відповідне перетворення правих частин системи.
Загальний алгоритм методу Гауса
для
для
для
для
;
Прямий хід:
для
Оберне-ний хід:
Опис алгоритму
Прямий хід методу. Резервуємо (копіюємо) базові матриці та у відповідні матриці та . Вхідні матриці та нам необхідні для кінцевої перевірки результату. Протягом виконання алгоритму ми працюємо з копіями вхідних матриць.
Далі у трьох циклах виконується перетворення початкової матриці до трикутного вигляду матриці та відповідне перетворення правих частин системи .
Обернений хід. Спершу присвоюємо значення для останнього невідомого , а потім в циклі відшукуємо усі решта невідомі.
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (1.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
3. Метод Гауса з вибором головного елемента
У методі Гауса при обчисленні елементів матриці вимагається ділення на головні елементи , , … , . Якщо ж один з головних елементів рівний нулю, то схему єдиного ділення не можливо реалізувати. І навіть, коли усі головні елементи відмінні від нуля, але серед них є близькі до нуля, то тоді похибки суттєво зростають і не є контрольованими.
3.1. Метод Гауса з вибором головного елемента по стовпцю.
Для того, щоб уникнути ситуації коли головні елементи є рівними або близькими до нуля, здійснюють перестановку рівнянь у системі (1.1) так, щоб на місці головного елемента опинився елемент з найбільшим по модулю значенням. Тобто, на кожному -му кроці методу Гауса переставляють стрічки з номерами таким чином, щоб на місці опинився елемент , найбільший серед усіх у -му стовці при . При цьому, звичайно, переставляють і елементи вектора .
Наприклад, якщо на першому кроці найбільшим елементом у першому стовпці виявиться елемент , то після перестановки місцями першого та -го рівнянь система (1.1) буде такою
. (3.1)
Аналогічно здійснюється і на -му кроці методу Гауса
. (3.2)
При такій схемі часткового вибору головного елемента по стовпцю загальний алгоритм Гауса не змінюється. Необхідно лише на кожному кроці методу здійснювати сортування по головному елементу.
Загальний алгоритм методу Гауса
з вибором головного елемента по стовпцю
для
для
стовпцеві сортування
для
для
;
Прямий хід:
стовпцеві сортування
;
для
якщо {; }
; ;
для
; ;
для
Оберне-ний хід:
Опис алгоритму
Прямий хід методу. Резервуємо (копіюємо) базові матриці та у відповідні матриці та . Вхідні матриці та нам необхідні для кінцевої перевірки результату. Протягом виконання алгоритму ми працюємо з копіями вхідних матриць.
Далі у трьох циклах виконується перетворення початкової матриці до трикутного вигляду матриці та відповідне перетворення правих частин системи . Зазначимо, що на кожному кроці першого циклу по змінній виконуємо процедуру стовпцевого сортування по головним елементам. Тобто, відшукуємо максимальне значення по модулю головного елемента, а потім міняємо місцями рядки у матриці та (копії матриці та ). Змінна визначає номер рядка головного елемента, а використовується як проміжна змінна.
Обернений хід. Спершу присвоюємо значення для останнього невідомого , а потім в циклі відшукуємо усі решта невідомі.
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (1.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
3.2. Метод Гауса з вибором головного елемента по рядку.
При пошуку головного елемента по рядку місцями міняються не рівняння системи (1.1), як при пошуку по стовпцю, а невідомі у всіх рівняннях. Наприклад, на першому кроці методу Гауса серед коефіцієнтів знайдемо максимальний по абсолютному значенню коефіцієнт. Нехай це буде коефіцієнт . Перепишемо систему, переставивши місцями та у всіх рівняннях:
. (3.3)
Від перестановки місцями доданків у рівняннях розв’язок системи не зміниться. На наступному кроці методу Гауса знаходимо максималь ний коефіцієнт серед та знову здійснюємо заміну, і т.д. Після завершення зворотного ходу методу Гауса необхідно знову виконати перестановку , тобто впорядкувати елементи вектора у тому порядку, який був на самому початку.
Загальний алгоритм методу Гауса
з вибором головного елемента по рядку
для
для
для
рядкові сортування
для
для
;
Прямий хід:
рядкові сортування
,
для
якщо {; }
; ;
для
якщо {; ; }
інакше {; ; }
для
Оберне-ний хід:
для
якщо
Впорядку-вання
Опис алгоритму
Задаємо початкові значення вектора . Цей вектор містить інформацію про переміщення невідомих під час вибору головних елементів.
Прямий хід методу. Резервуємо (копіюємо) базові матриці та у відповідні матриці та . Вхідні матриці та нам необхідні для кінцевої перевірки результату. Протягом виконання алгоритму ми працюємо з копіями вхідних матриць.
Далі у трьох циклах виконується перетворення початкової матриці до трикутного вигляду матриці та відповідне перетворення правих частин системи . Зазначимо, що на кожному кроці першого циклу по змінній виконуємо процедуру рядкового сортування по головним елементам. Тобто, відшукуємо максимальне значення по модулю головного елемента, а потім міняємо місцями стовпці у матрицях та (копії матриць та ). Змінна визначає номер рядка головного елемента, змінна використовується як проміжна змінна при заміні значень у елементах матриць та , а як проміжна змінна при заміні значень елементів вектора .
Обернений хід. Спершу присвоюємо значення для останнього невідомого , а потім в циклі відшукуємо усі решта невідомі.
На останньому етапі впорядковуємо значення вектора у тому порядку, який був на самому початку.
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (1.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
3.3. Метод Гауса з вибором головного елемента по всій матриці.
У схемі повного вибору головний елемент шукається по всій матриці
. (3.4)
На першому кроці методу серед елементів визначають максимальний по модулю . Перше рівняння системи та рівняння з номером міняють місцями. Далі переставляють місцями та у всіх рівняннях. Після чого система (3.4) стає такою
. (3.5)
Як бачимо, цей метод об’єднує методи вибору головного елементу по рядку та по стовпцю. Відповідно наш робочий алгоритм методу Гауса з вибором головного елементу по всій матриці буде гібридом двох попередніх методів.
Загальний алгоритм методу Гауса
з вибором головного елемента по всій матриці
для
для
для
матричне сортування
для
для
;
Прямий хід:
матричне сортування
; ;
для
якщо {; ; }
; ;
для
; ;
; ;
для
якщо {; ; }
інакше {; ; }
для
Оберне-ний хід:
для
якщо
Впорядку-вання
Опис алгоритму
Задаємо початкові значення вектора . Цей вектор містить інформацію про переміщення невідомих під час вибору головних елементів.
Прямий хід методу. Резервуємо (копіюємо) базові матриці та у відповідні матриці та . Вхідні матриці та нам необхідні для кінцевої перевірки результату. Протягом виконання алгоритму ми працюємо з копіями вхідних матриць.
Далі у трьох циклах виконується перетворення початкової матриці до трикутного вигляду матриці та відповідне перетворення правих частин системи . Зазначимо, що на кожному кроці першого циклу по змінній виконуємо процедуру матричного сортування по головним елементам. Тобто, відшукуємо максимальне значення по модулю головного елемента, а потім міняємо місцями рядки у матрицях та (копії матриць та ) та здійснюємо заміну стовпців у матриці , щоб головний елемент вийшов на верхнє зліва місце. Змінна та визначають, відповідно, номер стовпця та рядка головного елемента, змінна використовується як проміжна змінна при заміні значень у елементах матриць та , а як проміжна змінна при заміні значень елементів вектора .
Обернений хід. Спершу присвоюємо значення для останнього невідомого , а потім в циклі відшукуємо усі решта невідомі.
На останньому етапі впорядковуємо значення вектора у тому порядку, який був на самому початку.
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (1.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
У схемі повного вибору головного елемента по всій матриці гарантія доброї обумовленості досягається ціною значних затрат на вибір головних елементів. І тому на практиці у більшості випадках перевага віддається все ж таки схемі часткового вибору головного елемента по стовпцю.
4. Застосування методу Гауса для обчислення визначників матриць
Нехай маємо деяку матрицю
. (4.1)
Розглянемо лінійну систему
. (4.2)
При розв’язуванні системи (4.2) методом Гауса (п.2) ми здійснювали заміну матриці трикутною матрицею , що складалася з елементів зазначених стрічок,
. (4.3)
У результаті ми отримували еквівалентну систему
. (4.4)
Елементи матриці послідовно утворювалися з елементів матриці та подальших допоміжних матриць за допомогою таких елементарних перетворень:
ділення на головні елементи , , … , , які передбачалися відмінними від нуля, та
віднімання із рядків матриці та проміжних матриць чисел, що пропорційні елементам відповідних головних стрічок.
При першій операції визначник матриці також ділиться на відповідний головний елемент, при другій – визначник матриці залишається незмінним. Тому
.
Отже
(4.5)
Як бачимо з виразу (4.5), визначник дорівнює добутку головних елементів для відповідної схеми Гауса. До того ж немає потреби здійснювати обчислення для вектора вільних членів та операції зворотного ходу – вистачає лише прямого ходу методу Гауса.
Загальний алгоритм обчислення визначника матриці
простим методом Гауса
для
для
для
;
Прямий хід:
Опис алгоритму
На початку алгоритму змінній , що відповідає за значення визначника, присвоюємо одиницю. Копіюємо матрицю у .
Виконуємо спрощений прямий хід методу Гауса (без обчислень для вектора ). На кожному кроці першого циклу по змінній помножаємо значення визначника на значення головного елементу.
Зазначимо, що якщо будь-який головний елемент чи близький до нуля (тягне за собою зменшення точності обчислень), то необхідно використовувати метод Гауса з вибором головного елемента (повну або часткову схему).
При використанні методу Гауса з вибором головного елемента слід врахувати таку деталь: оскільки величина визначника рівна сумі добутків елементів стовпця (рядка) матриці на
,
де – відповідні мінори (у методі Гауса на кожному кроці прямого ходу у робочому стовпці усі елементи, за винятком першого верхнього, рівні нулю), то слід у формулі (4.5) врахувати знак для кожного головного елемента, який був переміщений з іншого місця матриці.
Загальний алгоритм обчислення визначника матриці
методом Гауса з вибором головного елемента по стовпцю
для
для
стовпцеві сортування
для
;
Прямий хід:
стовпцеві сортування
;
для
якщо {; }
для
; ;
Опис алгоритму
На початку алгоритму змінній , що відповідає за значення визначника, присвоюємо одиницю. Копіюємо матрицю у .
Виконуємо спрощений прямий хід методу Гауса (без обчислень для вектора ). На кожному кроці першого циклу по змінній проводимо спочатку стовпцеві сортування для визначення максимального по модулю значення головного елемента та опісля помножаємо значення визначника на значення головного елементу із коефіцієнтом його місця розташування.
Аналогічно до цього будуються і алгоритми для обчислення визначника матриці на основі методів Гауса з визначенням головного елемента по рядку та по всій матриці. Відрізняються вони лише процедурами сортування.
Загальний алгоритм обчислення визначника матриці
методом Гауса з вибором головного елемента по рядку
для
для
рядкові сортування
для
;
Прямий хід:
рядкові сортування
;
для
якщо {; }
для
якщо {; ; }
інакше {; ; }
Загальний алгоритм обчислення визначника матриці
методом Гауса з вибором головного елемента по всій матриці
для
для
матричне сортування
для
;
Прямий хід:
матричне сортування
; ;
для
якщо {; ; }
для
; ;
для
якщо {; ; }
інакше {; ; }
5. Застосування методу Гауса для обчислення оберненої матриці
Нехай дано неособливу матрицю
. (5.1)
Для знаходження її оберненої матриці
(5.2)
використаємо основне співвідношення
, (5.3)
де – одинична матриця.
Множачи матриці та , будемо мати систем рівнянь відностно невідомих
, , (5.4)
де
.
Проілюструємо формулу (5.4) на прикладі матриці з .
Тепер розіб’ємо на три окремі системи рівнянь
, ,
,
де – матриця коефіцієнтів системи; , , – вектора невідомих; , , – вектора вільних членів (аналогічно вектору системи рівнянь (1.2) ).
Загальний алгоритм обчислення оберненої матриці
методом Гауса
для
якщо {}
інакше {}
для
Метод Гауса
для
для
для
для
;
для
для
Опис алгоритму
Встановлюємо значення для одиничної матриці .
У верхньому циклі по змінній здійснюємо пошук стовпців оберненої матриці шляхом розв’язування систем рівнянь (5.4) методом Гауса. У прямому ході методу Гауса ми замість вектора вільних членів передаємо методу відповідний стовпець одиничної матриці . Після закінчення роботи методу Гауса здійснюємо присвоєння обчислених значень елементів вектора невідомих відповідному стовпцю оберненої матриці .
Виконуємо перевірку алгоритму. Скалярно помножимо матрицю на знайдену їй обернену матрицю . В результаті маємо отримати одиничну матрицю (в межах похибки обчислень).
З метою уникнення ситуації, коли головні елементи можуть бути рівними чи близькими нулю необхідно використовувати метод Гауса з вибором головного елемента. У наведеному вище алгоритмі потрібно лише замінити використаний звичайний метод Гауса на метод із повним чи частковим вибором головного елемента (стр. 9, 11, 13). Єдиною модифікацією для них є лише на початку прямого ходу.
6. Метод LU-розкладу
Алгоритми цього методу є схожими до методу Гауса. Основна перевага методу LU-факторизації у порівнянні з методом Гауса полягає у більш простому отриманні розв’язку для різних векторів системи лінійних алгебричних рівнянь (1.1).
У цьому методі матрицю подають як скалярний добуток двох трикутних матриць та
, (6.1)
де
, .
Запишемо систему (1.2) із врахуванням виразу (6.1)
. (6.2)
Введемо допоміжний вектор як
. (6.3)
Після цього запишемо вираз (6.2) так
. (6.4)
Розв’язок системи (1.2) чи (6.2) відбувається у два етапи: спершу розв’язується система (6.4), а потім (6.3). Така послідовність розв’язування дає перевагу методу (у порівнянні з методом Гауса) при розв’язуванні декілька систем з однаковою матрицею та різними векторами вільних членів , оскільки матриці та залишаються незмінними.
Розв’язування системи (6.4) складає прямий хід методу, а системи (6.3) – обернений хід.
Розглянемо прямий хід. Завдяки спеціальній формі матриці вектор легко обчислюється. Для цього запишемо вираз (6.4) у виді системи рівнянь
. (6.5)
Узагальнені формули для системи (6.5) є такими
; для . (6.6)
При оберненому ході вектор визначається з системи рівнянь (6.3)
. (6.7)
Починаючи з останнього рівняння, можна послідовно знайти елементи вектора . Запишемо узагальнені формули для системи (6.7)
; для . (6.8)
LU-розклад матриці здійснюватимемо методом Краута.
Загальний алгоритм методу LU-розкладу
для
для
для
LU-розклад:
для
Прямий хід:
для
Оберне-ний хід:
Опис алгоритму
Виконуємо розклад матриці на матриці та .
Прямий хід методу. Обчислюємо перший елемент вектора , а потім у циклі відшукуємо усі решта елементи.
Обернений хід методу. Спершу присвоюємо значення для останнього невідомого , а потім в циклі відшукуємо усі решта невідомі.
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (1.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
7. Метод прогону
Метод прогону є простим та ефективним алгоритмом для розв’язування систем лінійних алгебричних рівнянь з трьохдіагональ ними матрицями
(7.1)
Систему (7.1) у загальному випадку записують так:
; ; , (7.2)
Прямий хід прогону (алгоритм прямого ходу методу Гауса).
Кожне невідоме виражається через з допомогою прогонних коефіцієнтів та
, . (7.3)
Наприклад, з першого рівняння системи (7.1) знайдемо
, звідки . (7.4)
З другого рівняння системи (7.3) виразимо через , замінюючи формулою (7.3) або (7.4)
.
Звідси знайдемо
або ,
де , .
Приймаючи, що е2 = а2А1 + b2, запишемо:
.
Аналогічно для кожного -го індексу прогонні коефіцієнти з рівняння (3) мають вигляд:
, , (7.5)
де , .
При цьому враховуючи, що приймаємо
, . (7.6)
В розгорнутому вигляді формула (7.5) буде мати вигляд формули (7.7)
(7.7)
Значення прогонних коефіцієнтів (7.7) можна одержати і таким шляхом. В рівнянні (7.3) понизимо індекс на одиницю та підставимо значення в -те рівняння системи (7.2)
Обернений хід прогону (аналог оберненого ходу методу Гауса).
Він полягає у послідовному обчисленні невідомих . Спочатку знаходять . Для цього формулу (7.7) запишемо при (враховуючи, що )
.
Далі, використовуючи формулу (7.3), знаходимо послідовно усі невідомі .
Для запису коефіцієнтів , та прогонних коефіцієнтів , використовується той самий масив.
Загальний алгоритм методу прогону
для
; ; ;
;
Ініціалі-
зація:
для
; ;
Прямий хід:
для
Оберне-ний хід:
для
Вихідні
дані:
Опис алгоритму
На етапі ініціалізації ми копіюємо вхідні дані (вектори , , , розмірності ) у вектори методу , , , з розмірністю . Елементи вхідних векторів розміщуються у векторах методу, починаючи з другої комірки. Це є необхідним, щоб можна було за дати значення для початкових коефіцієнтів прогону , . Треба зазначити, що значення коефіцієнтів системи (7.1) мають бути вже задані у вхідних даних.
Прямий хід методу. Обчислюються коефіцієнти прогону та . У змінній обчислюється вираз з їх попередніми значеннями.
Обернений хід. Спершу присвоюємо значення для останнього невідомого, а потім в циклі відшукуємо усі решта невідомі.
На останньому етапі повертаються значення у вектор .
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (7.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
8. Метод простої ітерації
Трансформуємо систему (1.2) до такого вигляду
, (8.1)
де – числова квадратна матриця -го порядку, – вектор вільних членів. Це здійснюється шляхом вираження з першого рівняння системи (1.1), – з другого рівняння, – з -го рівняння
, (8.2)
де ; , при ; , при . При цьому вважаємо, що діагональні коефіцієнти , .
Метод простої ітерації полягає у наступному. Вибирається довільне початкове наближення вектора та будується ітераційна послідовність векторів за формулою
, (8.3)
Ітераційний процес триває до тих пір, поки не виконається умова його збіжності
, (8.4)
де – задана похибка збіжності ітераційного процесу у відсотках.
Умова збіжності: якщо сума модулів елементів рядків або стовпців матриці є меншою за 1, то процес ітерації для даної системи збігається до єдиного розв’язку, незалежно від вибору вектора початкових наближень.
Ця умова збіжності вважається достатньою, але не необхідною. Тобто, якщо умова виконується, то процес буде збіжним. Коли ж умова не виконується, то це ще не означає, що процес буде розбіжним.
Загальний алгоритм методу простої ітерації
для
;
для
якщо {}
інакше {}
Трансформування
матриць:
для
Умова збіжності
для
Ітераційний
процес:
Опис алгоритму
На етапі трансформування здійснюємо перетворення базових матриць та у відповідні матриці та . У циклі також присвоюємо вектору початкових наближень , як початкові, значення вектора .
Умовою виходу з ітераційного процесу є виконання умови збіжності для кожного елементу вектора . Якщо ж для якогось умова не виконується, ітераційний процес продовжуємо далі.
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (1.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
9. Метод Зейделя
Ітераційний метод Зейделя відрізняється від методу простої ітерації, що при обчисленні на ()-й ітерації враховуються значення , , …, , обчислені на цій же ітерації. Іншими словами, уточнені значення невідомих одразу ж підставляються у наступні рівняння
. (9.1)
Слід зауважити, що в загальному метод Зейделя має кращу збіжність ніж метод простої ітерації. Хоча все залежить від параметрів конкретної задачі, тому не виключена ситуація, що метод простої ітерації дасть кращі результати.
Ітераційний процес (9.1) завершуємо при виконанні умови його збіжності (8.4).
Загальний алгоритм методу Зейделя
для
;
для
якщо {}
інакше {}
Трансформування
матриць:
для
Умова збіжності
для
Ітераційний
процес:
Опис алгоритму
На етапі трансформування здійснюємо перетворення базових матриць та у відповідні матриці та . У циклі також присвоюємо значенням векторів та , як початкові, значення вектора .
Умовою виходу з ітераційного процесу є виконання умови збіжності для кожного елементу вектора . Якщо ж для якогось умова не виконується, ітераційний процес продовжуємо далі. Ітераційна формула методу Зейделя відрізняється від формули методу простої ітерації лише тим, що замість вектора в елементі суми присутній вектор .
Для перевірки вірності роботи алгоритму підставляємо наші знайдені в систему (1.1). Обчислені ліві частини рів нянь повинні відповідати правим значенням елементів вектора .
10. Порядок виконання роботи
Вдома вивчити теоретичні відомості, необхідні для виконання лабораторної роботи.
Згідно варіанту (порядкового номера у журналі викладача) завдання (таблиця 1), вдома написати програму для реалізації алгоритму вказаного методу, а у лабораторії вписати програмний код та налагодити цю програму.
Отримані на комп’ютері числові результати представити викладачу.
По результатах виконаної роботи оформити звіт та здати його.
Таблиця 1. Завдання до лабораторної роботи
№
п/п
Завдання
Вхідні дані
1
Розв’язати систему рівнянь методом Гауса
система №1
2
Розв’язати систему рівнянь методом Гауса з вибором головного елемента по стовпцю
система №1
3
Розв’язати систему рівнянь методом Гауса з вибором головного елемента по рядку
система №1
4
Розв’язати систему рівнянь методом Гауса з вибором головного елемента по всій матриці
система №1
5
Обчислити визначник матриці простим методом Гауса
матриця №1
6
Обчислити визначник матриці методом Гауса з вибором головного елемента по стовпцю
матриця №1
7
Обчислити визначник матриці методом Гауса з вибором головного елемента по рядку
матриця №1
8
Обчислити визначник матриці методом Гауса з вибором головного елемента по всій матриці
матриця №1
9
Знайти обернену матрицю простим методом Гауса
матриця №1
10
Знайти обернену матрицю методом Гауса з вибором головного елемента по стовпцю
матриця №1
11
Знайти обернену матрицю методом Гауса з вибором головного елемента по рядку
матриця №1
12
Знайти обернену матрицю методом Гауса з вибором головного елемента по всій матриці
матриця №1
13
Розв’язати систему рівнянь методом LU-розкладу
система №1
14
Розв’язати систему рівнянь методом прогону
система №3
15
Розв’язати систему рівнянь методом простої ітерації
система №2
16
Розв’язати систему рівнянь методом Зейделя
система №2
17
Розв’язати систему рівнянь методом Гауса
система №1
18
Розв’язати систему рівнянь методом Гауса з вибором головного елемента по стовпцю
система №1
19
Розв’язати систему рівнянь методом Гауса з вибором головного елемента по рядку
система №1
20
Розв’язати систему рівнянь методом Гауса з вибором головного елемента по всій матриці
система №1
21
Обчислити визначник матриці простим методом Гауса
матриця №1
22
Обчислити визначник матриці методом Гауса з вибором головного елемента по стовпцю
матриця №1
23
Обчислити визначник матриці методом Гауса з вибором головного елемента по рядку
матриця №1
24
Обчислити визначник матриці методом Гауса з вибором головного елемента по всій матриці
матриця №1
25
Знайти обернену матрицю простим методом Гауса
матриця №1
26
Знайти обернену матрицю методом Гауса з вибором головного елемента по стовпцю
матриця №1
27
Знайти обернену матрицю методом Гауса з вибором головного елемента по рядку
матриця №1
28
Знайти обернену матрицю методом Гауса з вибором головного елемента по всій матриці
матриця №1
29
Розв’язати систему рівнянь методом LU-розкладу
система №1
30
Розв’язати систему рівнянь методом прогону
система №3
Вхідні дані:
Система №1
де ; ; порядковому № зав
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора