1.1 동기와 전체 그림

수치선형대수의 주인공은 \(Ax=b\), 최소제곱, 고유값, 특이값 같은 익숙한 문제들이다. 그런데 여기서 질문은 “해가 무엇인가?”에서 멈추지 않는다. “얼마나 빠르게 구할 수 있는가?”, “반올림 오차가 해를 얼마나 흔드는가?”, “문제 자체가 작은 입력 변화에 얼마나 예민한가?”까지 묻는다. 칠판에서는 \(A^{-1}b\)라고 쓰면 끝나지만, 실제 계산에서는 역행렬을 만들지 않고 분해와 치환으로 해를 구하는 편이 보통 더 빠르고 더 안정적이다.

앞으로 반복해서 등장할 세 단어는 비용, 정확도, 안정성이다. 비용은 대략 몇 번의 산술연산과 얼마나 많은 저장공간이 필요한지를 뜻하고, 정확도는 계산된 \(\hat{x}\)가 참해 \(x\)에 얼마나 가까운지를 뜻한다. 안정성은 조금 더 영리한 관점이다. 계산된 답이 원래 문제의 정확한 답은 아니더라도, 아주 조금 바뀐 문제 \((A+\Delta A)\hat{x}=b+\Delta b\)의 정확한 답이라면 그 알고리즘은 믿을 만하다고 본다. 즉 좋은 알고리즘은 “실수는 하되, 작은 실수만 한다.”

1.2 선형시스템이 나타나는 예

선형시스템은 단순한 연습문제가 아니라 모델링의 기본 문법이다. 열전도나 탄성체를 격자로 나누면 각 격자점의 미지수가 이웃과 연결되어 \(Ax=b\) 꼴이 되고, 전기회로에서는 키르히호프 법칙이 전압과 전류의 선형 방정식으로 모인다. 데이터 피팅에서도 잔차 \(\|Ax-b\|_2\)를 줄이는 문제가 생기며, 정규방정식 \(A^T A x=A^T b\)는 다시 선형시스템이 된다. 행렬은 숫자의 표가 아니라 관계의 압축 파일이다.

예를 들어 \(n\times n\) 조밀 행렬을 아무 구조 없이 풀면 직접해법의 대표 비용은 대략 \(O(n^3)\)이고 저장공간은 \(O(n^2)\)이다. 그러나 미분방정식 격자화에서 생기는 행렬은 대부분 원소가 0인 희소 행렬인 경우가 많아, 0을 저장하고 계산하는 것은 거의 의자까지 예약한 유령 손님을 대접하는 일이다. 그래서 수치선형대수는 같은 \(Ax=b\)라도 행렬의 대칭성, 양의 정부호성, 희소성, 대각 우세성 같은 성격을 먼저 살핀 뒤 그에 맞는 풀이법을 고른다.

1.3 유한 정밀도 계산

컴퓨터의 실수는 실수 전체가 아니라 정해진 자리수로 표현 가능한 부동소수점 수다. 표준적인 오차 모델은 산술연산 하나를 \[ \operatorname{fl}(x \circ y)=(x\circ y)(1+\delta),\qquad |\delta|\le u \] 로 본다. 여기서 \(\circ\)는 \(+,-,\times,/\) 중 하나이고, \(u\)는 단위 반올림 오차다. IEEE 배정밀도에서는 대략 \(u=2^{-53}\approx 1.11\times 10^{-16}\)이다. 이 모델은 “매 연산마다 아주 작은 상대오차가 붙는다”는 계산 세계의 일기예보처럼 쓰인다.

문제는 작은 오차가 항상 작게 남지는 않는다는 데 있다. 거의 같은 두 수를 빼면 앞자리의 믿을 만한 숫자들이 사라지는 소거가 일어난다. 예컨대 \(1.0000001-1.0000000\)은 결과가 \(10^{-7}\) 크기라서, 입력의 마지막 몇 자리 오차가 결과 전체를 좌우할 수 있다. 여러 수를 더할 때도 오차는 보통 \(\gamma_n=\frac{nu}{1-nu}\) 같은 형태로 누적된다고 추정한다. \(nu\ll1\)이면 별일 없지만, 항의 크기가 들쭉날쭉하거나 부호가 섞이면 계산 순서도 실력의 일부가 된다.

1.4 벡터, 행렬, 노름

오차를 말하려면 먼저 길이를 재는 자가 필요하다. 벡터 노름의 대표는 \(\|x\|_1=\sum_i |x_i|\), \(\|x\|_2=(\sum_i x_i^2)^{1/2}\), \(\|x\|_\infty=\max_i |x_i|\)이다. 어떤 노름을 고르느냐는 문제를 바라보는 렌즈를 고르는 일이다. 전체 에너지를 보고 싶으면 \(2\)-노름이 자연스럽고, 가장 큰 성분의 폭주가 걱정이면 \(\infty\)-노름이 잘 맞는다.

행렬 노름은 행렬이 벡터를 얼마나 키우는지를 잰다. 유도 노름은 \[ \|A\|=\max_{x\ne 0}\frac{\|Ax\|}{\|x\|} \] 로 정의되며, 특히 \(\|A\|_2=\sigma_{\max}(A)\)는 가장 큰 특이값과 같다. 중요한 성질은 \(\|Ax\|\le \|A\|\|x\|\)와 \(\|AB\|\le \|A\|\|B\|\)이다. 이 두 부등식은 오차 분석의 안전벨트다. 복잡한 오차식을 한 번에 이해하기 어렵더라도, “행렬을 지나며 얼마나 증폭될 수 있는가?”라는 질문으로 바꾸면 계산이 잡히기 시작한다.

1.5 정확도와 안정성

정확도는 보통 전방오차로 잰다. 참해가 \(x\), 계산해가 \(\hat{x}\)라면 상대 전방오차는 \(\|\hat{x}-x\|/\|x\|\)이다. 하지만 실제로는 참해를 모르는 경우가 대부분이므로 잔차 \(r=b-A\hat{x}\)를 본다. 잔차가 작다는 말은 \(\hat{x}\)가 원래 방정식을 거의 만족한다는 뜻이고, 이는 후방오차와 연결된다. 선형시스템에서는 “\(\hat{x}\)가 정확히 풀고 있는 가까운 문제는 무엇인가?”를 묻는 방식이 특히 강력하다.

안정적인 알고리즘은 작은 후방오차를 만든다. 예컨대 계산 결과가 \[ (A+\Delta A)\hat{x}=b,\qquad \frac{\|\Delta A\|}{\|A\|}=O(u) \] 를 만족한다면, 알고리즘은 입력 행렬을 마지막 몇 자리만 흔든 문제를 정확히 푼 셈이다. 그래도 전방오차가 반드시 작다는 보장은 없다. 가까운 문제의 답이 원래 문제의 답과 크게 다를 수 있기 때문이다. 그래서 정확도는 대략 “알고리즘의 안정성”과 “문제의 조건”이 함께 만든다. 계산의 성적표는 학생과 시험지가 같이 받는다.

1.6 조건과 조건수

조건은 알고리즘이 아니라 문제 자체의 예민함이다. 입력 \(x\)를 받아 출력 \(f(x)\)를 내는 문제에서 상대 조건수는 느슨하게 말해 \[ \kappa_f(x)\approx \lim_{\epsilon\to 0} \sup_{\|\Delta x\|\le \epsilon\|x\|} \frac{\|f(x+\Delta x)-f(x)\|/\|f(x)\|}{\|\Delta x\|/\|x\|} \] 이다. 입력을 \(1\%\) 흔들었을 때 출력이 최대 몇 \(\%\) 흔들릴 수 있는지를 보는 확대율이라고 생각하면 된다. \(\kappa\)가 작으면 좋은 조건, 크면 나쁜 조건이다.

소거는 조건이 나빠지는 대표 장면이다. 함수 \(f(a,b)=a-b\)에서 \(a\)와 \(b\)가 거의 같으면 출력은 작아지고, 입력의 작은 상대오차가 출력의 큰 상대오차로 튄다. 반면 \(a\)와 \(b\)의 크기가 충분히 다르면 같은 뺄셈도 덜 위험하다. 중요한 구분은 이것이다. 조건수가 크면 아무리 안정적인 알고리즘도 많은 정확한 자릿수를 기대하기 어렵고, 조건수가 작으면 안정적인 알고리즘이 보통 좋은 답을 준다. 나쁜 문제를 좋은 알고리즘이 마술처럼 건강하게 만들 수는 없다.

1.7 선형시스템의 조건수

선형시스템 \(Ax=b\)에서 \(A\)가 가역일 때 해는 \(x=A^{-1}b\)다. 오른쪽 항만 \(b+\Delta b\)로 바뀌면 \(\Delta x=A^{-1}\Delta b\)이고, \[ \frac{\|\Delta x\|}{\|x\|} \le \|A\|\|A^{-1}\|\frac{\|\Delta b\|}{\|b\|} \] 이다. 여기서 \(\kappa(A)=\|A\|\|A^{-1}\|\)가 선형시스템의 조건수다. \(2\)-노름에서는 \(\kappa_2(A)=\sigma_{\max}(A)/\sigma_{\min}(A)\)라서, 가장 많이 늘리는 방향과 가장 적게 늘리는 방향의 비율로 읽을 수 있다.

행렬 \(A\) 자체도 흔들리면 이야기는 조금 더 매워진다. 대략 \(\|A^{-1}\|\|\Delta A\|<1\)일 때 \[ \frac{\|\Delta x\|}{\|x\|} \lesssim \frac{\kappa(A)}{1-\kappa(A)\|\Delta A\|/\|A\|} \left( \frac{\|\Delta A\|}{\|A\|}+ \frac{\|\Delta b\|}{\|b\|} \right) \] 같은 형태의 경계가 나온다. 직교행렬은 \(\kappa_2=1\)이라 길이를 왜곡하지 않는 모범생이고, 거의 특이한 행렬은 \(\sigma_{\min}\)이 작아 조건수가 폭발한다. 그래서 작은 잔차가 있어도 조건수가 크면 해의 성분은 크게 틀릴 수 있다. 잔차는 “방정식을 잘 만족했는가”를, 조건수는 “그 만족이 해를 얼마나 보장하는가”를 말한다.

2.1 일반적인 고려사항

\(Ax=b\)를 푼다고 해서 보통 \(A^{-1}\)을 계산하지 않는다. 역행렬을 명시적으로 만들면 비용도 크고 오차도 불필요하게 늘 수 있다. 대신 \(A\)를 삼각행렬들의 곱으로 분해한 뒤, 전진대입과 후진대입으로 푼다. 하삼각 \(L\)과 상삼각 \(U\)에 대해 \(A=LU\)라면 \(Ly=b\), \(Ux=y\)를 차례로 풀면 된다. 삼각시스템 하나는 \(O(n^2)\), 조밀 LU 분해는 대략 \(\frac{2}{3}n^3\)번의 곱셈-덧셈 규모가 든다.

직접해법을 고를 때는 행렬의 구조가 계산법을 결정한다. 일반 조밀 행렬이면 피벗팅을 곁들인 LU가 기본이고, 대칭 양의 정부호 행렬이면 Cholesky가 더 빠르고 저장도 덜 쓴다. 같은 \(A\)로 여러 \(b\)를 풀어야 한다면 분해를 한 번 저장해 두고 오른쪽 항마다 삼각해법만 반복하면 된다. 계산 후에는 잔차 \(r=b-A\hat{x}\)를 확인하는 습관이 좋다. 잔차가 작으면 적어도 “가까운 문제는 잘 풀었다”는 신호를 얻는다.

2.2 LU 분해

가우스 소거법은 \(A\)의 아래쪽 원소를 차례로 없애 상삼각행렬로 만드는 과정이고, 그때 사용한 소거 계수를 모으면 \(L\)이 된다. 피벗 교환까지 포함하면 보통 \[ PA=LU \] 로 쓴다. \(P\)는 행 교환을 기록한 순열행렬이다. 풀이 순서는 \(Ly=Pb\), \(Ux=y\)다. 여기서 \(L\)의 대각을 1로 두는 관례를 쓰면 저장공간도 아낄 수 있어, 실제 구현에서는 \(L\)과 \(U\)를 원래 행렬 자리 안에 함께 넣는 경우가 많다.

피벗팅은 단순한 장식이 아니라 안정성의 안전장치다. 피벗 원소가 너무 작으면 소거 계수가 커지고, 작은 반올림 오차가 행렬 전체로 퍼질 수 있다. 부분 피벗팅은 현재 열에서 절댓값이 큰 원소를 피벗으로 고르기 위해 행을 바꾸며, 실전에서 매우 좋은 안정성을 보인다. 이론적으로는 성장인자 \(\rho=\|U\|_\infty/\|A\|_\infty\)가 커질 수 있지만, 많은 실제 문제에서는 적당히 얌전하다. LU의 요령은 “0을 만들되, 너무 작은 수로 나누지는 말자”다.

2.3 Cholesky와 LDLT 분해

\(A\)가 대칭 양의 정부호, 즉 모든 \(x\ne0\)에 대해 \(x^T A x>0\)이면 더 좋은 길이 열린다. 이때 \[ A=LL^T \quad \text{또는} \quad A=R^T R \] 꼴의 Cholesky 분해가 가능하다. 조밀 행렬에서 비용은 대략 \(\frac{1}{3}n^3\)으로 LU의 절반 수준이고, 대칭성 덕분에 저장도 절약된다. 양의 정부호 조건은 피벗팅 없이도 계산이 안정적으로 진행되게 해 주는 든든한 보증서다.

\(LDL^T\) 분해는 제곱근을 피하고 대각 행렬 \(D\)를 따로 두는 방식이다. 양의 정부호라면 \(D\)의 대각 원소가 양수로 나오며 Cholesky와 거의 같은 정보를 담는다. 대칭이지만 부호가 섞인 부정 행렬에서는 \(LDL^T\)도 가능하지만, 안정성을 위해 대칭 피벗팅이나 \(1\times1\), \(2\times2\) 블록 피벗을 사용한다. 한 가지 조심할 점은 최소제곱에서 정규방정식 \(A^T A x=A^T b\)를 만들면 조건수가 대략 \(\kappa(A)^2\)로 나빠진다는 것이다. Cholesky가 빠르다고 해서 모든 문을 그 열쇠로 열면 안 된다.

2.4 희소 행렬

희소 행렬에서는 0이 아닌 원소만 저장하고 계산하는 것이 핵심이다. 대표 저장 형식인 CSR이나 CSC는 값, 인덱스, 행 또는 열 포인터를 따로 저장해 \(\operatorname{nnz}(A)\), 즉 비영 원소 수에 비례하는 저장을 목표로 한다. 하지만 희소 직접해법에서 진짜 변수는 분해 중 새로 생기는 비영 원소, 곧 fill-in이다. 원래 \(A\)가 희소해도 \(L\)과 \(U\)가 빽빽해지면 계산의 장점이 사라진다.

fill-in은 행렬을 그래프로 보면 더 잘 보인다. 변수는 정점, 비영 원소는 연결선이고, 소거는 한 정점을 없애면서 그 이웃들을 서로 연결하는 일에 가깝다. 따라서 소거 순서를 잘 고르면 새 연결선을 줄일 수 있다. AMD, nested dissection 같은 재정렬 기법은 수치값을 바꾸기보다 계산의 지형을 바꾼다. 희소 Cholesky나 희소 LU는 보통 기호분해로 구조와 저장공간을 먼저 예측하고, 수치분해에서 실제 값을 계산한다. 희소성은 공짜 속도가 아니라, 구조를 읽을 줄 아는 사람에게 주는 할인권이다.

3.1 QR 분해

선형대수에서 \(A=QR\)이라고 쓰면, 행렬 \(A\)를 길이와 각도를 잘 보존하는 부분 \(Q\)와 위삼각 행렬 \(R\)로 나누어 보겠다는 뜻이다. \(Q\)의 열들이 서로 직교정규라면 \(Q^TQ=I\)이고, 따라서 \(Q\)를 곱하는 일은 벡터를 찌그러뜨리지 않는다. 수치계산에서는 이 점이 아주 중요하다. 같은 연립방정식을 풀더라도, 길이를 마구 키우고 줄이는 계산보다 직교 변환을 쓰는 계산이 반올림오차에 훨씬 덜 예민하다.

\(m\ge n\)이고 \(A\in\mathbb{R}^{m\times n}\)의 열들이 선형독립이면 얇은 QR 분해는 \[ A = QR,\qquad Q\in\mathbb{R}^{m\times n},\quad Q^TQ=I,\quad R\in\mathbb{R}^{n\times n} \] 로 쓴다. 고전 Gram-Schmidt는 직관적이지만 수치적으로는 직교성이 조금씩 샌다. 수정 Gram-Schmidt, Householder 반사, Givens 회전은 그 누수를 더 잘 막는다. 특히 Householder 방법은 벡터 하나를 좌표축 방향으로 반사시켜 아래쪽 성분을 한꺼번에 0으로 만드는 방식이라, 조밀 행렬의 QR 분해에서 표준적인 선택이다.

3.2 선형계의 해 존재성

\(Ax=b\)가 풀리는지 묻는 말은 사실 \(b\)가 \(A\)의 열공간 \(\mathcal{R}(A)\) 안에 있느냐를 묻는 말이다. \(A\)의 열벡터들을 재료라고 생각하면, \(Ax\)는 그 재료들의 선형결합으로 만들 수 있는 모든 벡터다. 따라서 \(b\notin\mathcal{R}(A)\)이면 정확한 해는 없다. 반대로 \(b\in\mathcal{R}(A)\)이면 해가 적어도 하나 있으며, \(A\)의 영공간 \(\mathcal{N}(A)\)에 0이 아닌 벡터가 있으면 해는 하나가 아니라 무수히 많아진다.

계수 행렬의 랭크는 이 이야기를 정리해 주는 언어다. \(\operatorname{rank}(A)=n\)인 tall 행렬은 열들이 독립이므로 최소제곱 해가 유일해지고, \(\operatorname{rank}(A)

3.3 최소제곱 문제

데이터가 방정식보다 많으면 \(Ax=b\)를 정확히 만족시키기 어렵다. 이때 우리는 해를 포기하는 대신, 오차 \(r=b-Ax\)의 길이를 가장 작게 만드는 \(x\)를 찾는다. 즉 최소제곱 문제는 \[ \min_x \|Ax-b\|_2 \] 이다. 기하적으로는 \(b\)를 \(A\)의 열공간 위로 정사영하고, 그 그림자 \(Ax_\star\)를 만드는 계수 \(x_\star\)를 찾는 일이다. 잔차 \(r_\star=b-Ax_\star\)는 열공간에 수직이므로 \(A^Tr_\star=0\)이다.

이 조건에서 정규방정식 \[ A^TAx_\star=A^Tb \] 이 나온다. 다만 \(A^TA\)를 직접 만들면 조건수가 대략 제곱되어 오차에 더 약해질 수 있다. 그래서 실전에서는 QR 분해가 더 사랑받는다. \(A=QR\)이면 \[ \|Ax-b\|_2=\|QRx-b\|_2=\|Rx-Q^Tb\|_2 \] 로 바뀌고, full column rank인 경우 \(Rx=Q^Tb\)라는 작은 위삼각 선형계를 후진대입으로 풀면 된다.

3.4 특잇값 분해

특잇값 분해, 즉 SVD는 행렬을 가장 솔직하게 해부하는 도구다. 임의의 \(A\in\mathbb{R}^{m\times n}\)에 대해 \[ A=U\Sigma V^T \] 로 쓸 수 있으며, \(U\)와 \(V\)는 직교 행렬이고 \(\Sigma\)는 대각선에 음이 아닌 수 \(\sigma_1\ge\sigma_2\ge\cdots\ge0\)를 가진다. 이 \(\sigma_i\)들이 특잇값이다. \(V^T\)가 입력 좌표를 돌리고, \(\Sigma\)가 축마다 늘이거나 줄이고, \(U\)가 출력 좌표를 다시 돌린다고 보면 된다.

SVD의 힘은 랭크, 영공간, 열공간, 근사까지 한꺼번에 보여 준다는 데 있다. 0이 아닌 특잇값의 개수는 \(\operatorname{rank}(A)\)이고, 작은 특잇값에 해당하는 방향은 \(A\)가 거의 눌러 버리는 입력 방향이다. 따라서 작은 \(\sigma_i\)는 계산의 불안정성을 알리는 조용한 경고등이다. 또한 rank-\(k\) 근사 \[ A_k=\sum_{i=1}^{k}\sigma_i u_i v_i^T \] 는 2-노름과 Frobenius 노름에서 가장 좋은 rank-\(k\) 근사다. 데이터 압축과 잡음 제거가 여기서 자연스럽게 나온다.

3.5 행렬의 의사역행렬

역행렬은 정사각이고 가역인 행렬에게만 허락된 호사다. 하지만 실제 문제의 행렬은 직사각형이거나 랭크가 부족한 경우가 많다. 이때 Moore-Penrose 의사역행렬 \(A^+\)가 등장한다. SVD가 \(A=U\Sigma V^T\)라면 \[ A^+=V\Sigma^+U^T \] 로 정의한다. 여기서 \(\Sigma^+\)는 0이 아닌 특잇값 \(\sigma_i\)를 \(1/\sigma_i\)로 뒤집고, 0은 그대로 0으로 둔 행렬이다.

의사역행렬은 여러 상황을 한 문장으로 묶어 준다. 최소제곱 해 중에서 노름이 가장 작은 해는 \[ x_\star=A^+b \] 이다. full column rank이면 \(A^+=(A^TA)^{-1}A^T\), full row rank이면 \(A^+=A^T(AA^T)^{-1}\)가 된다. 하지만 작은 특잇값을 무턱대고 뒤집으면 \(1/\sigma_i\)가 매우 커져 잡음까지 증폭한다. 그래서 절단 SVD나 Tikhonov 정규화처럼 작은 방향을 조심스럽게 다루는 방법이 필요하다.

3.6 행렬의 조건수

조건수는 문제가 얼마나 예민한지를 재는 온도계다. 2-노름에서 가역 정사각 행렬 \(A\)의 조건수는 \[ \kappa_2(A)=\|A\|_2\|A^{-1}\|_2=\frac{\sigma_{\max}}{\sigma_{\min}} \] 이다. 가장 많이 늘어나는 방향과 가장 적게 늘어나는 방향의 비율이라고 생각하면 된다. \(\kappa_2(A)\)가 1에 가까우면 행렬이 거의 등거리 변환처럼 행동하고, 매우 크면 어떤 방향은 크게 늘리고 어떤 방향은 거의 납작하게 눌러 버린다.

선형계 \(Ax=b\)에서 \(b\)에 작은 상대오차가 들어가면, 해의 상대오차는 대략 조건수만큼 증폭될 수 있다. \[ \frac{\|\delta x\|}{\|x\|}\lesssim \kappa(A)\frac{\|\delta b\|}{\|b\|} \] 라는 식은 “나쁜 알고리즘”이 아니라 “나쁜 문제”도 있음을 알려 준다. 알고리즘 안정성은 계산 과정의 문제이고, 조건수는 문제 자체의 민감도다. 둘을 섞어 생각하면 원인을 잘못 짚기 쉽다.

3.7 백슬래시 연산자

MATLAB과 Octave의 백슬래시 연산자 \(A\backslash b\)는 단순한 기호 하나처럼 보이지만, 안쪽에서는 꽤 많은 판단을 한다. 정사각이고 잘 정해진 선형계라면 보통 LU 분해 계열을 쓰고, overdetermined 문제라면 QR 기반 최소제곱을 사용하며, 랭크 부족이 의심되면 피벗팅이나 SVD 성격의 처리가 개입할 수 있다. 사용자는 \(x=A\backslash b\)라고 쓰지만, 시스템은 행렬의 모양과 구조를 보고 적절한 길을 고르는 셈이다.

중요한 교훈은 “역행렬을 만들지 말고 선형계를 풀라”는 것이다. \(x=\operatorname{inv}(A)b\)는 수학적으로는 그럴듯해도, 계산적으로는 더 느리고 더 불안정할 수 있다. \(A\backslash b\)는 분해를 이용해 필요한 해만 계산하므로 보통 더 정확하고 효율적이다. 희소 행렬에서는 이 차이가 더 커진다. 좋은 수치 코드는 멋진 공식보다 행렬의 구조를 존중하는 쪽에 가깝다.

4.1 왜 반복해법이 필요한가

직접해법은 문제 크기가 적당할 때 든든하다. 하지만 미분방정식을 격자로 쪼개거나 그래프 문제를 다루다 보면 미지수가 수십만, 수백만 개로 커지고 행렬은 대부분 0인 희소 행렬이 된다. 이때 LU나 QR 분해를 그대로 쓰면 원래 0이던 자리에 값이 생기는 fill-in 때문에 메모리와 시간이 빠르게 불어난다. 반복해법은 행렬을 완전히 분해하지 않고, 행렬-벡터 곱 \(Av\)를 반복하면서 해에 접근한다.

반복해법의 기본 감각은 “완벽한 한 방” 대신 “싼 한 걸음을 여러 번”이다. 초기값 \(x_0\)에서 시작해 잔차 \[ r_k=b-Ax_k \] 를 줄이는 방향으로 \(x_k\)를 갱신한다. 행렬이 희소하면 \(Av\)는 빠르게 계산할 수 있고, 큰 행렬을 저장하는 부담도 작다. 물론 반복 횟수가 너무 많아지면 장점이 사라지므로, 수렴 속도와 전처리가 핵심 주제가 된다.

4.2 고전적 분할 고정점 방법

고전적 반복법은 행렬을 \(A=M-N\)으로 나누고 \[ Mx_{k+1}=Nx_k+b \] 를 반복하는 방식으로 볼 수 있다. 이는 \[ x_{k+1}=M^{-1}Nx_k+M^{-1}b \] 라는 고정점 반복이다. Jacobi 방법은 \(M\)을 \(A\)의 대각성분 \(D\)로 두고, Gauss-Seidel 방법은 \(M=D+L\)처럼 아래삼각 부분까지 포함한다. 한 번의 반복이 싸고 구현이 단순하다는 점이 매력이다.

수렴 여부는 반복행렬 \(G=M^{-1}N\)의 스펙트럼 반지름 \(\rho(G)\)가 결정한다. \(\rho(G)<1\)이면 오차 \(e_k=x-x_k\)가 \[ e_{k+1}=Ge_k \] 를 따라 줄어든다. Jacobi와 Gauss-Seidel은 대각우세 행렬이나 특정 양의 정부호 문제에서 잘 작동하지만, 일반적으로는 느릴 수 있다. 그래도 이들은 현대 전처리와 다중격자 방법의 구성 요소로 계속 살아 있다. 오래된 도구가 꼭 낡은 도구는 아니다.

4.3 켤레기울기법

켤레기울기법(CG)은 \(A\)가 대칭 양의 정부호일 때 \(Ax=b\)를 푸는 대표적인 반복해법이다. 이 조건에서는 선형계를 푸는 일이 이차함수 \[ \phi(x)=\frac12x^TAx-b^Tx \] 를 최소화하는 일과 같다. 기울기는 \(\nabla\phi(x)=Ax-b=-r\)이므로, 잔차는 내려갈 방향을 알려 주는 신호다. 단순 최급강하법은 매번 가장 가파른 방향으로 내려가지만 지그재그가 심할 수 있다.

CG의 묘수는 탐색 방향 \(p_i\)들을 \(A\)-내적에서 서로 직교하게 만드는 것이다. \[ p_i^TAp_j=0\qquad (i\ne j) \] 이런 방향들을 켤레 방향이라고 부른다. 각 단계에서 \(x_{k+1}=x_k+\alpha_kp_k\)로 갱신하고, \(\alpha_k\)는 그 방향에서 \(\phi\)를 가장 작게 만드는 값으로 고른다. 정확한 산술에서는 최대 \(n\)번 만에 끝나지만, 실제 부동소수점 계산에서는 좋은 근사해를 빠르게 얻는 반복법으로 이해하는 편이 현실적이다.

4.4 크릴로프 공간

크릴로프 공간은 반복해법이 실제로 어디를 뒤지고 있는지 보여 주는 무대다. 초기 잔차 \(r_0=b-Ax_0\)에 대해 \(k\)차 크릴로프 공간은 \[ \mathcal{K}_k(A,r_0)=\operatorname{span}\{r_0,Ar_0,A^2r_0,\ldots,A^{k-1}r_0\} \] 이다. 행렬-벡터 곱을 반복하면 자연스럽게 이 벡터들이 생긴다. 따라서 많은 반복해법은 \(x_k\in x_0+\mathcal{K}_k(A,r_0)\) 중에서 어떤 기준으로 좋은 근사해를 고르는 방법이라고 볼 수 있다.

크릴로프 관점이 유용한 이유는 큰 행렬을 작게 다룰 수 있기 때문이다. 전체 공간에서 답을 찾는 대신, \(k\)차원 부분공간에 투영된 작은 문제를 푼다. \(k\)가 커질수록 후보 공간은 넓어지고, 행렬의 고유값 구조를 더 잘 반영한다. 특히 고유값이 몇 개의 덩어리로 모여 있으면 낮은 차수의 다항식으로 오차를 잘 줄일 수 있어 반복해법이 빠르게 수렴한다.

4.5 GMRES

GMRES는 일반적인 비대칭 행렬에도 쓸 수 있는 크릴로프 반복법이다. 이름 그대로 Generalized Minimal Residual Method, 즉 현재 크릴로프 공간 안에서 잔차 노름을 가장 작게 만드는 근사해를 고른다. \[ x_k=\arg\min_{x\in x_0+\mathcal{K}_k(A,r_0)}\|b-Ax\|_2 \] CG가 대칭 양의 정부호라는 좋은 지형에서 빠르게 달리는 방법이라면, GMRES는 더 울퉁불퉁한 지형에서도 “잔차를 실제로 줄였는가”를 기준으로 차분히 전진한다.

구현에서는 Arnoldi 과정을 사용해 크릴로프 공간의 직교기저 \(V_k\)를 만들고, \[ AV_k=V_{k+1}\bar H_k \] 라는 작은 Hessenberg 행렬 \(\bar H_k\) 문제로 바꾼다. 그러면 큰 문제의 잔차 최소화가 작은 최소제곱 문제로 줄어든다. 단점은 반복이 진행될수록 저장해야 할 기저 벡터가 늘어난다는 것이다. 그래서 실제로는 일정 횟수마다 다시 시작하는 restarted GMRES가 자주 쓰이지만, 재시작은 때때로 수렴 정보를 잃게 만든다.

4.6 CG의 크릴로프 공간 해석

CG도 크릴로프 방법이다. \(k\)번째 근사해는 \[ x_k\in x_0+\mathcal{K}_k(A,r_0) \] 에서 에너지 노름 오차 \(\|x-x_k\|_A=\sqrt{(x-x_k)^TA(x-x_k)}\)를 가장 작게 하는 벡터로 볼 수 있다. 대칭 양의 정부호 조건 덕분에 \(A\)-내적이 진짜 내적처럼 행동하고, 그래서 “직교”와 “최소화”가 아름답게 맞물린다.

이 관점에서는 CG의 수렴이 다항식 근사 문제로 바뀐다. 오차는 \[ e_k=q_k(A)e_0,\qquad q_k(0)=1 \] 꼴로 표현할 수 있고, 좋은 \(q_k\)가 \(A\)의 고유값들에서 작아지면 오차도 작아진다. 그래서 고유값이 모여 있거나 조건수 \(\kappa(A)\)가 작으면 CG가 빠르다. 대표적인 오차 경계는 \[ \frac{\|e_k\|_A}{\|e_0\|_A} \le 2\left(\frac{\sqrt{\kappa(A)}-1}{\sqrt{\kappa(A)}+1}\right)^k \] 이다. 조건수가 작을수록 괄호 안의 값이 작아지고, 반복은 산뜻해진다.

4.7 전처리

전처리는 같은 문제를 더 풀기 좋은 모양으로 바꾸는 기술이다. \(Ax=b\) 대신 \[ M^{-1}Ax=M^{-1}b \] 를 풀거나, 대칭성을 보존하기 위해 \(M\approx A\)인 양의 정부호 행렬을 이용해 적절히 변환한다. 좋은 전처리 행렬 \(M\)은 \(M^{-1}A\)의 조건수를 낮추거나 고유값을 모아 주어 반복 횟수를 줄인다. 동시에 \(Mz=v\)를 푸는 일이 충분히 싸야 한다. 비싼 전처리는 좋은 의도가 과한 계산비로 돌아온다.

예를 들어 Jacobi 전처리는 \(M=\operatorname{diag}(A)\)만 쓰므로 매우 싸지만 효과는 제한적일 수 있다. 불완전 Cholesky나 불완전 LU는 직접분해의 느낌을 일부 빌려 오되 fill-in을 제한한다. 문제 구조가 PDE에서 왔다면 다중격자 전처리가 강력할 수 있다. 전처리는 범용 마법 버튼이라기보다, 행렬이 어디서 왔는지 이해할수록 좋아지는 맞춤 운동화에 가깝다.

4.8 켤레기울기 알고리즘의 유도

CG 알고리즘은 몇 가지 최적화 조건을 재귀적으로 정리하면 나온다. 현재 방향 \(p_k\)에서 \(x_{k+1}=x_k+\alpha_kp_k\)라 두고 \(\phi(x)\)를 최소화하면 \[ \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k} \] 를 얻는다. 이어서 잔차는 \[ r_{k+1}=r_k-\alpha_kAp_k \] 로 갱신된다. 새 잔차는 지금까지의 크릴로프 공간에서 필요한 직교성을 만족하도록 만들어지며, 이것이 불필요한 되돌아감을 줄여 준다.

다음 탐색 방향은 새 잔차에 이전 방향을 조금 섞어 \[ p_{k+1}=r_{k+1}+\beta_kp_k,\qquad \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k} \] 로 둔다. 이렇게 하면 \(p_{k+1}^TAp_k=0\)이 유지된다. 전체 알고리즘은 행렬-벡터 곱 하나, 내적 몇 번, 벡터 갱신 몇 번으로 한 단계가 끝난다. 그래서 큰 희소 대칭 양의 정부호 문제에서 CG는 가볍고도 날카로운 기본기다.

5.1 큰 그림

정사각행렬 \(A\)에 대해 \(Ax=\lambda x\), \(x\neq 0\)을 만족하는 \(\lambda\)와 \(x\)를 각각 고유값과 고유벡터라 한다. 모든 고유값의 집합 \(\Lambda(A)\)는 스펙트럼이고, 수치 계산에서는 보통 "전체 스펙트럼"과 "몇 개의 관심 고유값" 문제가 갈린다. 작은 밀집 행렬이면 Schur 분해나 QR 알고리즘이 자연스럽고, 큰 희소 행렬이면 행렬-벡터 곱만 반복해서 쓰는 Krylov 방법이 주인공이 된다.

고유값 문제의 핵심 난점은 민감도다. 대칭 또는 에르미트 행렬은 직교 고유벡터 기저를 가져 비교적 온순하지만, 비정규 행렬은 고유값이 잔차보다 훨씬 크게 흔들릴 수 있다. 근사 고유쌍 \((\mu,x)\)의 잔차 \(r=Ax-\mu x\)가 작아도 안심은 금물이다. 특히 왼쪽 고유벡터 \(y\)와 오른쪽 고유벡터 \(x\)가 거의 직교하면 \(\kappa(\lambda)\approx \|x\|\|y\|/|y^*x|\)가 커져, 계산된 자릿수가 얌전히 남아 있지 않는다.

5.2 고립된 고유값 계산

하나의 두드러진 고유값을 잡을 때 가장 먼저 떠올릴 도구는 멱법이다. \(x_{k+1}=Ax_k/\|Ax_k\|\)를 반복하면 적절한 조건에서 절댓값이 가장 큰 고유값 방향으로 \(x_k\)가 기운다. 수렴 속도는 대략 \(|\lambda_2/\lambda_1|\)에 의해 정해지므로, 1등과 2등의 격차가 작으면 계산도 느긋해진다. 고유값 추정에는 Rayleigh 몫 \[ \rho(x)=\frac{x^*Ax}{x^*x} \] 이 자주 쓰이며, 에르미트 행렬에서는 방향 오차에 비해 고유값 오차가 한 차수 더 작아지는 반가운 성질이 있다.

원하는 고유값이 스펙트럼 한가운데 숨어 있으면 shift-and-invert가 계산의 망원경 역할을 한다. \((A-\sigma I)^{-1}\)의 고유값은 \(1/(\lambda-\sigma)\)이므로, \(\sigma\)에 가까운 고유값이 바깥쪽으로 튀어나온다. 실제 반복은 매번 \((A-\sigma I)y=x_k\)를 풀고 정규화하는 식이다. \(\sigma\)를 Rayleigh 몫으로 계속 갱신하면 Rayleigh quotient iteration이 되며, 에르미트 행렬 근방에서는 국소적으로 매우 빠르게, 흔히 3차 수렴을 보인다. 다만 선형시스템을 반복해서 풀어야 하므로, 분해 재사용과 조건수 점검이 계산비의 장부를 좌우한다.

5.3 스펙트럼 계산: 직교 반복과 QR 반복

여러 고유값을 한꺼번에 보려면 벡터 하나 대신 부분공간을 움직인다. 직교 반복은 \(AZ_k=Q_kR_k\)처럼 곱한 뒤 다시 직교화하여 \(Z_{k+1}=Q_k\)로 둔다. 지배적인 불변부분공간이 분리되어 있으면 이 부분공간이 안정적으로 드러난다. 여기서 직교화가 중요한 이유는 수치적 건강관리다. 거의 같은 방향의 벡터들을 그대로 두면 정보가 한쪽으로 무너지고, QR 분해는 그 무너짐을 매 반복마다 바로 세운다.

QR 반복은 이 생각을 행렬 전체에 적용한 형태다. \[ A_k=Q_kR_k,\qquad A_{k+1}=R_kQ_k=Q_k^*A_kQ_k. \] 즉 매 단계가 직교 닮음변환이므로 고유값은 보존된다. 충분히 좋은 조건에서는 \(A_k\)가 Schur 형태, 에르미트 행렬이면 대각 형태에 가까워진다. 실전에서는 먼저 \(A\)를 Hessenberg 형태로, 대칭이면 삼대각 형태로 줄여 둔다. 그래야 한 번의 QR 단계가 밀집 \(O(n^3)\) 작업이 아니라 Hessenberg의 \(O(n^2)\), 삼대각의 \(O(n)\) 작업으로 내려간다.

5.4 개선된 QR 알고리즘

순진한 QR 반복은 아름답지만, 기다림이 길 수 있다. 그래서 shift를 넣는다. \[ A_k-\mu_k I=Q_kR_k,\qquad A_{k+1}=R_kQ_k+\mu_k I. \] \(\mu_k\)가 어떤 고유값에 가까우면 마지막 부분대각 원소가 빠르게 작아져 deflation이 가능해진다. 대칭 삼대각 문제에서는 Wilkinson shift가 대표적이며, 맨 아래 \(2\times 2\) 블록의 고유값 중 \(a_{nn}\)에 가까운 값을 골라 수렴을 크게 가속한다.

구현의 묘미는 shift를 명시적으로 빼고 더하지 않는 "implicit" 방식에 있다. implicit Q 정리는 첫 열에서 시작된 작은 변화가 전체 QR 단계를 거의 결정한다는 사실을 보장하고, 알고리즘은 bulge chasing으로 Hessenberg 구조를 계속 유지한다. 비대칭 실수 행렬에서는 복소 켤레쌍을 다루기 위해 double shift가 쓰인다. 또한 \(|h_{i+1,i}|\)가 주변 대각 원소 크기와 기계 정밀도에 비해 충분히 작아지면 그 원소를 0으로 놓고 문제를 둘로 나눈다. 좋은 QR 코드는 수학 공식보다 이런 "언제 쪼갤 것인가"의 감각이 훨씬 많이 들어 있다.

5.5 확장 주제

고유값 문제는 \(Ax=\lambda Bx\) 꼴의 일반화 고유값 문제로 자주 확장된다. \(B\)가 양의 정부호이면 Cholesky 분해로 표준 문제에 가깝게 바꿀 수 있고, 일반적인 경우에는 QZ 알고리즘이 Schur 분해의 짝꿍처럼 등장한다. 구조가 있는 문제에서는 구조를 잃지 않는 변환이 중요하다. 대칭성, 대역성, 희소성은 계산비와 안정성을 함께 아껴 주는 자산이라 함부로 밀집 행렬로 만들면 아깝다.

큰 행렬에서는 Arnoldi와 Lanczos 방법이 중심이다. 이들은 Krylov 부분공간 \[ \mathcal{K}_m(A,v)=\operatorname{span}\{v,Av,\ldots,A^{m-1}v\} \] 위에 작은 투영 문제를 만들고, 그 고유값으로 원래 스펙트럼을 근사한다. 에르미트 문제의 Lanczos는 짧은 점화식 덕분에 빠르지만, 유한정밀도에서는 직교성이 서서히 새어나가 유령 고유값이 나타날 수 있다. 비정규 문제에서는 pseudospectrum도 함께 보는 습관이 좋다. 고유값 점들이 지도라면, pseudospectrum은 안개와 지형의 기울기까지 보여 주는 지도다.

6.1 들어가기

선형문제 \(Ax\approx b\)에서 \(A\)가 거의 랭크 부족이면, 어떤 방향의 입력은 출력에 거의 보이지 않는다. 그 방향을 되살리려면 작은 숫자로 나눠야 하므로 잡음도 함께 커진다. 조건수 \[ \kappa_2(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} \] 는 이 증폭의 대표적인 척도다. \(\sigma_{\min}\)이 작을수록 문제는 "정답은 있지만 만지면 번지는 잉크"처럼 행동한다.

중요한 구분은 불안정한 알고리즘과 ill-conditioned 문제다. 좋은 알고리즘은 뒤로 안정적일 수 있지만, 문제 자체가 민감하면 입력의 작은 오차가 해의 큰 오차로 바뀌는 일은 피할 수 없다. 그래서 정칙화는 단순히 계산을 편하게 만드는 장치가 아니라, "우리가 믿을 수 있는 정보만 어느 정도까지 사용할 것인가"를 정하는 모델링 결정이다.

6.2 SVD와 절단 SVD

SVD는 \(A=U\Sigma V^*\)로 쓰며, \(v_i\) 방향의 입력이 \(u_i\) 방향의 출력으로 \(\sigma_i\)만큼 확대된다고 해석한다. 특이값은 보통 \(\sigma_1\ge \sigma_2\ge \cdots\ge 0\)로 정렬한다. Eckart-Young 정리에 따르면 \[ A_k=\sum_{i=1}^k \sigma_i u_i v_i^* \] 는 2-노름과 Frobenius 노름에서 \(A\)에 가장 가까운 랭크 \(k\) 행렬이다. 즉 저랭크 근사는 "중요한 축부터 남기는" 최적의 압축이다.

절단 SVD는 작은 특이값 방향을 버린다. 이것은 정보 손실이지만, 동시에 잡음 증폭을 막는 방어선이다. 수치적 랭크는 완전한 0을 세는 일이 아니라, 데이터 오차와 기계 정밀도를 고려해 "더 이상 믿기 어려운 특이값"의 경계를 정하는 일이다. 그래서 \(\sigma_i/\sigma_1\) 그래프의 급격한 꺾임, 잔차 수준, 실험 잡음의 크기가 모두 \(k\) 선택에 관여한다.

6.3 정칙화된 최소제곱

가장 표준적인 정칙화는 Tikhonov 또는 ridge 형태다. \[ \min_x \|Ax-b\|_2^2+\lambda\|Lx\|_2^2. \] 여기서 \(\lambda>0\)는 데이터 적합과 해의 단순함 사이의 손잡이고, \(L\)은 무엇을 벌점으로 볼지 정한다. \(L=I\)이면 큰 노름의 해를 억제하고, 차분 행렬을 쓰면 거친 해를 억제한다. 정규방정식은 \[ (A^*A+\lambda L^*L)x=A^*b \] 이지만, 실제 계산에서는 조건수 악화를 피하려고 QR, SVD, 또는 적절한 반복법을 선호한다.

\(L=I\)일 때 SVD로 보면 정칙화의 의미가 아주 선명하다. 해 성분은 \[ x_\lambda=\sum_i \frac{\sigma_i}{\sigma_i^2+\lambda}(u_i^*b)v_i \] 로 표현되며, 작은 \(\sigma_i\) 방향은 \(1/\sigma_i\)로 폭주하는 대신 부드럽게 눌린다. \(\lambda\) 선택은 쉬운 문제가 아니다. 잡음 크기를 안다면 discrepancy principle을, 모른다면 L-curve, 교차검증, 일반화 교차검증 같은 기준을 쓴다. 핵심은 \(\lambda\)가 수학 상수가 아니라 데이터와 믿음의 계약서라는 점이다.

6.4 절단 SVD를 이용한 정칙화

최소제곱 해를 SVD로 쓰면 \[ x_{\mathrm{ls}}=\sum_{\sigma_i>0}\frac{u_i^*b}{\sigma_i}v_i \] 이다. 작은 \(\sigma_i\)가 있으면 \(u_i^*b\)에 섞인 잡음까지 크게 나뉜다. 절단 SVD 정칙화는 \[ x_k=\sum_{i=1}^k\frac{u_i^*b}{\sigma_i}v_i \] 만 남긴다. Tikhonov가 작은 성분을 서서히 낮추는 조광기라면, 절단 SVD는 \(k\) 이후를 꺼 버리는 스위치에 가깝다.

\(k\)는 Picard 조건을 보며 고르는 경우가 많다. 이상적으로는 \(|u_i^*b|\)가 \(\sigma_i\)보다 충분히 빨리 줄어들어야 안정적인 해가 나오지만, 실제 데이터에서는 어느 순간부터 \(|u_i^*b|\)가 잡음 바닥에 걸려 더 내려가지 않는다. 그 이후의 항은 정보를 복원하기보다 잡음을 꾸미는 데 가깝다. 따라서 절단 지점은 잔차가 허용 가능한 수준이면서 해가 불필요하게 요동치지 않는 타협점으로 잡는다.

6.5 희소성을 촉진하는 정칙화

어떤 문제에서는 해가 작기만 한 것이 아니라 대부분의 성분이 0에 가깝다고 믿는다. 이때는 \(\ell_2\) 벌점보다 \(\ell_1\) 벌점이 더 어울린다. \[ \min_x \frac12\|Ax-b\|_2^2+\lambda\|x\|_1 \] 는 LASSO 형태이고, 잡음 없는 이상화에서는 \(\min\|x\|_1\) subject to \(Ax=b\)가 basis pursuit로 불린다. \(\ell_1\) 노름은 마름모 모양의 기하 때문에 좌표축 위의 해, 즉 많은 0을 가진 해를 자연스럽게 선호한다.

알고리즘적으로는 근접연산자가 핵심이다. \(A\)가 직교에 가까운 단순한 경우에는 성분별 soft-thresholding \[ S_\tau(z)_i=\operatorname{sign}(z_i)\max(|z_i|-\tau,0) \] 이 나타난다. 일반 행렬에서는 ISTA, FISTA, 좌표하강법, ADMM 같은 방법이 쓰인다. 다만 희소성은 마법의 필터가 아니라 사전지식이다. 실제 해가 희소하지 않거나 \(A\)의 열들이 심하게 닮아 있으면, \(\ell_1\) 정칙화도 그럴듯한 이야기만 만들고 진실과는 멀어질 수 있다.

7.1 기본 정의와 사실 요약

벡터 노름은 크기를 재는 함수이고, 행렬 노름은 선형변환이 벡터를 얼마나 키울 수 있는지 재는 함수다. 유도 2-노름은 \(\|A\|_2=\sigma_1(A)\)이고, Frobenius 노름은 모든 원소 제곱합의 제곱근이다. 조건수는 상대 입력 오차가 상대 출력 또는 해 오차로 얼마나 증폭될 수 있는지 말해 준다. 가역 행렬에 대해 \(\kappa(A)=\|A\|\|A^{-1}\|\)이며, 2-노름에서는 \(\kappa_2(A)=\sigma_1/\sigma_n\)이다.

직교 또는 유니터리 행렬 \(Q\)는 \(Q^*Q=I\)를 만족하고 2-노름을 보존한다. 그래서 수치선형대수는 가능하면 직교변환을 좋아한다. 랭크는 독립적인 열의 수, 영공간은 \(Ax=0\)의 해집합, 치역은 \(Ax\)가 도달할 수 있는 공간이다. 양의 정부호 행렬은 \(x^*Ax>0\)을 만족하며 Cholesky 분해와 에너지 노름의 기반이 된다.

7.2 행렬 분해 한눈에 보기

LU 분해는 \(PA=LU\) 형태로 선형시스템을 빠르게 풀게 해 주며, pivoting이 안정성의 열쇠다. Cholesky 분해 \(A=R^*R\)은 에르미트 양의 정부호 행렬에서 가장 효율적인 직접해법이다. QR 분해 \(A=QR\)은 최소제곱과 직교화의 표준 도구이고, Householder QR은 안정성이 좋아 밀집 문제에서 믿음직하다.

SVD \(A=U\Sigma V^*\)는 랭크, 조건수, 최소제곱, 저랭크 근사를 한 번에 설명한다. 고유값 분해는 행렬이 대각화 가능할 때 \(A=X\Lambda X^{-1}\)로 쓰지만, 수치적으로는 Schur 분해 \(A=QTQ^*\)가 더 기본적이다. Hessenberg와 삼대각 축소는 QR 고유값 알고리즘의 전처리이며, Krylov 분해는 큰 희소 행렬을 작은 투영 문제로 바꾸는 현대적 작업대다.

7.3 기본 계산 과정 한눈에 보기

선형시스템은 대개 \(A^{-1}\)을 만들지 않고 \(Ax=b\)를 직접 푼다. 잔차 \(r=b-A\hat{x}\)가 작다는 것은 원래 문제를 조금 바꾼 문제의 정확한 해에 가깝다는 뜻일 수 있지만, 해 오차가 작다는 보장은 조건수와 함께 봐야 한다. 반복개선은 낮은 정밀도 또는 이미 계산된 분해를 활용해 잔차 방정식을 다시 풀며 해를 다듬는 방법이다.

최소제곱은 \(Ax\approx b\)에서 잔차 노름을 최소화하는 문제이고, QR 또는 SVD가 안정적인 해법이다. 반복법에서는 정지 기준을 \(\|r_k\|/\|b\|\), 해 변화량, 또는 backward error로 둔다. CG는 대칭 양의 정부호 문제, GMRES는 일반 비대칭 문제, LSQR은 큰 희소 최소제곱에 잘 맞는다. 전처리는 스펙트럼을 보기 좋게 모아 반복 횟수를 줄이는, 계산 전의 정리정돈이다.

7.4 수치선형대수에서 자주 쓰는 Matlab 연산자

Matlab에서는 선형시스템과 최소제곱 모두 A\b가 기본 출발점이다. 가역 행렬이라고 해서 inv(A)*b를 쓰는 습관은 피하자. 분해 함수로는 lu, chol, qr, svd, eig가 자주 쓰이고, 큰 희소 고유값 문제에는 eigs, 큰 최소제곱에는 lsqr, SPD 반복해법에는 pcg가 유용하다.

기본 점검 도구로 norm(A), cond(A), rank(A), rcond(A)를 기억해 두면 좋다. *는 행렬곱, .*는 성분별 곱이고, '는 복소 켤레전치, .'는 단순 전치다. 희소 행렬은 sparse, spdiags로 만들며, 큰 문제에서 밀집으로 바뀌는 순간 메모리와 시간이 갑자기 무거워질 수 있으니 중간 결과의 구조를 자주 확인하자.