반복 개선법

잔차를 그대로 더하지 않는다

Ax = b에서 근삿값을 q라 하면 잔차는 r = b-Aq다. 보정량 d는 Ad = r을 풀어 구하고 새 값은 q+d다. r과 d는 일반적으로 다르다. 잔차 자체를 해에 더하는 계산으로 바꾸면 다른 반복법이 된다.

보정량의 수치 예

A의 두 행이 (3,1), (1,2)이고 b = (5,5)라고 하자. 근삿값 q = (0.9,2.1)을 넣으면 Aq = (4.8,5.1)로 잔차는 (0.2,-0.1)이다. Ad = r의 정확한 해는 d = (0.1,-0.1)이며 q에 더하면 (1,2)다. 이 값은 원래 두 식을 모두 만족한다.

분해를 재사용하는 이유

보정 방정식의 계수 행렬은 원래와 같다. LU 분해를 이미 구했다면 매번 분해를 다시 만들지 않고 삼각계 풀이로 보정량을 계산할 수 있다. 보정을 몇 번 반복할지와 분해를 어떤 정밀도로 만들지는 문제와 목표 정확도에 따라 정한다.

잔차 계산의 정밀도

b와 Aq가 가까우면 뺄셈에서 작은 잔차의 유효 자릿수가 부족해질 수 있다. 잔차를 더 높은 정밀도로 계산하는 혼합 정밀도 구성이 사용된다. 앞의 예는 정확한 보정 방정식을 푼 예이며 실제 계산에서 한 번이면 항상 정확해진다는 보장은 아니다. 조건수와 보정 풀이의 품질도 확인한다.