제 6장: 그 외의 알고리즘들(2)

67. 연립방정식의 해를 구하는 ‘가우스 소거법’

가우스 소거법: 미지수를 하나씩 줄여 나가는 작업을 통해 연립 방정식을 푸는 알고리즘
왼쪽의 n차 연립 방정식을 행렬로 표현한 결과는 아래와 같다.

$$ a_{11}x_1+a_{12}x_2+…+a_{1n}x_n=b_1\ a_{21}x_1+a_{22}x_2+…+a_{3n}x_n=b_2\ …\ a_{n1}x_1+a_{n2}x_2+…+a_{nn}x_n=b_n\ $$

$$ A = \begin{pmatrix} a_{11} & a_{12} & … & a_{1n} \ a_{21} & a_{22} & … & a_{2n} \ … & … & … &… \ a_{n1} & a_{n2} & … & a_{nn} \end{pmatrix} \begin{pmatrix} x_1 \ x_2 \ … \ x_n \end{pmatrix} = \begin{pmatrix} b_1 \ b_2 \ … \ b_n\end{pmatrix} $$
1단계: $a_{11}$이 1이 되도록 1번째 방정식을 1/$a_{11}$배 곱한다.
- 주의: $a_{12}/a_{11}=p_{12}$, $a_{13}/a_{11}=p_{13}$, …, $a_{1n}/a_{11}=p_{1n}$, $b_{1}/a_{11}=q_{1}$로 한다.
2단계: 2 ~ $n$ 번째 방정식에 대해 다음을 계산해 $a_{1n}$~$a_{n1}$이 0이 되도록 한다.
- (2번째 방정식) - (1번째 방정식) * $a_{12}$
- …
- (2번째 방정식) - (1번째 방정식) * $a_{1n}$
위 과정을 2번째 방정식부터 3번째 방정식까지 순차적으로 반복해 나가면, 행렬 왼쪽 위에서 오른쪽 아래로 대각선 성분이 모두 1, 왼쪽의 성분이 모두 0인 행렬을 구할 수 있다(전진 소거 단계)
다음으로 후진대입을 실행
- 전진 소거에서 구한 $x_n=q_n$ 과 1단계 위의 행 m = n-1을 보면 $x_m + p_{mn}x_n=q_m$으로 되어있으므로, 이 식에 $x_n=q_n$을 대입하면 $x_m$을 구할 수 있다.

$$ \int_{a}^{b} f(x)dx $$

함수 $f(x)$ 를 구간 [a, b]에서 정적분한 값은 $f(x)$와 직선 $y=0$, 직선 $x=a$및 직선 $x=b$로 둘러싸인 부분의 면적이다.
이 부분을 y축에 평행한 선분으로 n등분했을 때 각 구간의 x축 폭을 h라고 할 경우, $h=\frac{b-a}{n}$가 된다. 이 때 n등분한 각 구간을 사다리꼴로 간주한다.
사다리꼴을 구하는 공식은 (윗 변 + 아랫 변) * 높이 / 2 → 따라서 구간 $[x_0, x_1]$부분의 면적은 $\frac{(f(x_0)+f(x_1)*h}{2}$로 구할 수 있다.
$[x_i, x_{i+1}]$부분의 면적은 $\frac{(f(x_1)+f(x_{i+1})*h}{2}$이므로 구간 [a, b]의 면적은 다음과 같이 구할 수 있다.

$\frac{(f(x_0)+f(x_{1})*h}{2}$ + $\frac{(f(x_1)+f(x_{2})*h}{2}$ + … + $\frac{(f(x_{n-1})+f(x_{n})*h}{2}$$\frac{(f(x_1)+f(x_{i+1})*h}{2}$

= $\frac{(f(x_0)+f(x_{n})*h}{2}$ + $(f(x_1) +f(x_2)+…+f(x_{n-1}))*h$

= $(\frac{(f(x_0)+f(x_{n})}{2})+(f(x_1)+f(x_2)+…+f(x_{n-1}))*\frac{b-a}{n}$