수학에서는 정확한 값을 계산할 수 있는 경우가 많다.
하지만 컴퓨터에서는 이야기가 다르다.
컴퓨터가 다루는 숫자는 유한한 정밀도를 가지고 있고, 복잡한 함수의 해를 항상 정확하게 계산할 수도 없다.
그래서 실제 프로그램에서는
수학적 문제 -> 근사 방법 -> 수치 계산 -> 오차가 있는 결과
라는 과정을 거치는 경우가 많다.
이런 문제를 다루는 분야가 수치해석(Numerical Analysis) 이다.
게임 개발에서도 상당히 중요하다.
물리 시뮬레이션, 충돌 판정, 보간, 애니메이션, 경로 계산, 최적화, 그래픽스 등에서 수치해석의 개념을 사용한다.
수치해석의 핵심
수치해석에서 가장 중요한 것은 정확한 답을 구하는 것보다 필요한 정확도의 답을 안정적으로 구하는 것이다.
문제
-> 수학적 모델
-> 근사 알고리즘
-> 반복 계산
-> 오차 측정
-> 충분한 정확도에서 종료
따라서 수치해석에서는 다음 네 가지를 계속 확인한다.
정확도
안정성
수렴성
계산 비용
근사
수학적으로 정확한 값을 구하기 어려운 경우 근사값을 사용한다.
예를 들어
π = 3.14159265...
를 컴퓨터에서 무한히 저장할 수는 없다.
따라서 특정 정밀도에서 잘라 사용한다.
π ≈ 3.14159
게임에서도 대부분의 계산 결과는 어떤 의미에서는 근사값이다.
오차
계산한 값과 실제 값의 차이를 오차라고 한다.
실제값을 x, 근사값을 x̂라고 하면 절대 오차는
absolute error = |x - x̂|
이다.
상대 오차는
relative error = |x - x̂| / |x|
이다.
절대 오차는 실제 값의 크기를 고려하지 않지만 상대 오차는 값의 크기에 대한 오차 비율을 나타낸다.
절단 오차
무한히 이어지는 수학적 계산을 일정 부분에서 잘라내면서 발생하는 오차다.
예를 들어
1 + 1/2 + 1/4 + 1/8 + ...
같은 무한한 계산을 컴퓨터에서 전부 수행할 수 없다.
따라서
1 + 1/2 + 1/4 + 1/8
까지만 계산한다.
이때 생기는 차이가 절단 오차다.
반올림 오차
컴퓨터가 숫자를 유한한 비트로 표현하기 때문에 발생하는 오차다.
대표적인 것이 부동소수점이다.
float
double
같은 자료형은 모든 실수를 정확하게 표현할 수 없다.
예를 들어 우리가 생각하는
0.1
이라는 숫자가 이진수에서는 정확하게 표현되지 않는 경우가 있다.
따라서
0.1 + 0.2
의 결과가 수학적으로 생각하는 정확한 0.3과 내부적으로 미세하게 다를 수 있다.
부동소수점
게임 개발에서는 float를 매우 많이 사용한다.
대표적으로
float speed = 5.0f;
float deltaTime = Time.deltaTime;
같은 코드가 있다.
문제는 float가 유한한 정밀도를 가진다는 것이다.
따라서 다음처럼 직접 비교하는 것은 위험할 수 있다.
if (value == 0.3f)
{
}
실제 계산 과정에서 미세한 오차가 발생할 수 있기 때문이다.
대신 허용 오차를 두고 비교하는 방법을 사용할 수 있다.
if (MathF.Abs(a - b) < epsilon)
{
}
핵심은
실수 -> 정확한 값이라고 가정하지 않음
이다.
오차 전파
계산 과정에서 발생한 오차가 다음 계산으로 전달될 수 있다.
입력 오차
-> 계산
-> 출력 오차
-> 다음 계산의 입력
-> 더 큰 오차
특히 게임 물리나 장시간 실행되는 시뮬레이션에서는 작은 오차가 계속 누적될 수 있다.
그래서 수치 계산에서는 단순히 현재 오차만 보는 것이 아니라 시간에 따른 오차의 증가도 확인해야 한다.
안정성
수치 알고리즘이 작은 입력 오차에 얼마나 민감한지를 생각해야 한다.
입력에 아주 작은 변화가 있었는데 결과가 크게 변한다면 해당 문제나 알고리즘은 민감한 것이다.
작은 입력 오차
-> 작은 결과 변화
라면 비교적 안정적이고,
작은 입력 오차
-> 큰 결과 변화
라면 불안정할 수 있다.
게임에서는 작은 부동소수점 오차가 충돌이나 물리 계산에서 큰 차이를 만들어낼 수 있기 때문에 중요하다.
수렴
반복 계산을 통해 어떤 값에 점점 가까워지는 것을 수렴이라고 한다.
예를 들어
1
1.5
1.75
1.875
1.9375
...
처럼 어떤 값에 가까워진다면 수렴하고 있다고 볼 수 있다.
수치해석에서는
초기값
-> 반복 계산
-> 오차 감소
-> 목표값에 접근
의 구조가 자주 등장한다.
반복법
정확한 해를 한 번에 계산하지 않고 반복적으로 근사하는 방법이다.
x₀ -> x₁ -> x₂ -> x₃ -> ...
충분히 반복해서 원하는 오차 범위 안에 들어오면 종료한다.
while (error > tolerance)
{
x = next(x);
}
게임에서도 반복적인 물리 계산이나 최적화 과정에서 비슷한 구조를 사용한다.
이분법
방정식
f(x) = 0
의 해를 찾는 대표적인 방법이다.
구간 [a,b]에서 함수의 부호가 바뀐다면 중간값을 계산하고 해가 어느 쪽에 있는지 반복해서 좁혀간다.
[a ---------------- b]
|
middle
과정을 반복하면서
[a,b]
-> [a,m]
-> [a,m2]
-> ...
처럼 구간을 줄인다.
장점은 안정적이라는 것이다.
단점은 수렴 속도가 빠르지 않다는 것이다.
뉴턴 방법
뉴턴 방법(Newton-Raphson Method)은 함수의 접선을 이용해서 해를 빠르게 찾는 방법이다.
기본 공식은
xₙ₊₁ = xₙ - f(xₙ) / f'(xₙ)
이다.
구조는
초기값
-> 함수값 / 기울기 계산
-> 새로운 x 계산
-> 반복
이다.
조건이 좋다면 매우 빠르게 수렴한다.
하지만 초기값이 좋지 않거나 함수의 형태가 좋지 않으면 발산하거나 잘못된 해로 갈 수도 있다.
따라서 빠른 알고리즘이 항상 안정적인 알고리즘은 아니다.
선형 보간
두 점 사이의 값을 직선으로 추정하는 방법이다.
두 값 a, b와 t가 있을 때
Lerp(a,b,t) = a + (b-a)t
이다.
t = 0 -> a
t = 0.5 -> 중간값
t = 1 -> b
게임 개발에서는 매우 많이 사용한다.
float value = Mathf.Lerp(a, b, t);
색상, 위치, 회전, UI, 애니메이션 등 다양한 곳에서 사용한다.
보간과 외삽
보간(Interpolation)은 알고 있는 값 사이의 값을 추정하는 것이다.
A ---- ? ---- B
외삽(Extrapolation)은 알고 있는 범위 밖의 값을 추정한다.
? ---- A ---- B
외삽은 현재 데이터의 추세가 계속된다고 가정하기 때문에 오차가 커질 가능성이 높다.
게임 네트워크에서 보간과 외삽은 특히 중요하다.
서버 상태
-> 클라이언트 수신
-> 보간
-> 부드러운 화면 출력
수치 미분
미분을 정확한 공식으로 계산하지 않고 함수값을 이용해서 근사할 수 있다.
가장 단순한 전진 차분은
f'(x) ≈ [f(x+h) - f(x)] / h
이다.
중앙 차분은
f'(x) ≈ [f(x+h) - f(x-h)] / 2h
이다.
중앙 차분은 같은 h에서 전진 차분보다 정확도가 높은 경우가 많다.
수치 적분
적분도 근사할 수 있다.
대표적인 방법이 사다리꼴 공식이다.
두 점의 함수값을 이용해 넓이를 사다리꼴로 근사한다.
∫[a,b] f(x)dx
≈ (b-a)(f(a)+f(b))/2
구간을 여러 개로 나누면 더 정확하게 근사할 수 있다.
전체 구간
-> 작은 구간으로 분할
-> 각각의 넓이 계산
-> 모두 합산
오일러 적분
게임 물리에서 매우 중요한 수치 적분 방법이다.
가속도를 알고 있다면
v(t + dt) = v(t) + a(t)dt
위치를
x(t + dt) = x(t) + v(t)dt
로 계산할 수 있다.
코드로 보면
velocity += acceleration * deltaTime;
position += velocity * deltaTime;
와 같은 형태다.
수식 자체는 단순하지만 deltaTime이 크거나 계산이 불안정하면 오차가 커질 수 있다.
고정 시간 간격
물리 시뮬레이션에서는 일정한 시간 간격으로 계산하는 것이 중요할 수 있다.
Update
-> 가변 deltaTime
FixedUpdate
-> 고정된 시간 간격 기반 물리 계산
시간 간격이 계속 변하면 수치 적분 결과도 달라질 수 있다.
따라서 물리 계산에서는 고정 시간 간격을 사용해 시뮬레이션의 안정성을 높이는 방법이 흔하다.
오일러 방법의 문제
오일러 방법은 간단하지만 정확하지 않다.
시간 간격이 크면 오차가 커질 수 있고, 특정 물리 시스템에서는 에너지가 계속 증가하거나 감소하면서 시뮬레이션이 불안정해질 수 있다.
그래서 다양한 적분 방법이 존재한다.
Euler
-> Semi-Implicit Euler
-> Verlet
-> Runge-Kutta
등이 있다.
각 방법은 정확도, 안정성, 계산 비용이 다르다.
반암시적 오일러
게임 물리에서 자주 언급되는 방법이다.
먼저 속도를 업데이트하고 그 새로운 속도를 이용해서 위치를 업데이트한다.
v = v + a * dt
x = x + v * dt
일반적인 오일러 방식과 비교했을 때 특정 물리 시스템에서 더 안정적인 특성을 가질 수 있다.
Verlet Integration
Verlet 적분은 위치 기반으로 계산하는 방식이다.
대표적인 형태는
xₙ₊₁ = 2xₙ - xₙ₋₁ + aₙdt²
이다.
현재 위치와 이전 위치를 이용한다.
물리 시뮬레이션, 파티클, 로프, 천 등의 구현에서 활용되는 방식이다.
Runge-Kutta
Runge-Kutta 방법은 한 번의 시간 간격에서 여러 지점의 기울기를 평가해서 더 정확한 결과를 얻는다.
대표적인 것이 RK4다.
k1 -> k2 -> k3 -> k4 -> 결과 계산
오일러 방법보다 계산량은 많지만 일반적으로 훨씬 높은 정확도를 얻을 수 있다.
다만 게임에서는 항상 가장 정확한 방법을 사용하는 것이 좋은 것은 아니다.
정확도
vs
계산 비용
사이에서 적절한 방법을 선택해야 한다.
방정식의 수치해
어떤 방정식은 해를 공식으로 구하기 어렵다.
예를 들어
f(x) = 0
을 만족하는 x를 찾아야 한다면
이분법
뉴턴 방법
할선법
등을 사용할 수 있다.
게임에서도 특정 조건을 만족하는 시간이나 위치를 찾아야 하는 경우 이런 문제로 바꿔 생각할 수 있다.
선형 시스템
여러 개의 선형 방정식을 동시에 풀어야 하는 경우가 있다.
a₁x + b₁y = c₁
a₂x + b₂y = c₂
이것은 행렬을 이용해서
Ax = b
형태로 표현할 수 있다.
수치해석에서는 이런 선형 시스템을 효율적이고 안정적으로 푸는 방법도 중요하다.
대표적으로
Gaussian Elimination
LU Decomposition
Jacobi Method
Gauss-Seidel Method
Conjugate Gradient
등이 있다.
게임 물리, 그래픽스, 최적화 등에서 사용될 수 있다.
조건수
어떤 문제는 입력값의 작은 오차가 결과에 크게 영향을 미친다.
이런 문제의 민감도를 나타내는 개념이 조건수(Condition Number)다.
조건수가 크면 일반적으로
작은 입력 오차
-> 큰 결과 오차
가 발생할 가능성이 높다.
따라서 알고리즘 자체가 아무리 정확해도 문제 자체가 민감하다면 결과의 정확도에 한계가 생길 수 있다.
안정성과 정확도
두 개념은 다르다.
정확도는 결과가 실제 값에 얼마나 가까운지를 의미한다.
안정성은 계산 과정에서 작은 오차가 얼마나 통제되는지를 의미한다.
정확도 -> 결과의 품질
안정성 -> 계산 과정의 견고함
실제 프로그램에서는 둘을 같이 봐야 한다.
정확하지만 불안정한 알고리즘보다 약간 덜 정확하더라도 안정적이고 빠른 알고리즘이 더 적합한 경우가 많다.
수치해석과 게임 물리
게임 물리를 단순하게 보면
힘
-> 가속도
-> 속도
-> 위치
라는 연속적인 수학 모델이 존재한다.
하지만 컴퓨터에서는 이를 프레임이나 고정 시간 간격으로 나눠 계산한다.
연속적인 물리 모델
-> 시간 discretization
-> 수치 적분
-> 위치 / 속도 업데이트
-> 다음 시간 구간
따라서 게임 물리 엔진을 이해하려면 미적분뿐 아니라 수치해석도 알아야 한다.
수치해석과 충돌
충돌 판정에서도 근사가 등장한다.
예를 들어 두 물체의 위치를 일정 시간 간격으로만 확인하면
Frame A -> 충돌 없음
Frame B -> 충돌 없음
으로 나왔지만 실제로는 두 프레임 사이에서 서로 통과했을 수 있다.
이런 문제가 터널링(Tunneling) 이다.
이를 해결하기 위해
Continuous Collision Detection
Swept Collision
Substep
등의 방법을 사용할 수 있다.
즉 시간 간격을 어떻게 나누느냐 자체가 결과에 영향을 줄 수 있다.
수치해석과 최적화
최적화 문제에서도 반복적인 수치 계산이 사용된다.
예를 들어 함수의 최소값을 찾는다면
목표 함수
-> Gradient 계산
-> 이동
-> 새로운 위치
-> 다시 계산
을 반복할 수 있다.
대표적으로 Gradient Descent가 있다.
xₙ₊₁ = xₙ - α∇f(xₙ)
여기서 α는 학습률 또는 이동 크기다.
너무 크면
최솟값을 지나침
-> 발산 가능
하고,
너무 작으면
수렴
-> 매우 느림
이 될 수 있다.
시간 복잡도와 수치 계산
수치적으로 더 정확한 방법은 일반적으로 더 많은 계산을 요구한다.
예를 들어 적분 구간을
10개
-> 100개
-> 1000개
로 세분화하면 일반적으로 근사 정확도는 높아지지만 계산량도 증가한다.
따라서 실제 게임에서는
정확도
+ 안정성
+ 성능
을 동시에 고려해야 한다.
결정론적 시뮬레이션
멀티플레이 게임이나 리플레이 시스템에서는 같은 입력에 대해 같은 결과가 나오는 것이 중요할 수 있다.
Input
-> Simulation
-> State
가 항상 동일한 결과를 만들어야 한다.
하지만 부동소수점 연산의 차이, 플랫폼 차이, 연산 순서 차이 등으로 결과가 조금씩 달라질 수 있다.
이 때문에 결정론적 시뮬레이션에서는
고정 timestep
수치 연산 통제
동일한 연산 순서
난수 Seed 관리
등이 중요해진다.
수치해석의 전체 구조
수치해석은 크게 다음 구조로 볼 수 있다.
수학적 문제
-> 정확한 해가 어려움
-> 근사 알고리즘 선택
-> 반복 계산
-> 오차 측정
-> 수렴 확인
-> 결과 사용
게임 개발에서는
물리 모델
-> 수치 적분
-> 오차 누적
-> 안정성 관리
-> 게임 상태 업데이트
로 연결된다.
그래픽스에서는
수학적 함수
-> 근사 계산
-> 보간
-> 샘플링
-> 화면 출력
으로 이어진다.
최적화에서는
목표 함수
-> Gradient / 수치 탐색
-> 반복
-> 수렴
-> 최적값 근사
가 된다.
핵심 정리
수치해석에서 중요한 개념은 다음과 같다.
근사
-> 정확한 해 대신 충분히 정확한 값을 계산
오차
-> 실제값과 근사값의 차이
절단 오차
-> 계산을 중간에 끊어서 발생하는 오차
반올림 오차
-> 유한한 숫자 표현으로 발생하는 오차
수렴
-> 반복 계산 결과가 특정 값에 가까워지는 현상
안정성
-> 계산 중 오차가 폭발하지 않는 특성
보간
-> 알려진 값 사이의 값을 추정
수치 미분
-> 함수값으로 변화율을 근사
수치 적분
-> 함수의 누적값을 근사
이분법
-> 구간을 반복적으로 줄여 해를 찾음
뉴턴 방법
-> 기울기를 이용해 해를 빠르게 탐색
오일러 적분
-> 가장 단순한 수치 적분 방법 중 하나
Verlet
-> 이전 위치와 현재 위치를 이용한 적분 방법
Runge-Kutta
-> 여러 기울기를 이용해 정확도를 높이는 방법
수치해석에서 가장 중요한 사고방식은 계산 결과를 무조건 정확한 값이라고 믿지 않는 것이다.
컴퓨터에서 계산되는 값에는 정밀도의 한계가 있고, 알고리즘에는 근사 오차가 있으며, 반복 계산에서는 오차가 누적될 수 있다.
그래서 실제 개발에서는
정확한가?
-> 얼마나 오차가 있는가?
-> 오차가 누적되는가?
-> 안정적인가?
-> 계산 비용은 감당 가능한가?
를 같이 판단해야 한다.
결국 수치해석은 수학적 모델을 컴퓨터에서 실제로 계산 가능한 형태로 바꾸는 기술이라고 볼 수 있다.
현실의 문제
-> 수학적 모델
-> 수치적 근사
-> 컴퓨터 계산
-> 오차 관리
-> 실제 시스템
게임 개발에서는 이 과정이 물리 엔진, 애니메이션, 그래픽스, AI, 네트워크 시뮬레이션까지 광범위하게 연결된다.