11강 / 20강

가우스 소거법 — 계단 꼴로 만들어 푼다

쓸 수 있는 손놀림은 딱 세 가지

미지수가 셋, 넷, 백 개가 되면 눈으로 푸는 건 불가능합니다. 그래서 절대 실패하지 않는 절차가 필요해요. 그것이 가우스 소거법입니다.

핵심은 이겁니다 — 방정식을 주물러도 해가 변하지 않는 손놀림이 세 가지 있습니다.

① 두 줄의 순서를 바꾼다 (식을 쓴 순서는 답과 무관)

② 한 줄에 0이 아닌 수를 곱한다 (양변에 같은 수를 곱한 것)

③ 한 줄에 다른 줄의 몇 배를 더한다 (같은 값을 양변에 더한 것)

이 셋만 써서 첨가행렬을 계단 꼴로 만듭니다. 왼쪽 아래가 전부 0이 되면, 마지막 줄부터 거꾸로 값을 구해 올라갈 수 있어요.

고등학생계단 꼴로 만들어 푼다

연립방정식을 기계적으로 푸는 방법입니다.

쓸 수 있는 손놀림은 딱 세 가지

연산	왜 괜찮나
두 행을 바꾼다	식의 순서는 상관없다
행에 0 아닌 수를 곱한다	양변에 곱하는 것
한 행의 배수를 다른 행에 더한다	참인 식끼리 더해도 참

세 가지 모두 해를 바꾸지 않는다 — 그게 핵심이다

왜 세 번째가 해를 안 바꾸나

두 식이 참이면 더한 식도 참이니까요.

—	—
2x+y=5, x−y=1	둘 다 참인 (x,y)는
더한 3x=6 도	만족한다 ✔

그리고 되돌릴 수 있다 — 빼면 원래로

비유 — 저울

동작	균형
양쪽에 같은 것을 더한다	유지 ✔
양쪽에 같은 수를 곱한다	유지 ✔

"등식을 지키는 조작" 만 쓰는 것이 대수의 기본이다

중학교에서 배운 가감법을 체계적으로 정리한 것이 가우스 소거법입니다.

축(피벗)을 1로 만들고, 그 아래를 0으로 지웁니다. 이것을 왼쪽부터 반복합니다.

Python 브라우저에서 실행

# 손놀림 셋을 함수로 만들어 봅니다
def 줄바꿈(M, i, j):
    M[i], M[j] = M[j], M[i]

def 줄곱하기(M, i, k):
    M[i] = [k * v for v in M[i]]

def 줄더하기(M, i, j, k):     # i행에 j행의 k배를 더한다
    M[i] = [a + k * b for a, b in zip(M[i], M[j])]

M = [[2, 1, -1, 8],
     [-3, -1, 2, -11],
     [-2, 1, 2, -3]]

def 보기(M, 말):
    print(말)
    for 행 in M:
        print("  [", " ".join(f"{v:>6.2f}" for v in 행[:-1]), "|", f"{행[-1]:>6.2f}", "]")
    print()

보기(M, "처음")
줄곱하기(M, 0, 1/2)
보기(M, "R1 / 2 — 첫 축을 1 로")
줄더하기(M, 1, 0, 3)
줄더하기(M, 2, 0, 2)
보기(M, "R2 + 3R1, R3 + 2R1 — 첫 열의 아래를 0 으로")

🎮 한 단계씩 밟아 보세요

"다음 단계" 를 누를 때마다 소거가 한 번씩 진행되고, 무엇을 왜 했는지가 아래에 적힙니다. 어느 칸이 방금 0이 되었는지도 표시돼요. "해가 없음"과 "해가 무수히" 예제도 꼭 끝까지 돌려 보세요.

고등학생계단 꼴과 기약 계단 꼴

note 의 두 형태를 왜 나누는지 봅시다.

형태	모양	쓰임
계단 꼴 (REF)	아래를 0 으로	랭크 확인 · 후진대입
기약 계단 꼴 (RREF)	위아래 다 0 · 선두가 1	답이 바로 보인다 ✔

RREF 는 유일하다 — 어떤 순서로 해도 같은 결과

이 유일성이 중요합니다

결과	—
사람마다 계산 순서가 달라도	같은 RREF ✔
그래서	랭크·영공간이 잘 정의된다

12강의 랭크가 행렬의 성질이 될 수 있는 근거다

선두 성분 = 피벗

—	—
피벗의 개수	= 랭크 (12강) ⭐
피벗이 있는 열	= 독립인 열
피벗이 없는 열	= 자유변수 (15강)

계단 꼴 하나에서 12·14·15강의 답이 전부 나온다

비유 — 서류 정리

—	—
어지러운 서류 더미	원래 행렬
순서대로 정리	계단 꼴 — 구조가 보인다
중복을 없애고 표준화	RREF ✔

정리하면 없던 정보가 생기는 게 아니라 보이게 된다

피벗이 0 이면 어떡하나

축으로 삼으려는 자리가 0 이면 나눌 수 없습니다. 이때는 아래 줄과 자리를 바꿉니다(손놀림 ①). 바꿀 줄이 없다면? 그 열에는 축을 세울 수 없으니 다음 열로 넘어갑니다 — 이때 자유변수가 생겨요 (12강).

실제 컴퓨터는 한 걸음 더 나갑니다. 0이 아니어도 절댓값이 가장 큰 수를 축으로 골라 줄을 바꿉니다. 이것을 부분 피벗팅이라고 해요.

왜 그럴까요? 아주 작은 수로 나누면 오차가 크게 부풀기 때문입니다. 0.0001 로 나누면 원래 있던 작은 오차가 만 배가 되어 버려요. 수학적으로는 아무 수로 나눠도 되지만, 컴퓨터의 실수 계산에서는 큰 차이가 납니다.

수학적으로는 같아도, 컴퓨터에서는 나누는 수의 크기가 정확도를 좌우합니다.

Python 브라우저에서 실행

# 부분 피벗팅이 왜 필요한지 — 오차를 눈으로 봅니다
# 0.0001x + y = 1
#        x + y = 2
# 참값: x ≈ 1.0001, y ≈ 0.9999

def 풀기(축먼저바꾸기):
    M = [[0.0001, 1.0, 1.0],
         [1.0,    1.0, 2.0]]
    if 축먼저바꾸기:
        M[0], M[1] = M[1], M[0]
    배수 = M[1][0] / M[0][0]
    M[1] = [a - 배수 * b for a, b in zip(M[1], M[0])]
    y = M[1][2] / M[1][1]
    x = (M[0][2] - M[0][1] * y) / M[0][0]
    return x, y

x1, y1 = 풀기(False)
x2, y2 = 풀기(True)
print("작은 수를 축으로:  x =", x1, " y =", y1)
print("큰 수를 축으로  :  x =", x2, " y =", y2)
print()
print("참값에 가까운 쪽은? 큰 수를 축으로 고른 쪽입니다.")
print("이 예제는 오차가 작지만, 100x100 에서는 답이 통째로 망가지기도 합니다.")

고등학생얼마나 빠른가

note 의 비용 이야기를 다른 방법과 비교해 봅시다.

방법	비용	n=20 이면
가우스 소거법	n³/3	약 2,700 ✔
크래머 공식 (행렬식)	n!	2×10¹⁸ ⚠

교과서의 크래머 공식은 실제로 쓰지 않는다

n³ 이 어느 정도인가

n	연산 수	대략
100	33만	순간
1,000	3.3억	1초 미만
10,000	3300억	몇 분 ⚠

n 이 10배면 시간은 1000배 — 큰 문제에는 다른 방법이 필요하다

그래서 대규모 문제에서는

방법	—
반복법	근사해를 점점 개선한다
희소 행렬 활용	0 이 많으면 건너뛴다

현실 문제의 행렬은 대개 0 이 아주 많다 — 그걸 이용한다

⚠ 수치 안정성 — 피벗 고르기

0 에 가까운 수로 나누면 오차가 폭발합니다.

—	—
그냥 순서대로	위험 ⚠
절댓값이 큰 것을 피벗으로	안정 ✔ — 부분 피벗팅

수학적으로는 같은데 계산 정확도가 다르다 — /ca 3강의 실수 오차

소거법이 알려 주는 것들

소거법은 답만 주는 게 아닙니다. 끝까지 돌려 놓으면 이 행렬에 대한 거의 모든 것이 드러납니다.

소거 결과	알 수 있는 것
피벗의 개수	랭크 (12강)
피벗이 없는 열	자유변수 → 영공간의 차원 (15강)
[0 0 0 \| 5] 같은 줄	해가 없음
대각선의 곱	행렬식 (부호는 줄바꿈 횟수로)
[A \| I] 를 소거	오른쪽에 A⁻¹ 이 나타남

마지막 줄이 재미있습니다. A 옆에 단위행렬을 붙여 놓고 A 쪽을 I 로 만들면, 같은 손놀림을 받은 오른쪽이 저절로 A⁻¹ 이 됩니다. 역행렬을 구하는 실제 방법이 이거예요.

소거법 하나로 방정식도 풀고 역행렬도 구합니다.

Python 브라우저에서 실행

# [A | I] 를 소거해서 역행렬 구하기
def 역행렬(A):
    n = len(A)
    M = [행[:] + [1.0 if i == j else 0.0 for j in range(n)] for i, 행 in enumerate(A)]
    for c in range(n):
        축 = max(range(c, n), key=lambda i: abs(M[i][c]))
        if abs(M[축][c]) < 1e-12: return None
        M[c], M[축] = M[축], M[c]
        M[c] = [v / M[c][c] for v in M[c]]
        for i in range(n):
            if i != c and M[i][c] != 0:
                배수 = M[i][c]
                M[i] = [a - 배수 * b for a, b in zip(M[i], M[c])]
    return [행[n:] for 행 in M]

A = [[2, 1, 1],
     [1, 3, 2],
     [1, 0, 0]]
Ai = 역행렬(A)
for 행 in Ai:
    print([round(v, 4) for v in 행])
print()
곱 = [[round(sum(A[i][k]*Ai[k][j] for k in range(3)), 6) for j in range(3)] for i in range(3)]
print("A·A^-1 =", 곱, "← 단위행렬")

고등학생소거법이 알려 주는 것들

11강을 마치며 소거법의 부산물을 정리합시다.

한 번 소거하면 여러 답이 동시에 나온다

알 수 있는 것	어떻게	강
해	후진대입	10
랭크	피벗 개수	12
행렬식	대각 성분의 곱 (부호 주의)	8
역행렬	[A\|I] → [I\|A⁻¹]	9
영공간	자유변수로 표현	15
일차독립	피벗이 모든 열에 있나	14

계단 꼴 하나가 여섯 가지를 알려 준다 — 만능 도구다

왜 이렇게 많이 나오나

소거는 정보를 안 바꾸고 모양만 정리하기 때문입니다.

—	—
원래 행렬의 성질	그대로 남아 있다
다만	보기 쉬운 형태가 되었다 ✔

"보이게 만드는" 것이 이 방법의 전부다

비유 — X선 촬영

—	—
몸을 바꾸지 않는다	—
안이 보이게 한다	진단이 가능해진다 ✔

대상을 안 바꾸고 구조를 드러내는 것 — 좋은 도구의 조건이다

그래서 손으로 한 번은 해 보는 게 좋습니다. 무엇이 드러나는지 몸으로 알게 되니까요.

🤔 확인 문제

가우스 소거법에서 허용되지 않는 손놀림은?

🤔 확인 문제

소거 끝에 [0 0 0 | 7] 이라는 줄이 나왔습니다. 무슨 뜻인가요?

해설 그 줄을 식으로 읽으면 0 = 7 입니다. 어떤 값을 넣어도 성립할 수 없으니 해가 없어요. 서로 어긋나는 조건이 섞여 있었다는 뜻입니다.

🤔 확인 문제

컴퓨터가 절댓값이 가장 큰 수를 축으로 고르는 까닭은?