[[분류:알고리즘]]
[목차]
== 개요 ==
바빌로니아 법(Babylonian method) 또는 헤론법(Heron's method)은 [[제곱근]]에 대한 근사값을 구하는 알고리즘이다. [[뉴턴-랩슨 방법]]의 제곱근 버전이라고 할 수 있다.

== 방법 ==
찾고자하는 제곱근 값 [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)]가 작다.
== 예시 ==
[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 )]

== 관련문서 ==
 * [[이진 탐색 알고리즘]]