Gram-Schmidt¶
Copyright By PowCoder代写 加微信 powcoder
using LinearAlgebra
A = [1 1 1;
m,n = size(A)
Q = zeros(m,n) # reduced QR, so Q̂
R = UpperTriangular(zeros(n,n))
v₁ = A[:,1]
R[1,1] = norm(v₁)
q₁ = Q[:,1] = v₁/R[1,1]
a₂ = A[:,2]
R[1,2] = q₁’*a₂
v₂ = a₂ – R[1,2] * q₁
R[2,2] = norm(v₂)
q₂ = Q[:,2] = v₂/R[2,2]
a₃ = A[:,3]
R[1,3] = q₁’*a₃
R[2,3] = q₂’*a₃
v₃ = a₃ – R[1,3] * q₁ – R[2,3] * q₂
R[3,3] = norm(v₃)
Q[:,3] = v₃/R[3,3]
4-element Vector{Float64}:
0.1995930819792704
0.11405318970244017
0.5132393536609808
-0.8268856253426914
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
Note $O(mn^2)$
# returns the reduced QR
function gramschmidt(A)
m,n = size(A)
Q = zeros(m,n) # reduced QR, so Q̂
R = UpperTriangular(zeros(n,n))
for j = 1:n
aⱼ = A[:,j]
for k = 1:j-1
R[k,j] = Q[:,k]’aⱼ
vⱼ = aⱼ – Q[:,1:j-1] * R[1:j-1,j]
R[j,j] = norm(vⱼ)
Q[:,j] = vⱼ/R[j,j]
gramschmidt (generic function with 1 method)
Q, R = gramschmidt(A)
3×3 Matrix{Float64}:
1.0 1.38778e-17 -5.55112e-17
1.38778e-17 1.0 -7.31824e-17
-5.55112e-17 -7.31824e-17 1.0
Instability as dimension becomes large¶
A = randn(300,300);
Q,R = gramschmidt(A)
norm(Q*R – A)
1.115988908646552e-13
norm(Q’Q – I) # Numerically is unstable: loss of orthogonality
1.8601923656787078e-12
What about qr?
Q,R = qr(A)
norm(Q*R – A)
2.5714988731054025e-13
Q = Matrix(Q)
norm(Q’Q – I) # orthogonality is maintained (as much as possible)
1.885974411483999e-14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com