|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
П 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, STS, STDS и QR-разложение. LU-разложение – это представление квадратной матрицы А в виде произведения нижней треугольной матрицы L на верхнюю треугольную матрицу U, т.е. Пусть L – нижняя треугольная матрица с единичной диагональю, а U – верхняя треугольная матрица с ненулевыми диагональными элементами. Значения элементов матрицы L и U находятся по рекуррентным соотношениям:
LU-разложение, полученное по формулам (1), применяется для построения LDU-разложения. Пример 1. Для заданной матрицы Решение: Воспользуемся рекуррентными формулами (1) При к=1: При к=2: При к=3:
В результате получены две треугольные матрицы:
LDU-разложение– это представление квадратной матрицы А в виде произведения LDU, где L – нижняя треугольная матрица с единичной диагональю, D – диагональная матрица, а U – верхняя треугольная матрица с единичной диагональю.
Элементы
Пример 2. Дана матрица Решение: В предыдущем примере получены матрицы L и U вида:
Матрица L не изменяется. Матрицу D выделим из матрицы U. Получаем решение:
STDS-разложение – это представление симметрической матрицы А в виде произведения матриц ST, D и S, где S – верхняя треугольная матрица, ST – транспонированная к ней матрица (нижняя треугольная), D – диагональная матрица с элементами, равными +1 или –1.
Значения коэффициентов данных матриц находятся по формулам [19]
STS-разложение – это представление симметрической положительно определенной матрицы А в виде произведения матриц ST и S, где S – верхняя треугольная матрица, ST – транспонированная к ней матрица (нижняя треугольная). Для положительной определенности матрицы достаточно выполнения требования положительности диагональных элементов и их диагонального преобладания, т.е.
Значения коэффициентов матрицы S находятся по формулам [19].
Пример 3. Дана матрица Решение: Матрица А является симметрической и положительно определенной. Воспользуемся формулами (2), получаем: Таким образом, получили матрицу QR-разложение – это представление квадратной матрицы А в виде произведения ортогональной матрицы Q на верхнюю треугольную матрицу R. QR-разложение может быть получено различными методами. Рассмотрим построение QR-разложения с помощью преобразования Хаусхолдера, которое позволяет обратить в нуль группу поддиагональных элементов столбца матрицы. Преобразование Хаусхолдера осуществляется с использованием матрицы Хаусхолдера (матрица отражения), имеющей следующий вид [20]:
где w – произвольный ненулевой вектор-столбец, E – единичная матрица. Любая матрица такого вида является симметрической и ортогональной. Рассмотрим подробнее реализацию данного преобразования. Положим
Для этого построим вектор [20]:
где
Матрица Хаусхолдера строится согласно формуле (4)
Тогда легко проверить, что
Для того чтобы обнулить поддиагональные элементы второго столбца матрицы
где
Тогда лежащие ниже главной диагонали элементы двух первых столбцов матрицы Продолжая этот процесс с помощью векторов w i, имеющих нули в первых i-1 позициях, получаем:
где R – верхняя треугольная матрица. Положим
Тогда можно записать, что Так как каждая матрица Тогда имеет место соотношение
Пример 4. Дана матрица Решение: Выберем вектор
где Тогда Построим матрицу
Выберем вектор
где
Тогда
Построим матрицу
Построим матрицу 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(){};};
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.026 сек.) |