뉴턴 방법(Newton's method)
곡선을 접선(tangent line)으로 바꿔 그 접선의 0점으로 건너뛰기를 되풀이해 근을 찾는다. 복소평면(complex plane)에서 돌리면 확대해도 끝없이 복잡한 경계(프랙털, fractal)가 나온다.
곡선의 0점을 바로 찾기는 어렵지만, 직선의 0점은 쉽습니다. 그래서 국소 선형성(local linearity)을 이용합니다. 곡선을 지금 위치의 접선으로 바꾸고, 접선이 x축과 만나는 곳으로 건너뜁니다. 출발점을 끌고, 그림 아래 단추로 반복을 한 번씩 진행해 보세요.
근에 가까워지면 오차가 매번 제곱에 비례해 줄어듭니다(0.01 → 0.0001 → 0.00000001 정도). 그래서 맞는 자릿수가 대략 두 배씩 늘어납니다. 여기에는 조건이 있습니다. f가 매끄럽고 근에서
1669년 무렵 뉴턴이 다항식(polynomial)의 근을 구하며 쓴 방법을 1690년 영국의 조지프 랩슨이 더 간단한 반복 꼴로 발표해서, '뉴턴–랩슨 방법(Newton–Raphson method)'이라고도 부릅니다. 도함수(derivative function)로 적은 위의 식처럼 일반 함수(function)에 쓰는 형태는 1740년 토머스 심프슨이 내놓았습니다.
같은 반복을 복소평면에서
경계 어디를 확대해도 세 색이 모두 만납니다. 두 색만 맞닿은 경계선은 한 군데도 없습니다. 이렇게 어디를 확대해도 복잡한 구조가 계속 나타나는 도형을 흔히 프랙털이라 하고, 칸토어 집합(Cantor set)이 단순한 예입니다. 단순한 반복 규칙에서 프랙털이 나오는 또 다른 예가 망델브로 집합(Mandelbrot set)입니다. 이런 그림은 도메인 컬러링(domain coloring)에 반복을 더해 그립니다.
최솟값을 찾을 때는 도함수의 0점에 뉴턴 방법을 쓰면 됩니다. 그러려면 도함수를 한 번 더 미분(differentiation)한 이계 도함수(second derivative), 곧 곡선이 휘는 정도까지 계산해야 합니다. 변수가 n개이면 이계 도함수는 n×n개의 수로 된 표가 되어, 변수가 수백만 개인 신경망(neural network)에서는 너무 비쌉니다. 그래서 신경망 학습에는 주로 기울기(slope)만 보고 내리막으로 조금씩 걷는 경사 하강법(gradient descent)을 씁니다. 한 걸음에 드는 계산이 훨씬 적기 때문입니다. 실제로는 기울기마저 자료 전체 대신 무작위로 뽑은 일부로 어림하는 확률적 경사 하강법(stochastic gradient descent)이 쓰입니다.
뉴턴 방법은 규칙
이 개념이 나오는 긴 글
이 개념을 언급하는 페이지
- 미분계수
… 은 x = 0 에서 기울기가 0이지만 계속 오릅니다). 접선을 따라 건너뛰며 방정식의 근을 찾는 것이뉴턴 방법입니다. 미분할 수 있으면 연속이지만 그 반대는 아닙니다. |x| 는 x = 0 에서 끊기지 않지만 …
- 국소 선형성
… 정해지지 않고, 미분할 수 없습니다. 국소 선형성은 계산법이 됩니다. 곡선 대신 접선의 0점으로 건너뛰는뉴턴 방법이 그 하나입니다. 두 함수를 합성하면(한 함수의 출력을 다른 함수에 넣으면) 확대 배율(미분계수)이 …
- 중간값 정리
… 약 3.3번 해야 1/10이 되기 때문입니다( \log_{10} 2 \approx 0.3 ). 접선을 쓰는뉴턴 방법은 근 근처에서 훨씬 빠르지만, 이분법은 연속함수에서 부호가 다른 두 점만 있으면 절대 실패하지 않습니다. …
- 최적화
… 5/3 일 때의 2000/27 \approx 74.1 입니다. 식으로 풀리지 않는 문제라면 V' 의 0점을뉴턴 방법이나 이분법으로 찾으면 됩니다. 최적화는 수학 곳곳에 숨어 있습니다. 최소제곱 회귀는 오차 제곱의 …
- 도메인 컬러링
… 확대해도 복잡한 무늬가 계속 나타나는 프랙털이 보입니다(칸토어 집합이 단순한 프랙털의 예입니다).뉴턴 방법의 수렴 영역과 망델브로 집합이 이렇게 그려집니다.
- 영점과 극
… zⁿ − 1의 영점들은 원 위에 고르게 놓인 1의 거듭제곱근입니다. 영점을 찾는 반복법인뉴턴 방법을 복소평면에서 돌리면 각 영점으로 끌려가는 영역들의 경계가 어디를 확대해도 끝없이 복잡한 프랙털이 …
- 망델브로 집합
… 도메인 컬러링과 같은 방식에 반복만 더했습니다. 반복이 어디로 끌려가는지로 평면을 칠하는 그림은뉴턴 방법에서도 나타납니다. 뉴턴 방법을 되풀이하면 출발점마다 어느 근으로 끌려가는지가 정해지는데, 같은 근으로 …
- 1의 거듭제곱근
… 1805년 무렵 같은 방법을 써 두었다는 사실이 뒤에 밝혀졌습니다. 또 z^3 = 1 의 세 근은뉴턴 방법을 복소평면에서 돌린 그림, 곧 어디를 확대해도 경계가 끝없이 복잡한 프랙털 그림에서 세 색의 중심이 …
- 대수적 수와 초월수
… 추측을 나머지 추측들을 참고해 동시에 고치기를 되풀이하는 반복법입니다. 추측을 조금씩 고쳐 근에 다가가는뉴턴 방법과 같은 생각입니다. 대수적 수가 차지하는 \aleph_0 와 실수 전체의 2^{\aleph_0} 사이에 …
- 로지스틱 사상
… 미분계수만큼 곱해집니다. 오차가 등비수열을 이루는 셈입니다. |f'(x^*)| 입니다. |2 - r|뉴턴 방법도 같은 원리로 움직이는 되풀이입니다. 뉴턴 방법의 한 걸음을 규칙 g로 보면 찾는 근이 g의 고정점인데, …
- 경사 하강법
… 함수⟧)라면 극소가 곧 최소라서, 이때는 가장 낮은 곳에 다가간다고 말할 수 있습니다. 곡률까지 쓰는뉴턴 방법은 이차함수라면 한 걸음에 바닥에 닿지만, 변수가 n개면 n × n 헤세 행렬을 만들고 연립방정식을 풀어야 …
- 역전파
… 수 없었고, 매끄러운 활성화 함수가 그 문을 열었습니다. 기울기로 한 걸음씩 내려가는 대신 곡률까지 쓰는뉴턴 방법은 두 번 미분이 필요해 큰 신경망에서는 거의 쓰지 않습니다.
- 이진 탐색
… 이분법이 됩니다. 부호가 바뀌는 구간을 반씩 잘라 근을 찾는 것으로, 한 번에 한 비트씩 정확해집니다.뉴턴 방법은 접선을 써서, 근에서 기울기가 0이 아니면 근에 충분히 가까워진 뒤로 맞는 자릿수를 매번 두 배쯤으로 …
- 다항식
… 선형 미분방정식의 해도 특성방정식의 근이 정합니다. 근을 수치로 찾는 대표적인 방법은뉴턴 방법이고, 정수 계수 다항식의 근이 되는 수가 대수적 수입니다. xⁿ − 1의 근은 ⟦1의 …
- 고정점
… 걸음마다 대략 두 배로 늘어납니다. x²의 고정점 0이 그렇고(1에서는 f′ = 2라 밀어냅니다),뉴턴 방법이 빠른 이유도 이것입니다. 뉴턴 방법은 N(x) = x - g(x)/g'(x) 를 되풀이해 N의 고정점, …
- 근사 이론
… 전체에서 한꺼번에 다가간다는 말의 정확한 뜻은 점별 수렴과 균등 수렴에 있습니다. 근을 찾는 반복법은뉴턴 방법에 있습니다. 가장 큰 오차를 가장 작게 하는 문제는 선형 계획법으로도 풀 수 있고, ⟦가장 좋은 것 …
- 동역학계
… 미래입니다. 이렇게 이어지는 상태들을 궤도라 합니다. 점화식, 로지스틱 사상, 방정식의 근을 찾는뉴턴 방법, 웹 페이지의 순위를 매기는 페이지랭크의 반복 계산이 모두 이 꼴입니다. 연속 동역학계 에서는 시간이 …
- 로지스틱 회귀
… 볼록 함수이고, 볼록 함수에서는 기울기가 0인 곳이 곧 가장 낮은 곳입니다. 그래서 경사 하강법이든뉴턴 방법이든 엉뚱한 골짜기에 갇히지 않습니다. 둘째 그림은 (w, b) 평면에 그린 L의 등고선이고, 흰 점들은 …
- 기울기 벡터와 야코비 행렬
… 것입니다. 이차 근사의 바닥으로 한 번에 건너뛰는 걸음 -H^{-1}\nabla f 를 되풀이하는 것이뉴턴 방법입니다. 신경망 속의 야코비 행렬. 층 하나 \vec y = \sigma(W\vec x + \vec b) …
- 자동 미분
… 이르는 가중치 하나하나에 대해 '이 수를 조금 바꾸면 손실이 얼마나 변하나'를 알아야 합니다. 방정식을뉴턴 방법으로 풀 때도 같은 종류의 값이 필요합니다. 이런 변화율을 주는 함수가 도함수입니다. 컴퓨터는 도함수의 …