켤레기울기법 (Conjugate Gradient Method)

한 줄 정의: 대칭 양정부호 연립방정식을 반복적으로 푸는 효율적인 수치 알고리즘입니다.

쉽게 풀면

큰 연립방정식을 직접 소거법으로 푸는 대신, 해에 점점 가까워지는 방향으로 반복해서 나아가는 방법입니다. 경사하강법은 지그재그로 느리게 움직이지만, 켤레기울기법은 이전에 나아간 방향과 겹치지 않도록 새 방향을 고르기 때문에 훨씬 빠르게 수렴합니다. 이론적으로는 미지수 개수만큼 반복하면 정확한 해에 도달합니다.

왜 중요한가

유한요소 해석이나 편미분방정식 이산화에서 나오는 행렬은 수백만 차원이면서 대부분의 성분이 0인 희소행렬이라, 직접법으로는 메모리와 시간이 감당되지 않습니다. 켤레기울기법은 행렬-벡터 곱만 사용하므로 이런 대규모 문제의 표준 해법이 되었습니다.

논문에서는 이렇게 쓰입니다

"전처리 조건을 적용한 켤레기울기법으로 희소 선형계를 반복적으로 풀어 수렴 속도를 개선하였다."

조금 더 깊게 보면

각 반복에서 선택되는 탐색 방향들은 행렬을 매개로 한 내적에서 서로 직교하며, 이 성질 덕분에 이미 최적화한 방향을 다시 손대지 않아도 됩니다. 수렴 속도는 행렬의 조건수의 제곱근에 좌우되므로, 조건수를 낮추는 전처리 행렬을 곱해 사용하는 전처리 켤레기울기법이 실무의 기본형입니다. 대칭이 아니거나 양정부호가 아닌 문제에는 GMRES나 BiCGSTAB 같은 변형이 사용됩니다.

주의할 점

행렬이 대칭이고 양의 정부호라는 조건이 필요하며, 이를 만족하지 않으면 수렴이 보장되지 않습니다. 또 반올림 오차 때문에 실제로는 미지수 개수만큼 반복해도 정확한 해가 나오지 않아, 수렴 판정 기준을 따로 두어야 합니다.