지금까지 이 단원의 문제들은 모두 을 손으로 풀 수 있었습니다. 이나 은 인수분해나 이항으로 정리됩니다.
그런데 그것은 문제를 그렇게 골랐기 때문입니다. 조금만 벗어나면 사정이 달라집니다. 의 해를 근의 공식 같은 것으로 적을 방법은 없습니다. 도 마찬가지이고, 실제로 5차 이상의 일반 방정식에는 근의 공식이 존재하지 않는다는 것이 증명되어 있습니다.
손으로 풀리지 않는 방정식이 오히려 정상입니다. 그러면 어떻게 해야 하는가. 답을 정확히 적는 것을 포기하고 원하는 만큼 가까운 근삿값을 얻는 절차를 만듭니다. 그것이 이 강의의 주제입니다.
이 강의가 이 단원에서 특별한 이유가 있습니다. 지금까지 미분은 함수의 성질을 알아내는 분석 도구였는데, 여기서는 답을 계산해 내는 알고리즘이 됩니다. 접선을 긋고 그 접선의 근으로 옮겨 가기를 반복하는 것이 전부입니다. 109강의 경사하강법과 112강의 뉴턴법도 정확히 같은 발상이므로, 이 강의는 그쪽으로 가는 문입니다.
문제. 의 양의 근, 즉 를 구하려 합니다.
(1) 에서 의 접선을 구하세요.
(2) 그 접선이 축과 만나는 점 을 구하세요.
(3) 일반적으로 에서 같은 일을 할 때 의 식을 세우세요.
생각의 실마리. 곡선의 근을 직접 구하기 어려우면 곡선을 직선으로 바꿔 봅니다. 37강에서 접선이 그 점 근처에서 함수를 가장 잘 흉내 내는 직선이라고 배웠습니다. 직선의 근은 언제나 쉽게 구해집니다. 그 근이 원래 곡선의 근에 가까울 것이라 기대하는 것이 출발점입니다.
풀이. (1) 이고 이므로 입니다. 접선은
입니다.
(2) 에서 이므로 입니다. 참값 에 상당히 가까워졌습니다.
(3) 에서의 접선은
입니다. 으로 두고 에 대해 풀면
이고 이것을 로 삼습니다.
이 문제에서 배우는 것: 뉴턴법.
뉴턴법. 의 근을 찾기 위해 초기값 에서 출발해
을 반복합니다. 단 이어야 합니다.
이 식이 하는 일을 말로 옮기면 이렇습니다. 현재 위치에서 곡선을 접선으로 바꿔치기하고, 그 직선의 근으로 이동합니다. 곡선의 근은 못 구해도 직선의 근은 늘 구할 수 있다는 점을 이용합니다.
에 적용하면 특히 유명한 식이 나옵니다.
현재 추정값과 의 평균을 취하는 것입니다. 이 보다 작으면 이 크고, 크면 그 반대이므로 참값이 둘 사이에 있습니다. 그 중간을 취하니 가까워집니다. 이 방법은 뉴턴보다 훨씬 오래되어 바빌로니아 시대부터 알려져 있었습니다.
, 로 몇 번 계산해 봅니다.
| x_ | 오차 | |
|---|---|---|
| 4.14\times 10^ | ||
| 8.58\times 10^ | ||
| 2.45\times 10^ | ||
| 2.12\times 10^ | ||
| 1.59\times 10^ |
정확한 자릿수가 매번 대략 두 배가 됩니다. 이 현상을 이차 수렴이라 부르며 문제 5와 심화 1에서 이유를 밝힙니다.
바로 확인 1.
확인 1-1. 에 뉴턴법을 적용한 반복식을 쓰세요.
답. 입니다.
확인 1-2. 에 뉴턴법을 적용한 반복식을 정리해 쓰세요.
답. 입니다.
확인 1-3. 뉴턴법에서 이면 무슨 일이 생기는지 쓰세요.
답. 분모가 이 되어 다음 값을 계산할 수 없습니다. 기하학적으로는 접선이 수평이라 축과 만나지 않기 때문입니다.
문제. 의 근을 뉴턴법으로 구합니다. 에서 출발합니다.
(1) 근이 존재하고 유일함을 보이세요.
(2) 과 를 계산하세요.
(3) 반복을 언제 멈출지 정하는 기준을 세우세요.
생각의 실마리. (1)은 계산이 아니라 정리를 쓰는 문제입니다. 존재는 36강의 중간값 정리로, 유일성은 43강의 증가 판정법으로 처리합니다. 근이 있는지 확인하지 않고 반복부터 돌리면 아무 데도 도달하지 못할 수 있습니다. (3)에서는 참값을 모르는 상태에서 오차를 어떻게 가늠할지 생각합니다.
풀이. (1) 이고 입니다. 가 연속이므로 중간값 정리에 의해 에 근이 있습니다.
이고 이 되는 점은 인 고립된 점들뿐이므로, 43강 심화 1에 의해 는 실수 전체에서 순증가합니다. 순증가하는 함수는 같은 값을 두 번 취하지 않으므로 근은 하나뿐입니다.
(2) 입니다.
참값은 이므로 두 번 만에 소수 넷째 자리까지 맞았습니다.
(3) 참값을 모르므로 연속한 두 추정값의 차이를 봅니다. 이 원하는 정밀도보다 작아지면 멈춥니다. 함숫값 이 충분히 작은지도 함께 확인하면 더 안전합니다.
이 문제에서 배우는 것: 반복법의 세 가지 준비.
수치적 방법을 쓰기 전에 반드시 확인할 것이 있습니다.
| 항목 | 확인 방법 | 이 문제에서 |
|---|---|---|
| 근의 존재 | 중간값 정리(36강) | 입니다 |
| 근의 개수 | 증가·감소 판정(43강) | 순증가이므로 하나뿐입니다 |
| 초기값 | 근 근처를 고릅니다 | 이 구간 안에 있습니다 |
존재를 확인하지 않고 반복하면 위험합니다. 처럼 실근이 없는 함수에 뉴턴법을 돌리면 값이 끝없이 떠돌 뿐 아무 데도 도달하지 않습니다.
정지 조건도 형식이 아닙니다. 세 가지 방식이 있고 각각 결함이 있습니다.
| 정지 조건 | 뜻 | 약점 |
|---|---|---|
| 더 이상 움직이지 않습니다 | 수렴이 느리면 일찍 멈춥니다 | |
| 함숫값이 거의 입니다 | 기울기가 완만하면 근에서 멀어도 통과합니다 | |
| 반복 횟수 상한 | 무한 루프를 막습니다 | 답을 보장하지 않습니다 |
실무에서는 세 조건을 모두 함께 씁니다. 앞의 둘은 정확도를 위한 것이고 마지막은 실패했을 때 빠져나오기 위한 것입니다.
한 가지 더 알아 둘 것이 있습니다. 부동소수점에서는 어느 순간 값이 더 이상 개선되지 않고 마지막 비트에서 미세하게 흔들립니다. 검산에서 실제로 확인하는데, 의 반복이 다섯 번째에서 정확한 값에 도달했다가 여섯 번째에 마지막 자리 하나만큼 어긋납니다. 이는 알고리즘의 결함이 아니라 유한한 자릿수의 한계이며, 정지 조건이 필요한 실질적인 이유입니다.
바로 확인 2.
확인 2-1. 의 실근이 에 존재함을 보이세요.
답. 이고 입니다. 가 연속이므로 중간값 정리에 의해 그 사이에 근이 있습니다.
확인 2-2. 정지 조건으로 만 쓰면 위험한 이유를 쓰세요.
답. 기울기가 완만한 함수에서는 근에서 멀리 떨어져도 함숫값이 작을 수 있어 잘못된 값을 답으로 받아들이게 되기 때문입니다.
확인 2-3. 뉴턴법을 돌리기 전에 근의 존재를 확인해야 하는 이유를 쓰세요.
답. 근이 없으면 반복이 수렴할 곳이 없어 값이 끝없이 떠돌기 때문입니다.
문제. 다음 세 경우에 뉴턴법이 어떻게 되는지 조사하세요.
(1) 에 을 넣습니다.
(2) 에 을 넣습니다.
(3) 에 을 넣습니다.
생각의 실마리. 반복식을 그대로 몇 번 계산해 봅니다. (1)에서는 두어 번만 계산해도 무언가 이상한 것이 보입니다. (2)는 일반항을 구할 수 있을 만큼 식이 단순해지므로 정리해 봅니다. (3)은 계산하기 전에 의 값을 확인합니다.
풀이. (1) 입니다. 에서 이고 이므로
입니다. 에서 이고 이므로
입니다. 으로 돌아왔습니다. 이후 을 끝없이 반복하며 근에 다가가지 않습니다.
(2) 이므로
입니다. 매번 부호가 바뀌면서 크기가 두 배가 됩니다. 에서 시작하면 으로 근 에서 점점 멀어집니다.
(3) 이므로 분모가 이 되어 을 계산할 수 없습니다. 접선이 수평이라 축과 만나지 않습니다.
이 문제에서 배우는 것: 뉴턴법의 실패 방식.
세 가지를 표로 모읍니다.
| 실패 방식 | 원인 | 예 |
|---|---|---|
| 순환 | 두 점 사이를 오갑니다 | , |
| 발산 | 근에서 멀어집니다 | , 임의의 |
| 정지 | 입니다 | , |
이 밖에 다른 근으로 수렴하는 경우도 있습니다. 근이 여러 개일 때 초기값에 따라 어느 근에 도달할지가 정해지는데, 그 경계가 대단히 복잡해질 수 있습니다. 복소평면에서 에 뉴턴법을 적용하면 세 근의 수렴 영역 경계가 프랙탈이 되며, 뉴턴 프랙탈이라 불립니다.
그러므로 뉴턴법의 성질을 정확히 말해야 합니다.
뉴턴법은 근 근처에서 출발하면 매우 빠르지만, 멀리서 출발하면 아무것도 보장하지 않습니다.
이런 성질을 국소 수렴이라 합니다. 43강과 44강에서 본 "판정법은 충분조건만 준다"와 같은 성격의 제한입니다.
(2)의 실패에는 짚어 둘 점이 있습니다. 은 근 에서 접선이 수직이라 미분되지 않습니다. 함수가 근에서 매끄럽지 않으면 접선 근사라는 발상 자체가 무너집니다. 뉴턴법이 잘 작동하려면 근 근처에서 이 에서 떨어져 있고 이 유계여야 하며, 그 조건이 심화 1의 수렴 정리에 그대로 나타납니다.
실무에서는 이 위험을 이렇게 다룹니다.
| 대책 | 내용 |
|---|---|
| 초기값을 잘 고릅니다 | 이분법으로 대략 위치를 잡고 넘깁니다 |
| 이동 폭을 제한합니다 | 한 걸음이 너무 크면 줄입니다 |
| 구간을 벗어나면 되돌립니다 | 이분법과 섞은 혼합법을 씁니다 |
| 반복 횟수에 상한을 둡니다 | 순환과 발산에서 빠져나옵니다 |
바로 확인 3.
확인 3-1. 에 을 넣으면 왜 순환하는지 계산으로 보이세요.
답. 이고 이므로 두 값을 오갑니다.
확인 3-2. 에서 뉴턴 반복식이 이 되는 과정을 쓰세요.
답. 이므로 입니다.
확인 3-3. 뉴턴법이 국소 수렴한다는 말의 뜻을 쓰세요.
답. 근에 충분히 가까운 곳에서 출발하면 수렴이 보장되지만, 먼 곳에서 출발하면 수렴 여부를 보장하지 못한다는 뜻입니다.
문제. 가 에서 연속이고 이라 합니다.
(1) 구간을 반으로 나누어 근이 있는 쪽을 고르기를 반복하는 방법을 설명하고 근거가 되는 정리를 쓰세요.
(2) 번 반복한 뒤 오차의 상한을 구하세요.
(3) 에서 오차 를 얻으려면 몇 번 반복해야 합니까?
(4) 뉴턴법과 비교하세요.
생각의 실마리. (1)에서 근이 어느 쪽 반에 있는지는 부호로 판정합니다. 양 끝의 부호가 다르면 그 사이에 근이 있다는 것이 36강의 결론이었습니다. (2)에서는 구간 길이가 매번 어떻게 변하는지 보면 등비수열이 나옵니다.
풀이. (1) 중점 에서 의 부호를 봅니다. 이면 근이 에 있으므로 그쪽을 새 구간으로 삼고, 아니면 를 택합니다. 근거는 36강의 중간값 정리입니다. 연속함수의 양 끝 부호가 다르면 그 사이에 반드시 근이 있습니다.
(2) 구간 길이가 매번 절반이 되므로 번 뒤의 길이는 입니다. 근은 그 구간 안에 있고 우리가 답으로 내놓는 값은 중점이므로, 오차는 그 절반 이하입니다.
(3) 이므로 입니다. 에서
이므로 번입니다.
(4) 문제 2에서 같은 방정식에 뉴턴법을 쓰면 네 번만에 배정밀도의 한계에 도달합니다. 이분법은 번이 필요합니다.
이 문제에서 배우는 것: 안전성과 속도의 맞바꿈.
두 방법을 정면으로 비교합니다.
| 이분법 | 뉴턴법 | |
|---|---|---|
| 필요한 것 | 부호가 다른 두 점 | 초기값 하나와 |
| 수렴 보장 | 항상 합니다 | 근 근처에서만 합니다 |
| 속도 | 한 번에 한 비트 | 한 번에 자릿수가 두 배 |
| 반복당 비용 | 한 번 | 와 각각 한 번 |
| 실패 방식 | 없습니다 | 순환, 발산, 정지 |
| 근거 정리 | 중간값 정리(36강) | 접선 근사(37강) |
이분법이 매번 정확히 한 비트씩 얻는다는 표현은 정확합니다. 구간이 절반이 되면 이진수로 한 자리가 확정되기 때문입니다. 느리지만 예측 가능하고 절대 실패하지 않습니다.
뉴턴법은 반대입니다. 빠르지만 보장이 없습니다. 그래서 실무의 표준은 둘을 섞는 것입니다.
혼합 전략. 이분법으로 구간을 충분히 좁혀 근의 위치를 대략 잡은 뒤, 그 값을 초기값으로 뉴턴법에 넘깁니다. 뉴턴법이 구간을 벗어나려 하면 그 걸음을 버리고 이분법 한 걸음으로 대체합니다.
이 방식이면 이분법의 보장과 뉴턴법의 속도를 함께 얻습니다. 실제 수치 라이브러리의 근 찾기 함수는 대개 이런 구조입니다.
이 맞바꿈은 수치 계산 전반에서 반복되는 주제입니다. 빠른 방법은 조건이 까다롭고 안전한 방법은 느립니다. 109강에서 경사하강법과 뉴턴법을 비교할 때 같은 구도가 다시 나오며, 그때는 안전성 대신 계산 비용이 논점이 됩니다.
바로 확인 4.
확인 4-1. 에서 이분법으로 오차 을 얻으려면 몇 번 반복해야 합니까?
답. 에서 이므로 번입니다.
확인 4-2. 이분법이 항상 수렴하는 근거가 되는 정리는 무엇입니까?
답. 36강의 중간값 정리입니다. 양 끝의 부호가 다르면 반드시 그 사이에 근이 있으므로 매번 근을 품은 구간을 유지할 수 있습니다.
확인 4-3. 이분법과 뉴턴법을 섞어 쓰는 이유를 쓰세요.
답. 이분법으로 수렴을 보장하고 뉴턴법으로 속도를 얻기 위해서입니다. 뉴턴법이 구간을 벗어나면 이분법 한 걸음으로 대체합니다.
문제. 뉴턴 반복을 함수 의 되풀이로 봅니다. 근을 이라 합니다.
(1) 임을 확인하세요.
(2) 를 구하고 의 값을 계산하세요.
(3) (2)의 결과가 수렴 속도에 대해 무엇을 말해 줍니까?
생각의 실마리. 반복법을 같은 함수를 계속 먹이는 과정으로 보면 근은 그 함수의 고정점입니다. 고정점 근처에서 오차가 어떻게 변하는지는 그 함수의 도함수가 정합니다. (2)는 몫의 미분법(38강)을 쓰는 계산이며, 이라는 사실이 마지막에 결정적으로 쓰입니다.
풀이. (1) 이므로
입니다. 근은 의 고정점입니다. 즉 한 번 근에 도달하면 그 뒤로 움직이지 않습니다.
(2) 를 미분합니다. 몫의 미분법으로
입니다. 정리하면
이고, 에서 이므로 인 한
입니다.
(3) 오차를 이라 하면 이고 이므로
입니다. 42강의 평균값 정리를 쓰면 어떤 가 과 사이에 있어 입니다.
일반적인 반복법에서는 이므로 이 되어 오차가 일정 비율로만 줄어듭니다. 그런데 뉴턴법은 이므로 가 에 가까워질수록 도 에 가까워집니다. 줄어드는 비율 자체가 점점 좋아지므로 훨씬 빠릅니다.
이 문제에서 배우는 것: 수렴 차수.
반복법의 속도를 등급으로 나눕니다.
수렴 차수. 가 성립할 때 를 수렴 차수라 합니다. 이면 일차 수렴(선형), 이면 이차 수렴입니다.
| 방법 | 차수 | 뜻 |
|---|---|---|
| 이분법 | (비율 ) | 한 번에 한 비트를 얻습니다 |
| 뉴턴법 (단순근) | 정확한 자릿수가 두 배가 됩니다 | |
| 뉴턴법 (중근) | 심화 2에서 다룹니다 | |
| 할선법 | 심화 6에서 다룹니다 |
뉴턴법이 이차인 이유를 더 정확히 적으면 이렇습니다. 이므로 를 근처에서 이차까지 펼치면 일차항이 사라지고
가 됩니다. 오차가 제곱으로 줄어드니 유효숫자가 두 배가 됩니다. 이 전개의 엄밀한 근거는 57강의 테일러 정리이므로, 여기서는 이라는 확실한 사실까지만 증명하고 제곱 관계는 그때 완성합니다.
상수 의 모양도 읽어 둘 값이 있습니다. 이 에 가까우면 상수가 커져 수렴이 나빠집니다. 중근에서 뉴턴법이 느려지는 이유가 여기 있고, 그것이 심화 2의 주제입니다.
바로 확인 5.
확인 5-1. 뉴턴 사상 에 대해 인 이유를 쓰세요.
답. 이므로 빼는 항 이 이 되어 이기 때문입니다.
확인 5-2. 에서 이 나오는 이유를 쓰세요.
답. 분자에 가 인수로 들어 있는데 이고 분모 은 이 아니기 때문입니다.
확인 5-3. 오차가 일 때 이차 수렴이면 다음 오차의 크기를 어림하세요.
답. 대략 정도입니다. 상수가 근처라면 오차의 제곱이 되기 때문입니다.
| 방법 | 반복식 | 근거 |
|---|---|---|
| 뉴턴법 | 접선 근사(37강) | |
| 제곱근 | 입니다 | |
| 세제곱근 | 입니다 | |
| 역수 | 입니다 | |
| 이분법 | 부호가 바뀌는 쪽 반을 택합니다 | 중간값 정리(36강) |
| 할선법 | 두 점을 잇는 직선 |
| 항목 | 뉴턴법 | 이분법 |
|---|---|---|
| 수렴 보장 | 국소적입니다 | 항상 합니다 |
| 수렴 차수 | (비율 ) | |
| 도함수 | 필요합니다 | 필요 없습니다 |
| 초기 조건 | 근 근처의 한 점 | 부호가 다른 두 점 |
| 실패 방식 | 신호 | 대책 |
|---|---|---|
| 순환 | 값이 되돌아옵니다 | 반복 상한을 둡니다 |
| 발산 | 값이 커집니다 | 이동 폭을 제한합니다 |
| 정지 | 입니다 | 초기값을 바꿉니다 |
| 중근 | 수렴이 느립니다 | 을 씁니다 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 근의 존재를 확인하지 않습니다 | 중간값 정리로 먼저 확인합니다 |
| 정지 조건을 하나만 씁니다 | 세 조건을 함께 씁니다 |
| 수렴했다고 단정합니다 | 의 크기도 확인합니다 |
| 초기값을 아무 데나 잡습니다 | 이분법으로 좁힌 뒤 넘깁니다 |
문제 6. 에 대한 뉴턴 반복식을 정리해 쓰세요.
답. 입니다.
문제 7. 문제 6에서 일 때 을 구하세요.
답. 입니다.
문제 8. 에 을 넣어 을 구하세요.
답. 이고 이므로 입니다. 입니다.
문제 9. 에 을 넣어 을 구하세요.
답. 이고 이므로 입니다. 입니다.
문제 10. 에서 이분법으로 오차 을 얻으려면 몇 번 반복해야 합니까?
답. 에서 이므로 번입니다.
문제 11. 의 근에 대한 뉴턴 반복식을 쓰세요.
답. 이므로 입니다.
문제 12. 에 뉴턴법을 적용하면 어떻게 되는지 판정하세요.
답. 실근이 없으므로 수렴할 곳이 없습니다. 반복값이 실수 위를 끝없이 떠돕니다.
문제 13. 뉴턴법의 오차가 에서 다음 단계에 대략 얼마가 되는지 어림하세요. 상수는 로 봅니다.
답. 이차 수렴이므로 대략 입니다.
문제 14. 의 근 에 대한 뉴턴 반복식을 쓰세요.
답. 이므로 입니다.
문제 15. 문제 14에서 일 때 을 구하세요.
답. 입니다.
문제 16. 이분법이 뉴턴법보다 나은 상황을 하나 쓰세요.
답. 도함수를 구할 수 없거나 근의 위치를 전혀 모를 때입니다. 부호가 다른 두 점만 있으면 반드시 수렴하기 때문입니다.
문제 17. 뉴턴 사상 에서 를 구하세요.
답. 입니다.
문제 18. 일 때 역수 를 구하는 뉴턴 반복식을 쓰고 를 넣어 을 구하세요.
답. 입니다. 이므로 이미 고정점입니다.
심화 1. 뉴턴법의 국소 수렴 정리를 서술하고, 문제 5의 결과로 증명의 뼈대를 세우세요.
풀이. 서술은 이렇습니다.
국소 수렴 정리. 가 근 을 포함하는 어떤 열린구간에서 두 번 연속미분가능하고 이라 합니다. 그러면 을 중심으로 하는 어떤 구간 가 있어, 에서 출발한 뉴턴 반복은 안에 머물며 로 수렴합니다.
증명의 뼈대는 문제 5의 계산에 있습니다. 이고 이 연속이므로, 어떤 이 있어 인 모든 에서
입니다. 로 둡니다.
라 하면 평균값 정리로 어떤 가 과 사이에 있어
입니다. 도 안에 있으므로 위의 부등식을 쓸 수 있습니다. 이 식이 두 가지를 한꺼번에 줍니다. 첫째, 이므로 도 안에 있어 반복이 구간을 벗어나지 않습니다. 둘째, 오차가 매 단계 절반 이하로 줄어드므로
이고 수렴합니다.
증명이 보장하는 것은 여기까지, 즉 일차 수렴입니다. 이차 수렴은 이라는 사실을 한 번 더 써서 얻어지며 57강의 테일러 정리가 필요합니다. 정리의 가정 두 가지가 문제 3의 실패 사례에 정확히 대응한다는 점을 확인해 두십시오. 은 에서 미분가능하지 않아 첫 가정이 깨지고, 에 을 넣은 경우는 이라 초기값이 밖에 있습니다.
심화 2. 가 에서 중근을 가질 때, 즉 이고 일 때 뉴턴법의 수렴이 어떻게 달라지는지 으로 확인하고, 개선된 반복식을 제시하세요.
풀이. 이면 이므로
입니다. 에서 이 되어 오차가 매번 정확히 절반씩만 줄어듭니다. 이차 수렴이 아니라 일차 수렴이고, 이분법과 같은 속도입니다.
이유는 문제 5의 계산에 있습니다. 을 쓰려면 이어야 하는데, 중근에서는 분자와 분모가 모두 이라 그 식을 쓸 수 없습니다. 직접 계산하면 이므로 입니다. 고정점의 도함수가 이 아니므로 일차 수렴입니다.
일반적으로 근의 중복도가 이면 이 되어, 이 클수록 에 가까워지고 수렴이 더 느려집니다.
개선책은 반복식을 고치는 것입니다.
수정 뉴턴법. 근의 중복도가 일 때
을 쓰면 이차 수렴이 회복됩니다.
에 를 넣으면 이 되어 한 걸음 만에 정확한 답에 도달합니다. 원래 뉴턴법이 걸음마다 절반씩만 가던 것과 대조적입니다.
실무에서 어려운 점은 을 미리 모른다는 것입니다. 그래서 에 뉴턴법을 적용하는 방법을 씁니다. 가 에서 중근이면 는 에서 단순근을 가지므로 중복도를 몰라도 이차 수렴이 회복됩니다.
심화 3. 나눗셈을 쓰지 않고 를 계산하는 뉴턴 반복식을 유도하고, 에 을 넣어 몇 걸음 계산하세요.
풀이. 가 근이 되는 함수를 고르되 뉴턴 반복식에 나눗셈이 남지 않도록 골라야 합니다. 을 쓰면 가 되어 로 나누게 되므로 목적에 어긋납니다.
를 씁니다. 이므로
즉
입니다. 곱셈과 뺄셈만 남았습니다.
, 으로 계산합니다.
| x_ | |
|---|---|
정확한 자릿수가 으로 정확히 두 배씩 늘어납니다. 이차 수렴이 이보다 선명하게 드러나는 예는 드뭅니다.
이 반복식은 실용적 가치가 큽니다. 나눗셈은 곱셈보다 훨씬 느린 연산이므로, 하드웨어에서 나눗셈을 구현할 때 실제로 이 방법을 씁니다. 를 계산하는 대신 를 뉴턴법으로 구하고 를 곱합니다. 초기값은 지수부를 이용해 표에서 가져오며, 배정밀도라면 서너 걸음이면 충분합니다.
심화 4. 문제 3의 순환 예 에서 을 조금만 바꾸면 어떻게 되는지 생각해 보고, 순환이 얼마나 불안정한 현상인지 논하세요.
풀이. 에서는 의 완전한 순환이 일어납니다. 그런데 이 순환은 정확히 그 두 점에서만 성립합니다.
순환이 유지되려면 이어야 합니다. 이 조건을 만족하는 점은 방정식의 해이므로 고립되어 있고, 따라서 을 아주 조금만 옮기면 조건이 깨집니다. 실제로 에서 시작하면 두 걸음 뒤에 정확히 로 돌아오지 않고 조금 어긋나며, 그 어긋남이 반복될수록 커져 결국 순환에서 벗어납니다.
여기서 두 가지를 구별해야 합니다.
| 관점 | 결론 |
|---|---|
| 이론적으로 | 순환하는 초기값은 존재하며 무시할 수 없습니다 |
| 실제 계산에서 | 부동소수점 오차 때문에 정확한 순환은 거의 일어나지 않습니다 |
그러니 실무에서 반복이 안 끝나는 이유는 대개 완전한 순환이 아니라 거의 순환하며 매우 느리게 움직이는 상태입니다. 반복 횟수 상한이 필요한 이유가 여기 있습니다. 순환인지 발산인지 느린 수렴인지 구별하지 않고 일단 빠져나온 뒤 다른 초기값으로 다시 시도하는 편이 실용적입니다.
이 관찰은 더 넓은 이야기로 이어집니다. 뉴턴법의 수렴 영역 경계는 매우 복잡하며, 그 경계 위의 점들이 바로 순환하거나 영원히 결정되지 않는 점들입니다. 경계가 프랙탈이 되는 이유이고, 이런 민감성은 231강 이후 동역학계와 혼돈을 다룰 때 다시 만납니다.
심화 5. 최적화 문제 를 푸는 데 뉴턴법을 어떻게 쓰는지 반복식을 세우고, 43강·44강의 판정법과 어떤 관계인지 설명하세요.
풀이. 43강에서 최적점의 필요조건이 이었습니다. 그러니 을 근 찾기의 대상 함수로 삼으면 됩니다. 뉴턴법의 자리에 을, 자리에 을 넣습니다.
이것이 최적화를 위한 뉴턴법입니다.
이 식이 하는 일을 기하학적으로 읽으면 이렇습니다. 근 찾기 뉴턴법이 함수를 접선으로 바꿔치기했다면, 여기서는 함수를 접하는 포물선으로 바꿔치기합니다. 그 포물선의 꼭짓점으로 이동하는 것이 위 식입니다.
44강의 판정법이 여기서 그대로 쓰입니다.
| 조건 | 결과 |
|---|---|
| 포물선이 위로 열려 꼭짓점이 최소이므로 올바른 방향입니다 | |
| 포물선이 아래로 열려 꼭짓점이 최대이므로 최댓값 쪽으로 갑니다 | |
| 계산할 수 없습니다 |
두 번째 줄이 중요합니다. 이 방법은 최솟값을 찾는 것이 아니라 인 점을 찾을 뿐입니다. 극대점도 극솟값과 똑같이 을 만족하므로, 초기값이 나쁘면 최댓값으로 수렴합니다. 44강에서 "임계점은 후보일 뿐"이라고 한 것이 알고리즘 차원에서 다시 나타납니다.
가 순볼록하면 이 문제가 사라집니다. 이 항상 성립하고 44강 심화 5에 의해 임계점이 곧 전역 최소이기 때문입니다. 볼록성이 최적화에서 왜 중요한지가 여기서 또 한 번 확인됩니다.
112강에서 이 방법을 다변수로 확장하며, 그때 의 자리에 헤세 행렬이 들어갑니다. 109강의 경사하강법은 을 계산하지 않고 상수로 대체하는 방식이며, 계산 비용과 수렴 속도를 맞바꾼 것입니다.
심화 6. 도함수를 쓸 수 없을 때 뉴턴법의 접선을 두 점을 잇는 직선으로 대신하는 방법을 세우고, 에 적용하세요.
풀이. 접선의 기울기 을 최근 두 점에서의 차분몫으로 바꿉니다.
이를 뉴턴 반복식에 넣으면
입니다. 이것이 할선법이며, 이름 그대로 곡선을 두 점에서 자르는 직선을 씁니다. 초기값이 두 개 필요합니다.
에 , 을 넣으면 다음과 같습니다.
| x_ | |
|---|---|
여섯 걸음에 배정밀도의 한계에 도달합니다. 뉴턴법이 네 걸음이었으니 조금 느리지만 도함수를 한 번도 쓰지 않았습니다.
두 방법을 비교합니다.
| 뉴턴법 | 할선법 | |
|---|---|---|
| 수렴 차수 | ||
| 반복당 함수 계산 | 와 두 번 | 한 번(이전 값 재사용) |
| 초기값 | 한 개 | 두 개 |
수렴 차수 은 황금비이며, 오차 지수가 을 만족하는 데서 나옵니다. 이는 이라는 관계에서 유도되는데, 피보나치 수열의 점화식과 같은 구조입니다. 32강에서 점화식을 닫힌 형태로 바꿀 때 만난 그 방정식이 여기서 다시 나옵니다.
반복당 비용을 함께 보면 할선법이 오히려 유리할 때가 많습니다. 을 계산하는 비용이 와 비슷하다면, 뉴턴법 한 걸음의 비용으로 할선법을 두 걸음 갈 수 있고 이므로 같은 비용에서 더 멀리 갑니다.
이 강의에서는 numpy만 씁니다. 반복법은 코드로 확인하기에 가장 적합한 주제입니다. 손으로는 서너 걸음이 한계이지만 코드는 수렴이 끝날 때까지 밀어붙일 수 있습니다.
import numpy as np
def newton(f, fp, x0, n=8):
xs = [float(x0)]
for _ in range(n):
x = xs[-1]
xs.append(x - f(x)/fp(x))
return xs
# --- 문제 1, 2: sqrt(2) 와 이차 수렴 -----------------------------------
xs = newton(lambda t: t**2 - 2, lambda t: 2*t, 1.0, 6)
for k, v in enumerate(xs):
print(k, "%.16f" % v, "%.3e" % abs(v - np.sqrt(2)))
# 0 1.0000000000000000 4.142e-01
# 1 1.5000000000000000 8.579e-02
# 2 1.4166666666666667 2.453e-03
# 3 1.4142156862745099 2.124e-06
# 4 1.4142135623746899 1.595e-12
# 5 1.4142135623730951 0.000e+00
# 6 1.4142135623730949 2.220e-16
# --- 문제 3: 뉴턴법이 실패하는 두 가지 --------------------------------
c = newton(lambda t: t**3 - 2*t + 2, lambda t: 3*t**2 - 2, 0.0, 6)
print([round(v, 10) for v in c])
# [0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0]
d = newton(np.cbrt, lambda t: 1/(3*np.cbrt(t)**2), 0.1, 6)
print(["%.4g" % v for v in d])
# ['0.1', '-0.2', '0.4', '-0.8', '1.6', '-3.2', '6.4']
# --- 문제 4: 이분법과 뉴턴법의 반복 횟수 -------------------------------
g = lambda t: t - np.cos(t)
gp = lambda t: 1 + np.sin(t)
lo, hi, k = 0.0, 1.0, 0
while hi - lo > 1e-15:
mid = 0.5*(lo + hi)
if g(lo)*g(mid) <= 0: hi = mid
else: lo = mid
k += 1
root = 0.5*(lo + hi)
print(k, "%.16f" % root) # 50 0.7390851332151605
xs = newton(g, gp, 1.0, 5)
for i, v in enumerate(xs):
print(i, "%.16f" % v, "%.3e" % abs(v - root))
# 0 1.0000000000000000 2.609e-01
# 1 0.7503638678402439 1.128e-02
# 2 0.7391128909113617 2.776e-05
# 3 0.7390851333852840 1.701e-10
# 4 0.7390851332151607 2.220e-16
# 5 0.7390851332151607 2.220e-16
# --- 심화 2: 중근에서는 일차 수렴 --------------------------------------
m = newton(lambda t: t**2, lambda t: 2*t, 1.0, 6)
print(["%.6g" % v for v in m])
# ['1', '0.5', '0.25', '0.125', '0.0625', '0.03125', '0.015625']
x = 1.0
print(x, x - 2*(x**2)/(2*x)) # 1.0 0.0 (수정 뉴턴법은 한 걸음)
# --- 심화 3: 나눗셈 없이 역수 구하기 -----------------------------------
a, y = 3.0, 0.3
out = [y]
for _ in range(4):
y = y*(2 - a*y); out.append(y)
print(["%.16f" % v for v in out], 1/3)
# ['0.3000000000000000', '0.3300000000000000', '0.3333000000000000',
# '0.3333333300000000', '0.3333333333333333'] 0.3333333333333333
# --- 심화 6: 할선법 ----------------------------------------------------
p, q = 0.0, 1.0
sec = [p, q]
for _ in range(6):
den = g(q) - g(p)
if den == 0: break
p, q = q, q - g(q)*(q - p)/den
sec.append(q)
print(["%.12f" % v for v in sec])
# ['0.000000000000', '1.000000000000', '0.685073357326', '0.736298997614',
# '0.739119361912', '0.739085112127', '0.739085133215', '0.739085133215']
실행하면 주석과 같은 값이 나옵니다. 다섯 곳을 짚어 둡니다.
첫째, 의 오차가 로 줄어듭니다. 지수를 읽으면 로 대략 두 배씩 늘어납니다. 이차 수렴이 눈으로 확인됩니다.
둘째, 다섯 번째 값의 오차가 정확히 인데 여섯 번째에서 으로 도로 커집니다. 반복이 참값에 정착하지 못하고 마지막 비트에서 흔들립니다. 부동소수점에서 를 계산할 때 반올림이 개입하기 때문이며, 알고리즘의 결함이 아닙니다. 정지 조건 없이 반복만 늘리면 답이 좋아지지 않고 이렇게 진동한다는 것을 보여 줍니다.
셋째, 순환 예가 [0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0]으로 완벽하게 되풀이됩니다. 두 값이 모두 부동소수점에서 정확히 표현되는 수라 오차가 끼어들 여지가 없어 이론대로 순환합니다. 심화 4에서 지적한 대로 초기값이 조금만 달랐다면 이 그림이 깨집니다.
넷째, 이분법이 번 걸린 문제를 뉴턴법이 네 번에 끝냅니다. 문제 4에서 손으로 계산한 과 실제 반복 횟수 이 정확히 맞습니다.
다섯째, 역수 계산의 출력이 이 강의에서 가장 보기 좋은 결과입니다. 으로 정확한 자릿수가 이 됩니다. 이차 수렴의 정의가 그대로 눈에 보입니다.
코드로 할 수 없는 일도 분명히 해 둡니다. 반복이 수렴하는 것처럼 보인다고 해서 수렴이 증명된 것은 아닙니다. 순환 예에서 처음 두 값만 보고 판단했다면 에서 로 잘 움직인다고 오해했을 것입니다. 수렴의 보장은 심화 1의 정리에서 나오며, 그 가정을 만족하는지는 코드가 아니라 사람이 확인해야 합니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 뉴턴법 | Newton's method | 접선의 근으로 반복 이동합니다 |
| 이분법 | bisection | 부호가 바뀌는 반쪽을 반복해 택합니다 |
| 할선법 | secant method | 두 점을 잇는 직선의 근으로 이동합니다 |
| 뉴턴 사상 | Newton map | 입니다 |
| 고정점 | fixed point | 인 점입니다 |
| 수렴 차수 | order of convergence | 오차가 몇 제곱으로 줄어드는지입니다 |
| 이차 수렴 | quadratic convergence | 정확한 자릿수가 두 배씩 늘어납니다 |
| 국소 수렴 | local convergence | 근 근처에서 출발할 때만 보장됩니다 |
| 중근 | multiple root | 인 근입니다 |
이 강의로 03단원 미분의 활용이 끝납니다. 42강의 평균값 정리에서 출발해 증가와 감소, 볼록성, 부정형, 최적화, 근 찾기까지 왔습니다. 되돌아보면 여섯 강의 전부가 한 점의 정보인 도함수로 구간 전체를 말하는 일이었고, 그 다리를 놓은 것이 평균값 정리였습니다.
다음 04단원에서는 방향을 완전히 바꿉니다. 지금까지 함수를 쪼개 변화율을 보았다면, 이제 잘게 쪼갠 것을 다시 더합니다. 놀랍게도 그 두 작업이 서로의 역이라는 사실이 밝혀지며, 그것이 미적분의 기본정리입니다.