연립 일차 방정식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

연립 일차 방정식은 여러 개의 일차 방정식을 묶어 놓은 것으로, 미지수의 값들을 찾는 데 사용된다. m개의 방정식과 n개의 미지수로 이루어진 연립 일차 방정식은 행렬을 사용하여 표현할 수 있으며, 계수 행렬, 해 벡터, 소스 벡터, 첨가 행렬 등의 용어가 사용된다. 연립 일차 방정식은 동차와 비동차로 구분되며, 해의 존재성과 유일성은 계수 행렬의 성질과 관련이 있다. 해의 집합은 공집합이거나 벡터 공간의 잉여류 형태로 나타나며, 해의 존재 여부는 행렬의 랭크와 밀접한 관련이 있다. 연립 일차 방정식은 변수 소거, 가우스 소거법, 크라메르 법칙, 행렬 해법 등 다양한 방법으로 풀 수 있으며, 해의 개수는 방정식과 미지수의 관계에 따라 결정된다. 특히 동차 연립 일차 방정식은 자명해를 가지며, 해 집합은 영공간과 관련된다. 연립 일차 방정식은 신호 처리, 선형 계획법 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

수치선형대수학 - 가우스 소거법
가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.
방정식 - 피타고라스 정리
피타고라스 정리는 직각삼각형에서 직각변의 제곱의 합이 빗변의 제곱과 같다는 정리로, a² + b² = c²으로 표현되며, 한 변의 길이를 계산하는 데 사용되고, 여러 지역에서 알려졌으나 피타고라스 학파에 의해 체계화되었다고 전해진다.
방정식 - 케플러 방정식
케플러 방정식은 천체의 궤도를 기술하는 초월 방정식으로, 행성의 위치를 결정하는 데 사용되며 평균 이상, 편심 이상, 이심률 간의 관계를 나타낸다.
선형대수학 - 벡터 공간
벡터 공간은 체 위의 가군으로 정의되는 대수적 구조로, 벡터 덧셈과 스칼라 곱셈 연산을 가지며 특정 공리들을 만족하고, 기저, 차원, 선형 사상 등의 개념을 통해 수학과 물리학 등 다양한 분야에서 활용된다.
선형대수학 - 선형 결합
선형 결합은 벡터 공간에서 벡터들의 스칼라 곱의 합으로 표현되는 식으로, 벡터 집합의 선형 독립성 판단 및 부분 공간 생성과 관련되며, 계수 제약을 통해 다양한 종류의 결합을 정의할 수 있고, 위상 벡터 공간이나 가군으로 일반화될 수 있다.

연립 일차 방정식
개요
정의	대수학에서, 일차 방정식의 모임
연구 분야	선형대수학
표현
일반적인 형태	a₁x₁ + a₂x₂ + ... + aₙxₙ = b (a₁, a₂, ..., aₙ, b는 상수)
행렬 형태	Ax = b (A는 계수 행렬, x는 변수 벡터, b는 상수 벡터)
해법
해의 종류	유일해 무수히 많은 해 해 없음
풀이 방법	가우스 소거법 크래머 공식 역행렬 수치적 방법 (반복법 등)
응용
활용 분야	컴퓨터 과학 물리학 공학 경제학 통계학

2. 정의

''m''개의 방정식으로 이루어진 ''n''원 '''연립 일차 방정식'''은 다음과 같은 꼴로 나타낼 수 있다.

: $a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1n}x_n=b_1$

: $a_{21}x_1+a_{22}x_2+a_{23}x_3+\cdots+a_{2n}x_n=b_2$

: $a_{31}x_1+a_{32}x_2+a_{33}x_3+\cdots+a_{3n}x_n=b_3$

: $\vdots$

: $a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\cdots+a_{mn}x_n=b_m$

이는 행렬 곱셈을 사용하여 다음과 같이 간단하게 표현할 수 있다.^[5]

: $\begin{pmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots&&\vdots\\a_{m1}&a_{m2}&a_{m3}&\cdots&a_{mn}\\\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3\\\vdots\\b_m\end{pmatrix}$

여기서 왼쪽부터 차례대로 $A_{m\times n}$ , $x_{n\times1}$ , $b_{m\times1}$ 라고 하면, 연립 일차 방정식은 $Ax=b$ 와 같이 쓸 수 있다. 이때, $A$ 는 계수 행렬, $x$ 는 해 벡터(solution vector^영어), $b$ 는 소스 벡터(source vector^영어)라고 부른다.^[5] 또한, 계수 행렬 옆에 소스 벡터를 덧붙인 행렬 $(A|b)$ 는 첨가 행렬이라고 한다.

연립 일차 방정식 $Ax=b$ 에서 $b=0$ 이면 동차 연립 일차 방정식(homogeneous system of linear equations^영어), $b\ne0$ 이면 비동차 연립 일차 방정식(non-homogeneous system of linear equations^영어)이라고 한다.

주어진 선형 방정식계에 속하는 모든 방정식을 동시에 만족하는 변수 값을 '''선형 방정식계의 해'''라고 하며, 선형 방정식계의 해를 구하는 것을 '''선형 방정식계를 푼다'''라고 한다.

선형 방정식계가 주어졌을 때, 변수의 수와 방정식의 개수를 비교하면 그 해는 대략 다음과 같이 생각할 수 있다.

변수의 수가 더 많다면, (변수의 수) - (방정식의 개수)만큼 변수를 자유롭게 정할 수 있으며, 해가 하나로 정해지지 않는다.
변수의 수와 방정식의 개수가 일치한다면, 해가 존재하고, 하나로 정해진다.
방정식의 개수가 더 많다면, 제약이 과도하므로, 해가 존재하지 않는다.

2. 1. 일반적인 형태

''m''개의 일차 방정식과 ''n''개의 미지수를 가진 일반적인 연립 일차 방정식은 다음과 같이 표현할 수 있다.

:

\begin{cases}a_{11} x_1 + a_{12} x_2 +\dots + a_{1n} x_n = b_1 \\a_{21} x_1 + a_{22} x_2  + \dots + a_{2n} x_n = b_2 \\\vdots\\a_{m1} x_1 + a_{m2} x_2 + \dots + a_{mn} x_n = b_m,\end{cases}

여기서

x_1, x_2,\dots,x_n

는 미지수이고,

a_{11},a_{12},\dots,a_{mn}

는 연립 방정식의 계수,

b_1,b_2,\dots,b_m

는 상수항이다.^[5]

이 식은 행렬 곱셈을 이용하여 다음과 같이 나타낼 수 있다.

:

\begin{pmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots&&\vdots\\a_{m1}&a_{m2}&a_{m3}&\cdots&a_{mn}\\\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3\\\vdots\\b_m\end{pmatrix}

이를 간단하게

Ax=b

로 표현할 수 있다. 여기서

A

는 계수 행렬,

x

는 해 벡터,

b

는 소스 벡터라고 한다. 계수 행렬 옆에 소스 벡터를 덧붙인 행렬

(A|b)

는 첨가 행렬이라고 한다.

연립 일차 방정식

Ax=b

에서

b=0

이면 동차 연립 일차 방정식,

b\ne0

이면 비동차 연립 일차 방정식이라고 한다.

계수와 미지수는 실수 또는 복소수뿐만 아니라, 정수, 유리수, 다항식 등 다양한 대수 구조의 원소를 사용할 수 있다.

2. 2. 벡터 방정식

연립 일차 방정식은 미지수를 열 벡터의 가중치로 해석하여 다음과 같은 형태로 표현할 수 있다.^[1]

:

x_1\begin{bmatrix}a_{11}\\a_{21}\\ \vdots \\a_{m1}\end{bmatrix} +x_2\begin{bmatrix}a_{12}\\a_{22}\\ \vdots \\a_{m2}\end{bmatrix} +\dots +x_n\begin{bmatrix}a_{1n}\\a_{2n}\\ \vdots \\a_{mn}\end{bmatrix} = \begin{bmatrix}b_1\\b_2\\ \vdots \\b_m\end{bmatrix}

이러한 표현 방식을 통해 벡터 공간의 개념을 활용할 수 있다. 예를 들어, 좌변 벡터들의 가능한 모든 선형 결합 집합은 해당 벡터들의 생성이라고 불린다.^[1] 방정식의 해는 우변 벡터가 해당 생성 안에 있을 때만 존재한다.^[1]

만약 생성 안의 모든 벡터가 주어진 좌변 벡터의 선형 결합으로 정확히 하나의 표현을 갖는다면, 해는 유일하다.^[1] 선형 독립인 벡터들의 기저는 정확히 하나의 표현을 보장하며, 기저의 벡터 수(차원)는 ''m'' 또는 ''n''보다 클 수 없지만 더 작을 수 있다.^[1] ''m''개의 독립적인 벡터가 있다면 우변과 관계없이 해가 보장되지만, 그렇지 않으면 보장되지 않는다.^[1]

2. 3. 행렬 방정식

vector equation^영어을 행렬 방정식으로 표현하면 다음과 같다.

:

\begin{pmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots&&\vdots\\a_{m1}&a_{m2}&a_{m3}&\cdots&a_{mn}\\\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3\\\vdots\\b_m\end{pmatrix}

여기서 왼쪽부터

A_{m\times n}

,

x_{n\times1}

,

b_{m\times1}

라고 하면, 연립 일차 방정식은 다음과 같이 단순하게 쓸 수 있다.

:

Ax=b

이 경우,

A

를 이 연립 일차 방정식의 '''계수 행렬''',

x

를 '''해 벡터'''(解-, solution vector^영어),

b

를 '''소스 벡터'''(source vector^영어)라고 한다.^[5] 또한, 계수 행렬 옆에 소스 벡터를 덧붙인 행렬

(A|b)

를 '''첨가 행렬'''이라고 한다.

벡터 방정식은 다음과 같은 형태의 행렬 방정식과 동일하다.

:

A\mathbf{x} = \mathbf{b}

여기서 ''A''는 ''m''×''n'' 행렬이고, '''x'''는 ''n''개의 성분을 가진 열 벡터이며, '''b'''는 ''m''개의 성분을 가진 열 벡터이다.

:

A=\begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n} \\a_{21} & a_{22} & \cdots & a_{2n} \\\vdots & \vdots & \ddots & \vdots \\a_{m1} & a_{m2} & \cdots & a_{mn}\end{bmatrix},\quad\mathbf{x}=\begin{bmatrix}x_1 \\x_2 \\\vdots \\x_n\end{bmatrix},\quad\mathbf{b}=\begin{bmatrix}b_1 \\b_2 \\\vdots \\b_m\end{bmatrix}.

생성 집합의 기저에 있는 벡터의 개수는 행렬의 ''계수''로 표현된다.

''m''개의 변수를 가진 ''n''개의 선형 방정식 계는 일반적으로 ''mn''개의 계수 ''a''_''i'',''j'' (''i'' = 1, 2, ..., ''m'', ''j'' = 1, 2, ..., ''n'') 및 ''m''개의 상수 ''b''₁, ''b''₂, ..., ''b''_''m''을 사용하여

:

\left\{\begin{matrix}a_{1,1}x_1 + a_{1,2}x_2 +\cdots + a_{1,n}x_n &=& b_1\\a_{2,1}x_1 + a_{2,2}x_2 +\cdots + a_{2,n}x_n &=& b_2\\\vdots &\vdots &\vdots \\a_{m,1}x_1 + a_{m,2}x_2 +\cdots + a_{m,n}x_n &=& b_m\end{matrix}\right.

의 형태로 나타낼 수 있다. 이를 표기법을 바꿔

:

\begin{bmatrix}a_{1,1} & a_{1,2} &\cdots & a_{1,n}\\a_{2,1} & a_{2,2} &\cdots & a_{2,n}\\\vdots & \vdots &\ddots & \vdots \\a_{m,1} & a_{m,2} &\cdots & a_{m,n}\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ \vdots \\ b_m\end{bmatrix}

로 표시하거나, 더 나아가 행렬과 벡터를 사용하여, ''A'' = [''a''_{''i j''}], '''x''' = [''x''_''j''], '''b''' = [''b''_''i''] 등과 같이 놓으면

:

Ax = b

로 기술할 수 있다. 여기서 ''A''를 이 방정식 계의 '''계수 행렬''', '''x'''를 변수 벡터라고 한다.

선형 방정식 ''A'''''x''' = '''b'''의 해가 유일하다는 것은, 선형 사상 ''f''_''A''가 단사임을 의미하며, 이는 ker ''A'' = {'''0'''}인 것과 동치이다. 또한 이는 계수와 퇴화 차수의 관계로부터, ''f''_''A''가 비퇴화 (full rank^영어)라고 바꿔 말할 수 있다. 또한 이때, 더 나아가 ''V'', ''W''의 차원이 같다면, 행렬식 |''A''|는 0이 아니다.

3. 해의 존재성 및 유일성

체 $K$ 에서 계수를 취하는 연립 일차 방정식 $Ax=b$ 의 해집합은 공집합이거나, $K$ -벡터 공간의 잉여류 $x_0+\ker A\subset K^n$ 를 이룬다. (여기서 $x_0$ 은 임의의 고정된 해이며, $\ker$ 는 핵이다.)^[5] 특히, 동차 연립 일차 방정식의 해들은 $K$ -벡터 공간 $\ker A\subset K^n$ 을 이룬다.

구체적으로, 연립 일차 방정식 $Ax=b$ 의 해는 존재하지 않을 수도, 유일할 수도, 무수히 많을 수도 있는데, 다음 세 조건은 서로 동치이다.

$Ax=b$ 의 해가 존재한다.
$b\in\operatorname{im}A$ (여기서 $\operatorname{im}$ 는 상이다.)
$\operatorname{rank}A=\operatorname{rank}(A|b)$ (여기서 $\operatorname{rank}$ 는 계수이다.)

또한, 다음 두 조건은 서로 동치이다.

$Ax=b$ 의 해가 유일하다.
$A$ 는 가역 행렬이다.

특히, 동차 연립 일차 방정식은 영벡터를 자명한 해로 가지며, 해가 영벡터뿐일 필요충분조건은 계수 행렬이 (정사각) 가역 행렬인 것이다. 보다 구체적으로, 해공간의 차원은 다음과 같으며, 이를 계수-퇴화차수 정리라고 한다.

:

\dim\ker A=n-\operatorname{rank}A

4. 해집합

계수를 체 ''K''에서 취하는 연립 일차 방정식 $Ax=b$ 의 해의 집합은 공집합이거나, ''K''-벡터 공간의 잉여류 $x_0+\ker A\subset K^n$ 를 이룬다. (여기서 $x_0$ 은 임의의 고정된 해이며, $\ker$ 는 핵이다.) 특히, 동차 연립 일차 방정식(우변이 0인 경우)의 해들은 ''K''-벡터 공간 $\ker A\subset K^n$ 을 이룬다.

연립 일차 방정식 $Ax=b$ 의 해는 다음 세 가지 경우 중 하나이다.

해가 존재하지 않는다.
유일한 해가 존재한다.
무수히 많은 해가 존재한다.

이는 다음 조건들과 동치이다.

$Ax=b$ 의 해가 존재한다.
$b\in\operatorname{im}A$ (여기서 $\operatorname{im}$ 는 상이다.)
$\operatorname{rank}A=\operatorname{rank}(A|b)$ (여기서 $\operatorname{rank}$ 는 계수이다.)

또한, 다음 두 조건이 서로 동치이다.

$Ax=b$ 의 해는 유일하다.
$A$ 는 가역 행렬이다.

특히, 동차 연립 일차 방정식은 영벡터를 자명한 해로 가지며, 해가 영벡터뿐일 필요충분조건은 계수 행렬이 (정사각) 가역 행렬인 것이다. 보다 구체적으로, 해공간의 차원은 계수-퇴화차수 정리에 의해 다음과 같다.

:

\dim\ker A=n-\operatorname{rank}A

선형 시스템의 '''해'''는 각 방정식을 만족하는 변수 값의 할당이다. '''해집합'''은 모든 가능한 해의 집합이다.^[2]

방정식계가 제차형('''b''' = '''0''')이면, 이 방정식은 항상 영벡터 '''x''' = '''0'''을 해로 가지며, 이를 '''자명한 해'''라고 부른다. 제차형이면 방정식의 해를 중첩할 수 있다. 즉, '''x'''와 '''y'''가 제차 선형 방정식계의 해일 때, 임의의 스칼라 α와 β에 대해 α'''x''' + β'''y'''도 같은 방정식계의 해가 된다. 따라서 제차 방정식계의 해 전체 집합은 ''V''의 선형 부분 공간을 이루며, '''해 벡터 공간''' 또는 '''해 공간'''이라고 불린다.

방정식계가 비제차('''b''' ≠ '''0''')일 때, '''b'''가 선형 사상의 상에 포함되어 있지 않으면 방정식계의 해는 존재하지 않으며, '''b'''가 ''A''의 상에 속하면 적어도 하나의 해가 존재한다. 비제차 선형 방정식계가 두 개의 해 '''x'''와 '''y'''를 가질 때, 차 '''x''' - '''y'''는 0이 되므로, 비제차 방정식계의 두 해는 수반하는 제차 방정식계의 해를 더하는 만큼의 차이만 갖는다. 따라서 비제차 방정식계의 해 중 하나(특수해)와 수반 제차 방정식계의 일반해에 의해 비제차 방정식의 모든 해를 기술할 수 있다.

선형 방정식 ''A'''''x''' = '''b'''의 해가 유일하다는 것은, 선형 사상이 단사임을 의미하며, 이는 ker ''A'' = {'''0'''}인 것과 동치이다.

4. 1. 기하학적 해석

두 변수 (''x''와 ''y'')를 포함하는 시스템의 경우, 각 선형 방정식은 ''xy''-좌표 평면에 선을 결정한다. 선형 시스템의 해는 모든 방정식을 만족해야 하므로 해 집합은 이러한 선들의 교집합이며, 따라서 선, 단일 점 또는 공집합 중 하나이다.

세 개의 변수의 경우, 각 선형 방정식은 3차원 공간에서 평면을 결정하며, 해 집합은 이러한 평면들의 교집합이다. 따라서 해 집합은 평면, 선, 단일 점 또는 공집합일 수 있다. 예를 들어, 세 개의 평행 평면은 공통점을 갖지 않으므로, 그 방정식의 해 집합은 공집합이다; 한 점에서 교차하는 세 평면의 방정식의 해 집합은 단일 점이다; 세 평면이 두 점을 통과하면, 그 방정식은 적어도 두 개의 공통 해를 가지며; 실제로 해 집합은 무한하며 이 점들을 통과하는 모든 선으로 구성된다.^[2]

''n''개의 변수의 경우, 각 선형 방정식은 ''n''차원 공간에서 초평면을 결정한다. 해 집합은 이러한 초평면들의 교집합이며, ''n''보다 작은 차원을 가질 수 있는 평탄이다.

4. 2. 일반적인 동작

선형 시스템의 해는 변수

x_1, x_2,\dots,x_n

에 값을 할당하여 각 방정식을 만족시키는 것이다. 모든 가능한 해의 집합을 ''해 집합''이라고 한다.^[2]

선형 시스템은 다음 세 가지 경우 중 하나로 동작한다.

# 시스템이 ''무한히 많은 해''를 갖는다.

# 시스템이 ''유일한 해''를 갖는다.

# 시스템이 ''해가 없다''.

일반적으로 선형 시스템의 동작은 방정식의 수와 미지수의 관계에 의해 결정된다. "일반적으로"라는 표현은 방정식의 계수에 따라 다른 동작이 발생할 수 있음을 의미한다.

일반적으로 미지수보다 방정식의 수가 적은 시스템은 무수히 많은 해를 갖지만 해가 없을 수도 있다. 이러한 시스템을 부정 방정식이라고 한다.
일반적으로 방정식과 미지수의 수가 동일한 시스템은 단 하나의 고유한 해를 갖는다.
일반적으로 미지수보다 방정식의 수가 많은 시스템은 해가 없다. 이러한 시스템을 과잉 결정 시스템이라고 한다.

첫 번째 경우, 해 집합의 차원은 일반적으로

n - m

과 같다. 여기서 ''n''은 변수의 수이고 ''m''은 방정식의 수이다.

두 변수 (''x''와 ''y'')를 포함하는 시스템의 경우, 각 선형 방정식은 ''xy''-좌표 평면에 선을 결정한다. 선형 시스템의 해는 모든 방정식을 만족해야 하므로 해 집합은 이러한 선들의 교집합이며, 따라서 선, 단일 점 또는 공집합 중 하나이다.

다음 그림은 두 변수의 경우에 이러한 관계를 보여준다.

첫 번째 시스템은 무수히 많은 해 (파란색 선 위의 모든 점)를 갖는다. 두 번째 시스템은 단 하나의 고유한 해 (두 선의 교차점)를 갖는다. 세 번째 시스템은 세 선이 공통점을 공유하지 않으므로 해가 없다.

세 개의 변수의 경우, 각 선형 방정식은 3차원 공간에서 평면을 결정하며, 해 집합은 이러한 평면들의 교집합이다. 따라서 해 집합은 평면, 선, 단일 점 또는 공집합일 수 있다. 예를 들어, 세 개의 평행 평면은 공통점을 갖지 않으므로, 그 방정식의 해 집합은 공집합이다. 한 점에서 교차하는 세 평면의 방정식의 해 집합은 단일 점이다. 세 평면이 두 점을 통과하면, 그 방정식은 적어도 두 개의 공통 해를 가지며, 실제로 해 집합은 무한하며 이 점들을 통과하는 모든 선으로 구성된다.

''n''개의 변수의 경우, 각 선형 방정식은 ''n''차원 공간에서 초평면을 결정한다. 해 집합은 이러한 초평면들의 교집합이며, ''n''보다 작은 차원을 가질 수 있는 평탄이다.

위의 경우는 일반적인 경우이며, 방정식이 ''선형 독립''이거나, ''모순''이고 미지수보다 더 많은 방정식이 없는 경우 일반적인 경우와 다르게 동작할 수 있다. 예를 들어 두 방정식과 두 개의 미지수를 갖는 시스템이 해를 갖지 않거나(두 선이 평행인 경우), 세 방정식과 두 개의 미지수를 갖는 시스템이 해를 가질 수 있다(세 선이 한 점에서 교차하는 경우).

선형 방정식계가 주어졌을 때, 변수의 수와 방정식의 개수를 비교하면, 그 해는 대략 다음과 같이 생각할 수 있다.

# 변수의 수가 더 많다면, (변수의 수) - (방정식의 개수)만큼 변수를 자유롭게 정할 수 있으며, 해가 하나로 정해지지 않는다.

# 변수의 수와 방정식의 개수가 일치한다면, 해가 존재하고, 하나로 정해진다.

# 방정식의 개수가 더 많다면, 제약이 과도하므로, 해가 존재하지 않는다.

또한, 변수의 수가 많을 때에는, 몇몇 변수를 임의의 값을 가질 수 있는 상수로 간주하여, 변수의 수와 방정식의 개수가 같다고 생각할 수 있다. 따라서, 평소에는 방정식의 수와 변수의 수가 일치하는 방정식계를 많이 다룬다.

주어진 선형 방정식계에 속하는 모든 방정식을 동시에 만족하는 변수 값을 '''선형 방정식계의 해'''라고 하며, 선형 방정식계의 해를 구하는 것을 '''선형 방정식계를 푼다'''라고 한다.

다음 식은 2 변수 선형 방정식계의 예이다.

:

\begin{cases}x + 2y = 5\\2x + 3y = 8\end{cases}

왼쪽의 기호(중괄호)는 특별히 필요하지는 않지만, 방정식계임을 명시하기 위해 자주 사용된다.

이 식에서 두 개의 선형 방정식을 동시에 만족하는 (''x'', ''y'') = (1, 2)가 해이다.

해법으로 잘 알려진 것으로 다음과 같은 방법이 있다. 어느 방법이나 변수를 줄여가며, 일변수 방정식으로 귀착시킴으로써 푸는 방법이다.

; 대입법

: 어느 하나의 방정식을 하나의 변수에 대해 풀고, 다른 방정식에 대입함으로써, 변수를 줄이고 방정식을 간단하게 한 다음 푸는 방법.

; 등치법

: 각각의 방정식을 특정 변수에 대해 풀었을 때의 값을 같다고 하여, 변수를 소거하는 방법. 대입법의 일종이라고도 할 수 있다.

; 가감법

: 방정식의 양변에 상수를 곱하거나, 더하거나 빼는 것을 통해 변수를 소거하는 방법.

5. 성질

m개의 방정식으로 이루어진 n원 연립 일차 방정식은 다음과 같은 꼴로 나타낼 수 있다.

: $a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1n}x_n=b_1$

: $a_{21}x_1+a_{22}x_2+a_{23}x_3+\cdots+a_{2n}x_n=b_2$

: $a_{31}x_1+a_{32}x_2+a_{33}x_3+\cdots+a_{3n}x_n=b_3$

: $\vdots$

: $a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\cdots+a_{mn}x_n=b_m$

이는 행렬 곱셈을 이용하여 다음과 같이 간단하게 표현할 수 있다.

: $\begin{pmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots&&\vdots\\a_{m1}&a_{m2}&a_{m3}&\cdots&a_{mn}\\\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3\\\vdots\\b_m\end{pmatrix}$

: $Ax=b$

여기서 A는 계수 행렬, x는 해 벡터(解-, solution vector^영어), b는 소스 벡터(source vector^영어)라고 부른다.^[5] 계수 행렬 옆에 소스 벡터를 덧붙인 행렬 (A|b)는 첨가 행렬이다.

연립 일차 방정식 $Ax=b$ 에서 $b=0$ 이면 동차 연립 일차 방정식(同次聯立一次方程式, homogeneous system of linear equations^영어)이라고 하며, $b\ne0$ 이면 비동차 연립 일차 방정식(非同次聯立一次方程式, non-homogeneous system of linear equations^영어)이라고 한다.

선형 시스템의 해는 변수 $x_1, x_2,\dots,x_n$ 에 값을 할당하여 각 방정식을 만족시키는 것을 의미하며, 모든 가능한 해의 집합을 해 집합이라고 한다.^[2]

선형 시스템은 다음 세 가지 경우 중 하나로 나타난다.

무한히 많은 해를 갖는 경우
유일한 해를 갖는 경우
해가 없는 경우

5. 1. 독립성

연립 일차 방정식에서, 각 방정식이 다른 방정식들로부터 대수적으로 유도될 수 없을 때 그 방정식들을 독립적이라고 한다. 방정식들이 독립적이면 각 방정식은 변수에 대한 새로운 정보를 포함하며, 어떤 방정식을 제거하더라도 해 집합의 크기가 증가한다. 선형 방정식의 경우, 논리적 독립은 선형 독립과 동일하다.

예를 들어, 방정식

: 3x + 2y = 6 과 6x + 4y = 12

는 독립적이지 않다. 두 번째 방정식은 첫 번째 방정식에 2를 곱하면 얻을 수 있으며, 동일한 그래프를 갖는다. 이는 연립 일차 방정식의 동치의 예시이다.

더 복잡한 예로, 다음 방정식들을 들 수 있다.

: x - 2y = -1

: 3x + 5y = 8

: 4x + 3y = 7

이 방정식들은 독립적이지 않다. 세 번째 방정식은 첫 번째 방정식과 두 번째 방정식의 합으로 나타낼 수 있기 때문이다. 실제로, 이 방정식들 중 어느 것이든 다른 두 방정식으로부터 유도될 수 있으며, 어떤 방정식을 제거해도 해 집합은 변하지 않는다. 이 방정식들의 그래프는 한 점에서 교차하는 세 개의 직선이다.

5. 2. 일관성

선형 시스템은 해가 없으면 '''모순적'''이라고 하며, 그렇지 않으면 '''일치적'''이라고 한다.^[5] 시스템이 모순적인 경우, 방정식에서 모순을 도출할 수 있으며, 이는 항상

0=1

로 다시 쓸 수 있다.

예를 들어, 다음 방정식

:

3x+2y=6\;\;\;\;\text{and}\;\;\;\;3x+2y=12

는 모순적이다. 실제로, 첫 번째 방정식을 두 번째 방정식에서 빼고, 그 결과의 양변에 1/6을 곱하면

0=1

이 된다. 이 방정식들의 ''xy'' 평면에서의 그래프는 평행선 쌍이다.

세 개의 선형 방정식이 두 개씩 짝을 지어 일치하더라도 전체적으로는 모순적일 수 있다. 예를 들어, 다음 방정식

:

\begin{alignat}{7}x &&\; + \;&& y &&\; = \;&& 1 & \\2x &&\; + \;&& y &&\; = \;&& 1 & \\3x &&\; + \;&& 2y &&\; = \;&& 3 &\end{alignat}

는 모순적이다. 처음 두 방정식을 더하면

3x + 2y = 2

가 되며, 이를 세 번째 방정식에서 빼면

0=1

이 된다. 이 방정식 중 임의의 두 개는 공통 해를 갖는다. 이와 같은 현상은 어떤 수의 방정식에서도 발생할 수 있다.

일반적으로, 시스템의 방정식의 좌변이 선형 종속적이고, 상수항이 종속 관계를 만족하지 않으면 모순이 발생한다. 좌변이 선형 독립적인 방정식 시스템은 항상 일치한다.

다르게 말하면, 루셰-카펠리 정리에 따르면, (과결정된 경우를 포함한) 모든 방정식 시스템은 확대 행렬의 계수가 계수 행렬의 계수보다 크면 모순적이다. 반면에 이 두 행렬의 계수가 같으면, 시스템은 적어도 하나의 해를 가져야 한다. 해는 계수가 변수의 수와 같을 때만 유일하다. 그렇지 않으면 일반 해는 ''k''개의 자유 매개변수를 가지며, 여기서 ''k''는 변수의 수와 계수의 차이이다. 따라서 이러한 경우 무한히 많은 해가 있다. 방정식 시스템의 계수(즉, 확대 행렬의 계수)는 [변수의 수] + 1보다 클 수 없으며, 이는 어떤 수의 방정식을 가진 시스템도 [변수의 수] + 1과 같거나 작은 수의 독립 방정식을 갖는 시스템으로 항상 줄일 수 있음을 의미한다.

5. 3. 동치

두 개의 연립 일차 방정식에서 동일한 변수 집합을 사용하고, 두 번째 시스템의 각 방정식이 첫 번째 시스템의 방정식으로부터 대수적으로 유도될 수 있으며 그 역도 성립하면 두 연립 일차 방정식은 '''동치'''라고 한다. 두 시스템이 모두 모순되거나 각 시스템의 각 방정식이 다른 시스템의 방정식의 선형 결합이면 두 시스템은 동치이다. 따라서 두 연립 일차 방정식은 동일한 해 집합을 갖는 경우에만 동치이다.

6. 풀이

체 $K$ 에서 계수를 가져오는 연립 일차 방정식 $Ax=b$ 의 해집합은 공집합이거나, $K$ -벡터 공간의 잉여류 $x_0+\ker A\subset K^n$ 를 이룬다. 여기서 $x_0$ 는 임의의 고정된 해이고, $\ker$ 는 핵이다. 특히, 동차 연립 일차 방정식(homogeneous)의 해는 $K$ -벡터 공간 $\ker A\subset K^n$ 을 이룬다.

연립 일차 방정식 $Ax=b$ 의 해는 존재하지 않거나, 유일하거나, 무수히 많을 수 있는데, 다음 세 조건은 서로 동치이다.

$Ax=b$ 의 해가 존재한다.
$b\in\operatorname{im}A$ (여기서 $\operatorname{im}$ 는 상이다.)
$\operatorname{rank}A=\operatorname{rank}(A|b)$ (여기서 $\operatorname{rank}$ 는 계수이다.)

또한, 다음 두 조건은 서로 동치이다.

$Ax=b$ 의 해가 유일하다.
$A$ 는 가역 행렬이다.

특히, 동차 연립 일차 방정식은 영벡터를 자명한 해로 가지며, 해가 영벡터뿐일 필요충분조건은 계수 행렬이 (정사각) 가역 행렬인 것이다. 해공간의 차원은 계수-퇴화차수 정리에 따라 다음과 같다.

:

\dim\ker A=n-\operatorname{rank}A

선형 연립 방정식을 푸는 여러 알고리즘이 있다. 예를 들어 다음과 같은 2변수 선형 방정식계가 있다.

:

\begin{cases}x + 2y = 5\\2x + 3y = 8\end{cases}

왼쪽의 중괄호는 필수는 아니지만, 방정식계임을 명시하기 위해 자주 사용된다. 이 식에서 두 개의 선형 방정식을 동시에 만족하는 (x, y) = (1, 2)가 해이다.

주어진 선형 방정식계에 속하는 모든 방정식을 동시에 만족하는 변수 값을 '''선형 방정식계의 해'''라고 하며, 선형 방정식계의 해를 구하는 것을 '''선형 방정식계를 푼다'''라고 한다.

일반적으로 선형 방정식계에서 변수의 수와 방정식의 개수를 비교하면 해의 존재 여부를 대략적으로 파악할 수 있다.

# 변수의 수가 더 많으면, (변수의 수) − (방정식의 개수)만큼 변수를 자유롭게 정할 수 있으며, 해가 하나로 정해지지 않는다.

# 변수의 수와 방정식의 개수가 같으면, 해가 존재하고, 하나로 정해진다.

# 방정식의 개수가 더 많으면, 제약이 과도하므로, 해가 존재하지 않는다.

변수의 수가 많을 때는, 몇몇 변수를 임의의 값을 가질 수 있는 상수로 간주하여, 변수의 수와 방정식의 개수가 같다고 생각할 수도 있다. 따라서 일반적으로는 방정식의 수와 변수의 수가 일치하는 방정식계를 많이 다룬다.

잘 알려진 해법은 다음과 같다.

'''대입법''': 한 방정식을 한 변수에 대해 풀고, 다른 방정식에 대입하여 변수를 줄이고 방정식을 간단하게 만든 후 푸는 방법이다.
'''등치법''': 각 방정식을 특정 변수에 대해 풀었을 때의 값을 같다고 하여 변수를 소거하는 방법이다. 대입법의 일종이라고도 할 수 있다.
'''가감법''': 방정식의 양변에 상수를 곱하거나, 더하거나 빼는 것을 통해 변수를 소거하는 방법이다.

n개의 변수를 가진 m개의 선형 방정식 계는 일반적으로 다음과 같이 나타낼 수 있다.

:

\left\{\begin{matrix}a_{1,1}x_1 + a_{1,2}x_2 +\cdots + a_{1,n}x_n &=& b_1\\a_{2,1}x_1 + a_{2,2}x_2 +\cdots + a_{2,n}x_n &=& b_2\\\vdots &\vdots &\vdots \\a_{m,1}x_1 + a_{m,2}x_2 +\cdots + a_{m,n}x_n &=& b_m\end{matrix}\right.

이를 행렬과 벡터를 사용하여 간단하게 표현할 수 있다.

:

\begin{bmatrix}a_{1,1} & a_{1,2} &\cdots & a_{1,n}\\a_{2,1} & a_{2,2} &\cdots & a_{2,n}\\\vdots & \vdots &\ddots & \vdots \\a_{m,1} & a_{m,2} &\cdots & a_{m,n}\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_n\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ \vdots \\ b_m\end{bmatrix}

A = [a_ij], x = [x_j], b = [b_i] 와 같이 놓으면,

:

Ax = b

로 표현할 수 있다. 여기서 A를 '''계수 행렬''', x를 변수 벡터라고 한다.

b가 영벡터 0(모든 성분이 0)일 경우, 이 선형 방정식은 '''제차''' (또는 '''동차''', homogeneous^영어)라고 하며, 그렇지 않을 때는 '''비제차''' (또는 '''비동차''', inhomogeneous^영어)라고 한다. 비제차 방정식 Ax = b가 주어졌을 때, b = 0으로 놓고 얻어지는 제차 방정식 Ax = 0는 원래의 비제차 방정식에 '''수반'''하는 제차 방정식이라고 한다.

방정식의 개수와 변수의 개수가 일치하는 경우, A가 정칙 행렬이면, A의 역행렬 A^-1을 사용하여 해를 구할 수 있다.

:

x = A^{-1}b

그러나 역행렬을 계산하는 것은 일반적으로 어렵기 때문에, 가우스 소거법, 행렬의 기본 변형과 같은 다른 해법들이 다양하게 제안되어 있다. 실용적으로는 문제의 규모, 계수 행렬 A의 특성, 상수 벡터 b의 변화 여부 등에 따라 LU 분해, 특이값 분해, 켤레 기울기 방법등 적합한 해법을 선택해야 한다.

6. 1. 가우스 소거법

가우스 소거법은 가감법을 사용하여 연립 일차 방정식을 푸는 방법이다. 기본 행 연산을 통해 첨가 행렬을 기약 행 사다리꼴 행렬로 변환한다.

'''행렬 변환'''(또는 '''가우스 소거법''')에서 선형 시스템은 첨가 행렬로 표현된다.

:

\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\3 & 5 & 6 & 7 \\2 & 4 & 3 & 8\end{array}\right]\text{.}

그런 다음 이 행렬은 기본 행 연산을 사용하여 기약 행 사다리꼴에 도달할 때까지 수정된다. 기본 행 연산에는 세 가지 유형이 있다.

'''유형 1''': 두 행의 위치를 바꾼다.
'''유형 2''': 행에 0이 아닌 스칼라를 곱한다.
'''유형 3''': 다른 행의 스칼라 배수를 한 행에 더한다.

이러한 연산은 가역적이므로 생성된 첨가 행렬은 항상 원래 선형 시스템과 동등한 선형 시스템을 나타낸다.

첨가 행렬을 행 축소하는 몇 가지 특정 알고리즘이 있으며, 그 중 가장 간단한 것은 가우스 소거법과 가우스-조던 소거법이다. 다음 계산은 위의 행렬에 적용된 가우스-조던 소거법을 보여준다.

:

\begin{align}\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\3 & 5 & 6 & 7 \\2 & 4 & 3 & 8\end{array}\right]&\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & -4 & 12 & -8 \\2 & 4 & 3 & 8\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & -4 & 12 & -8 \\0 & -2 & 7 & -2\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & 1 & -3 & 2 \\0 & -2 & 7 & -2\end{array}\right]\\&\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & 1 & -3 & 2 \\0 & 0 & 1 & 2\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 3 & 0 & 9 \\0 & 1 & 0 & 8 \\0 & 0 & 1 & 2\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 0 & 0 & -15 \\0 & 1 & 0 & 8 \\0 & 0 & 1 & 2\end{array}\right].\end{align}

마지막 행렬은 기약 행 사다리꼴에 있으며 ''x'' = -15, ''y'' = 8, ''z'' = 2 인 시스템을 나타낸다. 변수의 대수적 소거에 대한 이전 섹션의 예와 비교하면 이 두 방법이 실제로 동일하다는 것을 알 수 있다. 차이점은 계산을 작성하는 방식에 있다.

6. 2. 크라메르 법칙

크라메르 법칙은 방정식의 개수와 미지수의 개수가 같고, 계수 행렬이 가역 행렬일 경우에 유일한 해를 구하는 공식이다. 이 유일한 해는 다음과 같다.

:

x=A^{-1}b

크라메르 법칙은 이를 다음과 같이 풀어쓴다.

:

x_i=\frac{\det A_i}{\det A}\qquad i=1,\dots,n

여기서

A_i

는

A

의

i

번째 열을

b

로 대신하여 얻는 행렬이며,

\det

는 행렬식이다.

예를 들어, 다음 연립 방정식의 해는 다음과 같다.

:

\begin{alignat}{7}x &\; + &\; 3y &\; - &\; 2z &\; = &\; 5 \\3x &\; + &\; 5y &\; + &\; 6z &\; = &\; 7 \\2x &\; + &\; 4y &\; + &\; 3z &\; = &\; 8\end{alignat}

:

x=\frac{\, \begin{vmatrix}5&3&-2\\7&5&6\\8&4&3\end{vmatrix} \,}{\, \begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix} \,},\;\;\;\;y=\frac{\, \begin{vmatrix}1&5&-2\\3&7&6\\2&8&3\end{vmatrix} \,}{\, \begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix} \,},\;\;\;\;z=\frac{\, \begin{vmatrix}1&3&5\\3&5&7\\2&4&8\end{vmatrix} \,}{\, \begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix} \,}.

각 변수에 대해 분모는 계수 행렬의 행렬식이고, 분자는 상수항 벡터로 대체된 열이 하나 있는 행렬의 행렬식이다.

크라메르 공식은 이론적으로 중요하지만, 큰 행렬의 행렬식 계산이 다소 번거롭기 때문에 큰 행렬에는 실용적인 가치가 거의 없다.

6. 3. 변수 소거

연립 일차 방정식을 푸는 가장 간단한 방법은 변수를 반복적으로 소거하는 것이다. 이 방법은 다음과 같이 설명할 수 있다.

# 첫 번째 방정식에서 다른 변수를 기준으로 한 변수를 푼다.

# 이 식을 나머지 방정식에 대입한다. 그러면 방정식과 미지수가 하나씩 줄어든 연립 방정식이 생성된다.

# 연립 방정식이 단일 선형 방정식으로 축소될 때까지 1단계와 2단계를 반복한다.

# 이 방정식을 풀고, 전체 해를 찾을 때까지 역대입한다.

예를 들어, 다음 연립 방정식을 생각해 보자.

:

\begin{cases}x+3y-2z=5\\3x+5y+6z=7\\2x+4y+3z=8\end{cases}

첫 번째 방정식에서 ''x''를 풀면

x=5+2z-3y

가 되고, 이를 두 번째 및 세 번째 방정식에 대입하면 다음이 된다.

:

\begin{cases}y=3z+2\\y=\tfrac{7}{2}z+1\end{cases}

두 방정식의 좌변(LHS)이 모두 ''y''이므로 방정식의 우변(RHS)을 동일하게 한다. 이제 다음과 같다.

:

\begin{align}3z+2=\tfrac{7}{2}z+1\\ \Rightarrow z=2\end{align}

''z'' = 2를 두 번째 또는 세 번째 방정식에 대입하면 ''y'' = 8이 되고, ''y''와 ''z''의 값을 첫 번째 방정식에 대입하면 ''x'' = −15가 된다. 따라서 해 집합은 순서쌍

(x,y,z)=(-15,8,2)

이다.

이러한 풀이 방법은 대입법이라고 하며, 하나의 방정식을 하나의 변수에 대해 풀고, 다른 방정식에 대입함으로써 변수를 줄여 나가는 방식이다.^[1]

6. 4. 행 축소

가우스 소거법은 가감법을 사용하여 연립 일차 방정식을 푸는 방법이다. 기본 행 연산을 통해 첨가 행렬을 계수 행렬이 기약 행 사다리꼴 행렬인 새로운 첨가 행렬로 변환시켜 해를 구한다.

'''행렬 변환'''(또는 '''가우스 소거법''')에서 선형 시스템은 첨가 행렬로 표현된다.

다음은 행렬 변환의 예시이다.

:

\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\3 & 5 & 6 & 7 \\2 & 4 & 3 & 8\end{array}\right]\text{.}

이 행렬은 기본 행 연산을 사용하여 기약 행 사다리꼴에 도달할 때까지 수정된다. 기본 행 연산에는 세 가지 유형이 있다.

'''유형 1''': 두 행의 위치를 바꾼다.
'''유형 2''': 행에 0이 아닌 스칼라를 곱한다.
'''유형 3''': 다른 행의 스칼라 배수를 한 행에 더한다.

이러한 연산은 가역적이므로 생성된 첨가 행렬은 항상 원래 선형 시스템과 동등한 선형 시스템을 나타낸다.

첨가 행렬을 행 축소하는 몇 가지 특정 알고리즘이 있으며, 그 중 가장 간단한 것은 가우스 소거법과 가우스-조던 소거법이다. 다음은 위의 행렬에 적용된 가우스-조던 소거법을 보여준다.

:

\begin{align}\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\3 & 5 & 6 & 7 \\2 & 4 & 3 & 8\end{array}\right]&\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & -4 & 12 & -8 \\2 & 4 & 3 & 8\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & -4 & 12 & -8 \\0 & -2 & 7 & -2\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & 1 & -3 & 2 \\0 & -2 & 7 & -2\end{array}\right]\\&\sim\left[\begin{array}{rrr|r}1 & 3 & -2 & 5 \\0 & 1 & -3 & 2 \\0 & 0 & 1 & 2\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 3 & 0 & 9 \\0 & 1 & 0 & 8 \\0 & 0 & 1 & 2\end{array}\right]\sim\left[\begin{array}{rrr|r}1 & 0 & 0 & -15 \\0 & 1 & 0 & 8 \\0 & 0 & 1 & 2\end{array}\right].\end{align}

마지막 행렬은 기약 행 사다리꼴에 있으며, ''x'' = -15, ''y'' = 8, ''z'' = 2 인 시스템을 나타낸다.

선형대수학에서 연립 일차 방정식의 해를 구하는 중요한 방법에는 가우스 소거법과 행렬의 기본 변형이 있다.

6. 5. 행렬 해

벡터 방정식은 행렬 방정식과 같은 형태로 표현할 수 있다.

:

A\mathbf{x} = \mathbf{b}

여기서 ''A''는 ''m''×''n'' 행렬이고, '''x'''는 ''n''개의 성분을 가진 열 벡터, '''b'''는 ''m''개의 성분을 가진 열 벡터이다.

:

A=\begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n} \\a_{21} & a_{22} & \cdots & a_{2n} \\\vdots & \vdots & \ddots & \vdots \\a_{m1} & a_{m2} & \cdots & a_{mn}\end{bmatrix},\quad\mathbf{x}=\begin{bmatrix}x_1 \\x_2 \\\vdots \\x_n\end{bmatrix},\quad\mathbf{b}=\begin{bmatrix}b_1 \\b_2 \\\vdots \\b_m\end{bmatrix}.

연립 방정식이

A\mathbf{x}=\mathbf{b}

와 같은 행렬 형식으로 표현될 때, 전체 해 집합 역시 행렬 형식으로 표현할 수 있다. 행렬 ''A''가 정방 행렬(''m''개의 행과 ''n''=''m''개의 열)이고 모든 행이 독립적인 랭크를 가지면, 시스템은 다음과 같은 유일한 해를 갖는다.

:

\mathbf{x}=A^{-1}\mathbf{b}

여기서

A^{-1}

는 ''A''의 역행렬이다.

일반적으로 ''m''=''n''인지, ''A''의 랭크가 얼마인지와 관계없이, (존재하는 경우) 모든 해는 ''A''의 무어-펜로즈 역행렬

A^+

를 사용하여 다음과 같이 나타낼 수 있다.

:

\mathbf{x}=A^+ \mathbf{b} + \left(I - A^+ A\right)\mathbf{w}

여기서

\mathbf{w}

는 가능한 모든 ''n''×1 벡터 값을 가질 수 있는 자유 매개변수 벡터이다. 임의의 해가 존재하기 위한 필요충분조건은

\mathbf{w}=\mathbf{0}

을 사용하여 얻은 해가

A\mathbf{x}=\mathbf{b}

를 만족하는 것, 즉

AA^+ \mathbf{b}=\mathbf{b}

이다. 이 조건이 충족되지 않으면 연립 방정식은 모순되어 해가 없다. 조건이 충족되면 방정식은 일관성이 있으며 적어도 하나의 해가 존재한다.

예를 들어 ''A''가 정방 행렬이고 전체 랭크인 경우,

A^+

는

A^{-1}

과 같으며, 일반 해 방정식은 다음과 같이 단순화된다.

:

\mathbf{x}=A^{-1}\mathbf{b} + \left(I - A^{-1}A\right)\mathbf{w} = A^{-1}\mathbf{b} + \left(I-I\right)\mathbf{w} = A^{-1}\mathbf{b}

이 경우

\mathbf{w}

는 해에서 완전히 사라져 유일한 해만 남는다. 그러나

\mathbf{w}

가 남아있는 경우도 있는데, 이때는 자유 매개변수 벡터

\mathbf{w}

의 값에 따라 무한히 많은 해가 존재한다.

6. 6. 기타 방법

선형 방정식 시스템의 수치적 해법

세 개 또는 네 개의 방정식으로 구성된 연립 일차 방정식은 손으로 풀기 쉽지만(크라코비안 참조), 더 큰 시스템은 컴퓨터를 사용한다. 선형 방정식 시스템을 풀기 위한 표준 알고리즘은 수정된 가우스 소거법을 기반으로 한다. 작은 숫자로 나누는 것을 피하기 위해 방정식을 재정렬하는 피벗팅을 사용하기도 한다. 또한, 행렬 ''A''의 LU 분해를 계산하는 방법도 사용된다.

행렬 ''A''에 특별한 구조가 있는 경우, 더 빠르거나 더 정확한 알고리즘을 얻을 수 있다. 예를 들어, 대칭 양의 정부호 행렬을 갖는 시스템은 촐레스키 분해를 사용하여 두 배 빠르게 풀 수 있다. 레빈슨 재귀는 토플리츠 행렬에 대한 빠른 방법이다. 많은 0 요소를 가진 행렬 (희소 행렬)에 대한 특수 방법도 존재한다.

매우 큰 시스템의 경우, 반복법을 사용하기도 한다. 반복법은 해에 대한 초기 근사값으로 시작하여 이 근사값을 여러 단계로 변경하여 실제 해에 더 가깝게 만드는 방법이다. 근사값이 충분히 정확해지면 이를 시스템의 해로 간주한다. 반복법의 한 예는 야코비 방법이다.^[3] 야코비 방법은 행렬

A

를 대각 성분

D

와 비대각 성분

L+U

로 분할하여, 초기 추측

{\bold x}^{(0)}

에서 시작하여 다음 반복 방정식을 통해 해를 계산한다.

:

{\bold x}^{(k+1)} = D^{-1}({\bold b} - (L+U){\bold x}^{(k)})

추측

{\bold x}^{(k)}

와

{\bold x}^{(k+1)}

의 차이가 충분히 작으면, 알고리즘은 해에 수렴했다고 판단한다.^[4]

선형 방정식 시스템에 대한 양자 알고리즘도 있다.

방정식의 개수와 변수의 개수가 일치하는 경우, ''A''가 정칙 행렬이면, ''A''의 역행렬 ''A''^-1을 사용하여 다음 선형 방정식의 해를 구할 수 있다.

:

x = A^{-1}b

그러나 역행렬을 계산하는 것은 일반적으로 어렵기 때문에, 다른 수치적 해법들이 다양하게 제안되어 있다.

다음은 선형대수학에서 중요한 해법들이다.

가우스 소거법
행렬의 기본 변형

실용적으로 등장하는 문제는, 문제의 규모(방정식의 개수나 변수의 개수)가 작고, 계수 행렬 ''A''가 밀집 행렬이거나, 문제의 규모는 크지만, 행렬 ''A''는 희소 행렬이고 성질이 있는 경우가 많다. 또한 행렬 ''A''는 변하지 않고, 상수 벡터 '''b'''를 여러 번 바꾸어 계산할 필요도 생긴다. 따라서 각 상황에 적합한 해법을 선택할 필요가 있다.

LU 분해
특이값 분해
켤레 기울기 방법

7. 동차 연립 일차 방정식

모든 상수항이 0인 연립 일차 방정식을 동차 연립 일차 방정식(homogeneous system of linear equations^영어)이라고 한다. 일반적인 연립 일차 방정식은 다음과 같이 표현할 수 있다.

: $a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1n}x_n=b_1$

: $a_{21}x_1+a_{22}x_2+a_{23}x_3+\cdots+a_{2n}x_n=b_2$

: $a_{31}x_1+a_{32}x_2+a_{33}x_3+\cdots+a_{3n}x_n=b_3$

: $\vdots$

: $a_{m1}x_1+a_{m2}x_2+a_{m3}x_3+\cdots+a_{mn}x_n=b_m$

이를 행렬 곱셈으로 표현하면 다음과 같다.

: $\begin{pmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\\vdots&\vdots&\vdots&&\vdots\\a_{m1}&a_{m2}&a_{m3}&\cdots&a_{mn}\\\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\\\vdots\\x_n\end{pmatrix}=\begin{pmatrix}b_1\\b_2\\b_3\\\vdots\\b_m\end{pmatrix}$

여기서 왼쪽부터 순서대로 $A_{m\times n}$ , $x_{n\times1}$ , $b_{m\times1}$ 라고 하면, 연립 일차 방정식은 $Ax=b$ 와 같이 간단하게 쓸 수 있다. 이때, $A$ 를 계수 행렬, $x$ 를 해 벡터, $b$ 를 소스 벡터라고 한다.^[5]

동차 연립 일차 방정식은 $b=0$ 인 경우, 즉, $Ax=0$ 인 경우를 말한다. 반대로, $b\ne0$ 이면 비동차 연립 일차 방정식(non-homogeneous system of linear equations^영어)이라고 한다.

방정식계가 제차형 ('''b''' = '''0''')이면, 이 방정식은 항상 영벡터 '''x''' = '''0'''을 해로 가지는데 이를 제차 방정식의 '''자명한 해'''라고 부른다. 제차형에서는 방정식의 해를 중첩할수 있다. 즉, '''x'''와 '''y'''가 제차 선형 방정식계의 해일 때, 임의의 스칼라 α와 β에 대해 α'''x''' + β'''y'''도 같은 방정식계의 해가 된다.

선형 방정식 $Ax = b$ 의 해가 유일하다는 것은, 선형 사상 $f_A$ 가 단사임을 의미하며, 이는 ker $A$ = {'''0'''}인 것과 동치이다.

7. 1. 동차 해집합

homogeneous system^영어은 모든 상수항이 0인 경우의 선형 방정식 시스템이다.

:

\begin{alignat}{7}a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; = \;&&& 0 \\a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; = \;&&& 0 \\&&       &&            &&              &&  &&   \vdots\;\  &&&  \\a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; = \;&&& 0. \\\end{alignat}

이러한 동차 시스템은 행렬 방정식으로 표현하면 다음과 같다.

:

A\mathbf{x}=\mathbf{0}

여기서 ''A''는 행렬이고, '''x'''는 ''n''개의 항목을 가진 열 벡터이며, '''0'''은 ''m''개의 항목을 가진 영 벡터이다.

모든 동차 연립 일차 방정식은 영벡터를 자명한 해로 가진다. 해가 영벡터뿐일 필요충분조건은 계수 행렬이 (정사각) 가역 행렬인 것이다. 동차 시스템이 비특이 행렬을 가지면, 영벡터가 유일한 해가 된다. 만약 시스템이 특이 행렬을 갖는다면, 무한히 많은 해를 가진 해 집합이 존재한다.

이 해 집합은 다음과 같은 추가적인 속성을 갖는다.

'''u'''와 '''v'''가 동차 시스템의 해를 나타내는 두 개의 벡터라면, 벡터 합 '''u''' + '''v''' 또한 시스템의 해이다.
'''u'''가 동차 시스템의 해를 나타내는 벡터이고, ''r''이 임의의 스칼라라면, ''r'''''u''' 또한 시스템의 해이다.

이것들은 해 집합이 '''R'''^''n''의 선형 부분 공간이 되기 위해 필요한 속성들이다. 동차 시스템의 해 집합은 해당 행렬 ''A''의 영공간과 같다.

해 공간의 차원은 다음과 같으며, 이를 계수-퇴화차수 정리라고 한다.

:

\dim\ker A=n-\operatorname{rank}A

7. 2. 비동차 시스템과의 관계

Inhomogeneous system^영어인 비동차 시스템 A'''x''' = '''b'''의 해집합은 동차 시스템 A'''x''' = '''0'''의 해집합을 평행이동한 것이다. '''p'''가 A'''x''' = '''b'''의 특정 해이면, 전체 해집합은 {'''p''' + '''v''' : '''v'''는 A'''x''' = '''0'''의 임의의 해}로 표현된다. 벡터 '''b'''가 선형 변환 A의 상에 속해야 해가 존재한다.

구체적으로, '''b'''가 선형 사상 ''f''_''A''의 상에 포함되지 않으면 방정식계의 해는 존재하지 않으며, '''b'''가 ''A''의 상에 속하면 적어도 하나의 해가 존재한다.

비제차 선형 방정식계가 두 개의 해 '''x'''와 '''y'''를 가질 때, 차 '''x''' - '''y'''는 사상 ''f''_''A''의 선형성에 의해 ''A''('''x''' - '''y''') = '''0'''을 만족한다. 따라서 비제차 선형 방정식계의 두 해는 수반하는 제차 방정식계의 해를 더하는 만큼의 차이만 갖는다. 따라서 비제차 방정식계의 해 중 하나(특수해)와 수반 제차 방정식계의 일반해에 의해 비제차 방정식의 모든 해를 기술할 수 있다.

즉, '''x'''₀이 ''A'''''x''' = '''b'''의 특수해라면, 비제차 방정식의 해 전체는

:

x_0 + \ker f_A := \{ \mathbf{x_0} + \mathbf{v} \in V \mid A\mathbf{v} = \mathbf{0} \}

로 주어진다. 이것은 ker ''A''에 수반된 아핀 공간이며, 역시 방정식계의 '''해 공간'''이라고 불린다. 수반 제차 방정식의 기본해 '''x'''₁, '''x'''₂, ..., '''x'''_''n''을 사용하면

:

\mathbf{x_0} + c_1\mathbf{x_1} + c_2\mathbf{x_2} + \cdots + c_n\mathbf{x_n}

의 형태로 모든 해를 쓸 수 있다.

8. 응용

신호 처리, 선형 계획법, 뉴턴 방법, 유한 요소법 등 선형 근사를 포함한 다양한 분야에 응용된다.

참조

_[1] 간행물 System of Equations https://www.britanni[...] 2024-08-26
_[2] 웹사이트 Systems of Linear Equations https://math.berkele[...]
_[3] 뉴스 New Algorithm Breaks Speed Limit for Solving Linear Equations https://www.quantama[...] 2021-03-08
_[4] 웹사이트 Jacobi Method https://mathworld.wo[...]
_[5] 웹사이트 cemm#을 활용한 수치해석, 제 3 장 수치 선형대수 www.msharpmath.com, revised on 2012.11.28,p21 http://www.msharpmat[...] 2017-08-02

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com