2021년 3월 4일 목요일

행렬 노름과 조건수(Matrix Norm and Condition Number)

[경고] 아래 글을 읽지 않고 "행렬 노름과 조건수"를 보면 바보로 느껴질 수 있습니다.


[그림 1] 3차원에서 정의한 유클리드 거리(출처: wikipedia.org)

벡터(vector) $\bar r$의 크기 $|\bar r|$은 유클리드 거리(Euclidean distance) 혹은 피타고라스 거리(Pythagorean distance)를 이용하여 정의한다. 유클리드 거리는 피타고라스의 정리(Pythagorean theorem)를 [그림 1]처럼 연속적으로 적용해서 만든다.

                  (1)

피타고라스의 정리가 매우 오래 되었기 때문에, 유클리드 거리의 역사도 길다고 오해할지 모른다. 하지만 벡터에는 좌표계(coordinate system)라는 개념이 꼭 필요하므로, 식 (1)과 같은 정의는 데카르트René Descartes(1596–1650)데카르트 좌표계(Cartesian coordinate system)를 발명한 1637년데카르트 41세, 조선 인조 시절 이후에나 등장한다. 우리가 현실에서 보는 좌표계는 2차원 혹은 3차원이라서 식 (1)의 정의만 사용해도 충분하다. 하지만 수학자들의 상상력은 끝이 없어서 식 (1)을 $n$차원 유클리드 거리까지 확장한다.

                  (2)

$n$차원 벡터 공간에 사용되는 식 (2)는 현실 세계의 자유로운 확장이다. 그래서 기하학에 바탕을 둔 유클리드 거리 이외에 다양한 거리 개념을 만들 수 있다. 수학에서는 유클리드 거리를 일반화해서 계량하는 함수를 노름(norm)이라 한다. 이 노름의 치역은 음이 아닌 실수로 정의한다. 노름의 어원은 표준을 뜻하는 라틴어 노르마(norma)이다. 그래서 노름 대신에 규준(規準)이란 용어를 쓰기도 한다. 노름 개념이 벡터에 쓰이면 벡터 노름(vector norm), 행렬까지 확장하면 행렬 노름(matrix norm)이라 한다. 노름은 거리를 일반화하기 때문에 표기법도 유클리드 거리와는 달라진다. 예를 들어, 식 (2)로 정의한 유클리드 거리는 벡터 노름의 일종이라서 다음처럼 유클리드 노름(Euclidean norm)으로 표현할 수 있다.

                  (3)

제곱과 제곱근을 사용한 유클리드 노름을 더 일반화해서 정의한 $p$-노름($p$-norm)도 있다.

                  (4)

차수 $p$가 계속 커지면, 좌표 성분중에서 큰 값이 우세해진다. 그래서 최대 노름(maximum norm) 혹은 무한대 노름(infinity norm)을 다음처럼 정의한다.

                  (5)

$p$-노름의 차수를 $1$로 선택하면 절대값으로 계산하는 택시 노름(taxicab norm)을 얻는다.

                  (6)

사각형으로 도시 계획된 도로를 지나는 택시의 이동 거리와 비슷하다고 해서 식 (6)을 택시 노름이라 부른다. 택시 노름 대신 사각형 도로로 유명한 맨해튼의 거리에 빗대서 맨해튼 노름(Manhattan norm)이라고도 한다.
벡터 노름은 유클리드 거리를 유추해서 손쉽게 정의할 수 있지만, 행렬 노름의 정의에는 수준이 다른 고민이 숨어있다. 왜냐하면 행렬은 행과 열에 모두 원소가 있기 때문에 단순히 벡터 노름을 변형해서 정의하기 어렵다. 그래서 연립 방정식 ${\bf Ax}$ = $\bf b$에 등장하는 행렬의 곱 ${\bf Ax}$를 이용해서 행렬을 벡터로 바꾼 후 행렬 노름을 다음처럼 멋드러지게 정의한다.

                  (7)

여기서 $\bf x$는 임의의 모든 열 벡터(column vector)이다. 열 벡터에 따라 벡터 노름 $\|{\bf Ax}\|$는 달라지므로, 행렬 $\bf A$가 $\|{\bf x}\|$를 기준으로 $\|{\bf Ax}\|$를 최대로 증폭하는 비율로써 행렬 노름 $\|{\bf A}\|$를 정의한다. 또한 행렬 노름은 벡터 노름을 바탕으로 정의하므로, $p$-노름을 강조해서 다음처럼 식 (7)을 다시 쓸 수 있다.

                  (8)

행렬 노름의 개념은 조건수(條件數, condition number) 정의에 필수적이다. 연립 방정식 ${\bf Ax}$ = $\bf b$에서 입력 열 벡터 $\bf b$의 작은 변화 $\Delta {\bf b}$에 대해, 연립 방정식을 풀어서 얻는 출력 열 벡터 $\bf x$의 변화 비율로 조건수를 정의한다. 즉, 조건수는 행렬 연산에 필연적으로 생기는 수치 계산의 오차율을 의미한다. 조건수를 엄밀히 정의하기 위해, 다음과 같은 연립 방정식의 계산 오차 $\Delta {\bf b}$와 $\Delta {\bf x}$를 고려한다.

                  (9)

여기서 불필요하게 생기는 입력 오차 $\Delta {\bf b}$에 의해 해 $\bf x$가 변하는 출력 오차를 $\Delta {\bf x}$라 한다. 식 (9)의 유도 과정을 행렬 노름으로 깔끔하게 표현한다.

                  (10)

식 (10)의 두 부등식을 나누어서 오차를 오차율로 바꾼다.

                  (11)

식 (11)에 등장한 행렬과 역행렬의 행렬 노름 곱을 행렬 $\bf A$의 조건수 ${\rm cond}({\bf A})$라 한다.

                  (12)

식 (11)에 따라 조건수 ${\rm cond}({\bf A})$는 입력 열 벡터의 변화 비율 $\| \Delta {\bf b}\|/\|  {\bf b}\|$이 행렬 $\bf A$에 의해 증폭되어 나타나는 출력 열 벡터의 변화 비율 $\| \Delta {\bf x}\|/\|  {\bf x}\|$에 대한 최대 한계를 규정한다. 다만 조건수를 정의할 때에 사용한 행렬 노름은 $p$-노름을 사용하므로, 행렬 $\bf A$가 동일하더라도 차수 $p$에 따라 조건수는 달라질 수 있다.
행렬 노름의 정의에 식 (3)에 나온 유클리드 노름을 선택할 경우는 주로 행렬의 고유치(eigenvalue)와 고유 벡터(eigenvector) 개념을 이용한다. 먼저 대칭 행렬(symmetric matrix)을 만들기 위해 행렬 노름의 제곱을 고려한다.

                  (13)

여기서 $\bf S$ = ${\bf A}^T {\bf A}$는 대칭 행렬이다. 대칭 행렬의 고유치는 실수이고 서로 다른 고유치를 가진 대칭 행렬의 고유 벡터는 서로 직교한다. 이 성질을 이용해서 행렬 곱 $\bf S x$를 직교하는 고유 벡터의 선형 결합(linear combination)으로 다시 표현한다.

                  (14)

여기서 $\alpha_i$는 선형 결합의 계수, $\lambda_i$는 고유치, $\hat {\bf x}_i$는 $\lambda_i$에 대한 단위 고유 벡터(unit eigenvector)[$|\hat {\bf x}_i|$ = $1$]이다. 식 (14)를 식 (13)에 넣어서 행렬 관계를 대수 관계로 바꾼다.

                  (15)

여기서 $r_1^2 + r_2^2 + \cdots + r_n^2$ = $1$이다. 만약 $\lambda_1$이 최대 고유치라면, $r_1^2$ = $1 - r_2^2 - \cdots - r_n^2$을 식 (15)에 대입해서 최대값을 구한다.

                  (16)

따라서 유클리드 노름으로 정의한 행렬 노름의 제곱은 ${\bf A}^T {\bf A}$의 최대 고유치 동일하다.

                  (17)

여기서 $\lambda_{\max}[{\bf A}]$는 행렬 $\bf A$의 최대 고유치이다. 고유치의 최대값은 스펙트럼 반경(spectral radius)이라고도 한다. 만약 $\bf A$가 대칭 행렬이면, 식 (17)은 다음과 같이 더욱 간략화된다.

                  (18)

따라서 대칭 행렬인 경우의 조건수는 고유치의 최대값과 최소값의 비율이다.

                  (19)

여기서 $\lambda_{\min}[{\bf A}]$는 행렬 $\bf A$의 최소 고유치이다. 식 (19)에 따라 조건수의 최소값은 당연히 $1$이다. 고유치의 최소값이 $0$이면, 조건수는 가장 나빠져서 무한대로 발산한다. 즉, 해를 구할 수 없는 조건인 행렬식이 $0$인 경우는 조건수가 무한대로 가서 해의 계산 오차가 무한히 증가한다.
행렬 $\bf A$가 대칭이 아닌 경우는 특이값 분해(singular value decomposition, SVD)를 이용한다. 유클리드 노름의 최대값은 특이값(singular value)이므로, 최대와 최소 특이값을 구해서 행렬 노름과 조건수를 명확히 정의한다.

                  (20)

                  (21)

여기서 $\sigma_{\max}[{\bf A}]$와 $\sigma_{\min}[{\bf A}]$는 각각 행렬 $\bf A$의 최대 및 최소 특이값이다.

[참고문헌]
[1] G. Strang, Linear Algebra and its Applications, 4th ed., Brooks/Cole, 2006.

[다음 읽을거리]

댓글 없음 :

댓글 쓰기

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.