10 분 소요

이번 포스트는 수치해석 기말 범위 (ch09. PCA ~ 끝범위) 까지 다룬다.

1. PCA

Principal Component Analysis (PCA)

  • 고차원 데이터를 분산이 가장 큰 방향으로 정렬하거나 차원 축소에 사용하는 기법
  • 데이터를 선형 변환하여, 새로운 좌표계 (주성분)에 표현함
  • 데이터의 분포의 방향성, 분산 정보, 압축 가능성을 파악함.

Bounding Volume

  • 복잡한 객체를 감싸하는 단순한 형태의 부피
  • 종류
    • Axis-Aligned Bounding Box : 사각형 박스로, x/y/z 축에 표현에 적합
    • Oriented Bounding Box : PCA 기반 회전이 가능한 박스

Principal Components

  • 데이터의 분산이 가장 큰 방향을 정의하는 새로운 좌표축
  • 모든 PC는 원점에서 시작
    • 첫번 째 PC는 원점으로부터 최대 분산의 방향
    • Subsequent PC는 1st PC의 직교하게 다음 최대 분산 방향으로

PCA 절차 요약

  1. 평균 벡터 계산
    • 모든 점에서 중심 위치로 이동하기 위해 필요
\[\bar{P} = \frac{1}{N} \sum_{i=1}^{N} P_i\]

  1. 공분산 행렬 계산

    • 공분산 행렬이 3차원일 경우 3X3 행렬로, 각 좌표 축 간의 상관관계를 나낸다. \(C = \frac{1}{N} \sum_{i=1}^{N} (P_i - \bar{P}) (P_i - \bar{P})^T\)

  2. 공분산 행렬 값의 고유값 분해

    • 고육벡터 : 새로운 축 (주성분)
    • 고유값 (eigenvalues) : 각 축 방향의 분산 크기
\[C v_i = \lambda_i v_i\] \[\lambda_1 \ge \lambda_2 \ge \lambda_3\]
  1. 변환 행렬 구성
    • 고유 벡터를 행으로 정렬한 행렬을 구성
\[A = \begin{bmatrix} v_1^T \\ v_2^T \\ v_3^T \end{bmatrix}\]
  1. PCA 변환
    • 직교 좌표계로의 정렬
    • 원래 좔표를 평균 중심으로 이동후에 주성분 방향으로 정렬
\[P' = A (P - \bar{P})\]

차원 축소 (Dimensionality Reduction)

  • 분산이 큰 상위 k개의 고유 벡터만 사용하는 경우

  • 상위 k개의 주성분으로 구성된 행렬
  • 데이터 압축 및 특징 추출 가능
\[P' \approx A_k (P - \bar{P})\]

2. Decomposition

Triangular System

Forward Subsitution

  • 하삼각 행렬 시스템

  • 위에서 아래로 순차적으로 계산 \(Lx = r\)

BackWard Substitution

  • 상삼각 행렬 시스템

  • 아래에서 위로 역순으로 계산 \(Lx = r\)

LU Decomposition

  • 일반 행렬 M을 하삼각행렬 L과 상삼각행렬 U로 분해 \(M = LU\)

Doolittle’s Method

  • L은 대각선이 1인 하삼각행렬

  • U는 상삼각 행렬
  • 하나의 행렬에 L, U 정보를 함께 저장 가능

Error Correction

\[r_0 = r - Mx_0, Mx_1 = r_0, x = x_0 + x_1 + \dots\]

3. Iterative Methods

Jacobi Method

  • 반복적 해법 (Iterative Approximation)

  • 선형 시스템 AX = B를 행 기준으로 분리하여 반복적으로 해를 업데이트 한다.

  • 일반 수식 \(x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j \ne i} a_{ij} x_j^{(k)} \right)\)

    • 모든 x_j는 이전 반복의 값을 사용
    • 수렴 속도는 느림

Gauss-Seidel Method

  • 새로운 값을 바로 사용 : Jacobi Method 보다 빠르다.
  • 일반 수식
\[x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j < i} a_{ij} x_j^{(k+1)} - \sum_{j > i} a_{ij} x_j^{(k)} \right)\]
  • 위쪽의 새로운 값들과 아래쪽의 이전 값을 동시에 사용
  • 수렴 속도 개선

Convergence Condition

  • 행 기준 대각 우세 (Diagonal Dominance) 조건이면 수렴 보장:
\[|a_{ii}| > \sum_{j \ne i} |a_{ij}|\]

Relaxation (이완 기법)

  • Gauss-Seidel에 λ 계수 적용:
\[x_i^{(k+1)} = \lambda x_i^{(k+1)} + (1 - \lambda)x_i^{(k)} \quad \text{for } 0 < \lambda < 2\]
  • lambda = 1 → 기본 Gauss-Seidel
  • 0 < λ < 1 → Under-relaxation
  • 1 < λ < 2 → Over-relaxation

4. Interpolation

Interpolation 이란?

  • 주어진 점들 (x,y)을 지나는 함수를 찾는 과정
  • Interpolation 구간 안의 미지점에서 추정, 즉 반대로 구간 밖은 Extrapolation

Linear Interpolation (선형 보간법)

  • 두 점 (x_0, y_0), (x_1, y_1) 사이 직선 보간
\[y(x) = y_0 + \frac{y_1 - y_0}{x_1 - x_0} (x - x_0)\]
  • LERP: 점 x가 아닌 비율 (0과 1사이)로 표현
\[P(t) = (1 - t) \cdot x_0 + t \cdot x_1\]

Quadratic Interpolation (2차 보간법)

  • 세 점 (x_0, y_0), (x_1, y_1), (x_2, y_2)를 지나는 2차 다항식 P(x) 구하기

  • Lagrange Interpolation (기본형) 식

\[P(x) = \sum_{i=0}^2 y_i \cdot L_i(x)\] \[L_0(x) = \frac{(x - x_1)(x - x_2)}{(x_0 - x_1)(x_0 - x_2)} \quad \text{(기타 $L_1(x), L_2(x)$도 유사)}\]

Higher Degree Interpolation

  • n + 1개의 점 -> n차 다항식

  • 점점 에러가 줄어들기는 하지만 항상 줄어드는 것은 아니다.

  • 보간식 : \(P(x) = \sum_{i=0}^n y_i \cdot L_i(x)\)

Newton Polynomials

  • 재귀적 방식

  • 새로운 점 추가 시에 기존 다항식에 누적 가능하다.

  • 일반 형태 \(P(x) = a_0 + a_1(x - x_0) + a_2(x - x_0)(x - x_1) + \dots\)

  • 계수 계산 \(a_1 = \frac{f(x_1) - f(x_0)}{x_1 - x_0}\)

    \[a_2 = \frac{f[x_2, x_1] - f[x_1, x_0]}{x_2 - x_0}\]

Spherical Linear Interpolation (SLERP)

  • 두 단위 벡터 사이의 구면 상 보간
  • 선형 보간보다는 회전 축 보존에 적합하다.
\[\text{Slerp}(q_1, q_2; t) = \frac{\sin((1 - t) \theta)}{\sin(\theta)} q_1 + \frac{\sin(t \theta)}{\sin(\theta)} q_2\]
  • theta: 두 벡터 사이의 각도

Bilinear Interpolation

  • 사각형 네 꼭짓점 (x,y) 상에서 추정
\[f(x, y) = f_{00}(1 - u)(1 - v) + f_{10} u(1 - v) + f_{01}(1 - u)v + f_{11}uv\]

Trilinear Interpolation

  • 3D 큐브 내 보간 (8개 점)
  • 각 방향에 대해 선형 보간 → x to y to z 순서

5. Least-Squares

Least-Squares 란?

  • 주어진 데이터 (x_i, y_i)에 대해서 가장 잘 맞는 함수를 찾는 방법

  • 잘 맞는다의 기준은 오차 제곱합을 최소화하는 것

  • 오차의 정의
\[e_i = y_i - f(x_i)\]
  • 오차를 측정하는 방법:
    • 최대 오차 (Max error)
    • 평균 오차 (Average error)
    • RMS 오차 (Root-Mean-Square error) → 주로 사용
\[\text{RMS} = \sqrt{ \frac{1}{n} \sum_{i=1}^n e_i^2 }\]

Least-Squares Line

  • 직선을 찾기 (아래의 형태) \(f(x) = ax + b\)

  • 목적

\[\min_{a, b} \sum_{i=1}^n (y_i - (ax_i + b))^2\]
  • 최적 조건: 오차 제곱합의 편미분이 0일 때
\[\frac{\partial E}{\partial a} = 0, \quad \frac{\partial E}{\partial b} = 0\]
  • 결과 선형 시스템
\[\begin{bmatrix} \sum x_i^2 & \sum x_i \\ \sum x_i & n \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} \sum x_i y_i \\ \sum y_i \end{bmatrix}\]

Power Fit

  • 아래의 함수 형태로 Fitting
\[f(x) = Ax^M\]
  • 목적
\[\min_A \sum_{i=1}^n \left( y_i - Ax_i^M \right)^2\]
  • Linearization 가능
\[\ln y = \ln A + M \ln x\]

→ 선형 Least-Squares로 변환 가능

Data Linearization (데이터 선형화)

  • 비선형 모델을 선형으로 변환 후에 선형 Least - Squares 적용
  • 양변에 로그를 적용함.

Linear Least - Squares

  • 일반 선형 형태
\[y = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n\]
  • 목적
\[\min \sum_{i=1}^n \left( y_i - \sum_{j=0}^n a_j x_i^j \right)^2\]
  • 선형 시스템으로 변환 가능 → 행렬 형태로 풀이

Polynomial Fitting

  • n차 다항식으로 Least-Squares 수행하기

  • 2차 예시

\[y = a x^2 + b x + c\]
  • 역시 선형 시스템으로 변환해서 풀이 가능

Nonlinear Least- Squares

  • 비선형 모델 y= f(x; A, C) 에 대해서
\[\min_{A, C} \sum_{i=1}^n \left( y_i - f(x_i; A, C) \right)^2\]
  • Partial Derivatives 를 이용해 최적화
\[\frac{\partial E}{\partial A} = 0, \quad \frac{\partial E}{\partial C} = 0\]
  • 일반적으로 Newton’s Method 또는 수치적 최적화 기법으로 해결

6. Optimization

Optimiazation 개념

  • 목적 : 함수 f(x)의 극값(최소 or 최대) 위치 x = p 찾기
  • 지역 최소 :
\[\exists I \text{ such that } f(p) \leq f(x), \forall x \in I\]
  • 지역 최대:
\[\exists I \text{ such that } f(p) \geq f(x), \forall x \in I\]

극값 판정법

First Derivative Test

  • f'(p) = 0 -> 임계점 (critcial Point)
  • 부호 변화에 따라서 최대 / 최소를 판정

Second Derivative Test

  • f''(p) > 0 (local minimum)
  • f''(p) < 0 (local maximum)

Bracketing Search Methods

  • 구간 [a,b]를 점점 좁혀 나가면서 local extremum을 찾는다
  • 반복적으로 함수 평가 횟수 최소화를 목표로 한다.
  • unimodal 함수에 적용 (극값이 하나만 존재함.)
  • 두 내부점 c, d를 선택한다.
\[d - a = b - c\]

→ [a, d] 또는 [c, b] 중 하나로 갱신

  • Golden Ratio 비율
\[r = \frac{b - c}{b - a} = \frac{d - a}{b - a}\]

  • 장점

    • 이전 구간의 내부점을 다음 구간에서 재활용 가능

    • 평가 효율 높음

  • Golden Ratio Search와 유사하지만:

    • 사전 정의된 반복 횟수(n) 기반으로 진행
    • r 값이 고정이 아님 → Fibonacci 수열에 따라 변화

  • Fiabonacci 수열

\[F_0 = 0, \quad F_1 = 1, \quad F_{n} = F_{n-1} + F_{n-2}\]
  • 내부점 계산
    • [a_k, b_k] 구간에서 내부점 c_k, d_k:
\[c_k = a_k + \frac{F_{n - k - 1}}{F_{n - k + 1}} (b_k - a_k)\] \[d_k = a_k + \frac{F_{n - k}}{F_{n - k + 1}} (b_k - a_k)\]

  • 특징

    • 고정된 반복 횟수로 종료 시점 명확

    • 최종 구간 길이:

\[L_n \leq \frac{b - a}{F_n}\]

7. Multidimensional Unconstrained Optimization

Optimization 목적

  • 다변수 함수의 극값을 찾는 방법
  • 주요 기법

Direct Method

  • 임의의 점 f(x) 평가를 반복하여 최적의 점을 탐색한다.
  • 장점 : 비연속 함수, 미분 불가능한 함수에도 사용이 가능하다.
  • 단점 : 비효율적이고 변수 수가 많아지면 어렵다.

Univariate & Pattern Searches

  • 한 번에 하나의 변수만 변경 (나머지는 고정)
  • 일련의 1D 최적화 문제로 환원하여 반복
  • 근처로 갈수록 비효율적

Gradient Method

  • 미분을 이용한다.

  • Gradient 벡터 (기울기 벡터)

\[\nabla f = \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{bmatrix}\]
  • 방향: 가장 큰 증가 방향 (steepest ascent)
  • 크기: 그 방향으로의 증가율

Optimum Point 판정

1D \(f'(x) = 0\)

\[f''(x) < 0 -> 최댓값\] \[f''(x) > 0 -> 최솟값\] \[f''(x) = 0 -> saddle point 가능성이 있다.\]

2D

  • 임계점

  • 2차 미분을 이용한 판정 필요 → Hessian Matrix 사용

Hessian Matrix

\[H = \begin{bmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{bmatrix}\]

  • 판정 기준

  • |H| > 0$ and $f_{xx} > 0 → 최소점
  • |H| > 0$ and $f_{xx} < 0 → 최대점
  • |H| < 0 → saddle point

Finite Difference Approxiamation

  • 편미분 직접 계산이 어려울 때 중심차분법을 사용한다.
\[\frac{\partial f}{\partial x} \approx \frac{f(x+h, y) - f(x-h, y)}{2h}\] \[\frac{\partial^2 f}{\partial x^2} \approx \frac{f(x+h, y) - 2f(x, y) + f(x-h, y)}{h^2}\]

Steepest Ascent

  • 알고리즘
    • 초기점 x_0를 선택하고
    • Nabla f를 계산하여 최적의 상승 방향을 찾는다.
    • h를 찾아서 이동한다.
    • 수렴할 대까지 반복한다.
\[x_{i+1} = x_i + h \cdot \nabla f\]
  • 수렴 속도 : 선형 수렴 (linear convergence)

8. Nonlinear Equations

Bisection Method (이분법)

  • 조건 \(f(x_l) \cdot f(x_u) < 0 (초기 구간 [x_l, x_u]에서 부호가 바뀜)\)

  • 수렴 보장 (언제나 수렴), 속도 느림

  • 알고리즘

    1. 중간점 계산:
\[x_m = \frac{x_l + x_u}{2}\]

  1. f(x_m) 판정: \(f(x_l) \cdot f(x_m) < 0 → x_u = x_m\)

    \[f(x_l) \cdot f(x_m) > 0 → x_l = x_m\] \[f(x_m) = 0 → x_m\]

  2. 오차 계산:

\[\varepsilon_a = 100 \times \left| \frac{x_{\text{new}} - x_{\text{old}}}{x_{\text{new}}} \right|\]
  1. 오차가 허용 오차보다 작으면 종료

Newton-Raphson Method

  • 수렴이 빠르고, 초기에 하는 guess가 중요하다.
  • 알고리즘
\[x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}\]
  • 장점: 매우 빠름 (quadratic convergence)
  • 단점: 발산 가능, f'(x_i) = 0 이면 실패

Secant Method

  • Newton 방법에서 f'(x)를 근사치로 대체
  • 알고리즘
\[x_{i+1} = x_i - \frac{f(x_i) (x_i - x_{i-1})}{f(x_i) - f(x_{i-1})}\]
  • 장점: 미분 계산 불필요, 빠름
  • 단점: 수렴 실패 가능, 두 초기 guess 필요

Simple Fixed-Point Iteration

  • 형태로 변환:
\[x = g(x)\]
  • 알고리즘
\[x_{k+1} = g(x_k)\]
  • 수렴 조건: |g'(x)| < 1 일 때 수렴 (선형 수렴)

Fixed-Point Iteration

  • u(x, y) = 0, v(x, y) = 0 시스템을 다음과 같이 재정의:
\[x = g_1(x, y), \quad y = g_2(x, y)\]
  • 초기 guess (x_0, y_0)로 시작하여 반복

Multi-diemensional Newton-Raphson

  • 다변수 Taylor 전개 기반

  • 1차 근사

\[\begin{bmatrix} u_{i+1} \\ v_{i+1} \end{bmatrix} = \begin{bmatrix} u_i \\ v_i \end{bmatrix} + J^{-1} \begin{bmatrix} - u(x_i, y_i) \\ - v(x_i, y_i) \end{bmatrix}\]
  • Jacobian Matrix
\[J = \begin{bmatrix} \frac{\partial u}{\partial x} & \frac{\partial u}{\partial y} \\ \frac{\partial v}{\partial x} & \frac{\partial v}{\partial y} \end{bmatrix}\]
  • Update Step
\[\begin{bmatrix} x_{i+1} \\ y_{i+1} \end{bmatrix} = \begin{bmatrix} x_i \\ y_i \end{bmatrix} - J^{-1} \begin{bmatrix} u(x_i, y_i) \\ v(x_i, y_i) \end{bmatrix}\]
  • 수렴 빠름
  • Jacobian 계산 필요
  • 초기 guess 민감

9. Differential Equations

Euler’s Method

  • 매우 단순한 1차 ODE 근사법

  • 알고리즘

    • 초기 조건 \(y(x_0) = y_0\)
\[x_{i+1} = x_i + h\] \[y_{i+1} = y_i + h \cdot f(x_i, y_i)\]
  • h: step size

Taylor Series Method

\[y(x+h) 근사\] \[y(x+h) = y(x) + h y'(x) + \frac{h^2}{2!} y''(x) + \dots\]
  • k=1일 경우 Euler와 동일

Runge-Kutta Method

  • 고정도 ODE 해법으로 실무에서 가장 많이 사용
  • RK2 (Second order)
\[k_1 = h \cdot f(x_i, y_i)\] \[k_2 = h \cdot f(x_i + \alpha h, y_i + \beta k_1)\] \[y_{i+1} = y_i + w_1 k_1 + w_2 k_2\]
  • RK4 (Fourth order)
\[k_1 = h f(x_i, y_i)\] \[k_2 = h f(x_i + \frac{h}{2}, y_i + \frac{k_1}{2})\] \[k_3 = h f(x_i + \frac{h}{2}, y_i + \frac{k_2}{2})\] \[k_4 = h f(x_i + h, y_i + k_3)\] \[y_{i+1} = y_i + \frac{1}{6}(k_1 + 2k_2 + 2k_3 + k_4)\]

Higher Order Differential Equations

  • n차 미분 방정식
\[y^{(n)} = f(x, y, y', \dots, y^{(n-1)})\]
  • 벡터 형태로 변환 후 Euler, RK 등 사용 가능

Systems of Equations

  • 여러 ODE 동시 해석:
\[\frac{dy_1}{dx} = f_1(x, y_1, y_2, \dots, y_n)\] \[\frac{dy_2}{dx} = f_2(x, y_1, y_2, \dots, y_n)\]

→ 각 식에 대해 Euler, RK 사용 가능

Initial Value Problem

  • 모든 조건이 동일한 x에서 주어진다.

Boundary Value Problem

  • 조건이 서로 다른 x 위치에서 주어진다.

Shooting Method

  • BVP -> IVP로 변환

  • 과정

  1. 초기 기울기 guess (y'(0)) 선택
  2. IVP로 적분 (ex: RK4 사용)
  3. 결과가 목표 y(L)과 차이나면 y'(0) 수정 → 반복
  • 비선형 ODE에서는 Root Finding Problem으로 변환 가능

Finite - Deifference Method

  • 미분 → 유한차분 근사 후 선형 방정식 시스템으로 변환

  • 중앙 차분

\[\frac{d^2 T}{dx^2} \approx \frac{T_{i+1} - 2T_i + T_{i-1}}{(\Delta x)^2}\]
  • 방정식 전체를 행렬 형태로 변환:
\[[A] \{T\} = \{b\}\]
  • 경계조건 (T_0, T_n)은 RHS로 이동

참고

Concurrency, Locks

8 분 소요

이번 포스트는 OS의 Concurrency와 Locks에 대해 다룬다.