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.
Where it lands in Jayverse
- DeFi: add an ill-conditioning regression test for the exchange-rate math. Assert relative error stays bounded as pool size or share price sweeps toward extreme values (near-zero liquidity, near-zero shares), not just a single happy-path check.
- Verex: sweep the LMSR liquidity parameter toward its lower bound in tests. Add a test that checks price and error don't blow up in fixed-point as b shrinks, catching the same amplification the card describes before it reaches production.
- OFA: flag near-singular clearing computations explicitly. If the solver auction's clearing math involves matrix-like operations, log an ill-conditioning check so a bad auction result is diagnosed as "bad problem" rather than "bad solver," since the fix differs.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| amplified into | ~로 증폭되어 나타나다 · 작은 입력 오차가 큰 출력 오차로 바뀔 때. "gets amplified into a relative error in the output" |
| on the order of | ~자릿수 정도의 · 대략적인 크기를 수량적으로 말할 때. "a condition number on the order of 10^k" |
| significant digits | 유효숫자 · 정밀도를 몇 자리 잃는지 말할 때. "you can expect to lose about k significant digits" |
| ill-conditioned | 조건이 나쁜(민감도가 큰) · 문제 자체가 불안정한 특성을 가질 때. "the problem itself is ill-conditioned" |
| wobble wildly | 심하게 요동치다·크게 흔들리다 · 값이 작은 변화에도 크게 튈 때. "regression or optimization results wobble wildly" |
| blow up | 값이 폭발적으로 커지다·발산하다 · 수식의 항이 감당 못할 만큼 커질 때. "exponential and logarithmic terms can blow up" |
| bound the input range | 입력 범위를 제한하다 · 수치 안정성을 위해 값의 범위를 미리 제한할 때. "fixed-point implementations need to bound the input range" |
| LMSR | 로그마켓 스코어링 규칙(Logarithmic Market Scoring Rule) · 예측시장에서 유동성 파라미터로 가격을 정하는 방식. "In AMM curves or LMSR price calculations" |
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/.