Solving f(u)=0 by Newton’s Method

  • The sciences, are small power; because not eminent; and therefore, not acknowledged in any man; nor are at all, but in a few; and in them, but of few things. For science is of that nature, as none can understand it to be, but such as in a good measure have attained it. (Thomas Hobbes in Leviathan Chapter X 14.)
  • Arts of public use, as fortifications, making of engines, and other instruments of war; because they confer to defence, and victory, are power: and though the true mother of them, be science namely the mathematics; yet, because they are brought into the light, by hand of the artificer, they be esteemed (the midwife passing with vulgar for the mother,) as his issue. (Thomas Hobbes in Leviathan Chapter X 15.)

We now consider a variant of time stepping for solving f(u)=0 with faster convergence by invoking the (inverse of the) derivative f^\prime (u), referred to as Newton’s Method.

Let us then start with N=1 and let f:R\rightarrow R be a differentiable function. Consider the following Fixed Point Iteration:

  • u^{n+1}=u^n-\frac{f(u^n)}{f^\prime (u^n)}=g(u^n)     (1)

with corresponding function

  • g(u)=u-\frac{f(u)}{f^\prime (u)}

assuming that f^\prime (u)\neq 0. Computing the derivative g^\prime(u), we get

  • g^\prime (u)=1-\frac{f^\prime (u)}{f^\prime (u)}+\frac{f(u)f^{\prime\prime}(u)}{(f^\prime (u))^2}= 0,

if f(u)=0. Thus we may expect that \vert g^\prime (u)\vert is small, that is that L<<1 implying fast convcergence.

The iteration (1) is called Newton’s Method for computing a solution of the equation f(u)=0. Compare with the choice g(u) = u - f(u) in the setting of the Contraction Mapping with thus f(u) instead of \frac{f(u)}{f^\prime (u)}.

Newton’s method directly generalizes to f: R^N\rightarrow R^N in the form

  • u^{n+1}=u^n-(f^\prime (u^n))^{-1}f(u^n)     (Newton’s Method)

where f^\prime (u^n))^{-1} is the inverse of the N\times N matrix f^\prime (u^n) (thus assuming that f^\prime (u^n) is non-singular).

One can show that \vert e^{n+1}\vert\sim \vert e^n\vert^2, if the initial guess is close enough to the root, which means that the number of correct digits may double each iteration step.

Wellposed and Illposed Roots

Suppose u is an approximate solution with residual f(u)\approx 0, or approximate root of an equation f(u)=0 with exact root \bar u satisfying f(\bar u)=0. We have for small \vert u-\bar u\vert

  • f(u)-f(\bar u)\approx f^\prime (u)(u -\bar u),

still assuming for simplicity N=1. This shows that

  • \vert u-\bar u\vert \approx \frac{\vert f(u)\vert}{\vert f^\prime (u)\vert}

indicating that the residual error \vert f(u)\vert translates to the root error \vert u-\bar u\vert with the stability factor

  • S =\frac{1}{\vert f^\prime (u)\vert},

that is

  • \vert u-\bar u\vert \approx S\vert f(u)\vert

In other words, if \vert f^\prime (u)\vert is not small so that S is not large, then the root is well defined or well posed, while if \vert f^\prime (u)\vert is small so that S is large, then the root is ill posed or not well defined.

For a wellposed root u the curve x\rightarrow f(x) crosses the x-axis at x=u with a definite slope, which makes the crossing point well determined. For an illposed root the curve is almost tangent to the x-axis which makes the crossing point difficult to pin down.

Newton’s Method Requires Good Initial Guess

Newton’s method converges very quickly towards a root, if the starting value is close enough to the root. If not, the iterations may diverge and then give rise complex fractal patterns as shown in the figure below showing big basins of convergence around roots separated by fractal boundary zones.

Learn More

  • \hyperref[chapterfixedpoint]{Fixed point iteration.}
  • \hyperref[chapternewton]{Newton’s method}

To Think About

  • How to compute \sqrt{2} by solving x^2=2?

Watch

Fractals from iterations by Newton’s method. Big basins show roots. Boundaries between basins show fractal complexity.

Next: From Residual to Root Error       Previous: Solving f(u)=0 by Time Stepping

Advertisements

1 Comment

Comments RSS
  1. best membership plugins

    I just like the helpful info you supply for your articles.
    I’ll bookmark your weblog and test again here frequently.
    I’m relatively certain I will learn plenty of new stuff right here!
    Best of luck for the following!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: