새 움직임 안에 이미 사용한 방향이 섞여 있다면 그 부분을 먼저 빼 본다. 남은 움직임은 앞의 방향과 겹치지 않게 만들 수 있다. 이 남은 방향의 길이를 1로 맞추어 다음 기준으로 쓴다.
앞 방향의 성분을 빼는 단계가 직교화, 남은 벡터를 자기 길이로 나누는 단계가 정규화이다. 한 직선 위로의 정사영과 정규직교기저의 내적 좌표 공식을 차례로 되풀이하는 계산이다.
그람–슈미트는 순서 있는 독립 벡터에서 시작한다
그람–슈미트 직교화는 Rn의 일차독립인 벡터 목록을 같은 생성공간의 직교 벡터 목록으로 바꾸는 과정이다. 각 결과를 정규화하면 정규직교기저가 된다. '그람-슈미트 과정', '그람-슈미트 직교정규화'라고도 부르며, 영어 이름은 Gram–Schmidt process이다. 표준 내적을 쓰며 입력 벡터의 순서를 고정한다.
정의
기호
이름
원어
뜻
a1,…,am
입력 벡터
input vectors
순서를 정한 일차독립 벡터들
wk
직교화한 잔차
orthogonal residual
앞 방향의 성분을 빼고 남긴 벡터
uk
정규화한 벡터
normalized vector
wk를 길이 1로 만든 벡터
projwa
정사영
projection
a를 w 방향 직선 위로 내린 벡터 w⋅wa⋅ww
x⋅y
내적
dot product
대응 성분의 곱을 더한 값
∥wk∥
잔차의 길이
residual norm
정규화할 때 나누는 양수
첫 잔차는 입력 그대로이다. 그다음부터는 앞에서 만든 잔차 방향의 정사영을 모두 뺀다. 빼는 방향이 원래 입력 aj가 아니라 이미 서로 직교하는 잔차 wj라는 점이 핵심이다.
각 wj는 아직 길이가 1이 아닐 수 있으므로 길이의 제곱으로 나눈다. 마지막에 각 잔차를 자기 길이로 나누어 정규화한다.
uk=∥wk∥wk(k=1,…,m).(2)
정규화를 매 단계 먼저 해 두어도 결과는 같다. uj=wj/∥wj∥를 넣으면 projwjak=(ak⋅uj)uj이기 때문이다. 그래서 식 (1)을 다음처럼 쓰는 교재도 많다.
wk=ak−j=1∑k−1(ak⋅uj)uj.(3)
식 (3)의 합은 정규직교기저의 내적 공식으로 구한, 앞 k−1개 방향이 생성하는 공간 위로의 정사영이다. 입력이 독립이면 분모가 0이 되지 않는다는 것은 아래에서 증명한다.
평면의 두 벡터로 빼기와 나누기를 본다
a1=(2,1), a2=(3,4)를 이 순서로 직교화한다. 둘째 입력과 첫 잔차의 내적은 6+4=10, 첫 잔차의 길이의 제곱은 4+1=5이다. 따라서 빼는 계수는 2이다.
w2=(3,4)−510(2,1)=(3,4)−(4,2)=(−1,2).(4)
검산하면 (2,1)⋅(−1,2)=−2+2=0이다. 그림 1에서 a2의 끝에서 a1 방향 직선에 내린 수선의 발이 (4,2)이다. 빼는 것은 a1 자신이 아니라 그 방향의 성분 2a1이다.
그림 1 둘째 입력 a2=(3,4)에서 첫 방향의 성분 2a1=(4,2)를 빼면 잔차 w2=(−1,2)가 남는다. 점선은 같은 잔차를 사영의 끝에서 그린 것이고, 두 직각 표시는 잔차가 첫 방향과 수직임을 나타낸다. figures/subtract_projection.py
두 잔차의 길이는 모두 5이다. 식 (2)로 나누면 평면의 정규직교기저를 얻는다.
u1=51(2,1),u2=51(−1,2).(5)
입력 순서를 바꾸면 결과 기저가 달라질 수 있다
그람–슈미트는 첫 입력의 방향을 그대로 채택하므로 입력 순서가 결과를 정한다. 같은 두 벡터를 (3,4),(2,1) 순서로 넣으면 첫 벡터는 q1=(3,4)/5이다. 둘째는 (2,1)−2510(3,4)=(54,−53)이고, 길이가 이미 1이라 q2=(4,−3)/5이다.
두 결과는 모두 R2의 정규직교기저이지만 서로 다르다. 그림 2에서 첫 벡터 u1과 q1은 각 입력의 방향을 그대로 따르고, 둘째 벡터만 첫 벡터와 직각이 되도록 돌아가 있다.
그림 2 같은 입력 (2,1),(3,4)를 두 순서로 직교화·정규화한 결과이다. u1,u2는 (2,1)을 먼저, q1,q2는 (3,4)를 먼저 넣은 것이다. 두 입력을 길이로 나누기만 한 u1과 q1 사이의 각은 26.6∘이다. figures/unit_circle_orders.py
결과 기저가 달라도 생성하는 공간은 같다. 같은 공간의 정규직교기저는 하나가 아니며, 그람–슈미트는 순서에 따라 그중 하나를 고른다. 입력이 처음부터 서로 직교하면 순서를 바꾸어도 같은 방향의 벡터들이 순서만 바뀌어 나온다.
Q. 각 입력 벡터를 길이로 나누기만 해도 그람–슈미트 결과가 되나?
아니다. 길이로 나누는 정규화는 두 벡터 사이의 각을 바꾸지 않으므로, 직교하지 않는 입력은 나눈 뒤에도 직교하지 않는다. (2,1)과 (3,4)를 각각 길이로 나눈 두 단위벡터 사이의 각은 그대로 26.6∘이다(그림 2). 앞 방향의 성분을 빼는 단계가 있어야 직각이 생긴다.
공간의 세 벡터를 끝까지 직교화한다
입력은 a1=(1,1,0), a2=(1,0,1), a3=(0,1,1)이다. ra1+sa2+ta3=0의 성분식은 r+s=0, r+t=0, s+t=0이다. 앞의 두 식에서 s=t=−r이고 마지막 식에서 −2r=0이므로 독립이다.
첫 잔차는 w1=(1,1,0)이고 자기 내적은 2이다. 둘째 입력과의 내적은 1이므로 빼는 계수는 1/2이다.
그림 3은 이 단계를 보여 준다. 빼는 두 성분의 합 p3=21w1+31w2=(32,31,31)은 a1,a2가 생성하는 평면 위의 정사영이다. 남은 w3은 그 평면에 수직이다.
그림 3 셋째 단계에서 a3=(0,1,1)을 평면 span(a1,a2) 위의 성분 p3=21w1+31w2=(32,31,31)과 평면에 수직인 잔차 w3으로 나눈다. 입체를 평면에 그린 그림이므로 화면의 각을 실제 각으로 읽지 않는다. figures/third_step_plane.py
손으로 계산할 때는 분수를 줄여도 된다. 잔차에 0 아닌 수를 곱해도 방향과 직교성은 그대로이고, 식 (1)의 정사영도 바뀌지 않는다. 예를 들어 w2 대신 2w2=(1,−1,2)를 쓰면 계수는 (0−1+2)/6=1/6이고, 61(1,−1,2)는 31w2와 같은 벡터이다.
w2=(1,−1,2)/2의 길이는 6/2이므로 나누면 식 (8)의 둘째 벡터가 된다. 셋째도 w3=2(−1,1,1)/3을 길이 23/3으로 나눈 결과이다.
그람–슈미트의 결과는 왜 직교하고 같은 공간을 생성할까?
앞의 잔차들이 서로 직교한다고 하자. 식 (1)에 wi를 내적하면 합에서 j=i인 항만 살아남는다. 따라서 다음처럼 같은 값이 빠진다.
wk⋅wi=ak⋅wi−∥wi∥2ak⋅wi∥wi∥2=0(i<k).(9)
새 잔차는 입력 벡터와 앞 잔차들의 조합이다. 거꾸로 식 (1)을 옮기면 ak=wk+∑j<kprojwjak이므로 입력 벡터도 잔차들의 조합이다. 매 단계 양쪽 표현을 복원할 수 있으므로, 앞 k개의 입력과 앞 k개의 잔차는 같은 공간을 생성한다.
정규화한 뒤에는 이 복원의 계수가 식 (3)의 내적이다. ak는 u1,…,uk만으로 쓰이고, 마지막 계수 ak⋅uk는 잔차의 길이 ∥wk∥와 같다.
ak=j=1∑k(ak⋅uj)uj,ak⋅uk=∥wk∥.(10)
공간의 예에서는 a1=2u1, a2=21u1+26u2, a3=21u1+61u2+32u3이다. 대각 자리의 2, 6/2, 2/3이 식 (6)·(7)의 잔차 길이와 같다.
Q. 그람–슈미트 직교화와 QR 분해는 어떤 관계인가?
QR 분해는 그람–슈미트의 결과를 행렬로 적은 것이다. 입력 ak를 열로 모은 행렬은, uk를 열로 모은 Q와 식 (10)의 계수 ak⋅uj를 모은 위삼각행렬 R의 곱 QR이다. 공간의 예에서 R의 대각성분은 2,6/2,2/3이다. QR 분해 자체는 고급 대수 성취기준 밖의 확장 주제이다.
잔차가 0이 되면 입력이 종속이다
독립인 입력에서는 잔차가 영벡터가 될 수 없다. 만약 wk=0이라면 식 (1)에서 ak가 앞 잔차들, 따라서 앞 입력 벡터들의 조합이 되어 입력의 일차독립에 모순이다. 그러므로 모든 잔차의 길이가 양수이고 식 (2)로 정규화할 수 있다.
반대로 종속 입력에서는 앞 벡터들의 조합인 입력을 만났을 때 잔차가 0이다. 평면에서 (1,2),(2,4)를 넣으면 둘째 잔차가 (2,4)−2(1,2)=0이다. 공간에서 셋째 입력을 (2,1,1)=a1+a2로 바꾸면 계수가 3/2와 1이 되어 (2,1,1)−23(1,1,0)−(21,−21,1)=0이다.
그림 4는 한 바퀴의 계산을 정리한 것이다. 잔차가 0이면 영벡터로는 나눌 수 없으므로 정규화하지 않는다. 그 입력은 새 방향을 보태지 않으니, 같은 생성공간의 기저만 필요하다면 버리고 다음 입력으로 넘어간다. 그래서 그람–슈미트는 일차독립인지 판정하는 데도 쓸 수 있다.
그림 4 그람–슈미트의 한 바퀴이다. 앞 잔차 방향의 정사영을 모두 뺀 잔차가 영벡터가 아니면 정규화하고, 영벡터이면 그 입력이 앞 입력들의 일차결합이라는 뜻이므로 정규화하지 않는다. k가 m에 이를 때까지 되풀이한다. figures/gram_schmidt_flow.py
Q. 그람–슈미트에서 잔차가 0이면 아주 작은 수로 바꾸어 나누어도 되나?
아니다. 정확한 계산에서 잔차 0은 그 입력이 앞 벡터들의 조합이라 새 방향을 보태지 않는다는 뜻이다. 영벡터를 어떤 양수로 나누어도 영벡터일 뿐 단위벡터가 되지 않는다. (1,2),(2,4)처럼 둘째 잔차가 0이면 그 입력을 빼고 생성공간의 기저를 만든다.
그람–슈미트로 구한 기저는 어디에 쓰나?
부분공간의 정규직교기저를 얻으면 그 공간 위로의 정사영을 내적만으로 구한다. a1,a2가 생성하는 평면 위로 x=(1,2,3)을 정사영해 보자. 직교 잔차 w1,w2와의 내적은 3과 1/2−1+3=5/2이다.
남은 부분 x−p=(−34,34,34)은 34(−1,1,1)로, 식 (8)의 u3 방향이다. 원래 입력 a1,a2는 직교하지 않아 이 계산을 바로 할 수 없었다. 대칭행렬의 같은 고윳값에 속한 고유벡터들을 정규직교로 바꿀 때도 이 과정을 쓴다(직교대각화).
핵심
그람–슈미트 직교화는 순서 있는 독립 벡터에서 앞 잔차 방향의 정사영을 모두 빼고 정규화해, 같은 생성공간의 정규직교기저를 만든다. 잔차 0은 입력이 종속이라는 신호이다.
그람–슈미트의 흔한 오해
정규화하지 않은 잔차에도 내적만 계수로 쓴다. — 식 (4)에서 내적은 10이지만 첫 잔차의 길이의 제곱이 5이므로 계수는 2이다. 내적 10을 그대로 쓰면 (3,4)−10(2,1)=(−17,−6)이 되어 (2,1)과의 내적이 −40이다.
원래 입력 벡터 방향으로 사영해 빼도 된다. — 셋째 입력에서 a1,a2 방향의 정사영을 빼면 (0,1,1)−21(1,1,0)−21(1,0,1)=(−1,21,21)이고, a1과의 내적이 −1/2이다. a1,a2가 서로 직교하지 않아 같은 성분을 두 번 빼기 때문이다.
직접 해보기
a1=(1,2), a2=(3,1)을 순서대로 직교화하고 정규화하라.
(2,0,0),(1,3,0),(1,1,4)의 직교 잔차 세 개와 정규직교기저를 구하라.
(2,−1),(6,−3)에서 둘째 잔차를 구하고 정규화 가능 여부를 설명하라.
식 (7)에서 첫째 방향 제거를 빠뜨리고 w3=a3−31w2만 계산하면 w1과 직교하는가?
R4의 (1,1,1,1),(1,1,0,0)을 순서대로 직교화하고 정규화하라.
답
첫 길이제곱은 5이고 두 입력의 내적도 5이므로 w2=(3,1)−(1,2)=(2,−1)이다. 두 잔차의 길이는 모두 5이다. 답은 (1,2)/5,(2,−1)/5이고 내적은 (2−2)/5=0이다.
w1=(2,0,0), w2=(1,3,0)−21(2,0,0)=(0,3,0)이다. 셋째는 (1,1,4)−21(2,0,0)−31(0,3,0)=(0,0,4)이다. 길이 2, 3, 4로 나누면 표준기저가 된다.
계수는 ((6,−3)⋅(2,−1))/5=15/5=3이다. 잔차가 (6,−3)−3(2,−1)=0이므로 정규화할 수 없다. 둘째 입력이 첫째의 3배라 새 방향이 없다.
w3=(−1/6,7/6,2/3)이다. 첫 잔차와의 내적은 −1/6+7/6=1이므로 직교하지 않는다. 첫 방향의 성분도 제거해야 한다.
내적은 2, 첫 길이제곱은 4이므로 계수는 1/2이다. w2=(1,1,0,0)−21(1,1,1,1)=(21,21,−21,−21)이고 길이는 1이다. 답은 21(1,1,1,1)과 21(1,1,−1,−1)이다.
더 읽기
UC Davis, Linear Algebra — The Gram–Schmidt Orthogonalization Procedure 절의 구성 증명. 독립 입력의 분모 비영과 생성공간 보존을 확인했다.