Gram–Schmidt(그람-슈미트) 직교화

Gram-Schmidt(그람-슈미트) 직교화..

오늘 최적화 관련 글을 읽다가 Gram-Schmidt에 대한 내용이 나왔다. 옛날 학생 때 배웠던 것 같긴 한데 기억이 가물가물하다.

주어진 벡터들로부터 수직인 벡터들을 새로 만들어내는 방법이란 정도는 알고 있지만 명확하지 않다. '떡 본 김에 제사 지낸다'고 Gram-Schmidt 직교화에 대해 간단히 정리해 본다.

그람-슈미트(Gram-Schmidt) 직교화란?

주어진 벡터들을 이용해서 서로 수직인 벡터들을 만드는 방법이다. 좀더 고상한 말로 표현하면 주어진 벡터들에 대한 직교기저(orthogonal basis) 또는 정규직교기저(orthonormal basis)를 구하는 과정이다.

• 그람-슈미트 직교화(Gram-Schmidt orthogonalization): 주어진 벡터 v1, v2, ... 로부터 이 벡터들을 생성할 수 있는 직교기저(orthogonal basis)를 구하는 과정
• 그람-슈미트 정규직교화(Gram-Schmidt orthonormalization): 주어진 벡터 v1, v2, ... 로부터 이 벡터들을 생성할 수 있는 정규직교기저(orthonormal basis)를 구하는 과정

☞ 기저, 직교기저, 정규직교기저 등의 용어는 [선형대수학 #3] 고유값과 고유벡터 글 참조

그람-슈미트(Gram-Schmidt) 직교화 수식

주어진 벡터 v1, v2, ..., vk 에 대해, 이 벡터들을 생성할 수 있는 직교 벡터 u1, u2, ... 들은 다음과 같이 얻어진다 (단, proj_u(v)는 벡터 v를 벡터 u에 수직으로 투영한 벡터).

 --- (1)

이렇게 얻어진 u1, u2, ..., uk는 서로 수직(orthogonal)이고 벡터공간 V = {v1, v2, ..., vk}에 대한 직교기저가 된다. 그리고 이러한 과정을 그람-슈미트 직교화(orthogonalization)라 부른다.

여기서 더 나아가 ui들을 단위벡터(길이가 1인 벡터)로 만들면 e1, e2, ..., ek는 벡터공간 V의 정규직교기저(orthonormal basis)가 된다. 그리고 이러한 과정을 그람-슈미트 정규직교화(orthonormalization)라 부른다.

 --- (2)

그람-슈미트(Gram-Schmidt) 직교화 원리

그람-슈미트 직교화 원리는 2단계로 설명할 수 있다. 먼저, 벡터 v를 이용해서 u1, u2, ..., ui 모두와 수직인 벡터를 만드는 방법은 v를 벡터공간 {u1, u2, ..., ui}에 투영시킨 후 v에서 빼는 것이다. 즉, v' = v - proj_{{u1, ..., ui}}(v)는 u1, u2, ..., ui 모두와 수직인 벡터가 된다.

그림 1. Gram-Schmidt 직교화 원리1

벡터공간 {u1, ..., ui}는 수학적으로는 u1, ..., ui의 일차결합으로 생성할 수 있는 모든 가능한 벡터들의 집합으로 정의된다. 또는 간단하게 이 벡터들을 모두 포함하는 부분공간(subspace) 또는 평면으로 생각하면 된다. v를 이 공간에 투영한 후 v에서 빼면 이 공간의 모든 벡터와 수직인 벡터가 얻어진다.

다음으로 벡터 v를 공간 {u1, ..., ui}에 투영시킨 벡터는 아래 그림과 같이 v를 u1, u2, ..., ui 각각에 투영시킨 벡터의 합으로 구해진다 (단, ui가 서로 수직인 경우).

그림 2. Gram-Schmidt 직교화 원리2

이제 원래의 식 (1)으로 돌아가 보자. 지금까지 내용을 잘 이해했다면 Gram-Schmidt 직교화 과정이 손쉽게 이해되리라 생각한다.

Gram-Schmidt 제대로 이해하기 (Q & A)

Q1. 직교화 도중에 {u1, u2, ..., ui}에 수직인 벡터를 새로 생성할 때 v를 사용하지 않고 아무 벡터나 잡아서 투영시켜도 되지 않을까? 왜 굳이 원래의 vi 들을 이용해야 하는지?

A. 안된다. v를 사용해야 한다. Gram-Schmidt 직교화가 무조건 수직인 벡터들만 만들어 내는 방법이라고 생각한다면 그건 오해이다.

입력 v1, v2, ..., vk에 대해 Gram-Schmidt를 적용하여 얻어진 u1, u2, ... 들은 v1, v2, ...., vk를 생성할 수 있는 직교기저(orthogonal basis)가 된다. 즉, u1, u2, .. 들은 벡터 v1, v2, ..., vk와 동일한 공간에 포함되면서 이 공간을 생성할 수 있는 벡터들이다. 그림 1을 보자. 왼쪽 예에서 3차원 공간을 가정하면 u와 수직인 벡터는 무한이 많이 존재한다. 그 중 v - proju(v)는 u와 v에 의해 결정되는 공간(평면)에 속한 벡터임을 확인할 수 있다. 즉, u, v에 대해 직교화로 얻은 벡터는 u, v에 의해 결정되는 부분공간(subspace)에 포함되면서 서로 수직인 벡터들이다.

Q2. 직교화는 입력 벡터의 수만 많으면 무한히 적용할 수 있는가? 즉, 무한히 많은 수의 서로 수직인 벡터들을 만들어 낼 수 있는가?

A. 그렇지 않다. 상식적으로 생각해도 n차원 공간에서 n개보다 많은 서로 수직인 벡터들이 존재할 순 없다.

입력 v1, v2, ... 벡터들이 모두 일차독립인 경우에만 Gram-Schmidt로 입력 벡터의 수와 동일한 개수의 수직 벡터들이 만들어 진다. 만일 직교화 과정 도중에 일차독립이 아닌 벡터가 입력으로 들어오면 여기서 생성된 u는 0벡터가 된다. 입력 v1, v2, ..., vk까지는 일차독립이라 하자. 그런데, 새로 들어온 벡터 v_k+1이 기존의 v1, ..., vk와 일차독립이 아니라고 하자. 즉, v_k+1이 v1, ..., vk로 이루어진 공간에 포함된 벡터라고 가정하자. 그러면 v_k+1에서 {v1, ..., vk}에 내린 투영벡터는 자기 자신이 된다. 따라서 u = v_k+1 - proj_{v1,...,vk}(v_k+1) = 0이 된다.

Gram-Schmidt 과정 도중에 영벡터가 나온다면 이를 무시하고 다음 입력 벡터로 넘어가거나 또는 차원의 개수만큼 수직 벡터가 얻어졌으면 직교화 과정을 종료한다.

by 다크 프로그래머