Зміст
Введення
1. Метод Гаусса
2. Модифікації методу Гауса
3. Метод прогонки
4. Обчислення визначників
5. Обчислення зворотних матриць
6. Ітераційні методи
Висновок
Список літератури
Введення
Основною метою реферату є вивчення та порівняльний аналіз чисельних методів розв'язання систем лінійних алгебраїчних рівнянь, обчислення визначників і зворотних матриць; реалізація цих методів у вигляді машинних програм мовою високого рівня і практичне вирішення завдань на ЕОМ.
У загальному випадку система лінійних алгебраїчних рівнянь має вигляд
(1)
У матричної формі система (1) представляється як
AX = B (2)
де
В
Щоб така система рівнянь мала єдине рішення, що входять до неї n рівнянь повинні бути лінійно незалежними. Необхідною і достатньою умовою цього є нерівність нулю визначника цієї системи, тобто det A В№ 0. Алгоритми розв'язання систем рівнянь такого типу поділяються на прямі та ітераційні.
1. Метод Гаусса
Даний метод також називається методом послідовного виключення невідомих. Він відноситься до групи прямих методів і заснований на перетворенні вихідної системи до еквівалентної формі з трикутною матрицею коефіцієнтів. p> При використанні методу Гаусса завдання вирішується в два етапи:
1) прямий хід;
2) зворотний хід.
Прямий хід полягає в перетворенні системи до трикутного вигляду.
При зворотному ході виробляється обчислення значень невідомих.
Прямий хід методу Гауса. Для отримання розрахункових формул прямого ходу перетворимо вихідну систему (1), замінивши елементи b i () на a i, n +1 . В результаті система (1) буде мати наступний вигляд
В
Прямий хід виконується за (N-1) кроків, причому на кожному кроці з рівнянь з номерами k + 1, k + 2, ..., n виключається невідоме x k .
На першому кроці спочатку перше рівняння ділиться на a 11 В№ 0. Отримаємо
(3)
де
В
Потім з кожної з решти рівняння виду
()
віднімається отримане рівняння (3), помножене на коефіцієнт a i1 . У підсумку, після виконання першого кроку прямого ходу система рівнянь прийме наступний вигляд
(4)
де
В
На другому кроці зазначені вище дії повторюються над (n - 1) рівняннями системи (4), усіма крім першого, з метою виключення змінної x 2 , де
В
У підсумку отримаємо
В
де
В
Повторюючи кроки прямого ходу (n - 1) раз, остаточно отримаємо систему рівнянь трикутного виду
(5)
де
В
При програмної реалізації прямого ходу використовується розширена матриця коефіцієнтів A Вў
,
для якої елементи мають наступний сенс
1) - початкові значення;
2) - проміжні значення;
3) - кінцеві значення.
Для визначення елементів матриці A Вў на деякій k-му кроці
()
використовуються наступні розрахункові формули
В
Зворотний хід методу Гаусса. Після приведення вихідної системи рівнянь (1) до трикутного вигляду (5) обчислюються значення коренів за такими формулами
В
Таким чином, розрахункові формули зворотного ходу мають вигляд
В
Обчислювальна складність методу Гауса оцінюється як O (n 3 ), причому для реалізації прямого ходу потрібно близько арифметичних операцій, а для зворотного - близько n 2 операцій.
2. Модифікації методу Гауса
Метод Гаусса з вибором головного елемента. Основним обмеженням методу Гауса є припущення про те, що всі елементи, на які здійснюється поділ на кожному кроці прямого ходу, не рівні нулю. Ці елементи називаються головними елементами і розташовуються на головній діагоналі матриці A. p> Якщо на деякому кроці прямого ходу головний елемент = 0, то подальше вирішення системи неможливо. Якщо головний елемент має мале значення, близьке до нуля, то можливий сильний ріст похибки через різке зростання абсолютної величини одержуваних у результаті поділу коефіцієнтів. У таких ситуаціях метод Гауса стає нестійким. p> Виключити виникнення подібних випадків дозволяє метод Гауса з вибором головного елемента.
Ідея цього методу полягає в наступному. На деякій k-му кроці прямого ходу з рівнянь виключається НЕ наступна за номером мінлива x k , а така мінлива, коефіцієнт при якій є найбільшим за абсолютною величиною. Цим гарантується відсутність поділу на нуль і збереження стійкості методу. p> Якщо на k-му кроці в як головний елемент вибирається В№, то в матриці A Вў повинні бути переставлені місцями рядка c номерами k і p і стовпці з номерами k і q. p> П...