Newton’s Method

10 Feb 2024 in Study / Computer science on Newton's method

Algorithm

• We can estimate the specific number whose value cannot be determined accurately
• We use tangent line (접선)

√2 Estimation

• 1^st : f(x) = x² (When x = √2, y = 2) and initial a = 2
• 2^nd : f ^‘(x) = 2x
• 3^rd : f ^‘(a) = 4
• 4^th : tangent line = 4x - 4
• 5^th : Intersection point’s x coordinate between tangent line and y = 2 → Update a (a = 1.5)
• 6^th : repeat 2^nd ~ 5^th
• That is, intersection point’s x coordinate between tangent line and y = 2 gets closer to √2

repeat = 10
a = 2

for i in range(repeat):
    a = (a ** 2 + 2) / (2 * a)             # y = 2ax - a^2 and y = 2

print(a)

1.414213562373095

Generalization

• 1^st : set continuous f(x) (When y = r meets f(x), the intersection x coordinate is target number being going to estimate) and initial a (Initial a should be close to the target number)
• 2^nd : At point (a, f(a)), tanget line should be calculated
• 3^rd : The intersection point’s x coordinate between the tangent line and y = r should be calculated and it gonna be new a
• 4^th : repeat
• Example
  • ⁵√3 → f(x) = x⁵ and y = r = 3
  • e³ → f(x) = lnx and y = r = 3
  • ln6 → f(x) = e^x and y = r = 6
  • 5^0.6 → f(x) = x¹⁰ and y = r = 5⁶

Binary Search

• We can use binary search as well for some estimation
• √2 Estimation
  • 1^st : Think 1 < √2 < 2
  • 2^nd : middle = (start + end) / 2 (initial start == 1, initial end == 2)
  • 3^rd : If m² < (√2)² = 2, start = m & end = end
  • 4^th : If m² >= (√2)² = 2, start = start & end = m
  • 5^th : Repeat

  
  

  def Binary_newton(start, end, count):
    m = (start + end) / 2
    count += 1
    if count == 20:
        return m
  
    if m ** 2 < 2:
        return Binary_newton(m, end, count)
    else:
        return Binary_newton(start, m, count)
  
  print(Binary_newton(1, 2, 0))
  
  
  

• Newton’s method vs Binary search
  • Newton’s method (repeat = 3) : 5 location correct
  • Binary search (repeat = 20) : 5 location correct