*Notes to a video lecture on http://www.unizor.com*

__Derivatives - Newton's Method__

to Find Zeros of Function

to Find Zeros of Function

The purpose of this lecture is to address a specific problem of finding an approximate solution of equations

**using some methodology suggested by Sir Isaac Newton a few centuries ago.**

*f(x)=0*Obviously, it makes sense to apply this methodology when there is no analytical solution of a given equation, or this analytical solution requires too much efforts.

A word of warning should be given up front. This method might sometimes fail to find an approximate solution. After describing this method it will be obvious that under some circumstances the process of finding a solution is not converging to any number.

Let's start with an impractical but illustrative example of a linear function

**. Obviously, linear equation**

*f(x)=2x−4***looks like**

*f(x)=0***and can be immediately solved:**

*2x−4=0*

*2x=4*

*x=2*But let's approach it differently using the following method.

The graph of

**looks like this (blue line):**

*f(x)=2x−4*To solve the equation

**means to find the X-coordinate of point**

*2x−4=0***, where the graph intersects the X-axis.**

*C*Let's choose any point

**with X-coordinate**

*A***and draw a perpendicular to X-axis from this point to an intersection with the graph of our function**

*x*_{0}**at point**

*f(x)=2x−4***with coordinates**

*B***{**(black line).

*x*}_{0}, f(x_{0})We notice that segment

**is a cathetus of triangle Δ**

*AC***and, therefore, its length equals to**

*ABC*

**AC = AB/**tan(∠**ACB**)We also know that

*tan(∠*is a derivative of a function

**ACB**)**at point**

*f(x)=2x−4***, which is the same as a derivative at any other point, like**

*C***, since our function is linear. This derivative is equal to**

*A***.**

*f*^{ I}(x_{0})=2Therefore, knowing this derivative, X-coordinate of point

**, which is equal to**

*A***, and the value of our function at point**

*x*_{0}**, which is equal to**

*A***, that is the length of segment**

*f(x*_{0})**, we can easily find the length of segment**

*AB***and then the X-coordinate of point**

*AC***:**

*C*

=

**AC = AB /**tan(∠**ACB**) ==

**f(x**_{0}) / f^{ I}(x_{0})Now, X-coordinate of point

**, let's call it**

*C***, equals to X-coordinate of point**

*x*_{1}**minus the length of segment**

*A***:**

*AC*

*x*_{1}= x_{0}− f(x_{0}) / f^{ I}(x_{0})Point

**can be taken arbitrarily. Let's say,**

*A***.**

*x*_{0}=4Then

**.**

*AB=f(x*_{0})=2·4−4=4Since

*tan(∠*,

**ACB**)=**2****.**

*AC=4/2=2*Finally, knowing

**and coordinate of point**

*AC***(**

*A***), we can determine the coordinate of point**

*x*_{0}=4**:**

*C*

*x*_{1}= x_{0}− AC = 4−2=2This is a solution to an original equation

**.**

*2x−4=0*Next step towards Newton's Method is to consider a more complex function and how analogous approach to the one above might lead to a solution.

Our next example is a quadratic polynomial

*f(x)=(2/9)x²+(2/9)x-(4/9)*presented on the next graph (red line).

We have specifically considered such a function that the linear function described above (blue line) is a tangential line to this new function exactly at a point where we chose to start our calculation

**.**

*x*_{0}=4Incidentally, it's easy to see that the zero point of this quadratic polynomial is

**. However, we pretend that we don't know this and attempt to approach this value in a process similar to described above for a linear function.**

*x=1*First of all, note that the behavior of parabola is very smooth on a graph. It is smooth not only in terms of differentiability and continuity of a derivative, but also in terms of its derivative being a monotonic function. In particular, as seen from the graph, direction of parabola and direction of its tangential line at

**(blue line) are very close to each other. From the point of tangency**

*x*_{0}=4**both parabola and its tangential line go to zero towards the same direction - to the left from point**

*x*_{0}=4**.**

*x*_{0}The main implication of this is that a zero point

**of a tangential line with X-coordinate**

*C***, as we calculated above, is closer to a zero point of parabola than original point**

*x*_{1}=2**at X-coordinate**

*A***, where we started the process. Therefore, jumping from point**

*x*_{0}=4**to point**

*A***we got closer to a zero point of a parabola.**

*C*An obvious continuation of this process is to recursively repeat the step above, starting at point

**with X-coordinate**

*C***.**

*x*_{1}=2We draw a perpendicular to X-axis at point

**to intersection with our parabola at point**

*C***with coordinates**

*D***{**and a tangential line to parabola at point

*x*}_{1}, f(x_{1})**(green line) that intersects X-axis at point**

*D***with X-coordinate**

*E***.**

*x*_{2}Let's determine

**from triangle Δ**

*x*_{2}**similarly to the above procedure:**

*EDC*

**CE = CD/**tan(∠**CED**)

**CD = f(x**_{1}) = (2/9)·2²+(2/9)·2−(4/9) = 8/9*tan(∠*=

**CED**)

*f*

= (2/9)·2x^{ I}(x_{1}) == (2/9)·2x

_{1}+(2/9) = 10/9

**CE = (8/9) / (10/9) = 4/5**

*x*

= x

= 2−(4/5) = 6/5_{2}= x_{1}− CE == x

_{1}− f(x_{1}) / f^{ I}(x_{1}) == 2−(4/5) = 6/5

Got closer to a zero point of a parabola that we know is

**, but pretend we don't know it.**

*x=1*Let's repeat this process once more, starting at

**.**

*x*_{2}=6/5

*x*

≅ 1.2 − 0.142222 / 0.755556 ≅

≅ 1.01176_{3}= x_{2}− f(x_{2}) / f^{ I}(x_{2}) ≅≅ 1.2 − 0.142222 / 0.755556 ≅

≅ 1.01176

Got very close to

**!**

*x=1*The recursive process described above is the Newton's method of finding arguments where function equals to zero.

Let's formulate it more rigorously.

Assume, we need to find zeros of some smooth function

**.**

*f(x)**Step 0*

Start with some approximation of a value of an argument

**that is relatively close to the one where our function equals to zero.**

*x*_{0}There is no universal recipe for this approximation, but the better your approximation is - the sooner you will approach the real zero of

**.**

*f(x)*And, to be noted, if your starting value is too far from the real zero, the Newton's method might never converge to real zero of our function.

*Step 1*

From the chosen value

**calculate the next value of a sequence:**

*x*_{0 }

*x*_{1}= x_{0}− f(x_{0}) / f^{ I}(x_{0})This and subsequent steps are straightforward calculations.

*Step 2, 3 etc.*

Check two things:

(a) the value of

**- is it close to zero within your chosen precision?**

*f(x*_{n})(b) the difference between

**and**

*x*_{n }**- is it smaller than your chosen precision?**

*x*_{n−1}If both checks are satisfactory, stop the process. The last

**is your final result.**

*x*_{n}If your precision requirements are not satisfied yet, continue.

Repeat the previous step according to this recursive formula:

*x*_{n+1}= x_{n}− f(x_{n}) / f^{ I}(x_{n})As we noted, Newton's method is not universal. A lot depends on properties of function, whose zeros we are trying to find, and on a choice of the first approximation

**.**

*x*_{0}Let's have an example where Newton's method does not converge to a zero point of a function.

An obvious example is when we choose the first approximation point where a tangential line is parallel to the X-axis.

Thus, in case of a parabola

*f(x)=(2/9)x²+(2/9)x-(4/9)***.**

*x=−0.5*Another obvious example is an attempt to find a zero point if the function has none. Consider function

**with any starting point. The Newton's method will lead you to infinity.**

*f(x)=1/x*It is very important that the first approximation point should be relatively close to a real zero point of a function. Imagine a function having a zero point and a "hump" near it. If we choose a starting point "behind a hump", the process will never get to a zero point. Here is an example.

*f(x)=x·e*^{−x}This function has a maximum at point

**. At this point the tangential line is parallel to X-axis. If our first approximation**

*x=1***is greater or equal to**

*x*_{0}**, we will never converge to a function's zero point at**

*1***.**

*x=0*
## No comments:

Post a Comment