[인공지능 데브코스 TIL]가우스 소거법

Solutions of  a Linear System

• 해가 하나인 경우(unique solution)
• 해가 없는 경우(no solution)
  • 0 * x = 6
• 해가 여러개인 경우(infinitely many solutions)
  • 0 * x = 0
• ax = b에서
  • a = 0이면 특이하다.
    • ax = b의 해가 곧장 나오지 않는다. 왜?
    • a의 역수(inverse)가 존재하지 않는 경우, a가 특이(singular)하다고 한다.
  • 해가 있으면 선형시스템이 consistent하다고 한다.
  • 해가 없으면 선형시스템이 inconsistent하다고 한다.

Gauss elimination(가우스 소거법)

• Forward elimination(전방소거법) : 주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형한다.
• back-substitution(후방대입법) : 아래에서부터 위로 미지수를 실제값으로 대체한다.

위의 식을 forward elimination 하는 절차

1. 1행 1열을 기준(pivot)으로 잡기.
2. 2행 <= 2행 - 1행
3. 3행 <= 3행 - 2 * 1행
4. 2행 2열을 기준(pivot)으로 잡기
5. 2행 2열 값이 0 이므로 3행과 교환 2행 <= > 3행
6. 2행 <= -2행
7. 3행 3열을 기준으로 잡기
8. 3행 <= 1/2 * 3행

• 소거법에 쓰이는 Elementary Row Operations( EROs, 기본행연산)
  • Replacement(치환) 
  • j 번째 행을 기준행을 m배 하여 빼서 업데이트 한다.

• Interchange(교환)
  • j번째 행과 i번째 행을 교환한다.

• Scaling(스케일링)
  • j번째 행을 s배 스케일링한다.

 

⭐중요 Foward Elimination(전방소거법)의 가치

• 주어진 선형시스템을 가장 풀기 쉬운 꼴로 변형해준다.
• 주어진 선형시스템의 rank(랭크)를 알려준다.
• 선형시스템이 해가 있는지 없는지 알려준다.
• Upper triangular form(상삼각형태) : Forward elimination은 EROs을 활용하여 주어진 성형 시스템 Ax=b에서 행렬 A를 upper triangular form으로 만드는 작업을 수행한다.
•