Оцените 1 обновление до QR-факторизации
[Q1,R1] = qrupdate(Q,R,u,v)
[Q1,R1] = qrupdate(Q,R,u,v) когда [Q,R] = qr(A) является исходным QR-факторизацией A, возвращает QR-факторизацию A + u*v', где u и v являются векторами-столбцами соответствующих длин.
Матрица
mu = sqrt(eps) mu = 1.4901e-08 A = [ones(1,4); mu*eye(4)];
является хорошо известным примером в наименьших квадратах, который указывает на опасность формирования A'*A. Вместо этого мы работаем с QR-факторизацией - ортонормальной Q и верхней треугольной R.
[Q,R] = qr(A);
Как мы ожидаем, R является верхним треугольным.
R =
-1.0000 -1.0000 -1.0000 -1.0000
0 0.0000 0.0000 0.0000
0 0 0.0000 0.0000
0 0 0 0.0000
0 0 0 0В этом случае верхние треугольные значения R, за исключением первой строки, находятся в порядке sqrt(eps).
Рассмотрим векторы обновления
u = [-1 0 0 0 0]'; v = ones(4,1);
Вместо вычисления довольно тривиального QR-факторизации этого ранга одно обновление к A с нуля с
[QT,RT] = qr(A + u*v')
QT =
0 0 0 0 1
-1 0 0 0 0
0 -1 0 0 0
0 0 -1 0 0
0 0 0 -1 0
RT =
1.0e-007 *
-0.1490 0 0 0
0 -0.1490 0 0
0 0 -0.1490 0
0 0 0 -0.1490
0 0 0 0мы можем использовать qrupdate.
[Q1,R1] = qrupdate(Q,R,u,v)
Q1 =
-0.0000 -0.0000 -0.0000 -0.0000 1.0000
1.0000 -0.0000 -0.0000 -0.0000 0.0000
0.0000 1.0000 -0.0000 -0.0000 0.0000
0.0000 0.0000 1.0000 -0.0000 0.0000
-0.0000 -0.0000 -0.0000 1.0000 0.0000
R1 =
1.0e-007 *
0.1490 0.0000 0.0000 0.0000
0 0.1490 0.0000 0.0000
0 0 0.1490 0.0000
0 0 0 0.1490
0 0 0 0Обратите внимание, что обе факторизации верны, даже если они разные.
qrupdate работает только для полных матриц.
qrupdate использует алгоритм в разделе 12.5.1 третьего издания Matrix Computations Голуба и ван Лоуна. qrupdate полезно, так как, если мы принимаем N = max(m,n), тогда вычисление нового QR-факторизации с нуля примерно O (N3) алгоритм, в то время как простое обновление существующих факторов таким образом является O (N2) алгоритм.
[1] Golub, Gene H. and Charles Van Loan, Matrix Computations, Third Edition, Johns Hopkins University Press, Балтимор, 1996
cholupdate | qr