What is Newton's Method?

In numerical analysis, we use an algorithm or equation to repeat calculations towards a solution until the desired level of accuracy and precision is reached. These repeated calculations are called iterations.

Newton's Method, also known as the Newton-Raphson method, is a numerical algorithm that finds a better approximation of a function's root with each iteration.

Why do we Learn Newton's Method?

One of the many real-world uses for Newton’s Method is calculating if an asteroid will encounter the Earth during its orbit around the Sun.

All objects in orbit around the Sun have an elliptical orbit, where the size and shape of the ellipse are unique to each respective astronomical object. The standard equation form for an ellipse is given as:

$$ \frac{x^{2}}{a^{2}} + \frac{y^{2}}{b^{2}} = 1 $$

Since an ellipse is represented by this nonlinear equation form and the path of the Earth and asteroid are each represented by their own unique ellipse equation, the two objects’ paths around the Sun are in fact a system of nonlinear equations which can be solved to find intersection points.

Typically, we learn Newton’s Method in the context of finding the roots/zeroes of an equation. However, Newton’s Method is so powerful that it can also be used to solve a system of equations, linear and nonlinear.

Once we are comfortable using Newton’s Method for a single equation, we can set up a modified version of the method to solve our Earth/asteroid system of nonlinear ellipse equations. If any intersection points are found, we can use other orbital mechanics equations to determine when each object will reach those intersection points.

If there are no intersection points, the asteroid will not encounter the Earth. If there are intersection points but the asteroid and Earth reach them at different times, the asteroid will not encounter the Earth. If there are intersection points and the asteroid and Earth do reach them at the same time, the asteroid could encounter the Earth.

How to Calculate the Roots of a Function Using Newton's Method

The general equation for Newton's Method is given as:

$$x_{i + 1} = x_{i} \; - \; \frac{f(x_{i})}{f'(x_{i})}; \; i=0, 1, 2...$$

Where x_{i + 1} is the x value being calculated for the new iteration, x_i is the x value of the previous iteration, f(x_i) is the function's value at x_i, and f '(x_i) is the value of the function's derivative at x_i.

For the first iteration i = 0 we will plug 0 in for i in the general equation. This results in:

$$x_{(0) + 1} = x_{(0)} \; - \; \frac{f(x_{(0)})}{f'(x_{(0)})} \; \Rightarrow \; x_{1} = x_{0} \; - \; \frac{f(x_{0})}{f'(x_{0})}$$

To begin the calculation process, we must decide on an initial guess of the root which we will call x₀. The initial guess can be any real number but keep in mind that the closer our initial guess is to the actual root of the function, the more likely we are to find a solution quickly.

Then, evaluate the function and its derivative at x = x₀. Plug x₀, f(x₀), and f '(x₀) into the equation to find x₁. We have now completed the first iteration and must determine if more iterations are necessary.

To determine if more iterations are necessary, we use the following convergence criteria formulas:

$$\lvert x_{i + 1} \; - \; x_{i} \rvert \leq \varepsilon \; \text{ and } \; \lvert f(x_{i + 1}) \rvert \leq \delta $$

Where x_{i + 1} is the x value being calculated for the new iteration, x_i is the x value of the previous iteration, ε is the desired precision (closeness of successive x values), f(x_i+1) is the function's value at x_i+1, and δ is the desired accuracy (closeness of approximated root to the true root).

We must decide on the value of ε and δ and leave them constant during the entire run of iterations. The smaller these values are, the more precise and accurate our solution will be. However, if we set the values too small, it could take an excessive amount of iterations to satisfy the convergence criteria.

Now, we check if the convergence criteria have been satisfied by plugging the values of the respective variables into each of the two convergence criteria formulas. For the first iteration i = 0, this will look like:

$$ \begin{align} & \lvert x_{(0)+1} \; - \; x_{(0)} \rvert \leq \varepsilon \; \Rightarrow \; \lvert x_{1} \; - \; x_{0}\rvert \leq \varepsilon \\ \\ & \lvert f(x_{(0) \; + \; 1}) \rvert \leq \delta \; \Rightarrow \; \lvert f(x_{1}) \rvert \leq \delta \end{align}$$

For the convergence criteria to be satisfied, the inequalities in each of the formulas must be true. If one of the inequalities is true but the other is not, convergence has not been met and iteration must continue until the convergence criteria have been satisfied.

If the convergence criteria have been satisfied on a given iteration, calculations are stopped and the x value for that iteration is taken as the solution.

Sometimes Newton's Method will diverge away from a solution and the convergence criteria will never be satisfied. This may happen in any number of iterations. If using a computer to solve with Newton's Method, it is important to set a maximum number of iterations such that calculations will be stopped before a potentially infinite number of iterations occur.

Example Problem

$$\begin{align}& \text{1.) Let's solve for the root of } \; f(x) = x^2-10 \; \text{ using Newton's Method: } \\ \\ & \hspace{3ex} x_{i + 1} = x_{i} - \frac{f(x_{i})}{f'(x_{i})} \\ \\ & \hspace{3ex} \text{Convergence when } \lvert x_{i + 1} - x_{i} \rvert \leq \varepsilon \: \text{ and } \: \lvert f(x_{i + 1}) \rvert \leq \delta\\ & \\ & \text{2.) Given } f(x) = x^2-10\text{, find } f'(x) \\ \\ & \hspace{3ex} f'(x) =2 \cdot x\\ & \\ & \text{3.) Begin Newton's Method iterations at } i = 0 \\ \\ & \hspace{3ex} \text{Using an initial guess of } x_{0} = 10\: \text{ and a convergence critieria of } \: \varepsilon \text{,} \, \delta = 0.0001\\ \\ & \hspace{3ex} \text{Plugging 0 in for } i \text{ in the Newton's Method equation, we get:}\\ \\ & \hspace{3ex} x_{1} = x_{0} - \frac{f(x_{0})}{f'(x_{0})} \Rightarrow x_{1} = (10) - \frac{(10)^2-10}{2 \cdot (10)} \Rightarrow x_{1} = 5.50000\\ \\ & \hspace{3ex} \lvert x_{1} - x_{0} \rvert \leq \varepsilon \Rightarrow \lvert(5.50000) - (10)\rvert = 4.50000\text{, }4.50000\nleq0.0001\\ \\ & \hspace{3ex} \lvert f(x_{1}) \rvert \leq \delta \Rightarrow \lvert(5.50000)^2-10\rvert = 20.25000\text{, }20.25000\nleq0.0001\\ \\ & \hspace{3ex} \text{Convergence criteria not satisfied, continue iterating.} \\ & \hspace{12em} \swarrow \\ \\ & \text{4.) }x_{2} = x_{1} - \frac{f(x_{1})}{f'(x_{1})} \Rightarrow x_{2} = (5.50000) - \frac{(5.50000)^2-10}{2 \cdot (5.50000)} \Rightarrow x_{2} = 3.65909\\ \\ & \hspace{3ex} \lvert x_{2} - x_{1} \rvert \leq \varepsilon \Rightarrow \lvert(3.65909) - (5.50000)\rvert = 1.84091\text{, }1.84091\nleq0.0001\\ \\ & \hspace{3ex} \lvert f(x_{2}) \rvert \leq \delta \Rightarrow \lvert(3.65909)^2-10\rvert = 3.38895\text{, }3.38895\nleq0.0001\\ \\ & \hspace{3ex} \text{Convergence criteria not satisfied, continue iterating.} \\ & \hspace{12em} \swarrow \\ \\ & \text{5.) }x_{3} = x_{2} - \frac{f(x_{2})}{f'(x_{2})} \Rightarrow x_{3} = (3.65909) - \frac{(3.65909)^2-10}{2 \cdot (3.65909)} \Rightarrow x_{3} = 3.19601\\ \\ & \hspace{3ex} \lvert x_{3} - x_{2} \rvert \leq \varepsilon \Rightarrow \lvert(3.19601) - (3.65909)\rvert = 0.46309\text{, }0.46309\nleq0.0001\\ \\ & \hspace{3ex} \lvert f(x_{3}) \rvert \leq \delta \Rightarrow \lvert(3.19601)^2-10\rvert = 0.21445\text{, }0.21445\nleq0.0001\\ \\ & \hspace{3ex} \text{Convergence criteria not satisfied, continue iterating.} \\ & \hspace{12em} \swarrow \\ \\ & \text{6.) }x_{4} = x_{3} - \frac{f(x_{3})}{f'(x_{3})} \Rightarrow x_{4} = (3.19601) - \frac{(3.19601)^2-10}{2 \cdot (3.19601)} \Rightarrow x_{4} = 3.16246\\ \\ & \hspace{3ex} \lvert x_{4} - x_{3} \rvert \leq \varepsilon \Rightarrow \lvert(3.16246) - (3.19601)\rvert = 0.03355\text{, }0.03355\nleq0.0001\\ \\ & \hspace{3ex} \lvert f(x_{4}) \rvert \leq \delta \Rightarrow \lvert(3.16246)^2-10\rvert = 0.00113\text{, }0.00113\nleq0.0001\\ \\ & \hspace{3ex} \text{Convergence criteria not satisfied, continue iterating.} \\ & \hspace{12em} \swarrow \\ \\ & \text{7.) }x_{5} = x_{4} - \frac{f(x_{4})}{f'(x_{4})} \Rightarrow x_{5} = (3.16246) - \frac{(3.16246)^2-10}{2 \cdot (3.16246)} \Rightarrow x_{5} = 3.16228\\ \\ & \hspace{3ex} \lvert x_{5} - x_{4} \rvert \leq \varepsilon \Rightarrow \lvert(3.16228) - (3.16246)\rvert = 0.00018\text{, }0.00018\nleq0.0001\\ \\ & \hspace{3ex} \lvert f(x_{5}) \rvert \leq \delta \Rightarrow \lvert(3.16228)^2-10\rvert = 0.00000\text{, }0.00000\leq0.0001\\ \\ & \hspace{3ex} \text{Convergence criteria not satisfied, continue iterating.} \\ & \hspace{12em} \swarrow \\ \\ & \text{8.) }x_{6} = x_{5} - \frac{f(x_{5})}{f'(x_{5})} \Rightarrow x_{6} = (3.16228) - \frac{(3.16228)^2-10}{2 \cdot (3.16228)} \Rightarrow x_{6} = 3.16228\\ \\ & \hspace{3ex} \lvert x_{6} - x_{5} \rvert \leq \varepsilon \Rightarrow \lvert(3.16228) - (3.16228)\rvert = 0.00000\text{, }0.00000\leq0.0001\\ \\ & \hspace{3ex} \lvert f(x_{6}) \rvert \leq \delta \Rightarrow \lvert(3.16228)^2-10\rvert = 0.00000\text{, }0.00000\leq0.0001\\ \\ & \hspace{3ex} \text{Convergence criteria has been satisfied.}\end{align}$$

How the Calculator Works

This calculator is written in the web programming technologies HTML, CSS, and JavaScript (JS). The HTML builds the framework of the calculator, the CSS styles the framework, and the JS enables interactions with the user and the calculations to happen.

JS runs inside an internet browser just like a program runs inside a computer's operating system. Since this calculator relies only on JS to perform calculations, it can provide instant solutions to the user.

Inside the JS code that powers this calculator is the same routine outlined throughout this lesson. The user's inputted initial guess is plugged into the Newton's Method formula and the new x value is calculated. The convergence criteria formulas are evaluated and compared against the user's inputted convergence criteria value.

The routine will continue iterating until the convergence criteria are satisfied or the iteration limit is reached. If the convergence criteria are satisfied, the x value from the final iteration is returned as the root of the user's inputted function. If the iteration limit is reached, the user is informed that the evaluation has diverged and no solution was found.