МИНИСТЕРСТВО
ОБРАЗОВАНИЯ УКРАИНЫ
З а п о р о ж с к и й г о с у д а р с т
в е н н ы й т е х н и ч е с к и й
у н и в е р с и т е т
|
Кафедра
__________________________
ПОЯСНИТЕЛЬНАЯ
ЗАПИСКА К КУРСОВОМУ ПРОЭКТУ
|
________________________________________________________
ст. гр. РПз-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:
Требуется вычислить определитель матрицы 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). Функция VARTYPE vmodule( ) вычисляет
длину (модуль) вектора
11.
Функция операции вывода friend ostream&
operator<<(ostream&, Matrix&):
Данная функция не может быть членом класса, поэтому
чтобы иметь доступ к приватным элементам класса, она объявлена
"дружественной" функцией. Она имеет два параметра: ссылку на поток,
который находится слева от знака операции <<, и ссылку на объект, который
находится слева от знака операции, данные этого объекта и будут выводиться.
Затем следует форматированный вывод в поток всех элементов массива и
возвращается поток. Если требуется вывести данные в файл, нужно открыть его присоединением
к потоку ofstream.
12.
Функция операции ввода friend istream&
operator>>(istream&, Matrix&):
Так же как и предыдущая, данная функция не может быть
членом класса, а поэтому для доступа к приватным элементам класса объявлена
"дружественной" функцией класса. Она так же имеет два параметра:
ссылку на поток, который находится слева от знака >>, и ссылку объект,
который находится слева от знака операции, в него и будут вводиться данные из
потока. Затем следует ввод данных из потока в элементы массива и возвращается
поток. Для ввода данных из файла, нужно открыть его присоединением к потоку
ifstream.
13.
Функции-члены dim write(ofstream&) и
dim read(ifstream&):
Функции предназначены для вывода в файл и ввода из
файла матриц в из двоичном представлении. Для этого необходимо передать в них
соответствующую ссылку на открытый файл.
14.
Функция void ERROR_MATRIX(dim):
Это функция-член, которая вызывается для фиксации
некоторых ошибок при создании матриц и работе с ними, таких как отсутствие
памяти, несогласованность размеров матриц при операции умножения, попытки
вычислить отрицательную степень матрицы и т.п.
Листинг модуля с определением и
реализацией класса матриц
// файл
tmatr.cpp
#include
<stdlib.h>
#include
<mem.h> // для setmem()
#include
<fstream.h>
#include
<math.h>
typedef unsigned
char dim;
template <class
VARTYPE> 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<VARTYPE>&); // Конструктор копирования
~Matrix() { delete [ ]matr; }
// доступ к элементам матрицы
dim size_row() { return m; } // число строк
dim size_col()
{ return n; } // число столбцов
VARTYPE&
operator() (dim x) const { return (*this)(x,0); } // элементу
// перегруженные операции и
функции:
Matrix<VARTYPE>& operator=(const
Matrix<VARTYPE>&);
Matrix<VARTYPE>& operator=(const VARTYPE&);
Matrix<VARTYPE> operator^(int); // возведение в степень
Matrix<VARTYPE> 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<VARTYPE>&
operator<<=(const Matrix &A) { return newsize(A.m,A.n)=A; }
//
безусловное приравнивание матриц
Matrix<VARTYPE>& insert(const Matrix&, dim=0, dim=0); // вставить часть матрицы
Matrix<VARTYPE> extract(dim, dim, dim=0, dim=0); // извлечь часть матрицы
Matrix<VARTYPE>& newsize(dim, dim=1); //
установить новые размеры
void swap_line(dim, dim); //обмен
строками матрицы
void swap_column(dim,
dim); // обмен
столбцами матрицы
friend Matrix<VARTYPE> operator+(const
Matrix<VARTYPE>&,const Matrix<VARTYPE>&); //A-B
friend
Matrix<VARTYPE> operator-(const Matrix<VARTYPE>&,const
Matrix<VARTYPE>&); //A-B
friend
Matrix<VARTYPE> operator*(const Matrix<VARTYPE>&,const
Matrix<VARTYPE>&); //A*B
friend Matrix
operator*(const double&,const Matrix<VARTYPE>&); //k*A
friend Matrix
operator*(const Matrix<VARTYPE>&, const double&); //A*k
friend
ostream& operator<<(ostream&,Matrix<VARTYPE>&);
//
потоковый вывод матрицы
friend int
operator>>(istream&,Matrix<VARTYPE>&);
// потоковый ввод существ. матрицы
//
0 - без. ошибок, 1 - была ошибка
dim read(ifstream&);
// файловое чтение и запись матрицы
dim write(ofstream&); //
в ее внутреннем, двоичном представлении.
friend VARTYPE operator %(const
Matrix<VARTYPE>&,const Matrix<VARTYPE>&);
//Функция ошибок
void
ERROR_MATRIX(dim) const;
};
// Реализация класса матриц
template <class
VARTYPE>
Matrix<VARTYPE>::Matrix(dim
M, dim N)
{
m=M;
n=N;
matr=new
VARTYPE[m*n];
if(!matr)
ERROR_MATRIX(1);
setmem(matr,sizeof(VARTYPE)*m*n,0);
}
template <class
VARTYPE>
Matrix<VARTYPE>::Matrix(const
Matrix<VARTYPE> &M_Obj) //Конструктор копирования
{
m=M_Obj.m;
n=M_Obj.n;
matr=new
VARTYPE[m*n];
if(!matr)
ERROR_MATRIX(1);
movmem(M_Obj.matr, matr, sizeof(VARTYPE)*m*n);
}
template <class
VARTYPE>
Matrix<VARTYPE>&
Matrix<VARTYPE>::operator=(const Matrix<VARTYPE> &M_Obj)
{
m=M_Obj.m;
n=M_Obj.n;
matr=new
VARTYPE[m*n];
if(!matr)
ERROR_MATRIX(1);
movmem(M_Obj.matr,matr,sizeof(VARTYPE)*m*n);
return *this;
}
//Диагональ?
template <class
VARTYPE>
Matrix<VARTYPE>&
Matrix<VARTYPE>::operator=(const VARTYPE &f)
{
for(int
i=0,j;i<m;i++) for(j=0;j<n;j++)
if(i==j)
(*this)(i,j)=f;
else
(*this)(i,j)=0;
return *this;
}
template <class
VARTYPE>
Matrix<VARTYPE>
Matrix<VARTYPE>::operator^(int q) // Степень
{
if (q>0)
{
for(Matrix
M=*this; q>1; q--)
M=M*(*this);
return
M;
}
if (q!=-1)
ERROR_MATRIX(3);
// вычисление обратной метoдом преобразований Гаусса
if (n!=m) ERROR_MATRIX(4);
Matrix
M(m,2*n);
M.insert(*this);
for(int
i=0;i<M.m;i++)
M(i,i+M.m)=1;
for(i=0;i<M.m;i++)
M.Gauss(i,i);
return
M.extract(M.m,M.m,0,M.m);
}
template <class
VARTYPE>
Matrix<VARTYPE>
Matrix<VARTYPE>::operator!() //
Транспозиция
{ Matrix<VARTYPE> A(n,m);
for(int i=0, j;
i<m; i++)
for(j=0;
j<n; j++)
A(j,i)=(*this)(i,j);
return A;
}
template <class
VARTYPE>
VARTYPE
Matrix<VARTYPE>::determ() // рекурсивно находит определитель матрицы
{
if (n!=m)
ERROR_MATRIX(4);
if (n==1)
return
(*this)(0,0);
for(int i=0;
i<m; i++)
if
((*this)(i,0))
{
static
Matrix<VARTYPE> M;
M
<<= *this;
VARTYPE
d=M(i,0)*(i%2?-1:1);
return
d*M.Gauss(i,0).minor(i,0).determ();
}
return 0.0;
}
template <class
VARTYPE>
VARTYPE
Matrix<VARTYPE>::vmodul() // Модуль вектора
{
VARTYPE d=0;
if (n!=1)
ERROR_MATRIX(9);
static
Matrix<VARTYPE> M;
M <<=
*this;
for(int i=0;
i<m; i++)
d=d+M(i,0)*M(i,0);
return sqrt(d);
}
template <class
VARTYPE>
Matrix<VARTYPE>&
Matrix<VARTYPE>::Gauss(dim M, dim N)
{
Matrix<VARTYPE>& A=*this;
if (!A(M,N))
ERROR_MATRIX(5);
for(int
i=0,j;i<m;i++)
for(j=0;j<n;j++)
if
(i!=M && j!=N)
A(i,j)-=A(M,j)*A(i,N)/A(M,N);
for(j=0;j<n;j++)
if (j!=N)
A(M,j)/=A(M,N);
for(i=0;i<m;i++)
A(i,N)=0;
A(M,N)=1;
return *this;
}
template <class
VARTYPE>
Matrix<VARTYPE>
Matrix<VARTYPE>::minor(dim M, dim N) // возвращ. матрицу без
{ //
строки y и столбца x
Matrix<VARTYPE> A(m-1,n-1);
for(int
i=0,in=0,j,jn;i<m;i++)
if (i!=M)
{
for(j=0,jn=0;j<n;j++)
if (j!=N)
A(in,jn++)=(*this)(i,j);
in++;
}
return A;
}
template <class
VARTYPE> // вставка
Matrix<VARTYPE>&
Matrix<VARTYPE>::insert(const Matrix<VARTYPE> &A, dim M, dim N)
{
if (M+A.m>m
|| N+A.n>n) ERROR_MATRIX(6);
for(int i=0, j;
i<A.m; i++)
for(j=0;
j<A.n; j++)
(*this)(i+M,j+N)=A(i,j);
return *this;
}
template <class
VARTYPE> // извлечение
Matrix<VARTYPE>
Matrix<VARTYPE>::extract(dim LM, dim LN, dim M, dim N)
{
if (M+LM>m
|| N+LN>n) ERROR_MATRIX(7);
Matrix<VARTYPE> A(LM,LN);
for(int i=0,
j; i<LM; i++)
for(j=0;
j<LN; j++)
A(i,j)=(*this)(i+M,j+N);
return A;
}
template <class
VARTYPE>
VARTYPE&
Matrix<VARTYPE>::operator() (dim M, dim N) const
{ return
*(matr+n*M+N); }
template <class
VARTYPE>
Matrix<VARTYPE>
operator+(const Matrix<VARTYPE> &A, const
Matrix<VARTYPE>&B)
{
Matrix<VARTYPE> C=A;
for(int i=0,j;
i<A.m; i++)
for(j=0;
j<A.n; j++)
C(i,j)+=B(i,j);
return C;
}
template <class
VARTYPE>
Matrix<VARTYPE>
operator-(const Matrix<VARTYPE> &A, const Matrix<VARTYPE>
&B)
{
Matrix<VARTYPE> C=A;
for(int i=0, j;
i<A.m; i++)
for(j=0;j<A.n;j++)
C(i,j)-=B(i,j);
return C;
}
template <class
VARTYPE>
Matrix<VARTYPE>
operator*(const Matrix<VARTYPE> &A,const Matrix<VARTYPE>
&B)
{
Matrix<VARTYPE> C(A.m,B.n);
if (A.n!=B.m)
{
if(A.m==3 &&
A.n==1 && B.m==3 && B.n==1)
{
C(0)=A(1)*B(2)-A(2)*B(1);
C(1)=A(2)*B(0)-A(0)*B(2);
C(2)=A(0)*B(1)-A(1)*B(0);
}
else
A.ERROR_MATRIX(2);
}
else
{
for(int
i=0,j,k;i<C.m;i++)
for(j=0;j<C.n;j++)
for(k=0;k<A.n;k++)
C(i,j)+=A(i,k)*B(k,j);
}
return C;
}
template <class
VARTYPE>//умножение числа на матрицу
Matrix<VARTYPE>
operator*(const double &f,const Matrix<VARTYPE> &A)
{
Matrix<VARTYPE> B=A;
for(int
i=0,j;i<A.m;i++)
for(j=0;j<A.n;j++)
B(i,j)*=f;
return B;
}
template <class
VARTYPE>// умножение матрицы на число
Matrix<VARTYPE>
operator*(const Matrix<VARTYPE> &A, const double &f)
{
Matrix<VARTYPE> B=A;
for(int
i=0,j;i<A.m;i++)
for(j=0;j<A.n;j++)
B(i,j)*=f;
return B;
}
template <class
VARTYPE>
Matrix<VARTYPE>&
Matrix<VARTYPE>::newsize(dim M, dim N)
{ delete [] matr;
m=M;
n=N;
if (N
&& M) { matr=new VARTYPE[m*n];
if (!matr)
ERROR_MATRIX(1);
setmem(matr,sizeof(VARTYPE)*m*n,0);
}
else { m=n=0; matr=(VARTYPE*)0;
}
return *this;
}
template <class
VARTYPE>
ostream&
operator<<(ostream &out,Matrix<VARTYPE> &A)
{ for(int
i=0,j;i<A.size_row();i++)
{
for(j=0;j<A.size_col();j++)
out
<< A(i,j)<< " ";
out<<endl;
}
return out;
}
template <class
VARTYPE>
int
operator>>(istream &inp,Matrix<VARTYPE> &A)
{ for(int
i=0,j;i<A.size_row();i++)
for(j=0;j<A.size_col();j++) if( !(inp>>A(i,j)) ) return 1;
return 0;
}
template <class
VARTYPE>
void
Matrix<VARTYPE>::swap_line(dim L1, dim L2)
{
if (L1==L2)
return;
double b;
for(int
j=0;j<n;j++)
{
b=(*this)(L1,j);
(*this)(L1,j)=(*this)(L2,j);
(*this)(L2,j)=b;
}
}
template <class
VARTYPE>
void
Matrix<VARTYPE>::swap_column(dim C1, dim C2)
{
if (C1==C2)
return;
double b;
for(int
i=0;i<m;i++)
{
b=(*this)(i,C1);
(*this)(i,C1)=(*this)(i,C2);
(*this)(i,C2)=b;
}
}
template <class
VARTYPE>
dim
Matrix<VARTYPE>::read(ifstream &finp)
{
(finp.get(m)).get(n); delete []matr; matr=new VARTYPE[m*n];
if(!matr)
ERROR_MATRIX(1);
setmem(matr,sizeof(VARTYPE)*m*n,0);
finp.read((char
*)matr,sizeof(VARTYPE)*m*n); return finp.fail();
}
template <class
VARTYPE>
dim
Matrix<VARTYPE>::write(ofstream &fout)
{ (fout.put(m)).put(n);
(fout.write((char *)matr,sizeof(VARTYPE)*m*n))<<flush; return
fout.fail();
}
template <class
VARTYPE>
VARTYPE
operator%(const Matrix<VARTYPE> &A, const
Matrix<VARTYPE>&B)
{
if(A.n!=1 ||
B.n!=1) A.ERROR_MATRIX(9);
if(A.m!=B.m)
A.ERROR_MATRIX(0);
VARTYPE
scalarmul = 0;
for(int i=0;
i<A.m; i++)
scalarmul
= scalarmul+A(i)*B(i);
return
scalarmul;
}
template <class
VARTYPE>
void
Matrix<VARTYPE>::ERROR_MATRIX(dim E) const
{ static char
*message[] = {
"Матрицы должны иметь одинаковую
размерность", //0
"Не
выделена память!", //1
"Матрицы не
согласованы для умножения", //2
"Степень
должна быть больше нуля или -1", //3
"Матрица
должна быть квадратной", //4
"Нулевой
ведущий элемент в преобразовании Гаусса", //5
"Вставка
невозможна из-за перекрытия базовой матрицы", //6
"Извлекаемая
матрица выходит за границы базовой", //7
"Выход за
границы. Попытка доступа к несущ. элементу", //8
"Это не
вектор!"}; //9
cerr<<"ERROR: "<< message[E]
<< endl; exit(1);
}
Демонстративно - тестирующая
программа:
#include
<conio.h>
#include
<iostream.h>
#include
<fstream.h>
#include
"tmatr.cpp"
int
main()
{
clrscr();
Matrix<double> A(3,3), B(3,3), C(3,3);
Matrix<double> V(3),X(3),H(3),U(3);
double d;
A(0,0)=1.1; A(0,1)=2.2; A(0,2)=3.3;
A(1,0)=2.4; A(1,1)=1.1; A(1,2)=4.4;
A(2,0)=1.3; A(2,1)=2.1; A(2,2)=4.1;
B(0,0)=2; B(0,1)=7; B(0,2)=2;
B(1,0)=4; B(1,1)=8; B(1,2)=1;
B(2,0)=6; B(2,1)=4; B(2,2)=1;
V(0)=2.1; V(1)=3.31; V(2)=1.4;
H(0)=1.1; H(1)=2.1; H(2)=3.1;
//******************************
C=A+B;
cout<<"A:\n"<<A<<endl;
cout<<"B:\n"<<B<<endl;
cout<<"C=A+B:\n"<<C<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//******************************
C=A-B;
cout<<"A:\n"<<A<<endl;
cout<<"B:\n"<<B<<endl;
cout<<"C=A-B:\n"<<C<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//******************************
//******************************
X=V+H;
cout<<"V:\n"<<V<<endl;
cout<<"H:\n"<<H<<endl;
cout<<"X=V+H:\n"<<X<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//******************************
X=V-H;
cout<<"V:\n"<<V<<endl;
cout<<"H:\n"<<H<<endl;
cout<<"X=V-H:\n"<<X<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
C=A*V;
cout<<"A:\n"<<A<<endl;
cout<<"V:\n"<<V<<endl;
cout<<"C=A*V:\n"<<C<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//******************************
Matrix<int> D(3,3), E(3,3);
D(0,0)=1; D(0,1)=2; D(0,2)=3;
D(1,0)=2; D(1,1)=5; D(1,2)=6;
D(2,0)=7; D(2,1)=3; D(2,2)=9;
ofstream fout("test.mtr");
if(!fout)
{
cout<<"file not open\n";
return 1;
}
D.write(fout);
fout.close();
ifstream fin("test.mtr");
if(!fin)
{
cout<<"file not open\n";
return 1;
}
E.read(fin); //é ñó«¿t¡«¼
ó¿ñÑ
cout<<"D:\n";
cout<<D;
cout<<"E:\n";
cout<<E;
fin.close();
cout<<"Press any key...\n";
getch();
clrscr();
//************************************
C=A^-1;
cout<<"A:\n"<<A<<endl;
cout<<"C=A^-1:\n"<<C<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//****************************
//
A*X=V X=(A^-1)*V
X=(A^-1)*V;
cout<<"A^-1:\n"<<(A^-1)<<endl;
cout<<"V:\n"<<V<<endl;
cout<<"X:\n"<<X<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//************************************
d=A.determ();
cout<<"determinant of A = "<<d<< endl;
d=V.vmodul();
cout<<"modul of V = "<<d<< endl;
cout<<"Press any key...\n";
getch();
clrscr();
//************************************
V(0)=4; V(1)=3; V(2)=2;
U(0)=1; U(1)=2; U(2)=3;
d=V%U;
cout<<"scalar product V*U= "<< d<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//************************************
C=!A;
cout<<"A:\n"<<A<<endl;
cout<<"C=!A:\n"<<C<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
C=5*A;
B=A*2;
cout<<"A:\n"<<A<<endl;
cout<<"C=5*A:\n"<<C<<endl;
cout<<"B=A*2:\n"<<B<<endl;
cout<<"Press any key...\n";
getch();
clrscr();
//************************************
//************************************
return
0;
Результаты тестирования класса Matrix
Сложение
матриц A и B:
A: B: C=A+B:
1.1 2.2 3.3 2 7 2 3.1 9.2 5.3
2.4 1.1 4.4 4 8 1 6.4 9.1 5.4
1.3 2.1 4.1 6 4 1 7.3 6.1 5.1
Вычитание
матриц A и B:
A: B: C=A-B:
1.1 2.2 3.3 2 7 2 -0.9 -4.8 1.3
2.4 1.1 4.4 4 8 1 -1.6 -6.9 3.4
1.3 2.1 4.1 6 4 1 -4.7 -1.9 3.1
Сложение
матриц A и B:
A: B: C=A*B:
1.1 2.2 3.3 2 7 2 30.8 38.5 7.7
2.4 1.1 4.4 4 8 1 35.6 43.2 10.3
1.3 2.1 4.1 6 4 1 35.6 42.3 8.8
Сложение векторов
V:
2.1
3.31
1.4
H:
1.1
2.1
3.1
X=V+H
3.2
5.41
4.5
Вычитание векторов
V:
2.1
3.31
1.4
H:
1.1
2.1
3.1
X=V-H:
1
1.21
-1.7
Умножение матрицы на вектор
A:
1.1 2.2 3.3
2.4 1.1 4.4
1.3 2.1 4.1
V:
2.1
3.31
1.4
C=A*V:
14.212
14.841
15.421
Запись матрицы в файл
D:
1
2 3
2
5 6
7
3 9
Считывание матрицы из файла
E:
1
2 3
2
5 6
7
3 9
Вычисление обратной матрицы
A:
1.1 2.2 3.3
2.4 1.1 4.4
1.3 2.1 4.1
C=A^-1:
2.009346
0.88785 -2.570093
1.750212
-0.093458 -1.308411
-1.53356
-0.233645 1.728972
Решение алгебраического уравнения
A^-1:
2.009346
0.88785 -2.570093
1.750212
-0.093458 -1.308411
-1.53356
-0.233645 1.728972
V:
2.1
3.31
1.4
X:
3.56028
1.534325
-1.57328
Определение детерминанта матрицы
determinant of A = -2.354
Определение длины (модуля) вектора
modul of V = 4.162463
Вычисление скалярного произведения векторов
scalar product V*U= 16
ВЫВОД
В результате выполнения курсового проекта были разработаны
два класса функций для решения простейших задач линейной алгебры. Число этих
функций сравнительно невелико, однако можно легко добавить в эти классы более
сложные функции, построенные на базе уже имеющихся. Классы позволяют работать с
матрицами и векторами, элементы которых могут быть любого типа, однако на практике
чаще всего используется целый тип и тип чисел с плавающей запятой.
Классы написаны на языке С++, однако могут быть легко
переписаны на любом из современных языков программирования, так как приведены
довольно простые алгоритмы всех компонентных функций. Были максимально
предусмотрены все возможные ошибки, которые могут возникнуть при использовании
функций данных классов. Особое внимание уделялось разумному выделению памяти
под объекты во время выполнения программы, поэтому все функции были тщательно отлажены.
Классы Matrix
и Vector могут быть эффекивно применены на
практике в задачах, требующих операций с матрицами и векторами, а также
связанных с решением систем линейных алгебраических уравнений.
Список
использованной литературы
1. Дискретная математика, конспект
лекций. В. Г. Засовенко. Запорожье, 1998 г.
2. Начальный курс С и С++. Б. И.
Березин. Москва: "ДИАЛОГ-МИФИ", 1999 г.
3. Язык программирования С++. Б.
Страуструп. Киев:"ДиаСофт", 1993 г.
| ! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
| ! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
| ! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
| ! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
| ! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
| → | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |