[PYTHON] What is Newton's method? ?? Approximate solution of equation to be solved by Newton's method

What is Newton's method?

Newton's method is one of the algorithms to find x such that f (x) = 0, and it is a method that can approximate the solution of the equation.

Using Newton's method, it is possible to approximate the value of √2 and the value of x such that sin (x) = 0.5.

Newton's method concept

In Newton's method, the calculation is based on the following idea.

** When looking for a value x such that f (x) = 0, the tangent intercept x2 at a value x1 is closer to the true value x than the original value x1 **

As shown in the figure below, when you want to find x such that f (x) = 0 in the function f (x), you can find the section x2 of the tangent f'(x) at a certain value x1. It means that x2 is closer than x1 to the value x you want to find.

If you do the same operation based on the value of x2 calculated earlier, x3 will be closer to the target value x.

The more you repeat this procedure, the closer the calculated intercept value will be to the desired value x.

Specific calculation method

The procedure for finding x2 and x3 from x1 is shown, and the general relational expression is calculated from it.

Calculate x2 from x1

Notice the right triangle created by x1, x2, f (x1) as shown in the figure below. ⊿x and ⊿y represent the lengths of the sides of a right triangle, respectively.

Since f'(x1) is a tangent line at f (x1), x2 can be obtained from the relationship of the slope definition formula.

\begin{aligned}
f'(x_1)&=\frac{\Delta y}{\Delta x} \\
&=\frac{f(x_1)}{x_1 - x_2} \\
\Leftrightarrow x_1-x_2&=\frac{f(x_1)}{f'(x_1)} \\
\therefore x_2 &=x_1 - \frac{f(x_1)}{f'(x_1)}
\end{aligned}

You can also calculate x3 from x2 using the same procedure.

\begin{aligned}
x_3 &=x_2 - \frac{f(x_2)}{f'(x_2)}
\end{aligned}

In other words, the following relational expression holds for the x-coordinate xn + 1 calculated by applying the Newton's method to the x-coordinate xn calculated by performing the Newton's method n times.

Newton's method

\begin{aligned}
x_{n+1} &=x_n - \frac{f(x_n)}{f'(x_n)}
\end{aligned}

As the number of calculations n is increased, xn approaches the true value x.

Calculation example (calculate √2)

I think I was able to understand Newton's method somehow, but I will deepen my understanding of how to actually use it through actual calculation examples. Here, I would like to find the value of √2.

First, I don't know the value of √2, so let's set it as x

x=\sqrt{2}

Square both sides to make the calculation easier, and transform the formula so that f (x) = 0.

\begin{aligned}
x^2 &= 2 \\
x^2-2 &= 0 \\
f(x) &= 0  \hspace{1em} (\therefore f(x) = x^2 - 2)
\end{aligned}

Applying the relational expression of Newton's method, it becomes as follows.

\begin{aligned}
x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)} \\
&= x_n - \frac{x_{n}^2-2}{2x_n}
\end{aligned}

Here, let's assume that the value of x1 is 5 and perform the calculation.

\begin{aligned}
x_2 &= x_1 - \frac{x_{1}^2-2}{2x_1} \\
&= 5 - \frac{5^2 -2 }{2 \times 5} \\
&= 2.7
\end{aligned}

Do the same calculation until n = 5

\begin{aligned}
x_3 &\risingdotseq 1.720 \\
x_4 &\risingdotseq 1.441 \\
x_5 &\risingdotseq 1.414
\end{aligned}

The true value of √2 is 1.414 ..., so you can see that the more calculations you make, the closer you get to the true value.

Newton's method to write programmatically

The program that finds the value of √2 as described above is introduced below. Write the program using Python3 from the viewpoint that the contents of the program are easy to understand.

NewtonMethod.py

#Setting an appropriate initial value
x = 5.0

while True:
    
    #Find new x by Newton's method
    x2 =  x - (x * x - 2) / (x * 2)

    #Calculation ends when the calculated value is within the margin of error
    if abs(x2 - x) < 0.0001:
        break
        
    #Repeat the calculation with the calculated value as x
    x = x2

#Display of calculation results
print(x)

x = 5.0 By setting the initial value to 5.0 instead of 5, the result after the decimal point is also secured in the variable.

x2 = x - (x * x - 2) / (x * 2) From the equation obtained in the previous section, calculate the value of x that is close to the true value.

if abs(x2 - x) < 0.0001 As the calculation is repeated, the solution approaches the true value, and the change in the value becomes smaller. Therefore, set the error and end the calculation when the amount of change in the value is within the error range.

Summary

Newton's method is a method for finding x such that f (x) = 0, and it can be calculated approximately with respect to x by iterative calculation. Also, by specifying the error range, you can obtain a value with a guaranteed number of effective digits.