반복은 한 점으로 빨려든다
계산기에 수를 넣고 cos 를 거듭 누르면 결과가 어느 수 근처에서 더는 움직이지 않는다. 약 0.7391이다. 같은 함수를 자기 출력에 거듭 넣는 이 반복이 불동점 반복이에요. x 다음에 g(x), 그 다음에 g(g(x)). g(x)=x 가 되는 점, 곧 넣어도 그대로 나오는 점에 닿으면 멈춘다. 그 점이 불동점이다. 위상평면의 이야기는 같은 점을 고정점이라 부른다. 어디서 출발하든 같은 점으로 빨려든다는 것이 신기해요. 조건이 있다. 불동점 근처에서 기울기 |g'| 가 1 보다 작아야 한다. 그래야 한 걸음마다 거리가 줄어드는 수축이 된다. 방정식, 컴퓨터 그래픽, 경제의 균형, 검색의 순위까지 이 생각이 숨어 있다. 뉴턴법도 아주 빠른 불동점 반복이에요. 거미줄 그림이 그 빨려듦을 보여 준다.
파란 곡선이 g(x)=cos x, 점선이 y=x 다. 두 선이 만나는 초록 점이 불동점이에요. 한 걸음을 누르면 거미줄(cobweb)이 그려진다. 지금 x 에서 수직으로 곡선까지 올라가 다음 값을 읽고, 거기서 수평으로 y=x 선까지 가서 그 값을 새로운 x 로 삼는다. 시작 x0 를 어디로 옮겨도 거미줄이 교점으로 말려 들어간다. 이 그림 한 장이 불동점 반복의 전부예요. 초록 점은 두 선이 같은 높이를 가지는 자리다.
어떤 반복은 모이고 어떤 반복은 흩어진다. 답은 기울기 하나다. 여기 g 는 직선이고 불동점은 1 이에요. a 슬라이더가 곧 g' 다. |a| 를 1 보다 작게 두면 거미줄이 초록으로 불동점에 차곡차곡 모이고, 이것이 수축이다. |a| 를 1 보다 크게 하면 빨강으로 바뀌며 불동점에서 밀려나 발산해요. |a| 가 0 에 가까울수록 몇 걸음 만에 끝난다. 작은 기울기가 곧 빠른 수렴이에요.
같은 직선 g 인데 이번에는 a 의 부호를 본다. 기울기의 크기는 수렴인지 발산인지를 정하고, 부호는 모양을 정해요. a 가 양수면 거미줄이 한쪽에서 불동점으로 단조롭게 다가가는 계단이 된다. a 가 음수면 불동점을 사이에 두고 위아래로 번갈아 오가는 나선이 되어, 한 걸음마다 부호가 뒤집힌다. 슬라이더를 0 을 가로질러 끌면 계단이 나선으로, 나선이 계단으로 바뀌는 순간이 보여요.
수렴이 보장되어도 속도는 천차만별이다. 허용오차 1e-6 에 닿기까지 걸리는 걸음 수는 대략 n ≈ log(tol)/log|g'| 예요. 곡선이 그 수를 |g'| 에 따라 보여 준다. 슬라이더를 0.5 쯤 두면 스무 걸음 안에 끝나지만, 0.95 쪽으로 밀면 수백 걸음으로 폭증한다. 1 에 가까운 수축은 모이긴 해도 답답할 만큼 느려요. 그래서 더 빠른 방법이 필요해진다. 가로축은 기울기의 크기이고, 세로축은 필요한 걸음 수다.
그 빠른 방법이 여기 있다. 보통의 불동점 반복은 선형 수렴이라 오차가 절반처럼 한 걸음마다 일정한 비율로만 줄어요. 막대는 완만하게 내려간다. 뉴턴법은 2차 수렴이라 오차가 한 걸음마다 제곱되고, 맞는 자릿수가 두 배씩 늘어 막대가 절벽처럼 떨어진다. 둘을 바꾸면 같은 1e-10 정밀도에 선형은 수십 걸음, 2차는 몇 걸음이다. 뉴턴이 g'=0 이 되도록 g 를 설계한, 가장 빠른 불동점 반복인 까닭이에요.