미적분 (Calculus)

정의

미적분 (Calculus) 은 함수의 변화율(미분)과 누적량(적분)을 다루는 수학 분야. 알고리즘 문제에서는 수치 미분 (Numerical Differentiation) 과 수치 적분 (Numerical Integration) 으로 주로 등장한다.

• 미분: 함수 f(x) 의 순간 변화율. f'(x) = lim_{h->0} (f(x+h) - f(x)) / h
• 적분: 함수 f(x) 의 정적분. ∫_a^b f(x) dx = lim_{N->∞} Σ f(x_i) Δx

PS 에서는 closed form 으로 미분/적분이 어려운 함수를 수치적으로 근사하는 테크닉이 중요.

문제 상황과 동기

“함수의 적분값 또는 미분계수를 O(N) 에 근사” 하고 싶다.

• naive Riemann sum: Σ f(x_i) Δx, 오차 O(1/N).
• Trapezoidal rule: 사다리꼴로 근사, 오차 O(1/N²).
• Simpson 1/3 rule: 2차 곡선 근사, 오차 O(1/N⁴).

핵심 통찰: 더 높은 차수의 근사법으로 같은 N 에서 더 정밀한 계산이 가능.

수치 미분은 central difference 로 O(h²) 정밀도로 O(1) 계산.

시각화

핵심 아이디어

수치 미분

전향(forward) / 중앙(central) / 후향(backward) 차분:

f'(x) ≈ (f(x+h) - f(x)) / h        # forward, O(h)
f'(x) ≈ (f(x) - f(x-h)) / h        # backward, O(h)
f'(x) ≈ (f(x+h) - f(x-h)) / (2h)   # central, O(h²)

Central difference 가 오차 1차 작음. h = ε^(1/2) ≈ 1e-8 (double) 권장.

수치 적분

Trapezoidal rule: 각 subinterval 을 선형(1차) 근사.

∫_a^b f(x) dx ≈ (Δx/2) · (f(x₀) + 2f(x₁) + ... + 2f(x_{N-1}) + f(x_N))

오차: -(b-a)h²/12 · f”(ξ).

Simpson 1/3 rule: 각 2개 interval 을 2차 곡선 근사 (N 짝수).

∫_a^b f(x) dx ≈ (Δx/3) · (f(x₀) + 4f(x₁) + 2f(x₂) + 4f(x₃) + ... + f(x_N))

오차: -(b-a)h⁴/180 · f⁴(ξ). 정밀도가 훨씬 높음.

알고리즘

numerical_derivative(f, x, h):
    return (f(x + h) - f(x - h)) / (2 * h)

simpson(f, a, b, n):    # n must be even
    h = (b - a) / n
    sum = f(a) + f(b)
    for i = 1 to n-1:
        if i % 2 == 1: sum += 4 * f(a + i * h)
        else:          sum += 2 * f(a + i * h)
    return sum * h / 3

구현

// Simpson 1/3 rule + central difference
// Integral of sin(x) from 0 to PI = 2
#include <bits/stdc++.h>
using namespace std;
​
double f(double x) { return sin(x); }
​
double derivative(double x, double h = 1e-8) {
  return (f(x + h) - f(x - h)) / (2 * h);
}
​
double simpson(double a, double b, int n) {
  if (n & 1) n++;
  double h = (b - a) / n;
  double sum = f(a) + f(b);
  for (int i = 1; i < n; i++) {
      double x = a + i * h;
      sum += (i & 1 ? 4 : 2) * f(x);
  }
  return sum * h / 3;
}
​
int main() {
  double a = 0, b = M_PI;
  int n = 100;
  cout << fixed << setprecision(10);
  cout << "Integral (Simpson): " << simpson(a, b, n) << "\n";
  cout << "Exact:              2.0000000000\n";
  cout << "Deriv at pi/4:      " << derivative(M_PI / 4) << "\n";
  cout << "cos(pi/4):          " << cos(M_PI / 4) << "\n";
}

# Simpson 1/3 rule + central difference
import math
​
def f(x):
  return math.sin(x)
​
def derivative(x, h=1e-8):
  return (f(x + h) - f(x - h)) / (2 * h)
​
def simpson(a, b, n):
  if n & 1:
      n += 1
  h = (b - a) / n
  s = f(a) + f(b)
  for i in range(1, n):
      x = a + i * h
      s += (4 if i & 1 else 2) * f(x)
  return s * h / 3
​
a, b, n = 0, math.pi, 100
print(f"Integral (Simpson): {simpson(a, b, n):.10f}")
print(f"Exact:              2.0000000000")
print(f"Deriv at pi/4:      {derivative(math.pi / 4):.10f}")
print(f"cos(pi/4):          {math.cos(math.pi / 4):.10f}")

// Simpson rule + central difference
import java.util.*;
import java.io.*;
​
public class Main {
  static double f(double x) { return Math.sin(x); }
​
  static double derivative(double x) {
      double h = 1e-8;
      return (f(x + h) - f(x - h)) / (2 * h);
  }
​
  static double simpson(double a, double b, int n) {
      if ((n & 1) == 1) n++;
      double h = (b - a) / n;
      double s = f(a) + f(b);
      for (int i = 1; i < n; i++) {
          double x = a + i * h;
          s += (i % 2 == 1 ? 4 : 2) * f(x);
      }
      return s * h / 3;
  }
​
  public static void main(String[] args) {
      double a = 0, b = Math.PI;
      int n = 100;
      System.out.printf("Integral (Simpson): %.10f%n", simpson(a, b, n));
      System.out.println("Exact:              2.0000000000");
      System.out.printf("Deriv at pi/4:      %.10f%n", derivative(Math.PI / 4));
      System.out.printf("cos(pi/4):          %.10f%n", Math.cos(Math.PI / 4));
  }
}

Integral (Simpson): 2.0000000000
Exact:              2.0000000000
Deriv at pi/4:      0.7071067812
cos(pi/4):          0.7071067812

복잡도

N = 구간 수, h = (b-a)/N.

변형 / 활용

함정

1. h 선택 (수치 미분)

h 가 너무 작으면 반올림 오차 (cancellation), 너무 크면 절단 오차. Central diff: h ≈ √ε ≈ 1e-8 (double).

2. Simpson rule 짝수 조건

Simpson 1/3 은 구간 N 이 짝수여야 함 (subinterval 2개씩 묶음). 홀수면 마지막 3구간을 3/8 rule 처리.

3. 진동 함수

고주파 진동 함수는 균등 분할로 정밀도 불충분. 구간당 주기 여러 번이면 실패.

4. 특이점

적분 구간 내 발산점이 있으면 수치 적분 불안정. Rombeg 또는 특수 변환 필요.

5. 부동소수점 누적

Summation 에서 큰 수 + 작은 수 순서로 인한 loss. Kahan summation 또는 고정밀 누적.

BOJ 연습 문제

참고

• 수치해석
• 테일러 급수
• 고속 푸리에 변환 (다항식 미분)