켤레기울기법

보통의 직교와 다른 방향 조건

켤레 방향은 A를 사이에 둔 내적이 0이라는 뜻이다. 일반적인 pᵀq = 0과 같은 조건은 아니다. 매번 현재 잔차만 따라가는 최급강하와 달리 이전 방향의 정보를 함께 반영하여 탐색 방향을 구성한다.

첫 이동을 계산하는 예

A가 대각 원소 2와 4를 갖고 b = (2,4), 초기값이 (0,0)이라고 하자. 첫 잔차와 방향 p는 모두 (2,4)다. 첫 이동 계수는 잔차 길이 제곱을 pᵀAp로 나눈 20/72 = 5/18이다. 따라서 새 값은 (5/9,10/9)다.

잔차의 변화 확인

위 새 값의 잔차 b-Ax는 (8/9,-4/9)다. 첫 잔차와의 내적은 16/9-16/9 = 0이다. 정확한 해는 (1,1)이므로 첫 이동에서 해에 도달한 것은 아니다. 잔차가 작아지는 과정과 해 자체의 오차는 행렬 조건수도 고려해 해석한다.

이론적 종료와 실제 계산

정확한 산술에서는 n차 기본 CG가 최대 n단계 안에 해에 도달한다. 실제 부동 소수점에서는 직교 관계가 흐트러질 수 있어 이 횟수만으로 종료를 보장하지 않는다. 잔차 기준과 최대 반복 횟수를 확인하고 필요한 경우 적절한 전처리를 사용한다. 임의의 비대칭 행렬에 기본 CG를 그대로 적용하지 않는다.