04_선형방정식의 해법과 응용

1. 가우스 소거법을 이용한 선형방정식의 해법

1.1. 첨가행렬 표현

• 첨가행렬 $[A,|,b]$
  1. 선형방정식 시스템을 계수행렬 $A$, 변수벡터 $x$, 상수벡터 $b$로 나누어 $Ax=b$ 형태로 쓴다.
  2. 계수행렬 오른쪽에 상수항을 붙여 나타낸다. (계수행렬 | 상수항행렬)

1.2. 가우스-조단 소거법

• 방정식에서의 소거법은 첨가행렬의 기본 행 연산과 동치이다.

• 세 가지 기본 행 연산은

  1. 한 행에 0이 아닌 상수 곱하기
  2. 두 행 교환
  3. 한 행을 상수배하여 다른 행에 더하기

• 이 연산들로 행렬을 행 사다리꼴(또는 기약 행 사다리꼴)로 만든 뒤 역대입법으로 해를 구한다.

• 변수를 직접 소거하는 것보다 행 연산으로 처리하는 것이 결과는 같으면서 훨씬 편리하다.

1.3. 해의 종류

• 해의 종류는 세 가지로 나뉜다.
  1. 유일해를 가지는 경우,
  2. 모순(예: $0=\frac{5}{2}$)이 생겨 해가 존재하지 않는 경우,
  3. 그리고 자유변수가 생겨 무수히 많은 해를 가지는 경우이다.

(1) 해의 존재성

• (1) 해가 존재한다.

  • → 직선의 교점이 존재 (일치 또는 교점 유한개)
  1. 오직 하나 존재할 경우
     • $detA\ne 0$
  2. 해가 무수히 많이 존재할 경우 (=직선이 일치)
     • $detA=0$

• (2) 해가 존재하지 않는다.

  • → 직선의 교점이 없음, 즉 두 직선이 일치하지 않은 평행
  • $detA=0$

기울기	직선	교점	해의 존재성	행렬식
${\Delta }_1\ne {\Delta }_2$	교차	1개	유일해	$\Vert A\Vert \ne 0$
${\Delta }_1={\Delta }_2\ne \Delta c$	평행	0개	무해	$\Vert A\Vert =0$
${\Delta }_1={\Delta }_2=\Delta c$	일치	무수히 많음	무한해	$\Vert A\Vert =0$

1.4. LU분해 방법

$IA=LU$

• 정방행렬 $A$를 하부삼각행렬 $L$과 상부삼각행렬 $U$의 곱($A=LU$)으로 분해해 푸는 방법이다.

• 가우스 소거법으로 $U$를 구하고, 단위행렬 $I$에 그 연산의 역순·역연산을 적용해 $L$을 구한다.

• 풀이는 4단계로 진행된다.

  1. $Ax=b$를 $LUx=b$로 분해
  2. $Ux=y$로 치환하여 $Ly=b$로 대체
  3. $Ly=b$를 풀어 $y$를 구함 (전진대입)
  4. $Ux=y$를 풀어 $x$를 구함 (역대입)

(1) LU분해의 예

• 예: 행렬 A$A=\left(\begin{array}{ccc}1& 1& 1\\ 1& 2& 1\\ 0& -1& 2\end{array}\right)$

• 행렬 A를 상삼각행렬로 만들면서 기본행렬 얻어내기 1$E_1=\left(\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ 0& 0& 1\end{array}\right),\left(\begin{array}{ccc}1& 1& 1\\ 0& 1& 0\\ 0& -1& 2\end{array}\right)$

• 행렬 A를 상삼각행렬로 만들면서 기본행렬 얻어내기 2$E_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 1\end{array}\right),\left(\begin{array}{ccc}1& 1& 1\\ 0& 1& 0\\ 0& 0& 2\end{array}\right)$

• 상삼각행렬 구하기$U=E_2{E}_{1}A=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 1\end{array}\right)\left(\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{ccc}1& 1& 1\\ 1& 2& 1\\ 0& -1& 2\end{array}\right)$

• 하삼각행렬 구하기$L=(E_2{E}_1{)}^{-1}={\left(\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ -1& 1& 1\end{array}\right)}^{-1}=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 0& -1& 1\end{array}\right)$

1.5. 역행렬 방법

$IA=A^{-1}I$

• 행렬을 이용하여 모든 n차 연립방정식을 쉽게 풀 수 있다.

• 연립방정식을 행렬의 곱셈식으로 나타내기

  • 계수행렬 × 변수행렬 = 상수항행렬
  • $\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}p\\ q\end{array}\right)$
  • 연립방정식을 행렬의 곱으로 나타내면 AX=B꼴이다.
  • (단, $X=\left(\begin{array}{c}x\\ y\\ z\\ ⋮\end{array}\right)$는 $AX=B$의 해)

• (1) AX=B꼴

  • A가 가역 정방행렬이면, 양변의 왼쪽에 $A^{-1}$을 곱한다.

• (2) XA=B꼴

  • A가 가역 정방행렬이면, 양변의 오른쪽에 $A^{-1}$을 곱한다.

1.6. cramer 공식

• 연립일차방정식 AX=B의 해가 오직 하나 존재할 때, $|A|\ne 0$이다 .

• 이때 크래머 공식을 써서 연립방정식의 해(X)를 구할 수도 있다.

• 크래머 공식$x_1=\frac{\left|\begin{array}{ccc}{b}_1& a_{12}& a_{13}\\ b_2& a_{22}& a_{23}\\ b_3& a_{32}& a_{33}\end{array}\right|}{|A|},x_2=\frac{\left|\begin{array}{ccc}{a}_{11}& b_1& a_{13}\\ a_{21}& b_2& a_{23}\\ a_{31}& b_3& a_{33}\end{array}\right|}{|A|},x_3=\frac{\left|\begin{array}{ccc}{a}_{11}& a_{12}& b_1\\ a_{21}& a_{22}& b_2\\ a_{31}& a_{32}& b_3\end{array}\right|}{|A|}$

2. 행렬의 rank

2.1. 행 사다리꼴 만들기

• pivot

  • 행렬의 각 행에서 0이 아닌 가장 처음 나타는 수

• 행 사다리꼴(row echelon form; REF)

  • m×n 행렬 A가 기본 행 연산들을 거친 후, 다음 조건을 만족시키면 행 사다리꼴이라고 한다.
    • 한 행의 처음으로 0이 아닌 수는 반드시 1이어야 한다.
    • 인접한 두 행에서, 가장 위의 행 맨 앞의 1은 아래 행의 맨 앞 1보다 왼쪽에 있어야 한다.
    • pivot의 아래 수가 모두 0

• 기약 행 사다리꼴(reduced row echelon form; RREF)

  • 다음 조건까지를 만족시키면 기약 행 사다리꼴이라고 한다.
    • 맨 앞 성분(1)을 포함하는 열의 나머지 성분들이 0인 사다리꼴 행렬
    • pivot의 아래와 위의 수가 모두 0

2.2. 행렬의 rank

• cf. rank의 개념

  • 행렬
    • 행벡터와 열벡터의 집합
  • 선형 독립
    • 어떤 벡터를 다른 벡터들의 조합으로 표현할 수 없을 때
    • 예: (1, 0)과 (0, 1)은 선형 독립
    • 예: (1, 0)과 (2, 0)은 선형 종속
  • rank
    • 선형 독립인 벡터의 최대 개수(열 rank=행 rank)
    • 진짜 독립적인 방정식의 개수
    • rank의 증가는 확장 행렬에 새로운 독립적인 정보가 추가되었음을 의미

• 주어진 행렬에 행 연산을 하여 행 사다리꼴로 만들어나간다.

  • 다만, 모양이 완벽하지 않아도 좋다. 즉 맨 앞이 1이 아니어도 괜찮다. 모양을 보고 더 이상 (000)을 얻지 못할 것이라 생각 들 때 rank를 판단하자.

• 모두 0인 행을 제외한 나머지 행의 계수가 rank이다.

2.3. 행 연산과 rank의 관계

• $rank(A)=rank(A^T)$
• 기본 행 연산을 해도 rank에는 변화가 없다. (행 사다리꼴 만들기)

2.4. rank와 연립일차방정식의 해

• 확대행렬(첨가행렬, 확장행렬; $A|B$)

  • 행렬 A|B는 AX=B 꼴에서 행렬 A와 B를 맞닿아 붙인 모양의 행렬
  • 계수행렬과 확대행렬의 비교로 해의 존재성 파악

• 해의 존재성($AX=B$)

  • 해를 갖지 않을 조건: $rank(A)<rank(A|B)$
    • 같은 방정식이 서로 다른 상수항을 가지는 모순된 경우
  • 해를 가질 조건: $rank(A)=rank(A|B)$
    • 오직 하나의 해를 갖는다: $rank(A)=rank(A|B)=n$(변수의 개수)
    • 무수히 많은 해를 갖는다: $rank(A)=rank(A|B)<n$(변수의 개수)

2.5. 가우스 소거법

• 가우스 소거법

  • 확대행렬이 행 사다리꼴이 되도록 행 연산을 시행하는 방법

• 전향단계: pivot의 아랫부분이 0 → 행 사다리꼴 → 가우스 소거법

  1. 선행 계수 위치 찾기(0이 아닌 첫 번째 성분)
  2. 선행 계수를 1로 만들기
  3. 아래 행의 해당 열을 0으로 만들기
  4. 다음 행과 열로 이동해서 반복

• 후향단계: pivot의 윗부분까지 0 → 기약 행 사다리꼴 → 가우스-조단 소거법 5. 아래에서 위로 올라가며 선행계수 위쪽의 성분도 0으로 만들기

3. 최소제곱 해

3.1. 최소제곱 해

• 연립방정식 AX=B를 풀려면 양변의 좌측에 $A^{-1}$을 곱하여 $X=A^{-1}B$로 만들어야 한다. 그런데 $A^{-1}$을 만들기 위해서는 A가 정방행렬이어야 한다.
• 만일 A가 장방행렬이라면 A의 역행렬을 만들지 못하므로 $A^T$를 $A$와 곱하여 정방행렬로 만든 후에 역행렬을 곱해서 구한 해(X)를 최소제곱 해라고 한다.
• 즉 해를 구할 수 없으나 해가 존재한다고 간주하고 구한 해가 최소제곱 해다.
• 최소제곱 해: $\overline{X}=(A^{T}A{)}^{-1}(A^{T}B)$

3.2. 최소제곱 오차

• 최소제곱 오차
  • 참값($AX$)에서 근삿값($A\overline{X}$)을 뺀 결과
  • 오차는 $||AX-A\overline{X}||$이다.
  • 만일 AX=B로 쓴다면 오차는 $||B-A\overline{X}||$

3.3. 최소제곱 직선

• 최소제곱 직선
  • 각 점들에 가장 근접한 직선이며, 통계학에서는 회귀직선이라고도 부른다.
  • 여러 점들(데이터)에 최적화된 하나의 직선을 찾는 것이 목표다.

4. 선형방정식의 다양한 응용들

• 여러 가지 응용

  • 경제학의 레온티에프(Leontief) 투입-산출 모형(1973년 노벨 경제학상),
  • 행렬 곱을 통한 선형변환(점의 반사, 회전 — CAD/CAM의 기초),
  • 두 점을 지나는 직선의 방정식(행렬식 활용),
  • 세 꼭짓점 좌표로 삼각형 면적 구하기 등

• 화학방정식 균형 맞추기

  • 각 원소(탄소·수소·산소 등)의 개수를 벡터로 나타내고,
  • 계수 $x_1,\dots ,x_n$을 미지수로 하는 동차 선형시스템을 세워 푼다.
  • 계수는 정수여야 하므로 자유변수를 적절히 잡아 가장 작은 정수 해를 선택한다.
  • (예: $C_3{H}_8+5O_2\to 3C{O}_2+4H_{2}O$)

• 교통 흐름

  • 각 교차점에서 “유입 차량 수 = 유출 차량 수”라는 조건으로 방정식을 세운다.
  • 보통 자유변수가 생겨 무수히 많은 해를 가지며, 한 도로의 측정값을 알면 나머지가 결정된다.
  • 교통량은 음수가 될 수 없다는 현실적 제약이 추가된다.

• 마르코프 체인

  • 상태벡터의 시간에 따른 변화를 추이행렬 $P$로 모델링한다.
  • ($x(k+1)=Px(k)$)
  • 도시-교외 인구 이동 추정, 정당 지지율 변화 추정 등에 활용된다.
  • 추이행렬을 반복해서 곱하면 미래 시점의 상태를 예측할 수 있다.

• 암호 해독

  • 알파벳에 정수를 대응시켜 메시지 행렬 $B$를 만들고,
  • 약속된 행렬 $A$를 곱해 암호화($AB$)한다.
  • 수신자는 역행렬 $A^{-1}$을 곱해($A^{-1}(AB)=B$) 원래 메시지를 복원한다.

• 키르히호프 법칙

  • 전류법칙(한 점으로 들어오는 전류의 합 = 나가는 전류의 합)과
  • 전압법칙(닫힌 회로의 전압강하 합 = 기전력)으로
  • 회로의 전류·전압에 대한 선형시스템을 세워 푼다.
  • 계산 결과 전류값이 음수면 실제 흐름이 가정한 방향과 반대임을 뜻한다.

Python 실습

• NumPy로 연립방정식(solve)·최소자승(lstsq) 풀기