가우스 소거법
가우스 소거법은 연립 일차방정식 또는 행렬을 기본 행 연산으로 삼각 형태로 바꾸어 해를 구한다 선형대수 계산 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합...
| 분류 | 알고리즘 · 선형대수 계산 |
|---|---|
| 핵심 문제 | 연립 일차방정식 또는 행렬을 기본 행 연산으로 삼각 형태로 바꾸어 해를 구한다 |
| 방법 | 피벗 열의 행을 선택해 아래 행에서 피벗 계수를 제거하고, 뒤로 대입하여 미지수를 구한다 |
| 계산 비용 | 조밀한 n×n 시스템에서 O(n³) 연산, 저장 O(n²) |
| 적용 조건 | 피벗 0·특이 행렬·부동소수점 오차를 처리해야 한다 |
| 관련 활용 | 선형 방정식 해법과 행렬 계수 분석의 기반이다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
가우스 소거법은 연립 일차방정식 또는 행렬을 기본 행 연산으로 삼각 형태로 바꾸어 해를 구한다 선형대수 계산 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 피벗 열의 행을 선택해 아래 행에서 피벗 계수를 제거하고, 뒤로 대입하여 미지수를 구한다. 부분 피벗팅은 수치적 불안정을 줄이는 데 도움이 된다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 조밀한 n×n 시스템에서 O(n³) 연산, 저장 O(n²) 적용 전제는 피벗 0·특이 행렬·부동소수점 오차를 처리해야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 선형 방정식 해법과 행렬 계수 분석의 기반이다. 여러 우변을 풀 때 LU 분해를 재사용하는 방법도 있다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]