1. 개요
바빌로니아 법(Babylonian method) 또는 헤론법(Heron's method)은 제곱근에 대한 근사값을 구하는 알고리즘이다. 뉴턴-랩슨 방법의 제곱근 버전이라고 할 수 있다.2. 방법
찾고자하는 제곱근 값 [math( \sqrt{S})]에 대해서 다음과 같은 공식이 극한(limit)의 개념에서 성립한다.[math(\sqrt{S} = x + y )]를 가정하고
[math(\sqrt{S}^2 = (x + y)^2 )]
[math({S} = (x + y)(x + y) )]
[math(S = x^2 + 2xy + y^2 )]
[math(S -x^2 = 2xy + y^2 )]
[math(S -x^2 = y(2x + y) )]
[math(\displaystyle {{S -x^2} \over {(2x + y) }} = y)]
재귀함수에서
[math(\sqrt{S} = x + y )]는
[math(\displaystyle \sqrt{S} = x + \left( { {S -x^2} \over {2x + \cancel{y} }} \right))] 여기서 [math(y)]는 재귀함수 값이므로 유보하여 0으로 가정한다.
[math(\displaystyle \sqrt{S} =x + { {S -x^2} \over {2x }} )]
[math(\displaystyle \sqrt{S} = { {2x^2 + S -x^2} \over {2x }} )]
[math(\displaystyle \sqrt{S} = { {2x -x + {{S}\over{x}} } \over {2 }} )]
[math(\displaystyle \sqrt{S} = { {x + {{S}\over{x}} } \over {2 }} )]
[math(\displaystyle \sqrt{S} = { {1}\over{2 }} \left( {x + {{S} \over {x}} } \right))]
수열의 생성에서
[math(\displaystyle { {1}\over{2 }} \left( {x_0 + {{S} \over {x_0}} } \right) =x_{1} )]
[math(\displaystyle { {1}\over{2 }} \left( {x_1 + {{S} \over {x_1}} } \right) =x_{2} )]
[math(\displaystyle { {1}\over{2 }} \left( {x_2 + {{S} \over {x_2}} } \right) =x_{3} )]
[math( \> \> \> \> \vdots )]
[math(\displaystyle { {1}\over{2 }} \left( {x_n + {{S} \over {x_n}} } \right) =x_{n+1} )]
[math( \lim \limits_{n \rightarrow \infty} x_n = \sqrt{S} )]
이전 스텝에서의 오류를 e라고 한다면 S에 대해서 [math( x_{n} = \sqrt S + e )]라고 할 수 있다.
이에 대해서 [math( x_{n+1})] 는...
[math( let \ \sqrt S = T )]
[math(\displaystyle x_{n+1} = {1 \over 2} \times ( (T + e) + {S \over T + e} ) )]
[math(\displaystyle = {1 \over 2} \times { (T + e)^2 + T^2 \over T + e })]
[math(\displaystyle = {1 \over 2} \times { 2 \times T^2 + 2 \times eT + e^2 \over T+e } )]
[math(\displaystyle = {1 \over 2} \times { 2(T+e) \times T + e^2 \over T + e })]
[math(\displaystyle = {1 \over 2} \times ( 2 \times T + { e^2 \over T + e} ))]
[math(\displaystyle = T + { e^2 \over 2 x_n } )]
이 되며
[math(\displaystyle e_{n+1} = { e_{n} \over 2 } \times { e_{n} \over T + e_n } )]
[math(\displaystyle \because T > 0 \rightarrow | { e_{n} \over T + e_n } | < 1 )]
이므로 이진탐색보다 빠르게 에러를 줄일 수 있다.
특히 [math(|e|<1)]이면 [math(\displaystyle { e_{n} \over T + e_n } )]는 몹시 빠른 속도로 줄어든다.
1보다 큰 수에 대해서는 1에서 시작하는 편이, 1보다 작은 수에 대해서는 그 수에서 시작하는 편이 시작 [math(e)]가 작다.
3. 예시
[math( \sqrt 7 )]에 대한 바빌로니아 법 계산[math( \sqrt 9 > \sqrt 7 > \sqrt 4 )]
[math( 3 > \sqrt 7 > 2 )]
[math(\displaystyle \sqrt{S} = { {1}\over{2 }} \left( x+ {{S} \over {x}} \right) )]에서
[math(\displaystyle \sqrt 7 = { {1}\over{2 }} \left( 2+ {{ 7}\over{2}} \right)= {{11} \over {4}} )]
[math(\displaystyle \sqrt 7 = { {1}\over{2 }} \left( {{11}\over{4}} + {{ 7}\over
11}\over{4} \right)= {{233} \over {88}})][math(\displaystyle \sqrt 7 = { {1}\over{2 }} \left( {{233}\over{88}} + {{ 7}\over
233} \over {88} \right) =2.6458 \dots )]