Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Лабораторна робота №5. Рішення систем лінійних алгебраїчних рівнянь методом Гауса

1. Мета роботи

Освоєння методу рішення систем лінійних алгебраїчних рівнянь. Вивчення та використання прикладних програм із бібліотеки програм ХТФ ОНПУ.

 

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

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

 

a11×x1 + a12×x2 +.....+ a1n×xn = b1

a21×x1 + a22×x2 +.....+ a2n×xn = b2

...................................................

an1×x1 + an2×x2 +.....+ ann×xn = bn

 

(2.1)

чи у матричному вигляді

A X = В, (2.2)

де

А = (aij) = матриця коефіцієнтів, , – стовпець вільних членів та стовпець невідомих відповідно.

Коефіцієнти системи (2.1) характеризуються двома індексами. Перший індекс – і визначає номер строки, другий – j – номер стовпця.

Рішення системи (2.1) складається зі знаходження таких значень невідомих, при підстановці яких у висхідну систему кожне з рівнянь перетворюється у тотожність.

Якщо матриця A неособлива , то

det A = 0

та система (2.1) має одиничне рішення.

Способи рішення систем лінійних рівнянь (СЛР) у основному діляться на дві групи .

1. Точні методи, які являють собою кінцеві алгоритми для обчислювання коренів системи (правило Крамера, метод Гауса, метод головних елементів, метод квадратних коренів та інші).

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

2.1. Метод Крамера

Значення невідомих xi (i = 1,2,...,n) можуть бути одержані по формулам Крамера:

xi = ,

де матриця Аi визначається з матриці А заміною i-того стовпця стовпцем вільних членів.

Такий спосіб рішення лінійних систем із n невідомими приводить до обчислювання n+1 детермінанту порядку n, що представляє собою дуже складну операцію при якомусь великому числі n.

 


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

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

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

Метод Гауса полягає у наступному:

1. З усіх рівнянь, крім першого, виключаються члени, які містять x1. Для цього з другого, третього,....., n-го рівнянь системи почленно, включаючи праві частини, віднімаються перше рівняння, поділене на а11 та помножене відповідно на а21, а22, а23,....., аn1. У результаті цієї операції порядок усіх рівнянь, за виключенням першого, понижується на одиницю.

2. Знову отримане друге рівняння ділиться на а22121121 та аналогічним способом, починаючи з третього рівняння, виключаються усі елементи, які містять х2.

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

4. Рішення ступінчатої системи рівнянь здійснюється шляхом послідовного обчислювання невідомих, починаючи з останнього рівняння.

 

ПРИКЛАД: Для визначення вмісту компонентів початкової суміші необхідно вирішити наступну систему рівнянь:

2,0 × x1 + 1,0 × x2 – 0,1 × x3 = 3,7 0,4 × x1 + 0,5 × x2 – 4,0 × x3 = 13,4 0,3 × x1 – 1,0 × x2 + 1,0 × x3 = 1,3

Для вирішення системи використовуємо метод Гауса. З другого та третього рівняння виключимо члени, які містять х1. Для цього спочатку поділимо перше рівняння на а11 = 2,0. Отримаємо:

х1 + 0,5× x2 – 0,05 – x3 = 1,85

Потім, помножимо отримане рівняння на а21 та а31, віднімемо з другого та третього рівнянь відповідно. Таким чином отримаємо систему з двома невідомими:

0,3 × x2 + 4,02 × x3 = 12,66

––1,15 × x2 + 1,015 × x3 = 0,745

Поділив перше рівняння отриманої системи на а22 та помножив його на а32, вирахуємо з другого рівняння цієї системи.

16,425 × x3 = 49,275

Таким чином, еквівалентна система має вигляд:

x1 + 0,5 × x2 – 0,05 × x3 = 1,85

x2 + 13,4 × x3 = 42,2

16,425 × x3 = 49,275

З отриманої еквівалентної системи послідовно знайдемо:

x3 = 3,0

x2 = 42,2 – 13,4 × 3,0 = 2,0

x1 = 1,85 – 0,5 × 2,0 + 0,05 × 0,3 = 1,0

Процес побудування еквівалентної трикутної системи називається прямим ходом, а процес знаходження значень невідомих – зворотнім ходом.

 

2.3. Блок-схема програми для рішення систем лінійних рівнянь методом Гауса

Блок-схему програми можна поділити умовно на три частини. Перша – реалізує алгоритм виключення невідомих; друга – зворотну підстановку; третя – визначає найбільший коефіцієнт при х та переставляє рівняння при необхідності.

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

При аналізі блок – схеми треба чітко представити зміст індексів i, j, k:

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

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

j – означає номер стовпця.

Блок-схема послідовного виключення невідомих представлена на рис. 2.1.

Зворотна підстановка для находження значення невідомих задається наступними формулами:

x n = ;

xn–1 = ;

......................................

xj =

для j = n–2, n–3, ..., 1.

Блок-схема зворотного ходу представлена на рис. 2.2. Помітимо, що у блок–схемі (рис. 2.1) усі індекси у процесі обчислювання збільшуються, а у блок-схемі (рис. 2.2) один з індексів, а саме i, зменшується.

Рис. 2.1. Блок-схема послідовного виключення невідомих

 

 

 

Рис. 2.2. Блок-схема зворотної підстановки

 

Розглянемо третю блок-схему перестановки рівнянь, яка входить у блок–схему (2.1). Завдання знаходження найбільшого коефіцієнта при xk та перестановці рівнянь при необхідності пов'язана зі зменшенням помилки округлення, яка виникає при обчислюванні з числами з плаваючою комою. По-перше, перестановка може бути потрібна, для того щоб akk ¹ 0 (щоб ухилитися від ділення на 0). А також, використовуючи перестановку, можливо зменшити помилку округлення.

 

Спочатку розглянемо числовий приклад. Розв'яжемо систему:

3,241×102 × x1+1,600×102 × x2 = 1,632×102

1,020×104 × x1+1,540×103 × x2 = 1,174×104

Точне рішення цієї системи наступне:

x1=1,000×100 ; x2=1,000×100 .

Вирішимо ці рівняння методом виключення у тому порядку, у якому вони записані, використовуючи при обчисленні числа з 4 значущими цифрами у мантисі. Так як а11¹ 0, то можна рішити по відомій схемі.

Перший та єдиний множник:

m = 1,020×104 / 3,241×100 = 3,147×103

Перетворене друге рішення має вигляд:

5,730×10–1 × x1 – 5,020×105 × x2 = –5,019×105

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

x2 = –5,019×105 / –5,020×105 = 9,998×10–1

З першого рівняння одержуємо:

x1 = 9,873×10–1.

Зараз підставимо рівняння так, щоб максимальний по модулю елемент попав на головну діагональ:

1,020×104 × x1 + 1,540×103 × x2 = 1,174×104

3,241×100 × x1 + 1,600×102 × x2 = 1,632×102

Зараз множник

m = 3,241×100 / 1,020×104 = 3,177×10–4

Перетворене друге рівняння:

0,000 × x1 + 1,595×102 × x2 = 1,595×102

Звідки x2 = 1,000×100 ; x1=1,000×100.

 

У цьому прикладі коефіцієнти дуже відрізняються по величині, але частіше ця різниця не так велика. Однак при рішенні великої системи рівнянь помилки округлення можуть накопичуватися та відповіді можуть не містить ні одної вірної цифри. Тому при рішенні СЛР на ЕОМ методом виключення повинно передбачити можливість перестановки рівнянь.

Отже, завдання зводиться до перестановки n–k+1 останніх рівнянь так, щоб найбільший по модулю коефіцієнт при xk попав на головну діагональ. Описаний спосіб рішення СЛР називають методом головного елементу.

При розгляданні блок–схеми необхідно пам'ятати, що при переході до даного етапу індекс k, що обчислюється, має деяке визначене значення, а i = k+1 (дивись рис. 2.3).

1. Спочатку у програму вводиться допоміжний індекс l, якому надається значення k.

2. Перше порівняння робиться між елементом акl, який лежить на головній діагоналі, та наступним за ним aik. Якщо |aik|>|alk|, то індексу l надають значення i та подальше порівняння виконується з другим елементом.

 

Рис. 2.3. Блок–схема перестановки рівнянь

Тому індекс l являється номером елементу, який з'явився при порівнянні більше двох елементів по модулю. Індекс і пробігає за ходом програми значення від k+1 до n включно, та у кінці цього циклу індекс l визначає номер найбільшого по модулю елементу у k-ому стовпці. При перестановці рівняння цей коефіцієнт повинен попасти на головну діагональ.

Може статися так, що значення аік вже являється найбільшим по модулю елементом. Тому така можливість відразу перевіряється і в такому випадку перестановка не проводиться.

Фактично процес полягає у перестановці коефіцієнтів, один з яких утримується у рівнянні k, а другий – у рівнянні l, яким би не було значення l.

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

Перед поверненням до основного процесу обчислювань необхідно відновити первісне значення індексу і, який було використано при порівнянні. Так як перед початком процесу індекс і мав значення k+1, то наприкінці блоку йому надається попереднє значення i = k+1.

 

 

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...