Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом icon

Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом




Скачати 128.77 Kb.
НазваЛабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом
Дата14.09.2012
Розмір128.77 Kb.
ТипДокументи
1. /Лабораторные_работы/KMD_Методичка_по_ЛАБ_ ОМ_2007.doc
2. /Лабораторные_работы/Lab2_1.doc
3. /Лабораторные_работы/lab_2_2.doc
4. /Лабораторные_работы/lab_3.doc
5. /Лабораторные_работы/lab_4.doc
6. /Лабораторные_работы/lab_5.doc
7. /Лабораторные_работы/lab_6.doc
8. /Лабораторные_работы/lab_7.doc
9. /Лабораторные_работы/lab_8.doc
10. /Лабораторные_работы/lab_9.doc
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом
Лабораторна робота №2 (Частина 2) розв'язання систем лінійних алгебраїчних рівнянь наближеними методами на еом
Лабораторна робота №3 чисельні методи розв’язання нелінійних рівнянь на еом
Лабораторна робота №4 апроксимація табличних функцій степеневим та ортогональним поліномом
Лабораторна робота №5 чисельні методи розв’язання звичайних диференційних рівнянь на еом
Лабораторна робота №6 чисельні методи розв’язання крайової задачі на еом
Лабораторна робота №7 розвязання диференційних рівнянь у частних похіднихна еом
Лабораторна робота №8 обчислення визначеного інтеграла на еом
Лабораторна робота №9 оптимізація одно- та багатопараметричних функцій

Лабораторна робота №2 (Частина 1)

РОЗВ’ЯЗАННЯ СИСТЕМ ЛЫНЫЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ НА ЕОМ


Мета роботи: ознайомлення з особливостями алгоритмів точних методів розв’язання систем лінійних алгебраїчних рівнянь на ЕОМ

Порядок виконання роботи





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

  2. Скласти схему алгоритму розв’язання систем лінійних алгебраїчних рівнянь методом, вказаним викладачем.

  3. Скласти програму розв'язання систем лінійних алгебраїчних рівнянь на алгоритмічній мові, запропонованій викладачем.

  4. Користуючись даними відповідного варіанту (табл 2.1), розв’язати СЛАР на ЕОМ (початкові дані та результати роздрукувати).

  5. Розв’язати систему лінійних алгебраїчних рівнянь в середовищі MathCAD.

  6. Порівняти результати, які отримані при виконані пунктів 4,5, зробити висновки.

  7. Оформити звіт.


Примітка. Пункти 1, 2, 3 повинні бути виконані до початку занять в лабораторії.

Варіанти завдань





  1. Варіанти лабораторної роботи приведені в таблиці 2.1.

  2. Для розв’язання системи лінійних алгебраїчних рівнянь необхідно розробити:

  • основну програму, виконуючу опис даних, ввід початкових даних, виклик підпрограми розв’язання СЛАР, вивід початкових даних, виклик підпрограми розв’язання СЛАР, вивід початкових даних і отриманих результатів;

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

  1. У список параметрів підпрограми слід включити:

Вхідні параметри:

N – кількість рівнянь в СЛАР;

A – масив N N дійсних чисел (матриця коефіцієнтів системи);

B – масив із N дійсних чисел (стовпець вільних членів системи).

Вихідні параметри:

X (або) B – масив із дійсних чисел (він також може бути вхідним), який містить розв’язок системи;

IRR – ознака розв’язання (код помилки), причому:

IRR=0 – нормальне завершення роботи підпрограми;

IRR=1 – визначник системи дорівнює 0;

IRR=2, 3 ... – інші типи помилок, які визначає студент.

Таблиця 2.1 – Варіанти завдань


Номер варіанту

Матриця коефіцієнтів системи

Стовпець вільних ленів

Примітка

1



-1

-4

2

Х1 = 1

Х2 = 2

Х3 = -2

2



1

2

2

Х1 = 2

Х2 = 1

Х3 = 1

3



5

7

9

Х1 = 5

Х2 = 2

Х3 = 3

4



4

9

-2

Х1 = 1

Х2 = 2

Х3 = 1

5



-5

-2

-7

Х1 = 6

Х2 = 5

Х3 = 2

6



2,08

0,17

1,28

0,05

Х1 = 0,4026

Х2 = 1,5016

Х3 = 0,5862

Х4 = -0,2678

7



-4,75

-1,05

-5,06

Х1 = 0,2386

Х2 = 0,5945

Х3 = 3,2019

8



-6,09

-6,96

-5,52




9



1,48

1,92

2,16




10



6,97

0,10

2,04

Х1 = 1,22

Х2 = -0,67

Х3 = 0,35

11



-9,7

13,1

6,9

25,1

Х1 = -0,72

Х2 = 1,88

Х3 = -0,92

Х4 = -1,94

12



-6,66

-3,58

-5,01




13



-1,97

-3,69

-5,98




14



1,9

9,7

-1,4

Х1 = 0,248

Х2 = 1,114

Х3 = -0,224

15



26

7

7

Х1 = 3

Х2 = 1

Х3 = 1

16



7

-5

-14

Х1 = 0

Х2 = -1

Х3 = 2

17



15

-11

1

Х1 = 2

Х2 = -2

Х3 = 1

18



6

-1

-1

3

Х1 = 1

Х2 = -1

Х3 = 1

Х4 = -1

19



-8

-1

-6

7

Х1 = -1

Х2 = 2

Х3 = 0

Х4 = 3

20



2,05

0,80

-1,07

Х1 = 1,12

Х2 = -0,341

Х3 = -0,008

21



-0,16

0,50

0,95

Х1 = 0,008

Х2 = -0,231

Х3 = 0,042



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

Основні поняття та визначення



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

(2.1)

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

В матричному вигляді рівняння (2.1) прийме вигляд: , де ={} – вектор невідомих; ={} – вектор вільних членів; ={} – матриця коефіцієнтів СЛАР.

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

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

Дві системи називаються еквівалентними, якщо ці системи сумісні, визначені і мають однаковий розв’язок.

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

Класифікація методів розв’язання СЛАР на ЕОМ


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

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

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

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

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






Рисунок 2.1 – Класифікація чисельних методів

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


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

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

(2.2)

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

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

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


Метод Гауса з послідовним виключенням невідомих (базовий метод)засновано на алгоритмі, в основі якого лежить послідовне виключення невідомих вектора з усіх рівнянь, починаючи з (і+1) го, шляхом елементарних перетворень: перемноження обох частин рівняння на будь-яке число, крім нуля; додавання (віднімання) до обох частин одного рівняння відповідних частин другого рівняння, помножених на будь-яке число, крім нуля.

Суть алгоритму розглянемо на прикладі системи, яка складається з трьох лінійних алгебраїчних рівнянь з трьома невідомими:

(2.3)

  1. Перевіримо, щоб принаймні один із коефіцієнтів , , не дорівнював нулю. Якщо, наприклад, , тоді необхідно переставити рівняння так, щоб коефіцієнт при x1 у першому рівнянні не дорівнював нулю.

  2. Обчислюється множник:

. (2.4)

  1. Перше рівняння системи (2.3) множиться на і віднімається від другого рівняння системи, отриманої після перестановки рівнянь, якщо вона була необхідною. Результат обчислення має вигляд:

, (2.5)

Але . (2.6)

Тоді виключається із другого рівняння.

Позначимо нові коефіцієнти:

(2.7)

Тоді друге рівняння системи (2.3) набуває вигляду:

. (2.8)

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

  1. Обчислюється множник для третього рівняння:

. (2.9)

  1. Перше рівняння системи (2.3) множиться на і віднімається від третього рівняння. Коефіцієнт при стає нулем, і третє рівняння набуває вигляду:

, (2.10)

Де , (2.11)

, (2.12)

. (2.13)

Перетворена таким чином система рівнянь (2.3) набуває вигляду:

(2.14)

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

7) Обчислюємо множник . (2.15)

8) Друге рівняння системи (2.11) помножується на і віднімається від третього рівняння:

. (2.16)

При цьому коефіцієнт біля дорівнює нулю:

, (2.17)

, (2.18)

, (2.19)

Отримаємо . (2.20)

Замінивши в системі (2.14) третє рівняння на (2.20), отримаємо систему рівнянь виду:

(2.21)

Таку систему називають системою з трикутною матрицею коефіцієнтів, що еквівалентна СЛАР (2.3). Процес знаходження такої системи називається прямим ходом Гауса. Знайти розв’язок такої системи просто: із 3 го рівняння знайти , підставити результат у друге і знайти , підставити і в 1 е рівняння системи (2.21) і знайти за формулами:

, (2.22)

, (2.23)

. (2.24)

Процес знаходження вектора розв’язку системи (2.3) називають зворотнім ходом метода Гауса . На рисунку 2.2 показана схема алгоритму метода Гауса з послідовним виключенням для розв’язання системи із N рівнянь з N невідомими. Ця схема відповідає розглянутому алгоритму і може бути використана при розробці програми. Блок “Перестановка рівнянь так, щоб ” означає деякий алгоритм, який дає змогу не допустити помилки “ділення на 0”. Якщо прямувати до можливого зменшення помилок округлення, то можна використати алгоритм з вибиранням головного елементу.



Рисунок 2.2 – Схема алгоритму розв’язання системи лінійних алгебраїчних рівнянь методом Гауса.

Призначення індексів в схемі алгоритму (рисунку 2.2):


к – номер рівняння, яке віднімається від інших, а також номер невідомого, яке виключається із залишених к-рівнянь;


i – номер рівняння, із якого в даний момент виключається невідоме;


j – номер стовпця.


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



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


(2.25)

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


1) в системі (2.1) необхідно знайти з k го стовпця найбільший за абсолютним значенням коефіцієнт ak j ;


2) переставити k те рівняння з рівнянням у якому знаходиться цій максимальний коефіцієнт;


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


Схема алгоритму метода Гауса з вибором головного елемента (прямий та обернений хід) показана на рисунку 2.3.





Рисунок 2.3 – Схема алгоритму метода Гауса з вибором головного елемента

Метод Гауса з одиничними коефіцієнтами


В цьому методі зроблена спроба зменшити недоліки перших двох методів пов’язаних з багаторазовим діленням одного наближеного числа на інше. Для цього перед введенням масштабного множника k - те рівняння системи ділиться один раз на діагональний елемент так, щоб коефіцієнт при , а масштабний множник Мі буде дорівнювати ak j. Результатом прямого ходу є система, еквівалентна СЛАР (2.1), з одиничними коефіцієнтами на головній діагоналі виду:

(2.26)

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



  1. Організація циклу по всім рівнянням від 1 до N-1 (k = 1, 2, …, N-1).

  2. В кожному k-му стовпці визначається номер l-го рівняння з головним елементом (тобто номер l -го рівняння, в якому знаходиться коефіцієнт при зі всіх рівнянь починаючи з k-го до N-го).

  3. Якщо номер цього рівняння l не дорівнює k (l<>k), тоді необхідно переставити місцями l-е рівняння з k-м.

  4. Нормування k-го рівняння, тобто ділення всіх коефіцієнтів k-го рівняння на (головний елемент при ), включаючи .

  5. Перетворення всіх і-х рівнянь, починаючи з (k+1) до N у відповідності з базовим алгоритмом Гауса з метою отримати еквівалентну систему з верхньою трикутною матрицею коефіцієнтів.

  6. Кінець циклу по k.

Формула зворотного ходу для систем виду (2.26) спрощується і має вигляд:

(2.27)

Схема алгоритму методу Гауса з одиничними діагональними коефіцієнтами наведена на рисунку 2.4.



Рисунок 2.4 – Схема алгоритму метода Гауса з одиничними коефіцієнтами

Приклади розв’язання СЛАР точними методами в середовищі MathCAD


Для розв’язання СЛАР точними методами в середовищі MathCAD використовуються наступні функції:

augment(A,B)формує матрицю, в перших стовпцях якої міститься матриця А, а в останніх – матриця В (матриця А і В повинні мати однакове число рядків);

submatrix(A,ir,jr,ic,jc) формує матрицю, яка є блоком матриці А, яка розташована в рядках з ir по jr і в стовпцях з ic по jc, irjr, icjc;

norm1(A),norm2(A),norme(A),normi(A) – обчислення норм квадратної матриці А;

rref(А) – зведення матриці до ступінчатого вигляду з одиничним базисним мінором;


lsolve(A,b) –розв’зок системи лінійних рівнянь Ax=b

Розв’язання лінійної системи методом Гауса



В MathCAD прямий і зворотній ходи методу Гауса виконує функція rref(A).

Нижче поданий фрагмент робочого документу MathCAD, який містить розв’язання методом Гауса системи трьох лінійних алгебраїчних рівнянь відносно трьох невідомих.

Задамо матрицю системи А і праву частину b



Сформуємо розширену матрицю системи Ag додаванням до матриці системи праворуч стовпця правих частин



Зведемо розширену матрицю системи Ag до ступінчатого вигляду. Функція rref(A) зводить розширену матрицю системи до ступінчатого вигляду, виконуючи прямий та зворотній хід Гаусового виключення:



Виділимо блок матриці Ag – її останній стовпець, який містить розв’язання системи:



Перевіримо правильність розв’язання:



Розв’яжемо систему за допомогою функції lsolve і порівняємо з розв’язком, що отриманий методом Гауса:


Література


1. Щуп Т. Решение инженерных задач на ЕВМ. – М.: Мир, 1982. – 235с.

2. Демидович Б. П., Марон И. А. Основы вычислительной математики. – М.: Наука, 1970. – 664 с.

3. Демидович Б. П., Марон И. А., Шувалова Е. З. Численные методы анализа. – М.: Мир, 1967

4. Мак – Кракен Д., Дрон У. Численные методы и програмирование на фортране. – М.: Мир, 1977. – 584 с.

5. Бахвалов Н. С. Численные методы . Т. И. Анализ, алгебра, обычные диференциальные уравнения. – М.: Наука, 1975. – 631 с.

Контрольні питання


  1. Дати визначення слідуючи термінів: розв’язання СЛАР, визначена і

невизначена, вироджена, співмісцева і неспівмісцева СЛАР.

  1. Класифікація методів розв’язання СЛАР.

  2. Суть точних методів розв’язання СЛАР.

  3. У яких випадках краще використовувати точні методи?

  4. Суть алгоритму методу Гауса розв’язання СЛАР.

  5. У чому різниця між алгоритмами методів Гауса з послідовним

виключенням невідомих і з вибранням головного елементу; що спільного?

  1. У чому суть методу Гауса за схемою Халецького?

  2. Порівняйте алгоритми методів Гауса з вибиранням головного елементу і за схемою Халецького. Обчислення за яким з цих алгоритмів швидше? Який із алгоритмів ефективніший?

  3. В чому суть методу Гауса за схемою Халецького?

  4. Яку систему отримано в результаті прямого ходу методу Гауса-Жордана?

  5. Дати визначення слідуючим термінам: розв’язання СЛАР, норма матриці, норма вектора, достатня умова сходження.

  6. Привести СЛАР: 9,9х1 -1,5х2+2,6х3=0;

0,4х1+13,6х2-4,2х3=8,2;

0,7х1+0,4х2+7,1х3=-13;

до нормального вигляду.

Схожі:

Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом iconКод модуля: ес 6032 С01 Тип модуля: обов’язковий Семестр
Числові методи розвязання систем лінійних скінчених рівнянь. Числові методи розв’язання систем нелінійних скінчених рівнянь. Математичні...
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом iconПрограма з курсу "Вища, математика" Матриці. Визначники матриць. Системи рівнянь першої степені
Розв'язок системи "n" рівнянь з "n" невідомими, правило Крамера. Розв'язок І дослідження систем рівнянь першої степені методом повного...
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом iconРозв’язування систем лінійних алгебраїчних рівнянь
...
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом icon§5 Розв'язок систем n рівнянь із n невідомими
Встановивши основні властивості І способи обчислення визначників матриць будь-якого порядку, повернемося до основної задачі розв'язку...
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом icon§5 Розв'язок систем n рівнянь із n невідомими
Встановивши основні властивості І способи обчислення визначників матриць будь-якого порядку, повернемося до основної задачі розв'язку...
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом iconРозв'язати систему лінійних алгебраїчних рівнянь за правилом Крамера

Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом icon1 Основні класи сучасних паралельних комп'ютерів
Розділ Сучасні високопродуктивні обчислювальні системи та паралельні методи розв'язання систем звичайних диференційних рівнянь
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом icon1 Основні класи сучасних паралельних комп'ютерів
Розділ Сучасні високопродуктивні обчислювальні системи та паралельні методи розв'язання систем звичайних диференційних рівнянь
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом iconЛабораторна робота №3. 1 Одношаровий персептрон Мета
Мета: отримати навички розв’язання практичних задач за допомогою одношарового персептрона
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом icon1. Матриці та основні операції з матрицями. Визначники матриць. Системи рівнянь першого ступеня: правило Крамера. Метод повного виключення. Обернена матриця. Розвязання матричних рівнянь
Тема Матриці та основні операції з матрицями. Визначники матриць. Системи рівнянь першого ступеня: правило Крамера. Метод повного...
Лабораторна робота №2 (Частина 1) розв’язання систем лыныйних алгебраїчних рівнянь на еом iconСекція математичного аналізу та диференціальних рівнянь
Про асимптотичне розвинення розв’язків сингулярно збурених систем диференціальних рівнянь з виродженнями під точками повороту
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи