Файл: Маркова Вычислит методы алгебры Практикум.doc

.

Для этого построим вектор [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(){};};

Лабораторная работа № 3

Цель: изучить иерархию классов, представленную на рис. 2. Реализовать иерархию классов вычислительных методов алгебры. Изучить методы факторизации. Реализовать методы для LU-, LDU-, S^TDS - , S^TS и QR-разложения.

Задание

Разработайте базовый класс «VMA» с производными от него классами – «Алгоритмы факторизации» («FactorizationAlgorithms»), «СЛАУ» («SLAU»), «Собственные значения» («Eigenvalues»).

От класса «Eigenvalues» наследуйте 2 класса – «Прямые методы нахождения собственных значений» («DirectMethodsE») и «Итерационные методы нахождения собственных значений» («IterationMethodsE»).

От класса «СЛАУ» наследуйте 2 класса – «Прямые методы решения СЛАУ» («DirectMethods») и «Итерационные методы решения СЛАУ» («IterationMethods»).

В классе «FactorizationAlgorithms» реализуйте методы для LU-, LDU-, S^TS-, S^TDS и QR-разложения (LU_decomposition, LDU_decomposition, STS_decomposition, SDS_decomposition, QR_decomposition).

Для работы с матрицами используйте объекты матричного класса «SquareMatrix» и методы, реализованные в данном классе. Доступ к элементам осуществляется с помощью методов getElement и setElement.

Глава 3 решение систем линейных алгебраических уравнений

В главе 3 рассматриваются методы решения систем линейных алгебраических уравнений. К решению таких систем приводят многие прикладные задачи. Наряду с проблемой решения неоднородной системы линейных алгебраических уравнений в данной главе будет изучена проблема обращения матриц, а также задача вычисления определителя матрицы.

Линейная неоднородная задача для систем линейных алгебраических уравнений (СЛАУ) записывается в виде [19; 8]

АХ = f или , (1)

где  действительная матрица размера (n*n), i, j  переменные, соответствующие номерам строк и столбцов (целые числа);  вектор-столбец,  вектор-столбец неизвестных,  n-мерное евклидово пространство, верхний индекс «T» обозначает операцию транспонирования.