Свойства верхней треугольной матрицы

Если верхняя треугольная матрица имеет n² элементов, приблизительно половина из них являются нулевыми и нет необходимости сохранять их явно. Конкретно, если мы вычитаем n диагональных элементов из суммы n² элементов, то половина оставшихся элементов являются нулевыми. Например, при n=25 имеется 300 элементов со значением 0:

(n²-n)/2 = (25²-25)/2=(625-25)/2 = 300

Далее следует набор операций для треугольных матриц. Мы определяем сложение, вычитание и умножение матриц, а также детерминант, который имеет важное применение для решения уравнений.

Сумма или разность двух треугольных матриц А и В получается в результате сложения или вычитания соответствующих элементов матриц. Результирующая матрица является треугольной.

Сложение С = А + В

где С - это треугольная матрица с элементами C_i,j = A_i,j + B_i,j.

Вычитание С = А - В

где С - это треугольная матрица с элементами C_i,j = A_i,j + B_i,j.

Умножение С = А * В

Результирующая матрица С - это треугольная матрица с элементами C_i,j, значения которых вычисляются из элементов строки i матрицы А и столбца j матрицы В:

C_i,j=(A_i,0*B_0,j)+ (A_i,1*B_1,j)+ (A_i,2*B_2,j)+…+ (A_i,n-1*B_n-1,j)

Для общей квадратной матрицы детерминант является сложной для вычисления функцией, однако вычислить детерминант треугольной матрицы не трудно. Просто получите произведение элементов на диагонали.

Хранение треугольной матрицы

Применение для хранения верхней треугольной матрицы стандартного двумерного массива требует использования всей памяти размером n², несмотря на прогнозируемые нули, расположенные ниже диагонали. Для исключения этого пространства мы сохраняем элементы из треугольной матрицы в одномерном массиве М. Все элементы ниже главной диагонали не сохраняются. Таблица 3.1 показывает количество элементов, которые сохраняются в каждой строке.

Хранение треугольной матрицы

Таблица 1

Строка	Число элементов	Элементы
	n	(A0,0…A0,n-1)
	n-1	(A1,1…A1,n-1)
	n-2	(A2,2…A2,n-1)
…	…	…
n-2		(An-2,n-2…An-2,n-1)
n-1		(An-1,n-1)

Алгоритму сохранения требуется функция доступа, которая должна определять местоположение в массиве М элемента A_i,j. Для j < i элемент A_i,j является равным 0 и не сохраняется в М. Для j ³ i функция доступа использует информацию о числе сохраняемых элементов в каждой строке вплоть до строки i. Эта информация может быть вычислена для каждой строки i и сохранена в массиве (rowTable) для использования функцией доступа.

Строка	rowTable	Замечание
	rowTable[0] = 0	0 элементов перед строкой 0
	rowTable [1] = n	n элементов перед строкой 1 (от строки 0)
	rowTable [2] = n + n-1	n + n-1 элементов перед строкой 2
	rowTable[3] = n + n-l+n-2	элементы перед строкой 3
…	…	…
n-1	rowTable[n-1] = n + n-1 +... +2

Пример 4.

С учетом того, что элементы треугольной матрицы сохраняются построчно в массиве М, функция доступа для A_i,j использует следующие параметры:

Индексы i и j,

Массив rowTable

Алгоритм доступа к элементу A_i,j заключается в следующем:

Если j<i, A_i,j = 0 и этот элемент не сохраняется.

Если j³i, то получается значение rowTable[i], являющееся количеством элементов, которые сохраняются в массиве М, для элементов до строки i. В строке i первые i элементов являются нулевыми и не сохраняются в М. Элемент A_i,j помещается в M[rowTable[i]+(j-i)].

Пример 5.

Рассмотрим треугольную матрицу Х[3][3] из примера 3.4:

1.Х_0,2 =M[rowTable[0]+(2-0)]=М[0+2]=М[2]=0

2.X_1,0 не сохраняются

3.Х_1,2 =M[rowTable[l]+(2-1)]=М[3+1]=М[4]=1

 

Класс TriMat

Класс TriMat реализует ряд операций треугольной матрицы. Вычитание и умножение треугольной матрицы оставлены для упражнений в конце главы. Учитывая то ограничение, что мы должны использовать только статические массивы, наш класс ограничивает размер строки и столбца числом 25. При этом мы будем иметь 300=(25²-25)/2 нулевых элементов, поэтому массив М должен содержать 325 элементов.

Спецификация класса TriMat

ОБЪЯВЛЕНИЕ

#include <iostream.h>

#include <stdlib.h>

// максимальное число элементов и строк

// верхней треугольной матрицы

const int ELEMENTLIMIT = 325;

const int ROWLIMIT = 25;

class TriMat

{

private:

// закрытые данные-члены

int rowTable[ROWLIMIT]; // начальный индекс строки в М

int n; // размер строки/колонки

double М[ELEMENTLIMIT];

public:

// конструктор с параметрами TriMat(int matsize);

// методы доступа к элементам матрицы

void PutElement (double item, int i, int j);

double GetElement(int i, int j) const;

// матричные арифметические операции

TriMat AddMat(const TriMat& A) const;

double DelMat(void) const;

// матричные операции ввода/вывода

void ReadMat(void);

void WriteMat(void) const;

// получить размерность матрицы

int GetDimension(void) const;

};

ОПИСАНИЕ

Конструктор принимает число строк и столбцов матрицы. Методы PutEle-ment и GetElement сохраняют и возвращают элементы верхней треугольной матрицы. GetElement возвращает 0 для элементов ниже диагонали. AddMat возвращает сумму матрицы А с текущим объектом. Этот метод не изменяет значение текущей матрицы. Операторы ввода/вывода ReadMat и WriteMat работают со всеми элементами матрицы n x n. Сам метод ReadMat сохраняет только верхне-треугольные элементы матрицы.

Пример

#include trimat.h // включить класс TriMat

TriMat A (10), В (10), С (10); // треугольные матрицы 10x10

A.ReadMat (); // ввести матрицы А и В

B.ReadMat ();

С = A. AddMat (В); // вычислить С = А + В

C.WriteMat (); // печатать С

Реализация класса TriMat

Конструктор инициализирует закрытый член n параметром matsize. Таким образом задается число строк и столбцов матрицы. Этот же параметр используется для инициализации массива rowTable, который используется для доступа к элементам матрицы. Если matsize превышает ROWLIMIT, выдается сообщение об ошибке и выполнение программы прерывается.

// инициализация n и rowTable

TriMat::TriMat (int matsize)

{

int storedElements = 0;

// прервать программу, если matsize больше ROWLIMIT

if (matsize > ROWLIMIT)

{

cerr << "Превышен размер матрицы" << ROWLIMIT << "x" << ROWLIMIT << endl;

exit (1);

}

n = matsize;

// задать таблицу

for (int i = 0; i < n; i++)

{

rowTable [i] = storedElements;

storedElements += n - i;

}

}

Матричные методы доступа. Ключевым моментом при работе с треугольными матрицами является возможность эффективного хранения ненулевых элементов в линейном массиве. Чтобы достичь такой эффективности и все же использовать обычные двумерные индексы i и j для доступа к элементу матрицы, нам необходимы функции PutElement и GetElement для сохранения и возвращения элементов матрицы в массиве.

Метод GetDimension предоставляет клиенту доступ к размеру матрицы. Эта информация может использоваться для обеспечения того, чтобы методам доступа передавались параметры, соответствующие правильной строке и столбцу:

// возвратить размерность матрицы n

int TriMat::GetDimension(void) const

{

return n;

}

Метод PutElement проверяет индексы i и j. Если j ³ i, мы сохраняем значение данных в М, используя функцию доступа к матрице для треугольных матриц: Если i или j не находится в диапазоне 0.. (n-1), то программа заканчивается:

// записать элемент матрицы [i,j] в массив М

void TriMat::PutElement (double item, int i, int j)

{

// прервать программу, если индексы элемента вне

// индексного диапазона

if ((i < 0 || i >= n) || (j < 0 |1 j >= n))

{

cerr << "PutElement: индекс вне диапазона 0—"<< n-1 << endl;

exit (1);

}

// все элементы ниже диагонали игнорируются if (j >= i)

M[rowTable[i] + j-i] = item;

}

Для получения любого элемента метод GetElement проверяет индексы i и j. Если i или j не находится в диапазоне 0…(n — 1), программа заканчивается. Если j<i, то элемент находится в нижней треугольной матрице со значением 0. GetElement просто возвращает несохраняемое значение 0. В противном случае, j³i, и метод доступа может возвращать элемент из массива М:

// получить матричный элемент [i, j] массива М

double TriMat::GetElement(int i, int j) const

{

// прервать программу, если индексы вне индексного диапазона

if ((i < 0 || i >= п) || (j < 0 |I j >= n))

{

cerr << "GetElement: индекс вне диапазона 0—"<< n-1 << endl;

exit (1);

}

if (j >= i)

// вернуть элемент, если он выше диагонали

return M[rowTable [i] + j-i];

else

// элемент равен 0, если он ниже диагонали

return 0;

}

Ввод/вывод матричных объектов. Традиционно, ввод матрицы подразумевает, что данные вводятся построчно с полным набором значений строк, и столбцов. В объекте TriMat нижняя треугольная матрица является нулевой и значения не сохраняются в массиве. Тем не менее, пользователю предлагается ввести эти нулевые значения для сохранения обычного матричного ввода.

// читать элементы матрицы построчно, клиент должен ввести

// все (n x n) элементов

void TriMat::ReadMat (void)

double item;

int i, j;

for(i = 0; i<n; i++) // сканировать строки

for(j = 0; j<n; j++) //для каждой строки сканировать столбцы

{

cin >> item; //читать [i, j ]-й элемент матрицы

PutElement (item, i, j); // сохранить этот элемент

//построчная выдача в поток элементов матрицы

void TriMat::WriteMat (void) const

{

int i,j;

// установка режима выдачи

cout. setf (ios::fixed);

cout.precision (3);

cout.setf (ios::showpoint);

for (i =0; i < n; i++)

{

for (j = 0; j < n; j++)

cout << setw(7) << GetElement (i,j);

cout << endl;

}

}

Матричные операции. Класс TriMat имеет методы для вычисления суммы двух матриц и детерминанта матрицы. Метод AddMat принимает единственный параметр, который является правым операндом в сумме. Текущий объект соответствует левому операнду. Например, сумма треугольных матриц X и Y использует метод AddMat для объекта X. Предположим, сумма сохраняется в объекте Z. Для вычисления

Z = Х + Y используйте оператор

Z = X.AddMat(Y);

Алгоритм сложения двух объектов типа TriMat возвращает новую матрицу В с элементами B_i,j = CurrentObjecty_i,j + A_i,j:

// возвращает сумму текущей и матрицы А.

// Текущий объект не изменяется

TriMat TriMat::AddMat (const TriMat& A) const

int i, j;

double itemCurrent, itemA;

TriMat B(A.n); // в В будет искомая сумма

for (i = 0; i < n; i++) // цикл по строкам

{

for (j = i; j < n; j++) // пропускать элементы ниже диагонали

{

itemCurrent=GetElement i, j);

itemA = A.GetElement (i, j);

B. PutElement (itemCurrent + itemA, i, j);

}

}

return B;

}

Метод DetMat возвращает детерминант текущего объекта. Возвращаемое значение - это действительное число, которое является произведением элементов диагонали. Полный текст кода для реализации класса TriMat можно найти в программном приложении.

Программа 3.5. Операции с классом TriMat

Тестовая программа иллюстрирует класс TriMat с операциями ввода/вывода, а также матричного суммирования и определения детерминанта. Каждая секция программы снабжена комментариями.

#include <iostream.h>

#include <iomanip.h>

#include "trimat.h" // включить класс TriMat

void main(void)

{

int n;

// задать размер однородной матрицы

cout << "Каков размер матрицы? ";

cin >> n;

// объявить три матрицы размером (n x n)

TriMat A(n), B(n), C(n);

// читать матрицы А и В

cout<<"Введите некоторую "<<n<<"х"<<n<<

"треугольную матрицу" << endl;

A.ReadMat();

cout << endl;

cout << "Введите некоторую " << n << " x " << n <<

" треугольную матрицу" << endl;

B.ReadMat();

cout << endl;

// выполнить операции и напечать результат

cout << "Сумма А + В" << endl;

С = A.AddMat(В);

C.WriteMat();

Cout << endl;

cout << "Детерминант А+В= " << С.DetMat () << endl;

/*

<Выполнение программы 3.5>

Каков размер матрицы? 4

Введите некоторую 4x4 треугольную марицу

Введите некоторую 4x4 треугольную матрицу

 

Сумма А + В

2.000 6.000 10.000 12.000

0.000 4.000 10.000 2.000

0.000 0.000 6.000 8.000

0.000 0.000 0.000 7.000

Детерминант А+В= 336.000 */