Организация математичних операцій на С++

МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ З, а п про р про із до і і р про з у буд, а р з тонн на е зв зв и і т е x зв і год е з до і і у зв й у е р сек. і т е т.

Кафедра.

__________________________.

ПОЯСНЮВАЛЬНА ЗАПИСКА До КУРСОВОМУ ПРОЭКТУ.

ПО ДИСЦИПЛІНИ ________________________________________.

________________________________________________________.

________________________________________________________.

Розработала.

ст. грн. РПз-538.

Крыгина А. А.

Принял.

преподаватель.

Пінчук В.П.

2001р.

РЕФЕРАТ ПЗ: стр.

ЦЕЛЬ РОБОТИ: розробити бібліотечні засобу політичного вирішення завдань лінійної алгебры.

ОБЪЕКТ ДОСЛІДЖЕННЯ: класові типи — чисельна квадратна матриця і одновимірний динамічний масив зі змінними размерами.

МЕТОД ДОСЛІДЖЕННЯ: розробка алгоритмів і написання класів функцій на мові Borland С++.

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

Список ключових слів: ЛІНІЙНА АЛГЕБРА, МАТРИЦЯ, ВЕКТОР, СИСТЕМА ЛІНІЙНИХ РІВНЯНЬ, ВИЗНАЧНИК, ФУНКЦІЯ, КЛАС ФУНКЦІЙ, ОБ'ЄКТ, ОПЕРАЦІЯ, ШАБЛОН, ОБЪЕКТНООРІЄНТОВАНЕ ПРОГРАММИРОВАНИЕ.

Объектно-ориентированное програмування — це нове спосіб підходи до програмування. Таке програмування, узявши кращі риси структурного програмування, доповнює його новими ідеями, які до нового якість підхід до створення програм. Найбільш важливе поняття мов объектно-ориентированного програмування — це поняття об'єкта (object). Об'єкт — це логічна одиниця, яка містить дані і правил (методи) обробки цих даних. У мові З++ в ролі таких правил обробки виступають функції, т. е. об'єкт в Borland З++ об'єднує у собі дані і функції, обробні ці дані. Однією з найбільш головних понять мови З++ є поняття класу (class). У мові З++ у тому, щоб визначити об'єкт, треба спочатку визначити її форму з допомогою ключового слова class [1]. Найближчою аналогією класу є структура. Пам’ять виділяється об'єкту тільки тоді ми, коли клас використовується щодо його створення. Цей процес відбувається називається створенням примірника класу (class instance). Будь-який об'єкт мови З++ має однакові атрибути і функціональність з іншими об'єктами тієї самої класу. За створення своїх класів та поведінка об'єктів цих класів повну відповідальна сам програміст. Працюючи у певній середовищі, програміст отримує доступом до великим бібліотекам стандартних класів. Зазвичай, об'єкт перебуває у деякому унікальному стані, визначеному поточними значеннями його атрибутів. Функціональність об'єктного класу визначається можливими операціями над примірником цього. Шаблони, чи параметризованные типи, дозволяють конструювати сімейство пов’язаних функцій чи класів. Узагальнений синтаксис визначення шаблону має вигляд template {оголошення}; Розрізняють шаблони функцій і шаблони класів. Шаблону класів задає зразок визначень сімейства класів. Над типизированными елементами цього виконуються однакові базові операції незалежно від конкретного типу елементів [2].

Введення у объектно-ориентированное программирование.

Объектно-ориентированное програмування є трохи більш автоматизований спосіб програмування. Об'єктно-орієнтовані програми — це буде непросто процедурні програми, перекладені нового синтаксис. Вони мають будується новому філософії розробки. Їх потрібна нова стратегія програмування, яку це часто буває важко освоїти [3].

Основна ідея ОВП: програма складається з групи об'єктів, часто пов’язаних між собою. У З++ об'єкти описуються з допомогою нових типів даних class. Клас включає у собі набір змінних (даних) і операцій (методів чи функций-членов), що діють для цієї перемінні. Отриманими об'єктами можна управляти з допомогою сообщений.

У ОВП об'єкти містять у собі як дані (данные-члены), а й методи (функции-члены) на ці дані. Ці частини у поєднанні утворюють функціональну одиницю програми. Інакше кажучи, об'єкти містять дані та методи роботи цих даних. Нижче наведені три основних переваги объектно-ориентированных програм проти еквівалентними програмами, розробленими згори донизу.. Супровід програми. Програми простіше читати і розуміти, ОВП дозволяє управляти складністю програми, залишаючи видимими програмісту лише суттєві деталі.. Модифікація програми (додавання чи виняток можливостей). Можете часто робити доповнення чи винятку у програмі, наприклад під час роботи з базою даних, просто додаючи і виключаючи об'єкти. Нові об'єкти можуть успадковувати все властивості базових об'єктів, необхідно лише додати чи прибрати відмінні властивості.. Повторне використання. Можна зберегти грамотно розроблений об'єкт у традиційному наборі корисних програм, тож потім вставити їх у нову програму з невеликими змінами чи ні изменений.

ОВП повністю належить до світу З++, що у З немає основного ядра — абстрактного типу даних class [5]. Тому переписати процедурноорієнтовану програму як объектно-ориентированную набагато складніше, ніж просто підставити замість одного ключового слова інше. ОВП є техніку програмування, що дозволяє розглядати основні ідеї як безліч об'єктів. Використовуючи об'єкти, можна завдання, які потрібно виконати, їхню взаємодію й зняти будь-які задані умови, що їх дотримані. Структура даних часто утворює основи об'єктів; отже, у З або з++ тип struct може утворювати елементарний об'єкт. Зв’язок із об'єктом то можна організувати при допомоги повідомлень. Використання повідомлень схоже виклик функцій в процедурно-ориентированной програмі. Коли об'єкт отримує повідомлення, наберуть чинності методи, які у об'єкті. Методи (їх іноді називають фунциями-членами) аналогічні функцій процедурно-ориентированного програмування. Проте метод є частиною об'єкта, а чи не чимось окремим, як в процедурному аналоге.

Основні терміни й положення ООП.

Інкапсуляція данных.

Цей термін включає у собі логічне зв’язування даних із конкретної операцією. Вона як і означає, що є неглобальними доступними програмі, а локальними — доступними лише малої її частки. Інкапсуляція також автоматично передбачає захист даних. Саме з цього призначена структура class в З++. У класі управління функціональними деталями об'єкта здійснюється за допомогою специфікаторів private, public, protected.

Иерархия классов.

У випадку можна уявити ієрархію класів як родовід в генеалогічному дереві, де клас З++ є шаблон для створення классов-потомков. Об'єкти, отримані з описи класу, називають екземплярами цього. Можна створити ієрархію класів з класомбатьком і з декількома классами-потомками. Основою цього є похідні класи. Наследование.

Успадкування в ОВП дозволяє класу отримувати совйства іншого класу об'єктів. Батьківський клас служить шаблоном для похідного класу; цей шаблон можна змінювати в різний спосіб. Успадкування є важливим становищем, оскільки він дозволяє повторно використовувати визначення класу без значних змін — у коді. Полиморфизм.

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

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

Конструктор викликається щоразу, коли створюється об'єкт його класу. Завдання конструктора у разі полягає у зв’язуванні віртуальної функції з таблицею адресної інформації. Під час компіляції адресу віртуальної функції невідомий; натомість їй відводиться позиція в таблиці адрес. Цю позицію міститиме адресу функції [5].

Глава 2. Завдання лінійної алгебры.

2.1. Обчислення определителей.

Нехай маємо квадратну матрицю розміром n (n:

[pic]. (2.1.1) Потрібна обчислити визначник матриці det (A).

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

Використовуючи що така перетворення можна спробувати привести івходную матрицю до трикутникове виду:

[pic], у своїй det (A) = det (A ().

Формула для перерахунку елементів матриці має вид:

[pic], (2.1.2) де і - номер шпальти, у якому елементи, що лежать нижче главной.

діагоналі, перетворюються на нулі; j — номер елемента у обрабатываемом стовпці (тобто. номер рядки); k — номер елемента у поточної строке.

Алгоритм приведення матриці до трикутникове виду включає у собі 3 вкладених цикла:

— зовнішній цикл, і = 1. n-1 ;

— середній цикл, j = i+1. n ;

— внутрішній цикл, k = i+1. n .

Тепер шуканий визначник обчислюється як твір діагональных элементов:

[pic].

Описаний вище алгоритм дає результат досягнуто не завжди. Якщо за выполненді i-того кроку зовнішнього циклу діагональний елемент aii виявляється рав-ным нулю, серед елементів i-того шпальти з номерами від i+1 до n хоча б один не нульової, алгоритм завершується безрезультатно (через невозмож-ности обчислень за такою формулою (2.1.2). А, щоб це відбувалося, використовується прийом, що називається «вибір головного элемента».

За виконання чергового кроку циклу по і попередньо выполняют-ся такі операции:

1) перебуває максимальний по модулю елемент серед елементів i-то-го шпальти від aii до ani ;

2) якщо знайдений елемент ali нульовий, процес обчислення завершается із видачею результату det (A) = 0 ;

3) якщо l (i, тоді рядки вихідної матриці з номерами i, l поміняти местами.

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

[pic], де 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 :

[pic] .

Над рядками такий розширеній матриці продукуватимемо преобразования, аналогічні тим, описані в п. 2.1. Ліву частина матрицы R називатимемо подматрицей A, праву — подматрицей B. Весь про-цесс перетворення матриці R розіб'ємо на 3 этапа.

1 етап. Виконаємо перетворення рядків матриці те щоб все элементи, що лежать нижче діагональних елементів подматрицы A, звернулися на ну-ли. У цьому можна використовувати вибір головного элемента.

2 етап. Виконаємо перетворення те щоб все елементи, що лежать више діагональних елементів подматрицы A, звернулися на нулі. Преобразо-вания треба виконувати у порядку: зі шпальти номер n і по шпальти номер 2.

3 етап. Кожну рядок розширеній матриці R з номером і ділимо на діагональный елемент aii .

Після закінчення процедури подматрица A перетворюється на одиничну діагональну матрицю, а подматрица B дорівнюватиме шуканої зворотної мат-рице A-1. Алгоритм має порядок O (n3).

2.3. Методи рішення систем лінійних уравнений.

Завдання пошуку рішень системи лінійних рівнянь має лише самостоятельное значення, але часто є складовою алгоритму решения багатьох нелінійних завдань. Основні на методи вирішення СЛУ:

— метод Гаусса;

— метод звернення матрицы;

— итерационные методы.

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

Нехай маємо систему лінійних уравнений:

[pic].

Простий метод Гаусса полягає у следующем.

Складемо розширену матрицю, приписавши до матриці коефіцієнтів СЛУ додатковий стовпець — праві частини уравнения:

[pic] .

Виконаємо над рядками розширеній матриці перетворення, аналогичные тим, описані в п. 2.1:

[pic] ,.

[pic], і наведемо її до трикутникове виду:

[pic] .

Нині можна обчислити шукані величини xi, починаючи з останнього, тобто. спочатку перебуває xn, потім xn-1, xn-2, …, x1. Формула для обчислень має вид:

[pic] .

Для можливостей і підвищення стійкості наведеного алгоритму використовується вибір головного елемента. Порядок методу Гаусса дорівнює O (n3).

2.5. Метод звернення матрицы.

Уявімо систему лінійних рівнянь в матричної форме:

[pic]. Помножимо останнє рівність зліва на A-1 :

[pic]. З огляду на, що A-1(A = I, формально отримуємо дані решение:

[pic].

Отже, рішення системи виконується удвічі этапа:

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). Функція VARTYPE vmodule () обчислює довжину (модуль) вектора 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 і) // повертає вектор-строку матрицы.

{ return extract (1,n, i,0); }.

Vector column (dim j) // повертає вектор-столбец матрицы.

{ return extract (m, 1,0,j); }.

VARTYPE& operator () (dim, dim) const; // доступом до Matrix& operator.