이 과목 내내 "크기"를 재 왔습니다.
62강에서 ∥ v ∥ = v ⋅ v ∥ v ∥ = v ⋅ v ∥ A x − b ∥ ∥ A x − b ∥ ∥ A ∥ 2 = σ 1 ∥ A ∥ 2 = σ 1
그런데 "크기"가 하나가 아닙니다.
v = ( 3 , − 4 , 12 ) ⟹ 19 , 13 , 12 v = ( 3 , − 4 , 1 2 ) ⟹ 1 9 , 1 3 , 1 2
세 값이 모두 이 벡터의 크기입니다. 어느 것을 쓰느냐가 답을 바꿉니다. 82강 문제 1에서 최소제곱 대신 절댓값의 합이나 최댓값을 최소화할 수 있다고 했는데, 그 선택이 곧 노름의 선택 이었습니다.
이 강의는 크기 재는 법을 정리 합니다. 그리고 행렬의 크기로 넘어갑니다. 행렬은 변환이므로 크기를 재는 자연스러운 방법이 하나 있습니다.
∥ A ∥ = ∥ x ∥ = 1 ∥ A x ∥ ∥ A ∥ = ∥ x ∥ = 1 max ∥ A x ∥
가장 많이 늘이는 배율 입니다. 91강의 조건수가 이 위에 세워집니다.
세 가지 벡터 노름을 계산하고 관계를 말할 수 있습니다.
노름의 세 공리를 확인할 수 있습니다.
유도 행렬 노름을 정의하고 계산할 수 있습니다.
부등식들을 쓰고 언제 등호인지 압니다.
스펙트럼 반지름과 노름의 차이를 설명할 수 있습니다.
문제. v = ( 3 , − 4 , 12 ) v = ( 3 , − 4 , 1 2 )
생각의 실마리. 세 값이 모두 "이 벡터가 얼마나 큰가"에 답합니다. 무엇을 재려느냐에 따라 다른 것을 씁니다.
풀이. 검산에서
방식
값
절댓값의 합
19 1 9
제곱합의 제곱근
13 1 3
절댓값의 최댓값
12 1 2
언제나 이 순서 입니다. 문제 2에서 확인합니다.
이 문제에서 배우는 것: p p
p p p ≥ 1 p ≥ 1
∥ v ∥ p = ( ∑ i ∣ v i ∣ p ) 1 / p ∥ v ∥ p = ( i ∑ ∣ v i ∣ p ) 1 / p
이며 p = ∞ p = ∞ ∥ v ∥ ∞ = i ∣ v i ∣ ∥ v ∥ ∞ = max i ∣ v i ∣
세 가지가 특히 중요합니다.
이름
기호
뜻
맨해튼
\lVert\cdot\rVert_
격자 위를 걸은 거리
유클리드
\lVert\cdot\rVert_
직선 거리
최대
\lVert\cdot\rVert_
가장 큰 성분
p → ∞ p → ∞
p p \lVert\mathbf{v}\rVert_
1 1 19.00000000 1 9 . 0 0 0 0 0 0 0 0
2 2 13.00000000 1 3 . 0 0 0 0 0 0 0 0
4 4 12.04846143 1 2 . 0 4 8 4 6 1 4 3
8 8 12.00025149 1 2 . 0 0 0 2 5 1 4 9
32 3 2 12.00000000 1 2 . 0 0 0 0 0 0 0 0
p = 32 p = 3 2 12 1 2
∥ v ∥ p = ∣ v max ∣ ( ∑ i ∣ v i v max ∣ p ) 1 / p ∥ v ∥ p = ∣ v m a x ∣ ( i ∑ ∣ ∣ ∣ ∣ v m a x v i ∣ ∣ ∣ ∣ p ) 1 / p
괄호 안의 항들이 1 1 p p 1 1
단위구의 모양 도 다릅니다.
노름
∥ v ∥ = 1 ∥ v ∥ = 1 n = 2 n = 2
p = 1 p = 1 마름모
p = 2 p = 2 원
p = ∞ p = ∞ 정사각형
p p ℓ 1 ℓ 1 해가 축에 붙기 쉽습니다.
바로 확인 1.
확인 1-1. p p
답. ( ∑ ∣ v i ∣ p ) 1 / p ( ∑ ∣ v i ∣ p ) 1 / p
확인 1-2. p → ∞ p → ∞
답. 절댓값의 최댓값입니다.
확인 1-3. ℓ 1 ℓ 1
답. 마름모입니다.
문제. 노름의 조건과 세 노름의 관계를 봅니다.∥ v ∥ 2 / ∥ v ∥ 1 ∥ v ∥ 2 / ∥ v ∥ 1 ∥ v ∥ ∞ / ∥ v ∥ 2 ∥ v ∥ ∞ / ∥ v ∥ 2
생각의 실마리. (2)와 (3)에서 극단적인 경우 를 생각합니다. 성분이 하나만 있을 때와 모두 같을 때입니다.
풀이. (1) 세 조건입니다.
∥ v ∥ ≥ 0 이고 = 0 ⇔ v = 0 ∥ v ∥ ≥ 0 이고 = 0 ⇔ v = 0
∥ c v ∥ = ∣ c ∣ ∥ v ∥ ∥ c v ∥ = ∣ c ∣ ∥ v ∥
∥ u + v ∥ ≤ ∥ u ∥ + ∥ v ∥ ∥ u + v ∥ ≤ ∥ u ∥ + ∥ v ∥
(2) n = 6 n = 6 5000 5 0 0 0 [ 0.410780 , 0.804342 ] [ 0 . 4 1 0 7 8 0 , 0 . 8 0 4 3 4 2 ] [ 1 / 6 , 1 ] = [ 0.408248 , 1 ] [ 1 / 6 , 1 ] = [ 0 . 4 0 8 2 4 8 , 1 ]
(3) 비가 [ 0.465581 , 0.989490 ] [ 0 . 4 6 5 5 8 1 , 0 . 9 8 9 4 9 0 ]
이 문제에서 배우는 것: 노름의 공리와 동치성.
노름. 세 조건(양정치성, 동차성, 삼각부등식)을 만족하는 함수를 노름 이라 합니다.
63강에서 내적으로 노름을 만들었는데, 모든 노름이 내적에서 오는 것은 아닙니다. ℓ 1 ℓ 1 ℓ ∞ ℓ ∞
내적에서 온 노름 ⟺ 평행사변형 법칙을 만족 내적에서 온 노름 ⟺ 평행사변형 법칙을 만족
∥ u + v ∥ 2 + ∥ u − v ∥ 2 = 2 ∥ u ∥ 2 + 2 ∥ v ∥ 2 ∥ u + v ∥ 2 + ∥ u − v ∥ 2 = 2 ∥ u ∥ 2 + 2 ∥ v ∥ 2
ℓ 2 ℓ 2 ℓ 2 ℓ 2 ℓ 2 ℓ 2
동치성 이 중요합니다.
정리. 유한차원에서 모든 노름은 동치 입니다. 즉 상수 c , C > 0 c , C > 0
c ∥ v ∥ a ≤ ∥ v ∥ b ≤ C ∥ v ∥ a c ∥ v ∥ a ≤ ∥ v ∥ b ≤ C ∥ v ∥ a
구체적인 상수를 정리합니다.
관계
부등식
등호 조건
∥ ⋅ ∥ 2 ∥ ⋅ ∥ 2 \frac{1}{\sqrt n}\lVert\mathbf{v}\rVert_{1}\le\lVert\mathbf{v}\rVert_{2}\le\lVert\mathbf{v}\rVert_
왼쪽은 성분이 모두 같을 때, 오른쪽은 성분이 하나일 때
∥ ⋅ ∥ ∞ ∥ ⋅ ∥ ∞ \frac{1}{\sqrt n}\lVert\mathbf{v}\rVert_{2}\le\lVert\mathbf{v}\rVert_{\infty}\le\lVert\mathbf{v}\rVert_
같습니다
왼쪽 부등식이 코시-슈바르츠 입니다. 62강 심화 2에서 증명했습니다.
∥ v ∥ 1 = 1 ⋅ ∣ v ∣ ≤ ∥ 1 ∥ ∥ v ∥ 2 = n ∥ v ∥ 2 ∥ v ∥ 1 = 1 ⋅ ∣ v ∣ ≤ ∥ 1 ∥ ∥ v ∥ 2 = n ∥ v ∥ 2
동치성이 뜻하는 것 은 "수렴이냐 발산이냐"가 노름 선택에 무관하다는 것입니다. 어느 노름으로 0 0
정성적 결론은 노름과 무관 정성적 결론은 노름과 무관
그런데 정량적으로는 다릅니다. 상수 n n n n n = 1 0 6 n = 1 0 6 n = 1000 n = 1 0 0 0
무한차원에서는 동치가 아닙니다. 71강 심화 4에서 미분이 유계가 아니라 한 것이 그 예입니다.
바로 확인 2.
확인 2-1. 노름의 세 공리를 쓰세요.
답. 양정치성, 동차성, 삼각부등식입니다.
확인 2-2. 내적에서 온 노름의 특징을 쓰세요.
답. 평행사변형 법칙을 만족합니다.
확인 2-3. 유한차원 노름의 동치성이 뜻하는 것을 쓰세요.
답. 수렴 여부가 노름 선택과 무관합니다.
문제. A = ( 1 2 3 − 4 ) A = ( 1 3 2 − 4 ) ∥ A ∥ 1 ∥ A ∥ 1 ∥ A ∥ ∞ ∥ A ∥ ∞ ∥ A ∥ 2 ∥ A ∥ 2
생각의 실마리. 행렬은 변환이므로 **"얼마나 늘이는가"**로 재는 것이 자연스럽습니다.
∥ A ∥ = ∥ x ∥ = 1 ∥ A x ∥ ∥ A ∥ = ∥ x ∥ = 1 max ∥ A x ∥
어느 벡터 노름을 쓰느냐에 따라 다른 행렬 노름이 나옵니다.
풀이. (1) 검산에서 ∥ A ∥ 1 = 6 ∥ A ∥ 1 = 6 ∥ A ∥ ∞ = 7 ∥ A ∥ ∞ = 7
열 합 : ∣ 1 ∣ + ∣ 3 ∣ = 4 , ∣ 2 ∣ + ∣ − 4 ∣ = 6 ⟹ 6 열 합 : ∣ 1 ∣ + ∣ 3 ∣ = 4 , ∣ 2 ∣ + ∣ − 4 ∣ = 6 ⟹ 6
행 합 : ∣ 1 ∣ + ∣ 2 ∣ = 3 , ∣ 3 ∣ + ∣ − 4 ∣ = 7 ⟹ 7 행 합 : ∣ 1 ∣ + ∣ 2 ∣ = 3 , ∣ 3 ∣ + ∣ − 4 ∣ = 7 ⟹ 7
(2) ∥ A ∥ 2 = 5.11667274 ∥ A ∥ 2 = 5 . 1 1 6 6 7 2 7 4
표본으로도 확인 합니다. 단위원에서 20 2 0 ∥ A x ∥ ∥ A x ∥ 5.116673 5 . 1 1 6 6 7 3
(3) ∥ A ∥ F = 5.47722558 ∥ A ∥ F = 5 . 4 7 7 2 2 5 5 8 ∑ σ i 2 ∑ σ i 2
이 문제에서 배우는 것: 유도 노름.
유도 노름. 벡터 노름 ∥ ⋅ ∥ p ∥ ⋅ ∥ p
∥ A ∥ p = x ≠ 0 ∥ A x ∥ p ∥ x ∥ p ∥ A ∥ p = x = 0 max ∥ x ∥ p ∥ A x ∥ p
를 유도 노름 이라 합니다.
세 경우에 계산 공식이 있습니다.
노름
공식
기억법
\lVert A\rVert_
열의 절댓값 합의 최댓값
세로로 더합니다
\lVert A\rVert_
행의 절댓값 합의 최댓값
가로로 더합니다
\lVert A\rVert_
\sigma_
계산이 비쌉니다
1 1 ∞ ∞ ∥ A ∥ 1 ∥ A ∥ 1 ∥ A ∥ ∞ ∥ A ∥ ∞
이유를 봅니다. ∥ A x ∥ 1 ∥ A x ∥ 1 가장 큰 열 하나에 몰아주면 됩니다. x = e j x = e j A x A x j j
∥ A ∥ 1 = j ∥ a j ∥ 1 ∥ A ∥ 1 = j max ∥ a j ∥ 1
∥ A x ∥ ∞ ∥ A x ∥ ∞ x x ∥ x ∥ ∞ ≤ 1 ∥ x ∥ ∞ ≤ 1
∥ A ∥ ∞ = i ∥ a ( i ) ∥ 1 ∥ A ∥ ∞ = i max ∥ a ( i ) ∥ 1
프로베니우스 노름은 유도 노름이 아닙니다.
∥ A ∥ F = ∑ i , j a i j 2 = ∑ i σ i 2 ∥ A ∥ F = i , j ∑ a i j 2 = i ∑ σ i 2
성분을 벡터처럼 보고 ℓ 2 ℓ 2 한 것이며, 63강 심화 2의 행렬 내적에서 옵니다.
∥ A ∥ F 2 = tr ( A ⊤ A ) ∥ A ∥ F 2 = t r ( A ⊤ A )
유도가 아니라는 증거 는 ∥ I n ∥ F = n ∥ I n ∥ F = n 1 1
노름
∥ I n ∥ ∥ I n ∥
유도 노름 (아무 p p
1 1
프로베니우스
n n
계산 비용 도 다릅니다.
노름
비용
∥ A ∥ 1 ∥ A ∥ 1 O ( m n ) O ( m n )
\lVert A\rVert_
O ( m n ) O ( m n )
\lVert A\rVert_
SVD 필요
둘째 줄이 싸기 때문에 실무에서 ℓ 2 ℓ 2
바로 확인 3.
확인 3-1. 유도 노름의 정의를 쓰세요.
답. 단위벡터를 가장 많이 늘이는 배율입니다.
확인 3-2. ∥ A ∥ 1 ∥ A ∥ 1 ∥ A ∥ ∞ ∥ A ∥ ∞
답. 각각 열과 행의 절댓값 합의 최댓값입니다.
확인 3-3. 프로베니우스 노름이 유도가 아닌 증거를 쓰세요.
답. ∥ I n ∥ F = n ≠ 1 ∥ I n ∥ F = n = 1
문제. 무작위 4 × 4 4 × 4 ∥ A x ∥ ∥ A x ∥ ∥ A ∥ ∥ x ∥ ∥ A ∥ ∥ x ∥ ∥ A B ∥ ∥ A B ∥ ∥ A ∥ ∥ B ∥ ∥ A ∥ ∥ B ∥ ∥ A ∥ 2 ∥ A ∥ 2
생각의 실마리. (1)과 (2)는 유도 노름의 정의에서 바로 나옵니다. 최대이므로 다른 것들은 그보다 작습니다.
풀이. 검산에서 확인합니다.
비교
왼쪽
오른쪽
∥ A x ∥ ∥ A x ∥ ∥ A ∥ 2 ∥ x ∥ ∥ A ∥ 2 ∥ x ∥ 2.580921 2 . 5 8 0 9 2 1 6.042044 6 . 0 4 2 0 4 4
∥ A B ∥ 2 ∥ A B ∥ 2 3.894395 3 . 8 9 4 3 9 5 5.510624 5 . 5 1 0 6 2 4
∥ A ∥ 2 ∥ A ∥ 2 2.599891 2 . 5 9 9 8 9 1 3.193091 3 . 1 9 3 0 9 1
∥ A ∥ F ∥ A ∥ F 3.193091 3 . 1 9 3 0 9 1 5.199782 5 . 1 9 9 7 8 2
모두 왼쪽이 작거나 같습니다.
이 문제에서 배우는 것: 노름 부등식.
부등식.
이름
식
일관성
∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥
준곱셈성
∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥ ∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥
노름 비교
\lVert A\rVert_{2}\le\lVert A\rVert_{F}\le\sqrt{r}\,\lVert A\rVert_
첫째 줄이 유도 노름의 정의 입니다. 최댓값이므로 개별 x x
둘째 줄의 증명 도 한 줄입니다.
∥ A B x ∥ ≤ ∥ A ∥ ∥ B x ∥ ≤ ∥ A ∥ ∥ B ∥ ∥ x ∥ ∥ A B x ∥ ≤ ∥ A ∥ ∥ B x ∥ ≤ ∥ A ∥ ∥ B ∥ ∥ x ∥
두 번 적용 했습니다.
셋째 줄이 88강의 특이값 에서 나옵니다.
∥ A ∥ 2 = σ 1 , ∥ A ∥ F = ∑ i = 1 r σ i 2 ∥ A ∥ 2 = σ 1 , ∥ A ∥ F = i = 1 ∑ r σ i 2
최댓값 하나 대 전부의 제곱합 이므로 부등식이 자명합니다. 등호는 계수가 1 1
이 부등식들이 왜 중요한가. 오차 분석의 도구이기 때문입니다.
x → x + Δ x ⟹ ∥ A Δ x ∥ ≤ ∥ A ∥ ∥ Δ x ∥ x → x + Δ x ⟹ ∥ A Δ x ∥ ≤ ∥ A ∥ ∥ Δ x ∥
입력 오차가 출력에 얼마나 전달되는지 의 상한을 줍니다. 91강에서 이것을 조건수로 정리합니다.
준곱셈성이 없으면 곤란합니다. 여러 단계의 계산에서 오차를 누적할 수 없기 때문입니다. 프로베니우스 노름도 준곱셈적 이라 이 용도로 쓸 수 있습니다.
∥ A B ∥ F ≤ ∥ A ∥ F ∥ B ∥ F ∥ A B ∥ F ≤ ∥ A ∥ F ∥ B ∥ F
바로 확인 4.
확인 4-1. 일관성 부등식을 쓰세요.
답. ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥
확인 4-2. 준곱셈성의 증명을 한 줄로 쓰세요.
답. 일관성을 두 번 적용합니다.
확인 4-3. ∥ A ∥ 2 ∥ A ∥ 2 ∥ A ∥ F ∥ A ∥ F
답. ∥ A ∥ 2 ≤ ∥ A ∥ F ≤ r ∥ A ∥ 2 ∥ A ∥ 2 ≤ ∥ A ∥ F ≤ r ∥ A ∥ 2
문제. 다음을 비교하세요.N = ( 0 5 0 0 ) N = ( 0 0 5 0 ) S = ( 4 1 1 3 ) S = ( 4 1 1 3 )
생각의 실마리. 84강 부록에서 스펙트럼 반지름 을 고유값 크기의 최댓값이라 했습니다. 노름과 같은지 봅니다.
풀이. (1) 검산에서 스펙트럼 반지름이 0 0 5 5 완전히 다릅니다.
멱영행렬이라 고유값이 0 0 5 5
(2) 대칭이면 둘 다 4.618034 4 . 6 1 8 0 3 4
(3) 두 행렬로 거듭제곱을 봅니다.
M = ( 0 0.9 0.9 0 ) M = ( 0 0 . 9 0 . 9 0 ) ρ = 0.9 ρ = 0 . 9
k k \lVert M^{k}\rVert_
\rho^
1 1 0.90000000 0 . 9 0 0 0 0 0 0 0 0.90000000 0 . 9 0 0 0 0 0 0 0
5 5 0.59049000 0 . 5 9 0 4 9 0 0 0 0.59049000 0 . 5 9 0 4 9 0 0 0
20 2 0 0.12157665 0 . 1 2 1 5 7 6 6 5 0.12157665 0 . 1 2 1 5 7 6 6 5
60 6 0 0.00179701 0 . 0 0 1 7 9 7 0 1 0.00179701 0 . 0 0 1 7 9 7 0 1
정확히 같습니다.
G = ( 0.5 10 0 0.5 ) G = ( 0 . 5 0 1 0 0 . 5 ) ρ = 0.5 ρ = 0 . 5
k k \lVert G^{k}\rVert_
\rho^
1 1 1.0025\times10^
5.0000\times10^
3 3 7.5021\times10^
1.2500\times10^
10 1 0 1.9532\times10^
9.7656\times10^
40 4 0 7.2760\times10^
9.0949\times10^
k = 1 k = 1 20 2 0 k = 40 k = 4 0 800 8 0 0
이 문제에서 배우는 것: 스펙트럼 반지름과 노름.
스펙트럼 반지름. ρ ( A ) = i ∣ λ i ∣ ρ ( A ) = max i ∣ λ i ∣
ρ ( A ) ≤ ∥ A ∥ ρ ( A ) ≤ ∥ A ∥
입니다. **대칭이면 ρ ( A ) = ∥ A ∥ 2 ρ ( A ) = ∥ A ∥ 2
부등식의 증명 은 짧습니다. A v = λ v A v = λ v
∣ λ ∣ ∥ v ∥ = ∥ A v ∥ ≤ ∥ A ∥ ∥ v ∥ ∣ λ ∣ ∥ v ∥ = ∥ A v ∥ ≤ ∥ A ∥ ∥ v ∥
등호가 언제인가 를 정리합니다.
행렬
ρ ρ
대칭
같습니다
정규 (A ∗ A = A A ∗ A ∗ A = A A ∗
같습니다
일반
ρ < ∥ A ∥ 2 ρ < ∥ A ∥ 2
멱영
ρ = 0 ρ = 0
둘째 줄이 86강 심화 2의 정규행렬 입니다. 유니터리 대각화되면 노름이 고유값의 크기로 정해집니다.
k → ∞ k → ∞ ρ ρ
겔판트 공식.
k → ∞ ∥ A k ∥ 1 / k = ρ ( A ) k → ∞ lim ∥ A k ∥ 1 / k = ρ ( A )
검산에서 G G
k k \lVert G^{k}\rVert^
ρ ρ
1 1 10.02493781 1 0 . 0 2 4 9 3 7 8 1 0.50000000 0 . 5 0 0 0 0 0 0 0
5 5 1.25596833 1 . 2 5 5 9 6 8 3 3 0.50000000 0 . 5 0 0 0 0 0 0 0
20 2 0 0.67464163 0 . 6 7 4 6 4 1 6 3 0.50000000 0 . 5 0 0 0 0 0 0 0
80 8 0 0.54830412 0 . 5 4 8 3 0 4 1 2 0.50000000 0 . 5 0 0 0 0 0 0 0
200 2 0 0 0.52117108 0 . 5 2 1 1 7 1 0 8 0.50000000 0 . 5 0 0 0 0 0 0 0
천천히 수렴합니다. k = 200 k = 2 0 0 0.521 0 . 5 2 1 k m − 1 k m − 1
∥ G k ∥ ≈ C k ρ k ⟹ ∥ G k ∥ 1 / k ≈ ρ k 1 / k → ρ ∥ G k ∥ ≈ C k ρ k ⟹ ∥ G k ∥ 1 / k ≈ ρ k 1 / k → ρ
실무적 함의 가 중요합니다.
묻는 것
보는 것
장기적으로 수렴하는가
ρ < 1 ρ < 1
매 단계 줄어드는가
∥ A ∥ < 1 ∥ A ∥ < 1
초기에 커지는가
∥ A ∥ > 1 ∥ A ∥ > 1 ρ < 1 ρ < 1
셋째 줄이 과도 증폭 입니다. 결국은 수렴하지만 중간에 크게 부풀 수 있습니다. G G k = 3 k = 3 7.5 7 . 5
246강의 그래디언트 폭발 이 이 현상입니다. 스펙트럼 반지름만 보면 안전해 보이는데 실제로는 중간에 터집니다.
바로 확인 5.
확인 5-1. 스펙트럼 반지름과 노름의 부등식을 쓰세요.
답. ρ ( A ) ≤ ∥ A ∥ ρ ( A ) ≤ ∥ A ∥
확인 5-2. 등호가 성립하는 경우를 쓰세요.
답. 대칭이거나 정규행렬일 때입니다.
확인 5-3. 겔판트 공식을 쓰세요.
답. k ∥ A k ∥ 1 / k = ρ ( A ) lim k ∥ A k ∥ 1 / k = ρ ( A )
벡터 노름
정의
\lVert\mathbf{v}\rVert_
절댓값의 합
\lVert\mathbf{v}\rVert_
제곱합의 제곱근
\lVert\mathbf{v}\rVert_
절댓값의 최댓값
공리
양정치, 동차, 삼각부등식
행렬 노름
계산
\lVert A\rVert_
열 절댓값 합의 최댓값
\lVert A\rVert_
행 절댓값 합의 최댓값
\lVert A\rVert_
\sigma_
\lVert A\rVert_
∑ σ i 2 = tr ( A ⊤ A ) ∑ σ i 2 = t r ( A ⊤ A )
부등식
일관성
∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥
준곱셈
∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥ ∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥
비교
\lVert A\rVert_{2}\le\lVert A\rVert_{F}\le\sqrt r\lVert A\rVert_
스펙트럼
ρ ( A ) ≤ ∥ A ∥ ρ ( A ) ≤ ∥ A ∥
자주 하는 실수
바로잡기
∥ A ∥ 1 ∥ A ∥ 1 열입니다
프로베니우스를 유도 노름이라 합니다
∥ I ∥ F = n ∥ I ∥ F = n
ρ ρ 멱영에서 0 0
ρ < 1 ρ < 1 중간에 부풀 수 있습니다
문제 6. ( 1 , − 2 , 2 ) ( 1 , − 2 , 2 )
답. 5 5 3 3 2 2
문제 7. p → ∞ p → ∞
답. 절댓값의 최댓값입니다.
문제 8. 노름의 세 공리를 쓰세요.
답. 양정치성, 동차성, 삼각부등식입니다.
문제 9. 내적에서 온 노름의 특징을 쓰세요.
답. 평행사변형 법칙을 만족합니다.
문제 10. 유한차원 노름의 동치성을 쓰세요.
답. 두 노름이 상수배 범위로 서로를 감쌉니다.
문제 11. 유도 노름의 정의를 쓰세요.
답. 단위벡터를 가장 많이 늘이는 배율입니다.
문제 12. ( 2 − 1 3 4 ) ( 2 3 − 1 4 ) ∥ ⋅ ∥ 1 ∥ ⋅ ∥ 1 ∥ ⋅ ∥ ∞ ∥ ⋅ ∥ ∞
답. 열 합이 5 , 5 5 , 5 5 5 3 , 7 3 , 7 7 7
문제 13. ∥ A ∥ 2 ∥ A ∥ 2
답. σ 1 σ 1
문제 14. 프로베니우스 노름을 두 가지로 쓰세요.
답. ∑ a i j 2 ∑ a i j 2 tr ( A ⊤ A ) t r ( A ⊤ A )
문제 15. ∥ I n ∥ F ∥ I n ∥ F
답. n n
문제 16. 준곱셈성을 쓰세요.
답. ∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥ ∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥
문제 17. 스펙트럼 반지름과 노름의 관계를 쓰세요.
답. ρ ( A ) ≤ ∥ A ∥ ρ ( A ) ≤ ∥ A ∥
문제 18. ρ < 1 ρ < 1
답. 결손이거나 비정규이면 ∥ A ∥ > 1 ∥ A ∥ > 1
심화 1. 노름 동치성의 상수를 구하고 증명하세요.
풀이. 문제 2에서 관측한 범위를 증명합니다.
∥ v ∥ 2 ≤ ∥ v ∥ 1 ∥ v ∥ 2 ≤ ∥ v ∥ 1
∥ v ∥ 1 2 = ( ∑ ∣ v i ∣ ) 2 = ∑ i v i 2 + 2 ∑ i < j ∣ v i ∣ ∣ v j ∣ ≥ ∥ v ∥ 2 2 ∥ v ∥ 1 2 = ( ∑ ∣ v i ∣ ) 2 = i ∑ v i 2 + 2 i < j ∑ ∣ v i ∣ ∣ v j ∣ ≥ ∥ v ∥ 2 2
교차항이 음이 아니기 때문 입니다. 등호는 성분이 하나만 0 0
∥ v ∥ 1 ≤ n ∥ v ∥ 2 ∥ v ∥ 1 ≤ n ∥ v ∥ 2 1 1 ∣ v ∣ ∣ v ∣
∑ i ∣ v i ∣ = 1 ⋅ ∣ v ∣ ≤ ∥ 1 ∥ 2 ∥ v ∥ 2 = n ∥ v ∥ 2 i ∑ ∣ v i ∣ = 1 ⋅ ∣ v ∣ ≤ ∥ 1 ∥ 2 ∥ v ∥ 2 = n ∥ v ∥ 2
등호는 ∣ v ∣ ∣ v ∣ 1 1 , 즉 모든 성분의 절댓값이 같을 때입니다.
∥ v ∥ ∞ ≤ ∥ v ∥ 2 ≤ n ∥ v ∥ ∞ ∥ v ∥ ∞ ≤ ∥ v ∥ 2 ≤ n ∥ v ∥ ∞
정리합니다.
부등식
상수
등호 조건
\lVert\cdot\rVert_{\infty}\le\lVert\cdot\rVert_{2}\le\lVert\cdot\rVert_
1 1 성분이 하나
\lVert\cdot\rVert_{1}\le\sqrt n\lVert\cdot\rVert_
n n 성분이 모두 같음
\lVert\cdot\rVert_{2}\le\sqrt n\lVert\cdot\rVert_
n n 성분이 모두 같음
차원이 커지면 상수가 커집니다. n = 1 0 6 n = 1 0 6 n = 1000 n = 1 0 0 0
동치성의 일반 증명 도 봅니다. 유한차원에서 단위구가 컴팩트이고 노름이 연속이므로, 그 위에서 최댓값과 최솟값을 가집니다. **그 두 값이 상수 c , C c , C
c = ∥ v ∥ a = 1 ∥ v ∥ b , C = ∥ v ∥ a = 1 ∥ v ∥ b c = ∥ v ∥ a = 1 min ∥ v ∥ b , C = ∥ v ∥ a = 1 max ∥ v ∥ b
컴팩트성이 유한차원에서만 성립 하므로, 무한차원에서는 이 논증이 무너집니다.
심화 2. 유도 노름의 계산 공식을 증명하세요.
풀이. 문제 3에서 제시한 공식을 유도합니다.
∥ A ∥ 1 = j ∑ i ∣ a i j ∣ ∥ A ∥ 1 = max j ∑ i ∣ a i j ∣
상한. x x
∥ A x ∥ 1 = ∥ ∑ j x j a j ∥ 1 ≤ ∑ j ∣ x j ∣ ∥ a j ∥ 1 ≤ ( j ∥ a j ∥ 1 ) ∥ x ∥ 1 ∥ A x ∥ 1 = ∥ ∥ ∥ ∥ ∥ ∥ j ∑ x j a j ∥ ∥ ∥ ∥ ∥ ∥ 1 ≤ j ∑ ∣ x j ∣ ∥ a j ∥ 1 ≤ ( j max ∥ a j ∥ 1 ) ∥ x ∥ 1
달성. 최대인 열의 인덱스를 j ∗ j ∗ x = e j ∗ x = e j ∗
∥ A ∥ ∞ = i ∑ j ∣ a i j ∣ ∥ A ∥ ∞ = max i ∑ j ∣ a i j ∣
상한. i i
∣ ∑ j a i j x j ∣ ≤ ∑ j ∣ a i j ∣ ∣ x j ∣ ≤ ( ∑ j ∣ a i j ∣ ) ∥ x ∥ ∞ ∣ ∣ ∣ ∣ ∣ ∣ j ∑ a i j x j ∣ ∣ ∣ ∣ ∣ ∣ ≤ j ∑ ∣ a i j ∣ ∣ x j ∣ ≤ ( j ∑ ∣ a i j ∣ ) ∥ x ∥ ∞
달성. 최대인 행 i ∗ i ∗ x j = sgn ( a i ∗ j ) x j = s g n ( a i ∗ j ) ∥ x ∥ ∞ = 1 ∥ x ∥ ∞ = 1
∥ A ∥ 2 = σ 1 ∥ A ∥ 2 = σ 1
∥ A x ∥ 2 = x ⊤ A ⊤ A x ≤ λ max ( A ⊤ A ) ∥ x ∥ 2 = σ 1 2 ∥ x ∥ 2 ∥ A x ∥ 2 = x ⊤ A ⊤ A x ≤ λ m a x ( A ⊤ A ) ∥ x ∥ 2 = σ 1 2 ∥ x ∥ 2
등호는 x = v 1 x = v 1 입니다.
전치와의 관계 도 정리합니다.
노름
∥ A ⊤ ∥ ∥ A ⊤ ∥
\lVert\cdot\rVert_
\lVert A\rVert_
\lVert\cdot\rVert_
\lVert A\rVert_
\lVert\cdot\rVert_
\lVert A\rVert_
\lVert\cdot\rVert_
\lVert A\rVert_
첫 두 줄이 서로 바뀝니다. 행과 열이 뒤집히기 때문입니다. 셋째 줄은 88강에서 A A A ⊤ A ⊤
유용한 부등식 도 있습니다.
∥ A ∥ 2 ≤ ∥ A ∥ 1 ∥ A ∥ ∞ ∥ A ∥ 2 ≤ ∥ A ∥ 1 ∥ A ∥ ∞
싼 두 노름으로 비싼 것의 상한 을 얻습니다. SVD 없이 ∥ A ∥ 2 ∥ A ∥ 2 A A 6 ⋅ 7 = 6.48 6 ⋅ 7 = 6 . 4 8 ∥ A ∥ 2 = 5.12 ∥ A ∥ 2 = 5 . 1 2
심화 3. 노름 선택이 최적화에서 어떤 차이를 내는지 논하세요.
풀이. 82강 문제 1에서 세 기준을 나열했습니다. 노름의 언어로 다시 봅니다.
x ∥ A x − b ∥ p x min ∥ A x − b ∥ p
p p 이름
성질
2 2 최소제곱
닫힌 해, 이상치에 민감
1 1 최소절대편차
선형계획, 강건
∞ ∞ 체비셰프
선형계획, 최악 관리
p = 2 p = 2
왜 ℓ 1 ℓ 1 손실함수의 기울기를 봅니다.
손실
큰 잔차에서의 기울기
r^
2 r 2 r
$\lvert r\rvert $
± 1 ± 1
제곱은 큰 잔차에 무한정 끌려가고 절댓값은 그렇지 않습니다. 이상치 하나가 답을 통째로 옮기는 것을 막습니다.
정칙화에서도 노름 선택이 중요합니다.
min ∥ A x − b ∥ 2 2 + λ ∥ x ∥ p p min ∥ A x − b ∥ 2 2 + λ ∥ x ∥ p p
p p 이름
효과
2 2 능형
계수를 줄입니다
1 1 라소
계수를 0 0
왜 ℓ 1 ℓ 1 문제 1에서 본 단위구의 모양 때문입니다.
ℓ 1 의 단위구는 마름모 ℓ 1 의 단위구는 마름모
꼭짓점이 축 위에 있고 뾰족합니다. 제약 집합과 손실 등고선이 만나는 점이 꼭짓점이 되기 쉬우며, 그 점에서는 성분 일부가 정확히 0 0
ℓ 2 ℓ 2 0 0
모서리가 있으면 희소해집니다 모서리가 있으면 희소해집니다
82강 심화 2에서 라소를 언급 했는데, 그 기하적 이유가 이것입니다.
신경망에서도 노름이 선택 사항입니다.
용도
흔한 노름
회귀 손실
\ell^
강건 회귀
후버 (둘의 절충)
가중치 감쇠
\ell^
희소화
\ell^
그래디언트 클리핑
\ell^
둘째 줄의 후버 손실 은 작은 잔차에 제곱, 큰 잔차에 절댓값을 씁니다. 미분 가능하면서 강건합니다.
심화 4. 조건수의 예고로 오차 전파를 다루세요.
풀이. 문제 4의 부등식이 무엇에 쓰이는지 봅니다.
정방향 전파. y = A x y = A x
∥ Δ y ∥ = ∥ A Δ x ∥ ≤ ∥ A ∥ ∥ Δ x ∥ ∥ Δ y ∥ = ∥ A Δ x ∥ ≤ ∥ A ∥ ∥ Δ x ∥
상대오차로 바꿉니다.
∥ Δ y ∥ ∥ y ∥ ≤ ∥ A ∥ ∥ Δ x ∥ ∥ y ∥ = ∥ A ∥ ∥ x ∥ ∥ y ∥ ⋅ ∥ Δ x ∥ ∥ x ∥ ∥ y ∥ ∥ Δ y ∥ ≤ ∥ A ∥ ∥ y ∥ ∥ Δ x ∥ = ∥ A ∥ ∥ y ∥ ∥ x ∥ ⋅ ∥ x ∥ ∥ Δ x ∥
∥ x ∥ = ∥ A − 1 y ∥ ≤ ∥ A − 1 ∥ ∥ y ∥ ∥ x ∥ = ∥ A − 1 y ∥ ≤ ∥ A − 1 ∥ ∥ y ∥
∥ Δ y ∥ ∥ y ∥ ≤ ∥ A ∥ ∥ A − 1 ∥ ⏟ κ ( A ) ⋅ ∥ Δ x ∥ ∥ x ∥ ∥ y ∥ ∥ Δ y ∥ ≤ κ ( A ) ∥ A ∥ ∥ A − 1 ∥ ⋅ ∥ x ∥ ∥ Δ x ∥
조건수가 나타났습니다. 91강의 주제이며, 여기서 정의만 봅니다.
κ ( A ) = ∥ A ∥ ∥ A − 1 ∥ κ ( A ) = ∥ A ∥ ∥ A − 1 ∥
ℓ 2 ℓ 2
∥ A ∥ 2 = σ 1 , ∥ A − 1 ∥ 2 = 1 σ n ⟹ κ 2 ( A ) = σ 1 σ n ∥ A ∥ 2 = σ 1 , ∥ A − 1 ∥ 2 = σ n 1 ⟹ κ 2 ( A ) = σ n σ 1
88강 문제 5에서 쓴 식 이 여기서 유도됩니다.
둘째 줄의 근거 는 A − 1 = V Σ − 1 U ⊤ A − 1 = V Σ − 1 U ⊤ Σ − 1 Σ − 1 1 / σ n 1 / σ n
**언제나 κ ≥ 1 κ ≥ 1
1 = ∥ I ∥ = ∥ A A − 1 ∥ ≤ ∥ A ∥ ∥ A − 1 ∥ = κ ( A ) 1 = ∥ I ∥ = ∥ A A − 1 ∥ ≤ ∥ A ∥ ∥ A − 1 ∥ = κ ( A )
준곱셈성을 썼습니다. 등호는 직교행렬일 때이며, 75강 심화 4에서 κ ( Q ) = 1 κ ( Q ) = 1
노름마다 조건수가 다릅니다.
노름
표기
\ell^
\kappa_
\ell^
\kappa_{2}=\sigma_{1}/\sigma_
\ell^
\kappa_
동치성 때문에 서로 n n 로 다릅니다. 그래서 "조건수가 크다"는 판단은 노름과 무관하지만, 정확한 값은 다릅니다.
실무에서는 κ 1 κ 1 ∥ A − 1 ∥ 1 ∥ A − 1 ∥ 1 O ( n 2 ) O ( n 2 ) κ 2 κ 2
심화 5. 노름이 나타나는 자리를 정리하세요.
풀이. 이 개념이 어디서 쓰이는지 봅니다.
최적화의 손실. 심화 3에서 다뤘습니다.
수렴 판정. 반복법에서 ∥ x k + 1 − x k ∥ < ε ∥ x k + 1 − x k ∥ < ε 상대 기준이 나은 경우 가 많습니다.
∥ x k + 1 − x k ∥ ∥ x k ∥ < ε ∥ x k ∥ ∥ x k + 1 − x k ∥ < ε
규모가 다른 문제에서 절대 기준은 위험 합니다.
정칙화. 가중치 감쇠가 ∥ w ∥ 2 2 ∥ w ∥ 2 2
그래디언트 클리핑. 노름이 문턱을 넘으면 줄입니다.
g ← g ⋅ min ( 1 , τ ∥ g ∥ ) g ← g ⋅ min ( 1 , ∥ g ∥ τ )
방향은 유지하고 크기만 제한 합니다. 246강의 그래디언트 폭발 대응입니다.
립시츠 상수. 함수가 얼마나 급하게 변하는지 재는 양이며
∥ f ( x ) − f ( y ) ∥ ≤ L ∥ x − y ∥ ∥ f ( x ) − f ( y ) ∥ ≤ L ∥ x − y ∥
입니다. **선형사상이면 L = ∥ A ∥ L = ∥ A ∥
L ≤ ∏ ℓ ∥ W ℓ ∥ L ≤ ℓ ∏ ∥ W ℓ ∥
준곱셈성 을 쓴 것이며, 느슨하지만 계산이 쉽습니다.
저계수 근사의 오차. 88강 심화 2에서 두 노름으로 표현했습니다.
∥ A − A k ∥ 2 = σ k + 1 , ∥ A − A k ∥ F = ∑ i > k σ i 2 ∥ A − A k ∥ 2 = σ k + 1 , ∥ A − A k ∥ F = i > k ∑ σ i 2
어느 노름에서도 절단 SVD가 최선 이라는 것이 에카르트-영의 강한 형태입니다.
정리합니다.
분야
노름이 하는 일
최적화
손실과 정칙화
수치해석
오차와 수렴 판정
학습
클리핑, 감쇠
이론
립시츠 상수, 근사 오차
심화 6. 07단원 전체를 예고하세요.
풀이. 이 단원이 무엇을 하는지 정리합니다.
이 과목 내내 경고가 반복됐습니다.
강의
경고
45
파국적 상쇄
67
피벗팅 없으면 무너집니다
69
역행렬로 풀지 마세요
78
행렬식이 넘칩니다
80
고전 그람슈미트가 불안정합니다
81
정규방정식이 조건수를 제곱합니다
85
대각화가 위험할 수 있습니다
88
A ⊤ A A ⊤ A
여덟 번의 경고에 공통된 것 이 있습니다. 수학적으로 옳은 식이 부동소수점에서 무너진다 는 것입니다.
07단원이 그 현상을 정리합니다.
강의
내용
90 (이 강의)
크기를 재는 도구
91
조건수와 오차 증폭
92
부동소수점의 실제 규칙
91강이 핵심 입니다. 67강 심화 6에서 "안정성은 알고리즘의 성질이고 조건은 문제의 성질"이라 구별했는데, 그것을 정확히 정의하고 증명합니다.
출력 상대오차 입력 상대오차 ≤ κ ( A ) 입력 상대오차 출력 상대오차 ≤ κ ( A )
92강은 하드웨어 를 다룹니다. 부동소수점이 실수를 어떻게 표현하고, 어디서 정보가 사라지며, 어떤 코딩 습관이 그것을 피하는지 봅니다.
이 단원이 끝나면 S4가 완결됩니다 이 단원이 끝나면 S4 가 완결됩니다
62강에서 벡터를 정의하고 시작해, 행렬을 변환으로 읽고, 공간과 좌표를 세우고, 분해로 계산하고, 마지막에 그 계산이 얼마나 믿을 만한지 재는 데까지 왔습니다.
이 강의에서는 numpy만 씁니다. 세 벡터 노름과 극한을 확인하고, 유도 노름의 공식을 표본으로 검증하며, 스펙트럼 반지름과 노름이 다른 경우를 봅니다.
import numpy as np
# --- 문제 1: 세 벡터 노름과 p 의 극한 -----------------------------------
v = np.array([3.,-4.,12.])
print("%.8f %.8f %.8f" % (np.abs(v).sum(), np.linalg.norm(v), np.abs(v).max()))
# 19.00000000 13.00000000 12.00000000
for p in [1,2,4,8,32,128]:
print(p, "%.8f" % float(np.sum(np.abs(v)**p)**(1/p)))
# 1 19.00000000
# 2 13.00000000
# 4 12.04846143
# 8 12.00025149
# 32 12.00000000
# 128 12.00000000 <- 최댓값으로 수렴합니다
# --- 문제 2: 노름 동치성의 상수 ------------------------------------------
rng = np.random.default_rng(81)
n = 6
X = rng.standard_normal((5000,n))
r1 = np.abs(X).sum(axis=1); r2 = np.linalg.norm(X,axis=1); ri = np.abs(X).max(axis=1)
print("%.6f %.6f" % ((r2/r1).min(), (r2/r1).max()),
"%.6f %.6f" % (1/np.sqrt(n), 1.0))
# 0.410780 0.804342 0.408248 1.000000
print("%.6f %.6f" % ((ri/r2).min(), (ri/r2).max()),
"%.6f %.6f" % (1/np.sqrt(n), 1.0))
# 0.465581 0.989490 0.408248 1.000000 (이론 범위 안에 있습니다)
# --- 문제 3: 유도 노름의 공식 -------------------------------------------
A = np.array([[1.,2.],[3.,-4.]])
print("%.8f %.8f" % (np.linalg.norm(A,1), np.abs(A).sum(axis=0).max()))
# 6.00000000 6.00000000 (열 합의 최댓값)
print("%.8f %.8f" % (np.linalg.norm(A,np.inf), np.abs(A).sum(axis=1).max()))
# 7.00000000 7.00000000 (행 합의 최댓값)
s = np.linalg.svd(A, compute_uv=False)
print("%.8f %.8f" % (np.linalg.norm(A,2), s[0]))
# 5.11667274 5.11667274
print("%.8f %.8f" % (np.linalg.norm(A,'fro'), np.sqrt(np.sum(s**2))))
# 5.47722558 5.47722558
T = rng.standard_normal((200000,2)) # 단위원에서 최대 늘임
T = T/np.linalg.norm(T,axis=1,keepdims=True)
print("%.6f %.6f" % (np.linalg.norm(T@A.T,axis=1).max(), s[0]))
# 5.116673 5.116673
# --- 문제 4: 부등식 -----------------------------------------------------
B = rng.standard_normal((4,4)); C = rng.standard_normal((4,4))
x = rng.standard_normal(4)
print("%.6f %.6f" % (np.linalg.norm(B@x), np.linalg.norm(B,2)*np.linalg.norm(x)))
# 2.580921 6.042044 (일관성)
print("%.6f %.6f" % (np.linalg.norm(B@C,2), np.linalg.norm(B,2)*np.linalg.norm(C,2)))
# 3.894395 5.510624 (준곱셈성)
print("%.6f %.6f" % (np.linalg.norm(B,2), np.linalg.norm(B,'fro')))
# 2.599891 3.193091
print("%.6f %.6f" % (np.linalg.norm(B,'fro'), np.sqrt(4)*np.linalg.norm(B,2)))
# 3.193091 5.199782
# --- 문제 5: 스펙트럼 반지름은 노름이 아닙니다 --------------------------
N = np.array([[0.,5.],[0.,0.]]) # 멱영
print("%.6f %.6f" % (max(abs(np.linalg.eigvals(N))), np.linalg.norm(N,2)))
# 0.000000 5.000000 <- 완전히 다릅니다
S = np.array([[4.,1.],[1.,3.]]) # 대칭
print("%.6f %.6f" % (max(abs(np.linalg.eigvalsh(S))), np.linalg.norm(S,2)))
# 4.618034 4.618034 <- 같습니다
M = np.array([[0.,0.9],[0.9,0.]]) # 대칭, rho = 0.9
rho = max(abs(np.linalg.eigvals(M)))
for k in [1,5,20,60]:
print(k, "%.8f %.8f" % (np.linalg.norm(np.linalg.matrix_power(M,k),2), rho**k))
# 1 0.90000000 0.90000000
# 5 0.59049000 0.59049000
# 20 0.12157665 0.12157665
# 60 0.00179701 0.00179701
G = np.array([[0.5,10.],[0.,0.5]]) # 결손, rho = 0.5
rg = max(abs(np.linalg.eigvals(G)))
for k in [1,3,10,40]:
print(k, "%.4e %.4e" % (np.linalg.norm(np.linalg.matrix_power(G,k),2), rg**k))
# 1 1.0025e+01 5.0000e-01
# 3 7.5021e+00 1.2500e-01
# 10 1.9532e-01 9.7656e-04
# 40 7.2760e-10 9.0949e-13 <- 40 번 뒤에도 800 배 차이가 납니다
# --- 심화: 겔판트 공식은 천천히 수렴합니다 ------------------------------
for k in [1,5,20,80,200]:
nk = np.linalg.norm(np.linalg.matrix_power(G,k),2)
print(k, "%.8f %.8f" % (nk**(1/k), rg))
# 1 10.02493781 0.50000000
# 5 1.25596833 0.50000000
# 20 0.67464163 0.50000000
# 80 0.54830412 0.50000000
# 200 0.52117108 0.50000000
실행하면 주석과 같은 값이 나옵니다. 다섯 곳을 짚어 둡니다.
첫째, 같은 벡터의 크기가 19 1 9 13 1 3 12 1 2 p p p = 32 p = 3 2 12 1 2
둘째, 노름 비의 표본 범위가 이론값 [ 1 / 6 , 1 ] = [ 0.408 , 1 ] [ 1 / 6 , 1 ] = [ 0 . 4 0 8 , 1 ] 0.99 0 . 9 9 모든 성분의 절댓값이 같아야 하한이 달성되므로 무작위로는 잘 나오지 않습니다.
셋째, 유도 노름의 공식이 정확히 맞습니다. ∥ A ∥ 1 = 6 ∥ A ∥ 1 = 6 ∥ A ∥ ∞ = 7 ∥ A ∥ ∞ = 7 20 2 0 σ 1 σ 1
넷째, 세 부등식이 모두 성립합니다. 일관성에서 2.58 ≤ 6.04 2 . 5 8 ≤ 6 . 0 4 x x v 1 v 1
다섯째가 이 강의의 핵심 경고입니다. 멱영행렬에서 **스펙트럼 반지름이 0 0 5 5 G G k = 40 k = 4 0 ρ k ρ k 800 8 0 0 ρ < 1 ρ < 1
겔판트 공식의 수렴도 느립니다. k = 200 k = 2 0 0 0.521 0 . 5 2 1 ρ = 0.5 ρ = 0 . 5
코드로 할 수 없는 일도 분명히 해 둡니다. 유도 노름의 공식은 표본으로 증명되지 않습니다. 20 2 0 σ 1 σ 1 표본이 범위 안에 있음을 확인한 것 이지 상수가 최선임을 증명한 것이 아닙니다.
세 벡터 노름을 쓰세요.
p → ∞ p → ∞ 노름의 세 공리를 쓰세요.
내적에서 온 노름의 특징을 쓰세요.
유도 노름의 정의를 쓰세요.
∥ A ∥ 1 ∥ A ∥ 1 ∥ A ∥ ∞ ∥ A ∥ ∞ 프로베니우스 노름이 유도가 아닌 증거를 쓰세요.
일관성과 준곱셈성을 쓰세요.
스펙트럼 반지름과 노름의 관계를 쓰세요.
ρ < 1 ρ < 1
정답.
절댓값의 합, 제곱합의 제곱근, 절댓값의 최댓값입니다.
최댓값이며 가장 큰 성분이 지수적으로 지배하기 때문입니다.
양정치성, 동차성, 삼각부등식입니다.
평행사변형 법칙을 만족합니다.
단위벡터를 가장 많이 늘이는 배율입니다.
각각 열과 행의 절댓값 합의 최댓값입니다.
∥ I n ∥ F = n ≠ 1 ∥ I n ∥ F = n = 1 ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥ ∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥ ρ ( A ) ≤ ∥ A ∥ ρ ( A ) ≤ ∥ A ∥ 결손이거나 비정규이면 초기에 크게 부풀 수 있습니다.
기호
읽는 법
뜻
\lVert\mathbf{v}\rVert_
p p ( ∑ ∣ v i ∣ p ) 1 / p ( ∑ ∣ v i ∣ p ) 1 / p
\lVert A\rVert_
유도 노름
최대 늘임 배율입니다
\lVert A\rVert_
프로베니우스
성분의 ℓ 2 ℓ 2
ρ ( A ) ρ ( A ) 스펙트럼 반지름
고유값 크기의 최댓값입니다
일관성
consistency
∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥ ∥ A x ∥ ≤ ∥ A ∥ ∥ x ∥
준곱셈성
submultiplicativity
∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥ ∥ A B ∥ ≤ ∥ A ∥ ∥ B ∥
겔판트 공식
Gelfand
∥ A k ∥ 1 / k → ρ ∥ A k ∥ 1 / k → ρ
립시츠 상수
Lipschitz
변화율의 상한입니다
다음 91강에서는 조건수 를 정면으로 다룹니다. 심화 4에서 유도만 해 두었는데, 그 정의와 성질을 세우고 오차가 왜 그만큼 증폭되는지 증명 합니다. 67강 심화 6에서 구별한 "문제의 조건"과 "알고리즘의 안정성"이 여기서 정확한 뜻을 얻습니다.