# 직교화 기법(QR 분해)의 활용

선형 방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$을 풀기 위한 여러 가지 수치 기법들 중에서 직교화 기법을 기반으로 한 QR 분해는 매우 중요한 역할을 한다. 이러한 기법은 고유값 분해나 특이값 분해와 함께 수학적 안정성과 계산 효율성을 동시에 추구하는 대표적인 방법이다. 특히, 직교행렬이 갖는 성질을 이용하면 계산 과정에서 발생할 수 있는 오차를 줄이고, 알고리즘의 수치적 안정성을 높일 수 있다. 이러한 이유로 QR 분해는 단순히 선형 방정식을 풀 때뿐 아니라, 최소제곱 문제나 고차원 데이터 분석 등에서도 널리 활용된다.

#### QR 분해의 기초 개념

QR 분해는 정사각 행렬(또는 행과 열의 크기가 다른 직사각 행렬) $\mathbf{A}$를 직교(또는 직교에 준하는 정규직교) 행렬 $\mathbf{Q}$와 상삼각 행렬 $\mathbf{R}$의 곱으로 표현하는 것이다. 선형 독립인 열을 가진 $\mathbf{A}\in\mathbb{R}^{m\times n}$에 대해, 다음과 같은 분해가 가능하다.

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

여기에서 $\mathbf{Q}$는 열 벡터들이 서로 직교하며, 각 열 벡터의 길이가 1로 정규화되어 있는 $m\times m$ 직교행렬(또는 $m\times n$ 반직교행렬)이고, $\mathbf{R}$은 $m\times n$ 행렬 중에서 윗부분이 상삼각 형태를 갖는 행렬이다. 만일 $\mathbf{A}$가 정사각 행렬($m=n$)이라면 $\mathbf{Q}$는 완전한 직교행렬이 되어 $\mathbf{Q}^{\mathsf{T}}\mathbf{Q} = \mathbf{I}$가 성립한다.

직교(Orthogonal) 혹은 직교화(Orthogonalization)란, 점곱 내적이 서로 0이 되도록 벡터들을 변환하는 과정을 말한다. 직교화가 중요한 이유는 수치적 계산과정에서 발생하는 부동소수점 연산 오차를 최소화할 수 있기 때문이다. 벡터들 간에 직교성이 확보되면, 해석적 구조가 단순화되고 조건수가 상대적으로 개선되어 더 안정적인 계산을 기대할 수 있다.

#### 고전적 Gram-Schmidt 직교화

QR 분해를 얻는 가장 전통적인 접근법 중 하나는 Gram-Schmidt 직교화 과정을 이용하는 것이다. 이 방법은 행렬 $\mathbf{A}$의 열 벡터를 순차적으로 직교화하면서 $\mathbf{Q}$의 열 벡터를 생성하고, 그에 따른 크기 정보를 $\mathbf{R}$에 기록한다.

고전적(또는 순차적) Gram-Schmidt 절차에서, $\mathbf{A}$의 열 벡터들을 $\mathbf{a}\_1, \mathbf{a}\_2, \cdots, \mathbf{a}\_n$이라 하면, $\mathbf{Q}$의 열 벡터 $\mathbf{q}\_1, \mathbf{q}\_2, \cdots, \mathbf{q}\_n$는 다음 단계로 구해진다.

먼저 $\mathbf{q}\_1$은 $\mathbf{a}\_1$을 정규화한 벡터다.

$$
\mathbf{q}\_1 = \frac{\mathbf{a}\_1}{|\mathbf{a}\_1|}
$$

이후 두 번째 열 벡터를 직교화하기 위해,

$$
\mathbf{u}\_2 = \mathbf{a}\_2 - (\mathbf{q}\_1^{\mathsf{T}}\mathbf{a}\_2)\mathbf{q}\_1
$$

라고 정의하여 $\mathbf{a}\_2$가 이미 구해진 $\mathbf{q}\_1$과 직교가 되도록 조정한 뒤,

$$
\mathbf{q}\_2 = \frac{\mathbf{u}\_2}{|\mathbf{u}\_2|}
$$

로 다시 정규화한다. 일반적으로 $k$번째 단계에서,

$$
\mathbf{u}\_k = \mathbf{a}*k - \sum*{j=1}^{k-1} (\mathbf{q}\_j^{\mathsf{T}}\mathbf{a}\_k)\mathbf{q}\_j
$$

를 통해 이미 얻어진 $\mathbf{q}*1,\dots,\mathbf{q}*{k-1}$ 각각과 직교가 되도록 만든 뒤,

$$
\mathbf{q}\_k = \frac{\mathbf{u}\_k}{|\mathbf{u}\_k|}
$$

가 된다. 그런 다음에 $\mathbf{R}$의 원소는 각 단계에서 계산되는 내적을 이용하여

$$
R\_{j,k} = \mathbf{q}\_j^{\mathsf{T}}\mathbf{a}\_k
$$

와 같이 생성된다. 이렇게 구해진 $\mathbf{Q}$와 $\mathbf{R}$은 $\mathbf{A}$에 대한 유효한 QR 분해가 된다.

하지만 고전적 Gram-Schmidt 방법은 벡터 수가 많아지거나 수치적 조건이 좋지 않은 환경에서 부동소수점 오차에 취약할 수 있다. 내적을 통해 직교화하는 단계가 반복될 때, 이미 작은 값을 여러 번 빼는 일이 발생하고, 이는 수치적으로 심각한 손실 오차(loss of significance)를 야기할 수 있다. 따라서 실제로는 수정된(modified) Gram-Schmidt 방법 또는 다른 계열의 직교화 방법(예: Householder, Givens)을 더욱 선호한다.

#### Householder 변환을 통한 QR 분해

Householder 변환(혹은 반사라고도 부름)은 벡터를 특정 면에 대해 반사(reflection)시키는 매트릭스로, 수치적 안정성이 뛰어난 것으로 잘 알려져 있다. Householder 변환 $\mathbf{H}$는 보통 다음과 같이 표현된다.

$$
\mathbf{H} = \mathbf{I} - 2\frac{\mathbf{v}\mathbf{v}^{\mathsf{T}}}{\mathbf{v}^{\mathsf{T}}\mathbf{v}}
$$

여기에서 $\mathbf{v}$는 반사평면을 정의하는 벡터이며, $\mathbf{H}$는 대칭(symmetric)이면서 직교(orthogonal)인 행렬이 된다. Householder QR 분해는 $\mathbf{A}$를 상삼각으로 만들도록 순차적으로 Householder 변환을 곱해 주어 결과적으로

$$
\mathbf{R} = \mathbf{H}\_k \cdots \mathbf{H}\_2 \mathbf{H}\_1 \mathbf{A}
$$

이 상삼각 형태를 갖도록 하며, 직교행렬 $\mathbf{Q}$는 이 모든 변환의 곱의 전치로 정의된다.

Householder 변환이 Gram-Schmidt보다 더욱 안정적인 이유는, 반사를 정의하는 벡터 $\mathbf{v}$ 자체가 부분 벡터의 정보만을 사용하기 때문에 불필요한 내적 연산으로 인한 누적 오차가 상대적으로 적고, 국소적 방식으로 한 열씩 깎아 나가는 과정에서 오차가 체계적으로 관리될 수 있기 때문이다. 계산 복잡도와 메모리 접근 패턴 등을 고려하면 대규모 행렬 연산에서 많이 활용되는 방법이다.

#### 선형 방정식 풀이에서의 QR 분해

선형 방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$에서 $\mathbf{A}$가 정방행렬($n\times n$)이고 역행렬이 존재한다면, QR 분해를 이용하여 해를 구하는 대표적 방식은 다음과 같은 아이디어로 진행된다. 먼저,

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

라고 할 때, 위의 선형 방정식을 $\mathbf{Q}\mathbf{R}\mathbf{x} = \mathbf{b}$로 쓸 수 있다. 여기서 $\mathbf{Q}$가 직교행렬이므로 $\mathbf{Q}^{\mathsf{T}}\mathbf{Q} = \mathbf{I}$가 성립하므로, 양변에 $\mathbf{Q}^{\mathsf{T}}$를 곱하여

$$
\mathbf{R}\mathbf{x} = \mathbf{Q}^{\mathsf{T}}\mathbf{b}
$$

라는 간단한 상삼각 방정식을 얻을 수 있다. 이 식은 뒤에서부터 순차적으로 해를 구해나가는 후방대입(back-substitution) 과정을 통해 쉽게 풀이된다.

또한 $\mathbf{A}$가 풀 랭크를 가지지 않는(혹은 정방이 아닌) 일반적 상황에서 최소제곱 해를 구하는 과정에도

$$
\min\_{\mathbf{x}}|\mathbf{b}-\mathbf{A}\mathbf{x}|\_2
$$

가 필요할 때 QR 분해가 직접적으로 사용된다. 이 경우에는

$$
\mathbf{A} = \mathbf{Q}\mathbf{R}, \quad \mathbf{Q}^{\mathsf{T}}\mathbf{A} = \mathbf{R}
$$

의 성질을 활용하여,

$$
\min\_{\mathbf{x}}|\mathbf{b}-\mathbf{A}\mathbf{x}|*2 = \min*{\mathbf{x}}|\mathbf{Q}^{\mathsf{T}}\mathbf{b} - \mathbf{R}\mathbf{x}|\_2
$$

가 되고, 상삼각 행렬에 대한 후방대입을 통해 직접적으로 최소제곱 문제를 해석할 수 있다.

#### Givens 회전과 QR 분해

Householder 변환과 달리 Givens 회전은 2차원 회전 행렬을 부분적으로 곱해 주어 불필요한 요소를 0으로 만들어 나가는 방식이다. 특정 좌표축(예: $i$-$j$ 평면)을 대상으로 회전을 수행하면서 열이나 행의 특정 원소를 0으로 만드는 아이디어다. Givens 회전은 희소(sparse) 행렬에 대해서 유리한 측면이 있고, 하드웨어적으로 벡터화 연산이나 병렬화를 적용하기 쉬운 장점이 있다.

Givens 회전 행렬 $\mathbf{G}(i,j,\theta)$는 보통 항등행렬에서 $i$행, $j$행과 $i$열, $j$열에 해당하는 부분을

$$
\begin{pmatrix} \cos\theta & -\sin\theta \ \sin\theta & \cos\theta \end{pmatrix}
$$

로 대체한 형태이다. $\mathbf{A}$의 $(i,j)$ 원소를 0으로 만들고 싶을 때, 적절한 $\theta$를 골라 $\mathbf{G}(i,j,\theta),\mathbf{A}$를 계산하면 해당 위치 원소가 제거된다. 이를 상삼각 형태가 완성될 때까지 반복함으로써 QR 분해를 구현한다.

#### 간단한 예시 (Python)

다음 Python 코드는 Gram-Schmidt 또는 Householder를 이용하여 QR 분해를 수행한 뒤, 선형 방정식을 해결하는 간단 예시다. 원하는 방식을 선택하여 비교 실험을 해볼 수 있다.

```python
import numpy as np

def classical_gram_schmidt(A):
    m, n = A.shape
    Q = np.zeros_like(A, dtype=float)
    R = np.zeros((n, n), dtype=float)
    for k in range(n):
        u = A[:, k].copy()
        for j in range(k):
            R[j, k] = np.dot(Q[:, j], A[:, k])
            u -= R[j, k] * Q[:, j]
        R[k, k] = np.linalg.norm(u)
        Q[:, k] = u / R[k, k]
    return Q, R

def householder_qr(A):
    m, n = A.shape
    Q = np.eye(m)
    R = A.copy()
    for k in range(n):
        x = R[k:, k]
        e1 = np.zeros_like(x)
        e1[0] = np.linalg.norm(x)
        v = x - e1
        if np.linalg.norm(v) < 1e-14:
            continue
        v = v / np.linalg.norm(v)
        H_k = np.eye(m)
        H_k[k:, k:] -= 2.0 * np.outer(v, v)
        R = H_k @ R
        Q = Q @ H_k.T
    return Q, R

# 간단한 예시
A = np.array([[2.0, 1.0],
              [1.0, 3.0]])
b = np.array([7.0, 13.0])

Q, R = householder_qr(A)
# Q, R = classical_gram_schmidt(A)  # 비교를 위해 교체 가능

# QR을 이용한 선형 방정식 풀이
x_solution = np.linalg.inv(R) @ Q.T @ b
print("Solution via QR decomposition:", x_solution)
```

이 코드에서 Householder 버전의 QR 분해는 선형 방정식을 푸는 전형적인 과정을 보여 준다. Gram-Schmidt 버전도 충분히 같은 목적을 달성하지만, 부동소수점 오차의 누적이나 수치 안정성 등에서 Householder가 더욱 나은 결과를 낼 때가 많다. QR 분해로부터 얻어진 $\mathbf{Q}$와 $\mathbf{R}$을 바탕으로, $\mathbf{x}$를 구하는 과정은 후방대입(또는 적절한 선형대수 연산)만 수행하면 되므로 간결하다.

#### 수정된 Gram-Schmidt 직교화

고전적 Gram-Schmidt 과정은 알고리즘 자체가 간단하다는 장점이 있지만, 수치적으로 불안정해질 수 있는 단점이 있다. 특히, 큰 차이를 갖는 벡터 크기(스케일 차)가 존재할 때 부동소수점 연산 오차가 빠르게 누적될 수 있다. 이를 보완하기 위해 수정된 Gram-Schmidt(modified Gram-Schmidt, MGS) 기법이 고안되었다.

수정된 Gram-Schmidt에서는 $k$번째 벡터를 직교화할 때, 이미 직교화된 벡터들에 대해 한 번에 모든 내적을 구해서 한꺼번에 빼는 것이 아니라, 매 단계마다 한 벡터씩 차근차근 내적을 계산하고 그 결과를 즉시 빼 준다. 다시 말해, $k$번째 열 벡터 $\mathbf{a}\_k$를 정규 직교화시키고 싶다고 하면, 다음처럼 진행된다.

먼저 첫 번째 $\mathbf{q}\_1$과의 내적을 구해 그 성분을 빼고, 그 결과로 업데이트된 $\mathbf{u}\_k^{(1)}$에 대해 두 번째 $\mathbf{q}\_2$와의 내적을 구해서 빼 준다. 이런 식으로 이미 구해진 $\mathbf{q}*1,\dots,\mathbf{q}*{k-1}$에 대해 순차적으로 반복한다. 이렇게 하면, 이미 한 번 제거된 성분이 새롭게 내적을 구할 때 다시 반영되지 않으므로, 수치적 측면에서 보다 안정적인 결과를 얻을 수 있다. 수식으로 표현하면,

$$
\mathbf{u}\_k^{(j)} =  \mathbf{u}\_k^{(j-1)} -  \bigl(\mathbf{q}\_j^{\mathsf{T}}\mathbf{u}\_k^{(j-1)}\bigr)\mathbf{q}\_j
$$

와 같이 1차원씩 순차적으로 직교 성분을 제거한다. 여기에 $\mathbf{u}\_k^{(0)} := \mathbf{a}\_k$라 두고, 최종 $\mathbf{u}\_k^{(k-1)}$를 정규화하면 $\mathbf{q}\_k$가 된다. 전체 과정을 코드로 구현하면 고전적 Gram-Schmidt와 큰 차이가 없어 보이지만, 실제로는 수치적 연산 순서가 다르기 때문에 오류 누적 양상이 달라진다.

#### Pivoting과 Rank-Revealing QR

$\mathbf{A}$가 해석적으로는 완벽한 랭크를 갖는다고 해도, 수치계산 과정에서 $\mathbf{A}$의 열들 중에 서로 거의 선형 종속 상태에 가까운 벡터가 존재할 수 있다. 이때 열 벡터의 순서를 적절히 바꾸면(피보팅, pivoting), 계산 중 발생할 수 있는 오차를 억제하고, 분해의 유효랭크를 보다 정확하게 파악할 수 있다.

피보팅을 수반하는 QR 분해를 일반적으로 Pivoted QR이라고 부른다. 이 방법은 $|\mathbf{a}\_j|$가 큰 열을 먼저 처리하는 식으로 열 교환(pivot)을 수행해, 차례대로 직교화과정을 안정적으로 진행한다. Rank-Revealing QR (RRQR)은 더 나아가, $\mathbf{A}$가 희소 혹은 특수구조를 가질 때, 대규모 계산에서도 불필요한 연산을 줄이면서 (또는 메모리 접근을 최적화하여) 실제 작동 시간을 단축시키는 데 유리하다.

피보팅이 반영된 QR 분해는 다음과 같은 형태로 표현된다.

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

여기서 $\mathbf{\Pi}$는 열의 순서를 바꾸는 순열 행렬이다. 필요한 경우, 상위 몇 개 열만 따로 추려서 rank-$k$ 근사 해를 구하는 전략을 취할 수도 있으며, 이에 따라 $k$차 근사 행렬이나 $k$차 근사 해를 더욱 효율적으로 산출할 수 있다.

#### 블록(block) QR 기법

QR 분해를 구현할 때, 단일 벡터(또는 단일 열) 기준으로 순차적 변환을 적용하는 것보다, 여러 열을 한 번에 묶어서(블록으로) 처리하는 방식을 고려할 수 있다. 이를 블록 QR(block QR) 기법이라 하고, 고성능 수치연산 라이브러리(LAPACK, ScaLAPACK 등)에서 흔히 채택한다. 블록 단위로 연산하면, 연산을 벡터화(vectorization)하거나 병렬화(parallelization)하는 데에 유리하고, CPU 캐시 사용 측면에서도 효율적이다.

블록 QR에서 가장 널리 사용되는 방식은 Householder 변환을 블록 단위로 묶어서 처리하는 것이며, 단일 Householder 변환을 여러 번 곱하는 대신 한번에 큰 블록 반사(block reflector)를 구성해 적용한다. 이렇게 하면 메모리 접근 패턴이 집중적으로 이뤄져서 실제 계산 시간을 절감할 수 있다. 반면, 알고리즘의 복잡도는 다소 증가하고 코딩 난이도도 높아지지만, 대규모 행렬에 대해서는 현저한 성능 향상을 기대할 수 있다.

#### 희소 행렬의 QR 분해

행렬이 매우 커지지만 대부분의 원소가 0인 희소(sparse) 구조를 가진 경우, 단순히 밀집(dense) 행렬 알고리즘을 적용하면 불필요한 0 원소 연산까지 수행하게 된다. 따라서, 희소 행렬 구조를 능동적으로 활용해 계산 비용을 절감하고자 다양한 특수 알고리즘들이 개발되었다.

Givens 회전은 희소 행렬의 QR 분해에 유리한 대표적인 방식 중 하나다. 필요할 때만 2×2 차원의 회전 변환을 부분적으로 적용해 특정 원소를 0으로 만들므로, 연산 범위를 제한적으로 제어하기 쉽다. Householder 변환 방식도 희소 행렬에 맞게 최적화된 기법들이 존재하나, 반사를 정의하는 벡터가 부분 벡터만을 사용한다 해도 회전보다 큰 블록을 갱신해야 하므로, 적절한 전략을 세워야 한다. 대규모 희소 시스템을 다룰 때는, QR 외에 LU 분해나 직교 Krylov 하부공간 기법과 비교하여 장단점을 면밀히 검토한다.

#### 수치적 안정성과 조건수

QR 분해를 이용한 선형 방정식 풀이가 널리 사용되는 이유 중 하나는 수치적 안정성이다. 직교행렬이 갖는 성질과 상삼각 형태에 의한 후방대입 과정은, $LU$ 분해보다 상대적으로 오류전파가 적다. 만약 $\mathbf{A}$의 열벡터들이 거의 종속 상태라면, $\mathbf{R}$의 대각 원소 중 일부가 매우 작아질 것이고, 따라서 내부적으로 큰 수의 비율(large ratio)의 연산이 발생할 수 있다. 이때는 Pivoted QR을 통해 가능한 한 덜 유리한 방향으로 수치 오차가 진행되지 않도록 할 수 있다.

직교화 관점에서 가장 중요한 문제 중 하나는, 실제 계산 환경에서 벡터들 간의 내적이 부정확해질 때 생기는 오차 누적이다. Gram-Schmidt(특히 고전적 GS)는 여기서 치명적일 수 있지만, Householder나 Givens 같은 직교 변환 계열에서는 이 오차가 상대적으로 작다. 따라서, 매우 큰 크기의 문제나 민감도(sensitivity)가 높은 문제에서는 Householder 변환 또는 수정된 Gram-Schmidt 방법을 더욱 선호하게 된다.

#### 역조건(problem ill-conditioning)의 영향

$\mathbf{A}$가 고도로 ill-conditioned(조건수가 매우 큼) 상태일 때, $\mathbf{A}\mathbf{x}=\mathbf{b}$를 푸는 모든 근사적 방법은 불가피하게 큰 오차를 내포할 가능성이 있다. 이런 상황에서 QR 분해 기반의 방법 역시 완전히 자유로울 수는 없지만, $LU$ 분해 등에 비해 상대적으로 나은 수치적 행동을 기대할 수 있다. 또한, 문제가 불안정하다는 것이 미리 파악된다면, 정규화(regularization) 기법이나 사전 지식(prior)을 활용한 제약조건 등을 적용해 문제 해석의 견고성을 높이는 방향을 모색하기도 한다.

#### QR 분해의 메모리 및 연산량 분석

행렬 크기를 $m\times n$이라고 할 때, QR 분해의 연산량은 대략 $2mn^2 - \tfrac{2}{3}n^3$ 정도의 부동소수점 연산이 필요하다고 알려져 있다($m\ge n$ 가정). 이는 Householder 변환을 기반으로 할 때의 복잡도를 나타내며, $LU$ 분해($\tfrac{2}{3}n^3$)와 같은 차수로 볼 수 있지만, 미세한 상수 차이는 존재한다. Givens 회전을 이용하는 경우, 각 요소를 0으로 만들기 위해 수행해야 하는 회전 횟수가 상당히 많아질 수 있으므로, 보통 모든 원소를 처리하려면 $mn(n-1)$ 부근의 연산이 요구된다. 따라서 무작정 Givens 회전을 적용하기보다는, 특정한 열이나 행만 선택적으로 회전하는 전략이 병행된다.

메모리 사용 관점에서도 QR는 $Q$와 $R$ 자체에 대한 저장공간 이외에, 중간 변환 데이터를 관리하기 위한 일시적 버퍼가 필요할 수 있다. 블록 방법에서는 한 번에 여러 열을 대상으로 변환을 수행하므로, 캐시 적중률을 높이고 불필요한 메모리 접근을 줄이는 방향으로 알고리즘을 최적화한다.

#### 작은 예시 (C++)

다음은 C++로 Householder QR을 구현하는 예시다. 희소 행렬이 아니라고 가정한 기본 버전이며, Eigen이나 Armadillo 같은 선형대수 라이브러리를 사용하지 않고 최소한의 로직만 보여 준다. 실제 프로젝트에서는 BLAS/LAPACK 또는 Eigen 등을 적극 활용하는 것이 훨씬 안정적이고 효율적이다.

```c++
#include <iostream>
#include <vector>
#include <cmath>

// 간단한 행렬/벡터 연산 보조 함수
static double dot(const std::vector<double>& x, const std::vector<double>& y) {
    double sum = 0.0;
    for (size_t i = 0; i < x.size(); ++i) {
        sum += x[i] * y[i];
    }
    return sum;
}

static void axpy(double alpha, const std::vector<double>& x, std::vector<double>& y) {
    for (size_t i = 0; i < x.size(); ++i) {
        y[i] += alpha * x[i];
    }
}

static void scale(std::vector<double>& x, double alpha) {
    for (auto& xi : x) {
        xi *= alpha;
    }
}

static double norm2(const std::vector<double>& x) {
    return std::sqrt(dot(x, x));
}

// 행렬은 row-major로 저장. A의 (i, j)는 A[i*n + j].
std::pair<std::vector<double>, std::vector<double>> householder_qr(const std::vector<double>& A_in, int m, int n) {
    std::vector<double> R(A_in); 
    std::vector<double> Q(m*m, 0.0);
    for (int i = 0; i < m; i++) {
        Q[i*m + i] = 1.0;
    }

    for (int k = 0; k < n; k++) {
        // x 벡터 추출
        std::vector<double> x(m - k, 0.0);
        for (int i = k; i < m; i++) {
            x[i - k] = R[i*n + k];
        }
        double normx = norm2(x);
        if (normx < 1e-14) continue;
        std::vector<double> e1(m - k, 0.0);
        e1[0] = normx;

        // v = x - e1
        std::vector<double> v(x);
        for (int i = 0; i < (int)x.size(); i++) {
            v[i] -= e1[i];
        }
        double normv = norm2(v);
        if (normv < 1e-14) continue;
        scale(v, 1.0 / normv);

        // H_k = I - 2 v v^T
        // 부분 행렬에 대해서만 반사 적용
        for (int col = k; col < n; col++) {
            std::vector<double> subCol(m - k, 0.0);
            for (int row = k; row < m; row++) {
                subCol[row - k] = R[row*n + col];
            }
            double alpha = 2.0 * dot(v, subCol);
            axpy(-alpha, v, subCol);
            for (int row = k; row < m; row++) {
                R[row*n + col] = subCol[row - k];
            }
        }

        // Q에도 반사 적용 (Q = Q * H_k^T)
        for (int col = 0; col < m; col++) {
            std::vector<double> subCol(m - k, 0.0);
            for (int row = k; row < m; row++) {
                subCol[row - k] = Q[row*m + col];
            }
            double alpha = 2.0 * dot(v, subCol);
            axpy(-alpha, v, subCol);
            for (int row = k; row < m; row++) {
                Q[row*m + col] = subCol[row - k];
            }
        }
    }
    return {Q, R};
}

int main() {
    // 예시 행렬
    int m = 3, n = 2;
    std::vector<double> A = {
        2.0, 1.0,
        1.0, 3.0,
        4.0, 5.0
    };

    auto [Q, R] = householder_qr(A, m, n);

    // 출력 (간단 검증)
    std::cout << "Q = \n";
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            std::cout << Q[i*m + j] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\nR = \n";
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << R[i*n + j] << " ";
        }
        std::cout << "\n";
    }

    return 0;
}
```

이 예시는 $m \times n$인 일반 행렬에 대해 Householder 기반의 QR 분해를 구현한 후, 행렬 $Q$와 $R$를 반환한다. 실제로는 $\mathbf{Q}$가 $m\times m$ 완전 직교행렬 형태로 저장되지만, 사용자 입장에서는 필요한 열 부분만 활용하여 이후의 계산에 이용하면 된다. 예컨대 $m>n$인 최소제곱 문제에서는 $Q$의 $m\times n$ 부분만 사용해도 문제 해결이 가능하다.

#### QR 알고리즘과 고윳값 문제

QR 분해가 직접적으로 선형 방정식을 풀거나 최소제곱 해를 찾는 데 사용될 뿐 아니라, 고윳값 문제(eigenvalue problem)를 풀이하는 데에도 핵심적 역할을 한다. QR 알고리즘은 실대칭 행렬(또는 복소 에르미트 행렬)의 고윳값을 구하기 위한 가장 대표적인 방법 중 하나다. 일반 실정방 행렬의 고윳값을 구할 때도, Hessenberg 변환이나 상삼각화를 거쳐 유사하게 진행할 수 있다.

QR 알고리즘은 일반적으로 다음과 같이 전개된다. 어떤 정방행렬 $\mathbf{A}$에 대해, QR 분해를 수행하면

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

이 된다. 여기서 $\mathbf{Q}\_1$은 직교행렬이고 $\mathbf{R}\_1$은 상삼각 행렬이다. 다음으로,

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

를 새롭게 정의한다. 이렇게 하면 $\mathbf{A}$와 $\mathbf{A}\_1$은 닮음(similarity) 관계를 갖기 때문에 고윳값이 같다. 이어서 $\mathbf{A}\_1$에 대해 QR 분해를 다시 수행하여,

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

를 구한 뒤,

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

로 갱신하는 과정을 반복한다. 수렴성이 보장되면 $\mathbf{A}\_k$는 상삼각(또는 블록 상삼각)에 가까워지며, 그 대각원소(또는 블록 대각원소)가 원래 행렬의 고윳값으로 수렴한다. 이를 더욱 효율적으로 수행하기 위해선 행렬 $\mathbf{A}$를 먼저 Hessenberg 형태(또는 반 Hessenberg)로 축소해 두면, 각 단계마다 오차의 누적이 적고 계산비용도 크게 줄어든다.

#### QR 알고리즘을 도식화한 예 (mermaid)

아래는 QR 알고리즘을 단순화해 흐름도로 나타낸 예시다. (실제 구현에서는 다양한 최적화와 수치 안정화 기법이 활용된다.)

{% @mermaid/diagram content="flowchart TB
A0((시작)) --> A1\[행렬 A 준비]
A1 --> A2\[초기화: A\_0 := A]
A2 --> A3\[반복: k := 0...]
A3 --> A4("QR 분해: A\_k = Q\_{k+1} R\_{k+1}")
A4 --> A5("A\_{k+1} := R\_{k+1} Q\_{k+1}")
A5 --> C{수렴 검증}
C -- "미수렴" --> A3
C -- "수렴" --> A6((상삼각 근사 해 얻기))" %}

이 알고리즘은 단순해 보이지만, Householder 변환을 사용하여 매 단계 $\mathbf{A}\_k$를 효율적으로 QR 분해하는 과정이 내부적으로 수행된다. 수렴 판단은 대각선 밖의 원소들의 절댓값이 충분히 작아져서 상삼각(또는 블록 대각) 형태가 확실히 드러났는지 여부를 기준으로 삼는다.

#### 경제적 QR 분해(thin QR)와 대형 행렬

정방행렬보다 행의 수가 훨씬 많은 $m\times n$ 행렬에서 $(m>n)$, 굳이 $m\times m$ 완전 직교행렬을 구할 필요가 없을 때가 많다. 최소제곱 해를 구하거나, 주성분분석(PCA)처럼 주로 $\mathbf{R}$과 몇 개 열의 직교기저만 필요할 때는, 경제적 QR(혹은 reduced QR, thin QR) 분해를 활용한다.

$$
\mathbf{A} = \mathbf{Q}\mathbf{R}, \quad \mathbf{Q}\in \mathbb{R}^{m\times n},\quad \mathbf{R}\in \mathbb{R}^{n\times n}
$$

형태로 벡터열의 기저가 되는 $\mathbf{Q}$만 추려서 구성한다. 이렇게 하면 $\mathbf{Q}$는 열이 $n$개밖에 없고, 각각 서로 직교하며, 상삼각인 $\mathbf{R}$ 역시 $n\times n$ 크기로 저장용량도 훨씬 줄어든다.

#### Partial Reorthogonalization

Krylov 하부공간 기반 반복법(예: Lanczos, Arnoldi)에서 직교화 과정을 반복하다 보면, 이미 뽑아 놓은 직교 벡터에 새로운 벡터를 정규직교화하는 단계에서 누적 오차가 커질 수 있다. 이런 누적 오차를 방치하면, 이론적으론 직교해야 할 벡터들이 실제로는 서로 직교하지 않게 되는 문제가 발생한다.

이에 대한 한 가지 개선책은 Partial Reorthogonalization 기법이다. 벡터 집합이 충분히 서로 직교해 있다고 기대되는 상황에선 불필요한 재직교화를 생략하거나, 국소적으로만 추가 직교화를 수행하여 연산량을 아낀다. 반면 수치적 오류가 많이 쌓였다고 판단되는 시점에는, 교정(reorthogonalization)을 통해 다시 한 번 모든 벡터 쌍에 대해 오차를 제거한다. 이런 기법은 대규모 반복법에서 직교성 손실을 제어하면서 연산 비용을 줄이는 데 유용하다.

#### 사전조건(precondition)과 QR

선형계수행 문제에서 프리컨디셔너(사전조건행렬)를 사용하는 이유는, 해를 구하는 과정(예: 반복법)에서 시스템의 조건수를 낮추고 수렴속도를 개선하기 위해서다. 사전조건행렬을 단순 곱 형태로 정의할 수도 있지만, 더 복잡한 경우에는 역연산에 가까운 효과를 갖게 만들기도 한다.

QR 관점에서 사전조건을 수행하면, $\mathbf{A} = \mathbf{M}^{-1}\mathbf{B}$ 꼴의 형태로 바꾼 뒤 $\mathbf{B}\mathbf{x} = \mathbf{M}\mathbf{b}$를 풀 수 있는 식으로 접근할 수 있다. $\mathbf{B}$가 더 양호한 구조(예: 보다 좋은 스펙트럼 분포)를 갖도록 만드는 것이 목적이다. 직교화 기법은 $\mathbf{B}$에 대해서도 별다른 변형 없이 동일하게 적용되므로, 추후 사전조건 기법과 직교화의 결합이 자연스럽게 이뤄진다.

#### QR 분해와 SVD

QR 분해는 특이값 분해(SVD)를 구하는 초기 단계로도 활용된다. SVD를 직접 구하는 알고리즘은 일반적으로 매우 비싸지만, 어떤 상황에서는 $\mathbf{A} \approx \mathbf{Q}\mathbf{R}$를 먼저 얻은 뒤, $\mathbf{R}$ 자체를 고윳값 분해 또는 SVD에 더 적합한 작은 크기의 행렬로 만드는 방식(골벅-키ahan(Golub-Kahan) 등)이 사용되기도 한다.

만약 $\mathbf{A}$가 이미 얇은 QR 형태로 주어졌다면, $\mathbf{A} = \mathbf{Q}\mathbf{R}$, 그 뒤에 $\mathbf{R} = \mathbf{U}\_R \mathbf{\Sigma}\_R \mathbf{V}\_R^{\mathsf{T}}$ (SVD) 같은 식으로 분해하면, 최종적으로

$$
\mathbf{A} = (\mathbf{Q}\mathbf{U}\_R),\mathbf{\Sigma}\_R,\mathbf{V}\_R^{\mathsf{T}}
$$

가 되므로, 큰 $m\times n$ 행렬을 직접 SVD 분해하는 것보다 연산과정을 훨씬 줄일 수도 있다. 그러나 이는 어디까지나 $\mathbf{A}$의 열들이 잘 수축되어 있고, $\mathbf{R}$의 크기가 작을 때 유효한 시나리오다.

#### 고차원 데이터 분석에서의 QR 활용

QR 분해는 통계나 머신러닝 분야에서도 폭넓게 활용된다. 특히, 특이값 분해(SVD)가 비용 면에서 부담스러울 때, QR 분해를 통해 근사적으로 동일한 효과를 얻으려는 시도가 많다. 예컨대, 고차원 데이터에서 PCA(주성분분석)를 수행할 때도 QR 분해가 도입되며, 적절히 얇은 QR(thin QR) 과정을 거친 뒤에 상삼각 행렬 $\mathbf{R}$에 대해 추가적인 분해를 적용함으로써, 전체 연산 비용을 절감한다.

또한, 다중회귀(multiple regression) 문제에서 열공간(column space)의 차원을 축소하거나, 직교기저를 활용해 회귀계수를 안정적으로 추정하는 과정에서도 QR 분해가 훌륭한 수단이 된다. $X$가 데이터 행렬, $y$가 관측 벡터라고 할 때, 최소제곱 해

$$
\hat{\mathbf{\beta}} = \arg\min\_{\mathbf{\beta}}|y - X\mathbf{\beta}|\_2
$$

를 구하고자 하면, $X = \mathbf{Q}\mathbf{R}$ 형태로 QR 분해를 수행해,

$$
\hat{\mathbf{\beta}} = \mathbf{R}^{-1}\mathbf{Q}^{\mathsf{T}},y
$$

로 풀이가 가능하다. $X^\mathsf{T}X$를 직접 다루는 것(LSE, Normal Equation)보다 수치적으로 훨씬 안정적이며, 변수가 매우 많은 상황에서도 직교화 과정을 거치기 때문에 다항식 회귀나 다변량 회귀에 매우 유익하다.

#### 다항회귀에의 적용 예

다항식 회귀 문제에서, $i$번째 데이터 점 $(x\_i, y\_i)$가 있다고 하고, $p$차 다항식

$$
f(x) = \sum\_{k=0}^p \beta\_k x^k
$$

로 근사하고자 한다면, 설계행렬(design matrix) $X$는

$$
X =  \begin{pmatrix} 1 & x\_1 & x\_1^2 & \cdots & x\_1^p \ 1 & x\_2 & x\_2^2 & \cdots & x\_2^p \ \vdots & \vdots & \vdots & \ddots & \vdots \ 1 & x\_m & x\_m^2 & \cdots & x\_m^p \end{pmatrix}
$$

가 된다. 이때 $m$개의 관측값 $y\_1,\dots,y\_m$을 묶어 벡터 $\mathbf{y}$로 정의하면, 회귀계수 벡터 $\boldsymbol{\beta} = (\beta\_0,\dots,\beta\_p)^{\mathsf{T}}$가 최소제곱해로 주어진다. $X$가 꽤 크거나, $x\_i$ 값의 분포가 불균형해서 $X^\mathsf{T}X$가 심하게 ill-conditioned가 되기 쉬울 때, QR 분해를 통해

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

를 얻어서

$$
\boldsymbol{\beta} = \mathbf{R}^{-1}\mathbf{Q}^{\mathsf{T}}\mathbf{y}
$$

로 구하는 방법이 훨씬 더 안정적이다. 실제 구현 시엔, $\mathbf{R}$이 상삼각이므로 역을 직접 구하기보다는 후방대입만 수행하면 된다.

#### 일반화 선형모형과 직교화

일반화 선형모형(Generalized Linear Model, GLM)에서도 QR 분해는 필수적이다. 예컨대, 로지스틱 회귀(logistic regression)를 뉴턴-랩슨(Newton-Raphson)이나 아이터면(iteration)을 통해 추정할 때, 각 단계의 갱신량을 구하는 데 최소제곱근사 형태의 보조 문제가 등장한다. 이때도 QR 분해나 그 변형이 자주 활용되어 수렴속도와 안정성을 함께 보장한다.

#### 크리티컬한 응용: Kalman 필터

시계열 추정 및 추적 문제에 널리 쓰이는 Kalman 필터 알고리즘 역시, 내부적으로는 선형 방정식 풀이나 공분산 업데이트 단계에서 직교화 기법을 적용해 수치적 안정성을 높일 수 있다. 전통적인 표준 형태의 칼만 필터는, 예측-갱신 과정을 오차 공분산 형태로 유지한다. 그러나 순차적 또는 적분 형태로 관측을 포함하는 배치(batch) 방식에서는, QR 분해가 기존의 LU나 다른 분해에 비해 오차 전파를 완화한다. 특히, 측정행렬이 큰 경우나 반복적 업데이트가 필요한 경우, 부분방정식을 QR로 처리하면 과도한 조건수 악화 없이 필터링 과정을 진행할 수 있다.

#### 반복적 QR 분해 (Iterative Refinement)

$LU$ 분해 기반의 선형계 풀이에 익숙한 반복적 개선(iterative refinement) 기법은, QR 분해에 대해서도 유사한 방식으로 적용할 수 있다. 근사해 $\mathbf{x}\_0$를 구해놓고, 수치 오차를 다시 한 번 직교화 프레임으로 보정해 더 나은 해를 얻는 형태다. 보통은 $LU$ 분해와 달리 QR가 안정적이므로, 그 자체로도 큰 문제가 없지만, 고도의 정확도가 필요하거나 ill-conditioned 문제일 경우에는 QR+반복 개선을 통해 잔류 오차(residual)를 여러 번 줄일 수 있다.

#### 임의정밀도(arbitrary precision)에서의 QR

부동소수점 오차를 줄이기 위해, 고정 배정도(예: double precision)보다 더 높은 정밀도의 수 연산을 지원하는 임의정밀도(arbitrary precision) 라이브러리를 쓸 때가 있다. 이 경우, Gram-Schmidt 방식이나 Householder 변환 모두 정밀도가 높아지는 만큼 오차 누적이 줄어들지만, 한편으로는 연산 속도가 크게 떨어질 수 있다. 특히, 반복법이나 대규모 행렬 문제에서 임의정밀도를 사용하면 병목이 발생하기 쉬우므로, 실제로 어느 정도 정밀도까지 필요한지 사전에 예측하거나, 적응적으로 정밀도를 조정하는 전략(adaptive precision approach)을 취하기도 한다.

QR 분해는 임의정밀도 구현에서도 구현 난이도가 상대적으로 간단한 편이다. LU 분해처럼 피보팅이 복잡하게 들어가는 구조에 비해, 직교화 기법이 직교행렬의 특성을 활용해 정확성을 유지하기가 용이하기 때문이다. 예를 들어, Householder 벡터의 계산에서 필수적인 내적 및 노름 연산, 반사 적용 연산 등이 계층적으로 구성되므로, 임의정밀도 라이브러리와의 결합이 비교적 간단하다.

#### 커널 트릭과 직교 투영

머신러닝의 커널 기법에서는, 고차원(혹은 무한차원)으로의 비선형 매핑을 효율적으로 다룰 수 있도록 커널 함수를 사용한다. 이때도 직교화 개념이 등장하는데, ‘커널 공간에서의 직교 투영’을 구현하거나, 커널 PCA 등의 과정에서 암묵적으로 직교 기저를 형성하기 위해 QR 분해 혹은 그에 상응하는 매핑이 응용된다. 물론 실제로는 커널 행렬을 전면적으로 다루는 일은 $O(m^3)$ 비용이 될 수 있으므로, Nystrom 근사나 랜덤화 기법 등을 활용해 크기를 줄이는 전략을 취한다.

직교화는 노이즈가 섞인 데이터에서 조작 시에도 안정적으로 의미 있는(혹은 해석 가능한) 구조를 뽑아낼 수 있는 기능을 제공한다. 다만, 커널 트릭에서는 $\mathbf{A}$ 자체가 명시적으로 주어지지 않고, 점곱(커널) 값만 이용한다는 점을 유의해야 한다. 그럼에도 ‘직교화’라는 아이디어는 커널 공간에서도 내적이 정의되어 있기만 하면 언제든 적용 가능하다.

#### 분산/병렬 환경에서의 QR

현대 계산 환경에서는 다중 CPU 코어, GPU, 클러스터 등을 활용한 분산/병렬 연산이 필수가 되었다. QR 분해 역시 블록-분해와 병렬화가 많이 연구되어 있으며, MPI나 OpenMP, CUDA 같은 병렬 프로그래밍 모델에서 구현되는 사례가 많다.

Householder 변환 기반의 블록 QR는 각 블록별로 독립된 변환을 수행한 뒤, 점차적으로 전체 행렬을 상삼각 형태로 맞춰 가는 접근을 취한다. Givens 회전도 2×2 차원 연산 단위가 작다는 점에서 GPU와 같은 대량 병렬화 환경에 잘 맞을 수 있지만, 전체 행렬의 크기에 따라서는 Householder보다 오히려 많은 통신 및 동기화가 필요할 수도 있다.

특히, ScaLAPACK 등 분산 환경 라이브러리는 2차원 블록 사이클릭 분할(2D block-cyclic distribution) 구조를 사용해, 한 노드에 특정 열이나 행만 치우치지 않도록 한다. 이때 QR 분해의 단계별로 필요한 통신(예: Householder 벡터의 전파, Givens 파라미터의 공유)을 줄이거나, 효율적으로 파이프라인할 수 있게 만드는 것이 핵심이다. 대규모 행렬에서는 실제 연산량보다 통신량과 동기화가 병목이 될 수 있다는 점을 고려해 알고리즘을 디자인한다.

#### 다항직교(Orthogonal polynomials)와 QR

직교 다항식(Legendre, Chebyshev, Hermite 등)은 적분 구간에서의 내적 정의에 기반해 직교성을 가지는 특별한 함수족이다. 이들은 고차원 근사나 스펙트럴 방법(spectral method) 등을 다룰 때 많이 사용된다. QR 분해와 직접적인 관련성이 있는 이유는, 적분 내적을 벡터 내적으로 치환해 행렬 형태로 표현했을 때, 해당 벡터들을 직교화하는 과정을 Gram-Schmidt 또는 Householder 방식으로 재현할 수 있기 때문이다.

예컨대, 다항식 $p\_0(x), p\_1(x), \dots, p\_n(x)$가 어떤 가중함수(weight function) $w(x)$에 대해

$$
\int p\_i(x),p\_j(x),w(x),dx = 0 \quad (i\ne j)
$$

를 만족하도록 만들고 싶다면, 표본화(sampling) 또는 적분 근사 기법을 통해 효과적으로 직교화 연산을 수행할 수 있다. 때로는 이러한 다항직교를 구현하기 위해서 QR 분해가 부분적으로 기여하거나, 반대로 직교 다항식을 이용해 행렬 연산을 단순화하는 식의 상호교환적 기법도 생긴다.

#### Schur 분해와 QR의 연관성

선형대수에서 행렬의 고윳값과 고유벡터를 논할 때 Schur 분해(Schur decomposition)는 핵심적으로 사용된다. Schur 분해는 어떤 복소 정방행렬 $\mathbf{A}$에 대해, 유니터리(혹은 실수의 경우 직교) 행렬 $\mathbf{U}$를 이용해

$$
\mathbf{A} = \mathbf{U},\mathbf{T},\mathbf{U}^{\mathsf{H}}
$$

로 표현하는데, 여기서 $\mathbf{T}$는 상삼각이다. 이 상삼각 내부의 대각원소(또는 작은 블록들)는 원래의 행렬 $\mathbf{A}$의 고윳값을 반영한다. Schur 알고리즘 역시 QR 분해를 반복적으로 활용해 상삼각 형태로 근접시키는 과정이라, QR 알고리즘과 Schur 분해는 긴밀한 연관이 있다. 실수계에서 $\mathbf{U}$는 직교행렬이고, 복소계에선 에르미트(컨주게이트 전치) 내적 구조를 만족하는 유니터리 행렬을 쓴다.

Schur 분해는 일반적인 비정규행렬(non-normal matrix)에서도 안정적으로 고윳값 구조를 다룰 수 있으며, 수치 선형대수학에서 역치(shift)를 사용한 QR 알고리즘과 함께 행렬의 고윳값을 계산하는 표준적 접근이다. 따라서 Schur 분해나 QR 알고리즘은 서로 거의 동일한 골격이며, QR 분해가 직교화를 통해 상삼각 형태로 수렴해 나가는 아이디어가 바로 Schur 형태를 구현하는 핵심이다.

#### Rank-Deficient Least Squares에서의 QR

랭크가 부족한(rank-deficient) 시스템에서도 QR 분해는 요긴하다. 예컨대, $m\times n$ 행렬 $\mathbf{A}$($m\ge n$)가 풀랭크가 아닐 때, 최소제곱 문제

$$
\min\_{\mathbf{x}}|\mathbf{b} - \mathbf{A}\mathbf{x}|\_2
$$

는 해가 유일하지 않을 가능성이 크다. 일반적 해결책으로 정규방정식(Normal Equation)을 풀면, $X^\mathsf{T}X$가 심각하게 singular 또는 nearly singular일 수 있다. 이때 Rank-Revealing QR 분해(RRQR)나 SVD를 고려하게 되며, RRQR의 경우 $\mathbf{A}$와 순열행렬 $\mathbf{\Pi}$를 사용하여

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

를 구한다. $\mathbf{R}$에서 실제로 0에 가깝거나 매우 작은 대각원소가 나타나는 구간을 분리하면, 유효랭크(effective rank)를 추정할 수 있다. 그런 뒤 불안정한 부분을 제외하거나 축소해 해의 공간을 안정적으로 잡을 수 있다. 이처럼, QR 분해가 랭크 결핍 상황에서도 정규방정식을 직접 푸는 것보다 수치적으로 훨씬 안전하고, 해결책의 차원을 파악하는 데 용이하다.

#### 다중정밀도(mixed-precision) QR 기법

최근 CPU/GPU 아키텍처는 FP32(단정밀도)나 FP16(반정밀도) 같은 낮은 정밀도 부동소수점 연산을 매우 빠르게 처리할 수 있다. 이를 활용해 연산량이 많은 부분을 낮은 정밀도로 빨리 계산한 뒤, 일부 핵심 단계(예: 최종 보정, 후방대입)를 높은 정밀도(FP64, 배정밀도)로 수행하는 ‘혼합정밀도(mixed-precision)’ 기법이 주목받는다.

QR 분해도 혼합정밀도 접근으로 최적화가 가능하다. 예를 들어, Householder 벡터나 Givens 회전각을 구하는 과정은 높은 정밀도를 사용하되, 변환을 행렬 전체에 일괄 적용하는 연산은 낮은 정밀도로 처리해 속도를 올릴 수 있다. 이렇게 분할-정밀도 방식을 쓰면, 전체 QR 분해 과정의 계산 시간을 절감하면서도 결과 정확도를 어느 정도 유지할 수 있다.

응용 예로는, 대형 선형계 풀이나 머신러닝 학습에서 반복적으로 QR 분해를 해야 하는 경우에, 혼합정밀도 기법이 특히 유용하다. 다만, 문제의 조건수나 응용 요구 정확도에 따라 적절한 정밀도 설정이 중요하고, 자동 튜닝(auto-tuning)을 통해 어느 단계를 어떤 정밀도로 수행할지 동적으로 결정하기도 한다.

#### 정규방정식 vs. QR vs. SVD 비교

최소제곱 문제의 해를 구하기 위해 전통적 방식인 정규방정식 $A^\mathsf{T}A,\mathbf{x} = A^\mathsf{T}\mathbf{b}$를 채택하면, $A^\mathsf{T}A$의 수치적 안정성에 따른 문제가 발생한다. 반면 QR 분해($A=QR$)나 SVD($A=U\Sigma V^\mathsf{T}$)를 이용하면, 내적을 통한 조건수 악화를 어느 정도 피하면서 해를 구할 수 있다.

가장 안정적인 방법은 SVD이지만, 연산량이 크다. QR 분해는 SVD보다 덜 안정적이지만, $A^\mathsf{T}A$ 직접 계산 방식보다는 훨씬 안전하며, 구현과 속도 면에서 상대적으로 효율적이다. 따라서 일반적인 최소제곱 문제에서는 QR 분해가 매우 적합한 절충안이 된다. 특히, $m$이 $n$보다 훨씬 클 때 thin QR을 적용하면 공간과 시간을 크게 절약할 수 있다.

#### Wavelet 변환과 직교화

웨이블릿(wavelet) 변환에서는 다중해상도 분석(multi-resolution analysis)을 통해 신호를 단계적으로 분해한다. 이때 기저 함수를 축적해 가는 과정은, 수학적으로 보면 각 단계에서 직교성을 유지하거나 정규화 조건을 만족하도록 필터 계수를 구성하는 과정과 연결된다. Daubechies, Haar, Symlet 등 다양한 계열의 웨이블릿은, 내적 구조가 에너지를 보존하도록 설계되어 있다.

이는 QR 분해의 ‘직교화’ 정신과 맥락이 통한다. 신호를 분석할 때, $\mathbf{A}$라는 웨이블릿 행렬(또는 필터 뱅크)을 곱해서 변환 계수를 구하는 것은, 본질적으로는 직교(또는 준직교) 벡터 공간으로의 투영이다. 물론, 실제 웨이블릿 알고리즘에서 QR 분해를 직접 계산하는 일은 드물지만, 웨이블릿 계수 설계가 내포하는 직교(혹은 정규직교) 조건이 QR 혹은 Gram-Schmidt와 맞닿아 있다고 해석할 수 있다.

#### 수치 라운딩과 직교행렬의 왜곡

실제로 부동소수점 환경에서 아무리 직교행렬 $\mathbf{Q}$를 만들어도, 연산 과정에서

$$
\mathbf{Q}^\mathsf{T}\mathbf{Q} \approx \mathbf{I}
$$

가 정확히 성립하기란 쉽지 않다. 많은 반복 연산과 내적 연산이 누적되면, 기계 정밀도의 한계로 인해 $\mathbf{Q}$가 살짝 비직교 형태가 되기 때문이다. Householder나 Givens 회전은 이러한 왜곡을 상대적으로 억제하지만, 완벽히 방지할 순 없다.

어떤 응용에서는 $\mathbf{Q}$가 정말로 정밀하게 직교적이길 요구한다. 예를 들어, 다항식 근사나 물리 시뮬레이션에서 에너지가 보존되어야 하는 경우, 조금이라도 벗어난 직교행렬은 시뮬레이션 결과를 누적 편향으로 몰고 갈 수 있다. 이럴 땐, 한 번 직교화한 뒤 후처리로, 직교행렬에 가까운 행렬을 찾는 별도의 단계(Orthogonal Procrustes 문제 등)를 통해 추가 보정을 하기도 한다.

#### Lanczos 및 Arnoldi 반복에서의 직교화

큰 스펙트럼(고윳값) 문제를 반복법으로 접근할 때, Lanczos나 Arnoldi 알고리즘이 대표적이다. Lanczos 알고리즘은 대칭 행렬의 최대고윳값을 효율적으로 찾는 과정에서 벡터를 재귀적으로 업데이트하고, Arnoldi 알고리즘은 비대칭(또는 복소) 행렬에 대해 Hessenberg 형태를 만들어 가면서 Krylov 하부공간을 확장한다.

이 모든 과정의 핵심은, 새롭게 얻는 벡터를 기존 벡터들과 직교화하는 단계다. 직교화를 수행하지 않으면, 기본적인 재귀공식 자체가 고윳값 추정의 정밀도를 보장하지 못하게 된다. 특히, Lanczos는 수치적 오류가 누적되면 실제로는 bi-orthogonal화된 GMRES 계열과 비슷한 오차가 발생할 수 있으므로, 선택적 Reorthogonalization이나 Modified Gram-Schmidt를 병행하여 직교성을 유지하는 전략을 채택한다.

#### 준직교(quasi-orthogonal) 접근

실제로 완벽한 직교 대신, 어느 정도의 허용 오차 범위 안에서 직교성을 만족시키는 ‘준직교’ 개념을 사용하는 상황이 있다. 예컨대, 컴퓨터 그래픽스나 신호처리에서, 미세한 수치 오차를 억지로 제거하는 대신, 기준 임계값 이하의 오차는 자연스럽게 허용해 계산 효율을 높인다. 이를테면 기하학적 모델의 변환행렬이 부동소수점 오차로 인해 약간 스케일이 틀어져 있어도, 시각적으로 큰 차이가 없다면 굳이 완벽한 직교행렬로 보정하지 않아도 되는 식이다.

수치선형대수에서 QR 분해 후의 $\mathbf{Q}$도 마찬가지다. 크기가 매우 큰 $m\times n$ 행렬에 대해서, $|\mathbf{Q}^\mathsf{T}\mathbf{Q} - \mathbf{I}|\_F$나 $|\mathbf{Q}^\mathsf{T}\mathbf{Q} - \mathbf{I}|\_2$가 충분히 작은 편이라면, 특별히 재직교화를 할 필요 없이 후방대입 단계로 넘어가도 된다. 결국 문제의 물리적/통계적 맥락에 따라, “얼마나 정확한 직교화가 필요한가?”가 결정된다.

#### 현대적 응용: Randomized QR

최근에는 랜덤화 기법을 결합한 QR 분해 방법이 주목받고 있다. 대규모 데이터 행렬(예: $10^5\times 10^3$)에서, 전통적 QR 분해가 너무 시간이 오래 걸거나 메모리 사용량이 너무 큰 경우, 임의의 스케치(sketch)나 샘플링을 통해 행렬의 랭크 구조를 대략 추정하는 ‘Randomized QR’ 기법이 활용된다. 대표적 접근은

1. $\mathbf{A}$에 랜덤 행렬 $\mathbf{\Omega}$를 곱해 축소된 공간에서 대표를 뽑고
2. 그 대표 벡터들을 다시 한 번 정교하게 직교화하여 원하는 품질의 QR을 얻는 방식.

이를 통해 $m\times n$에서 $m\gg n$인 극단적 상황에서도, 전체 열에 대해 전부 Gram-Schmidt를 수행하지 않고도 근사적 QR 분해를 빠르게 구할 수 있다. 물론 이는 근사 해석을 전제로 하므로, 정밀도가 정말 중요한 문제(예: 중요 공학 계산)보다는 빅데이터 분석이나 기계학습 전처리 단계에 더 적합하다.

#### 추가 요약

QR 분해는 수치선형대수학에서 매우 광범위하게 응용되고, 직교화의 중요한 특징인 수치적 안정성을 활용해 선형방정식, 최소제곱, 고윳값 문제, 대규모 계산, 머신러닝, 통계 등 다양한 분야에서 필수 도구가 된다. 본 장에서 다룬 내용(Gram-Schmidt, Householder, Givens, Pivoted QR, Rank-Revealing QR, Block QR, Randomized QR 등)을 실무적으로 잘 선택해 사용하면, 고성능 계산과 높은 정확도를 양립할 수 있다.

#### 무선 통신에서의 QR 검출

대규모 MIMO(Multiple-Input Multiple-Output) 무선 통신 시스템에서, 송신 안테나와 수신 안테나가 여러 개 존재할 때, 수신 신호를 해석하기 위해 해결해야 하는 대표적 문제는

$$
\mathbf{y} = \mathbf{H},\mathbf{s} + \mathbf{n}
$$

와 같은 형태다. 여기서 $\mathbf{H}$는 채널행렬(channel matrix)이고, $\mathbf{s}$는 송신 신호(보통 복소수 스칼라 혹은 벡터), $\mathbf{n}$은 노이즈다. 만약 $\mathbf{H}$가 정방 혹은 직사각의 풀랭크 행렬이라면, 간단히 선형검출(linear detection) 문제로 접근할 수 있다. 이때 QR 분해를 $\mathbf{H} = \mathbf{Q}\mathbf{R}$ 형태로 수행하면,

$$
\mathbf{y} = \mathbf{Q}\mathbf{R},\mathbf{s} + \mathbf{n}
$$

가 되고, 직교행렬 $\mathbf{Q}$ 특성을 활용하여 양변에 $\mathbf{Q}^{\mathsf{H}}$(복소 정규직교)나 $\mathbf{Q}^{\mathsf{T}}$(실수 케이스) 등을 곱해

$$
\mathbf{y}' = \mathbf{R},\mathbf{s} + \mathbf{n}'
$$

로 나타낼 수 있다. 상삼각 구조를 갖는 $\mathbf{R}$로 인해, 신호 검출(예: ZF, Zero Forcing)에서 후방대입(back-substitution)으로 간단히 각 신호를 추정할 수 있게 된다.

또한, 하드 결정(hard decision) 기반의 심볼 검출이나(예: $M$-QAM, $M$-PSK), 유사최우도(ML-like) 검출 방식을 QR 변환 뒤에 적용함으로써, 연산 부담을 크게 낮출 수 있다. 대규모 MIMO 채널에서 SVD 검출 역시 가능하지만, QR 방식이 좀 더 간단하며 실시간 처리에 적합하다는 장점이 있다.

#### Kalman 필터에서의 QR 적용

확장 칼만 필터나 무향 칼만 필터 등 다양한 변형에서도, 예측과 업데이트 방정식을 풀 때 상삼각 또는 대각화 형태를 선호한다. 특히, 국소적 선형화 과정에서 얻게 되는 야코비 행렬(Jacobian)에 대해 QR 분해를 사용하면, 직접적인 역연산을 하지 않고서도 관측정보를 안정적으로 융합할 수 있다.

어떤 필터 공식을 업데이트 형태로 작성하면

$$
\mathbf{x}*{k} \leftarrow \mathbf{x}*{k} + \mathbf{K},( \mathbf{z}*{k} - \mathbf{H},\mathbf{x}*{k}),
$$

여기서 $\mathbf{K}$는 필터 이득(gain)을 의미하고, $\mathbf{H}$는 측정 행렬(관측 연산자)이다. 전통적으로는

$$
\mathbf{K} = \mathbf{P},\mathbf{H}^{\mathsf{T}}\bigl(\mathbf{H},\mathbf{P},\mathbf{H}^{\mathsf{T}} + \mathbf{R}\bigr)^{-1}
$$

같은 형태다. 직접 역연산 대신, $\mathbf{H},\mathbf{P},\mathbf{H}^{\mathsf{T}} + \mathbf{R}$를 QR 분해하거나, 더욱 일반화된 분해(Schur, LDL 등)를 사용해 역대신에 후방대입을 수행하면, 부동소수점 오차가 덜 누적되는 장점이 있다. 차수가 큰 문제나 부분 관측(partial observation) 상황에선, 재귀적으로 업데이트하면서도 직교화를 유지하는 방향으로 칼만 필터를 설계하기도 한다.

#### Orthogonal Procrustes 문제와 재직교화

Orthogonal Procrustes 문제는, 두 행렬 $\mathbf{A}$와 $\mathbf{B}$가 주어졌을 때, 직교행렬 $\mathbf{Q}$를 찾아서

$$
\min\_{\mathbf{Q}^\mathsf{T}\mathbf{Q} = \mathbf{I}} |\mathbf{A}\mathbf{Q} - \mathbf{B}|\_F
$$

를 만족하게 하는 문제다. 이때 QR 분해가 간접적으로 사용된다. 예컨대, $\mathbf{B}^\mathsf{T}\mathbf{A} = \mathbf{V}\mathbf{\Sigma}\mathbf{U}^\mathsf{T}$ 형태의 SVD를 먼저 구하면, 최적의 직교행렬은 $\mathbf{Q}^\star = \mathbf{U}\mathbf{V}^\mathsf{T}$로 나온다. 만약 SVD 대신 QR로 문제의 차원을 단순화하거나, 혹은 $\mathbf{A}$와 $\mathbf{B}$가 이미 특정 직교 형태를 갖고 있다면, Gram-Schmidt나 Householder 과정을 중간 단계로 수행하기도 한다.

이 문제는, “직교행렬 $\mathbf{Q}$를 찾는” 행위 그 자체가 수치적으로 민감할 수 있으므로, 재직교화 과정을 병행하며 해를 구하는 방식을 택한다. 특히, $\mathbf{A}$, $\mathbf{B}$가 서로 크기가 많이 다르면, QR/대각화/정규화 스텝을 적절히 조합해 최적해를 구해낸다.

#### Triangular Solve와 BLAS

QR 분해 뒤에 반드시 뒤따르는 작업은 상삼각 계(system) $\mathbf{R}\mathbf{x} = \mathbf{c}$를 푸는 것이다. BLAS(Library of Basic Linear Algebra Subprograms)에서는 이 과정을 “TRSV(triangular solve)” 연산으로 표준화해 놓았다. LAPACK 역시 $x = \mathbf{R}^{-1}\mathbf{c}$를 후방대입(back-substitution)으로 효율적으로 해결하기 위해, 내부적으로 최적화된 “trsm” 또는 “trsv” 루틴을 사용한다.

이처럼 QR 분해를 통해 얻어진 $\mathbf{R}$이 상삼각 구조라면, 별도의 역행렬(Explicit Inverse)을 구하지 않고도, 단순히 $O(n^2)$ 복잡도로 해 벡터 $\mathbf{x}$를 빠르게 구할 수 있다. LU 분해일 경우에도 “forward”와 “backward” substitution을 수행하지만, QR가 $LU$ 대비 더욱 안정적일 때가 많고, 희소 행렬인 경우에도 Givens 회전을 통해 부분 2×2 삼각화를 관리하기 때문에 특수 연산 루틴과 궁합이 좋다.

#### 심볼릭 QR과 자동미분

기호(symbolic) 기반 계산 환경(예: Mathematica, Maple)에서는, 행렬 $\mathbf{A}$의 원소가 실제 상수라기보다 어떤 변수들의 식(expression)으로 주어지는 상황도 나타난다. 이때 QR 분해를 상징적으로 계산해 두면, 향후 각 변수에 특정 값을 대입할 때마다, 직교화 결과가 어떻게 바뀌는지를 자동으로 추적 가능하다.

여기에 자동미분(automatic differentiation) 기법을 조합하면, 예를 들어

$$
\mathbf{A}(\boldsymbol{\theta})
$$

가 여러 파라미터 $\boldsymbol{\theta}$에 의해 결정될 때, $\mathbf{Q}(\boldsymbol{\theta}), \mathbf{R}(\boldsymbol{\theta})$의 미분(혹은 기울기, 야코비, Hessian)을 분석할 수 있다. 머신러닝이나 최적화에서, Loss 함수가 $\mathbf{A}$의 행렬 연산 형태로 표현되어 있고, QR 분해가 중간 계산 단계로 들어가는 경우에 이 기법이 사용된다. 다만, 심볼릭 QR는 행렬 크기가 커지면 식이 매우 복잡해질 수 있으므로, 실제로는 부분 기울기만 구하거나, 블록 단위로 미분을 수행하는 전략을 쓴다.

#### 작용소(operator) 형태의 QR

행렬이 아니라 연산자(operator) 차원에서 직교화를 고려하는 상황도 있다. 예컨대, 무한 차원 함수공간(힐베르트 공간)에서 특정 적분연산자나 차분연산자를 분해하려고 할 때, 스펙트럴(discretization) 기법을 도입하면 결국 큰 차원($m\times n$)의 행렬 근사를 얻게 된다. 이 행렬에 QR를 적용하면, 원래 무한 차원의 문제에서 “직교 기반의 공간 분해”를 유도하는 것이 가능하다.

적분방정식을 수치적으로 풀 때, Galerkin 혹은 Collocation 방법으로 디스크리타이즈(discretize)하면 생성되는 계수가 종종 비정규(non-normal)나 준직교적인 구조를 가질 수 있다. 이 상황에서, QR나 SVD 같은 분해를 통해, “가장 많이 기여하는 모드(mode)”만 골라서 근사하는 식으로 축소차원 모델(reduced-order model)을 만들 수도 있다. 즉, operator-level에서의 직교화가 행렬 수준으로 번안된 뒤, QR 분해가 그 핵심 알고리즘이 되는 셈이다.

#### 유체 시뮬레이션과 QR 안정화

유체역학 시뮬레이션(CFD)에서, 점진적으로 시간적/공간적 해를 구하면서 많은 양의 선형계 풀이가 반복된다. 불안정한 유동(instability)이나 난류(turbulence) 해석 중에는, 작은 수치 오차가 빠르게 증폭되기도 한다. 이때, 선형계 풀이 단계에서 QR 분해를 적용해, 잔류(residual)를 꾸준히 관찰하고 필요 시에는 재직교화를 시행한다.

특히, 비압축성(초음속이 아닌 범위) 유체 해석에서는 Poisson 방정식 같은 것이 중간에 등장하고, 큰 스파스(sparse) 계수행렬을 다루게 된다. 여기서 희소행렬 전용 Householder나 Givens 기법(또는 Iterative Methods + 재직교)이 적용되어, 안정된 시뮬레이션을 뒷받침한다. 또한, 수치 점성이 중요한 문제(고레 분리, 경계층 분리 등)에서 스펙트럴 정밀도가 요구되면, 직교화 기반 분해가 필수적이다.

#### PDE 솔버와 QR

편미분방정식(PDE) 솔버(특히 안정성 분석을 하는 솔버)에서, 진동해(oscillatory solution)나 경계층(bl boundary layer)을 다룰 때, 각 단계별 해가 매우 민감하다. Krylov 하부공간 기법(GMRES, BiCGSTAB, CG 등)이나 직교화 알고리즘이 PDE 솔버 코어에 통합되어, 반복법 수렴과정에서 발생하는 오차 누적을 제어한다. LU 분해도 자주 쓰이지만, QR가 조건수가 나쁜 문제에 대해서 더 견고한 경우가 적지 않다.

예컨대, GMRES는 내부적으로 Arnoldi 과정을 통해 획득되는 직교기저를 사용한다. 이것이 일종의 QR와 유사한 개념(상삼각 Hessenberg 행렬이 생김)으로 이해될 수 있다. PDE가 고차원이 되면, 효율적 재직교(modified Gram-Schmidt, Householder 등)와 다양한 사전조건(preconditioning)을 결합해, 반복 횟수를 줄이고 계산 정확도를 높이는 전략을 취한다.

#### 확률적 기법과 QR

확률적 알고리즘(예: 몬테카를로, MCMC)에서, 상태공간 전이를 정의하기 위해 직교변환을 도입하는 사례가 있다. 표준 정규분포 샘플링 등에서, 공분산 구조를 반영하기 위한 Cholesky 분해가 자주 사용되지만, QR 분해도 마찬가지로 직교 구조를 구현할 수 있으므로, 여러 변수 간 상관관계를 조정하거나, 샘플링 편차를 줄이는 목적 등으로 활용된다.

특히, $\mathbf{R}$이 쉽게 역을 구할 수 있는 상삼각 형태이므로, 가우시안 random variable 생성에 필요한 선형 변환 과정을 효율적으로 적용할 수 있다. 샘플링이 끝난 뒤에는, 희소 행렬 구조나 부분 샘플링 기법으로 다시 QR 분해를 수행해, 주성분에 해당하는 공간만 남기는 식으로 차원을 줄이는 작업도 가능하다.

#### 양방향 QR (bi-directional)

일부 특수 알고리즘에서는, 행렬의 양쪽에서 동시에 직교화를 진행해 가운데 부분을 상삼각 혹은 상헤센버그 형태로 좁혀가는 방식을 택한다. 이는 특히 분산 환경에서의 통신량 균형을 위해 도입되기도 하고, 또는 비정규행렬에 대한 특정 대칭화(symmetric-like) 처리에 유용하다. 양방향 Householder나 양방향 Givens를 병렬화하면, 행렬 양끝단에서 동시에 0을 만들어 나가며, 중간에서 만나도록 설계한다.

이 기법은 수렴 성능이나 계산성능이 전통적인 한쪽 방향 변환보다 반드시 낫다는 보장은 없지만, 하드웨어 최적화나 메모리 트래픽 측면에서 이점이 있을 수 있다. 알고리즘 복잡도가 올라가므로, 실제로는 대단히 큰 스케일의 문제에서만 의미가 있다.