QR-разложение
Среди матричных разложений особую роль играют ортогональные преобразования, обладающие свойством сохранения нормы вектора. Напомним из курса линейной алгебры, что матрица Q называется ортогональной, если QT Q=I, где I – единичная матрица. Свойство сохранения нормы вектора при ортогональных преобразованиях, т. е. |Qx|=|x|, дает рецепт поиска псевдорешения вырожденных СЛАУ, а именно, замену исходной задачи минимизации невязки с "плохой" матрицей |Аx-b| задачей |QT (Ax-b)|, в которой матрица уже будет "хорошей" благодаря специальному построению матрицы Q. Таким образом, ортогональные разложения используются при решении любых систем (в том числе с прямоугольной матрицей А, причем как переопределенных, так и недоопределенных).
Одним из важнейших вариантов ортогональных разложений некоторой матрицы А является QR-разложение вида A=QR, где Q – ортогональная матрица, а R – верхняя треугольная матрица:
- qr (A) – QR – разложение:
- А – вектор или матрица любого размера.
Результатом действия функции qr (А) является матрица, составленная из матриц Q и R соответственно (подобно рассмотренному в предыдущем разделе LU-разложению). Выделить матрицы QR-разложения несложно при помощи встроенной функции выделения подматрицы submatrix (листинг 8.22).
Листинг 8.22. QR-разложение сингулярной матрицы:
Если бы исходная СЛАУ Aх=b не была вырожденной, то можно было сразу записать: QT Q-Rx=QT b, откуда следует (благодаря ортогональности матрицы Q): Rx=QT b. Так как матрица к – треугольная, решение данной системы получается по формулам прямого хода. Если использовать нашу пользовательскую функцию решения треугольной системы (см. разд. 8.3. Т), то результат исходной СЛАУ запишется в виде одной строки кода: trg(R,QT b) (соответствующий пример решения невырожденной СЛАУ вы найдете на компакт-диске).
Обратимся теперь к проблеме решения СЛАУ с сингулярной квадратной NxN или прямоугольной NxM матрицей А. Если ее ранг равен k (он может быть меньше N и м, как в листинге 8.22, где N=M=S, a k=2), то получающаяся треугольная матрица R имеет следующую структуру:
Где R1 – верхняя треугольная матрица, a R2 – просто некоторая матрица, а нули обозначают, в общем случае, нулевые матрицы соответствующих размеров.
Если система вырожденная, то она имеет бесконечное множество псевдорешений (векторов, минимизирующих норму невязки). При помощи QR-разложения можно сразу выписать одно из них (правда, не обладающее минимальной нормой). В нашем примере последняя строка матрицы R содержит одни нули, поэтому последняя компонента вектора псевдорешения х может быть абсолютно любой. Если положить х2=0, то остальные компоненты х определятся из треугольной СЛАУ R1x=QT b, как это проиллюстрировано листингом 8.23.