Задача наименьших квадратов заключается в минимизация евклидовой длины вектора невязок || Ax-b ||.
Теорема 1. Пусть А – m´n– матрица ранга k, представленная в виде
A=HRKT (2)
где H ортогональная m ´ m матрица; R – m ´ n– матрица вида
, (3)
где: R 11 – k x k– матрица ранга k; K – ортогональная k x k– матрица. Определим вектор
(4)
и введем новую переменную
. (5)
Определим 
как единственное решение системы R 11 y 1= g 1. Тогда:
1. Все решения задачи о минимизации || Ax-b || имеют вид 
, где y 2 произвольно.
2. Любой такой вектор 
приводит к одному и тому же вектору невязки 
. (6)
3. Для нормы r справедливо 
4. Единственным решением минимальной длины является вектор 
Доказательство. В выражении для квадрата нормы невязки заменим A на HRKT в соответствии с (2) и умножая на ортогональную матрицу HT (умножение на ортогональную матрицу не меняет евклидову норму вектора) получим
(7)
Далее из (3) и (5) следует, что
.
Из (4) следует
Подставляя оба последних выражения в (7) получим
Последнее выражение имеет минимальное значение 
при R 11 y 1= g 1, а в этом уравнении единственным решением является 
, так как ранг матрицы R 11 равен к. Общее решение y выражается формулой 
, где y 2 произвольно. Для вектора 
имеем
,
что устанавливает равенство (3). Среди векторов 
наименьшую длину имеет тот, для которого y 2=0. Отсюда следует, что решением наименьшей длины будет вектор 
. Теорема доказана.
Всякое разложение матрицы А типа (2) мы будем называть ортогональным разложением А. Заметим, что решение минимальной длины, множество всех решений и минимальное значение для задачи минимизации || Ax-b || определяются единственным образом. Они не зависят от конкретного ортогонального разложения.
При проведении разложения необходимо приводить матрицы к диагональному виду. Для этого обычно используются два преобразования: Гивенса и Хаусхолдера, оставляющие нормы столбцов и строк матриц неизменными.
|
|
Ортогональное вращение Гивенса
Лемма. Пусть дан 2–вектор 
, причем 
либо 
.Существует ортогональная 2´2 матрица такая, что:
(8)
Доказательство. Положим:
.
Далее прямая проверка.
Матрица преобразования представляет собой матрицу вращений
или отражений
Ортогональное преобразование Хаусхолдера
Применяется для преобразования матриц к диагональному виду. Матрица преобразования представляет из себя следующее выражение: 
, (9)
или, если вектор v нормирован, т.е. используется вектор единичной длины 
, то 
. В обоих случаях H – симметричная и ортогональная матрица. Покажем это:
.
Отсюда следует: что 
, т.е. симметричность и ортогональность. В комплексном случае матрица 
эрмитова[1] и унитарна[2]. Предположим, что дан вектор х размерности m, тогда существует матрица H такая, что 
, где
а s = + 1, при положительной первой компоненте вектора х и = –1, при отрицательной.
Доказательство. Положим 
действительная матрица. Любую действительную матрицу можно привести в треугольному виду
Далее принимаем во внимание то, что 
и получаем следующее:
