# Newton’s method

Let ${\mathbf{f}}$ be a differentiable function from $\mathbb{R}^{n}$ to $\mathbb{R}^{n}$. Newton’s method consists of starting at an $\mathbf{a_{0}}$ for the equation ${\mathbf{f}}(\mathbf{x})=\mathbf{0}$. Then the function is linearized at $\mathbf{a_{0}}$ by replacing the increment ${\mathbf{f}}(\mathbf{x})-{\mathbf{f}}(\mathbf{a_{0}})$ by a linear function  of the increment $[\mathbf{D}(\mathbf{a_{0}})](\mathbf{x}-\mathbf{a_{0}})$.

Now we can solve the linear equation ${\mathbf{f}}(\mathbf{a_{0}})+[\mathbf{D}(\mathbf{a_{0}})](\mathbf{x}-\mathbf{a% _{0}})=\mathbf{0}$. Since this is a system of n linear equations in n unknowns, $[\mathbf{D}(\mathbf{a_{0}})](\mathbf{x}-\mathbf{a_{0}})=-{\mathbf{f}}(\mathbf{% a_{0}})$ can be likened to the general linear system $A\mathbf{x}=\mathbf{b}$.

Therefore, if $[\mathbf{D}(\mathbf{a_{0}})]$ is invertible   , then $\mathbf{x}=\mathbf{a_{0}}-[\mathbf{D}(\mathbf{a_{0}})]^{-1}{\mathbf{f}}(% \mathbf{a_{0}})$. By renaming $\mathbf{x}$ to $\mathbf{a_{1}}$, you can reiterate Newton’s method to get an $\mathbf{a_{2}}$. Thus, Newton’s method states

 $\mathbf{a}_{n+1}=\mathbf{a}_{n}-[\mathbf{D}{\mathbf{f}}(\mathbf{a}_{n})]^{-1}{% \mathbf{f}}(\mathbf{a}_{n})$

Thus we get a series of $\mathbf{a}$’s that we hope will converge to $\mathbf{x}$ such that ${\mathbf{f}}(\mathbf{x})=\mathbf{0}$. When we solve an equation of the form ${\mathbf{f}}(\mathbf{x})=\mathbf{0}$, we call the solution a root of the equation. Thus, Newton’s method is used to find roots of nonlinear equations.

Unfortunately, Newton’s method does not always converge. There are tests for neighborhoods  of $\mathbf{a_{0}}$’s where Newton’s method will converge however. One such test is Kantorovitch’s theorem  , which combines what is needed into a concise mathematical equation.

- The above equation is simplified in one dimension to the well-used

 $a_{1}=a_{0}-\frac{f(a_{0})}{f^{\prime}(a_{0})}$

This intuitively cute equation is pretty much the equation of first year calculus. :)

Corollary 2: Finding a square root - So now that you know the equation, you need to know how to use it, as it is an algorithm  . The construction of the primary equation, of course is the important part. Let’s see how you do it if you want to find a square root of a number b.

We want to find a number x (x for unknown), such that $x^{2}=b$. You might think “why not find a number such that $x=\sqrt{b}$ ?” Well, the problem with that approach is that we don’t have a value for $\sqrt{b}$, so we’d be right back where we started. However, squaring both sides of the equation to get $x^{2}=b$ lets us work with the number we do know, $b$.) Back to $x^{2}=b$. With some manipulation, we see this means that $x^{2}-b=0$ ! Thus we have our $f(x)=0$ scenario.

We can see that $f^{\prime}(x)=2x$ thus, $f^{\prime}(a_{0})=2a_{0}$ and $f(a_{0})=a_{0}^{2}-b$. Now we have all we need to carry out Newton’s method. By renaming $x$ to be $a_{1}$, we have

 $a_{1}=a_{0}-\frac{1}{2a_{0}}(a_{0}^{2}-b)=\frac{1}{2}\left(a_{0}+\frac{b}{a_{0% }}\right)$

.

The equation on the far right is also known as the divide and average  method, for those who have not learned the full Newton’s method, and just want a fast way to find square roots. Let’s see how this works out to find the square root of a number like 2:

Let $x^{2}=2$

 $x^{2}-2=0=f(x)$

Thus, by Newton’s method,…

 $a_{1}=a_{0}-\frac{a_{0}^{2}-2}{2a_{0}}$

All we did was plug in the expressions $f(a_{0})$ and $f^{\prime}(a_{0})$ where Newton’s method asks for them. Now we have to pick an $a_{0}$. Hmm, since

 $\sqrt{1}<\sqrt{2}<\sqrt{4}$
 $1<\sqrt{2}<2$

let’s pick a reasonable number between 1 and 2 like 1.5

 $a_{1}=1.5-\frac{1.5^{2}-2}{2(1.5)}$
 $a_{1}=1.41\bar{6}$
 $a_{2}=1.41\bar{6}-\frac{1.41\bar{6}^{2}-2}{2(1.41\bar{6})}$
 $a_{2}=1.414215686\dots$

getting better =) You can use your calculator to find that

 $\sqrt{2}=1.414213562\dots$

Not bad for only two iterations! Of course, the more you iterate, the more decimal places your $a_{n}$ will be accurate to. By the way, this is also how your calculator/computer finds square roots!

Consider an arbitrary function $f\colon\mathbb{R}\rightarrow\mathbb{R}$ such as $f(x)=x^{2}-b$. Say you wanted to find a root of this function. You know that in the neighborhood of $x=a_{0}$, there is a root (Maybe you used Kantorovitch’s theorem or tested and saw that the function changed signs in this neighborhood). We want to use our knowledge $a_{0}$ to find an $a_{1}$ that is a better approximation to $x_{0}$ (in this case, closer to it on the x-axis).

So we know that $x_{0}\leq a_{1}\leq a_{0}$ or in another case $a_{0}\leq a_{1}\leq x_{0}$. What is an efficient algorithm to bridge the gap between $a_{0}$ and $x_{0}$ ? Let’s look at a tangent line to the graph.

Note that the line intercepts the x-axis between $a_{0}$ and $x_{0}$, which is exactly what we want. The slope of this tangent line is $f^{\prime}(a_{0})$ by definition of the derivative   at $a_{0}$, and we know one point on the line is $(a_{1},0)$, since that is the x-intercept. That is all we need to find the formula   of the line, and solve for $a_{1}$.

 $\displaystyle y-y_{1}$ $\displaystyle=m(x-x_{1})$ $\displaystyle f(a_{0})-0$ $\displaystyle=f^{\prime}(a_{0})(a_{0}-a_{1})$ Substituting $\displaystyle\frac{f(a_{0})}{f^{\prime}(a_{0})}$ $\displaystyle=a_{0}-a_{1}$ $\displaystyle-a_{1}$ $\displaystyle=-a_{0}+\frac{f(a_{0})}{f^{\prime}(a_{0})}$ Aesthetic change. Flipped the equation around. $\displaystyle a_{1}$ $\displaystyle=a_{0}-\frac{f(a_{0})}{f^{\prime}(a_{0})}$ Newton’s method!
 Title Newton’s method Canonical name NewtonsMethod Date of creation 2013-03-22 11:58:05 Last modified on 2013-03-22 11:58:05 Owner alozano (2414) Last modified by alozano (2414) Numerical id 28 Author alozano (2414) Entry type Algorithm Classification msc 49M15 Synonym Newton-Raphson method Related topic LipschitzCondition Related topic KantorovitchsTheorem Related topic Derivative Related topic Superconvergence Related topic FixedPointsOfNormalFunctions