Метод Жордана Гаусса

Зміст

Вступ

1. Теоретична частина

1.1 Постановка задачі

1.2 Методи розв'язування задачі

1.3 Алгоритм розв'язку задачі

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

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

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

2.3 Контрольний приклад та результат машинного експерименту

Висновок

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

Додатки

Вступ

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

На сьогодні існує велика кількість різноманітних мов програмування, кожна з яких має свої певні переваги та недоліки. В цьому розмаїтті не завжди легко зробити свій вибір на користь якоїсь певної мови програмування.

Для реалізації поставленої задачі вибрано середовище Turbo Pascal. Алгоритмічна мова Паскаль була створена Н.Віртом на початку 70-х років. Завдяки зусиллям розробників ця мова програмування стала потужним інструментом професійних програмістів‚ не втративши простоти і ясності, властивих цій мові від народження.

Розробник системи Turbo Pascal - фірма Borland International виникла в 1984 році і за порівняно короткий час неодноразово дивувала користувачів персональних ЕОМ своїми Turbo системами. Було випущено кілька версій Turbo Pascal: 3.0‚ 4.0‚ 5.0‚ 5.5‚ 6.0‚ 7.0‚ Pascal for Windows, Borland Pascal.

Головні особливості середовища Turbo Pascal:

широкий спектр типів даних‚ можливість обробки рядкових та структурних типів даних;

достатній набір операторів управління розгалуженнями та циклами;

добре розвинутий апарат підпрограм та зручні конструкції роботи з

файлами;

великі можливості управління усіма ресурсами ПЕОМ;

різноманітні варіанти стикування з мовою Асемблера;

підтримка ідей об'єктно-орієнтованого програмування (ООП).

Саме з огляду на ці особливості програмна реалізація курсового проекту було здійснено в середовищі Turbo Pascal.

Курсовий проект складається зі вступу, двох розділів, висновків, списку використаної літератури, графічної частини та додатків. Текст пояснювальної записки набрано та роздруковано з використанням текстового редактора Word. Графічна частина виконана з допомогою графічного редактора Visio.

1. Теоретична частина

1.1 Постановка задачі

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

(I=1.2…..n) (1)

Систему (1) можна записати у вигляді одного матричного рівняння

AX=B, (2)

де

матриця коефіцієнтів (індекс і вказує рівняння, якому належить коефіцієнт, а індекс j - змінну, при якій він стоїть),

,

відповідно стовпець вільних членів і стовпець змінних.

Упорядкована сукупність п чисел , яка, будучи підставленою в систему (1) замість , перетворює всі рівняння в правильні числові рівності, називається розв'язком системи (1)

Методи розв'язування систем лінійних рівнянь можна поділити на дві групи: точні й ітераційні.

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

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

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

Якщо систему рівнянь у пам'яті машини записати навіть точно, то в процесі її розв'язування ЕОМ обов'язково виникнуть похибки округлень, які не можуть не вплинути на точність розв'язку. Проте, якщо матриця А системи (2) майже вираджена то можна сподіватися, що малі зміни в коефіцієнтах і (або) вільних членах також призведуть до значних змін у її розв'язку.

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

(3)

розв'язком якої є пара (1;0). Якщо число 6,1 у правій частині першого рівняння системи (3) змінити на 0,02, то система

матиме розв'язком пару (5,1;-7,35). Отже, мале збурення (меньше 0,33%) одного з вільних членів системи (3) зовсім змінило розв'язок системи.

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

1.2 Методи розв'язування задачі

Метод Жордана-Гаусса був розроблений двома вченими Жорданом та Гаусом (ві яких і пішла назва методу). Цей метод вони помітили після довгої практики роботи з системами рівнянь. Це можна пояснити складністю розв'язку цим методом.

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

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

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

шляхом вибору із системи певних елементів для обчислення визначника. Кількість обчислень таких визначників при розв'язуванні певної системи дорівнює:

де n - розмірність квадратної матриці (або кількість невідомих квадратної матриці).

1.3 Алгоритм розв'язку задачі

Розглянемо систему m лінійних рівнянь з n невідомими. Для методу Жордана-Гауса її зручно зобразити у вигляді такої таблиці:

Нехай потрібно виразити змінну з і-го рфвняння системи, а потім потрібно підставити отриманий вираз в усі інші рівняння системи. Таке перетворення системи називають кроком Жорданових виключень з основним елементом .

Такі перетворення зручно виконувати користуючись таблицею (1), яка перейде в іншц таблицю за слідуючими правилами:

Усі вільні елементи реально заданої системи лінійних алгебраїчних рівнянь, тобто стовпець замінюють на протилежні;

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

Інші елементи основного стовпчика j залишають без змін;

Інші елементи основного рядка і-го змінюють лише свої знаки;

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

а) елемента з цими ж індексами, що й в обчислювальному елементі;

б) основний елемент;

в) елемент, який є спільним для стовпця з елементом (а) і стовпця з елементом (б);

г) елемент, який є спільним для стовпця з елементом (б) і рядка з елементом (а).

Шуканий елемент обчислюється як добуток елементів (а) та (б) мінус добуток залишившихся елементів визначника.

Цю дію можна зобразити у вигляді формули:

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

Виконавши всі описані операції новостворена таблиця матиме вигляд:

Шукаючи невідомі системи лінійних алгебраїчних рівнянь продовжують виконувати операції 2...6, причому основним елементом вже не можна вибрати елемент jI рядка, в якому вже був при попередніх Жорданових виключеннях використаний елемент. Операції 2...6 продовжують мати, поки усі позначення рядків не будуть замінені позначеннями стовпців, тобто поки всі стовпці крім -го не будуть вилучені.

Шуканими елементами будуть елементи, які залишаться після всіх обчислень в рядках навпроти нових позначень даних рядків. Оскільки нові позначення рядків відповідають відповідним невідомим та елементи навпроти, будуть відповідати розв'язкам заданої системи. З обчислення випливає, що шукані невідомі опиняються в стовпці під позначенням стовпця вільних елементів.

З даного методу обчислення помітно, що для розв'язку система повинна мати одинакову кількість рядків і невідомих, бо в протилежному випадку невідомі буде важко чи навіть неможливо знайти (коли невідових більше чим рядків) даним методом.

Розв'язуючи систему вручну методом Жордана-Гауса, основним елементом зручно вибирати число на яке найменьше ділити і, зрозуміло, що неможливо вибирати 0. для полегшення розв'язку при обчисленні кожен рядок зокрема можна скорочувати.

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

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

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

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

Запустити дану програму можна наступними способами:

з головного меню середовища Turbo Pascal шляхом вибору опції Run/Run (спочатку програму потрібно завантажити в оперативну пам'ять);

з середовища Turbo Pascal нажиманням комбінації клавіш Ctrl+F9;

з середовища операційної оболонки Norton Commander шляхом запуску прграми Kursova.exe (попередньо програма повинна бути відкомпільована з опцією Destination to memory).

Програма Kursova.pas є продурноорієнтованою. До неї входять 7 наступних процедур:

ramka;

windo;

Страницы: 1, 2, 3