§ 5.3. Типы используемых матриц

Эффективность вычислений в линейной алгебре существенно зависит от умения использовать специальную структуру и свойства используемых в расчетах матриц. Напомним некоторые важные типы матриц.

Квадратная матрица А называется диагональной, если ее элементы удовлетворяют условию для (все отличные от нуля элементы расположены на главной диагонали):

Диагональную матрицу, у которой все элементы главной диагонали равны единице, называют единичной и обозначают буквой Е:

Пример 5.3. Вычислим норму единичной матрицы

По определению, Следовательно,

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

Нижняя и верхняя треугольная матрицы имеют соответственно следующий вид:

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

Квадратная матрица А называется симметричной, если она совпадает со своей транспонированной матрицей (или, что то же, для всех

Будем называть симметричную матрицу А положительно определенной и писать если для всех векторов квадратичная форма

принимает положительные значения.

Обозначим через и минимальное и максимальное собствен значения матрицы А. Известно, что для симметричной матрицы

и матрица А положительно определена тогда и только тогда, когда все ее собственные значения положительны.

Одна из трудностей практического решения систем большой размерности связана с ограниченностью оперативной памяти ЭВМ. Хотя объем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее еще быстрее возрастают потребности практики в решении задач все большей размерности (напомним, что

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

Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ Заметим, что для хранения диагональной матрицы достаточно отвести массив длины и расположить в нем элементы Для хранения треугольной матрицы достаточно ячеек памяти, что примерно вдвое меньше места, отводимого для хранения матрицы общего вида. Столько же ячеек используется для хранения симметричной матрицы, поскольку такая матрица полностью определяется, например, заданием своей нижней треугольной части.

К счастью, приложения очень часто приводят к матрицам, в которых число ненулевых элементов много меньше общего числа элементов матрицы. Такие матрицы принято называть разреженными. Напротив, матрицы общего вида называют плотными (или заполненными). Разреженность матрицы является очень ценным свойством, поскольку объем информации, который следует обрабатывать и хранить в памяти ЭВМ, для таких матриц даже очень большого размера может оказаться не слишком большим. Для хранения всех ненулевых элементов и информации об их расположении оказывается достаточным использовать только оперативную память ЭВМ. Иногда элементы матрицы известны либо вычисляются по простым формулам и необходимость в их хранении отпадает.

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

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

Простой пример разреженной матрицы дает трехдиаюналъная матрица

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

Многие приложения приводят к системам уравнений с так называемыми ленточными матрицами. Матрица А называется ленточной полушириной ленты, равной I, если для Все ненулевые элементы такой матрицы расположены на ближайших к главной диагоналях матрицы; число принято называть шириной ленты. Схематически ленточная матрица представлена на рис. 5.1. Частным случаем ленточной матрицы при является трехдиагональная матрица. Ясно, что в случае ленточная матрица является разреженной.

Рис. 5.1.