30장. 수치선형대수

컴퓨터는 실수를 유한한 자릿수로만 기억하므로 계산마다 작은 오차가 생깁니다. 이 장에서는 그 오차가 언제 크게 불어나는지(조건수), 어떤 알고리즘이 오차에 강한지(후방 안정성), 큰 행렬의 고윳값을 실제로 어떻게 구하는지(거듭제곱법, QR 반복)를 다룹니다. 수치 계산을 하는 모든 논문의 기본 상식입니다.

30.1 컴퓨터의 반올림

질문. 지금까지의 알고리즘은 모두 정확한 산술을 가정했습니다. 컴퓨터는 수를 유효숫자 16자리 정도로 반올림해서 저장합니다. 수학적으로 옳은 알고리즘이 반올림 때문에 엉뚱한 답을 낼 수 있을까요? 그렇다면 어떤 문제가 “위험”하고, 어떤 알고리즘이 “안전”할까요?

보통 쓰는 배정밀도 부동소수점 수는 $\pm(1.b_1b_2 \ldots b_{52})_2 \times 2^e$ 꼴입니다. 유효숫자가 이진법 53자리이므로, 실수 $a$를 저장한 값 $\mathrm{fl}(a)$와 사칙연산의 결과는

을 만족합니다. 연산 한 번의 상대 오차는 작습니다. 문제는 오차가 쌓이고 증폭되는 것입니다.

예제 30.1. $1 + 10^{-17}$은 fl에서 1이 되므로 $(1 + 10^{-17}) - 1$은 0이 됩니다. 정답 $10^{-17}$의 상대 오차는 100%입니다. 비슷한 두 수를 빼면 앞자리가 지워지고 반올림 오차만 남습니다. 이것을 상쇄(cancellation)라 합니다.

이 장은 두 질문을 구별합니다. 문제가 입력의 작은 변화에 얼마나 민감한가(조건수), 그리고 알고리즘이 문제가 원래 가진 민감도보다 오차를 더 키우는가(안정성). 둘을 재려면 먼저 벡터와 행렬의 “크기”가 필요합니다.

30.2 벡터 노름과 행렬 노름

정의 30.2 (노름). $\mathbb{F}^n$ 위의 함수 $\lVert \cdot \rVert$가 다음을 만족하면 노름(norm)이라 합니다.

1. $\lVert \mathbf{x} \rVert \ge 0$이고, $\lVert \mathbf{x} \rVert = 0 \iff \mathbf{x} = \mathbf{0}$.
2. $\lVert c\mathbf{x} \rVert = \lvert c \rvert\lVert \mathbf{x} \rVert$.
3. $\lVert \mathbf{x} + \mathbf{y} \rVert \le \lVert \mathbf{x} \rVert + \lVert \mathbf{y} \rVert$.

자주 쓰는 노름은 $\lVert \mathbf{x} \rVert_1 = \sum \lvert x_i \rvert$, $\lVert \mathbf{x} \rVert_2 = \sqrt{\sum \lvert x_i \rvert^2}$, $\lVert \mathbf{x} \rVert_\infty = \max \lvert x_i \rvert$입니다.

$\lVert \cdot \rVert_2$는 내적에서 온 노름이고, 나머지 둘은 내적에서 오지 않습니다(평행사변형 법칙이 깨진다, 문제 30.1). 유한차원에서는 모든 노름이 상수배 이내로 비슷합니다. 예를 들어 $\lVert \mathbf{x} \rVert_\infty \le \lVert \mathbf{x} \rVert_2 \le \sqrt{n}\lVert \mathbf{x} \rVert_\infty$.

그림 30.1. $\mathbb{R}^2$에서 세 노름의 단위공. 노름이 다르면 “같은 거리”의 모양이 다릅니다.

정의 30.3 (연산자 노름). 벡터 노름 $\lVert \cdot \rVert$에 대해 $m \times n$ 행렬 $A$의 연산자 노름(operator norm)은

입니다. $A$가 벡터를 최대 몇 배로 늘이는가를 잽니다.

정리 30.4 (연산자 노름의 성질).

1. $\lVert \cdot \rVert$는 $\mathbb{F}^{m \times n}$ 위의 노름이고, $\lVert A\mathbf{x} \rVert \le \lVert A \rVert\lVert \mathbf{x} \rVert$, $\lVert AB \rVert \le \lVert A \rVert\lVert B \rVert$.
2. $\lVert A \rVert_2 = \sigma_1$ (가장 큰 특잇값).
3. $\lVert A \rVert_1 = \max_j \sum_i \lvert a_{ij} \rvert$ (열의 절댓값 합의 최댓값), $\lVert A \rVert_\infty = \max_i \sum_j \lvert a_{ij} \rvert$ (행의 절댓값 합의 최댓값).

증명. (1) $\lVert A\mathbf{x} \rVert \le \lVert A \rVert\lVert \mathbf{x} \rVert$는 정의 그대로이고, $\lVert AB\mathbf{x} \rVert \le \lVert A \rVert\lVert B\mathbf{x} \rVert \le \lVert A \rVert\lVert B \rVert\lVert \mathbf{x} \rVert$. 노름의 세 성질은 벡터 노름에서 바로 옵니다.

(2) SVD $A = U\Sigma V^*$에서 $\mathbf{x} = \sum c_i\mathbf{v}_i$이면 $\lVert A\mathbf{x} \rVert_2^2 = \sum \sigma_i^2\lvert c_i \rvert^2 \le \sigma_1^2\sum \lvert c_i \rvert^2 = \sigma_1^2\lVert \mathbf{x} \rVert_2^2$. 등호는 $\mathbf{x} = \mathbf{v}_1$.

(3) $\lVert \cdot \rVert_\infty$만 보입시다. $\lvert (A\mathbf{x})_i \rvert \le \sum_j \lvert a_{ij} \rvert\lvert x_j \rvert \le \big(\sum_j \lvert a_{ij} \rvert\big)\lVert \mathbf{x} \rVert_\infty$. 등호는 최댓값을 주는 행 $i$에서 $x_j = \operatorname{sgn} a_{ij}$로 잡으면 됩니다. $\lVert \cdot \rVert_1$은 문제 30.3. ■

연산자 노름이 아닌 행렬 노름으로 프로베니우스 노름(Frobenius norm) $\lVert A \rVert_F = \sqrt{\sum_{i,j} \lvert a_{ij} \rvert^2}$도 자주 씁니다. 행렬을 긴 벡터로 보고 잰 길이이고, $\lVert A \rVert_F^2 = \operatorname{tr}(A^*A) = \sigma_1^2 + \cdots + \sigma_r^2$입니다.

▶ 문제 30.1–30.3

30.3 에카르트–영 정리의 증명

18장에서 미룬 증명을 합시다. $A = \sum_{i=1}^r \sigma_i\mathbf{u}_i\mathbf{v}_i^*$이고 $A_k = \sum_{i=1}^k \sigma_i\mathbf{u}_i\mathbf{v}_i^*$입니다.

정리 30.5 (에카르트–영). 랭크가 $k$ 이하인 모든 $B$에 대해 $\lVert A - B \rVert_2 \ge \sigma_{k+1} = \lVert A - A_k \rVert_2$입니다.

증명. $A - A_k = \sum_{i>k} \sigma_i\mathbf{u}_i\mathbf{v}_i^*$은 특잇값이 $\sigma_{k+1}, \sigma_{k+2}, \ldots$인 SVD를 가지므로 $\lVert A - A_k \rVert_2 = \sigma_{k+1}$입니다.

$\operatorname{rank} B \le k$이면 $\dim N(B) \ge n - k$입니다. $W = \operatorname{span}(\mathbf{v}_1, \ldots, \mathbf{v}_{k+1})$은 $k + 1$차원이므로 $\dim N(B) + \dim W \ge n + 1 > n$이고, 두 부분공간은 0이 아닌 벡터를 공유합니다(정리 21.17). 그런 단위벡터 $\mathbf{x} = \sum_{i \le k+1} c_i\mathbf{v}_i$에 대해

따라서 $\lVert A - B \rVert_2 \ge \sigma_{k+1}$. ■

$k = n - 1$로 두면 따름정리가 나옵니다. 가역행렬 $A$에서 가장 가까운 특이 행렬까지의 거리는 $\sigma_n$입니다. 28장에서 “가역성에서 얼마나 먼지는 $\sigma_n$이 잽니다”고 한 것이 이것입니다.

▶ 문제 30.4

30.4 조건수

정의 30.6 (조건수). 가역행렬 $A$의 조건수(condition number)는 $\kappa(A) = \lVert A \rVert\lVert A^{-1} \rVert$입니다. $\lVert \cdot \rVert_2$를 쓰면 $\kappa_2(A) = \sigma_1/\sigma_n$입니다.

$\kappa(A) \ge \lVert AA^{-1} \rVert = 1$이고, 직교행렬은 $\kappa_2 = 1$입니다.

정리 30.7 (조건수와 오차). $A\mathbf{x} = \mathbf{b}$이고 $A(\mathbf{x} + \delta\mathbf{x}) = \mathbf{b} + \delta\mathbf{b}$이면

증명. $\delta\mathbf{x} = A^{-1}\delta\mathbf{b}$이므로 $\lVert \delta\mathbf{x} \rVert \le \lVert A^{-1} \rVert\lVert \delta\mathbf{b} \rVert$. 또 $\lVert \mathbf{b} \rVert \le \lVert A \rVert\lVert \mathbf{x} \rVert$이므로 $1/\lVert \mathbf{x} \rVert \le \lVert A \rVert/\lVert \mathbf{b} \rVert$. 두 부등식을 곱합니다. ■

입력의 상대 오차가 최대 $\kappa$배로 커집니다. 대략, $\kappa \approx 10^p$이면 답의 유효숫자 $p$자리를 잃습니다. 이것은 문제의 성질입니다. 어떤 알고리즘을 써도 피할 수 없습니다.

예제 30.8. $A = \begin{bmatrix} 1 & 1 \\ 1 & 1.0001 \end{bmatrix}$, $\mathbf{b} = (2, 2.0001)$이면 $\mathbf{x} = (1, 1)$. $\mathbf{b}$를 $(2, 2.0002)$로 아주 조금 바꾸면 $\mathbf{x} = (0, 2)$가 됩니다. $A^{-1} = \begin{bmatrix} 10001 & -10000 \\ -10000 & 10000 \end{bmatrix}$이므로 $\kappa_\infty(A) = 2.0001 \times 20001 \approx 4 \times 10^4$. 실제로 $\mathbf{b}$의 상대 변화 $\approx 5 \times 10^{-5}$가 $\mathbf{x}$의 상대 변화 1이 되었습니다.

그림 30.2. 거의 평행한 두 직선의 교점. 한 직선을 조금만 옮겨도 교점이 멀리 움직입니다. $\kappa$가 큰 $2 \times 2$ 연립방정식의 모습입니다.

▶ 문제 30.5–30.7

30.5 안정성과 피벗팅

반올림이 있으면 알고리즘은 정확한 답 $\mathbf{x}$ 대신 $\hat{\mathbf{x}}$를 냅니다. 좋은 알고리즘의 기준은 다음과 같습니다.

정의 30.9 (후방 안정). $A\mathbf{x} = \mathbf{b}$를 푸는 알고리즘의 출력 $\hat{\mathbf{x}}$가 어떤 $\delta A$에 대해 $(A + \delta A)\hat{\mathbf{x}} = \mathbf{b}$를 정확히 만족하고 $\lVert \delta A \rVert/\lVert A \rVert$가 $\epsilon_{\mathrm{mach}}$의 적당한 배수 이하이면, 알고리즘이 후방 안정(backward stable)이라 합니다.

“답은 틀렸지만, 거의 같은 문제의 정확한 답입니다.” 입력 자체가 측정이나 저장 과정에서 $\epsilon_{\mathrm{mach}}$ 정도의 오차를 이미 가지므로 이보다 잘할 수는 없습니다. 후방 안정인 알고리즘의 전방 오차 $\lVert \hat{\mathbf{x}} - \mathbf{x} \rVert/\lVert \mathbf{x} \rVert$는 대략 $\kappa(A)\,\epsilon_{\mathrm{mach}}$입니다. 조건수가 문제의 몫, $\epsilon_{\mathrm{mach}}$의 배수가 알고리즘의 몫입니다.

예제 30.10. $\epsilon = 10^{-20}$일 때

피벗 $\epsilon$으로 소거하면 승수가 $10^{20}$이고, 2행은 $(1 - 10^{20})x_2 = 2 - 10^{20}$이 됩니다. 반올림하면 양변이 $-10^{20}$이므로 $x_2 = 1$, 그다음 $x_1 = (1 - x_2)/\epsilon = 0$. 완전히 틀렸습니다. 행을 바꿔 피벗 1로 소거하면 승수가 $\epsilon$이고 $(1 - \epsilon)x_2 = 1 - 2\epsilon$에서 $x_2 = 1$, $x_1 = 2 - x_2 = 1$. 정확합니다.

이 행렬의 조건수는 $\kappa_\infty \approx 4$로 작습니다. 문제는 쉬웠는데 알고리즘이 망쳤습니다. 작은 피벗으로 나누면 큰 승수가 생기고, 큰 수에 묻힌 정보가 반올림으로 사라집니다. 그래서 실제 소거는 각 열에서 절댓값이 가장 큰 성분을 피벗으로 고릅니다(부분 피벗팅(partial pivoting)). 승수가 모두 $\lvert \ell_{ij} \rvert \le 1$이 되고, 9장의 $PA = LU$가 바로 이 알고리즘입니다. 부분 피벗팅을 한 소거는 이론적으로 최악의 예가 있지만 실제로는 언제나 후방 안정처럼 동작합니다.

또 하나의 교훈: $A^{-1}$을 구해서 $A^{-1}\mathbf{b}$를 계산하지 말라. 더 비싸고 덜 정확합니다. 최소제곱에서 $A^TA$를 만들지 말라는 14장의 조언도 같은 이유입니다. $\kappa(A^TA) = \kappa(A)^2$이기 때문입니다(문제 30.8).

▶ 문제 30.8–30.9

30.6 하우스홀더 QR

직교변환은 $\lVert Q\mathbf{x} \rVert_2 = \lVert \mathbf{x} \rVert_2$이므로 오차를 키우지 않습니다. 그래서 수치 계산은 직교변환을 좋아합니다. 14장의 그람–슈미트는 반올림이 쌓이면 $\mathbf{q}_i$들의 직교성을 잃습니다. 실제 프로그램은 하우스홀더 반사로 QR을 만듭니다.

정리 30.11 (하우스홀더 반사로 0 만들기). $\mathbf{a} \in \mathbb{R}^m$, $\mathbf{a} \ne \mathbf{0}$, $s = \pm\lVert \mathbf{a} \rVert_2$ ($a_1$과 같은 부호)이고 $\mathbf{v} = \mathbf{a} + s\mathbf{e}_1$, $H = I - 2\dfrac{\mathbf{v}\mathbf{v}^T}{\mathbf{v}^T\mathbf{v}}$이면

증명. $\mathbf{v}^T\mathbf{a} = \lVert \mathbf{a} \rVert^2 + sa_1$이고 $\mathbf{v}^T\mathbf{v} = \lVert \mathbf{a} \rVert^2 + 2sa_1 + s^2 = 2(\lVert \mathbf{a} \rVert^2 + sa_1)$이므로 $2\mathbf{v}^T\mathbf{a}/\mathbf{v}^T\mathbf{v} = 1$. 따라서 $H\mathbf{a} = \mathbf{a} - \mathbf{v} = -s\mathbf{e}_1$. ■

부호를 $a_1$과 같게 고르는 것은 $\mathbf{v}$의 첫 성분 $a_1 + s$에서 상쇄를 피하기 위해서입니다.

예제 30.12. $\mathbf{a} = (3, 4)$, $s = 5$, $\mathbf{v} = (8, 4)$. $H\mathbf{a} = \mathbf{a} - \mathbf{v} = (-5, 0)$.

$A$의 첫 열에 이것을 쓰면 $H_1A$의 첫 열은 $(-s, 0, \ldots, 0)$입니다. 다음에는 $H_1A$의 둘째 열의 아래쪽 $m - 1$개 성분에 같은 일을 하는 $H_2$(왼쪽 위가 1인 블록)를 곱합니다. $n$번 하면

각 단계가 직교변환이므로 후방 안정입니다.

▶ 문제 30.10

30.7 고윳값 계산

16장에서는 $\det(A - \lambda I) = 0$을 풀었습니다. 이 방법은 실제로는 쓰지 않습니다. 다항식의 근은 계수에 극도로 민감할 수 있기 때문입니다. 예를 들어 근이 $1, 2, \ldots, 20$인 다항식의 $x^{19}$ 계수를 $2^{-23}$만큼만 바꿔도 근 몇 개가 복소수로 날아갑니다(윌킨슨). 반대로 29장에서 본 것처럼, 다항식의 근을 구할 때 동반행렬의 고윳값을 계산합니다.

30.7.1 거듭제곱법

정리 30.13 (거듭제곱법). $A$가 대각화 가능하고 고윳값이 $\lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert \ge \cdots \ge \lvert \lambda_n \rvert$, 고유벡터가 $\mathbf{q}_1, \ldots, \mathbf{q}_n$이라 합시다. $\mathbf{x}_0 = \sum c_i\mathbf{q}_i$에서 $c_1 \ne 0$이면 $A^k\mathbf{x}_0$의 방향은 $\mathbf{q}_1$의 방향으로 수렴하고, 오차는 $\lvert \lambda_2/\lambda_1 \rvert^k$에 비례해 줄어듭니다.

증명. $A^k\mathbf{x}_0 = \lambda_1^k\big(c_1\mathbf{q}_1 + \sum_{i \ge 2} c_i(\lambda_i/\lambda_1)^k\mathbf{q}_i\big)$이고 괄호 안의 둘째 항은 $\lvert \lambda_2/\lambda_1 \rvert^k$에 비례해 0으로 갑니다. ■

7장에서 관찰한 “가장 큰 고윳값이 장기적인 모습을 결정합니다”의 증명입니다. 실제로는 넘침을 막으려고 매번 정규화하고, 고윳값은 레일리 몫 $\mathbf{x}^TA\mathbf{x}/\mathbf{x}^T\mathbf{x}$로 읽습니다.

예제 30.14. $A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$, $\mathbf{x}_0 = (1, 0)$: $(2, 1), (5, 4), (14, 13), (41, 40), \ldots$. 두 성분의 비가 1로 가므로 방향은 $(1, 1)$, 레일리 몫은 3으로 갑니다. $\lambda_2/\lambda_1 = 1/3$이므로 한 번에 오차가 약 1/3이 됩니다.

$(A - \mu I)^{-1}$에 거듭제곱법을 쓰면 $\mu$에 가장 가까운 고윳값을 찾습니다(역반복법(inverse iteration)). $\mu$가 고윳값에 가까울수록 빨리 수렴합니다.

30.7.2 QR 알고리즘

모든 고윳값을 한꺼번에 구하는 표준 방법은 다음과 같습니다. $A_0 = A$에서 시작해

$A_{k+1} = Q_k^T(Q_kR_k)Q_k = Q_k^TA_kQ_k$이므로 모든 $A_k$는 $A$와 닮았고 고윳값이 같습니다.

정리 30.15 (QR 알고리즘과 거듭제곱). $\bar{Q}_k = Q_0Q_1 \cdots Q_{k-1}$, $\bar{R}_k = R_{k-1} \cdots R_1R_0$이라 하면 $A^k = \bar{Q}_k\bar{R}_k$입니다. 즉 $\bar{Q}_k$는 $A^k$의 QR 분해의 $Q$입니다.

증명은 귀납법입니다(문제 30.12). $A^k$의 첫 열은 $A^k\mathbf{e}_1$, 즉 거듭제곱법입니다. 처음 $j$개 열의 span은 $A^k$를 $j$차원 부분공간에 거듭 건 것이므로, 고윳값의 크기가 서로 다르면 처음 $j$개 고유벡터의 span으로 수렴합니다. 그 결과 $A_k = \bar{Q}_k^TA\bar{Q}_k$는 위삼각행렬(슈어 형식, 정리 25.12)로 수렴하고 대각에 고윳값이 나타납니다. QR 알고리즘은 모든 차원에서 동시에 돌아가는 거듭제곱법입니다. 실제 프로그램은 먼저 헤센베르크 꼴로 줄이고, 이동(shift)을 써서 수렴을 크게 빠르게 합니다.

▶ 문제 30.11–30.12

30.8 반복법

$n$이 수백만이고 $A$의 성분이 대부분 0인 연립방정식(편미분방정식의 이산화, 네트워크)에서는 소거가 0을 채워 넣어 메모리가 모자랍니다. 이때는 $A$를 곱하기만 하는 반복법을 씁니다.

$A = D + L + U$ (대각, 순아래, 순위)로 나누면 $A\mathbf{x} = \mathbf{b}$는 $D\mathbf{x} = \mathbf{b} - (L + U)\mathbf{x}$입니다. 야코비 반복(Jacobi iteration)은

오차 $\mathbf{e}_k = \mathbf{x}_k - \mathbf{x}$는 $\mathbf{e}_{k+1} = M\mathbf{e}_k$, $M = -D^{-1}(L + U)$를 만족합니다. 따라서 수렴 여부는 $M^k \to O$인지에 달렸습니다.

정의 30.16 (스펙트럼 반지름). $\rho(M) = \max\{ \lvert \lambda \rvert : \lambda\text{는 } M\text{의 (복소) 고윳값} \}$을 스펙트럼 반지름(spectral radius)이라 합니다.

정리 30.17 (거듭제곱이 0으로 가는 조건). $M^k \to O \iff \rho(M) < 1$.

증명. ($\Rightarrow$) $M\mathbf{q} = \lambda\mathbf{q}$이면 $M^k\mathbf{q} = \lambda^k\mathbf{q}$이므로 $\lvert \lambda \rvert < 1$이어야 합니다. ($\Leftarrow$) 조르당 형식 $M = PJP^{-1}$에서 $M^k = PJ^kP^{-1}$입니다. 크기 $s$인 블록 $J_s(\lambda)^k$의 성분은 $\binom{k}{j}\lambda^{k-j}$ ($j < s$) 꼴이고(27.7절), $\big\lvert \binom{k}{j}\lambda^{k-j} \big\rvert \le k^j\lvert \lambda \rvert^{k-j} \to 0$ ($\lvert \lambda \rvert < 1$이면 지수함수가 다항식을 이깁니다). ■

대각화 가능하면 $\lambda^k \to 0$만 보면 되지만, 그렇지 않으면 $k\lambda^k$ 같은 항을 다뤄야 합니다. 조르당 형식이 실용적인 정리에 쓰이는 대표적인 예입니다. 수렴 속도는 대략 $\rho(M)^k$입니다.

예제 30.18. $\begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix}\mathbf{x} = \begin{bmatrix} 5 \\ 4 \end{bmatrix}$, 해 $(1, 1)$. $\mathbf{x}_0 = \mathbf{0}$에서 야코비 반복은

$M = \begin{bmatrix} 0 & -1/4 \\ -1/3 & 0 \end{bmatrix}$의 고윳값은 $\pm 1/\sqrt{12}$이므로 $\rho \approx 0.29$, 한 번에 오차가 약 0.29배가 됩니다.

각 행에서 대각성분의 절댓값이 나머지의 절댓값 합보다 크면(대각 우세(diagonally dominant)) $\lVert M \rVert_\infty < 1$이므로 $\rho(M) \le \lVert M \rVert_\infty < 1$이고 야코비 반복은 수렴합니다(문제 30.14). 새로 계산한 성분을 바로 쓰는 가우스–자이델(Gauss–Seidel) 반복, 그리고 대칭 양정치 행렬에 쓰는 켤레기울기법(conjugate gradient)이 더 빠른 방법들입니다.

▶ 문제 30.13–30.15

쓰이는 곳. 논문의 실험 결과가 믿을 만한지 판단할 때 조건수와 수치 안정성을 봅니다. 대규모 머신러닝은 부동소수점 정밀도(fp16, bf16)를 낮춰 계산하므로 오차 감각이 특히 중요합니다.

이 장의 요약

• 부동소수점 연산은 상대 오차 $\epsilon_{\mathrm{mach}} \approx 10^{-16}$으로 반올림합니다. 비슷한 수의 뺄셈이 위험합니다.
• 연산자 노름 $\lVert A \rVert = \max \lVert A\mathbf{x} \rVert/\lVert \mathbf{x} \rVert$. $\lVert A \rVert_2 = \sigma_1$, $\lVert A \rVert_\infty$는 행 합의 최댓값.
• 에카르트–영: 랭크 $k$ 이하 행렬까지의 거리의 최솟값은 $\sigma_{k+1}$이고 $A_k$에서 이뤄집니다.
• 조건수 $\kappa = \lVert A \rVert\lVert A^{-1} \rVert$는 문제의 민감도. 후방 안정성은 알고리즘의 품질. 오차 $\approx \kappa\,\epsilon_{\mathrm{mach}}$.
• 부분 피벗팅, 하우스홀더 QR: 큰 수로 나누지 않고, 직교변환으로 계산합니다.
• 고윳값: 거듭제곱법(수렴비 $\lvert \lambda_2/\lambda_1 \rvert$), QR 알고리즘(모든 차원의 거듭제곱법).
• 반복법은 $\rho(M) < 1$일 때 수렴합니다. 증명에 조르당 형식이 쓰입니다.

문제

8
4
2
4

6
7
5.48
5.12

1.5
1.5
4.5
4.5
2.236

3
1000000
1
1

-1
2
36012

0
1
1
1

-5
-2.2
0
0.4

86
78
5
2

1/2
1/2
3/4
3/4
7/8
7/8
1/2

10
10
7.5
3.125
0.195