[수치해석] Introduction

수치해석은 많은 공학 분야에 사용되고 있습니다.

특히 시스템을 수학적으로 모델링하는 기계공학은, 직접적으로 풀기 어려운 시스템에 대해 수치해석을 많이 사용합니다.

그래서 이번에 공부해야할 필요성을 느꼈고 수업을 들으면서 배운 내용에 대해 정리하려고 합니다.

 

교재는 Fundamentals of Engineering Numerical Anaylsis (Moin, Parviz)를 사용합니다.

 

---

1. Numerical methods

 

아무런 상황에서도 다 numerical method를 적용하는 것이 아닙니다. Directly solve하기 어려운 physics에 numerical methods를 적용합니다.

 

physics를 크게 분류하자면

1) Linear / Nonlinear

2) Steady / Unsteady - 시간에 대한 의존성

3) Ordinary / Partial  - 독립 변수의 갯수

 

세 가지 카테고리로 분류할 수 있습니다.

 

어떤 physics를 differential equations(이하 DE)으로 표현하는 것을 modeling이라고 합니다.

때때로 문제들 중에는 모델링 자체가 어려운 것들이 있습니다.

 

위에서 differential equation의 경우 nonlinear거나 partial DE는 풀 수 있는 방법이 없습니다.

그래서 numerical method를 통해 algebraic equations으로 transform해서 문제를 해결할 수 있습니다.

 

복잡한 DE를 $Ax=b$ 와 같은 algebraic equations으로 바꾼다면 $x=A^{-1}b$로 $A$ matrix의 역행렬을 취함으로써 solution을 구할 수 있습니다.

다만 $A\in \mathbb{R}^{n\times n}$ n이 크면(차원이 크면) 역행렬을 구하기 어렵습니다. 특히 역행렬을 구하는 방법 중 하나인 gaussian elimination으로 푸는 것은 매우 비효율적인 방법입니다.

 

 

---

2. A variety of numerical schemes

 

numerical analysis에서 방법을 고를 때, 신경써야 하는 parameter는 accuracy, stability, expense 세 가지입니다.

가능한 한 간단하게 algebraic equations을 유도해야 합니다.

또한 accuracy(정확도)와 cost(비용) 간의 balance가 중요합니다. accuracy가 좋다해도 cost가 크거나 cost가 적을 때는 accuracy가 낮다는 문제가 있을 수 있기 때문입니다.

 

---

3. Theory of linear algebra

 

신경써야 하는 parameter가 accuracy, stability, expense 세 가지라고 했는데 이 세 가지와 연관된 것이 시스템의 the characteristics of eigenvalues입니다.

 

 

linear algebra 이론을 알아야 하는 이유는

1) computational cost를 추정 및 조절하기 위해서입니다.

2) $x=A^{-1}b$의 계산에 필요한 solution을 구하는 technique을 개발할 때 선형대수 이론은 중요한 역할을 합니다.

3) round-off error issue를 피하는 데에 사용되며

4) stiffness를 이해하는데 필요하기 때문입니다.

 

여기서 말하는 'stiffness'는 $A^{-1}$을 계산하는 데 어려운 정도를 말합니다. The less stiff, the better.

 

* round-off error : 컴퓨터의 숫자 한계 때문에 발생하는 오차입니다. 어떤 숫자를 무한하게 표현할 수 없으니 중간에 반올림을 하면서 발생하는 오차라고 볼 수 있습니다. (truncation error는 특정 소수점 이하를 잘라내면서 생기는 오류라고 합니다.) 어떤 수치해석에서는 소수점 아래 아주 작은 숫자 때문에 발산할 수도 있습니다.

컴퓨터에서 쓰는 수 체계는 single precision과 double precision이 있는데 보통은 single precision이 float이라고도 쓰고, double precision은 double이라고 쓰는 것 같습니다. single precision은 32bit value, double precision은 64bit value이기 때문에 double precision이 더 많은 숫자를 표현할 수 있습니다.

 

 

• matrix - matrix multiplication

 

$A\in \mathbb{R}^{m\times n} \cdot B\in \mathbb{R}^{n\times l}=C\in \mathbb{R}^{m\times l}$

$\text{Let column of B be denoted }B=\begin{bmatrix} \underline{b^{1}}&\underline{b^{2}}&\cdots&\underline{b^{l}}\end{bmatrix}$

$\text{then }A\cdot B=\begin{bmatrix}A\underline{b^{1}}&A\underline{b^{2}}&\cdots &A\underline{b^{l}}\end{bmatrix}$

 

$A$ matrix와 $B$ matrix의 column의 곱을 총 $l$번 진행합니다.

$Ab$에서 계산이 몇 번 일어나는 지 알면 그 값에 $l$을 곱한 것이 총 계산 operation 횟수입니다.

 

 

• operation count of $A\cdot b$

 

$\begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & \ddots  &  & \\ \vdots &  &  & \\ a_{m1} &  &  & a_{mn}\end{bmatrix}\begin{bmatrix}b_{1}\\
b_{2}\\ \vdots\\ b_{n}\end{bmatrix}$

 

여기서 존재하는 operation

1) multiplication : A의 row elemnt와 b column element의 곱은 $n$번($a_{11}b_{1}, \ldots, a_{1n}b_{n}$)

2) addition : element의 곱을 더하는 것 $n-1$번

3) m개 row이므로 1), 2) 과정을 m번 반복 : $n\times m + (n-1)\times m$

 

그리고 1),2),3) 과정을 $l$번 수행하므로 $(2n-1)\times m \times l$번의 operation이 발생합니다.

 

만약 multiplication과 addition의 cost가 동일하다면 total operation count를 $\approx O(n^{3})$이라고 합니다.

$n$의 지수는 order를 의미하며, $n$ 앞에 coefficient가 존재할 수 있습니다. $2n^{3}$

order가 3은 일반적으로 cost가 크다고 봅니다. 즉 우리가 원하는 order는 그보다 작은 1,2 정도가 될 것입니다.

 

 

• CPU Time

 

만약 위의 예에서 $n=5000$이라고 하면, $n^{3}=1.25 \times 10^{11}$

 

*FLOPS : floating point operation per second

 

1) Intel Pentium (586) ~ 1MFLOPS

operation을 하는데 걸리는 시간 $t=1.25\times 10^{11}/10^{6}=34.7]text{(hrs)}$

 

2) Intel Core i7 ~ 25GFLOPS

$t=\frac{1.25\times 10^{11}}{25\times 10^{9}}=0.05\times 10^{2}=5\text{(s)}$

 

3) Intel Xeon (E5500) ~ 100GFLOPS

$t=1.25\text{(s)}$

 

 

최근에는 CPU 성능이 아주 좋아져서 빠른 속도로도 계산을 수행할 수 있게 되었습니다.

 

---

수치해석 fortran, c언어 교재

 

s3.amazonaws.com/nrbook.com/book_C210.html

http://s3.amazonaws.com/nrbook.com/book_C210.html