“Ітераційні методи розв’язання систем лінійних рівнянь”

Скачати 65.32 Kb.

Назва	“Ітераційні методи розв’язання систем лінійних рівнянь”
Дата	07.02.2014
Розмір	65.32 Kb.
Тип	Документи

bibl.com.ua > Інформатика > Документи

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІНЖЕНЕРНО-ТЕХНІЧНИЙ ФАКУЛЬТЕТ

КАФЕДРА КОМП’ЮТЕРНИХ СИСТЕМ ТА МЕРЕЖ

МЕТОДИЧНІ ВКАЗІВКИ

І ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ З КУРСУ

“АЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ”

на тему

ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ

ЛІНІЙНИХ РІВНЯНЬ

Ужгород – 2006

Методичні вказівки і завдання до лабораторної роботи з курсу

“Алгоритми та методи обчислень”

на тему:

ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗАННЯ СИСТЕМ

ЛІНІЙНИХ РІВНЯНЬ
для студентів 3-го курсу інженерно-технічного факультету,

спеціальність комп’ютерні системи та мережі

Укладач: Король І.Ю., канд. фіз.-мат. наук, доцент,

зав. кафедри “ Комп’ютерних систем та мереж ”

Затверджено на засіданні кафедри Комп’ютерних систем та мереж,

Протокол № від вересня 2006 року

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

Тема: “Ітераційні методи розв’язання систем лінійних рівнянь”

Мета роботи: Вивчення ітераційних методів розв’язання систем лінійних рівнянь і набуття навичок їх реалізації за допомогою математичного пакету Mathcad.

Зміст роботи:

1. Вивчити можливості математичних пакетів Mathcad для розв’язання систем лінійних рівнянь ітераційними методами.

2. Виконати запропоновані завдання з використанням засобів пакетів Mathcad. Зміст звіту:

Навести короткі теоретичні відомості, постановку завдань та результати їх виконання.

КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ

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

Найпростішим ітераційним методом розв’язання систем лінійних рівнянь є метод простої ітерації.

1. Метод простої ітерації

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

(1)

або у матричній формі

(2)

,

де А – матриця коефіцієнтів системи,

– вектор вільних членів і

– вектор невідомих.

Нехай діагональні елементи

матриці

відмінні від нуля. Тоді, розв’язавши перше рівняння системи (1) відносно

, друге – відносно

і т.д., дістанемо систему.

(3)

де

.

Ввівши до розгляду матриці

,

систему (3) запишемо у вигляді

(4)

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

. Тоді наступні наближення будемо шукати за формулою

. (5)

Якщо послідовність наближень

має границю

, то ця границя і буде розв’язком системи (4), а отже, і системи (1).

У разі розв’язання системи ітераційним методом звичайно задають деяку похибку наближення

і припинять обчислення, якщо виконується умова

, (6)

де

– точний розв’язок системи лінійних рівнянь, а

– деяка норма вектора. На практиці використовувати умову (6) для завершення обчислень неможливо, тому що значення розв’язку

невідоме. Тому замість

зазвичай використовують

.

Розглянемо умову збіжності ітераційного методу (5). Для цього запишемо вираз для глобальної похибки (6) на двох послідовних ітераціях. Оскільки

, то глобальні похибки на двох сусідніх ітераціях зв’язані лінійною залежністю

або

. (7)

З формули (7) випливає, що для того, щоб процес обчислень збігався (або глобальна похибка за абсолютною величиною зменшувалася), необхідно, щоб норма матриці

була менша за одиницю:

. (8)

Зазначимо, що оцінювань глобальної похибки

зручно виконувати за значеннями локальної похибки, тобто за значеннями, які отримані на двох сусідніх ітераціях. Для цього перепишемо формулу (7), додавши до правої частини і віднявши від неї значення

,

звідки отримуємо

(9)

або

. (10)

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

Якщо в просторі векторів

уведена норма

, то узгодженою з нею нормою у просторі матриць

називають норму

.

Найбільш часто використовуються наступні три норми векторів і узгоджені з ними норми матриць:

;

,

де

– максимальне власне значення матриці

. Обчислення норми

досить трудомістка задача, то завдяки справедливості рівності

, де норма

обчислюється просто, в оцінках замість норми

можна використовувати норму

. Норму

називають евклідовою нормою матриці.

Приклад 1. Розв’язати систему лінійних рівнянь методом простої ітерації

Для розв’язання даної системи спочатку перетворимо її до вигляду

,

зручному для реалізації методу простої ітерації. Далі обчислюємо основні норми матриці

та реалізовуємо метод простої ітерації. Результати обчислень наведено на лістингу 1.

Лістинг 1. Реалізація методу простої ітерації

Аналіз результатів показує, що оскільки норми матриці

менші за одиницю, то ітераційний процес збіжний. Локальна похибка

.

На лістингу 2 наведено програму, реалізовану в пакеті Mathcad, для розв’язання системи лінійних рівнянь методом простої ітерації із заданою точністю. На цьому ж лістингу наведено і результати розв’язання заданої системи рівнянь за допомогою програми: розв’язок, кількість виконаних ітерацій і точність обчислень.

Лістинг 2. Програма реалізації методу простої ітерації

2. Метод Зейделя
Ітераційний метод Зейделя – це деяка модифікація методу простої ітерації. Як і метод простої ітерації, метод Зейделя передбачає розв’язання кожного рівняння окремо відносно тільки однієї змінної. Однак під час обчислення і-ї компоненти вектора розв’язку

-го наближення на поточній

-й ітерації використовуються вже знайдені компоненти

-го наближення з меншими індексами:

. (11)

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

-го наближення відповідна компонента вектора

стає непотрібною.

Приклад 2. Методом Зейделя розв’язати систему лінійних рівнянь наведену в прикладі 1, виконавши 9 ітерацій.

Програма, яка реалізовує метод Зейделя, наведена на лістингу 3. На лістингу 4 наведено результати, одержані за допомогою даної програми. Для порівняння на цьому ж лістингу наведено результати, одержані за допомогою вбудованої процедури lsolve(A,b).

Лістинг 3. Програма реалізації методу Зейделя

Лістинг 4. Результати роботи програми

ІНДИВІДУАЛЬНІ ЗАВДАННЯ

Завдання 1. Знайти наближений розв’язок системи лінійних алгебраїчних рівнянь методом простої ітерації та методом Зейделя. Порівняти результати за точністю та кількістю ітерацій.

Варіанти індивідуальних завдань:

1.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

ЛІТЕРАТУРА

1. Фельдман Л.П., Петренко А.І., Дмитрієва О.А. Чисельні методи в інформатиці. К.: Видавнича група BHV, 2006. – 480 с.

2. Алексеев Е.П., Чесноков О.В. Решение задач вычислительной математики в пакетах Mathcad 12, VFTLAB 7, Maple 9. М.: НТ Пресс, 2006. – 496 с.

3. Ляшенко М.Я., Головань М.С. Чисельні методи: Підручник . К.: Либідь. 1996. – 288 с.

Схожі:

Розділ РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ У цьому розділі розглянемо основні чисельні методи розв’язання задач лінійної алгебри. Наведемо математичне описання, блок-схеми...	Урок №73 Тема. Системи двох лінійних рівнянь із двома змінними та... Ня щодо залежності кількості розв'язків системи лінійних рівнянь від співвідношення коефіцієнтів a, b, c цих рівнянь; вироблення...
Урок №80 Тема. Розв'язування задач за допомогою систем лінійних рівнянь Мета: відпрацювати навички застосування схеми розв'язання текстових задач на складання системи лінійних рівнянь із двома змінними...	Графічний спосіб розв’язування систем лінійних рівнянь із двома змінними Учитель Сьогодні на уроці ми продовжимо вивчати тему «Розв’язування систем лінійних рівнянь з двома змінними графічним способом»....
УРОК №71 Тема уроку. Системи рівнянь Мета уроку: формування понять: «система рівнянь з двома змінними»; «розв'язки системи лінійних рівнянь з двома змінними»; «ознайомлення...	ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ Ужгород –... Мета роботи: Вивчення методів розв’язання систем нелінійних рівнянь і набуття навичок їх реалізації за допомогою математичного пакету...
УРОК №75 Тема уроку. Спосіб додавання Мета уроку: ознайомлення учнів із розв'язуванням систем лінійних рівнянь способом додавання; засвоєння алгоритму розв'язування систем...	“Чисельні методи розв’язання нелінійних рівнянь” Мета роботи: Вивчення методів розв’язання алгебраїчних і трансцендентних рівнянь і набуття навичок їх реалізації за допомогою математичного...
УРОК №76 Тема уроку. Розв'язування вправ на розв'язування систем... Мета уроку: формування вмінь учнів розв'язувати системи лінійних рівнянь з двома змінними способом додавання	ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ ЖОРСТКИХ ДИФЕРЕНЦІАЛЬНИХ РІВНЯНЬ ТА ЇХ СИСТЕМ Розглянемо спочатку питання умовної та абсолютної стійкості на простому прикладі. Задача Коші

Додайте кнопку на своєму сайті:
Портал навчання