1
$\begingroup$

The Chord Method is:

$x^{(k+1)} = x^{(k)} - {g(x^{(k)}) \over g'(x^{(0)})}$

The question is to compute the cube root of 2, using the Chord Method. Carry out the first few iterations, using x(0) = 0.6.

$g(x) = x^3 -2$

$g'(x) = 3x^2$

$x^{(1)} = 0.6 - {(0.6)^3 -2 \over 3(0.6)^2}$

$x^{(1)} = 0.6 - {(0.6)^3 -2 \over 1.08 }$

$x^{(1)} = 2.2518$

$x^{(2)} = 2.2518 - {(2.2518)^3 -2 \over 1.08 }$

$x^{(2)} = -6.4685$

$x^{(3)} = -6.4685 - {(-6.4685)^3 -2 \over 1.08 }$

$x^{(3)} = 245.9868$

And then things get really really bad.

The problem is when usign Newton's Method it converges to a value of around ~1.2599; and

"The two methods converge under essentially the same conditions."

According to my notes. So shouldn't it also converge using the Chord Method as it does using Newton's? Am I missing something?

$\endgroup$
  • $\begingroup$ For the Chord method to converge, the first guess, $x^{(0)}$, needs to be sufficiently close to the root. $\endgroup$ – Stephen Montgomery-Smith Feb 22 '15 at 5:13
  • $\begingroup$ Isn't that the same for Newton's method though, it does say under 'under essentially the same conditions.'? $\endgroup$ – RaenirSalazar Feb 22 '15 at 5:16
  • $\begingroup$ Yes, Newton's Method generally also requires that the first guess be sufficiently close to the root. However when solving polynomial equations, most of the time most anything will work as a first guess. $\endgroup$ – Stephen Montgomery-Smith Feb 22 '15 at 5:18
  • $\begingroup$ Are you sure that the denominator is always $g'(x_0)$? That would make it very sensitive to the initial approximation. $\endgroup$ – marty cohen Feb 22 '15 at 5:39
  • $\begingroup$ I would expect Newton's to be a bit more robust since for each iteration it uses an improved x value while this method does not. if you choose x = 1.2 as your initial condition the chord method converges fine. $\endgroup$ – bobbym Feb 22 '15 at 6:19
1
$\begingroup$

For solving $g(x)=0$, the iterates generated by the chord method are $$x_{k+1} = x_k - {g(x_k) \over g'(x_0)}$$ while those given by Newton method are $$x_{k+1} = x_k - {g(x_k) \over g'(x_k)}$$ so the two methods will behave the same (or almost the same) if $g'(x_k) \approx g'(x_0)$ (that is to say when $g(x)$ is almost linear from $x_0$ to the solution) or when the solution is close to $x_0$.

If you want to use the chord method (what I should almost never suggest), what you can do is to use it for $2$ or $3$ iterations (so we have $x_0,x_1,x_2$) and repeat the process defining the new $x_0$ as being equal to the last $x_2$.

I any manner, when it works, the chord method as a linear convergence while Newton method has a quadratic convergence (which means that it will require much less iterations).

If you really do not want to update the derivative, I suppose that you could approximate it by finite difference using $$g'(x_k)\approx\frac{g(x_k)-g(x_{k-1})}{x_k-x_{k-1}}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The question was "Show how to use the Chord method to compute the cube root of 2. Carry out the first few iterations, using x(0) = 0.6" so I do not believe it is expected that I update the denominator, I guess I got hung up on taking "will behave the same on essentially the same" as being that if using the same initial guess and g(x) will always converge. $\endgroup$ – RaenirSalazar Feb 22 '15 at 14:25
  • $\begingroup$ The approximation using the finite difference scheme is known as the Secant Method. $\endgroup$ – Stephen Montgomery-Smith Feb 23 '15 at 0:06

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.