Алгоритмы формирования матриц

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

Рис.3.1 – алгоритм формирования нижней и верхней треугольных

матриц с ненулевыми элементами на главных диагоналях

Рис.3.2 – алгоритм формирования неособенной квадратной матрицы

как произведение нижней и верхней треугольных матриц

с ненулевыми элементами на главных диагоналях

Методы разложения матриц

Разложение неособенной квадратной матрицы

в произведение двух треугольных матриц: верхней и нижней с единичной главной диагональю

Выше было указано, что всякую квадратную матрицу имеющую отличные от нуля главные диагональные миноры ….; можно представить в виде произведения двух треугольных матриц (верхней и нижней)причем это разложение будет единственнымесли зафиксировать диагональные элементы одной из матриц (напримерпринять их равными 1). Следовательно,, гдеи– нижняя и верхняя треугольные матрицы соответственно.

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

При из произведения матрицимеем:

Распространив эти формулы на общий случай (- произвольное), получим формулы для вычисления элементов матрицы:

и формулы для вычисления элементов матрицы :

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

Рис.3.3 – алгоритм разложения неособенной квадратной матрицы

в произведение двух треугольных матриц: верхней и нижней с единичной главной диагональю

Рис.3.4 – алгоритм разложения симметрической положительно определенной матрицы в произведение нижней треугольной

и транспонированной ей матрицы

Рис.3.5 – алгоритм разложения положительно определенной

ленточной матрицы в произведение нижней треугольной

и транспонированной ей матрицы

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

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

Разложение положительно определенной ленточной матрицы в произведение двухвзаимно транспонированных треугольных матриц

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

Разложение неособенной квадратной матрицы в произведение нижней треугольной матрицы с единичной диагональю и матрицы с ортогональными строками

Пусть дана действительная неособенная матрица



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