1. 연립일차방정식

1.1 연립일차방정식의 소개

일차방정식

정의: 일차방정식

n개의 변수 $ x_1, \dots , x_n $의 방정식이 일차(선형, linear)이다라는 것은 그것이

$$a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b$$

인 꼴로 쓸 수 있을 때이다.
여기서 $ a_i, b $는 각각 계수(coefficients), 상수항(constant term), 변수 $ x_n $를 미지수(unknowns), 부정원(indeterminants)이라고 한다.
만약 $ b = 0 $이면 그 방정식을 제차(homogeneous)라고 한다.
만약 변수에 순서를 준다면 0이 아닌 계수를 갖는 처음 변수를 선행변수(leading variable)이라고 하고, 나머지 변수를 자유 변수(free variable)이라고 한다.

결국 호모지니어스 방정식은 원점을 지나는 직선을 의미하고, 상수항이 추가됨으로써 제한 조건이 걸리는 것으로 이해할 수 있을 것이다. 이 때의 호모지니어스 방정식을 3D 공간에서의 호모지니어스 좌표계와 연관지어 생각해볼 필요가 있다.

연립일차방정식

정의 연립일차방정식

n개의 변수 $ x_n$ 에 관한 m개의 방정식으로 된 연립일차방정식이라는 것은,

$$a_{11} a_1 + a_{12} x_2 + \dots + a_{1n} x_n = b_1 \\
a_{21} a_1 + a_{22} x_2 + \dots + a_{2n} x_n = b_2 \\
\vdots \\
a_{m1} a_1 + a_{m2} x_2 + \dots + a_{mn} x_n = b_m$$

인 꼴의 m개의 일차방정식 집합이다.
a들은 계수이고, b는 상수항이다. 모든 상수항이 0이면 연립방정식을 제차라고 한다.
제차가 아닌 연립방정식과 그것에서 상수항만 0으로 만든 제차 연립방정식은 서로 대응한다고 한다.

변수의 이름과 순서를 명확히 한다면 방정식의 계수와 상수만을 행렬 형태로 표시하여 간략하게 할 수 있다. 이러한 행렬을 확대계수행렬(augmented matrix)라고 한다.

예를 들면,

$$x_1 + 2x_2 = -3 \\ 2 x_1 + 3 x_2 - 2 x_3 = -10 \\ -1 x_1 + 6 x_3 = 9 \\$$

의 확대계수 행렬은,

$$\begin{bmatrix} 1 & 2 & 0 & -3 \\ 2 & 3 & -2 & -10 \\ -1 & 0 & 6 & 9 \end{bmatrix}$$

이다.

여기서 좌측 3개 열로 이루어진 부분 행렬을 계수행렬(coefficient matrix), 우측 상수항을 나열한 하나의 열 행렬을 상수항 벡터(vector of constants) 이라고 한다.

정의 엽립방정식의 해

스칼라의 수열 $ r_1, r_2, \dots, r_n $가 연립방정식의 (특수)해라는 것은 $ x_1 = r_1, \dots, x_n = r_n $을 대입할 때 모든 방정식이 만족될 때이다. 모든 가능한 해의 집합을 해집합이라고 하고, 해집합의 임의의 기본이 되는 원소를 일반해라고 한다.

연립일차방정식은 하나의 해, 무한히 많은 해, 또흔 해를 가지지 않을 수도 있다. 만약 연립방정식이 해를 가진다면 그 연립방정식을 무모순(consistent)이다라고 하고, 그렇지 않을 경우에는 모순체계(incosistent: 해가 없다)라고 한다.

해집합

값 $ x_1 = 0, \dots, x_n = 0 $은 항상 제차방정식의 해이다. 이것을 자명(trivial)해 또는 영(zero)해라고 한다. 임의의 다른 해를 비자명(nontrivial)이라고 한다.

같은 해집합을 가지는 2개의 연립일차방정식을 동치(equivalent)이라고 한다.

연립일차방정식의 풀기

연립방정식 중 삼각형 또는 사다리꼴(echelon form)은 풀기가 가장 쉽다. 이런 형태의 연립방정식에서는, 각 방정식의 선행변수가 그것보다 위의 방정식의 선형변수의 오른쪽에 나타난다. 따라서 맨 아래에서 시작하여 위쪽으로 올라가면서 풀게 된다. 우선 마지막 식을 풀고 난 뒤에 구한 값을 그 식의 윗 식에 대입하여 푸는 식으로 반복한다. 이를 아래식-대입(back-substitution)이라고 한다.

일반적인 연립방정식을 풀기 위하여 미지수를 소거하여 사다리꼴을 갖는 동치의 연립방정식을 얻은 뒤, 위의 방버을 사용한다.

정의 식의 기본연산

연립일차방정식의 기본 연산은 소거(한 식의 상수배를 더하여 소거), 곱하기(영 아닌 상수를 한식에 곱함), 교환(두 식을 바꿈)으로 구성된다.

정의 기본행 연산(elementary row operation)

연립일차방정식에 해당하는 확대계수 행렬의 기본행 연산은 마찬가지로 소거, 곱하기 교환으로 이루어져있다.

1.2 가우스 소거법

행사다리꼴 ; 가우스 소거법

행렬에서 영으로 구성된 행을 영행(zero row), 그렇지 않은 행을 영 아닌 행(nonzero row)라고 하고, 영 아닌 행이 첫 영이 아닌 성분을 선행성분(leading entry)라고 한다. 선행성분이 1이라면 그것을 선행 1 이라고 한다.

정의 행사다리꼴

다음 조건 중,

1. 모든 영행은 그 행렬의 맨 아래에 있다.
2. 1행 이후의 각각의 영 아닌 행의 선행성분은 바로 앞 행의 선행성분의 오른쪽에 있다.
3. 임의의 영 아닌 행에서 선행성분은 1이다.
4. 선행 1의 위와 아래 열의 모든 성분은 영이다.

1, 2를 만족한다면 그 행렬을 행사다리꼴이라고 한다. 4개를 모두 만족하면 그 행령를 간소화된 행사다리꼴(in reduced row echelon form)이라고 한다.

정의 동치행렬

두 행렬이 (행)동치라는 것은 한 행렬이 다른 행렬에 유한번의 기본행 연산을 작용하여 얻어질 수 있을 때이다. 이를 $ A \sim B $ 로 쓴다.

알고리즘 가우스 소거법

가우스 소거법을 이용하여 임의의 행렬을 사다리꼴 혹은 간소화된 사다리꼴로 만들 수 있다.

1. 가장 왼쪽의 영 아닌 열을 찾는다.
2. 단계 1의 열에서 1행이 영을 가지면 같은 열의 영 아닌 성분을 가지는 행과 1행을 교환한다.
3. 맨위 행의 적당한 배수를 아래행에 더하여 선행성분 아래를 영으로 만든다.
4. 맨위 행을 두고 나머지 행에 대하여 1-3 단계를 반복한다.
5. 마지막 영 아닌 행에서 출발하여 위쪽으로 다시 위의 과정을 반복하여 선행 1위를 영으로 만든다.

위에서 1-4단계를 전진법(forward pass), 5단계를 후진법(backward pass) 혹은 아래식-대입(back-substitution)이라고 한다. 전진법에서 이미 사다리꼴이 만들어지고 5단계에서 비로소 간소화된 사다리꼴이 만들어진다.

간소화된 사다리꼴의 일의성 : 피보트

행렬은 몇개의 사다리꼴 행렬과 동치될 수 있으나, 간소화된 사다리꼴과는 단 하나만 동치될 수 있다. 또한 사다리꼴 행렬과 간소화된 사다리꼴 행렬의 선행성분은 항상 같은 열에 나타난다. 이 위치를 피보트위치(pivot positions)이라고 한다.

연립일차방정식의 해

알고리즘 2 연립일차방정식의 해

1. 그 연립방정식의 확대계수행렬에 가우스소거법을 적용한다. 만약 마지막 열(상수 벡터 부분)이 피보트열이면 모순체계이므로 그만둔다.
2. 간소화된 연립 방정식의 변수를 선행과 자유로 분리하고, 선행변수를 자유변수, 상수를 이용하여 표시한다.

관례적으로 자유변수에는 새로운 이름을 부여하고 이를 매개변수(parameters)라고 한다.

정리 2 해의 존재성

마지막 열이 피보트열이라는 것은

$$\begin{bmatrix} 0 & \cdots & 0 & c \end{bmatrix}$$

와 같은 꼴의 행을 가지는 것으로, 이럴 경우 모순 체계이다.

정리 3 해의 일의성

1. 무모순체계의 연립일차방정식이 꼭 하나의 행를 가질 필요충분조건은 그것이 자유변수를 가지지 않을 때이다.
2. 무모순체계의 연립일차방정식이 꼭 하나의 해를 가질 필요충분조건은 마지막 열 이외의 확대계수행렬의 각각의 열은 피보트열이고 마지막 열은 피보트열이 아닐 때이다.

정리 4 해의 수

임의의 연립일차방정식은, 꼭 하나의 해를 가지거나, 무한히 많은 해를 가지거나, 해를 가지지 않는다.

정리 5 제차연립일차방정식의 해

제차연립일차방정식은 자명해만을 가지고 무한히 많은 해를 가진다.
무한히 많은 해를 가질 필요충분조건은 그것이 자유변수를 가질 때이다.
망냑 방정식의 수보다 더 많은 미지수를 가진다면, 그것은 무한히 많은 해를 가진다.

가우스-조르당 소거법

전진법을 사용하는 동안, 선행을 1로 만들고 위아 아래를 0으로 만들어버리면 전진법만으로 간소화된 행사다리꼴을 만들 수 있다. 이를 가우스-조르당 소거법(Gauss-Jordan elimination)이라고 한다.

1.3 수치적 해

가우스 소거법과 가우스-조르당 사이의 선택

가우스-조르당 소거법이 더 간단히 해를 구할 수 있을 것으로 보이나, 가우스 소거법은 $ 2n^3 / 3 $의 연산이, 가우스-조르당 소거법은 $ n^3 $의 연산이 필요하여 가우스 소거법이 선호된다.

반복법

최초의 추정하는 해에서 출발하여 연립방정식의 해를 근사적으로 구하는 것이다. 해에 근접한다면, 반복이 수렴(converge)한다고 하고, 그렇지 않으면 발산(diverge)한다고 한다. 원하는 정확도 내에서 같은 답을 도출할 때 그 과정은 끝이 난다.

야코비 반복법

n개 미지수로 구성된 n개의 식을 갖는 정사각 연립방정식(square systems)에 적용한다. 다음의 연립방정식을 예로 살펴보자.

$$5x + y - z = 14 \\ x - 5y + 2z = -9 \\ x - 2y + 10z = -30$$

1. 연립방정식의 각 식을 각기 다른 미지수에 대해 정리한다.

   $$x = -0.2y + 0.2z + 2.8 \\ y = 0.2x + 0.4z + 1.8 \\ z = -0.1x + 0.2y - 3.0$$

2. 최초의 추정 해로부터 시작한다. 잘 모를 경우 0으로부터 시작한다. ($ x = y = z = 0$)
3. 현재 추정해를 1의 모든 식에 대입하여 새로운 x, y, z를 계산한다.
4. 추정해를 갱신해가면서 단계3을 반복하다 원하는 정확도가 이루어지면 계산을 멈춘다.

가우스-자이델 반복법

1. 야코비 반복법과 같다.
2. 야코비 반복법과 같다.
3. 미지수를 1의 가장 처음 식에 대입하여 새로운 x, y, z를 계산한다.
4. 3에서 계산된 새로운 해를 다음 식에 대입하여 x, y, z를 갱신한다. 원하는 정확도까지 이를 반복한다.

일반적으로 야코비 반복법보다 더 적은 반복으로 수렴한다. 하지만 이를 보장하지는 않는다.

수렴

야코비와 가우스-자이델 반복법이 수렴할 충분조건은 계수행렬이 대각적 우세(diagonally dominant)일 때다. 이는,

1. 행렬이 정사각이고,
2. 각각의 대각 성분의 절대값이 같은 행에서의 다른 성분의 절대값의 합보다 크다.

를 의미한다. 또한 방정식의 재배치로 대각적 우세를 얻을 수도 있다. 하지만 대각적 우세가 아닐지라도 수렴이 불가능한 것은 아니다.

가우스 소거법과 가우스-자이델 반복법 사이의 선택

큰 $n $에 대해서 가우스-자이델 방법은 대략 $ 2n^2 $의 연산이 필요하여 $ 2n^3 / 3 $인 가우스 소거법보다 적은 연산이 필요하다.
또한 가우스 소거법은 행연산 과정 중에 반올림 오차가 매번 누적되는 단점이 있으나 가우스-자이델은 마지막 반복에서 한번의 반올림 오차만 생긴다. (반올림 오차는 integer 환경에서의 계산하는 경우를 한정지어 이야기하는 것 같다.)
또한 가우스-자이델 방법은 자기-수정(self-correcting)이 가능하여 어떤 상황에서도 새로운 최초추정해로 돌아가서 재계산이 가능하다. 마지막으로 야코비와 가우스-자이델 방법은 계수행렬이 희박(sparse, 많은 영성분을 가진다면)할 때 아주 좋은 선택이다.

수치적 고려: 불량 조건과 피보팅

만약 연립방정식이 거의 일치하는 경우, 예를 들면,

$$x + y = 1 \\ 1.005x + y = 2 \\ x = 100, y = -99$$

와

$$x + y = 1 \\ 1.01x + y = 2 \\ x = 200, y= -199$$

을 비교해보면, 계수는 아주 작게 변했더라도 그 해는 큰 변화를 야기한다. 이러한 경우의 연립방정식을 불량조건(ill-conditioned)이라고 한다. 이러한 경우, 부동소수점 연산에서 허용하는 유효숫자 수에 따라 해의 근사도가 떨어지는 일이 발생한다. 이는 두 직선의 거의 평행한 경우로 해석할 수 있다.

이러한 효과를 최소화하기 위하여 가우스, 가우스-조르당 소거법에서는 부분피보팅(partial pivoting)을 수행한다. (전 피보팅(full pivoting)도 존재함.)

---