스테펜센 방법

1. 개요

스테펜센 방법 Steffensen's Method
푸는 것	f(x) = 0 또는 고정점 x = g(x)
필요한 것	초기점 1개, 반복당 함수 평가 2회 (도함수 불필요)
수렴 차수	2 (단순근, 근 근처에서)
제안	요한 프레데리크 스테펜센, 1933
뿌리	아이켄 Δ² 가속(1926)을 반복에 다시 먹인 것

뉴턴법의 2차 수렴은 갖고 싶은데 도함수는 계산하기 싫다. 그럼 도함수 자리에 함수값 자기 자신을 스텝 크기로 넣어 보자. 이상해 보이지만 된다.

스테펜센 방법(Steffensen’s method)은 뉴턴-랩슨법의 도함수 $f'(x)$ 를 스텝 크기가 $f(x)$ 인 차분몫으로 바꿔, 도함수 없이도 단순근 근처에서 2차 수렴을 얻는 반복법이다. 덴마크의 보험수리학자·수학자 스테펜센이 1933년에 발표했고, 고정점 반복에 쓰면 아이켄 델타제곱법으로 외삽한 값을 다음 반복의 출발점으로 다시 넣는 것과 정확히 같다.

할선법도 도함수가 필요 없지만 차수가 1.618이다. 스테펜센은 한 점에서 출발해 2차라는 점이 매력이지만, 반복당 함수 평가가 두 번이라 “평가당 효율”로 따지면 뉴턴과 같고 할선법보다 못하다. 이 문서는 그 셈법, 근에서 멀 때 드러나는 스케일 민감성, 그리고 이 방법이 실제로 살아 있는 곳 — 고정점 반복 가속 — 을 정리한다.

2. 공식

근 찾기 형태는 다음과 같다.

$$x_{k+1} = x_k - \frac{f(x_k)}{g(x_k)},\qquad g(x) = \frac{f\big(x + f(x)\big) - f(x)}{f(x)}$$

$g(x)$ 는 스텝 $h = f(x)$ 짜리 전진 차분몫이다. 근에 다가갈수록 $f(x_k)\to0$ 이니 스텝이 저절로 작아지고, 차분몫이 $f'(x_k)$ 에 점점 정확히 붙는다. 그 정확도 향상 속도가 오차와 같은 차수라서 전체가 2차가 된다. 실제로 오차는

$$e_{k+1} \approx \frac{f''(r)}{2f'(r)}\big(1 + f'(r)\big)\, e_k^2$$

꼴로 줄어든다. 뉴턴의 상수 $f''/(2f')$ 에 $(1+f')$ 가 곱해진 모양이다.¹

2.1. 검산 — 월리스의 삼차식

$f(x)=x^3-2x-5$, $x_0=2$ 에서 출발했다($f(2)=-1$ 이라 첫 차분 스텝이 $-1$ 이다).

반복	근사값	오차
1	2.2	$1.05\times10^{-1}$
3	2.1080363	$1.35\times10^{-2}$
4	2.0957202	$1.17\times10^{-3}$
5	2.0945608	$9.3\times10^{-6}$
6	2.0945514821	$5.9\times10^{-10}$
7	2.0945514815423265	0 (배정밀도)

4→5→6 에서 오차 지수가 $-3 \to -5 \to -10$ 으로 대략 두 배씩 뛰는 게 2차 수렴의 서명이다. 반복 7회, 함수 평가 14회다.

3. 평가당 효율 — 뉴턴과 같고 할선보다 못하다

한 반복에 $f(x_k)$ 와 $f(x_k + f(x_k))$ 두 번을 계산하니, 평가 한 번당 차수는 $2^{1/2} \approx 1.414$ 다.² 도함수 비용을 $f$ 와 같다고 친 뉴턴법도 $\sqrt2$ 이고, 할선법은 평가 한 번에 1.618, 뮬러 방법은 1.839다.

즉 스칼라 근 찾기만 놓고 보면 스테펜센이 이길 자리가 거의 없다. 할선법이 같은 평가 수로 더 멀리 간다. 위 삼차식에서도 브렌트 방법은 평가 8회로 끝냈다. 스테펜센의 실제 장점은 “초기점이 하나면 된다”와 “고정점 반복에 그대로 얹힌다” 쪽에 있다.

4. 근에서 멀면 — 스케일이 망가뜨린다

차분 스텝이 $f(x)$ 그 자체라는 건 단위가 안 맞는다는 뜻이다. $x$ 가 미터이고 $f$ 가 뉴턴이면 $x + f(x)$ 는 미터에 뉴턴을 더한 값이다. 근 근처에선 $f$ 가 작아서 상관없지만, 멀리서 시작하면 탐침점이 엉뚱한 곳에 꽂힌다.

같은 삼차식을 $x_0 = 3$ 에서 시작하면 $f(3)=16$ 이라 첫 탐침이 $x = 19$ 에 찍힌다. 거기서 잰 기울기는 근 근처 기울기와 딴판이라, 반복이 한 번에 $0.04$~$0.07$ 씩 기어 내려온다. 오차 $10^{-12}$ 까지 21회가 걸렸다($x_0=2$ 에선 7회). 스텝을 $\beta f(x)$ 로 줄여 $\beta = 0.05$ 를 주자 같은 출발점에서 6회로 줄었다. 근에 가까워지면 $\beta$ 는 수렴 차수에 영향이 없으니, 문제의 스케일을 알면 $\beta$ 를 박아 두는 게 국룰이다. 모르면 할선법이나 브렌트로 가는 게 낫다.

5. 고정점 형태 — 아이켄 Δ² 를 다시 먹이기

진짜 쓸모는 고정점 반복 $x = \phi(x)$ 쪽이다. 일반 반복 $x_{k+1} = \phi(x_k)$ 는 $|\phi'(r)| < 1$ 이면 바나흐 고정점 정리에 따라 수렴하지만, 수렴률이 $|\phi'(r)|$ 인 1차 수렴이다.

아이켄(Aitken, 1926)의 $\Delta^2$ 외삽은 연속한 세 값 $x,\ \phi(x),\ \phi(\phi(x))$ 가 기하수열처럼 근에 다가간다고 보고 극한을 추정한다.

$$\hat x = x - \frac{\big(\phi(x) - x\big)^2}{\phi(\phi(x)) - 2\phi(x) + x}$$

아이켄은 이걸 이미 만들어진 수열에 한 번 적용했다. 스테펜센은 $\hat x$ 를 다음 반복의 출발점으로 되먹였다. 이렇게 하면 1차 반복이 2차로 바뀐다. $f(x) = \phi(x) - x$ 로 두고 근 찾기 형태에 넣어도 똑같은 식이 나온다.

5.1. 검산 — 코사인 고정점

$x = \cos x$ (고정점 $0.7390851332151607$, $\phi'(r) = -\sin r \approx -0.674$) 를 $x_0 = 1$ 에서 풀었다.

• 일반 고정점 반복: 오차 $10^{-12}$ 까지 67회. 수렴률 0.674의 1차 수렴이니 반복마다 자릿수가 0.17개씩 붙는다.
• 스테펜센(아이켄 되먹임): 외부 반복 1·2·3회째 오차가 $1.1\times10^{-2}$, $1.8\times10^{-5}$, $4.9\times10^{-11}$ 이고 4회째에 정확한 배정밀도 값이다. $\cos$ 평가는 8회.

평가 수로 8배 넘게 줄었다. 근 찾기에서 할선법에 지던 방법이 여기선 이기는 이유는, 비교 대상이 할선법이 아니라 1차 고정점 반복이기 때문이다. 고정점 반복 쪽은 $\phi$ 를 그대로 쓰면서 바깥에 몇 줄만 얹으면 되니 기존 코드를 거의 안 건드린다.

6. 실무 — 분할 연성과 앤더슨 가속

고정점 반복이 비싼 대표 사례가 유체-구조 연성의 분할 강결합이다. 유체 솔버 → 구조 솔버 → 다시 유체를 도는 한 바퀴가 $\phi$ 이고, 계면 변위가 $x$ 다. 한 바퀴가 몇 분짜리라 반복 수가 곧 계산 시간이다.

• 아이켄 동적 완화. 계면 잔차 $r_k = \phi(x_k) - x_k$ 로 완화계수를 매 반복 갱신한다. 벡터판은 $\omega_{k} = -\omega_{k-1}\, \dfrac{r_{k-1}^{\mathsf T}(r_k - r_{k-1})}{\lVert r_k - r_{k-1}\rVert^2}$ 꼴로, 스칼라 스테펜센의 분모를 내적으로 바꾼 것이다(이언스-턱 1969 계열, FSI 에서는 퀴틀러·발 2008 이 대중화). 구현이 몇 줄이라 상용·공개 연성 코드의 기본 옵션으로 흔히 들어 있다.
• 앤더슨 가속. 최근 $m$ 개 잔차의 최소제곱 조합으로 외삽한다. $m=1$ 이면 아이켄형 외삽과 같은 정신이고, $m$ 을 늘리면 벡터 문제에서 훨씬 강해진다. IQN-ILS 같은 준뉴턴 연성 기법이 이 계열이다.

스칼라 스테펜센을 벡터로 바로 옮기는 건 생각보다 어렵다. 분모 $\phi(\phi(x)) - 2\phi(x) + x$ 가 벡터라 “나눗셈” 을 정의해야 하고, 그 선택에 따라 MPE·RRE·벡터 엡실론 같은 서로 다른 외삽법이 나온다. 결국 실무에서 살아남은 건 스칼라 스테펜센 그 자체라기보다 “되먹임 외삽으로 1차 반복을 가속한다”는 아이디어다.³

7. 함정

• 분모 상쇄. 근 근처에서 $\phi(\phi(x)) - 2\phi(x) + x$ 는 작은 수 셋의 차라 유효숫자를 크게 잃는다. 분모가 0이 되면 그 반복은 건너뛰고 일반 반복 한 번으로 대신하는 보호 코드가 필요하다.
• 중복근·$\phi'(r)=1$. 수렴이 1차로 떨어지거나 분모가 0에 가까워져 불안정하다. 뉴턴법과 같은 운명이다.
• 전역 보장 없음. 근에서 멀면 위 스케일 문제처럼 기거나 튄다. 브래킷이 필요하면 가위치법의 변형이나 브렌트를 쓴다.
• 발산하는 반복도 끌어올 수 있다. $|\phi'(r)| > 1$ 이라 일반 반복이 발산해도 스테펜센은 수렴할 수 있다. 장점이지만, 반대로 “가속했더니 원래 안 가던 엉뚱한 고정점으로 갔다”는 사고도 같은 이유로 생긴다.

8. 관련 문서

• 뉴턴-랩슨법 · 할선법 · 뮬러 방법 · 브렌트 방법 · 가위치법
• 아이켄 델타제곱법 · 앤더슨 가속 · 리처드슨 외삽법 · 바나흐 고정점 정리
• 유체-구조 연성 · 고정점 반복 · 역 이차 보간

9. Footnotes

1. $1 + f'(r)$ 항 때문에 $f'(r) = -1$ 이면 상수가 0이 돼 2차보다도 빨라진다. 반대로 $|f'|$ 이 크면 상수가 커진다. 함수값을 스텝으로 쓰는 대가다. ↩

2. 「차수의 (평가 횟수)제곱근」으로 비교하는 이 효율 지수는 오스트로프스키가 정리했다. 2차라고 자랑해도 평가를 두 번 하면 1.414 짜리다. 숫자 놀음에도 회계는 있다. ↩

3. 스테펜센의 본업은 보험수리였고, 이 논문도 보험수리 학술지에 실렸다. 보험료 계산하다 만든 반복법이 90년 뒤 유체-구조 연성 코드에 들어가 있다. 현생은 이어져 있다. ↩