Householder¶
Copyright By PowCoder代写 加微信 powcoder
using LinearAlgebra
A = [1 1 1;
a₁ = A[:,1]
e₁ = [1,0,0,0]
y₁ = +norm(a₁)*e₁ + a₁ # + since sign(A[1,1])
w₁ = y₁/norm(y₁)
Q₁ = I – 2w₁ * w₁’
a¹₂ = (Q₁*A)[2:end,2]
e₁ = [1,0,0]
y₂ = -norm(a¹₂)*e₁ + a¹₂
w₂ = [0; y₂/norm(y₂)]
Q₂ = I – 2w₂ * w₂’
a²₃ = (Q₂*Q₁*A)[3:end,3]
e₁ = [1,0]
y₃ = -norm(a²₃)*e₁ + a²₃
w₃ = [0; 0; y₃/norm(y₃)]
Q₃ = I – 2w₃ * w₃’
R = Q₃*Q₂*Q₁*A
triu!(R) # sets all entries below diagonal to exact 0
Q = Q₁*Q₂*Q₃
4×3 Matrix{Float64}:
1.0 1.0 1.0
1.0 2.0 3.0
1.0 4.0 9.0
1.0 3.0 2.0
Q̂ = Q[:,1:3]
R̂ = R[1:3,1:3]
4×3 Matrix{Float64}:
1.0 1.0 1.0
1.0 2.0 3.0
1.0 4.0 9.0
1.0 3.0 2.0
function householderreflection(x)
y = copy(x)
y[1] += (x[1] ≥ 0 ? 1 : -1)*norm(x)
w = y/norm(y)
I – 2w * w’
end # created a full m x m matrix, m^2 operations
function householderqr(A)
m,n = size(A)
R = copy(A)
Q = Matrix(1.0I, m, m)
for j = 1:n
Qⱼ = householderreflection(R[j:end,j]) # O(m^2)
R[j:end,:] = Qⱼ*R[j:end,:] # O(m^2*n)
Q[:,j:end] = Q[:,j:end]*Qⱼ # O(m^2*n)
end # O(m^2*n^2) operations
householderqr (generic function with 1 method)
A = randn(5,4)
Q,R = householderqr(A)
([-0.543292330529727 0.8289969893804807 … -0.05546174197595224 0.08655216328260636; -0.33099656879563877 -0.08821184001113105 … -0.042197195805381484 -0.4765334995229451; … ; 0.7253661208730787 0.4896542588148441 … -0.21353887727169082 0.1282265741419465; -0.2583004415660153 -0.25538304234656106 … -0.5777519228187887 0.6894968956618123], [-1.6841729636405733 0.8178195480599021 1.1636659476245057 1.2448984448641258; 3.797783816741242e-16 2.4707371346408697 -0.49064176553045175 -0.2756153105425074; … ; -7.629301370339078e-17 3.3079114109316946e-17 2.4311650497690955e-17 -1.4487394122956738; 5.77118033070349e-17 1.2796361519230945e-16 1.6239607132615985e-17 1.1609326863437107e-16])
What’s the computational cost? Remember, Gram–Schmidt was $O(mn^2)$. $O(m^2 n^2)$. BECAUSE, we formed the dense $Q_j$. PS will look at reducing this to $O(mn^2)$.
Matrix(1.0I, m, m)
5×5 Matrix{Float64}:
1.0 0.0 0.0 0.0 0.0
0.0 1.0 0.0 0.0 0.0
0.0 0.0 1.0 0.0 0.0
0.0 0.0 0.0 1.0 0.0
0.0 0.0 0.0 0.0 1.0
3×3 Matrix{Float64}:
1.0 2.77556e-16 2.22045e-16
2.77556e-16 1.0 8.32667e-17
2.22045e-16 8.32667e-17 1.0
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com