최소 제곱 문제 해결 - 실험 도서관

최소 제곱 문제는 주어진 데이터로부터 가장 잘 맞는 모델을 찾는 문제로, 선형 회귀 분석에서 흔히 나타난다. 이 과정에서 QR 분해는 중요한 역할을 하며, 수치적으로 안정적이고 효율적인 방법을 제공한다. QR 분해를 사용하여 최소 제곱 문제를 해결하는 방법을 아래와 같이 상세히 설명한다.

최소 제곱 문제의 정의

최소 제곱 문제는 다음과 같은 형태로 정의된다. 주어진 데이터 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$ 과 측정된 결과 벡터 $\mathbf{b} \in \mathbb{R}^{m}$ 가 있을 때, $\mathbf{x} \in \mathbb{R}^{n}$ 를 찾는 것이 목표이다. 이 벡터 $\mathbf{x}$ 는 다음의 조건을 만족해야 한다.

$\min_{\mathbf{x}} \|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2$

여기서 $\|\cdot\|_2$ 는 2-노름(Euclidean norm)을 의미한다. 위 문제의 해는 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 를 만족하는 $\mathbf{x}$ 중에서 잔차(residual) $\mathbf{r} = \mathbf{b} - \mathbf{A}\mathbf{x}$ 의 크기를 최소화하는 것이다.

QR 분해를 이용한 최소 제곱 문제 해결

행렬 $\mathbf{A}$ 에 대해 QR 분해를 적용하면, $\mathbf{A}$ 는 직교 행렬 $\mathbf{Q}$ 와 상삼각 행렬 $\mathbf{R}$ 의 곱으로 표현될 수 있다:

$\mathbf{A} = \mathbf{Q}\mathbf{R}$

이 표현을 최소 제곱 문제에 대입하면:

$\min_{\mathbf{x}} \|\mathbf{Q}\mathbf{R}\mathbf{x} - \mathbf{b}\|_2^2$

직교 행렬 $\mathbf{Q}$ 의 성질을 이용하면, 문제는 다음과 같이 단순화된다:

$\min_{\mathbf{x}} \|\mathbf{R}\mathbf{x} - \mathbf{Q}^\top\mathbf{b}\|_2^2$

여기서 $\mathbf{Q}^\top\mathbf{b}$ 는 새로운 벡터 $\mathbf{c}$ 로 치환할 수 있다:

$\mathbf{c} = \mathbf{Q}^\top\mathbf{b}$

따라서 문제는 다음과 같은 상삼각 행렬 $\mathbf{R}$ 에 대한 선형 방정식으로 바뀐다:

$\mathbf{R}\mathbf{x} = \mathbf{c}$

이제 $\mathbf{R}$ 이 상삼각 행렬이므로, 이 선형 방정식은 후방 대입(back substitution)을 통해 쉽게 풀 수 있다.

후방 대입을 통한 해의 계산

상삼각 행렬 $\mathbf{R}$ 에 대한 선형 방정식 $\mathbf{R}\mathbf{x} = \mathbf{c}$ 를 풀기 위해서는 후방 대입 방법을 사용한다. 이 과정은 다음과 같은 단계로 이루어진다:

마지막 방정식부터 시작: 상삼각 행렬 $\mathbf{R}$ 의 특성상, 마지막 방정식은 단일 변수에 대해 풀 수 있다. 만약 $\mathbf{R}$ 이 $n \times n$ 행렬이라면, 마지막 방정식은 다음과 같이 나타낼 수 있다:

$r_{nn} x_n = c_n$

여기서 $r_{nn}$ 은 행렬 $\mathbf{R}$ 의 마지막 대각 원소이고, $c_n$ 은 벡터 $\mathbf{c}$ 의 마지막 원소이다. 따라서 $x_n$ 은 다음과 같이 구할 수 있다:

$x_n = \frac{c_n}{r_{nn}}$

이전 방정식들에 대해 반복: 계산한 $x_n$ 값을 이용하여, 그 이전의 방정식을 차례대로 풀어 나간다. 예를 들어, $n-1$ 번째 방정식은 다음과 같다:

$r_{n-1,n-1}x_{n-1} + r_{n-1,n}x_n = c_{n-1}$

여기서 $x_n$ 값은 이미 계산되었으므로, 이를 대입하여 $x_{n-1}$ 을 구할 수 있다:

$x_{n-1} = \frac{c_{n-1} - r_{n-1,n}x_n}{r_{n-1,n-1}}$

이 과정을 반복하여 모든 $x_i$ 값을 계산할 수 있다.

수치적 안정성

QR 분해를 통해 최소 제곱 문제를 해결하는 방법은 수치적으로 매우 안정적이다. 행렬 $\mathbf{A}$ 의 조건 수(condition number)가 크더라도, QR 분해는 해를 구하는 과정에서 발생할 수 있는 오류를 최소화하는 특성을 가지고 있다. 특히, 행렬 $\mathbf{Q}$ 가 직교 행렬이기 때문에, $\mathbf{Q}^\top\mathbf{b}$ 계산 시의 수치적 오차가 적게 발생한다.

이는 고유값 계산, 신호 처리, 데이터 피팅과 같은 다양한 응용에서 매우 중요한 장점으로 작용한다. 또한, $\mathbf{R}$ 이 상삼각 행렬이기 때문에 후방 대입 과정도 간단하고 효율적이다.

최소 제곱 문제에서의 잔차 분석

QR 분해를 이용한 최소 제곱 문제의 해 $\mathbf{x}$ 를 구한 후, 잔차 $\mathbf{r}$ 는 다음과 같이 정의된다:

$\mathbf{r} = \mathbf{b} - \mathbf{A}\mathbf{x}$

이 잔차의 크기를 분석함으로써, 모델의 적합도를 평가할 수 있다. 만약 $\|\mathbf{r}\|$ 이 매우 작다면, 이는 모델이 주어진 데이터를 잘 설명한다는 의미이다. 반대로, $\|\mathbf{r}\|$ 이 크다면 모델이 데이터에 적합하지 않음을 나타낼 수 있다.

QR 분해를 이용한 해법은 잔차의 크기를 최소화하는 방향으로 계산되므로, 주어진 데이터에 대한 최적의 선형 모델을 제공한다.