75강 문제 3에서 정규직교기저가 좋다고 했습니다. 좌표가 내적으로 나오고, 노름이 보존되며, 조건수가 1 1
72강 심화 5에서도 같은 결론이었습니다. 계산 편의, 수치 안정, 구조 노출 어느 기준으로 봐도 직교가 유리합니다.
그런데 정작 이런 질문에 답하지 않았습니다.
그런 기저를 어떻게 만듭니까.
주어진 것은 대개 아무렇게나 생긴 기저입니다. 데이터의 열, 방정식의 계수, 측정된 방향은 직교일 이유가 없습니다.
이 강의에서 직교화 절차 를 세웁니다. 그람슈미트 과정이며, 아이디어는 64강의 정사영 하나입니다. 새 벡터에서 이미 만든 방향의 성분을 빼면 남는 것이 수직입니다.
그리고 마지막에 경고 하나를 답니다. 가장 자연스러운 구현이 수치적으로 무너집니다. 순서를 조금 바꾸면 해결되며, 그 차이가 0.707 0 . 7 0 7 1 0 − 8 1 0 − 8
직교기저에서 좌표를 내적으로 구할 수 있습니다.
그람슈미트 과정을 실행할 수 있습니다.
부분공간으로의 정사영 행렬을 만들 수 있습니다.
직교여공간으로의 분해를 계산할 수 있습니다.
고전 그람슈미트가 왜 불안정한지 설명할 수 있습니다.
문제. q 1 = 1 3 ( 1 , 1 , 1 ) q 1 = 3 1 ( 1 , 1 , 1 ) q 2 = 1 2 ( 1 , − 1 , 0 ) q 2 = 2 1 ( 1 , − 1 , 0 ) q 3 = 1 6 ( 1 , 1 , − 2 ) q 3 = 6 1 ( 1 , 1 , − 2 ) v = ( 3 , 1 , − 2 ) v = ( 3 , 1 , − 2 )
생각의 실마리. 75강 문제 3에서 Q ⊤ Q = I Q ⊤ Q = I [ v ] Q = Q ⊤ v [ v ] Q = Q ⊤ v 연립방정식을 풀지 않고 내적만 하면 됩니다.
풀이. (1) 검산에서 Q ⊤ Q = I Q ⊤ Q = I
q 1 ⋅ q 2 = 1 6 ( 1 − 1 + 0 ) = 0 q 1 ⋅ q 2 = 6 1 ( 1 − 1 + 0 ) = 0
(2) 각각 내적합니다.
c 1 = q 1 ⋅ v = 1 3 ( 3 + 1 − 2 ) = 2 3 = 1.15470054 c 1 = q 1 ⋅ v = 3 1 ( 3 + 1 − 2 ) = 3 2 = 1 . 1 5 4 7 0 0 5 4
검산에서 ( 1.15470054 , 1.41421356 , 3.26598632 ) ( 1 . 1 5 4 7 0 0 5 4 , 1 . 4 1 4 2 1 3 5 6 , 3 . 2 6 5 9 8 6 3 2 ) ( 3 , 1 , − 2 ) ( 3 , 1 , − 2 )
(3) 둘 다 3.74165739 3 . 7 4 1 6 5 7 3 9
∥ v ∥ = ∥ [ v ] Q ∥ = 14 ∥ v ∥ = ∥ [ v ] Q ∥ = 1 4
이 문제에서 배우는 것: 직교기저의 이점.
정규직교기저. q i ⋅ q j = δ i j q i ⋅ q j = δ i j
v = ∑ i ( v ⋅ q i ) q i , ∥ v ∥ 2 = ∑ i ( v ⋅ q i ) 2 v = i ∑ ( v ⋅ q i ) q i , ∥ v ∥ 2 = i ∑ ( v ⋅ q i ) 2
64강 문제 1의 정사영 공식이 그대로 입니다. 길이가 1 1 ( v ⋅ q ) q ( v ⋅ q ) q
이점을 정리합니다.
항목
일반 기저
정규직교기저
좌표 구하기
B c = v B c = v n 3 / 3 n 3 / 3 내적 (n 2 n 2
역행렬
계산 필요
Q^{-1}=Q^
노름
그람 행렬 필요
그대로 보존
조건수
클 수 있습니다
1 1
셋째 줄이 75강 심화 3의 내용 입니다. 일반 기저에서는 좌표끼리 그냥 내적하면 틀리고 G = B ⊤ B G = B ⊤ B G = I G = I
59강의 푸리에가 이 구조였습니다. 삼각함수들이 직교하므로 계수가 내적으로 나왔고, 파스발 항등식이 셋째 줄입니다.
b n = ⟨ f , sin n t ⟩ ∥ sin n t ∥ 2 b n = ∥ sin n t ∥ 2 ⟨ f , sin n t ⟩
직교하지 않으면 이 공식이 성립하지 않습니다. 그래서 직교기저를 만드는 일이 중요합니다.
바로 확인 1.
확인 1-1. 정규직교기저에서 좌표를 구하는 식을 쓰세요.
답. c i = v ⋅ q i c i = v ⋅ q i
확인 1-2. 계산량이 얼마나 줄어듭니까?
답. n 3 / 3 n 3 / 3 n 2 n 2
확인 1-3. 직교행렬의 역행렬을 쓰세요.
답. 전치 Q ⊤ Q ⊤
문제. a 1 = ( 1 , 1 , 0 ) a 1 = ( 1 , 1 , 0 ) a 2 = ( 1 , 0 , 1 ) a 2 = ( 1 , 0 , 1 ) a 3 = ( 0 , 1 , 1 ) a 3 = ( 0 , 1 , 1 )
생각의 실마리. 64강 문제 1에서 벡터를 한 방향 성분과 수직 성분으로 갈랐습니다. 수직 성분만 남기면 그 방향과 직교합니다.
풀이. (1) ∥ a 1 ∥ = 2 ∥ a 1 ∥ = 2
q 1 = 1 2 ( 1 , 1 , 0 ) q 1 = 2 1 ( 1 , 1 , 0 )
(2) a 2 a 2 q 1 q 1
w 2 = a 2 − ( a 2 ⋅ q 1 ) q 1 = ( 1 , 0 , 1 ) − 1 2 ⋅ 1 2 ( 1 , 1 , 0 ) = ( 1 2 , − 1 2 , 1 ) w 2 = a 2 − ( a 2 ⋅ q 1 ) q 1 = ( 1 , 0 , 1 ) − 2 1 ⋅ 2 1 ( 1 , 1 , 0 ) = ( 2 1 , − 2 1 , 1 )
정규화하면 q 2 = 1 6 ( 1 , − 1 , 2 ) q 2 = 6 1 ( 1 , − 1 , 2 )
(3) 셋째는 두 방향을 모두 뺍니다.
w 3 = a 3 − ( a 3 ⋅ q 1 ) q 1 − ( a 3 ⋅ q 2 ) q 2 w 3 = a 3 − ( a 3 ⋅ q 1 ) q 1 − ( a 3 ⋅ q 2 ) q 2
검산에서 결과가
Q = ( 0.70710678 0.40824829 − 0.57735027 0.70710678 − 0.40824829 0.57735027 0 0.81649658 0.57735027 ) Q = ⎝ ⎛ 0 . 7 0 7 1 0 6 7 8 0 . 7 0 7 1 0 6 7 8 0 0 . 4 0 8 2 4 8 2 9 − 0 . 4 0 8 2 4 8 2 9 0 . 8 1 6 4 9 6 5 8 − 0 . 5 7 7 3 5 0 2 7 0 . 5 7 7 3 5 0 2 7 0 . 5 7 7 3 5 0 2 7 ⎠ ⎞
이고 Q ⊤ Q = I Q ⊤ Q = I
이 문제에서 배우는 것: 그람슈미트 과정.
그람슈미트 과정. 일차독립인 a 1 , … , a n a 1 , … , a n
w k = a k − ∑ j < k ( a k ⋅ q j ) q j , q k = w k ∥ w k ∥ w k = a k − j < k ∑ ( a k ⋅ q j ) q j , q k = ∥ w k ∥ w k
를 차례로 계산하면 정규직교기저가 나옵니다.
왜 작동하는지 를 확인합니다. w k w k q i q i i < k i < k
w k ⋅ q i = a k ⋅ q i − ∑ j < k ( a k ⋅ q j ) ( q j ⋅ q i ) = a k ⋅ q i − a k ⋅ q i = 0 w k ⋅ q i = a k ⋅ q i − j < k ∑ ( a k ⋅ q j ) ( q j ⋅ q i ) = a k ⋅ q i − a k ⋅ q i = 0
q j ⋅ q i = δ i j q j ⋅ q i = δ i j
w k ≠ 0 w k = 0 a a w k = 0 w k = 0 a k a k
중요한 성질이 하나 더 있습니다.
부분공간 보존. 각 k k
span { a 1 , … , a k } = span { q 1 , … , q k } s p a n { a 1 , … , a k } = s p a n { q 1 , … , q k }
검산에서 세 단계 모두 확인됩니다. 처음 k k
이 성질이 81강의 QR 분해에서 결정적입니다. a k a k q 1 , … , q k q 1 , … , q k 위삼각행렬 이 됩니다.
순서가 결과를 바꿉니다. a a Q Q
바로 확인 2.
확인 2-1. 그람슈미트의 한 단계를 식으로 쓰세요.
답. w k = a k − ∑ j < k ( a k ⋅ q j ) q j w k = a k − ∑ j < k ( a k ⋅ q j ) q j
확인 2-2. w k = 0 w k = 0
답. a k a k
확인 2-3. 보존되는 성질을 쓰세요.
답. 처음 k k
문제. W = span { ( 1 , 1 , 0 ) , ( 0 , 1 , 1 ) } W = s p a n { ( 1 , 1 , 0 ) , ( 0 , 1 , 1 ) } W W P P x = ( 2 , 0 , 3 ) x = ( 2 , 0 , 3 ) P P
생각의 실마리. 64강에서 한 방향 으로의 정사영을 했습니다. 부분공간으로 확장하려면 그 부분공간의 기저를 열로 담은 W W P = W ( W ⊤ W ) − 1 W ⊤ P = W ( W ⊤ W ) − 1 W ⊤
풀이. (1) 검산에서
P = 1 3 ( 2 1 − 1 1 2 1 − 1 1 2 ) P = 3 1 ⎝ ⎛ 2 1 − 1 1 2 1 − 1 1 2 ⎠ ⎞
(2) P x = ( 1 3 , 5 3 , 4 3 ) P x = ( 3 1 , 3 5 , 3 4 ) ( 5 3 , − 5 3 , 5 3 ) ( 3 5 , − 3 5 , 3 5 )
두 성분의 내적이 정확히 0 0
(3) 검산에서 P 2 = P P 2 = P P ⊤ = P P ⊤ = P 2 2 2 2
이 문제에서 배우는 것: 정사영 행렬.
정사영 행렬. 부분공간 W W
P = W ( W ⊤ W ) − 1 W ⊤ P = W ( W ⊤ W ) − 1 W ⊤
이며, W W 정규직교 이면 훨씬 간단합니다.
P = Q Q ⊤ P = Q Q ⊤
검산에서 그람슈미트로 얻은 Q Q Q Q ⊤ = P Q Q ⊤ = P
왜 간단해지는가. Q ⊤ Q = I Q ⊤ Q = I
P = Q ( Q ⊤ Q ) − 1 Q ⊤ = Q I − 1 Q ⊤ = Q Q ⊤ P = Q ( Q ⊤ Q ) − 1 Q ⊤ = Q I − 1 Q ⊤ = Q Q ⊤
직교화를 해 두면 정사영이 공짜 입니다. 이것이 그람슈미트를 하는 실용적 이유 중 하나입니다.
P P
성질
뜻
P 2 = P P 2 = P 이미 W W
P ⊤ = P P ⊤ = P 대칭입니다
rank P = dim W r a n k P = dim W 상이 W W
tr P = dim W t r P = dim W 대각합이 차원
고유값이 0 0 1 1
84강에서
넷째 줄이 유용합니다. 64강 심화 2에서 한 방향 정사영의 대각합이 1 1 대각합이 곧 차원 입니다. 검산에서 2 2
P 2 = P P 2 = P 멱등 이라 합니다. 66강 문제 5의 ( 1 0 0 0 ) ( 1 0 0 0 )
대칭성이 왜 중요한가. P 2 = P P 2 = P 비스듬한 사영 이 그렇습니다.
S = ( 1 1 0 0 ) ⟹ S 2 = S , S ⊤ ≠ S S = ( 1 0 1 0 ) ⟹ S 2 = S , S ⊤ = S
이것도 어떤 부분공간으로 보내지만 수직으로 내리지 않습니다. 그래서 최소 거리를 주지 않습니다. 직교 정사영이려면 대칭이어야 합니다.
바로 확인 3.
확인 3-1. 정사영 행렬의 일반 공식을 쓰세요.
답. P = W ( W ⊤ W ) − 1 W ⊤ P = W ( W ⊤ W ) − 1 W ⊤
확인 3-2. 정규직교기저이면 어떻게 됩니까?
답. P = Q Q ⊤ P = Q Q ⊤
확인 3-3. tr P t r P
답. 부분공간의 차원입니다.
문제. 문제 3의 W W x x W W x − P x x − P x
생각의 실마리. W W
풀이. (1) 두 생성벡터의 외적을 정규화합니다.
n = 1 3 ( 1 , − 1 , 1 ) = ( 0.57735027 , − 0.57735027 , 0.57735027 ) n = 3 1 ( 1 , − 1 , 1 ) = ( 0 . 5 7 7 3 5 0 2 7 , − 0 . 5 7 7 3 5 0 2 7 , 0 . 5 7 7 3 5 0 2 7 )
검산에서 W W 0 0
(2) ( I − P ) x = ( 5 3 , − 5 3 , 5 3 ) ( I − P ) x = ( 3 5 , − 3 5 , 3 5 ) ( n ⋅ x ) n ( n ⋅ x ) n n n
(3) 정리합니다.
이 문제에서 배우는 것: 직교여공간 분해.
분해. W ⊆ R n W ⊆ R n
R n = W ⊕ W ⊥ , x = P x + ( I − P ) x R n = W ⊕ W ⊥ , x = P x + ( I − P ) x
이고 두 성분이 직교하며 분해가 유일합니다.
I − P I − P W ⊥ W ⊥
( I − P ) 2 = I − 2 P + P 2 = I − 2 P + P = I − P ( I − P ) 2 = I − 2 P + P 2 = I − 2 P + P = I − P
멱등이고 대칭이므로 정사영 이며, 상이 W ⊥ W ⊥
74강 심화 1에서 직교여공간의 성질을 다뤘고, 73강 문제 5에서 직합 분해를 다뤘습니다. 이제 그 분해를 실제로 계산할 수 있게 되었습니다.
dim W + dim W ⊥ = n , tr P + tr ( I − P ) = n dim W + dim W ⊥ = n , t r P + t r ( I − P ) = n
검산의 예에서 2 + 1 = 3 2 + 1 = 3
74강의 네 부분공간이 여기서 계산 가능해집니다.
분해
정사영
R n = C ( A ⊤ ) ⊕ N ( A ) R n = C ( A ⊤ ) ⊕ N ( A ) 행공간으로의 P P I − P I − P
R m = C ( A ) ⊕ N ( A ⊤ ) R m = C ( A ) ⊕ N ( A ⊤ ) 열공간으로의 P P I − P I − P
둘째 줄이 82강의 최소제곱 입니다. b b
피타고라스 정리도 성립합니다.
∥ x ∥ 2 = ∥ P x ∥ 2 + ∥ ( I − P ) x ∥ 2 ∥ x ∥ 2 = ∥ P x ∥ 2 + ∥ ( I − P ) x ∥ 2
63강에서 세운 것이 부분공간 수준에서 그대로 쓰입니다.
바로 확인 4.
확인 4-1. I − P I − P
답. W ⊥ W ⊥
확인 4-2. I − P I − P
답. ( I − P ) 2 = I − 2 P + P 2 = I − P ( I − P ) 2 = I − 2 P + P 2 = I − P
확인 4-3. 두 대각합의 합이 얼마입니까?
답. n n
문제. ε = 1 0 − 8 ε = 1 0 − 8
X = ( 1 1 1 ε 0 0 0 ε 0 0 0 ε ) X = ⎝ ⎜ ⎜ ⎜ ⎛ 1 ε 0 0 1 0 ε 0 1 0 0 ε ⎠ ⎟ ⎟ ⎟ ⎞
을 직교화합니다.Q ⊤ Q − I Q ⊤ Q − I
생각의 실마리. 세 열이 거의 평행합니다. 첫 성분이 모두 1 1 1 0 − 8 1 0 − 8 뺀 뒤에 남는 것이 아주 작습니다. 45강의 파국적 상쇄가 일어나는 조건입니다.
풀이. (1) 검산에서 오차가 7.071 × 1 0 − 1 7 . 0 7 1 × 1 0 − 1 0.7 0 . 7
(2) 순서를 바꾼 판(수정 그람슈미트)에서는 1.155 × 1 0 − 8 1 . 1 5 5 × 1 0 − 8
(3) 차이가 어디서 오는지 봅니다.
고전판 은 원래 벡터 a k a k
w k = a k − ∑ j < k ( a k ⋅ q j ) q j w k = a k − j < k ∑ ( a k ⋅ q j ) q j
수정판 은 빼 나가면서 갱신된 벡터와 내적합니다.
w ← a k , w ← w − ( w ⋅ q j ) q j ( j = 1 , … , k − 1 ) w ← a k , w ← w − ( w ⋅ q j ) q j ( j = 1 , … , k − 1 )
정확한 산술에서는 같습니다. w w 0 0
부동소수점에서는 다릅니다. 반올림 때문에 w w q j q j
이 문제에서 배우는 것: 수정 그람슈미트.
경고. 고전 그람슈미트는 수치적으로 불안정 합니다. 열들이 거의 종속이면 직교성이 크게 무너집니다.
검산 결과를 정리합니다.
방법
∥ Q ⊤ Q − I ∥ ∥ Q ⊤ Q − I ∥
고전 그람슈미트
7.071\times10^
수정 그람슈미트
1.155\times10^
하우스홀더 (np.linalg.qr)
7.181\times10^
세 방법의 차이가 16 1 6
이론은 셋 다 같은 것을 계산합니다. 다른 것은 반올림 오차가 어떻게 쌓이는가 뿐입니다. 67강 문제 5에서 피벗팅 없는 소거가 무너진 것과 같은 구조입니다.
오차의 크기를 조건수로 설명할 수 있습니다.
방법
직교성 오차
고전
O ( ε mach κ 2 ) O ( ε mach κ 2 )
수정
O ( ε mach κ ) O ( ε mach κ )
하우스홀더
O ( ε mach ) O ( ε mach )
하우스홀더만 조건수에 무관 합니다. 심화 5에서 그 이유를 봅니다.
실무의 결론 입니다.
손으로는 그람슈미트, 코드로는 qr 손으로는 그람슈미트 , 코드로는 qr
그람슈미트는 개념을 보여 주고 QR 분해로 이어지지만, 실제 계산은 라이브러리에 맡깁니다. 69강과 70강에서 반복한 원칙이 네 번째로 같습니다.
바로 확인 5.
확인 5-1. 고전과 수정 그람슈미트의 차이를 쓰세요.
답. 원래 벡터와 내적하느냐 갱신된 벡터와 내적하느냐입니다.
확인 5-2. 정확한 산술에서 두 결과가 같습니까?
답. 같습니다. 부동소수점에서만 달라집니다.
확인 5-3. 실무에서 무엇을 씁니까?
답. 하우스홀더 기반의 qr을 씁니다.
개념
식
정규직교
q i ⋅ q j = δ i j q i ⋅ q j = δ i j Q ⊤ Q = I Q ⊤ Q = I
좌표
c_{i}=\mathbf{v}\cdot\mathbf{q}_
파스발
\lVert\mathbf{v}\rVert^{2}=\sum c_{i}^
그람슈미트
\mathbf{w}_{k}=\mathbf{a}_{k}-\sum_{j
정사영
P=W(W^{\top}W)^{-1}W^
정규직교이면
P=QQ^
여공간
I − P I − P
P P 값
P^
P P
P^
P P
rank P r a n k P dim W dim W
tr P t r P dim W dim W
안정성
오차
고전 그람슈미트
O ( ε κ 2 ) O ( ε κ 2 )
수정 그람슈미트
O ( ε κ ) O ( ε κ )
하우스홀더
O ( ε ) O ( ε )
자주 하는 실수
바로잡기
정규화를 잊습니다
매 단계 나눠야 Q ⊤ Q = I Q ⊤ Q = I
멱등만 보고 정사영이라 합니다
대칭도 필요합니다
고전 그람슈미트를 코드로 씁니다
qr을 씁니다
순서를 바꿔도 같다고 봅니다
다른 Q Q
문제 6. 정규직교기저에서 좌표를 구하는 식을 쓰세요.
답. c i = v ⋅ q i c i = v ⋅ q i
문제 7. Q ⊤ Q = I Q ⊤ Q = I Q − 1 Q − 1
답. Q ⊤ Q ⊤
문제 8. 그람슈미트의 한 단계를 쓰세요.
답. w k = a k − ∑ j < k ( a k ⋅ q j ) q j w k = a k − ∑ j < k ( a k ⋅ q j ) q j
문제 9. w k = 0 w k = 0
답. 원래 벡터들이 일차종속입니다.
문제 10. 그람슈미트가 보존하는 것을 쓰세요.
답. 처음 k k
문제 11. ( 1 , 1 ) ( 1 , 1 ) ( 1 , 0 ) ( 1 , 0 )
답. q 1 = 1 2 ( 1 , 1 ) q 1 = 2 1 ( 1 , 1 ) w 2 = ( 1 , 0 ) − 1 2 ( 1 , 1 ) = ( 1 2 , − 1 2 ) w 2 = ( 1 , 0 ) − 2 1 ( 1 , 1 ) = ( 2 1 , − 2 1 ) q 2 = 1 2 ( 1 , − 1 ) q 2 = 2 1 ( 1 , − 1 )
문제 12. 정사영 행렬의 일반 공식을 쓰세요.
답. P = W ( W ⊤ W ) − 1 W ⊤ P = W ( W ⊤ W ) − 1 W ⊤
문제 13. 정규직교기저일 때의 공식을 쓰세요.
답. P = Q Q ⊤ P = Q Q ⊤
문제 14. P P
답. 멱등 P 2 = P P 2 = P P ⊤ = P P ⊤ = P
문제 15. tr P t r P
답. 부분공간의 차원입니다.
문제 16. I − P I − P
답. W ⊥ W ⊥
문제 17. 고전과 수정 그람슈미트의 차이를 쓰세요.
답. 원래 벡터와 내적하느냐 갱신된 벡터와 내적하느냐입니다.
문제 18. 실무에서 직교화에 무엇을 씁니까?
답. 하우스홀더 기반 qr을 씁니다.
심화 1. 그람슈미트가 QR 분해를 만드는 과정을 밝히세요.
풀이. 문제 2에서 부분공간이 보존된다고 했습니다. 그 사실을 식으로 적으면 분해가 나옵니다.
a k a k q 1 , … , q k q 1 , … , q k
a k = ∑ j ≤ k r j k q j a k = j ≤ k ∑ r j k q j
이고, q q
r j k = q j ⋅ a k r j k = q j ⋅ a k
**j > k j > k 0 0 a k a k k k R = ( r j k ) R = ( r j k ) 위삼각 입니다.
행렬로 적으면
A = Q R A = Q R
이것이 QR 분해 이며 81강의 주제입니다.
대각 성분도 뜻이 있습니다.
r k k = q k ⋅ a k = ∥ w k ∥ r k k = q k ⋅ a k = ∥ w k ∥
그람슈미트에서 정규화하기 전 벡터의 길이 입니다. 그래서 양수이고, 이것이 QR 분해의 유일성을 줍니다.
대각이 양수인 R 을 요구하면 Q , R 이 유일합니다 대각이 양수인 R 을 요구하면 Q , R 이 유일합니다
r k k r k k a k a k
70강의 LU와 비교합니다.
분해
형태
얻는 것
LU
A = L U A = L U 방정식 풀이
QR
A = Q R A = Q R 직교기저 + 최소제곱
**둘 다 "삼각으로 만들기"**인데, LU는 소거로 하고 QR은 직교화로 합니다. QR이 두 배 비싸지만 훨씬 안정합니다.
심화 2. 정사영 행렬을 완전히 특징짓고 비직교 사영과 구별하세요.
풀이. 문제 3에서 멱등과 대칭을 확인했습니다. 그 둘이 정사영을 완전히 특징짓습니다.
정리. P P P 2 = P P 2 = P P ⊤ = P P ⊤ = P
(⇒ ⇒ 문제 3에서 확인했습니다.
(⇐ ⇐ P P W = C ( P ) W = C ( P )
w ∈ W w ∈ W w = P u w = P u P w = P 2 u = P u = w P w = P 2 u = P u = w W W
x x x − P x x − P x W W
( x − P x ) ⋅ P u = x ⊤ ( I − P ) ⊤ P u = x ⊤ ( I − P ) P u = x ⊤ ( P − P 2 ) u = 0 ( x − P x ) ⋅ P u = x ⊤ ( I − P ) ⊤ P u = x ⊤ ( I − P ) P u = x ⊤ ( P − P 2 ) u = 0
대칭성이 둘째 등호에서 쓰였습니다. 따라서 P P W W
대칭이 없으면 무너집니다.
S = ( 1 1 0 0 ) S = ( 1 0 1 0 )
S 2 = S S 2 = S x x x x 그런데 수직으로 내리지 않습니다.
S ( 0 , 1 ) = ( 1 , 0 ) S ( 0 , 1 ) = ( 1 , 0 )
( 0 , 1 ) ( 0 , 1 ) x x ( 0 , 0 ) ( 0 , 0 ) S S ( 1 , 0 ) ( 1 , 0 ) ( − 1 , 1 ) ( − 1 , 1 )
직교 사영
비직교 사영
멱등
예
예
대칭
예
아닙니다
최소 거리
줍니다 주지 않습니다
노름
∥ P x ∥ ≤ ∥ x ∥ ∥ P x ∥ ≤ ∥ x ∥ 커질 수 있습니다
셋째 줄이 결정적입니다. 64강 문제 2에서 정사영이 최소 거리를 준다고 했는데, 그 증명에 수직성이 필요 했습니다. 비스듬히 내리면 더 가까운 점이 있습니다.
넷째 줄도 확인합니다. S ( 0 , 1 ) = ( 1 , 0 ) S ( 0 , 1 ) = ( 1 , 0 ) 1 1 1 1 S ( 0 , 2 ) = ( 2 , 0 ) S ( 0 , 2 ) = ( 2 , 0 ) 직교 사영은 절대 늘리지 않습니다.
∥ P x ∥ 2 = ∥ x ∥ 2 − ∥ ( I − P ) x ∥ 2 ≤ ∥ x ∥ 2 ∥ P x ∥ 2 = ∥ x ∥ 2 − ∥ ( I − P ) x ∥ 2 ≤ ∥ x ∥ 2
비직교 사영도 쓰임이 있습니다. 사각 성분을 특정 방향으로 제거하고 싶을 때 씁니다. 다만 "가장 가까운"을 원하면 직교여야 합니다.
심화 3. 함수 공간에서 그람슈미트를 실행해 르장드르 다항식을 얻으세요.
풀이. 71강 심화 2에서 함수 공간의 내적을 세웠습니다. [ − 1 , 1 ] [ − 1 , 1 ]
⟨ f , g ⟩ = ∫ − 1 1 f ( x ) g ( x ) d x ⟨ f , g ⟩ = ∫ − 1 1 f ( x ) g ( x ) d x
1 , x , x 2 , … 1 , x , x 2 , …
⟨ 1 , x 2 ⟩ = ∫ − 1 1 x 2 d x = 2 3 ≠ 0 ⟨ 1 , x 2 ⟩ = ∫ − 1 1 x 2 d x = 3 2 = 0
그람슈미트를 적용합니다.
p 0 p 0 ⟨ 1 , 1 ⟩ = 2 ⟨ 1 , 1 ⟩ = 2 1 2 2 1 p 0 = 1 p 0 = 1
p 1 p 1 ⟨ x , 1 ⟩ = ∫ − 1 1 x d x = 0 ⟨ x , 1 ⟩ = ∫ − 1 1 x d x = 0
p 1 = x p 1 = x
p 2 p 2
p 2 = x 2 − ⟨ x 2 , 1 ⟩ ⟨ 1 , 1 ⟩ ⋅ 1 − ⟨ x 2 , x ⟩ ⟨ x , x ⟩ ⋅ x = x 2 − 2 / 3 2 − 0 = x 2 − 1 3 p 2 = x 2 − ⟨ 1 , 1 ⟩ ⟨ x 2 , 1 ⟩ ⋅ 1 − ⟨ x , x ⟩ ⟨ x 2 , x ⟩ ⋅ x = x 2 − 2 2 / 3 − 0 = x 2 − 3 1
관례상 p 2 ( 1 ) = 1 p 2 ( 1 ) = 1 3 2 x 2 − 1 2 2 3 x 2 − 2 1
계속하면 르장드르 다항식 이 나옵니다.
P 0 = 1 , P 1 = x , P 2 = 3 2 x 2 − 1 2 , P 3 = 5 2 x 3 − 3 2 x P 0 = 1 , P 1 = x , P 2 = 2 3 x 2 − 2 1 , P 3 = 2 5 x 3 − 2 3 x
왜 유용한가. 함수를 다항식으로 근사할 때 표준기저 { x k } { x k } 직교기저를 쓰면 계수가 내적으로 나오고 안정합니다.
f ≈ ∑ k ⟨ f , P k ⟩ ⟨ P k , P k ⟩ P k f ≈ k ∑ ⟨ P k , P k ⟩ ⟨ f , P k ⟩ P k
59강의 푸리에와 같은 형태 입니다. 기저만 삼각함수에서 다항식으로 바뀌었습니다.
다른 가중치를 쓰면 다른 다항식족이 나옵니다.
가중치
구간
이름
1 1 [ − 1 , 1 ] [ − 1 , 1 ] 르장드르
1 / 1 − x 2 1 / 1 − x 2 [ − 1 , 1 ] [ − 1 , 1 ] 체비셰프
e^
[ 0 , ∞ ) [ 0 , ∞ ) 라게르
e − x 2 e − x 2 ( − ∞ , ∞ ) ( − ∞ , ∞ ) 에르미트
둘째 줄이 수치해석에서 가장 많이 쓰입니다. 근사 오차가 구간 전체에 고르게 퍼지기 때문입니다.
넷째 줄은 확률과 물리에 나옵니다. 가중치가 정규분포이므로, 가우스 분포에 대한 직교 다항식입니다. 양자역학의 조화진동자와 확률의 적률 전개에서 씁니다.
심화 4. 고전 그람슈미트가 무너지는 이유를 오차 분석으로 설명하세요.
풀이. 문제 5에서 결과를 보았습니다. 왜 그런지 봅니다.
k k a k a k q j q j q ^ j q ^ j
q ^ i ⋅ q ^ j = δ i j + η i j , ∣ η i j ∣ ∼ ε mach q ^ i ⋅ q ^ j = δ i j + η i j , ∣ η i j ∣ ∼ ε mach
고전판 은 원래 a k a k q j q j η η w k w k 상대적으로 큰 오염 이 됩니다.
남은 오염 ∥ w k ∥ ∼ ε ∥ a k ∥ ∥ w k ∥ ∥ w k ∥ 남은 오염 ∼ ∥ w k ∥ ε ∥ a k ∥
분모가 작으면 폭발합니다. 심화 1에서 ∥ w k ∥ = r k k ∥ w k ∥ = r k k
문제 5의 예에서 확인합니다. 세 열이 거의 ( 1 , 0 , 0 , 0 ) ( 1 , 0 , 0 , 0 )
∥ a k ∥ ≈ 1 , ∥ w 2 ∥ ≈ ε 2 = 1.4 × 1 0 − 8 ∥ a k ∥ ≈ 1 , ∥ w 2 ∥ ≈ ε 2 = 1 . 4 × 1 0 − 8
이고 비가 1 0 8 1 0 8 1 0 − 16 × 1 0 8 = 1 0 − 8 1 0 − 1 6 × 1 0 8 = 1 0 − 8 실제로는 0.7 0 . 7 오염이 다음 단계로 전파되며 제곱으로 커지기 때문입니다.
고전 : O ( ε κ 2 ) , κ ≈ 1 0 8 ⇒ 1 0 − 16 × 1 0 16 = 1 고전 : O ( ε κ 2 ) , κ ≈ 1 0 8 ⇒ 1 0 − 1 6 × 1 0 1 6 = 1
정확히 관측과 맞습니다. 0.707 0 . 7 0 7 1 1
수정판이 나은 이유 는 갱신된 w w
수정 : O ( ε κ ) = 1 0 − 16 × 1 0 8 = 1 0 − 8 수정 : O ( ε κ ) = 1 0 − 1 6 × 1 0 8 = 1 0 − 8
검산의 1.155 × 1 0 − 8 1 . 1 5 5 × 1 0 − 8
재직교화 라는 방법도 있습니다. 고전판을 두 번 돌리면 오차가 O ( ε ) O ( ε )
"두 번이면 충분하다" " 두 번이면 충분하다 "
라는 경험칙이 있으며, 이론적 근거도 있습니다. 다만 비용이 두 배이므로, 대개는 하우스홀더를 씁니다.
심화 5. 하우스홀더 반사를 소개하고 왜 안정한지 밝히세요.
풀이. 그람슈미트는 벡터를 만들어 갑니다. 하우스홀더는 반대로 행렬을 직교변환으로 삼각화합니다.
하우스홀더 반사. 단위벡터 u u
H = I − 2 u u ⊤ H = I − 2 u u ⊤
은 u u
성질을 확인합니다.
H ⊤ = H , H 2 = I − 4 u u ⊤ + 4 u ( u ⊤ u ) u ⊤ = I H ⊤ = H , H 2 = I − 4 u u ⊤ + 4 u ( u ⊤ u ) u ⊤ = I
대칭이고 자기 자신이 역 이며, 따라서 직교행렬입니다.
u u
H u = u − 2 u = − u , H v = v ( v ⊥ u ) H u = u − 2 u = − u , H v = v ( v ⊥ u )
78강 문제 5의 det Q = − 1 det Q = − 1 이며, 79강 심화 2의 방향 반전입니다.
QR을 만드는 방법 은 이렇습니다. 첫 열을 e 1 e 1 H 1 H 1
H n ⋯ H 1 A = R ⟹ A = ( H 1 ⋯ H n ) R = Q R H n ⋯ H 1 A = R ⟹ A = ( H 1 ⋯ H n ) R = Q R
왜 안정한가. 각 단계가 직교변환 이기 때문입니다. 직교변환은 노름을 보존하므로 오차를 증폭하지 않습니다.
∥ H e ∥ = ∥ e ∥ ∥ H e ∥ = ∥ e ∥
오차가 커지지 않고 그대로 옮겨갈 뿐 입니다. 그래서 조건수에 무관하게 O ( ε ) O ( ε )
그람슈미트와 비교합니다.
그람슈미트
하우스홀더
방식
벡터를 만듭니다
행렬을 삼각화합니다
각 연산
뺄셈과 나눗셈
직교변환
오차
증폭될 수 있습니다
증폭되지 않습니다
Q Q 명시적
반사 벡터들로 압축
계산량
2mn^
2 m n 2 − 2 n 3 / 3 2 m n 2 − 2 n 3 / 3
넷째 줄이 실용적입니다. Q Q u u Q x Q x
기븐스 회전 이라는 방법도 있습니다. 성분을 하나씩 0 0
하우스홀더 = 덩어리로 , 기븐스 = 하나씩 하우스홀더 = 덩어리로 , 기븐스 = 하나씩
심화 6. 직교화가 실무에서 쓰이는 자리를 정리하세요.
풀이. 직교기저를 만드는 일이 왜 중요한지 응용으로 봅니다.
최소제곱. 82강의 정규방정식 A ⊤ A x = A ⊤ b A ⊤ A x = A ⊤ b κ ( A ) 2 κ ( A ) 2 QR을 쓰면 κ ( A ) κ ( A ) 됩니다. 회귀 계산의 표준 방법입니다.
R x = Q ⊤ b R x = Q ⊤ b
고유값 계산. QR 알고리즘은 A = Q R A = Q R R Q R Q 닮음 변환이므로 고유값이 보존 되고, 반복하면 삼각형에 수렴합니다. 84강에서 다룹니다.
백색화. 75강 심화 5에서 언급했습니다. 데이터의 상관을 없애는 것이 직교화이며, 주성분분석의 전처리입니다.
특징 직교화. 회귀에서 설명변수가 상관이 높으면 계수가 불안정합니다. 직교화하면 각 변수의 기여가 분리되어 해석이 쉬워집니다. 다만 새 변수의 의미가 흐려지는 대가 가 있습니다.
신경망의 초기화. 가중치 행렬을 직교로 초기화하면 신호가 층을 지나며 크기를 유지합니다. 노름 보존 성질 을 쓰는 것이며, 246강의 그래디언트 소실 문제와 이어집니다.
어텐션의 위치 인코딩. 서로 다른 위치를 구별하려면 표현이 잘 분리되어야 하고, 직교에 가까운 것이 유리합니다. 73강 심화 4에서 본 고차원의 "거의 직교" 성질이 여기서 쓰입니다.
정리합니다.
응용
직교화가 주는 것
최소제곱
조건수를 제곱하지 않음
고유값
안정한 닮음 변환
백색화
상관 제거
특징 처리
기여의 분리
신경망 초기화
신호 크기 보존
**공통 원리는 "직교변환은 오차를 증폭하지 않는다"**입니다. 심화 5에서 본 이유이며, 이 과목 후반부가 직교 분해에 집중하는 근거입니다.
이 강의에서는 numpy만 씁니다. 그람슈미트를 직접 구현해 직교성을 확인하고, 정사영 행렬의 성질을 검산하며, 고전판과 수정판의 안정성 차이를 수치로 드러내는 것 이 핵심입니다.
import numpy as np
# --- 문제 1: 직교기저에서 좌표는 내적입니다 ------------------------------
q1 = np.array([1.,1.,1.])/np.sqrt(3)
q2 = np.array([1.,-1.,0.])/np.sqrt(2)
q3 = np.array([1.,1.,-2.])/np.sqrt(6)
Q = np.column_stack([q1,q2,q3])
print((np.round(Q.T@Q,10)+0.0).tolist())
# [[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]]
v = np.array([3.,1.,-2.]); c = Q.T@v
print(np.round(c,8).tolist()) # [1.15470054, 1.41421356, 3.26598632]
print(np.round(Q@c,10).tolist()) # [3.0, 1.0, -2.0]
print("%.8f %.8f" % (np.linalg.norm(v), np.linalg.norm(c)))
# 3.74165739 3.74165739 (파스발)
# --- 문제 2: 그람슈미트 --------------------------------------------------
def gram_schmidt(A):
n = A.shape[1]; Qc = []
for j in range(n):
w = A[:,j].astype(float).copy()
for q in Qc: w = w - (q @ A[:,j]) * q
Qc.append(w / np.linalg.norm(w))
return np.column_stack(Qc)
A = np.column_stack([[1.,1.,0.],[1.,0.,1.],[0.,1.,1.]])
G = gram_schmidt(A)
print(np.round(G,8).tolist())
# [[0.70710678, 0.40824829, -0.57735027], [0.70710678, -0.40824829, 0.57735027],
# [0.0, 0.81649658, 0.57735027]]
print((np.round(G.T@G,10)+0.0).tolist())
# [[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]]
for j in range(3): # 처음 j+1 개가 만드는 공간이 같은지
print(j, bool(np.allclose(
np.linalg.matrix_rank(np.column_stack([A[:,:j+1], G[:,:j+1]])),
np.linalg.matrix_rank(A[:,:j+1]))))
# 0 True
# 1 True
# 2 True
# --- 문제 3: 정사영 행렬 -------------------------------------------------
W = np.column_stack([[1.,1.,0.],[0.,1.,1.]])
P = W @ np.linalg.solve(W.T@W, W.T)
print(np.round(P,8).tolist())
# [[0.66666667, 0.33333333, -0.33333333], [0.33333333, 0.66666667, 0.33333333],
# [-0.33333333, 0.33333333, 0.66666667]]
print(bool(np.allclose(P@P, P)), bool(np.allclose(P, P.T))) # True True
x = np.array([2.,0.,3.]); px = P@x; rx = x - px
print(np.round(px,8).tolist(), np.round(rx,8).tolist())
# [0.33333333, 1.66666667, 1.33333333] [1.66666667, -1.66666667, 1.66666667]
print("%.12f" % float(px @ rx)) # 0.000000000000 (직교)
Qw = gram_schmidt(W)
print(bool(np.allclose(Qw@Qw.T, P))) # True (정규직교이면 P = QQ^T)
print(int(np.linalg.matrix_rank(P)), "%.8f" % float(np.trace(P))) # 2 2.00000000
# --- 문제 4: 직교여공간 --------------------------------------------------
n_ = np.cross(W[:,0], W[:,1]); n_ = n_/np.linalg.norm(n_)
print(np.round(n_,8).tolist()) # [0.57735027, -0.57735027, 0.57735027]
print(np.round(W.T@n_,12).tolist()) # [0.0, 0.0]
print(np.round((np.eye(3)-P)@x,8).tolist(), np.round((n_@x)*n_,8).tolist())
# [1.66666667, -1.66666667, 1.66666667] [1.66666667, -1.66666667, 1.66666667]
# --- 문제 5: 고전 대 수정 그람슈미트 -------------------------------------
def cgs(A): # 고전: 원래 열과 내적
n = A.shape[1]; Qc = []
for j in range(n):
w = A[:,j].astype(float).copy()
for q in Qc: w = w - (q @ A[:,j]) * q
Qc.append(w / np.linalg.norm(w))
return np.column_stack(Qc)
def mgs(A): # 수정: 갱신된 열과 내적
n = A.shape[1]; V = A.astype(float).copy(); Qc = []
for j in range(n):
q = V[:,j] / np.linalg.norm(V[:,j]); Qc.append(q)
for k in range(j+1, n): V[:,k] = V[:,k] - (q @ V[:,k]) * q
return np.column_stack(Qc)
eps = 1e-8
X = np.array([[1.,1.,1.],[eps,0.,0.],[0.,eps,0.],[0.,0.,eps]])
for name, f in [("고전", cgs), ("수정", mgs)]:
print(name, "%.3e" % float(np.linalg.norm(f(X).T @ f(X) - np.eye(3))))
# 고전 7.071e-01 <- 직교성이 완전히 무너졌습니다
# 수정 1.155e-08
Qh, _ = np.linalg.qr(X)
print("하우스홀더", "%.3e" % float(np.linalg.norm(Qh.T@Qh - np.eye(3))))
# 하우스홀더 7.181e-16
실행하면 주석과 같은 값이 나옵니다. 다섯 곳을 짚어 둡니다.
첫째, 정규직교기저에서 좌표가 내적으로 나오고 되돌리면 원래 벡터입니다. 노름이 14 = 3.7417 1 4 = 3 . 7 4 1 7
둘째, 그람슈미트 결과가 Q ⊤ Q = I Q ⊤ Q = I 처음 k k 됩니다.
셋째, 정사영 행렬이 멱등이고 대칭이며 두 성분의 내적이 정확히 0 0 정규직교기저로 만든 Q Q ⊤ Q Q ⊤ 그리고 계수와 대각합이 둘 다 2 2
넷째, ( I − P ) x ( I − P ) x
다섯째가 이 강의의 경고입니다. 같은 수학을 세 가지로 구현했더니 오차가 0.707 0 . 7 0 7 1.2 × 1 0 − 8 1 . 2 × 1 0 − 8 7.2 × 1 0 − 16 7 . 2 × 1 0 − 1 6 고전판의 0.707 0 . 7 0 7 O ( ε κ 2 ) O ( ε κ 2 ) O ( ε κ ) O ( ε κ ) O ( ε ) O ( ε ) κ ≈ 1 0 8 κ ≈ 1 0 8
코드로 할 수 없는 일도 분명히 해 둡니다. 그람슈미트가 언제나 직교기저를 준다는 것은 예로 증명되지 않습니다. 문제 2의 논증이 그 자리를 맡습니다. 그리고 이 검산의 안정성 비교는 특정 조건수에서의 관측 이며, 다른 행렬에서는 차이가 작을 수 있습니다. 조건이 좋으면 세 방법이 비슷합니다. 69강 문제 5에서 inv와 solve를 비교할 때와 같은 상황이며, 차이는 언제나 조건이 나쁠 때 드러납니다.
정규직교기저에서 좌표를 구하는 식을 쓰세요.
그 이점을 계산량으로 쓰세요.
그람슈미트의 한 단계를 쓰세요.
그 단계가 직교를 만드는 근거를 쓰세요.
그람슈미트가 보존하는 성질을 쓰세요.
정사영 행렬의 두 공식을 쓰세요.
정사영을 특징짓는 두 성질을 쓰세요.
대칭이 없으면 무엇이 무너집니까?
I − P I − P 고전 그람슈미트가 왜 불안정합니까?
정답.
c i = v ⋅ q i c i = v ⋅ q i n 3 / 3 n 3 / 3 n 2 n 2 w k = a k − ∑ j < k ( a k ⋅ q j ) q j w k = a k − ∑ j < k ( a k ⋅ q j ) q j 이미 만든 q i q i 0 0
처음 k k
P = W ( W ⊤ W ) − 1 W ⊤ P = W ( W ⊤ W ) − 1 W ⊤ Q Q ⊤ Q Q ⊤ 멱등 P 2 = P P 2 = P P ⊤ = P P ⊤ = P
최소 거리 성질이 무너집니다. 비스듬히 내리기 때문입니다.
W ⊥ W ⊥ 오차가 조건수의 제곱으로 증폭되기 때문입니다.
기호
읽는 법
뜻
\delta_
크로네커 델타
같으면 1 1 0 0
Q Q 직교행렬
Q ⊤ Q = I Q ⊤ Q = I
P P 정사영 행렬
멱등이고 대칭입니다
I − P I − P 여사영
W ⊥ W ⊥
CGS
고전 그람슈미트
불안정합니다
MGS
수정 그람슈미트
순서를 바꾼 판입니다
H=I-2\mathbf{u}\mathbf{u}^
하우스홀더 반사
직교이고 자기역입니다
르장드르
Legendre
함수 공간의 직교 다항식입니다
다음 81강에서는 이 강의의 절차를 분해로 정리 합니다. 심화 1에서 본 대로 그람슈미트가 A = Q R A = Q R