1.1 연립 선형 대수 방정식 Intro

글을 썼는데 크롬 Alert Control 확장 툴 때문에 글이 안떠서 당황했다가 글을 날려버렸다. :(

1. 표기법

대수에서 연립방정식은 다음과 같다. 

$$ A_{11}x_1 + A_{12}x_2 + \cdots +A_{1n}x_n = b_1\\
A_{21}x_1 + A_{22}x_2 + \cdots +A_{2n}x_n = b_2\\
\vdots \\
A_{n1}x_1 + A_{n2}x_2 + \cdots +A_{nn}x_n = b_n $$

여기에서 계수 \(A_{ij} \) 와 상수 \(b_j \)는 known이고, \(x_i\)는 미지수이다. 

행렬 표기법으로 나타내면 아래와 같다. 

 

$$ \begin{bmatrix}
A_{11} & A_{12} & \cdots & A_{1n} \\
\vdots & \vdots & \ddots & \vdots \\
A_{n1} & A_{n2} & \cdots & A_{nn}
\end{bmatrix}

\begin{bmatrix}
x_1 \\ \vdots \\ x_n
\end{bmatrix}
=
\begin{bmatrix}
b_1 \\ \vdots \\ b_n
\end{bmatrix} $$ 

행렬 계산에 용이하게 하기 위해, 위 행렬식의 계수 행렬 A에 상수 벡터 b를 인접시키면 증대된 계수 행렬 augmented coefficient matrix 이 된다.

$$  [ \;A\;|\;b\;] =
\left[
  \begin{matrix}
    A_{11} & \cdots & A_{1n} \\
    \vdots & \ddots & \vdots \\
    A_{n1} & \cdots & A_{nn}
  \end{matrix}
  \left|
    \,
    \begin{matrix}
      b_1  \\
      \vdots  \\
      b_3  \\
    \end{matrix}
  \right.
\right] $$

2. 해의 유일성

n개의 미지수를 가진 n 선형 연립방정식은 계수 행렬의 행렬식 determinant이 0이 아니어서 ( \( |A|  \neq 0 \) 가역행렬 nonsingular (=역행렬을 가지는 행렬)일 때, 고유한 해 unique solution 을 가진다. 

※ 가역행렬 nonsingular 의 행과 열은 선형 독립적 linear independent 이다.

<IFF>  가역행렬의 어떠한 행과 열도 다른 행 또는 열들의 선형 조합 linear combination에 의해 생성되지 않는다. 

 

만약 계수 행렬의 행렬식이 0이라면 ( \( |A|  = 0 \) 특이 행렬 singular 이고, 이 경우 방정식은 상수 벡터 b에 따라 무한한 수의 해를 가지거나 아예 없다. 

예시 ) 무한한 해를 가지는 경우

$$ 2x+y = 3 \quad 4x+2y = 6 $$ 이 방정식들이 있을 때, augmented coefficient는 아래로 만들 수 있다.

$$  [ \;A\;|\;b\;] =
\left[
  \begin{matrix}
    2 & 1 \\
    4 & 2
  \end{matrix}
  \left|
    \,
    \begin{matrix}
      3  \\
      6
    \end{matrix}
  \right.
\right] $$ 

여기에서 계수 행렬 A만 보면, determinant |A| 값은 0이기 때문에 행렬 A는 singular이다. 

linear combination에 의해 한 행 또는 열이 다른 행 또는 열에 의해 생성될 수 있고, 1행과 2행의 관계에서 확인할 수 있다.

1행에 2를 곱한 것이 2행이다. 상수 벡터를 반영해 방정식으로 보자. 첫번째 방정식에 2를 곱하면 두번째 방정식이 된다. 이는 두 방정식이 동일한 방정식이라는 뜻이고, 하나의 방정식에 대해 방정식의 해 solution (x, y)의 조합은 무한하게 존재하게 된다.

예시) 해가 없는 경우

$$ 2x+y = 3 \quad 4x+2y = 0 $$ 

$$  [ \;A\;|\;b\;] =
\left[
  \begin{matrix}
    2 & 1 \\
    4 & 2
  \end{matrix}
  \left|
    \,
    \begin{matrix}
      3  \\
      0
    \end{matrix}
  \right.
\right] $$ 

이전 예시에서와 비슷하게 진행될 수 있다. 

1. |A| == 0이기 때문에 계수 행렬 A는 singular이다

2. singular는 linear independent하지 못하기 때문에 구성하는 행 또는 열이 linear combination에 의해 생성된다. 

3. 이전의 예시처럼 무한한 해를 가지려면 linear combination 관계가 성립하는 계수 행에 대해 상수 벡터의 요소도 linear independent하지 않아야 한다.

4. 그러나 본 예시의 상수 벡터는 linear independent하기 때문에 방정식의 해는 존재하지 않는다. 

쉽게 말하면, 두번째 방정식을 2로 나누었을때 \( 2x+y=0 \)으로 첫번째 방정식 \(2x+y=3 \)과 모순되기 때문에 해가 없다. 

 

→ 행렬식 determinant를 계산하면 계수 행렬의 singular / nonsingular 여부를 판별할 수 있다

→ 연립방정식 해의 개수가 무한한지 / 하나인지 / 없는지 알 수 있다.

3. 불량 조건 III conditioning

계수 행렬이 singular일때 우리가 문제를 해결하고자 할 때 뭔 일이 발생하는지 궁금할 수 있다. 뭐 해의 개수가 어떤지 알 수는 있지만, 뭔가 직접적으로 느낌이 오지는 않으니까. 

앞선 해의 유일성을 이야기할 때, 해가 없는지 알려면 행렬식 determinant가 작은지 확인해야 했다.

근데 이게 얼마나 작은지 어떻게 알까? 컴퓨터로 계산하면 0에 가까운 수는 얻을 수 있지만 완전무결 0은 얻기 어려우니까 .

얼마나 작은지 판별하기 위한 기준점이 norm(기호로는 ||A|| )이다. 

 

- 유클리드 norm은 원소 하나하나를 제곱한 것을 다 더해서 루트를 씌운 것이다.

- row-sum norm은 한 행에서 원소의 절댓값을 다 더했을 때, 모든 행 중에서 합이 가장 큰 행의 값을 고른 것이다. 

 

각각으로 구한 norm이 행렬식보다 큰 경우에 determinant가 작다고 말할 수 있다.

$$ | A | \;<< \; ||A|| $$

 

또, 갑자기 새로운 친구가 나오는데 그 이름은 행렬 조건수 matrix condition number 이다. 

$$ cond( \bf A) = || A || \; ||A^{-1}|| $$ 

A의 norm 값과 A 역행렬의 norm 값이 유사해 1에 가까운 숫자가 나오면, 이 행렬 A는 잘 컨디셔닝 되었다 고 말한다.

이쯤되면 느낌이 오겠지만, 행렬 A가 singular 라면 무한대에 가까운 숫자가 나온다. 

 

이렇게 matrix condition number으로 행렬의 컨디션을 파악할 수 있다. 그래서 어떻게 쓰냐고? 예시로 알아보자.

예시) 컨디셔닝으로 알아보는 해의 신뢰성

$$ 2x +y = 3 \quad 2x+1.001y=0 $$

방정식의 해는 \( x= 1501.5, \; y=-3000 \)이다. 

\( |A| = 2*1.001 - 2*1 = 0.002 \) 으로 원소인 1.001, 2보다 훨씬 작은 것을 보아하니 이 연립 선형 방정식의 계수 행렬은 singular라고 판별된다.

 

여기에서 불량 컨디셔닝의 효과를 볼 수 있다. 

두번째 방정식의 y 계수를 1.002로 바꿔보면 해는 (x,y) = (751.5, -1500)으로 확확 바뀐다. 

y 계수의 0.001 변화 값이 해에서 100%의 변화를 가져왔다. 

=> 불량하게 컨디셔닝된 방정식의 수치 해 값은 신뢰할 수 없다. 

 

이유는 컴퓨터 연산의 구조 상 일어날 수 밖에 없는 반올림 오류가 있다. 

해를 구하기 위한 계산 과정에서 반올림 처리가 되는데 이는 계수 행렬의 작은 변화로 이어지며 예시로 본 결과가 일어난다. 

 

만약 해의 값이 잉? 이상한데 싶으면 해의 신뢰성이 있는지 확인하면 될 것이다.

앞에서 나온 matrix condition number를 일정 주기마다 구하면 좋겠지만!

모든 원소에 접근하는 것에서 보듯이 연산비용이 정말 높다. 유클리드 norm을 구하면 2차원 배열에서 \( \Theta(n^2) \)은 되겠지. 원래 행렬과 역행렬한 행렬에 대해 각각 norm을 구해야 하니 역행렬 구하는 비용도 들어갈 것으로 생각된다.

 

이렇게 matrix condition number는 일정 주기마다 계산하기에는 부담되기 때문에 원소의 크기와 행렬식 값을 비교하는 방법으로 확인해주면 좋을 것이라고 한다. 

나도 나중에 해볼 때 구현해봐야지.