На головну

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

  1.  I Розрахунок витрат для визначення повної собівартості вироби (роботи, послуги), визначення рентабельності його виробництва
  2.  I. Загальна характеристика роботи
  3.  II. Вихідні дані і порядок виконання курсової роботи
  4.  II. Загальні вимоги ДО ВИКОНАННЯ РОЗРАХУНКОВО-ГРАФІЧНОЇ РОБОТИ
  5.  II. Практичні завдання для контрольної роботи
  6.  II. Вимоги охорони праці перед початком роботи
  7.  II. Вказівки до виконання контрольних робіт

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

з дисципліни "Обчислювальна математика"

на тему "Метод Гаусса"

(Теорія і варіанти завдань) для студентів спеціальностей

230102, 230104, напрямки 230100

Форма навчання очна і заочна

Іжевськ 2009

рецензент:

Ісенбаева Е. н. Методичні вказівки до виконання лабораторної роботи з дисципліни «Обчислювальна математика» на тему «Метод Гаусса» (теорія і варіанти завдань) .- Іжевськ: Видавництво ІжГТУ, 2009 г.-24с.

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

Рекомендовано до видання на засіданні кафедри «Автоматизовані системи обробки інформації та управління» ІжГТУ (протокол №6 від 23.10.2009).

Навчальний посібник призначений для студентів очної та заочної форми навчання спеціальностей 230102, 230104, напрямки 230100.

© Ісенбаева Е. н., Складання 2009

© Видавництво ІжГТУ 2009


ЗМІСТ

ВСТУП. 4

1. Загальна характеристика методів рішення лінійних алгебраїчних задач. 5

2. Метод Гаусса .. 6

3. Метод Гаусса з постолбцовим вибором головного елемента 8

4 ................... УТОЧНЕННЯ КОРЕНІВ, ОТРИМАНИХ методом Гаусса .. 9

5. Застосування методу Гауса До обчислення визначника 12

6. ЗАСТОСУВАННЯ методом Гаусса До обчислення зворотної МАТРИЦІ 13

7. обумовлених ЛІНІЙНИХ АЛГЕБРАЇЧНИХ СИСТЕМ .. 16

8. ЗАВДАННЯ НА лабораторних робіт .. 19

Список використаної літератури .. 24


ВСТУП

Дані методичного вказівки призначені для використання студентами при виконанні лабораторної роботи на тему «Метод Гаусса. Рішення систем лінійних алгебраїчних рівнянь (СЛАР). Знаходження оберненої матриці »У посібнику дається опис методу Гаусса з постолбцовим вибором головного елемента. Описано алгоритм отримання і уточнення коренів, а також алгоритм обчислення визначника і оберненої матриці за допомогою методу Гаусса. Вивчено питання аналізу чутливості СЛАР до погрішностей вхідних даних. Описано алгоритм розрахунку показника чутливості систем лінійних рівнянь - condA. Всі алгоритми реалізовані на конкретних прикладах.

В роботі наведені варіанти завдань на лабораторну роботу.

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


1. Загальна характеристика методів рішення лінійних алгебраїчних задач

До лінійним алгебраїчним завдань відносяться завдання рішення СЛАР, обчислення визначників, звернення матриць, завдання на власні значення. Методи вирішення лінійних алгебраїчних задач можна розбити на дві групи:

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

2) ітераційні методи - методи, в яких рішення може бути отримано з заданою точністю шляхом нескінченного повторення однакових дій. До ітераційним (наближеним) методів належать метод простих ітерацій, метод Зейделя, метод релаксації, Шульца.

Метод Крамера неприйнятний для вирішення СЛАР великої розмірності. Кількість арифметичних операцій (т. Е. Арифметична складність) методу Крамера пропорційно (  - Розмірність системи). при  = 20 арифметична складність оцінюється величиною  операцій. При існуючому швидкодії ЕОМ результат в найближчому майбутньому ми отримати не зможемо. Така велика кількість операцій породжує другу принципову трудність: накопичена від кожної операції обчислювальна похибка дає такий кінцевий результат, що він часто буває дуже далеким від істинного рішення.

Метод Гаусса виявляється набагато більш економічним. Алгоритмічна складність цього методу має порядок 3.

В даний час точні методи зазвичай використовуються для вирішення СЛАР, порядок яких не перевищує 103. Для вирішення СЛАР більшої розмірності використовують ітераційні методи.

В даному методичному посібнику розглядається прямий метод вирішення - метод Гаусса і його модифікація - метод Гаусса з постолбцовим вибором головного елемента.


2. Метод Гаусса

Нехай дана система  лінійних рівнянь з  невідомими:

 (1)

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

 (2)

де -  - Матриця;

 - Вектор - стовпець невідомих;

 - Вектор - стовпець правих частин.

Метод Гаусса полягає в послідовному виключенні невідомих системи шляхом її рівносильно перетворення. При цьому в чисельних методах з метою хорошою алгоритмізації завдання перетворенню піддаються не самі рівняння, а вихідні дані - матриця A і вектор правих частин b, з'єднаних в одну розширену матрицю. Метод має прямий і зворотний хід.

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

1) кожен елемент рядка, в якій знаходиться провідний елемент (a11 - в першому рядку на першому кроці, a22 - у другому рядку на другому кроці ...) ділиться на провідний елемент. При цьому передбачається, що провідні елементи відмінні від нуля.

2) виключаються елементи стовпців, що лежать нижче провідних рядків. Для виключення елементів першого стовпця використовується перша провідна рядок, для елементів другого стовпця - друга ...

Формули перерахунку прямого ходу:

 (3)

де k = 1,2, ..., n-1, k - номер кроку,

i = k + 1, ..., n;

j = k + 1, ..., n.

За визначенням вважаємо

, .


Зворотній хід дозволяє послідовно одне за іншим обчислювати значення невідомих, починаючи з останнього. Для цього переходимо до системи, що включає х1, х2, ..., Хn.

 (4)


3. Метод Гаусса з постолбцовим вибором головного елемента

Реальні математичні розрахунки проводяться з наближеними числами, т. Е. Неминучі помилки заокруглень. Знаменник дробу у формулі (3) може виявитися рівним нулю або дуже маленьким числом. В результаті виконання алгоритму може припинитися або буде отримано результат, далекий від реального. Щоб уникнути цієї ситуації, на кожному кроці прямого ходу рядка даної матриці переставляють так, щоб поділ вироблялося на найбільший по модулю в оброблюваному подстолбце елемент. Числа, на які здійснюється поділ, називаються провідними або головними елементами. Відповідно, метод Гаусса, що виключає поділ на нуль і зменшує вплив помилок заокруглень, - це метод Гаусса з постолбцовим вибором головного елемента.


4. УТОЧНЕННЯ КОРЕНІВ, ОТРИМАНИХ методом Гаусса

Нехай для системи  знайдено наближений розв'язок х0.

вважаючи

для уточнення кореня матимемо рівняння:

 (5)

де  - (6)

невязка для наближеного рішення х0.

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

Приклад 1. Знайти рішення СЛАР методом Гауса з постолбцовим вибором головного елемента. Провести уточнення рішення.

; .

Рішення зробимо в табличному вигляді:

ai1 ai2 ai3 bi
 2,63,0  -4,53,03,5  -2,04,33,0  19,073,21-18,25  -0,007-0,0110,016
3,02,6  3,53,0-4,5  3,04,3-2,0  -18,253,2119,07  0,016-0,011-0,007
 -0,583 -2,983  -0,55,8-0,7  3,042-5,91511,162  -0,0027-0,003-0,0001
 -0,583  -0,51,221  3,0421,2457,447  -0,00270,0006-0,002
 -0,583  -0,51,221  3,042-1,2452,531  -0,0027-0,0006-0,0007

Для зворотного ходу перейдемо до системи, що включає невідомі хi , І послідовно одне за іншим обчислюємо їх значення, починаючи з х3.

Отже, вектор рішення:

Уточнимо рішення. Для цього отриманий вектор рішення х вважатимемо початковим наближення х0. Підставами його у вихідну схему і знайдемо невязку  за формулою (6).

Отриманий вектор нев'язок  використовуємо як новий вільний член системи А? = ?, приписуючи його як стовпець до основної схемою обчислень. Вирішуючи СЛАР з колишньої матрицею А і новим вільним членом  , Отримуємо вектор поправок  невідомих:

Уточнюємо рішення по формулі

:

Уточнений вектор рішення:


5. Застосування методу Гауса До обчислення визначника

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

.

Таким чином, detA дорівнює добутку всіх провідних елементів.

При використанні модифікації методу Гаусса з постолбцовим вибором головного елемента проводиться перестановка рядків матриці, що може змінити знак detА. Тому в результаті потрібно врахувати парність кількості перестановок:

 де  - Кількість перестановок рядків.

Знайдемо визначник для матриці А з прикладу 1 глави 4:

det A = (-1)1 * (-6,0) * 4,75 * 2,942 = 83,847


6. ЗАСТОСУВАННЯ методом Гаусса До обчислення зворотної МАТРИЦІ

Нехай дана матриця  Для знаходження оберненої матриці  використовуватимемо основне співвідношення  , де Е - одинична матриця n-го порядку. Т. е. Виходитимемо з того, що зворотна матриця  є рішенням матричного рівняння:

 (7)

Представляючи шукану матрицю  , Як набір векторів-стовпців:

а одиничну матрицю Е як набір одиничних векторів:

 ...,

матричне рівняння (7) відповідно до правил множення матриць замінюємо еквівалентної системою векторно-матричних рівнянь:

 ...,  . (8)

Кожне з останніх рівнянь має вигляд (1) і може бути вирішено методом Гаусса. Все СЛАР (8) мають одну і ту ж матрицю коефіцієнтів, але різні праві частини, складові одиничну матрицю. В результаті завершення роботи алгоритму будуть виходити стовпець за стовпцем елементи оберненої матриці  . Зауважимо, що елементи рядків оберненої матриці виходять в зворотному порядку.

Приклад 2. Вирішити систему лінійних рівнянь методом Гаусса. Уточнити рішення. Знайти визначник і зворотний матрицю  , Включивши процес в загальний алгоритм методу Гаусса.

Знаходження ЗВОРОТНЬОГО МАТРИЦІ методом Гаусса.

ai1 ai2 ai3 bi Ei e1 e2 e3
 1,15 1,00  0,420,550,35  100,710,323,00  -198,702,29-0,65  0,000350,00014-0,00000
 0,46218-0,11151  0,26891100,400762,73109  1,92437-200,91303-2,57437  0,000120,00021-0,00012  0,84034-0,96639-0,84034
 0,46218  0,26891-24,34141  1,9243722,94486-198,35474  0,000120,001070,00033  0,840347,49100-0,13107  -8,91424-0,99403
 0,46218  0,26891-24,34561  1,9243722,94856-2,03053  0,000120,001070,00000  0,01024  0,840347,49100-0,00134  -8,91424-0,01018

 * Використовуючи постолбцовий вибір головного елемента:

- На першому кроці міняємо рядки 1 і 2;

- На другому етапі міняємо рядки 2 і 3.

Рішення:

визначник:

Вектор поправок:

Уточнене рішення:

Знаходимо обернену матрицю :

зворотна матриця :


7. обумовлених ЛІНІЙНИХ АЛГЕБРАЇЧНИХ СИСТЕМ

Розглянемо СЛАР в векторно-матричної формі:

 , (9)

де А - невироджена  - Матриця коефіцієнтів даної системи;

b - ненульовий n-мірний вектор вільних членів;

- n-мірний вектор невідомих.

Нехай права частина (9) отримала приріст  реакцією рішення х на обурення  буде вектор поправок  , Т. Е. Якщо х - Рішення (9), то  - вирішення рівняння

 . (10)

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

де  - Будь-яка векторна норма,

К - Невідомий коефіцієнт зв'язку.

Підставляючи (9) в (10), отримуємо, що поправка  пов'язана з обуренням  аналогічним (9) рівністю:  , З якого знаходимо її явне вираз:

 (11)

Нормуючи рівності (9) і (11), отримаємо

де матрична норма повинна бути узгодженою з обраної векторної нормою. Детально про нормах розповідається в методичних вказівках до виконання лабораторної роботи «Ітераційні методи рішення СЛАР».

Перемножимо отримані нерівності (9), (11)

Розділивши отримане нерівність на  отримаємо шуканий коефіцієнт зв'язку К:

 (12)

позитивний коефіцієнт  називають числом обумовленості матриці А і позначають .

Аналогічно, можна показати, що те ж саме число  служить коефіцієнтом зростання відносних похибок при неточному завданні елементів матриці А о 9).

Отже, нерівність (12) показує, що чим більше число обумовленості, тим сильніше позначається на вирішенні СЛАР помилка у вихідних даних. якщо число  велике, то система вважається погано обумовленою. на величину  впливає розмірність завдання, точність, з якою має бути знайдено її рішення, точність надання чисел в ЕОМ і т. д. Для сучасних ЕОМ діапазон  добре обумовлених СЛАР знаходиться в діапазоні: .

Пояснимо поняття обумовленості на прикладі двовимірної задачі.

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

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

приклад 3.

Дослідити обумовленість СЛАР:

Для дослідження чутливості СЛАР до погрішностей вхідних даних потрібно знайти .

.

Знайдемо обернену матрицю А-1. Одночасно знайдемо рішення СЛАР в рамках алгоритму методу Гаусса.

ai1 ai2 bi e1 e2
 -5-4,9999
 -2,500,0001  0,5  0,5-1
 0,5  -10000-24999,5

Знайдемо норму-максимум матриць і : .  , Отже, СЛАР погано обумовлена ??і буде чуйно реагувати на невеликі похибки вхідних даних. Цей висновок можна підтвердити, надавши невелике збурення правій частині другого рівняння СЛАР:

Вирішуючи отриману систему, отримаємо вектор рішення:  , Який дуже далекий від вектора рішення вихідної СЛАР. Це ще раз підтверджує факт поганої обумовленості системи.


ЗАВДАННЯ НА лабораторних робіт

Написати програму, що реалізовує алгоритм методу Гаусса. У програмі потрібно:

1. вирішити систему Ax = b. Вирішити систему методом Гаусса. Передбачити постолбцовий вибір головного елемента;

2. провести ітераційне уточнення рішення до досягнення точності Е = 10-12 по евклідовій нормі невязки в рамках застосовуваної схеми реалізації методу;

3. Визначити визначник матриці А;

4. Визначити зворотний матрицю X = A-1 , Вирішуючи підсистеми Ах j = е j системи АХ = Е;

5. обчислити condA в різних простих нормах і охарактеризувати чутливість даної системи до погрішностей вихідних даних.

У звіті з лабораторної роботи повинні бути представлені наступні розділи:

1. Постановка завдання.

2. Математична модель.

3. Текст програми.

4. Результати роботи.

5. Висновки.

Лабораторна робота виконується на будь-якій мові високого рівня.

Варіанти завдань на лабораторну роботу

1. ; .

2. ; .

3. ; .

4. ; .

5. ; .

6. ; .

7. ; .

8. ; .

9. ; .

10. ; .

11. ; .

12. ; .

13. ; .

14. ; .

15. ; .

16. ; .

17. ; .

18. ; .

19. ; .

20. ; .

21. ; .

22. ; .

23. ; .

24. ; .

25. ; .

26. ; .

27. ; .

28. ; .

29. ; .

30. ; .

31. ; .

32. ; .

33. ; .

34. ; .

35. ; .

36. ; .

37. ; .

38. ; .

39. ; .

40. ; .


СПИСОК ЛІТЕРАТУРИ

1. Бахвалов Н. с. Чисельні методи. - М .: Наука, 1973.

2. Бахвалов Н. с., Лапін А. в., Чіжонков Е. в. Чисельні методи в задачах і вправах. - М .: Вища школа, 2000..

3. Вержбицький В. м. Чисельні методи (лінійна алгебра і нелінійні рівняння). - М .: Вища школа, 2000..

4. Вержбицький В. м. Чисельні методи (математичний аналіз і звичайні диференціальні рівняння). - М .: Вища школа, 2001..

5. Демидович Б. п., Марон І. а. Основи обчислювальної математики. - М .: Наука, 1970.

6. Демидович Б. п., Марон І. а. Чисельні методи аналізу. - М .: Наука, 1970.

7. Каліткін Н. н. Чисельні методи. - М .: Наука, 1978.

8. Кірєєв В. І., Пантелєєв А. В. Чисельні методи в прикладах і завданнях: Навчальний посібник. - М .: Вища школа, 2004.

9. Копченова Н. в., Марон І. а. Обчислювальна математика в прикладах і задачах. - М .: Наука, 1972.

 



 Інтерполяційного СХЕМА Ейткен |  теоретичні відомості
© um.co.ua - учбові матеріали та реферати