Обновление ранга 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 by Golub and van Loan. qrupdate полезен, поскольку, если мы берем N = max(m,n), тогда вычисление новой факторизации QR с нуля является примерно алгоритмом O (N3), в то время как простое обновление существующих факторов таким образом является алгоритмом O (N2).
[1] Голуб, Джин Х. и Чарльз Ван Займ, Matrix Computations, третье издание, Johns Hopkins University Press, Балтимор, 1996
cholupdate | qr