Оцените 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