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