반복은 한 점으로 빨려든다
계산기에 아무 숫자나 넣고 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 를 영리하게 설계한, 가장 빠른 불동점 반복인 이유예요.