ЧИСЕЛЬНІ МЕТОДИ
Методи розв’язування лінійних алгебраїчних рівнянь
методичні вказівки до лабораторної роботи № 3
для студентів напряму 6.050101 „Комп’ютерні науки”
Методичні вказівки обговорені та схвалені на засіданні Науково-методичної ради інституту комп’ютерних наук та інформаційних технологій Національного університету «Львівська політехніка». Протокол № ____ від _______________2017
Укладачі: Висоцька В.А., к.т.н., доцент кафедри ІСМ
Методичні вказівки до лабораторних робіт з дисципліни «Чисельні методи» для студентів напряму 6.050101 „Комп’ютерні науки” /Укл.: В.А.Висоцька.
Лабораторна робота № 3
на тему " Методи розв’язування лінійних алгебраїчних рівнянь "
Мета роботи: вивчити основні поняття методів розв’язування лінійних алгебраїчних рівнянь
Короткі теоретичні відомості
Інженеру часто доводиться розв’язувати алгебраїчні та трансцендентні рівняння і системи рівнянь, що можуть являти собою самостійну задачу (наприклад, аналіз рівноваги сил в жорсткій системі балок або дослідження умов та параметрів рівноваги хімічної реакції, тощо), або частину більш складних задач. В обох випадках практична цінність чисельного методу в значній мірі визначається швидкістю та ефективністю отримання розв’язку. Розглянемо найбільш відомі чисельні методи та ефективні алгоритми розв’язування систем лінійних алгебраїчних рівнянь.
3.1. Чисельне розв’язування систем лінійних алгебраїчних рівнянь
Розв’язком системи лінійних алгебраїчних рівнянь (3.1) називають вектор X, координати якого при підстановці у систему, яку розв’язують, перетворюють кожне рівняння системи в тотожність. Якщо детермінант матриці А відрізняється від нуля, тобто , то матриця А є неособливою і система лінійних рівнянь (3.1) або (3.2) має єдиний розв’язок.
3.2. Основні поняття та класифікація систем лінійних алгебраїчних рівнянь
Для розв’язування СЛАР на комп’ютері традиційно використовують дві групи чисельних методів, що представлені на рисунку 3.1.
Методи чисельного розв’язування систем лінійних алгебраїчних рівнянь поділяються на дві групи:
- Точні (прямі) методи, які дозволяють одержати розв’язок, якщо він існує, як скінченну кількість математичних операцій (наприклад: метод Гауса, метод Гауса з вибором головного елементу, метод Гауса з одиничною матрицею, метод Гауса з перетвореною матрицею, метод Гауса-Халецького, метод Гауса-Жордана, метод Крамера тощо). До точних методів відносять методи, які дозволяють отримати точний розв’язок системи (3.1) через відповідну кількість операцій перетворення без урахування похибок заокруглення.
Наближені (ітераційні) методи, які дозволяють одержати лише наближені до коренів значення із певною похибкою (наприклад, метод послідовних ітерацій, метод Гауса-Зейделя, метод векторів зміщень). Точний розв’язок можна отримати як результат нескінченно збіжного процесу дослідження або експерименту. До таких методів відносять метод простої ітерації, метод Зейделя та ін. “Точні” методи використовують при розв’язку на ПК систем невисокого порядку (n<103 , де n – число лінійних алгебраїчних рівнянь системи). Наближені методи використовують для систем високого порядку n=103…106. Переваги наближеного методу (простих ітерацій) над точним методом (Гауса) наступні:
- Час обчислень пропорційний n2 на ітерацію, тоді як для методу Гауса – n3. Якщо для розв’язку потрібно менше ніж n ітерацій, то втрати машинного часу будуть менші.
- Як правило похибки округлення при ітераційному методі впливають на остаточні результати значно менше, ніж при методі Гауса, оскільки при його використанні похибки не нагромаджуються.
- Ітераційний метод стає особливо зручним при розв’язуванні систем, переважна кількість коефіцієнтів яких дорівнює 0. Рівняння, які отримують, наприклад, при розв’язуванні крайових задач, відносяться саме до цього класу.
Недоліком ітераційного методу є те, що він не завжди збігається. Ітераційні методи дозволяють одержати приблизний розв’язок системи за скінченне число наближень (ітерацій) із заданою похибкою результату. До наближених методів відносять методи, які дозволяють отримати розв’язок системи (рис. 3.1) у вигляді границі послідовності векторів , яка збігається до точного розв’язку системи, де:
;;Кількість невідомих m в системі називають порядком СЛАР. Систему лінійних алгебраїчних рівнянь називають сумісною, якщо вона має хоча б один ненульовий розв’язок. В протилежному випадку СЛАР називають несумісною. СЛАР називається визначеною, якщо вона має тільки один розв’язок (випадок, коли m=n). Систему називають невизначеною, якщо вона має безліч розв’язків (m¹n). Система називається виродженою, якщо головний визначник системи дорівнює нулю. Система називається невиродженою, якщо головний визначник системи не дорівнює нулю. Дві системи називаються еквівалентними, якщо ці системи сумісні, визначені і мають однаковий розв’язок. СЛАР можна розв’язати на комп’ютері чисельними методами, якщо вона сумісна, визначена, невироджена.
3.3. Основні поняття та особливості матриць
Матриця – математичний об’єкт, що записується у вигляді прямокутної таблиці чисел (або елементів кільця), і допускає алгебраїчні операції (додавання, віднімання, множення тощо) між ним та іншими подібними об’єктами. Правила виконання операцій над матрицями визначені для зручності запису системи лінійних алгебраїчних рівнянь. Звичайно матрицю позначають великою буквою латинського алфавіту й виділяють круглими дужками (…) (зустрічається також виділення квадратними дужками – […], подвійними прямими лініями – ||…||). А числа (елементи матриці), позначають тією же буквою, що й саму матрицю, але маленькою. У кожного елемента матриці є 2 нижніх індекси (aij) – перший «i» позначає номер рядка, у якому перебуває елемент, а другий «j» – номер стовпця.
3.3.1. Операції над матрицями
Нехай – елементи матриці A, а – елементи матриці B.
1. Множення матриці A на число (позначення: A) полягає в побудові матриці B, елементи якої отримані шляхом множення кожного елемента матриці A на це число, тобто кожен елемент матриці B дорівнює:
2. Додавання матриць A+B – операція знаходження матриці C, всі елементи якої дорівнюють попарній сумі всіх відповідних елементів матриць A і B, тобто кожен елемент матриці C дорівнює:
3. Різниця матриць A–B визначається аналогічно додаванню, це операція знаходження матриці C, елементи якої визначаються як:
Додавання й віднімання допускається тільки для матриць однакового розміру.
4. Існує нульова матриця така, що її додавання до іншої матриці A не змінює A, тобто
Всі елементи нульової матриці рівні нулю.
5. Добуток матриць (позначення: AB, рідше зі знаком множення) – операція обчислення матриці C, елементи якої дорівнюють сумі добутків елементів у відповідному рядку першого множника й стовпці другого.
У першому множнику повинно бути стільки ж стовпців, скільки рядків у другому. Якщо матриця A має розмірність , B – , то розмірність їх добутку AB = C є . Множення матриць не є комутативною операцією. Це видно хоча б з того, що якщо матриці не квадратні, то можна множити тільки одну на іншу, але не навпаки. Для квадратних матриць результат множення залежить від порядку співмножників. Наприклад:
Підносити до степеня можна тільки квадратні матриці.
6. Транспонування матриці (позначення: AT) — операція, при якій матриця відображається відносно головної діагоналі, тобто
Якщо A – матриця розміру , то – матриця розміру .
3.3.2. Квадратна матриця й суміжні визначення
Якщо кількість рядків матриці дорівнює кількості стовпців, то така матриця називається квадратною. Для квадратних матриць існує одинична матриця E така, що множення будь-якої матриці на неї не впливає на результат, а саме:
В одиничній матриці одиниці розташовані тільки по діагоналі, інші елементи дорівнюють нулю
Для деяких квадратних матриць можна знайти так звану обернену матрицю. Обернена матриця є такою, що якщо помножити матрицю на неї, то отримаємо одиничну матрицю
Обернена матриця існує не завжди. Матриці, для яких обернена існує, називаються невиродженими, а для яких не існує – виродженими. Матриця невироджена, якщо всі її рядки (стовпці) лінійно незалежні як вектори. Максимальне число лінійно незалежних рядків (стовпців) називається рангом матриці. Визначником (детермінантом) матриці називається нормований кососиметричний лінійний функціонал на рядках матриці. Квадратна матриця над числовим полем вироджена тоді й тільки тоді, коли її визначник дорівнює нулю.
(Для ознайомлення з повним текстом статті необхідно залогінитись)