야코비·가우스–자이델 반복법 계산기

소거법은 정해진 횟수 안에 답을 끝내지만 반복법은 어림값에서 출발해 답에 다가갈 뿐이며, 수렴할 때만 쓸모가 있습니다. 대신 행렬을 통째로 들고 있지 않아도 되고 0이 대부분인 큰 행렬에서 훨씬 쌉니다. 편미분방정식을 격자로 풀 때처럼 미지수가 수백만 개인 문제는 반복법 말고는 방법이 없습니다.

오른쪽에 넣는 값이 다릅니다. 야코비는 지난 회차 값만 쓰고, 가우스–자이델은 방금 갱신한 값을 곧바로 씁니다. 정보가 빨리 퍼지므로 가우스–자이델이 같은 문제에서 대개 야코비의 절반쯤 되는 회차로 끝납니다. 2×2에서는 가우스–자이델의 수렴 인자가 야코비의 제곱이 되는 것이 정확히 증명됩니다. 대신 야코비는 한 회차 안의 계산이 서로 독립이라 병렬로 나눠 돌릴 수 있습니다.

반복행렬 T의 스펙트럼 반지름 ρ(T)가 1보다 작을 때만 수렴합니다. 한 회차는 x ← Tx + c라는 사상이고 오차는 회차마다 T를 한 번씩 더 먹으므로, 초기값을 아무리 잘 잡아도 ρ ≥ 1이면 발산하고 아무리 나쁘게 잡아도 ρ < 1이면 수렴합니다. 초기값은 걸리는 회차만 바꿀 뿐 수렴 여부를 바꾸지 못합니다.

네, 하지만 그 반대는 아닙니다. 대각우세(|aᵢᵢ| > 나머지 절댓값의 합)는 수렴을 보장하는 충분조건일 뿐이라, 대각우세가 아니어도 수렴하는 행렬이 얼마든지 있습니다. 「대각우세는 아닌데 수렴」 예제로 확인할 수 있습니다. 판정은 대각우세가 아니라 ρ(T)로 해야 정확합니다.

식의 순서는 수학적으로 아무 뜻이 없지만 반복법에는 뜻이 있습니다. 반복법이 푸는 것은 행렬 자체가 아니라 「행렬을 대각 부분과 나머지로 쪼갠 방식」이기 때문입니다. 순서가 바뀌면 무엇이 대각선에 오는지가 바뀌고, 그러면 반복행렬 T가 통째로 달라집니다. 발산하던 문제가 행 하나를 옮기는 것만으로 수렴하게 되는 일이 흔합니다.

1보다 조금 크게 두고 회차가 줄어드는지 보며 맞춥니다. 이 계산기에서 ω를 조금씩 올려 보면 ρ가 내려갔다가 다시 올라가는 골짜기가 보이는데, 그 바닥이 최적입니다. 특별한 구조(2-순환 일관 순서 행렬)에서는 최적 ω를 야코비의 ρ로부터 계산하는 공식이 있지만 일반 행렬에는 쓸 수 없습니다. ω가 2 이상이면 어떤 행렬에서도 발산합니다(카한 정리).

전송되지 않습니다. 모든 계산이 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.