АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. HMI/SCADA – создание графического интерфейса в SCADА-системе Trace Mode 6 (часть 1).
  2. I. Решение логических задач средствами алгебры логики
  3. II –I в. до н.э. – обострение классовых и социальных противоречий.
  4. III. Создание и обработка комплексного информационного объекта в виде презентации с использованием шаблонов.
  5. MathCad: понятие массива, создание векторов и матриц.
  6. V3: Создание советской политической системы. Конституция РСФСР 1918 г.
  7. А) совокупность предусмотренных законодательством видов и ставок налога, принципов, форм и методов их установления.
  8. А) Теория иерархии потребностей
  9. Агрессивная внешняя политика правящих классов Японии. Японо-китайская война 1894—1895 гг.
  10. Административное принуждение как один из административно – правовых методов. Понятие и особенности административного принуждения.
  11. Активный запрос на создание таблицы
  12. Алгебры и подалгебры.

 

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

 

• 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, STS, STDS и 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.

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

, , .

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

, .

 

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

(2)

 

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

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

, .

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

(3)

 

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

Решение:

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

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

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

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

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

 

, (4)

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

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

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

 

.

 

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

 

(5)

 

где .

 

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

 

.

 

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

 

. (6)

 

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

 

,

где .

 

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

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

 

, (7)

 

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

Положим

. (8)

 

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

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

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

 

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

Решение:

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

,

где , .

Тогда .

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

 

,

 

.

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

,

где , .

 

Тогда .

 

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

,

.

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

,

.

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

.

 

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

 

,

.

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

, .

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

При описании алгоритма используются объекты класса «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(){};};

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.025 сек.)