П 2.2 Создание иерархии классов вычислительных методов алгебры

Рассмотрим иерархию классов вычислительных методов алгебры следующего вида:

• VMA

• FactorizationAlgorithms

• LU_decomposition

• LDU_decomposition

• STS_decomposition

• SDS_decomposition

• QR_decomposition

• Eigenvalues

• DirectMethodsE

• danilevskyMethod

• IterationMethodsE

• PartialProblem

• iterationMethod

• CompleteProblem

• jacobiMethod

• qrMethod

• SLAU

• DirectMethods

• DirectMethodsFactorization

• gaussMethod

• gaussChooseElement

• gaussJordanMethod

• squareMethod

• DirectMethodsNF

• sweepMethod

• IterationMethods

• simpleIterationMethod

• zeidelMethod

• methodSkorSpusk

Рис. 2. Объектная классификация методов линейной алгебры.

Вершиной иерархии является базовый класс «VMA».

Класс «FactorizationAlgorithms» содержит методы факторизации.

Класс «Eigenvalues» предназначен для реализации численных методов нахождения собственных значений и собственных векторов матриц. Методы этого класса подразделяются на прямые – «DirectMethodsE» и итерационные – «IterationMethodsE». Класс «IterationMethodsE» разбивается на два производных класса: итерационные методы, применяемые к решению частичной проблемы нахождения собственных значений, им соответствует класс «PartialProblem» и итерационные методы, применяемые к решению полной проблемы нахождения собственных значений – «CompleteProblem».

В классе «SLAU» описаны методы для решения систем линейных алгебраических уравнений. Данные методы подразделяются на прямые и итерационные. В связи с этим выделены классы для реализации прямых методов решения СЛАУ «DirectMethods» и итерационных «IterationMethods». Класс «DirectMethods» разбивается на два производных класса: прямые методы, использующие факторизацию, им соответствует класс «DirectMethodsFactorization» и прямые методы, не использующие факторизацию, – «DirectMethodsNF».

Среди алгоритмов факторизации выделены пять методов: LU, LDU, S^TS, S^TDS и QR-разложение.

LU-разложение – это представление квадратной матрицы А в виде произведения нижней треугольной матрицы L на верхнюю треугольную матрицу U, т.е. . Данное разложение возможно в случае, когда все угловые миноры матрицы А отличны от нуля, и является единственным, если заранее оговорены элементы главной диагонали треугольных матриц [19].

Пусть L – нижняя треугольная матрица с единичной диагональю, а U – верхняя треугольная матрица с ненулевыми диагональными элементами. Значения элементов матрицы L и U находятся по рекуррентным соотношениям:

,

, (1)

LU-разложение, полученное по формулам (1), применяется для построения LDU-разложения.

Пример 1. Для заданной матрицы получить
LU-разложение.

Решение:

Воспользуемся рекуррентными формулами (1)

При к=1:

При к=2:

При к=3:

В результате получены две треугольные матрицы:

, .

LDU-разложение– это представление квадратной матрицы А в виде произведения LDU, где L – нижняя треугольная матрица с единичной диагональю, D – диагональная матрица, а U – верхняя треугольная матрица с единичной диагональю.

, , .

Элементы рассчитываются по формулам (1).

Пример 2. Дана матрица . Получить ее
LDU-разложение.

Решение:

В предыдущем примере получены матрицы L и U вида:

, .

Матрица L не изменяется. Матрицу D выделим из матрицы U.

Получаем решение:

, , .

S^TDS-разложение – это представление симметрической матрицы А в виде произведения матриц S^T, D и S, где S – верхняя треугольная матрица, S^T – транспонированная к ней матрица (нижняя треугольная), D – диагональная матрица с элементами, равными +1 или –1.

, .

Значения коэффициентов данных матриц находятся по формулам [19]

(2)

S^TS-разложение – это представление симметрической положительно определенной матрицы А в виде произведения матриц S^T и S, где S – верхняя треугольная матрица, S^T – транспонированная к ней матрица (нижняя треугольная).

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

, .

Значения коэффициентов матрицы S находятся по формулам [19].

(3)

Пример 3. Дана матрица . Получить ее S^TS-разложение.

Решение:

Матрица А является симметрической и положительно определенной. Воспользуемся формулами (2), получаем:

Таким образом, получили матрицу .

QR-разложение – это представление квадратной матрицы А в виде произведения ортогональной матрицы Q на верхнюю треугольную матрицу R.

QR-разложение может быть получено различными методами. Рассмотрим построение QR-разложения с помощью преобразования Хаусхолдера, которое позволяет обратить в нуль группу поддиагональных элементов столбца матрицы.

Преобразование Хаусхолдера осуществляется с использованием матрицы Хаусхолдера (матрица отражения), имеющей следующий вид [20]:

, (4)

где w – произвольный ненулевой вектор-столбец, E – единичная матрица.

Любая матрица такого вида является симметрической и ортогональной.

Рассмотрим подробнее реализацию данного преобразования. Положим и построим преобразование Хаусхолдера , переводящее матрицу в матрицу с нулевыми элементами первого столбца под главной диагональю

.

Для этого построим вектор [20]:

(5)

где .

Матрица Хаусхолдера строится согласно формуле (4)

.

Тогда легко проверить, что

. (6)

Для того чтобы обнулить поддиагональные элементы второго столбца матрицы , выберем вектор w ₂ так, что

,

где .

Тогда лежащие ниже главной диагонали элементы двух первых столбцов матрицы обратятся в нуль.

Продолжая этот процесс с помощью векторов w _i, имеющих нули в первых i-1 позициях, получаем:

, (7)

где R – верхняя треугольная матрица.

Положим

. (8)

Тогда можно записать, что .

Так как каждая матрица ортогональна, то и их произведение Q также будет ортогональной матрицей. Следовательно, .

Тогда имеет место соотношение , которое и представляет собой QR-разложение матрицы A.

Пример 4. Дана матрица . Получить ее QR-разложение.

Решение:

Выберем вектор согласно формуле (5):

,

где , .

Тогда .

Построим матрицу согласно формуле (6):

,

.

Выберем вектор по формуле (5):

,

где , .

Тогда .

Построим матрицу по формуле (6):

,

.

Построим матрицу Q согласно формуле (8):

,

.

Убедимся, что матрица Q – ортогональна.

.

Построим верхнюю треугольную матрицу R по формуле (7):

,

.

Получаем решение:

, .

Пример 5. Реализовать алгоритм S^TS-разложения для произвольной симметрической матрицы.

При описании алгоритма используются объекты класса «SquareMatrix» и методы данного класса: getRowCount (количество строк матрицы), getElement (получение значения элемента) и setElement (установка значения). Реализация примера на языке программирования С++ может иметь следующий вид:

void FactorizationAlgorithms:: STS_decomposition (SquareMatrix A, SquareMatrix S) {

for (int i = 0; i < A. getRowCount(); i++) {

for (int j = 0; j < i; j++) {

double sum = 0;

for (int k = 0; k < j; k++) {

sum += S.getElement(k, i) * S.getElement(k, j);

}

S.setElement(j, i,(A.getElement(i, j)-sum)/S.getElement(j, j));

}

double temp = A.getElement(i, i);

for (int k = 0; k < i; k++) {

temp -= S.getElement(k, i) * S.getElement(k, i);

}

S.setElement(i, i, sqrt(temp));

}

}

Пример 6. Реализовать следующую иерархию классов.

• VMA

• FactorizationAlgorithms

• LU_decomposition

• LDU_decomposition

• STS_decomposition

• SDS_decomposition

• QR_decomposition

• Eigenvalues

• DirectMethodsE

• IterationMethodsE

• SLAU

• DirectMethods

• IterationMethods

Реализуем пример на языке программирования С++

/* Базовый класс «ВМА» */

class VMA{

public:

VMA(){};

};

/*Класс «Алгоритмы факторизации» */

class FactorizationAlgorithms: public VMA{

public:

FactorizationAlgorithms(){};

/* LU разложение */

void LU_decomposition(SquareMatrix A, SquareMatrix LU);

/* LDU разложение*/

void LDU_decomposition (SquareMatrix A, SquareMatrix L, DiagonalMatrix D, SquareMatrix U);

/* STS разложение*/

void STS_decomposition (SquareMatrix A, SquareMatrix S);

/* SDS разложение */

void SDS_decomposition (SquareMatrix A, SquareMatrix S, SquareMatrix D);

/* QR разложение */

void QR_decomposition (SquareMatrix A, SquareMatrix Q, SquareMatrix R);

};

/* Класс «Собственные значения» */

class Eigenvalues: public VMA{

public:

Eigenvalues (){};

};

/* Класс «Прямые методы нахождения собственных значений»*/

class DirectMethodsE: public Eigenvalues {

public:

DirectMethodsE(){};

};

/* Класс «Итерационные методы нахождения собственных значений»*/

class IterationMethodsE: public Eigenvalues {

public:

IterationMethodsE (){};

};

/* Класс «Системы линейных алгебраических уравнений» */

class SLAU: public VMA{

public:

SLAU(){};

};

/* Класс «Прямые методы решения СЛАУ» */

class DirectMethods: public SLAU{

public:

DirectMethods(){};

};

/* Класс «Итерационные методы решения СЛАУ» */

class IterationMethods: public SLAU{

public:

IterationMethods(){};};

Поиск по сайту: