Python-Nonlinear equation solution dichotomy & Newton-Raphson method

Find the numerical solution of the following nonlinear equations using the dichotomy and Newton's method.

sin(x)=0

Dichotomy

When $ f (x) $ is continuous and $ f (a) f (b) <0 $ in the interval $ x = [a, b] $, the solution that $ f (x) = 0 $ in the interval How to find one.

The algorithm is

  1. Substitute the initial values for $ a_0 and b_0 $ within the range where you want to find a solution that satisfies $ f (a_0) f (b_0) <0 $.
  2. $ c = \ frac {(a_i + b_i)} {2} $, and if $ f (c) f (a_i) <0 $, then $ b_ {i + 1} = c, a_ {i + 1} If = a_i $ and $ f (c) f (a_i)> 0 $, update with $ b_ {i + 1} = b_i, a_ {i + 1} = c . 3.Perform 2 sequential calculations and|f(c)|<ε_1$Or|a_i-b_i|<ε_2If is satisfied, the calculation is terminated as if it has converged.

·Source code

In order to find the solution of $ x = π $, the initial values are $ a_0 = 3.0 $ and $ b_0 = 3.5 $.

import math

def f(x):
    return math.sin(x)

EPS1 = 0.00001
EPS2 = 0.00001

a = 3.0
b = 3.5

while True:
    c = (a + b)/2
    if f(a)*f(c) < 0:
        b = c
    else:
        a = c
    if abs(f(c)) < EPS1 or abs(a - b) < EPS2:
        break

print("x = %f" % c)

·result

>>> print("x = %f" % c)
x = 3.141602

Newton's method

A method of finding the tangent of $ f (x) $ in $ x_i $, updating the intersection of the tangent and the $ x $ axis as the next $ x_ {i + 1} $, and performing sequential calculations.

The tangent $ g (x) $ of $ f (x) $ in $ x_i $ is

g(x)-f(x_i)=f^{'}(x_i)(x-x_i)

Set $ g (x) = 0 $ to update the intersection of the tangent and the $ x $ axis as the next $ x_ {i + 1} $

0-f(x_i) = f^{'}(x_i)(x_{i+1}-x_i)\\
x_{i+1} = x_i-\frac{f(x_i)}{f^{'}(x_i)} ... ①

The algorithm is

  1. Give an initial value to $ x_0 $.
  2. Find the following $ x_ {i + 1} $ according to the formula ①. 3.Repeat 2$|f(x)|<ε$When it becomes, it is considered that it has converged and it ends.

·Source code

This time, the analytical solution ($ cos (x) $) was used as the differential value.

import math

def f(x):
    return math.sin(x)

def df(x):
    return math.cos(x)

EPS1 = 0.0001

x = 3.5

while True:
    x -= f(x)/df(x)
    if abs(f(x)) < EPS1:
        break
        
print("x = %f" % x)

·result

>>> print("x = %f" % x)
x = 3.141594

Recommended Posts

Python-Nonlinear equation solution dichotomy & Newton-Raphson method
Python --Differential equation numerical solution Euler method & central difference method & Runge-Kutta method