1
$\begingroup$

I understand mostly what going on when using Newton's method to approximate some value but there are some details I am still hazy on (like how you come up with the correct $f(x)$ for the update rule). I would appreciate it if someone could help me fill in the details. Here's what I understand so far:

The $f(x)$ used for linear approximation seems to be different than the $f(x)$ used in Newton's method.

For example, in estimating $\sqrt[3]{67}$, if we know beforehand somehow that $f(x)=x^3-67$, then $f(\sqrt[3]{67}) = 0$

$$ \begin{align} x_{n+1} &\approx x_n - \frac{f(x_n)}{f'(x_n)} \\ & \approx x_n - \frac{ {x_n}^3 - 67}{3{x_n}^2} \\ & \approx 4 - \frac{64-67}{3\cdot 16} \\ & \approx 4 - \frac{1}{16} \end{align} $$

Using linear approximation, we have $f(x) = \sqrt[3]{x}$, different than above. $$ \begin{align} f(x+h) & \approx f(x) + f'(x) \cdot h\\ & \approx \sqrt[3]{x} + \frac {1}{3x^{ \frac{2}{3} } }h\\ & \approx 64^{ \frac{1}{3} } + \frac{(64 -67)}{3\cdot 64^{\frac{2}{3}}} \\ & \approx 4 - \frac{1}{16} \end{align} $$

To find an $f(x)$ for the update rule, we set our approximation of $f(x+h)$ to zero and solve for $x$.

$$ \begin{align} 0 = f(x+h) &\approx f(x) + f'(x) \cdot h \\ -\frac{f(x)}{f'(x)} & \approx h \\ -\frac{f(x)}{f'(x)} & \approx x - a \\ a - \frac{f(x)}{f'(x)} &\approx x \\ 67 - \frac{x^1/3}{(3x^{\frac{2}{3}})^{-1}} & \approx \text{ new } f(x) \text { for the update rule}\\ 67 - x^3 & \approx \ ? \end{align} $$

I think I've done something wrong in this last part. The $f(x)$ I came up with is different than the one I was supposed to have guessed earlier, and it seems odd to me that you have to solve the linear approximation to get the $f(x)$ you use in the update rule. What's the proper way to find $f(x)$ for the update rule? What's the advantage from using the update rule? Why not just use linear approximation instead? Also, what do you do when the derivative is too hard to compute?

$\endgroup$
1
  • 1
    $\begingroup$ When the derivative is too hard to compute, you can use the Secant Method, the generalization of which to multiple variables is Broyden's Method. $\endgroup$ – Emily Jun 14 '13 at 21:50
4
$\begingroup$

The $f(x)$ is no different.

A graphical interpretation of Newton's method helps. You compute the derivative, which is the tangent of the curve. Then, you project this to the x-axis. This is your linear approximation!

Recall that $y=ax+b$ is a linear curve, and you compute the slope $a$ as $f'(x_n)$. Now, you need the $y$-axis intercept of this curve. How do we get this? We know that at $x=x_n$, that $y=f(x_n)$ because this curve must be tangent to the function.

Therefore, we solve

$$f(x_n) = f'(x_n)x_n + b \implies b = f(x_n)-f'(x_n)x_n.$$

Now, since we have $b$, which is the $y$-intercept, we can find the $x$ intercept by solving $$0 = ax+b.$$

The value of this $x$ gives us the starting point for the next iteration -- in essence, we are jumping back up to the function from this x-intercept.

Newton's method, in short:

  1. Draw slope from curve
  2. Ski down slope to x-axis
  3. Take rocket pack back up to function
  4. Repeat until no more fun can be had
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.