Розробка програмного забезпечення для розв'язку СЛАР методом Гауса (стр. 2 из 3)

a11x1 + a12x2 +…+ a1nxn = b1,

a22x2 +…+ a2nxn = b2,

…………………………….

annxn = bn,

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

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

Є багато реалізацій методу Гаусса з певними перевагами обчислення. Наприклад, у схемі з вибором головного елемента послідовність вилучення визначають під час обчислення.

Схема єдиного ділення. Опишемо метод Гаусса для розв’язування системи лінійних рівнянь загального вигляду:

a11x1 + a12x2 +…+ a1nxn = a1,n+1,

a21x1 + a22x2 +…+ a2nxn = a2,n+1,

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

an1x1 + an2x2 +…+ annxn = an,n+1.

Виберемо a11

0 як провідний елемент і поділимо на нього перше рівняння. Дістанемо

x1 + a12

x2+…+ a1n xn = a1,n+1 ,

a1k

= a1k a11, k=2,3,...,n.

Вилучимо x1 з усіх рівнянь системи, крім першого. Для цього помножимо перетворене перше рівняння на -a21 і додамо його до другого. Аналогічно вилучаємо x1 з третього рівняння і т. ін. Помножимопершерівняння на -an1 і додамо його до останньго, вилучимо x1 з n-го рівняння. На цьому перший крок гауссового вилучення завершено. Початкова система матиме еквівалентний вигляд:

x1 + a12

x2+…+ a1n xn = a1,n+1 ,

a22

x2+…+ a2n xn = a2,n+1 ,

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

an2

x2+…+ ann xn = an,n+1 .

де aij

= aij- ai1 a1j , j=2,3,...,n+1.

На другому кроці, припустивши, що провідний елемент a22

0, вилучимо невідомеx2 з усіх рівнянь, починаючи з третього.

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

а)

б)

У випадку а) система має єдиний розв’зок, який легко знайти шляхом послідовного вилучення невідомих, починаючи з xn, за формулами:

pascal рівняння лінійний програма гаус

Цей випадок можливий, коли всі рівняння системи лінійно незалежні, тобто визначник матриці коефіцієнтів біля невідомих не дорівнює нулю. Крім того, всі провідні елементи a11, a22

, ..., ann також відмінні від нуля. Остання умова завжди виконуватиметься, якщо матриця системи має властивість діагонального перевантаження, тобто

або відмінні від нуля головні мінори матриці.

У випадку б) система несумісна, коли хоча б одне з чисел сr+1,n+1,...,сn,n+1не дорівнює нулю. Якщо всі елементи сr+1,n+1,..., сn,n+1 дорівнюють нулю, то система має нескінченну множину розв’язків. Невідомі xr+1,...,xn можуть набирати будь-яких значень, а з перших r рівнянь перетвореної системи подано послідовно xr,xr-1,...,x1 через вільні невідомі xr+1,...,xn. У цьому разі система має r лінійно незалежних рівнянь, а решта є їх наслідками.

Схема єдиного ділення полягає у використанні однотипних дій, які легко програмувати на сучасних ЕОМ. Метод Гаусса надзвичайно ефективний також за кількістю арифметичних дій. Кількість множень і ділень у прямому перерізі методу має порядок O(n), де n – кількість рівнянь у системі. У зворотному перерізі цей порядок становить O(n

).

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

1.3Вхідна інформація

В програмі описаний тип mas1, який являється масивом дійсних чисел максимальної розмірності 50 на 51.

Для введення коефіцієнтів при невідомих і вільних членів в програмі описано матрицю а. Розмірність цієї матриці має тип integer, але її значення обмежене програмою – залежить від кількості рівнянь. Елементи матриці мають такий тип, як і матриця, до якої вони належать.

Показник	Ідентифікатор	Значність	Тип
матриця а	a	mas1
висота матриці а	n	1..50	integer
ширина матриці а	n+1	1..51	integer
елемент матриці а	a[i,j]	real

1.4Вихідна інформація

В програмі описаний тип mas2. Цей тип являється одновимірним масивом дійсних чисел розмірності 50. Матриця x формується в результаті перетворень над матрицею а і обчислень всередині програми.

Показник	Ідентифікатор	Значність	Тип
матриця x	a	mas1
розмірність матриці x	n	1..50	integer
елемент матриці x	a[i,j]	real

2.Практична частина

2.1Архітектура програми

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

Vvid

Mriv

Dil

Nkoef

Nevid

Result

Текст програми (Додаток ), блок-схеми всіх процедур і головної програми подані в додатках.

Процедура vvid призначена для введення кількості рівнянь, коефіцієнтів при невідомих і вільних членів (Додаток ).

Процедура mriv призначена для того, щоб поміняти провідне рівняння, якщо провідний коефіцієнт рівний нулю, на те, де ведучий коефіцієнт відмінний від нуля. Це рівняння автоматично стає ведучим (Додаток ).

Процедура dil призначена для ділення коефіцієнтів провідного рівняння на провідний коефіцієнт (Додаток ).

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

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

Процедура vuvidпризначена для виводу на екран результатів виконання програми (Додаток ).

Головна програма призначена для виклику процедур. Спочатку викликається процедура vvid. Процедури mriv, dil, nkoef викликаються в циклі, кількість повторень якого на одиницю менше від кількості рівнянь. На цьому прямий хід розв’язку системи лінійних рівнянь методом Гаусса закінчується.

Після цього викликається процедура nevid, яка реалізує зворотній хід розв’язку системи – пошук невідомих (Додаток ).

Останньою викликається процедура vuvid (Додаток ).

2.2Опис програми

{01} Назва програми;

{02} підключення модуля crt;

{03} службове слово для опису типів;

{04} опис двовимірного масиву дійсних чисел mas1;

{05} опис одновимірного масиву дійсних чисел mas2;

{06} службове слово для опису змінних;

{07} опис змінної a;

{08} опис змінної x;

{09} опис змінних b,c,d,r;

{10} опис змінних i,j,n,k,m;

{11} - {22} Процедура вводу коефіцієнтів і вільних членів

{11} заголовок процедури, опис змінних;

{12} початок процедури;

{13} вивід повідомлення „введіть кількість рівнянь n=”;

{14} оператор вводу кількості рівнянь;

{15} вивід повідомлення „введіть коефіцієнти і вільні члени”;

{16} оператор циклу;

{17} оператор циклу;

{18} командна дужка „begin”;

{19} вивід повідомлення;

{20} оператор вводу коефіцієнтів і вільних членів;

{21} командна дужка „end”;

{22} кінець процедури;

{23} - {36} Процедура зміни рівнянь місцями

{23} назва процедури, опис змінних;

{24} початок процедури;

{25} перевірка умови;

{26} оператор циклу;

{27}командна дужка „begin”;

{28} оператор циклу;

{29} оператор циклу;

{30} командна дужка „begin”;

{31} - {33} зміна коефіцієнтів місцями між даним і наступним

рядком через третю змінну r;

{31}змінній r присвоюється значення дане значення коефіцієнта;

{32} даному значенню коефіцієнта присвоюється значеннянаступного рядка;

{33} значенню коефіцієнта наступного рядка присвоюєтьсязначення змінної r;

{34} командна дужка „end”;

{35} командна дужка „end”;

{36} кінець процедури;

{37} - {43} Процедура ділення рівняння на провідний коефіцієнт;