Мета роботи. до виконання лабораторної роботи №2

04-03-

Методичні вказівки

до виконання лабораторної роботи №2

з навчальної дисципліни

" Числові методи"

студентам за напрямом підготовки

6.050202 " Автоматизація та комп'ютерно-інтегровані технології" денної та заочної форм навчання

Рекомендовано методичною

комісією за напрямом «Автоматизація та комп'ютерно-інтегровані технології»

Протокол № __ від _____ 2015 р.

Рівне – 2015

Методичні вказівки до виконання лабораторної роботи №2 з дисципліни «Числові методи» студентам за напрямом підготовки 6.050202 " Автоматизація та комп'ютерно-інтегровані технології" денної та заочної форм навчання / В. М. Кутя, А. П. Сафоник. – Рівне: НУВГП, 2015. – 23 с.

Упорядники: В. М. Кутя, ст. викладач кафедри автоматизації, електротехнічних та комп'ютерно-інтегрованих технологій;

А. П. Сафоник, к.т.н., доц., доцент кафедри автоматизації, електротехнічних та комп’ютерно-інтегрованих технологій,

Відповідальний за випуск: В. В. Древецький, д.т.н., професор, завідувач кафедри автоматизації, електротехнічних та комп'ютерно-інтегрованих технологій.

© В. М. Кутя, А. П. Сафоник, 2015

© НУВГП, 2015

Лабораторна робота №2

Чисельне розв'язування систем лінійних алгебраїчних рівнянь

Мета роботи

Ознайомитися з чисельними методами розв’язування систем лінійних алгебраїчних рівнянь. Навчитися знаходити розв'язки СЛАР точними та наближеними методами.

2.2. Теоретичні відомості

2.2.1. Загальні відомості

Розв’язування систем лінійних алгебраїчних рівнянь (СЛАР) є важливою обчислювальною задачею, до якої зводиться велика кількість прикладних розрахункових задач (наприклад, розрахунок параметрів електричних кіл, аналіз рівноваги сил у жорсткій системі балок, або дослідження умов та параметрів рівноваги хімічної реакції тощо). Практична цінність чисельного методу визначається швидкістю і ефективністю отримання розв'язку. Розглянемо деякі чисельні методи і ефективні алгоритми розв'язування СЛАР.

Системою лінійних алгебраїчних рівнянь (СЛАР) називають систему вигляду:

(2.1)

де – коефіцієнти системи; – невідомі; – вільні члени системи; .

Запишемо систему рівнянь (2.1) у матричному вигляді:

AX=B, (2.2)

де

Розв’язати СЛАР – означає знайти такі x_j, що перетворюють кожне рівняння системи (2.1) в тотожність.

Кількість невідомих m у СЛАР називають порядком системи. Якщо СЛАР має хоча б один ненульовий розв’язок, то її називають сумісною, у протилежному випадку – несумісною. Систему рівнянь називають визначеною, якщо вона має тільки один розв’язок (при m = n). Систему називають невизначеною, якщо вона має безліч розв’язків (m n). СЛАР називають виродженою, якщо її головний визначник дорівнює нулю, і невиродженою – у протилежному випадку(det A ≠ 0). Системи називають еквівалентними, якщо вони сумісні, визначені і мають однаковий розв’язок.

СЛАР можна розв'язати чисельними методами, якщо вона сумісна, визначена і невироджена.

Отже, необхідною і достатньою умовою існування єдиного розв’язку СЛАР є: det A ≠ 0, тобто визначник головної матриці системи повинен бути відмінним від нуля. Ця умова поширюється на СЛАР будь-якого порядку.

2.2.2. Чисельні методи розв’язування СЛАР

Для знаходження розв’язків СЛАР на ЕОМ використовують дві групи чисельних методів:

1) точні ( метод Гауса, метод Гауса з вибором головного елемента, метод Гауса з одиничною матрицею, метод Гауса з перетвореною матрицею, метод Гауса-Халецького, метод Гауса-Жордана, метод Крамера);

2) наближені ( метод послідовних ітерацій, метод Зейделя, метод векторів зміщень тощо).

Точними є методи, які дозволяють отримати точний розв’язок системи (2.1) за відповідну кількість операцій перетворення без урахування похибок заокруглення.

До наближених (ітераційних) належать методи, які дозволяють отримати розв'язок системи (2.1) у вигляді границі послідовності векторів , яка збігається до точного розв’язку системи, де:

Методом Крамера можна розв’язувати СЛАР будь-якого порядку n. Але зі зростанням n метод стає дуже громіздким, оскільки число арифметичних операцій для обчислення визначника приблизно рівна (n +1)!, а визначників є (n +1).

Можна знаходити розв’язок СЛАР (2.2) при m=n з використанням оберненої матриці А ^-1. Помноживши зліва рівняння (2.2) на А ^-1, одержуємо Х = А ^-1 В. Однак за кількістю арифметичних операцій знаходження оберненої матриці не простіше за формули Крамера.

Найпоширенішим обчислювальним методом розв’язування СЛАР є метод, запропонований німецьким матема­тиком Карлом Фрідріхом Гаусом.

Особливості методів Гауса

Найбільш відомим з точних методів розв’язання СЛАР (2.1) є методи Гауса, суть яких полягає в тому, що система рівнянь, яка розв’язується, зводиться до еквівалентної системи з верхньою трикутною матрицею. Невідомі знаходяться послідовними підстановками, починаючи з останнього рівняння перетвореної системи. Алгоритми Гауса складаються із виконання однотипних операцій, які легко формалізуються. Однак, точність результату й витрачений на його отримання час у більшості випадків залежить від алгоритму формування трикутної матриці системи. У загальному випадку алгоритми Гауса складаються з двох етапів:

Прямий хід, в результаті якого СЛАР (2.1), що розв'язується, перетворюється в еквівалентну систему з верхньою трикутною матрицею коефіцієнтів виду:

(2.3)

Зворотний хід дозволяє визначити вектор розв‘язку починаючи з останнього рівняння системи (2.3) шляхом підстановки координат вектора невідомих, отриманих на попередньому кроці.

Відомо декілька різних алгоритмів отримання еквівалентної системи з верхньою трикутною матрицею.

2.2.3. Метод Гауса з послідовним виключенням невідомих

Розглянемо базовий метод Гауса для розв'язування системи (2.1). Цей метод полягає в послідовному виключенні невідомих із системи. Припустимо, що . Послідовно помножимо перше рівняння на і додамо з і -м рівнянням. Таким чином виключимо зі всіх рівнянь системи. Отримаємо:

Аналогічно виключимо з отриманої системи. Послідовно виключивши всі невідомі до , отримаємо систему трикутного вигляду:

(2.4)

Виконання описаної вище процедури прямого ходу можливе при умові, що всі , не дорівнюють нулю.

У результаті зворотного ходу методу Гауса, виконуючи послідовні підстановки (починаючи з останнього рівняння) в системі (2.4), отримаємо всі значення невідомих:

.

Метод Гауса може бути легко реалізований на комп'ютері. Цей метод та його модифікації вирізняються меншою кількістю арифметичних дій, приблизно рівною n ³. Однак, один з основних недоліків методу Гауса пов'язаний з тим, що при його реалізації накопичуються обчислювальні похибки, які спотворюють розв’язок великих погано обумовлених СЛАР.

Для вирішення цієї проблеми був створений метод QR -розкладу, що майже усунув ці похибки.

Однією з найбільш поширених модифікацій методу Гауса є метод LU -розкладу, щополягає у розкладі матриці СЛАР на добуток двох матриць, нижньої трикутної L та верхньої трикутної U: A=LU. Тоді систему AX=B розв’язують у два етапи: спочатку розкладають матрицю А на добуток LU (прямий хід методу Гауса),
а потім послідовно розв’язують системи LY=B та UX=Y (зворотний хід).

QR -розклад полягає у розкладі матриці А на добуток дійсної ортогональної матриці Q і верхньої трикутної R. Поетапний розв’язок системи AX=B виконують так: спочатку обчислюють Y = Q ^т × B, а потім розв’язують систему RX=Y. QR -розклад є складнішим, ніж LU -розклад, а погано обумовлені системи не так часто зустрічаються.

Для того, щоб зменшити зростання обчислювальної похибки застосовуються різні модифікації методу Гауса. Наприклад, метод Гауса з вибором головного елемента по стовпцях, в цьому випадку на кожному етапі прямого ходу рядка матриці переставляються таким чином, щоб діагональний кутовий елемент був максимальним. При виключення відповідного невідомого з інших рядків поділ буде вироблятися на найбільший з можливих коефіцієнтів і отже відносна похибка буде найменшою.

2.2.4. Метод простих ітерацій

При великій кількості невідомих у СЛАР реалізація методу Гауса є досить складною. Тому для знаходження коренів системи інколи зручніше користуватись наближеними числовими методами. Ітераційні методи забезпечують отримання коренів системи із заданою точністю шляхом збіжних нескінченних процесів (наприклад, метод ітерації, метод Зейделя, метод релаксації та інші).

При використанні ітераційних процесів до похибок округлень додається похибка методу.

Крім того, ефективне застосування ітераційних методів істотно залежить від вдалого вибору початкового наближення та швидкості збіжності процесу.

Розглянемо метод простих ітерацій для розв’язування СЛАР.

Спочатку необхідно СЛАР (2.1) привести до нормального вигляду (зручного для ітерації):

З цією метою розв’яжемо перше рівняння системи (2.1) відносно , друге – відносно і т. д. Отримаємо систему:

(2.5)

де , при ; , при ;

; ; .

Нульове наближення розв'язку системи (2.5) можна вибрати довільним. Виберемо, наприклад, стовпчик вільних членів . Далі послідовно побудуємо матриці-стовпці наступних наближень розв’язку системи (2.5):

– перше наближення,

– друге наближення і т.д.

Будь-яке (k + 1)-е наближення обчислюється за формулою:

, (k = 0, 1, 2, …). (2.6)

У розгорнутому вигляді .

Якщо послідовність наближень має границю

, (2.7)

то ця границя є розв’язком системи (2.5).

Ітераційний процес зупиняють, при умові , де e – задана абсолютна похибка.

Значно простішою для програмної реалізації є така формула методу простих ітерацій:

. (2.8)

Умови збіжності методу простих ітерацій