Gram–Schmidt 직교화

원래 문제: 함수를 유용한 방향으로 전개하기

Schmidt의 1907년 논문은 미리 정한 다른 함수족으로 함수를 표현하는 문제를 묻는다. 거듭제곱, 삼각함수 등은 구성요소가 되지만 기여가 겹칠 수 있다. §3에서는 구간의 선형독립 연속 실함수들을 정규화된 상호 직교 함수들로 바꾼다. 각주는 본질적으로 같은 공식을 Gram에게 돌린다. 원문 437쪽의 문제, 442–443쪽의 구성을 참고하자. 원래부터 행렬 인수분해로 제시된 알고리즘이 아니라 함수 근사 문제이다.

선형결합은 각 구성요소에 수를 곱해 더한다. 생성공간(span)은 그런 모든 결합의 집합이다. 어느 원소도 다른 것들로 만들 수 없으면 선형독립이다. 직교 대체는 표현 가능한 근사를 유지하면서 계수를 쉽게 구하게 해야 한다.

원래 기호 구성을 현대 표기로 쓰기

Schmidt의 기호 문제를 현대적으로 다시 유도하기. $a<b$인 $[a,b]$ 위에서 $f_1,\ldots,f_n$을 독립인 연속 실함수라 하자. 겹침을 측정하는 내적과 관련 길이를 다음으로 정의한다.

내적이 0이면 직교, 서로 직교하고 각각 길이가 1이면 정규직교이다. 연속성과 독립성은 아래 0이 아닌 나머지 함수의 제곱 적분이 양수임을 보장한다. 이는 Schmidt, §3, 442–443쪽의 설정이며 원문의 $\varphi_j,\psi_j$ 대신 $f_j,q_j$를 쓴다.

$q_1=f_1/\lVert f_1\rVert$로 시작한다. $f_2$에서 $q_1$ 방향 부분을 제거하려면

왜 이 계수인가? $q_1$과 내적하면

이제 $q_2=u_2/\lVert u_2\rVert$로 정규화한다. 뒤의 각 함수에서도 앞의 모든 정규직교 성분을 제거한다.

이것이 정규화를 포함한 Gram–Schmidt 직교화이다. 직교화만 하면 수직인 $u_j$를 얻고 정규화는 길이까지 1로 만든다.

근사에 도움이 되는 이유

정규직교족 $q_1,\ldots,q_n$으로 목표 $g$를 $\sum_i c_iq_i$로 근사하자. 제곱오차를 전개하고 $i\ne j$에서 $\langle q_i,q_j\rangle=0$을 쓰면

각 계수를 독립적으로 $c_i=\langle q_i,g\rangle$로 고를 수 있다. 원래 구성요소의 겹침이 계수 계산에서 사라졌다. 이 유한차원 유도는 원래 전개 문제에서 직교성의 역할을 설명하며 무한 전개의 수렴을 증명하지는 않는다. Schmidt는 그 추가 문제를 따로 다룬다.

구체적인 함수 계산

Schmidt의 수치 자료가 아닌 보충용 특수화. $[a,b]=[0,1]$, $f_1(t)=1$, $f_2(t)=t$로 고르면

따라서 $u_2(t)=t-\frac12$이며 길이의 제곱은

$q_2$의 적분은 0, 제곱의 적분은 1이다. 평균을 빼 상수 성분을 제거했다. 두 새 함수는 여전히 모든 직선 $\alpha+\beta t=(\alpha+\beta/2)q_1+(\beta/\sqrt{12})q_2$를 표현한다.

원래 §3은 이 계산의 관측표가 아닌 일반 함수와 공식을 제공한다. 선택한 구간과 함수는 교육용 특수화이며 복원한 역사적 측정이 아니다.

함수에서 좌표벡터로

$\mathbb R^m$의 벡터에서는 적분을 내적으로 바꾼다.

위첨자 $T$는 열을 행으로 전치한다. 예를 들어 $(1,2)^T$의 길이 제곱은 5이다. 길이는 벡터 노름, 행렬 표기는 행렬 분해 개요를 참고하자. 벡터 구성과 단계별 생성공간 성질은 ALAFF, §3.2.1에서 전개한다.

투영은 이미 설명된 부분이다

단위벡터 $q$에 대해 $(q^Ta)q$는 $a$를 그 직선에 내린 직교투영, 즉 직선 위의 가장 가까운 벡터이다. 실제로

이므로 최선의 계수는 $c=q^Ta$이다. 정규화되지 않은 $v\ne0$의 계수는 $(v^Ta)/(v^Tv)$이다. 분모를 빠뜨리는 것은 흔한 실수이다.

벡터 계산: 새 부분을 남긴 뒤 정규화하기

QR 문서와 공유하는 보충용 예제. 다음을 보자.

첫 열의 길이가 $\sqrt3$이므로

둘째 열의 이 방향 계수는

투영을 빼고 나머지 길이를 구하면

따라서 $q_2=(-1,0,1)^T/\sqrt2$이다. 직접 확인하면

입력을 복원하는 방법도 기록했다.

이 계수들이 QR 분해의 삼각 인수가 된다.

알고리즘이 작동하는 이유와 멈추는 경우

독립인 $a_1,\ldots,a_n\in\mathbb R^m$에 대해 고전적 Gram–Schmidt는 다음을 계산한다.

앞의 임의의 $q_k$에 대해 정규직교성으로 한 항 외에는 모두 사라진다.

또한 새 $q_j$는 $a_j$와 앞의 방향들로 만들고 복원식은 새 방향들로 $a_j$를 표현한다. 따라서 매 $j$에서

최종 생성공간만 유지하는 것보다 강한 성질이며 출력의 순서 의존성을 설명한다. ALAFF의 단계별 생성공간 유도.

나머지가 0이면 새 방향이 없다

$a_2=2a_1$이면 첫 투영을 뺀 나머지는 0이고 단위벡터 $0/\lVert0\rVert$는 없다. 정확 산술에서는 종속성을 검출하며 첫 벡터가 0이면 즉시 실패한다. 종속 입력을 건너뛰면 생성공간의 기저를 얻지만 벡터 수가 줄어든다. 영나머지가 행렬에 QR 분해가 없다는 뜻은 아니다. 추가 방향으로 정규직교족을 완성할 수 있다. QR 문서에서 구별한다.

입력 정규화만으로는 부족하다

$(1,0)^T$, $(1,1)^T/\sqrt2$는 모두 길이가 1이지만 내적은 $1/\sqrt2$이다. 길이 정규화는 겹침을 제거하지 않는다. 반대로 수직인 벡터도 단위 길이일 필요는 없다.

순서를 바꾸면 방향도 바뀐다

계산 예제에서 $a_2$부터 처리하면 첫 방향은 $(1,1,1)^T/\sqrt3$이 아닌 $q_1=(0,1,2)^T/\sqrt5$이다. 두 순서는 같은 최종 평면을 표현하지만 첫 직선은 다르다. 순서 관례 없이 유일하게 선호할 축을 찾는 방법은 아니다.

유한 정밀도에서 고전적·수정 Gram–Schmidt

정확 공식은 내적과 뺄셈이 정확하다고 가정하지만 컴퓨터는 반올림한다. 열이 앞의 열들로 거의 설명되면 나머지는 그것을 만드는 뺄셈의 수들보다 훨씬 작을 수 있다. 이 상쇄는 반올림 오차의 상대적 중요성을 키운다.

고전적 Gram–Schmidt(CGS)는 원래 열 $a_j$에서 모든 계수를 측정한다. 수정 Gram–Schmidt(MGS)는 점차 갱신되는 나머지에서 측정한다.

for j = 1, ..., n:
    v = a_j
    for i = 1, ..., j-1:
        r_ij = dot(q_i, v)
        v = v - r_ij * q_i
    r_jj = norm(v)
    if r_jj == 0: 종속임을 알리고 중단한다
    q_j = v / r_jj

CGS에서는 dot(q_i, v)를 dot(q_i, a_j)로 바꾼다. 앞의 뺄셈이 $q_i$에 수직이라 정확 산술에서는 같지만 반올림 후에는 크게 다를 수 있다. Persson의 MIT 자료 3–5번 슬라이드.

출판된 예제: 작아 보이는 차이가 중요하다

출판된 설명용 행렬족의 현대적 재계산. Persson의 6–7번 슬라이드는 다음을 쓴다.

$\varepsilon$은 작은 양수이고 $1+\varepsilon^2\approx1$로 단순화한다. 이 명시된 반올림 모델에서 두 방법은 $q_2\approx(0,-1,1,0)^T/\sqrt2$를 얻는다. CGS는 이어 $q_3\approx(0,-1,0,1)^T/\sqrt2$를 주어 $q_2$와 내적이 $1/2$이다. MGS는 갱신된 나머지로 $q_3\approx(0,-1,-1,2)^T/\sqrt6$를 얻어 내적이 0이다. 출처의 단순 반올림 모델에 따른 결과이며 정확 산술 결과나 모든 기계·$\varepsilon$에 대한 예측이 아니다. 원래 슬라이드 6–7.

MGS는 대체로 단일 CGS 순회보다 신뢰할 만하지만 거의 종속인 입력에서는 직교성을 잃을 수 있다. 재직교화는 기존 기저에 대한 투영 제거를 반복한다. 조밀 QR에는 Householder 반사도 있다. MIT 수치해석 설명이 이런 대안을 소개한다. 작은 나머지에는 척도를 반영한 정책이 필요하며 고정 절대 상수 검사는 보편적인 계수 판정법이 아니다.

Gram–Schmidt는 앞 방향으로의 투영을 빼 기저를 만든다. Householder QR은 길이를 보존하는 반사로 좌표를 바꾸며 각 단계에서 열 꼬리를 통째로 0으로 만든다. 둘 다 QR을 주지만 중간 연산은 다르다. 반사 유도는 거울 선택을, QR 비교는 방법들의 차이를 보인다. LAPACK의 Householder 구성도 참고하자.

대화형 예제: 방향이 사라지는 모습 보기

실습은 원래 기호 직교화 문제를 현대적인 유한 벡터로 재구성한 것이다. 무차원 기준 $a_1=(1,1,1)^T$, $a_2=(0,1,2)^T$는 만든 값이며 원래 관측이라고 주장하지 않는다. $a_2$의 세 원소를 바꾸면 평균이 상수 투영의 계수가 되는 것을 볼 수 있다. 가로축은 표본 위치, 세로축은 성분값이며 3차원 벡터 자체의 그림이 아니다. 위 벡터 계산으로 JavaScript 없이 기준을 볼 수 있다.

세 원소를 모두 같게 한 뒤 거의 같게 해 보자. 첫 경우 정확히 종속이고 둘째는 작은 독립 성분을 주어 정규화 방향이 변경에 민감할 수 있다. 교육용 기준을 복원하면 계산 예제로 돌아간다.

연습문제

문제와 수치는 직접 만든 교육용 예제이다.

1. 손계산: 두 방향

$a_1=(1,1,0)^T$, $a_2=(1,0,1)^T$에 Gram–Schmidt를 적용하여 투영, 나머지와 정규화 벡터를 구하라.

2. 손계산: 함수도 벡터이다

$[-1,1]$의 $1,t,t^2$에 적분 내적을 써 셋째 정규화 전 직교함수를 구하라.

3. 해석: 사라진 열

독립인 $a_1,a_2$ 다음에 $a_3=3a_1-a_2$를 넣었다. 셋째 나머지가 0이면 앞 두 방향이 틀렸다는 뜻인가?

4. 논리: 새 방향이 살아남는 이유

처음 $j$개 입력이 독립이면 $u_j\ne0$임을 증명하라. 왜 정확 산술이 필요한가?

5. 실용적 응용: 신호에서 오프셋 제거하기

무차원 신호 $s=(2,5,8)^T$에서 $(1,1,1)^T$ 방향 성분을 제거하고 나머지를 정규화하라. 정규화는 어떤 정보를 버리는가?

더 공부할 자료

• Schmidt 원문 §3, 442–443쪽: 현대 벡터 점화식과 원래 적분식·종속성 논증을 비교한다.
• ALAFF: Classical Gram–Schmidt: 단계별 생성공간 불변성을 행렬 표현으로 연결한다.
• Persson의 MIT 자료: 두 알고리즘을 비교하고 반올림 예제를 계산한다.

관련 문서

• Householder 반사

• QR 분해
• 벡터 노름
• 행렬 인수분해와 분해
• Cholesky 분해

참고문헌

1. Schmidt, E. (1907). Zur Theorie der linearen und nichtlinearen Integralgleichungen. I. Teil: Entwicklung willkürlicher Funktionen nach Systemen vorgeschriebener. Mathematische Annalen, 63, 433–476. 원문 스캔. 437쪽과 442–443쪽이 본문의 문제와 구성이다. 내려받는 PDF에는 도서관 표지가 있어 인쇄 442쪽은 PDF 11쪽이다.
2. van de Geijn, R. A., Myers, M. Advanced Linear Algebra: Foundations to Frontiers, §3.2.1, Classical Gram–Schmidt.
3. Persson, P.-O. (2006). Gram–Schmidt Orthogonalization, MIT 18.335J/6.337J, 2006년 9월 21일 강의자료, 2019년 봄 강의에서 배포. 3–7번 슬라이드가 CGS와 MGS를 비교한다.
4. Johnson, S. G. (2019). MIT OpenCourseWare, Introduction to Numerical Methods, 4주차. 수치 직교성과 대안 구성.
5. Anderson, E., 외 (1999). LAPACK Users’ Guide. QR Factorization: Householder and blocked constructions.