Step By Step Calculus » 13.1 - Linear Approximation and Newton's Method

show_hiddenExpand All [+]
Synopsis
Suppose a\in \mathbb{R}a\in \mathbb{R} is some fixed number, which we will call an anchor, and we think of xx as varying close to aa. Then, we know from the mean value theorem that
\displaystyle f(x)=f(a)+f^{\prime }(y)(x-a)
\displaystyle f(x)=f(a)+f^{\prime }(y)(x-a)
for some yy between xx and aa that can depend upon xx. Now, if f^{\prime }f^{\prime } is continuous at aa and xx is close to aa, then it is reasonable to expect f^{\prime }(y)f^{\prime }(y) is close to f^{\prime }(a)f^{\prime }(a) and
\displaystyle f(x)\approx f(a)+f^{\prime }(a)(x-a).
\displaystyle f(x)\approx f(a)+f^{\prime }(a)(x-a).
This gives us our linear approximation
\displaystyle L_{a}(x)=f(a)+f^{\prime }(a)(x-a)
\displaystyle L_{a}(x)=f(a)+f^{\prime }(a)(x-a)
to f(x)f(x) about anchor aa.
The idea of a linear approximation can be extended to find the roots of a function, through what is called Newton’s method, which is an iterative method. If we wanted to find an xx-intercept, \hat{x}\hat{x}, for f(x)f(x) based upon some decent estimate x_{n}x_{n} of \hat{x}\hat{x}, then we might expect that the xx-intercept, x_{n+1}x_{n+1}, for L_{x_{n}}L_{x_{n}} might give a good approximation for \hat{x}\hat{x}. Then,
\displaystyle 0=L_{x_{n}}(x_{n+1})=f(x_{n})+f^{\prime }(x_{n})(x_{n+1}-x_{n})
\displaystyle 0=L_{x_{n}}(x_{n+1})=f(x_{n})+f^{\prime }(x_{n})(x_{n+1}-x_{n})
or, solving for x_{n+1}x_{n+1}, we have that
\displaystyle x_{n+1}=x_{n}-\frac{f(x_{n})}{f^{\prime }(x_{n})},
\displaystyle x_{n+1}=x_{n}-\frac{f(x_{n})}{f^{\prime }(x_{n})},
which is Newton’s method for finding xx-intercepts. We need only iterate through this final equation, starting from a reasonable guess.
The Newton root finding algorithm then becomes:
  • Make an initial estimate of the root, x_0x_0. This is often done by guessing or solving some Taylor polynomial T_n(x)T_n(x) (for nn small).
  • Given some x_nx_n, define x_{n+1}=x_n-\dfrac{f(x_n)}{f^\prime (x_n)}x_{n+1}=x_n-\dfrac{f(x_n)}{f^\prime (x_n)}.
  • Repeat previous step until the sequence either diverges or converges to the desired accuracy.
It is incredibly important to remember that Newton’s method will not always converge to a solution, so the choice of a good x_0x_0 becomes important.