代写代考

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