Speacial Matrices and Applications

열수철·2025년 3월 4일

1. 연속 문제의 이산화와 유한 차분법

미분방정식
$\frac{d^2u}{dx^2}$ = $f(x)$ $(0<x<1)$

와 경계 조건 $u(0)=u(1)=0$ 을 가진 문제는, 예를 들어 막대의 온도 분포 문제 등에서 나타납니다.
컴퓨터에서는 연속적인 $u(x)$ 를 다룰 수 없으므로, 구간 $[0,1]$ 을 $n$ 개의 균등 간격 (h)로 분할하고, 각 점 $x = jh$ 에서 $u(x)$ 의 값을 $u_j$ 로 근사합니다.
유한 차분법을 사용하여 도함수를 근사하면, 두 번째 도함수는
(중앙 차분 2번 사용 하면 구할 수 있음)
$u_{j+1}-2u_j+u_{j-1} \approx h^2 f(jh)$
의 형태가 되어, 전체 문제는 선형 시스템 $Au=b$ 로 표현됩니다.

2. 밴드 행렬과 그 응용

2.1 밴드 행렬(Band Matrix)이란?

실제 문제에서 이산화 과정을 거쳐 만들어지는 계수 행렬 (A)는 대부분 일정한 패턴을 갖습니다. 대표적인 예가 밴드 행렬인데, 이는 행렬의 대부분 원소가 0이고, 주대각선과 그 주변 몇 개의 대각선에만 비영(非零) 원소가 집중된 형태입니다.

삼대각 행렬(Tridiagonal Matrix):
가장 단순한 형태로, (A)의 비영 원소들이 오직 주대각선와 바로 위, 아래 대각선에만 나타납니다.
예를 들어, 위의 차분 방정식에서 나온 (A)는 다음과 같은 삼대각 행렬의 형태를 갖습니다.
$\begin{pmatrix} 2 & 1 & 0 & \cdots & 0\\ 1 & 2 & 1 & \cdots & 0\\ 0 & 1 & 2 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & 1\\ 0 & 0 & 0 & 1 & 2\\ \end{pmatrix}$
일반 밴드 행렬:
비영 원소가 주대각선을 중심으로 좌우로 (w-1)개의 대각선에만 분포하는 경우, 이를 밴드 폭(bandwidth)가 (w)인 행렬이라고 합니다.
이때 “반대각폭(half bandwidth)”은 대각선 양쪽에서 몇 개의 대각선에 값이 채워졌는지를 의미하며, (w)가 작을수록 행렬은 희소하고 연산량은 크게 줄어듭니다.

2.2 특수 행렬의 추가 성질

대칭성:
실제 미분방정식을 근사할 때 사용되는 유한 차분식은 중심 차분법을 사용하므로, 생성되는 행렬 (A)는 대칭성을 띱니다. 즉, $a_{ij}=a_{ji}$ 가 되어 $A^T=A$ 를 만족합니다.
대칭 행렬은 LDL $^T$ 분해와 같은 특수 분해법을 적용할 수 있어, 수치 안정성과 계산 효율이 크게 향상됩니다.
양의 정부호(Positive Definiteness):
위 문제처럼 경계 조건이 0인 경우, $A$ 는 보통 모든 피벗이 양수인 양의 정부호 행렬이 됩니다.
이는 수치해법에서 매우 중요한데, 피벗들이 양수이면 행 교환 없이 안정적으로 가우스 소거법을 진행할 수 있습니다.

2.3 밴드 행렬의 계산적 장점

밴드 행렬은 그 구조 덕분에 가우스 소거법을 사용할 때 연산량이 크게 감소합니다.

연산량 감소:
일반 $n\times n$ 행렬의 경우 가우스 소거법은 대략 $O(n^3)$ 연산이 필요하지만, 밴드 행렬에서는 각 열마다 처리하는 원소의 수가 $w$ 에 제한되므로 전체 연산량이 $O(nw^2)$ 정도로 줄어듭니다.
삼대각 행렬 $(w=3)$ 의 경우 실제 연산 횟수는 $O(n)$ 혹은 $O(n^2)$ 수준이 됩니다.
실제 응용:
열전달, 구조 해석, 진동 해석 등 다양한 분야에서 연속 문제를 이산화할 때 얻어지는 계수 행렬은 대개 밴드 행렬 구조를 띄므로, 이러한 특성을 활용한 특별 알고리즘(예, Thomas 알고리즘)으로 빠르게 문제를 해결할 수 있습니다.

3. 수치해법의 안정성과 반올림 오차(Roundoff Error)

3.1 반올림 오차가 발생하는 이유

컴퓨터는 유한한 유효숫자를 유지하면서 산술 연산을 수행합니다.
예를 들어, 3자리 유효숫자만 남긴다면,
$[ 456 + 0.0123 ]$
작은 값 0.0123의 뒷자리 정보가 소실되어 실제 결과와 오차가 발생할 수 있습니다.

3.2 반올림 오차의 누적과 민감도

연산 횟수와 누적 오차:
100×100 행렬의 경우, 가우스 소거법은 약 $\frac{1}{3}n^3$ (300만 번 미만) 연산을 수행합니다.
각 연산마다 미세한 오차가 발생하면, 이 오차들이 누적되어 최종 해에 큰 영향을 줄 수 있습니다.
Ill-conditioned 문제:
조건수가 큰 행렬에서는 오른쪽 상수벡터 $b$ 의 아주 작은 변화에도 해가 크게 달라질 수 있습니다.
예를 들어,
$A=\begin{pmatrix}1 & 1\\1 & 10001\end{pmatrix}$
같은 경우, $b$ 의 미세한 변화가 $u$ 와 $v$ 의 해에 극적으로 반영되어, 계산된 해가 실제 해와 큰 차이를 보일 수 있습니다.
잘 조건된 행렬에서도 발생하는 문제:
예를 들어,
$B=\begin{pmatrix}0.0001 & 1\\1 & 1\end{pmatrix}$

와 같이 조건수는 양호하더라도, 만약 피벗으로 0.0001과 같이 매우 작은 수가 선택된다면, 그 작은 수로 아래 행을 소거할 때 큰 배수가 곱해져 오차가 증폭됩니다.
이로 인해 반올림 오차가 전체 해에 심각한 왜곡을 가져올 수 있습니다.

3.3 안정성을 위한 피벗팅 전략

이러한 문제를 해결하기 위해 가우스 소거법에서는 피벗팅(pivoting) 기법을 사용합니다.

부분 피벗팅 (Partial Pivoting):
각 열에서 가능한 모든 후보 원소 중 절대값이 가장 큰 원소를 선택하여 피벗으로 사용합니다.
이를 통해 작은 값으로 인한 오차 증폭을 방지할 수 있습니다.
완전 피벗팅 (Complete Pivoting):
필요에 따라 행과 열 모두를 교환하여 가장 큰 값을 피벗으로 선택하는 방법도 있지만, 계산 비용 때문에 일반적으로 부분 피벗팅이 많이 사용됩니다.

이러한 피벗팅 기법은 수치해석 분야의 선구자인 폰 노이만과 Wilkinson 등이 연구한 결과로, 오늘날 수치 선형대수의 기본 알고리즘으로 자리 잡고 있습니다.