direction Link to heading

  • Mr. Satoru is stuck in a train station with a bunch of monsters (which he needs to kill) and humans (which he needs to save). He can expand a “sure-kill” domain that kills anyone within its perimeters, with him as the center, but he must consider the optimal amount of monsters killed and humans saved.
  • The monsters are distributed around him in a randomized manner, but can be represented with the equation $$\tag{1} M(x) = 20x - x^2. $$
  • The humans distributed around him can also be represented with the equation $$\tag{2} H(x) = \sin 2x. $$
  • Mr. Satoru’s judgement on the radius in which he would expand him domain can be represented with the following equation $$\tag{3} R(x) = M(x) + H(x). $$
  • Optimize the radius of Mr. Satoru’s domain using the Newton-Raphson method, and Secant Method until the error $\varepsilon < 10^{-3}$! (Hint: To optimize a function, differentiate it first and find its root).

derivative Link to heading

  • differentiate Eqn (3), with the help of Eqns (1) and (2) wil give $$\tag{4} R'(x) = M'(x) + H'(x) = 20 - 2x + 2\cos 2x. $$
  • Optimum radius is obtained when $$\tag{5} R'(x_{\rm optimum}) = 0. $$
  • Find root of $x'(x)$ to get $x_{\rm optimum}$.

iterative method Link to heading

  • Newton-Raphson method $$\tag{6} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. $$
  • Secant method $$\tag{7} x_{n+2} = x_{n+1} - \frac{(x_{n+1} - x_n) f(x_{n+1})}{f(x_{n+1}) - f(x_n)}. $$
  • Newton-Raphson method requires one initial value $x_0$ and secant method requires two initial values $x_0$ and $x_1$.

solution Link to heading

  • Code
    import math
    
    # test find optimum or y = (x - 2)(x - 6)
    # it will give x = 4
    # and ok
    TEST = False
    
    # break
    ITERMAX = 100
    
    # show iteration
    SHOWITER = False
    
    # Method
    METHOD = 'Newton-Raphson'
    
    def R(x):
      if TEST:
        y = (x - 2) * (x - 6)
      else:
        y = 20 * x - x**2 + math.sin(2 * x)
      return y
    
    def R_(x):
      if TEST:
        y = (x - 2) + (x - 6)
      else:
        y = 20 - 2*x + 2 * math.cos(2 * x)
      return y
    
    def R__(x):
      if TEST:
        y = 2
      else:
        y = -2 - 4 * math.sin(2 * x)
      return y
    
    # method 1
    print("Newton-Raphson method")
    if SHOWITER:
      print("i", "err", "R_(x)", "x", sep='\t')
    
    x0 = 19
    err = 1
    i = 1
    while err > 1E-3:
      # finding root for R_(x) not for R(x)
      x1 = x0 - R_(x0) / R__(x0)
      err = abs((x1 - x0))
    
      if SHOWITER:
        errs = f'{err:.2f}'
        R_xs = f'{R_(x1):.2f}'
        xs = f'{x1:.2f}'
        print(i, errs, R_xs, xs, sep='\t')
    
      x0 = x1
      i += 1
    
      if i > ITERMAX:
        break
    
    i -= 1
    x = x1
    
    print()
    print("Results")
    print("iteration =", i)
    print("err =", err)
    print("x =", x)
    print("R(x) =", R(x))
    print("R_(x) =", R_(x))
    print("R__(x) =", R__(x))
    print()
    
    # method 2
    print("secant method")
    if SHOWITER:
      print("i", "err", "R_(x)", "x", sep='\t')
    
    x0 = 1
    x1 = 50
    err = 1
    i = 1
    while err > 1E-3:
      # finding root for R_(x) not for R(x)
      x2 = x1 - R_(x1) / (R_(x1) - R_(x0)) * (x1 - x0)
      err = abs((x2 - x1))
    
      if SHOWITER:
        errs = f'{err:.2f}'
        R_xs = f'{R_(x2):.2f}'
        xs = f'{x2:.2f}'
        print(i, errs, R_xs, xs, sep='\t')
    
      x0 = x1
      x1 = x2
      i += 1
    
      if i > ITERMAX:
        break
    
    i -= 1
    x = x2
    
    print()
    print("Results")
    print("iteration =", i)
    print("err =", err)
    print("x =", x)
    print("R(x) =", R(x))
    print("R_(x) =", R_(x))
    print("R__(x) =", R__(x))
    
  • Result
    Newton-Raphson method
    
    Results
    iteration = 8
    err = 7.699729229315722e-06
    x = 10.139963731429795
    R(x) = 100.97056678487193
    R_(x) = -3.319355901254539e-11
    R__(x) = -5.960626523950763
    
    secant method
    
    Results
    iteration = 5
    err = 0.0002986050511903926
    x = 10.139963647548765
    R(x) = 100.97056678487193
    R_(x) = 4.9995029555161e-07
    R__(x) = -5.960626430028292
    

url https://onecompiler.com/python/3zpg9vgqa

notes Link to heading

  • It seem that Newton-Raphson method is very sensitive to initial value to obtain optimum of Eqn (3).
  • Furhter study is required to investigate the good function to optimize and not too sensitive to initial value for Newton-Raphson method and to initial values for secant method.