탐색 공간 안에서 가장 작은 잔차를 고른다
초기값이 0이면 첫 탐색 방향은 b가 생성하는 방향이다. 이후 행렬을 반복 적용해 얻는 방향으로 공간을 넓힌다. 각 단계에서는 그 공간 안에서 b-Ax의 길이를 최소로 하는 값을 구한다. 잔차 최소화는 알 수 없는 참해와의 거리 자체를 직접 최소화한다는 뜻은 아니다.
첫 단계의 계산 예
A의 두 행이 (2,1), (0,4)이고 b = (1,1)이라 하자. 첫 공간의 후보는 x = (c,c)다. Ax = (3c,4c)이므로 잔차 길이 제곱은 (1-3c)²+(1-4c)² = 25c²-14c+2다. 최소값은 c = 7/25에서 얻는다.
잔차와 해의 차이를 구분한다
첫 근삿값은 (0.28,0.28), 잔차는 (0.16,-0.12)이며 잔차 길이는 0.2다. 원래 방정식의 정확한 해는 (0.375,0.25)다. 첫 공간에서 최선의 잔차를 얻었다고 이미 정확한 해를 구한 것은 아니다. 다음 단계는 더 넓은 공간을 이용한다.
공간을 넓히는 비용
기저 벡터를 저장하고 새 방향을 이전 방향들에 대해 직교화하므로 탐색 공간이 커질수록 저장량과 작업량도 늘어난다. 다른 반복법과 비교할 때 반복 횟수만 세지 않는다. 원래 계의 잔차, 전처리 방식과 행렬 조건수도 함께 확인한다.
관련 문서
켤레기울기법 / 최소제곱법 / QR 분해 / 전처리 (수치해석) / 희소행렬 / 행렬 조건수 / 벡터 / 부동 소수점