qrupdate

---

QR 分解的秩 1 更新

函数库: TyMath

语法

Q1,R1 = qrupdate(Q,R,u,v)

说明

如果 Q,R = qr(A) 是 A 的原始 QR 分解，Q1,R1 = qrupdate(Q,R,u,v) 返回 A + u*v' 的 QR 分解，其中 u 和 v 是相应长度的列向量。

示例

QR 分解的秩 1 更新

using TyMath
mu = sqrt(eps())

mu = 1.4901161193847656e-8

A = Matrix([ones(1,4); mu*I(4)]);

是公认的最小平方示例，指明组成 A'*A 的危险。但我们使用 QR 分解 – 正交 Q 和上三角 R。

Q,R = qr(A)

LinearAlgebra.QRCompactWY{Float64, Matrix{Float64}, Matrix{Float64}}
Q factor: 5×5 LinearAlgebra.QRCompactWYQ{Float64, Matrix{Float64}, Matrix{Float64}}
R factor:
4×4 Matrix{Float64}:
 -1.0  -1.0         -1.0         -1.0
  0.0   2.10734e-8   1.05367e-8   1.05367e-8
  0.0   0.0          1.82501e-8   6.08337e-9
  0.0   0.0          0.0          1.72064e-8

在这种情况下，除了第一行，R 的上三角项都与 sqrt(eps) 类似。

请考虑更新向量

u = [-1, 0, 0, 0, 0];
v = ones(4,1);

通过以下项从头更新到 A，而不是计算该秩毫无价值的 QR 分解：

QT,RT = qr(A + u*v')
QT = Matrix(QT)

QT = 5×4 Matrix{Float64}:
  0.0   0.0   0.0   0.0
 -1.0   0.0   0.0   0.0
  0.0  -1.0   0.0   0.0
  0.0   0.0  -1.0   0.0
  0.0   0.0   0.0  -1.0
RT = 4×4 Matrix{Float64}:
 -1.49012e-8   0.0          0.0          0.0
  0.0         -1.49012e-8   0.0          0.0
  0.0          0.0         -1.49012e-8   0.0
  0.0          0.0          0.0         -1.49012e-8

我们可以使用 qrupdate。

Q1,R1 = qrupdate(Q,R,u,v)
Q1 = Matrix(Q1)

Q1 = 5×4 Matrix{Float64}:
  0.0  2.98023e-8  0.0  0.0
 -1.0  0.0         0.0  0.0
  0.0  1.0         0.0  0.0
  0.0  0.0         1.0  0.0
  0.0  0.0         0.0  1.0
R1 = 4×4 Matrix{Float64}:
 -1.49012e-8  -6.61744e-24  -9.92617e-24  -9.92617e-24
  0.0          1.49012e-8   -3.30872e-24  -3.30872e-24
  0.0          0.0           1.49012e-8    0.0
  0.0          0.0           0.0           1.49012e-8

请注意这两个分解都正确，即使它们不同。

提示

qrupdate 仅适用于满矩阵

算法

qrupdate 使用由 Golub 与 van Loan 合著的 Matrix Computations 第三版第 12.5.1 节中的算法。qrupdate 很有用，因为如果我们采用 N = max(m,n)，则从头计算新的 QR 分解大体上属于 O(N3) 算法，而以此方式仅更新现有因子属于 O(N2) 算法。

另请参阅

cholupdate | lu