[Math] ill-posed, well-posed, ill-conditioned, well-conditioned matrix (or problem)

well-posed matrix and well-conditioned matrix

$A\textbf{x}=\textbf{b}$와 같은 Linear System (연립방정식)에서
system matrix $A$가 invertible하다면
해당 linear system(달리 말하면 연립방정식)이 well-posed라고 할 수 있다.

• 하지만, 해당 matrix가 "일부 item의 약간의 변화" 또는 "$\text{b}$에서의 약간의 변화" 등에 solution이 지나치게 큰 변화를 보이는 "민감성"을 가질 수 있다.
• 이같은 경우, linear system을 풀 때 적용한 수치해석적 방법의 한계 나 matrix를 만들 때 피할 수 없는 noise등 의 영향이 매우 커져 solution을 구할 수 없다. 
• 이를 해결하는 대표적인 방법이 Regularization(정칙화) 임!

참고로, 이같은 민감도를 정량적인 scalar로 나타내는 것이 condition number(조건수)라고 한다.

(실제로 condition number가 지나치게 큰 경우, ill-conditioned라고 부름)

well-conditioned 란 linear systme의 system matrix의 condition number가 작은 경우로, 민감도가 낮아 solution을 용이하게 구할 수 있는 경우를 가르킨다.

 

condition number를 통해 well-posed와 well-conditioned 를 쉽게 구분하면,

• condition number가 유한할 경우 : well-posed
• condition number가 작을 경우 : well-conditioned
  라고 할 수 있다.

Well-Posed 인 경우, 다음의 3가지 조건을 만족한다.

1. Solution이 적어도 하나 존재해야 함: Existence

2. 존재하는 Solution이 유일해야 함: Uniqueness

3. 데이터(Matrix Entity 혹은 $\textbf{b}$)가 연속적으로 변할 때,

    Solution도 연속적으로 변하게 되며,

    데이터의 작은 변화가 Solution에 큰 변화를 일으키지 않아야 함.
    (noise로 인해 데이터가 약간 변하면 Solution도 약간의 영향을 받음)

 

3번의 조건은 Continuous Dependence라고 불림.

 

위의 조건은 고전적(또는 정성적)인 Well-Posed Problem의 조건으로
Hadamard가 제안함: 정량적인 조건은 Condition Number로 판정.

이를 만족하지 않는 경우를 ill-posed problem이라고 간주.

---

ill-posed matrix ill-conditioned matrix

ill-posed 는 well-posed에 대비되는 개념으로 condtion number가 무한한 경우이다. 

 

쉽게 생각하면

• 구해야하는 변수보다 주어진 equation(식)이 적은 경우로
  free variable이 생겨서 무수히 많은 solution을 가질 수 있는 경우를 예로 들 수 있다.
  • $A\mathbf{x}=\mathbf{b}$로 표현되는 경우에서 
  • 행(row)의 수(보통 m으로 표현)가 열(column)의 수(보통 n으로 표현)보다 작은 경우: Under-Determined
• solution이 존재하지 않는 경우도 ill-posed 에 해당하나, 많은 공학적 문제에선 여러 solution이 존재하는 경우가 더 많다.
  • 모델링한 linear system에서는 solution이나, 실제 해결책이 아닌 경우가 많기 때문임.
  • 즉, 모델의 한계로 solution set에 속하나, 실제 solution이 아닌 것을 제하고
  • 가장 적절한 solution을 골라야 함.

ill-posed의 경우, 보통 regularization(정칙화)등을 통해 수많은 해에서 가장 적절한 solution을 구하려고 노력하게 된다.

ill-posed의 경우, solution이 유일하게 존재하지 않기 때문에
주어진 matrix $A$만으로는 진짜 solution을 구하기가 매우 어렵다. 

 

반면 ill-conditioned 는 well-conditioned에 대비되는 개념이다.
(즉, well-posed이면서도 ill-conditioned 일 수 있다.)

 

ill-conditioned의 경우 condition number가 매우 큰 경우에 해당하며, nearly singular 이라고도 불린다.

수치해석적으로 볼 때 stability가 낮은 경우라 할 수 있다. (작은 noise에도 매우 큰 오차가 발생.)

• singular matrix 가 non-invertible 임을 기억!

역시 간략히 요약하면 다음과 같다.
Condition Number를 통해 ill-posed와 ill-conditioned 를 구분하면,

• condition number가 무한할 경우 : ill-posed
• condition number가 매우 클 경우 : ill-conditioned

condition number가 얼마나 커야 ill-conditioned이고
얼마나 작아야 well-conditioned인지는 각 문제(or task)에 따라 다르다.
참고로 identity matrix의 경우 conditin number는 1임.

---

참고

https://bme-g.tistory.com/29

[LA] Matrix Norm and Condition Number

---