Numerical Linear Algebra (Condition Number) TODO
Concept
The condition number expresses how much a relative error in the input gets amplified into a relative error in the output; for a linear system Ax = b, it's defined as κ(A) = ||A|| · ||A⁻¹||. Under the 2-norm, this equals the ratio of the largest to the smallest singular value, σ_max/σ_min, so the closer A is to being singular, the larger the condition number. The relative error of the solution is bounded roughly by the condition number times the relative error of the input, so a condition number on the order of 10^k means you can expect to lose about k significant digits. The key distinction is that the condition number is a property of the problem itself, separate from numerical stability, which is a property of the algorithm. In other words, even a backward-stable algorithm can't produce an accurate answer if the problem itself is ill-conditioned — in that case you need a model-level response like regularization or reformulation.
If regression or optimization results wobble wildly with tiny changes in the data, it's more likely that the problem itself is ill-conditioned than a code bug — and the appropriate response is completely different in each case.
Code & Formula
# 수치선형대수(조건수) — κ(A) = σ_max/σ_min 이 클수록 입력의 작은 오차가
# 해의 큰 오차로 증폭됨을 잘 조건화된 행렬과 거의 특이한 행렬을 비교해 확인한다.
import numpy as np
A_good = np.array([[2.0, 0.0], [0.0, 3.0]]) # 축이 직교, 스케일도 비슷 → 잘 조건화됨
A_bad = np.array([[1.0, 1.0], [1.0, 1.0001]]) # 두 행이 거의 평행 → 특이행렬에 근접
b = np.array([1.0, 1.0])
b_perturbed = b + np.array([1e-4, -1e-4]) # b에 아주 작은 오차 주입
for name, A in [("잘 조건화됨", A_good), ("거의 특이 (ill-conditioned)", A_bad)]:
cond = np.linalg.cond(A)
x = np.linalg.solve(A, b)
x_perturbed = np.linalg.solve(A, b_perturbed)
rel_input_err = np.linalg.norm(b_perturbed - b) / np.linalg.norm(b)
rel_output_err = np.linalg.norm(x_perturbed - x) / np.linalg.norm(x)
print(f"[{name}] κ(A) = {cond:.2f}")
print(f" 입력 상대오차 = {rel_input_err:.2e}")
print(f" 출력(해) 상대오차 = {rel_output_err:.2e} (κ(A) * 입력오차 ≈ {cond * rel_input_err:.2e})")
print(f" 증폭 배율 = {rel_output_err / rel_input_err:.2f}\n")
print("→ 조건수가 큰 A_bad에서 동일한 입력 오차가 훨씬 크게 증폭됨을 확인 — 문제 자체의 성질이지 알고리즘 탓이 아니다.")
Exercise
Solve Ax = b using increasingly large Hilbert matrices, print out both the condition number and the actual relative error together, and check whether the two grow in step with each other.
Practical Connection
In AMM curves or LMSR price calculations, when the liquidity parameter is small or probabilities approach 0/1, exponential and logarithmic terms can blow up, producing the same kind of amplification — so fixed-point implementations need to bound the input range and rearrange formulas into numerically stable forms.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.