МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
З а п о р о ж с к и й г о с у д а р с т в е н и й т е х н и ч е с к и й у н і в е р с и т е т
Кафедра
__________________________
ПОЯСНЮВАЛЬНА ЗАПИСКА до курсового ПРОЕКТ
З ДИСЦИПЛІНИ ________________________________________ < p> ________________________________________________________
________________________________________________________
розроблено
ст. гр. РПЗ-538
Кригіна А. А.
Прийняв
викладач
Пінчук В.П.
2001р.
РЕФЕРАТ
ПЗ: стор
МЕТА РОБОТИ : розробити бібліотечні засоби рішення задач лінійноїалгебри.
ОБ'ЄКТ ДОСЛІДЖЕННЯ: класові типи - чисельна квадратна матриця іодновимірний динамічний масив із змінними розмірами.
МЕТОД ДОСЛІДЖЕННЯ: розробка алгоритмів і написання класів функцій намові Borland С ++.
У курсовому проекті розроблені алгоритми для вирішення основних завданьлінійної алгебри. За цим алгоритмам на мові Borland C + + написані двакласу функцій, орієнтованих на об'єкти типу чисельна квадратнаматриця і одновимірний масив (вектор). У класи включені арифметичніоперації, операції вводу-виводу, функції обчислення визначника матриці,довжини вектора, а також рішення системи лінійних алгебраїчних рівнянь.
Для наочності отриманих результатів розроблена демонстраційно -Тестуюча програма.
Результати курсового проекту можуть бути використані на практиці длярішення систем лінійних рівнянь та інших задач лінійної алгебри.
Список ключових слів:
Лінійна алгебра, МАТРИЦЯ, ВЕКТОР, системи лінійних рівнянь,
Визначник, ФУНКЦІЯ, КЛАС ФУНКЦІЙ, Об'єкт, ОПЕРАЦІЯ, ШАБЛОН, об'єктно-
ОРІЄНТОВАНЕ ПРОГРАМУВАННЯ.
ВСТУП
Об'єктно-орієнтоване програмування - це новий спосіб підходу допрограмування. Таке програмування, взявши кращі риси структурногопрограмування, доповнює його новими ідеями, які переводять у новеякість підхід до створення програм.
Найбільш важливе поняття мов об'єктно-орієнтованого програмування --це поняття об'єкта (object). Об'єкт - це логічна одиниця, якамістить дані і правила (методи) обробки цих даних. У мові С + + вяк таких правил обробки виступають функції, тобто об'єкт у Borland
C + + поєднує в собі характеристики та функції, що обробляють ці дані.
Одним з найголовніших понять мови С + + є поняття класу (class). Умові С + + для того, щоб визначити об'єкт, треба спочатку визначити йогоформу за допомогою ключового слова class [1].
Найближчою аналогією класу є структура. Пам'ять виділяється об'єктутільки тоді, коли клас використовується для його створення. Цей процесназивається створенням екземпляра класу (class instance).
Будь-який об'єкт мови С + + має однакові атрибути і функціональність зіншими об'єктами того ж класу. За створення своїх класів і поведінкуоб'єктів цих класів повну відповідальність несе сам програміст. Працюючив деякому середовищі, програміст дістає доступ до великих бібліотекстандартних класів.
Зазвичай, об'єкт знаходиться в деякому унікальному стані, що визначаєтьсяпоточними значеннями його атрибутів. Функціональність об'єктного класувизначається можливими операціями над екземпляром цього класу.
Шаблони, або параметризрвані типи, дозволяють конструювати сімействопов'язаних функцій або класів. Узагальнений синтаксис визначення шаблонумає виглядtemplate (оголошення);
Розрізняють шаблони функцій і шаблони класів.
Шаблон класів задає зразок визначень сімейства класів. Надтипізований елементами цього класу виконуються однакові базовіоперації незалежно від конкретного типу елементів [2].
Введення в об'єктно-орієнтоване програмування
Об'єктно-орієнтоване програмування являє собою трохибільш автоматизований спосіб програмування. Об'єктно-орієнтованіпрограми - це не просто процедурні програми, переведені на новийсинтаксис. Вони повинні будується на новій філософії розробки. Для нихпотрібна нова стратегія програмування, яку часто буває важкоосвоїти [3].
Основна ідея ООП: програма складається з групи об'єктів, частопов'язаних між собою. У С + + об'єкти описуються за допомогою нового типуданих class. Клас включає в себе набір змінних (даних) і операцій
(методів або функцій-членів), які діють на ці змінні.
Отриманими об'єктами можна керувати за допомогою повідомлень.
У ООП об'єкти включають в себе не тільки дані (дані-члени), а йметоди (функції-члени) впливу на ці дані. Ці дві частини в поєднанніутворюють функціональну одиницю програми. Іншими словами, об'єктимістять дані та методи роботи з цими даними. Нижче наведено триосновних переваги об'єктно-орієнтованих програм в порівнянні зеквівалентними програмами, розробленими зверху вниз.
. Супровід програми. Програми простіше читати і розуміти, ООП дозволяє керувати складністю програми, залишаючи видимими програмісту тільки істотні деталі.
. Модифікація програми (додавання або виключення можливостей). Ви можете часто робити доповнення або виключення в програмі, наприклад, при роботі з базою даних, просто додаючи і виключаючи об'єкти. Нові об'єкти можуть наслідувати всі властивості базових об'єктів, необхідно тільки додати або прибрати що відрізняються властивості.
. Повторне використання. Можна зберегти грамотно розроблений об'єкт в наборі корисних програм і потім вставити його в нову програму з невеликими змінами або без змін.
ООП повністю належить до світу С + +, оскільки в С немає основного ядра
- Абстрактного типу даних class [5]. Тому переписати процедурно -орієнтовану програму як об'єктно-орієнтовану набагато складніше, ніжпросто підставити замість одного ключового слова іншого.
ООП представляє собою техніку програмування, яка дозволяєрозглядати основні ідеї як безліч об'єктів. Використовуючи об'єкти,можна представити завдання, які необхідно виконати, їх взаємодіяі будь-які поставлені умови, які повинні бути дотримані. Структура данихчасто утворює основи об'єктів; таким чином у С або С + + тип struct можеутворювати елементарний об'єкт. Зв'язок з об'єктом можна організувати придопомоги повідомлень. Використання повідомлень схоже на виклик функцій упроцедурно-орієнтованої програми. Коли об'єкт отримує повідомлення,вступають в дію методи, що містяться в об'єкті. Методи (їх інодіназивають Функція-членами) аналогічні функціям процедурно-орієнтованогопрограмування. Проте метод є частиною об'єкта, а не чимосьокремим, як було б у процедурному аналогу.
Основні терміни та положення ООП
Інкапсуляція даних
Цей термін включає в себе логічне зв'язування даних з конкретноюоперацією. Вона так само означає, що вони є не-глобальними доступнимивсій програмі, а локальними - доступними тільки малої її частини.
Інкапсуляція також автоматично передбачає захист даних. Саме дляцього призначена структура class в С + +. У класі управлінняфункціональними деталями об'єкта здійснюється за допомогою специфікаторprivate, public, protected.
Ієрархія класів
У загальному випадку можна уявити собі ієрархію класів як родовідв генеалогічному дереві, де клас С + + представляє собою шаблон длястворення класів-нащадків. Об'єкти, отримані з опису класу, називаютьпримірниками цього класу. Можна створити ієрархію класів з класом -батьком і декількома класами-нащадками. Основою для цього єпохідні класи.
Спадкування
Спадкування в ООП дозволяє класу отримувати совйства іншого класуоб'єктів. Батьківський клас є шаблоном для похідного класу; цейшаблон можна змінювати різними способами. Спадкування є важливимстановищем, оскільки воно дозволяє повторно використовувати визначеннякласу без значних змін в коді.
Поліморфізм
Будується на описаної вище концепції наслідування. Програма посилаєодне і теж повідомлення як об'єкту батьківського класу, так і всіх об'єктахпохідних класів. І батьківський клас, і класи-нащадки дадуть відповідь наповідомлення відповідним чином. Поліморфізм дає можливість доповнювативже існуючі частини програми.
Віртуальні функції
Віртуальні функції визначаються в батьківському класі, а впохідних класах відбувається довизначення цих функцій і для нихстворюються нові реалізації. Під час роботи з віртуальними функціями повідомленняпередаються як покажчики, які вказують на об'єкт замість прямоїпередачі об'єкта. Віртуальні функції використовують таблицю для адресноїінформації. Ця таблиця ініціалізується під час виконання за допомогоюконструктора.
Конструктор викликається кожного разу, коли створюється об'єкт його класу.
Завдання конструктора в даному випадку полягає в зв'язуванні віртуальноїфункції з таблицею адресної інформації. Під час компіляції адресавіртуальної функції невідомий; натомість їй відводиться позиція в таблиціадрес. Ця позиція буде містити адресу функції [5].
Глава 2. Задачі лінійної алгебри
2.1. Обчислення визначників
Нехай маємо квадратну матрицю розміром n (n:
. (2.1.1)
Потрібно обчислити визначник матриці det (A).
еквівалентним перетворенням матриці називають перетворенняматриці, що не змінюють величину визначника матриці. Еквівалентнимє наступне перетворення: будь-яку її рядок можна замінитисумою вихідної рядки і будь-який інший, помноженої на будь-яке число, не рівненулю.
Використовуючи такого роду перетворення можна спробувати привести ис -Ходна матрицю до Трикутному увазі:
,при цьому det (A) = det (A ().
Формула для перерахунку елементів матриці має вигляд:
, (2.1.2)де i - номер стовпця, в якому елементи, що лежать нижче головною
діагоналі, перетворюються на нулі; j - номер елемента в оброблюваному стовпці (тобто номер рядка); k - номер елемента в поточному рядку.
Алгоритм приведення матриці до Трикутному увазі включає в себе 3вкладених циклу:
- зовнішній цикл, i = 1 .. n-1;
- середній цикл, j = i +1 .. n;
- внутрішній цикл, k = i +1 .. n.
Тепер шуканий визначник обчислюється як добуток діагональ -них елементів:
.
Описаний вище алгоритм дає результат не завжди. Якщо при виконанні -нии i-того кроку зовнішнього циклу діагональний елемент aii виявляється рав-вимнулю, а серед елементів i-того стовпця з номерами від i +1 до n є хоча бодин не нульовий, алгоритм завершується безрезультатно (через невозмож-ностіобчислень за формулою (2.1.2). Для того, щоб це не відбувалося,використовується прийом, який називається «вибір головного елементу».
При виконанні чергового кроку циклу по i попередньо виконують-сянаступні операції:
1) знаходиться максимальний по модулю елемент серед елементів i-то-гостовпця від aii до ani;
2) якщо знайдений елемент ali дорівнює нулю, процес обчислення завер -щує з видачею результату det (A) = 0;
3) якщо l (i, тоді рядки вихідної матриці з номерами i, lпоміняти місцями.
Після завершення перетворення матриці, визначник обчислюється заформулою:
,де p - кількість виконаних операцій зміни рядків місцями.
2.2 Звернення матриць
Зворотному до матриці A називається матриця A-1, яка має властивість:
A (A -1 = A-1 (A = I,де I - одинична діагональна матриця. Опишемо один з універсальних іефективних методів розрахунку оберненої матриці (метод Жордана-Гаусса, у книзі
[4-218] описаний як «метод винятків»). В [5-22] наведено більш ефек -бництва по пам'яті алгоритм звернення матриці.
Нехай маємо матрицю A виду (2.1.1) і хай B - одинична діагональнаматриця такого ж розміру. Створимо робочу матрицю R розміром N (2N простоприєднавши матрицю B справа до матриці A:
.
Над рядками такої розширеної матриці будемо виробляти перетворень -тання, аналогічні тим, які були описані в п.2.1. Ліву частину мат -Ріци R будемо називати подматріцей A, праву - подматріцей B. Весь про-процесперетворення матриці R розіб'ємо на 3 етапи.
1 етап. Виконаємо перетворення рядків матриці так, щоб всі елементомти, що лежать нижче діагональних елементів подматріци A, звернулися до ну-ли.
При цьому може використовуватися вибір головного елемента.
2 етап. Виконаємо перетворення так, щоб всі елементи, що лежать ви -ше діагональних елементів подматріци A, звернулися в нулі. Перетворять-ваннятреба виконувати у зворотному порядку: з стовпця номер n і до стовпця номер 2.
3 етап. Кожну рядок розширеної матриці R з номером i ділимо на ді -агональну елемент aii.
Після завершення процедури подматріца A перетворюється на одиничнудіагональну матрицю, а подматріца B дорівнюватиме шуканої зворотного мат-ріце
A-1. Алгоритм має порядок O (n3).
2.3. Методи рішення систем лінійних рівнянь
Завдання пошуку рішень системи лінійних рівнянь має не тільки са -мостоятельное значення, але часто є складовою частиною алгоритму ре -ності багатьох нелінійних задач. Основні методи вирішення СЛР:
- метод Гауса;
- метод звернення матриці;
- ітераційні методи.
2.4. Метод Гаусса
Нехай маємо систему лінійних рівнянь:
Простий метод Гауса полягає в наступному.
Складемо розширену матрицю, приписав до матриці коефіцієнтів СЛРдодатковий стовпець - праві частини рівняння:
.
Виконаємо над рядками розширеної матриці перетворення, анало -гічної тим, які були описані в п. 2.1:
,
,і приведемо її до Трикутному увазі:
.
Тепер можна обчислити шукані величини xi, починаючи з останнього,тобто спочатку знаходиться xn, потім xn-1, xn-2, ..., x1. Формула дляобчислень має вигляд:
.
Для розширення можливостей і підвищення стійкості наведеногоалгоритму використовується вибір головного елемента. Порядок методу Гаусса дорівнює
O (n3).
2.5. Метод звернення матриці
Уявімо систему лінійних рівнянь в матричній формі:
.
Помножимо останнє рівність зліва на A-1:
.
Враховуючи, що A-1 (A = I, формально отримуємо шукане рішення:
Таким чином, рішення системи виконується в два етапи:
1) обчислення оберненої матриці;
2) множення оберненої матриці на вектор правих частин СЛР.
Незважаючи на те, що метод звернення матриці має такий же порядок,як і метод Гауса - O (n3), за обсягом обчислень він програє йому в ніс -колько раз. Однак, якщо СЛР необхідно вирішувати багато разів і при цьомузмінюється лише вектор правих частин, метод звернення матриці становит-сявсе-таки вигідним.
Практична частина
Опис класу Matrix для вирішення задач лінійної алгебри
Клас має приватні і загальнодоступні члени-дані та члени-функції
(методи). Для зберігання компонентів матриці використовується одновимірнийдинамічний масив елементів типу параметр шаблону. Для створення об'єктапередбачені три конструктори: конструктор за умовчанням, конструктор зпараметрами, конструктор копіювання і деструктор. Для виконання безлічіматричних операцій створені перевантажені операції: присвоювання (=),додавання (+), віднімання (-), множення (*) і т.п. На базі операторіввведення/виведення С + + розроблені функції введення матриць з потоку та виведення їх употік, що передбачають у випадку файлового введення/виводу як текстовуформу зберігання, так і бінарну.
Доступ до членів-даними класу - числу рядків і стовпців матриціздійснюється за допомогою методів size_row () і size_col (). Для доступу доелементів матриці створений перевантажений оператор виклику функції operator ()
(dim x, dim x), де dim - перевизначених тип unsigned char. Виклик функціївикористовується як оператор індексування, що приймає два аргументи.
Аналогічно створений оператор виклику функції з одним аргументом operator ()
(dim x). Для даного класу - це дуже важливі перевантажені оператори,тому що вони використовуються у всіх функціях і операторів, в яких відбуваєтьсязвернення до елементів матриці.
Опис функцій, конструкторів і деструкторів класу:
1. Конструктор за умовчанням Matrix ():
Конструктор за умовчанням створює матрицю нульового розміру. УНадалі розмір цієї матриці можна змінити за допомогою функції newsize (i,j).
2. Конструктор з параметрами Matrix (dim, dim = 1):
Це звичайний конструктор з параметрами, який приймає в якостіпараметрів розміри матриці і створює одновимірний динамічний масиврозміром m * n, де m - число рядків, а n - число стовпців матриці. З метоюможливості використовувати його для створення векторів, другий параметрконструктора заданий як замовчуваних із значенням 1. Для первісної
«Ініціалізації» елементів матриці нулями використовується функція setmem ().
3. Конструктор копіювання Matrix (const Matrix &):
Конструктор приймає як параметр посилання наоб'єкт класу (наіснуючу матрицю), визначає її розмір, виділяє для неї пам'ять ікопіює в цю пам'ять вміст матриці, що приймається за посиланням. Такимчином, створюється точна копія матриці з поточними значеннями її елементів.
4. Деструктор ~ Matrix ():
Деструктор вивільняє пам'ять, виділену для конструкторамиелементів матриці.
5. Функція операції присвоювання "=" Matrix & operator = (Matrix &):
Ця функція порівнює адреса переданого за посиланням об'єкта задресою власного класу, щоб не зробив спроби присвоїть об'єктсамому собі. Після цього створюється новий масив з числом елементів, рівнимчислу елементів масиву що приймається за посиланням, і в цей масив заноситьсявміст прийнятого масиву. Повертається разименованний покажчик this
(return * this;).
6. Опції операцій додавання, віднімання, множення матриць і множення матриці на число:
Ці функції реалізовані як дружні функції і алгоритми цихфункцій аналогічні за своїм складом. Загальний вигляд прототипу цих функцій:friend Matrix operator @ (const Matrix &, const Matrix &). Застосуваннядружніх функцій у даному випадку доцільно для того, щоб матиможливість надавати у оператор функцію об'єкти в будь-якійпослідовності. У цих операторах-функціях спочатку створюється тимчасовийоб'єкт типу матриця (за допомогою конструктора копіювання), до якогокопіюється перша матриця і який при виході з функції єщо повертається об'єктом. Потім ця матриця підсумовується (віднімається,множиться) з матрицею, що стоїть після символу оператора за відповіднимиправилами матричних операцій. При цьому для доступу до елементів матриці ііндексування використовуються перевантажені оператори виклику функціїoperator () (dim x, dim x) і operator () (dim x).
7. Функція - оператор Matrix operator ^ (int):
Цей оператор-функція реалізований як член класу і призначений длязведення матриці до степеня. У випадку, коли значення вхідного параметраодно мінус одиниці здійснюється виклик функції обчислення зворотногоматриці методом перетворень Гауса, для чого розроблена окремафункція Matrix & Gauss (dim, dim). Таким чином, використання цьогооператора дозволяє вирішувати систему лінійних алгебраїчних рівнянь вподанні X = (A ^ -1) & B, де X і B-вектора невідомих і правих частинвідповідно.
8. Функція - оператор Matrix operator! ():
Оператор для визначення транспонований матриці.
9. Функція - оператор friend VARTYPE operator% (const Matrix &, const
Matrix &):
Функція обчислення скалярного добутку векторів. У ній на початкуперевіряється, чи є що передаються об'єкти векторами, а потімобчислюється скалярний добуток.
10. Функції-члени VARTYPE determ () і VARTYPE vmodule ():
Перша функція обчислює визначник власного об'єкту (матриці).
При цьому використовуються функція Matrix & Gauss (dim, dim). Функція VARTYPEvmodule () обчислює довжину (модуль) вектора
11. Функція операції виводу friend ostream & operator, і посилання об'єкт, який знаходиться ліворуч відзнаку операції, у нього і будуть вводитися дані з потоку. Потім слідвведення даних з потоку в елементи масиву і повертається потік. Для введенняданих з файлу, треба відкрити його приєднанням до потоку ifstream.
13. Функції-члени dim write (ofstream &) і dim read (ifstream &):
Опції призначені для виведення у файл і введення з файлу матриць в здвійковому поданні. Для цього необхідно передати в них відповіднупосилання на відкритий файл.
14. Функція void ERROR_MATRIX (dim):
Це функція-член, яка викликається для фіксації деяких помилок пристворення матриць і роботі з ними, таких як відсутність пам'яті,неузгодженість розмірів матриць при операції множення, спроби обчислитинегативну ступінь матриці і т.п.
Лістинг модуля з визначенням і реалізацією класу матриць
// фото tmatr.cpp
# include
# include// для setmem ()
# include
# include
typedef unsigned char dim;
template class Matrix (typedef Matrix Vector;private:
VARTYPE * matr;// вказівник на масив матриці dim m, n;// розміри матриціpublic:
// конструктори і деструктори:
Matrix () (matr = (VARTYPE *) 0; m = n = 0;)
Matrix ( dim, dim = 1);// Звичайний конструктор
Matrix (const Matrix &);// Конструктор копіювання
~ Matrix () (delete [] matr;)
// доступ до елементів матриці dim size_row () (return m;)// кількість стрічок dim size_col () (return n;)// число стовпців
VARTYPE & operator () (dim x) const (return (* this) (x, 0);)// елементу
// перевантажені операції та функції:
Matrix & operator = (const Matrix &);
Matrix & operator = (const VARTYPE &);
Matrix operator ^ (int);// зведення в ступінь
Matrix operator! ();// транспонування
VARTYPE determ ();// визначник матриці
VARTYPE vmodul ();// модуль вектора
Matrix & Gauss (dim, dim);// перетворення по Гаусу
// (для получ. зворотної та одиничної матриці)
// (для получ. верхнетреугольной матриці)
Matrix minor (dim, dim);// повертає указ. мінор матриці
Vector line (dim i)// повертає вектор-рядок матриці
(return extract (1, n, i, 0);)
Vector column (dim j)// повертає вектор-стовпець матриці
(return extract (m, 1,0, j);)
VARTYPE & operator () (dim, dim) const;// доступ до
Matrix & operator
