Задание. Разработайте базовый класс «VMA» с производными от него классами – «Алгоритмы факторизации» («FactorizationAlgorithms»)

Разработайте базовый класс «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» обозначает операцию транспонирования.

Требуется найти решение системы (1), подстановка которого в (1) приводит к верному равенству .

Из линейной алгебры известно, что решение задачи (1) существует и единственно, если детерминант матрицы А отличен от нуля, т.е. (А - невырожденная матрица, называемая также неособенной). Если определитель матрицы системы равен нулю, то система уравнений либо не имеет решения, либо имеет их бесчисленное множество.

Характер задачи и точность получаемого решения в большой степени зависят от ее обусловленности, являющейся важнейшим математическим понятием, влияющим на выбор метода ее решения.

Обусловленность задачи определяется числом обусловленности , где - норма матрицы А, а - норма обратной матрицы. Чем больше это число, тем хуже обусловленность системы.

Число обусловленности характеризует степень зависимости относительной погрешности решения СЛАУ от погрешности исходных данных. Пусть , , – погрешности коэффициентов матрицы, правой части и вектора решений соответственно, тогда справедливы следующие неравенства [19]:

.

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

При решении СЛАУ на компьютере из-за погрешностей округлений не всегда удается получить точное равенство определителя нулю, т.е. можем получить . В этом случае малые погрешности вычислений могут привести к существенным погрешностям в решении, как в случае плохо обусловленной системы.

Поясним связь величины определителя матрицы системы с понятием обусловленности на примере двумерной задачи [8].

Имеем систему из двух линейных уравнений:

Точным решением этой задачи является вектор , компоненты которого определяются координатами точки пересечения двух прямых, соответствующих уравнениям (см. рис. 1).

,

.

Рис. 1. Точное решение.

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

Рис. 2. Характер обусловленности систем.

Рис. 2 является иллюстрацией возможных вариантов. Если det А существенно отличен от нуля, то точка пересечения пунктирных прямых, смещенных относительно сплошных прямых из-за погрешностей задания А и f, сдвигается несильно. Это свидетельствует о хорошей обусловленности системы.

Если определитель матрицы близок к нулю (), то небольшие погрешности исходных данных могут привести к большим погрешностям в решении. На рис. 2 прямые системы уравнений близки к параллельным, координаты точки пересечения этих прямых весьма чувствительны к изменению коэффициентов системы.

При прямые параллельны или совпадают, тогда решение задачи не существует или оно не единственно.

Условие является необходимым для плохой обусловленности системы линейных уравнений, но не достаточным. Например, система уравнений n-го порядка с диагональной матрицей с элементами не является плохо обусловленной, хотя ее определитель мал .

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

Под прямыми (точными) понимаются такие методы, которые позволяют в предположении отсутствия округлений получить точные значения неизвестных как результат выполнения конечного числа арифметических операций. Результат таких методов может быть выражен аналитической формулой.

К прямым методам относят методы исключения неизвестных (метод Гаусса и его модификации), метод квадратного корня для решения СЛАУ.

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

При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми, прежде всего из-за сложности хранения и обработки матриц большой размерности.

Методы, в которых при вычислении последующего приближения решения используются предыдущие, уже известные приближенные решения, называются итерационными. Для начала вычислений итерационные методы требуют задания одного или нескольких начальных приближений, которые задаются произвольно. Окончание итераций определяется либо заданием максимального числа итераций, либо условием Здесь -
i -тая компонента вектора приближенного решения, k - номер итерации, – заданная точность для поиска решения.

Условия и скорость сходимости каждого итерационного метода существенно зависят от свойств матрицы системы.

К итерационным методам решения СЛАУ относятся метод простых итераций, метод Зейделя и др.

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