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

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

Ах = b, (4.3.1.I)

где А – матрица с размерами m x n, b – заданный вектор, x – искомый вектор, понимают вектор u, удовлетворяющий условию

, (4.3.1.II)

где || || - евклидова норма.

Если система (4.3.1.I) имеет классическое решение, то оно совпадает с обобщенным, и при этом . Однако, нахождение векторов, минимизирующих функционал невязки , имеет смысл и в отсутствии классического решения системы (4.3.1.I). Поэтому введение определения обобщенного решения существенно расширяет понятие искомого решения системы (4.3.1.I).

В работе Воеводина В.В. "Линейная алгебра" доказано, что для системы (4.3.1.I) всегда существует множество псевдорешений, а если рассмотреть так называемое нормальное псевдорешение, то есть решение с минимальной евклидовой нормой, то оно еще и единственно.

Для решения системы (4.3.1.I) в дипломной работе было использовано специальное представление матрицы, называемое сингулярным разложением. Известно, что любую действительную матрицу с размерами m x n можно представить в виде

, (4.3.1.III)

где матрица U (m x m) сформирована из m ортонормированных собственных векторов матрицы AA^T, матрица V (n x n) — из n ортонормированных собственных векторов матрицы A^TA, матрица S с размерами m x n имеет вид , или , при [9].

Диагональные элементы s_i являются неотрицательными значениями квадратных корней из общих собственных значений матриц AA^T и A^TA и называются сингулярными числами матрицы А. Если сингулярные числа упорядочены, то такое разложение называется сингулярным разложением матрицы А.

Зная сингулярное разложение, можно сразу выписать решение системы (4.3.1.I):

где A^#=VS^#U^T называется псевдообратной к А матрицей.

Преобразование прямоугольной матрицы А к двухдиагональному виду [11], [14]

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

Умножая слева и справа исходную матрицу А соответственно на специально подбираемые матрицы отражения P⁽^k⁾ и Q⁽^k⁾, приходят к верхней двухдиагональной форме