\(f(x) = 0\)을 \(x = g(x)\) 꼴로 바꿔 놓고, 아무 값이나 \(g\)에 넣고 나온 값을 다시 넣기를 되풀이한다. 넣은 값과 나온 값이 같아지는 점(고정점)이 원래 식의 근이다. 식을 바꾸는 방법은 여러 가지인데, 근 근처에서 \(g\)의 기울기의 절댓값이 1보다 작으면 오차가 매번 그 비율로 줄어 수렴하고, 1보다 크면 발산한다. 계산은 단순하지만 수렴이 느리다(선형 수렴).
예시로 보기
\(f(x) = e^{-x} - x = 0\)은 \(x = e^{-x}\)로 바꿀 수 있다. \(x_0 = 0\)에서 되풀이한다.
| \(i\) | \(x_i\) | \(\lvert\epsilon_a\rvert\) (%) | \(\lvert\epsilon_t\rvert\) (%) |
|---|---|---|---|
| 0 | 0 | 100.0 | |
| 1 | 1.000000 | 100.0 | 76.3 |
| 2 | 0.367879 | 171.8 | 35.1 |
| 3 | 0.692201 | 46.9 | 22.1 |
| 4 | 0.500473 | 38.3 | 11.8 |
| 10 | 0.564879 | 1.11 | 0.399 |
근(0.56714329)의 양쪽을 오가며 다가간다. 오차는 매번 약 0.567배로 준다. 근에서 \(g'(x) = -e^{-x}\)의 절댓값이 \(e^{-0.567} \approx 0.567\)이기 때문이다1.
곡선 \(y = e^{-x}\)에서 값을 읽고(세로로), 직선 \(y = x\)에서 그 값을 다음 입력으로 옮기는(가로로) 일을 되풀이한 그림이다. 사각형이 근을 감싸며 점점 작아진다. 근의 양쪽을 번갈아 오가는 것이 보인다2.
정의
\(f(x) = 0\)을 \(x\)가 왼쪽에 오도록 \(x = g(x)\)로 바꾸고, 시작값 \(x_0\)에서 다음을 되풀이한다.
\[x_{i+1} = g(x_i)\]바꾸는 방법은 여러 가지다. \(x^2 - x - 2 = 0\)(\(x > 0\), 근 2)은 \(g(x) = x^2 - 2\), \(\sqrt{x + 2}\), \(1 + \frac2x\) 등으로 쓸 수 있다. \(\sin x = 0\)은 양변에 \(x\)를 더해 \(x = \sin x + x\)로 쓴다. 시작값과 바꾼 꼴에 따라 발산할 수도 있다.
flowchart TD
A["f(x) = 0"] --> B["x = g(x) 꼴 하나 고르기"]
B --> C["시작값 x0"]
C --> D["x_i+1 = g(x_i)"]
D --> E{"εa가 허용 오차 이하인가?"}
E -->|"예"| Y["x_i+1을 근으로"]
E -->|"아니오"| F{"값이 점점 멀어지나?"}
F -->|"아니오"| D
F -->|"예"| B
멀어지면 같은 식을 더 돌려도 소용없다. 식을 다른 \(g\)로 바꾸는 갈래로 돌아간다3.
근 근처에서 \(\vert g'(x)\vert < 1\)이면 고정점 반복은 수렴한다. 이때 오차는 대략 앞 오차에 비례해(그 이하로) 줄어든다. 그래서 선형 수렴이라 한다.
이유
근 \(r\)은 \(r = g(r)\)이다. 빼면 \(x_{i+1} - r = g(x_i) - g(r) = g'(\xi)(x_i - r)\)인 \(\xi\)가 \(x_i\)와 \(r\) 사이에 있다(평균값 정리). 그래서 오차는 매번 \(\vert g'(\xi)\vert\)배가 된다. 이 값이 1보다 작으면 오차가 0으로 간다.
\(x^2 - x - 2 = 0\)의 세 꼴을 근 2에서 보면 \(g(x) = x^2 - 2\)는 \(g'(2) = 4\)라 발산하고, \(\sqrt{x + 2}\)는 \(\frac14\), \(1 + \frac2x\)는 \(-\frac12\)라 수렴한다. \(g'\)이 음수이면 근의 양쪽을 번갈아 오간다1.
왼쪽 \(g(x) = x^2 - 2\)는 근 바로 옆 2.1에서 시작해도 한 번마다 근에서 크게 멀어진다. 오른쪽 \(g(x) = 1 + \frac2x\)는 1에서 시작해 근 2의 양쪽을 번갈아 오가며 다가간다2.
연립 비선형 방정식
\(u(x, y) = x^2 + xy - 10 = 0\), \(v(x, y) = y + 3xy^2 - 57 = 0\)(참값 \(x = 2\), \(y = 3\))을 \(x = g_1(x, y)\), \(y = g_2(x, y)\)로 바꾼다. 꼴이 여러 가지다.
- 방법 i: \(x = \frac{10 - x^2}{y}\), \(y = 57 - 3xy^2\). \((1.5, 3.5)\)에서 \(x_1 = 2.21429\), \(y_1 = -24.375\), \(x_2 = -0.2091\), \(y_2 = 429.71\)로 발산한다.
- 방법 ii: \(x = \sqrt{10 - xy}\), \(y = \sqrt{\frac{57 - y}{3x}}\). \(x_1 = 2.17945\), \(y_1 = 2.86051\), \(x_2 = 1.94053\), \(y_2 = 3.04955\)로 수렴한다.
두 방법 모두 \(y\)를 고칠 때 방금 구한 새 \(x\)를 쓴다(가우스-자이델과 같은 방식). 수렴의 충분조건은 근 근처에서 다음과 같다.
\[\left\vert \frac{\partial g_1}{\partial x}\right\vert + \left\vert \frac{\partial g_1}{\partial y}\right\vert < 1, \qquad \left\vert \frac{\partial g_2}{\partial x}\right\vert + \left\vert \frac{\partial g_2}{\partial y}\right\vert < 1\]1차원 조건 \(\vert g'(x)\vert < 1\)을 두 변수로 넓힌 것이라, 편미분은 원래 함수 \(u\), \(v\)가 아니라 반복 함수 \(g_1\), \(g_2\)의 것이다. \(u = x^2 + xy - 10\)으로 재면 근 \((2, 3)\)에서 \(\left\vert \frac{\partial u}{\partial x}\right\vert + \left\vert \frac{\partial u}{\partial y}\right\vert = 7 + 2 = 9\)라, 어떤 반복 함수를 고르든 이 조건은 맞을 수 없다.
이 조건은 충분조건일 뿐이다. 방법 ii는 근에서 \(\vert \partial g_1/\partial x\vert + \vert \partial g_1/\partial y\vert = 0.75 + 0.5 = 1.25\)로 조건을 만족하지 않는데도 수렴했다1.
활용
- 계산이 단순해 다른 방법의 바탕이 된다. 야코비·가우스-자이델 반복, PageRank의 거듭제곱법, 뉴턴 방법 자체도 \(g(x) = x - f(x)/f'(x)\)인 고정점 반복이다1.
- 흔한 실수: 처음 떠오른 \(g\)를 그대로 쓰는 것. \(g'\)의 크기를 근 근처에서 확인하고, 1보다 크면 식을 다르게 바꾼다.
연결
- 선수: 이분법(근 찾기의 틀), 평균값 정리(수렴 이유)
- 연립 일차방정식의 고정점 반복: 야코비 방법과 가우스-자이델 방법
- 더 빠른 연립 비선형 풀이: 다변수 뉴턴 방법
확인 문제
C1 고정점 반복의 갱신식과 수렴 조건을 쓰라. 왜 “선형 수렴”이라 하나?
답: \(x_{i+1} = g(x_i)\), 근 근처에서 \(\vert g'(x)\vert < 1\). 오차가 매번 약 \(\vert g'(r)\vert\)배, 곧 앞 오차에 비례해 줄기 때문이다.
C2 \(g(x) = \cos x\), \(x_0 = 0\)으로 두 번 반복하라.
답: \(x_1 = \cos0 = 1\), \(x_2 = \cos1 \approx 0.5403\).
C3 \(x^2 - x - 2 = 0\)을 \(x = x^2 - 2\)로 바꾸면 근 2 바로 옆에서 시작해도 발산하는 이유는?
답: \(g'(x) = 2x\)라 \(g'(2) = 4\)다. 근 근처에서 오차가 매번 약 4배로 불어난다. 평균값 정리로 \(x_{i+1} - 2 = g'(\xi)(x_i - 2)\)이기 때문이다.
C4 연립 고정점 반복의 수렴 조건(편미분 절댓값 합 < 1)을 만족하지 않는데도 수렴하는 예를 들라.
답: 방법 ii, \(g_1 = \sqrt{10 - xy}\). 근 \((2, 3)\)에서 \(\vert \partial g_1/\partial x\vert + \vert \partial g_1/\partial y\vert = 0.75 + 0.5 = 1.25 > 1\)인데 \((1.5, 3.5)\)에서 수렴한다. 조건은 충분조건이지 필요조건이 아니다.