홈

수치행렬대수에서의 조건수가 상대오차의 상한에 비례함을 증명

../2872

정의 ¹

주어진 행렬 $A \in \mathbb{R}^{m \times n}$ 에 대해, 조건수 $\kappa (A)$ 를 다음과 같이 정의한다. $$ \kappa(A) = \left\| A \right\| \left\| A^{\dagger} \right\| = {\frac{ \sigma_{1} }{ \sigma_{r} }} $$ 여기서 $\left\| \cdot \right\|$ 는 프로베니우스 놈, $A^{\dagger}$ 는 $A$ 의 유사역행렬이다. $\sigma_{k}$ 는 $A$ 의 $k$ 번째로 큰 특이값으로, $r \le \min (m, n)$ 은 $A$ 의 랭크다. $\kappa (A)$ 가 크면 $A$ 가 악조건 행렬^{ill-conditioned matrix}, 작으면 호조건 행렬^{well-conditioned matrix}이라고 한다.

정리

선형시스템 $A \mathbf{x} = \mathbf{b}$ 을 푸는 알고리즘의 상대오차 상한은 조건수에 비례한다. $$ \frac{\left\| \bar{\mathbf{x}} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \varepsilon c \kappa(A) $$ 여기서 $\varepsilon > 0$ 은 충분히 작은 상수, 더 구체적으로는 머신입실론 $\epsilon$ 이라 보아도 무방하다. $c = c(A, \mathbf{b})$ 는 $A$ 와 $\mathbf{b}$ 의해 결정된다.

설명

언뜻 보면 일반적인 조건수와 수치행렬대수에서의 조건수는 전혀 다른 정의를 가진 것처럼 보인다. 행렬에 대한 조건수가 왜 저렇게 정의되는지는 다음의 증명을 살펴봐야 이해가 된다.

증명 ²

$$ A \mathbf{x} = \mathbf{b} $$ $A \in \mathbb{R}^{m \times n}$ 와 $\mathbf{b} \in \mathbb{R}^{m}$ 에 대해 위와 같은 선형시스템을 푸는 알고리즘이 있다고 할 때, $m = n$ 이고 $A$ 가 가역행렬이 아닌 이상 최소제곱법을 쓰게 되는 것이고, $A$ 와 $\mathbf{b}$ 각각에 약간의 섭동^perturbation $\varepsilon F$ 와 $\varepsilon \mathbf{f}$ 가 가해진다고 두어야 한다. $$ \left( A + \varepsilon F \right) \mathbf{x} = \mathbf{b} + \varepsilon \mathbf{f} $$ 이 때의 해는 $\varepsilon$ 에 종속되어 $\mathbf{x} = \mathbf{x}(\varepsilon)$ 라 둘 수 있고, $\mathbf{x} (0) = \mathbf{x}$ 다. $\mathbf{x}(\varepsilon)$ 는 $\varepsilon = 0$ 의 근방에서 미분가능하고, 이에 대한 테일러전개는 다음과 같다. $$ \mathbf{x}(\varepsilon) = \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) $$ 여기서 $\mathbf{x} ' (0)$ 는 $\varepsilon$ 에 대한 미분으로써 구할 수 있다. $$ \begin{align*} \left( A + \varepsilon F \right) \mathbf{x} \left( \varepsilon \right) =& \mathbf{b} + \varepsilon \mathbf{f} \\ \implies A \mathbf{x} ' \left( \varepsilon \right) + F \mathbf{x} \left( \varepsilon \right) + \varepsilon F \mathbf{x} ' \left( \varepsilon \right) =& \mathbf{f} \\ \implies A \mathbf{x} ' \left( 0 \right) + F \mathbf{x} \left( 0 \right) =& \mathbf{f} \\ \implies \mathbf{x} ' \left( 0 \right) =& A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \left( 0 \right) \right] \end{align*} $$ 이를 상대오차에 대해 나타내려 해보면, 놈의 삼각부등식 $|a-b| \le |a| + |b|$ 에 의해 다음의 부등식을 얻는다. $$ \begin{align*} \mathbf{x}(\varepsilon) =& \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) \\ \implies \mathbf{x}(\varepsilon) - \mathbf{x} =& \varepsilon A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \end{align*} $$

일반화된 코시-슈바르츠 부등식: $$ \left\| \mathbf{x} \right\| \left\| \mathbf{y} \right\| \ge \left< \mathbf{x} , \mathbf{y} \right> $$

일반화된 코시-슈바르츠 부등식에 의해 다음의 보조부등식을 얻는다. $$ \begin{align*} \left\| \mathbf{b} \right\| \le& \left\| A \right\| \left\| \mathbf{x} \right\| \\ \implies {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} \le & {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} \end{align*} $$ 따라서 $\mathbf{x}$ 에 대한 상대오차는 다음과 같다. $$ \begin{align*} {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} + \left\| A \right\| {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A \right\| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{b} \right\| }} + {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \end{align*} $$ 여기서 $\left\| F \right\| / \left\| A \right\|$ 와 $\left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$ 는 그 자체가 각각 $A$ 와 $\mathbf{b}$ 에 대한 상대오차로, $c = \left\| F \right\| / \left\| A \right\| + \left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$ 라 두고 충분히 작은 $\varepsilon$ 에 대해 $O \left( \varepsilon^2 \right)$ 를 무시하면 원하던 결과를 얻는다.

■

최소제곱법에서 LU, QR, SVD의 속도 비교

../X005

요약 ¹

행렬 $A \in \mathbb{R}^{m \times n}$ 에 대해, $m \ge n$ 이라고 하자. LU 분해와 QR 분해 그리고 특이값 분해로 최소제곱법을 수행할 때 시간복잡도는 모두 동일하게 $O \left( mn^{2} \right)$ 이지만, 실제로 필요한 flop 수는 대략 다음과 같다.

• LU 분해²: $$ mn^{2} + {\frac{ 2 }{ 3 }} n^{3} $$
• QR 분해³: $$ 2mn^{2} - {\frac{ 2 }{ 3 }} n^{3} $$
• 특이값 분해⁴: $$ 4mn^{2} - {\frac{ 4 }{ 3 }} n^{3} $$

단 이 요약에는 ‘의도적으로 틀린 부분’이 포함되어 있으니 맹신하지 말고, 반드시 본문의 내용을 읽어보길 권한다.

설명

최소제곱법의 실질적인 구현으로써 행렬분해를 사용하는 방법은 여러가지가 있으나, 흔히 LU 분해(콜레스키 분해)를 통한 방법과 QR 분해를 통한 방법 그리고 SVD 분해를 통한 방법 세가지가 특히 널리 쓰인다. 참고로 LU 분해든 콜레스키 분해든 가우스 소거법이든 본질적으로 전진대입과 후진대입을 통해 선형시스템을 푸는 방법이므로 최소제곱법의 구현이라는 측면에서는 모두 같은 것이라고 보아도 무방하다. 실제로 콜레스키 분해의 flops는 $mn^{2} + {\frac{ 1 }{ 3 }} n^{3}$ 으로 LU 분해보다 조금 더 좋지만, 현실적으로는 안정성을 위해 피버팅^pivoting이 포함된 PLU 분해을 쓰게 된다.

줄리아⁵나 매트랩⁶의 구현을 보면 사실상 $A$ 에서 $m \ne n$ 일 때는 QR 분해, $m = n$ 일 때는 LU 분해를 쓴다고 보면 된다.

실제로 flops의 비교에서 가장 중요하고 지배적인 항은 $m n^{2}$ 으로써 LU에서 QR, SVD로 갈수록 계산량은 거의 2배씩 늘어나는 것을 볼 수 있다. 다만 이러한 요약은 받아들이기 쉽게 정리한 것이지 구체적인 공식 자체는 flop이나 구현방식에 따라 달라질 수도 있다.

LU 분해

사실 LU 분해는 $2n^{3}/3$ 만큼의 flops만 필요하지만 최소제곱법을 위해서는 $A \mathbf{x} = \mathbf{b}$ 에서 $A^{\top} A \mathbf{x} = A^{\top} \mathbf{b}$ 로 바꾸어야 하므로, $A^{\top} A$ 을 계산할 때 $mn^{2}$ 만큼의 flops가 추가로 필요하다.

당연하지만 $m = n$ 인 경우에는 $A^{\top} A$ 을 계산할 필요가 없으므로 앞의 항이 사라져서 $2/3 n^{3}$ 이 되고 QR 분해에 비해 두 배 빠르다. 반대로 $m \gg n$ 인 경우에도 $n^{3}$ 의 비중은 줄어들어서 결국 QR 분해에 비해 두 배 정도 빨라진다. 정말 좋은 조건의 행렬을 가지고 속도를 우선시해야 한다면 LU 분해를 쓰는 게 나을 때도 있는 것이다.

QR 분해

LU 분해에 비해 두 배 느리고 SVD에 비해 두 배 빠르다. 어떻게 보면 어중간하다고 볼 수도 있겠지만, SVD가 너무 느려서 최소제곱법의 구현에 기본적으로 쓰이는 경우가 드물다는 걸 생각해보면 가장 무난하고 좋은 방법이라 볼 수 있다. 현실적으로 이 세상에서 대부분의 최소제곱문제가 QR 분해를 통해 해결되고 있을 것이다.

SVD

정리된 SVD의 flops는 고룹-카한 이분대각화^{Golub-Kahan bidiagonalization}을 사용할 때 $4mn^{2}$ 이 앞서 나오지만, 행렬 분해만 하는 게 아니라 특이값 분해에 초점을 맞추면 행렬분해와 별개의 계산이 늘어나거나 줄어들어서 다음과 같다. $$ 2 mn^{2} + 11 n^{3} $$ 이것이 앞서 언급한 ‘의도적으로 틀린 부분’이다. 어찌됐든 QR에 비해 느린 건 사실이고, 말 그대로 최소제곱법 한 번을 위해서라면 이 방법을 쓸 이유가 딱히 없기 때문에 더 간결한 비교를 한 것이다.

안정성과의 트레이드 오프

세 방법의 속도를 비교해보고 안정성을 비교해보면 다음과 같이 아주 명확하게 트레이드 오프를 확인할 수 있다.

최소제곱법에서 LU, QR, SVD의 안정성 비교

../X006

요약

행렬 $A \in \mathbb{R}^{m \times n}$ 에 대해, $m \ge n$ 이라고 하자. LU 분해와 QR 분해 그리고 특이값 분해로 최소제곱법을 수행할 때 세 방법 모두 후방안정적이다. 다만, 후방안정성을 만족하는 조건이 다르다. 행렬이 풀랭크라는 것은 $A$ 의 랭크 $r$ 이 $\min (m, n)$ 과 같다는 의미다.

• LU 분해¹: $A$ 가 풀랭크일지라도 불안정적이다.
• QR 분해²: $A$ 가 풀랭크면 후방안정적이다.
• 특이값 분해³: $A$ 가 풀랭크가 아니라도 후방안정적이다.

설명

최소제곱법의 실질적인 구현으로써 행렬분해를 사용하는 방법은 여러가지가 있으나, 흔히 LU 분해(콜레스키 분해)를 통한 방법과 QR 분해를 통한 방법 그리고 SVD 분해를 통한 방법 세가지가 특히 널리 쓰인다. 참고로 LU 분해든 콜레스키 분해든 가우스 소거법이든 본질적으로 전진대입과 후진대입을 통해 선형시스템을 푸는 방법이므로 최소제곱법의 구현이라는 측면에서는 모두 같은 것이라고 보아도 무방하다. 실제로 콜레스키 분해의 flops는 $mn^{2} + {\frac{ 1 }{ 3 }} n^{3}$ 으로 LU 분해보다 조금 더 좋지만, 현실적으로는 안정성을 위해 피버팅^pivoting이 포함된 PLU 분해을 쓰게 된다.

줄리아⁴나 매트랩⁵의 구현을 보면 사실상 $A$ 에서 $m \ne n$ 일 때는 QR 분해, $m = n$ 일 때는 LU 분해를 쓴다고 보면 된다.

LU 분해

행렬의 조건수 $\kappa = \kappa(A)$ 를 생각해보면 알고리즘의 상대오차 상한은 $\kappa$ 에 달려있는데, LU 분해든 콜레스키 분해든 표준방정식 $A^{\top} A \mathbf{x} = A^{\top} \mathbf{b}$ 을 세우는 시점에서 이미 $\kappa \left( A^{\top} A \right) = \kappa^{2}$ 가 되어 가뜩이나 안 좋을 수 있는 조건수가 더 악화된다.

$A = LU$ 에 대해 $\rho = {\frac{ \max \left| U_{ij} \right| }{ \max \left| A_{ij} \right| }}$ 를 $A$ 의 성장요인^{growth factor}라 하는데, 그나마 피버팅 LU에서 $\rho = O (1)$ 이고 $A$ 의 상대오차가 $\rho$ 와 머신입실론 $\epsilon$ 에 대해 $O \left( \rho \epsilon \right)$ 이라고 할 때 후방안정성을 가진다.

딱 봐도 느껴지겠지만 끝끝내 후방안정적이긴한데 구구절절하게 필요한 조건들이 많아서 사실상 불안정적이다. 이는 가우스 소거법의 기본 행 연산을 수행할 때 수를 곱하고 더하면서 생기는 오차가 점점 더 커질 가능성이 있기 때문이다.

QR 분해

QR 분해의 과정:

• Step 2-4. 다음을 계산한다. $$ \mathbf{q}_{j} = {{ \mathbf{v}_{j} } \over {r_{jj} }} $$

QR 분해도 구현하는 방식이 여러가지가 있기 때문에 꼭 이 이러한 이유로 안정성을 잃는다고 할 수는 없지만, 적어도 이와 같이 그램-슈미트 직교화를 사용하는 경우에는 벡터를 $r_{jj}$ 로 나누는 등의 과정에서 문제가 발생할 수 있다. 그야말로 $A$ 가 악조건인가 아닌가, 다시 말해 이러한 특이성^singularity이 문제 속에 도사리고 있는지에 달렸다고 할 수 있다.

그러나 LU에 비할바는 아니며, 가장 범용적으로 쓰이는만큼 안정성을 지나치게 걱정할 필요는 없다. 참고로 QR 분해에서도 어지간하면 피버팅이 기본적으로 들어간다.

SVD

랭크 결핍^{rank-deficiency}이 있는 상황에서도 안정적인 알고리즘은 SVD 뿐이다. 수식적으로 $A = U \Sigma V^{\top}$ 에서 $\Sigma$ 의 역행렬 $\Sigma^{-1}$ 을 구할 때는 $A$ 의 특이값 중 $0$ 에 가까운 부분들을 아예 제거한 축소 특이값 분해^{reduced SVD}를 시도할 수 있다. 이는 피버팅에 의존해야 하는 다른 분해법과 달리 충분히 작은 임계치를 명시적으로 설정하여 수치적인 문제를 원천적으로 봉쇄하는 것이나 마찬가지다. 기본적인 코스트가 높기 때문에 최소제곱법을 구현하기 위해서 잘 쓰이는 것은 아니지만, 그만큼 안정성에서는 절대로 밀리지 않는 것이다.

속도와의 트레이드 오프

세 방법의 속도를 비교해보고 안정성을 비교해보면 다음과 같이 아주 명확하게 트레이드 오프를 확인할 수 있다.

SVD를 이용한 티호노프 정칙화 $\lambda$ 스윕 트릭

동역학계로써의 조류-주플랑크톤 모델

Chattopadhyay, S. N., & Gupta, A. K. (2024). B-tipping points in plankton dynamics: Stochasticity and early warning signals. Physical Review E, 110(6), 064218. https://doi.org/10.1103/PhysRevE.110.064218

아이자와 어트랙터

Ghanbari, B., Gómez-Aguilar, J.F. Two efficient numerical schemes for simulating dynamical systems and capturing chaotic behaviors with Mittag–Leffler memory. Engineering with Computers 38, 2139–2167 (2022). https://doi.org/10.1007/s00366-020-01170-0

Zhai, ZM., Stern, B.D. & Lai, YC. Bridging known and unknown dynamics by transformer-based machine-learning inference from sparse observations. Nat Commun 16, 8053 (2025). https://doi.org/10.1038/s41467-025-63019-8

Zhang, Y., Li, W., & Carvalho, R. (2026). Fast and principled equation discovery from chaos to climate. arXiv preprint arXiv:2604.11929. https://arxiv.org/pdf/2604.11929

https://www.algosome.com/articles/aizawa-attractor-chaos.html

https://sequelaencollection.home.blog/3d-chaotic-attractors/

머슈룸 바이퍼케이션

Otero-Muras, I., Perez-Carrasco, R., Banga, J. R., & Barnes, C. P. (2023). Automated design of gene circuits with optimal mushroom-bifurcation behavior. Iscience, 26(6). https://doi.org/10.1016/j.isci.2023.106836

커스프 바이퍼케이션

Frey, E., & Brauns, F. (2022). Self-organization of protein patterns. In Active Matter and Nonequilibrium Statistical Physics: Lecture Notes of the Les Houches Summer School (pp. 347-445). Oxford University Press. https://doi.org/10.48550/arXiv.2012.01797

리미트사이클의 바이퍼케이션

¹

F-사이클과 S-사이클

¹

동역학계의 대칭성

Pujals, E., Shub, M., & Yang, Y. (2020). Stable and non-symmetric pitchfork bifurcations. Science China Mathematics, 63(9), 1837-1852.

라자팍세-스메일

Rajapakse, I., & Smale, S. (2016). The pitchfork bifurcation. arXiv preprint arXiv:1609.05996. https://arxiv.org/pdf/1609.05996

Pujals, E., Shub, M., & Yang, Y. (2020). Stable and non-symmetric pitchfork bifurcations. Science China Mathematics, 63(9), 1837-1852. https://arxiv.org/pdf/1804.03264

$$ \begin{align*} \dot{x} =& y^{2} - \left( \varepsilon + 1 \right) y - x \\ \dot{y} =& x^{2} - \left( \varepsilon + 1 \right) x - y \end{align*} $$

Michaelis–Menten model for enzyme kinetics

$$ \dot{x} = j_{x} - {\frac{V_{max} x}{K_{m} + x}} $$

Kaheman, K., Kutz, J. N., & Brunton, S. L. (2020). SINDy-PI: a robust algorithm for parallel implicit sparse identification of nonlinear dynamics. Proceedings. Mathematical, physical, and engineering sciences, 476(2242), 20200279. https://doi.org/10.1098/rspa.2020.0279

첫논문 리뷰

둘쨰논문 리뷰

셋째논문 리뷰

• 퍼뮤테이션 엔트로피: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.88.174102, http://materias.df.uba.ar/dnla2019c1/files/2019/03/permutation_entropy.pdf
• 셀룰러 오토마타
  • 폰 노이만 네이버후드
  • 무어 네이버후드
• 쿠프만 오퍼레이터
• 하이퍼카오스
• CUR 분해

신경계형 레저버 컴퓨팅 Neuromorphic reservoir computing

¹

deviation value

Zhai, Z. M., Kong, L. W., & Lai, Y. C. (2023). Emergence of a resonance in machine learning. Physical Review Research, 5(3), 033127. https://doi.org/10.1103/PhysRevResearch.5.033127

동적 에러

정의 ¹