Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The reciprocal formula $F(x) = x (2 − Ax)$
$F'(x) = (2 − Ax) + x(−A) = 2 − 2Ax$
$⇒ F' = (1/A ) = 2 − 2A -(1/A) = 0$
$⇒$ We have to calculate the second derivative
at the root $X =1/A$

$F''(x) = −2A ⇒ F'' =1/A = −2A$
$⇒$ Second Order Process.
$⇒$ The convergence is quadratic

share|improve this question

closed as not a real question by Matt N., Chris Eagle, William, Arkamis, Hagen von Eitzen Sep 28 '12 at 19:49

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I did some preliminary editing. Please make sure I didn't change any of the meaning. Also - you might consider clarifying what the question is, and perhaps a title that indicates what the question is about. –  mixedmath May 30 '12 at 13:09

1 Answer 1

up vote 1 down vote accepted

This comes from an interesting special case of the Newton Method. Let $A\ne 0$. We want to calculate $\frac{1}{A}$ to high precision. We can view this as the problem of finding to high precision the solution of the equation $f(x)=0$, where $$f(x)=\frac{1}{x}-A.$$ The general Newton Method iteration for solving $f(x)=0$ is given by $$x_{n+1}=x_n -\frac{f(x_n)}{f'(x_n)}.$$ For our particular function, a short calculation shows that the iteration becomes the remarkably simple $$x_{n+1}=x_n(2-Ax_n).$$ In the absence of hardware divide, this iteration can be the basis of efficient division in software.

The Newton Method is a special case of fixed point iteration. In fixed point iteration, we are solving the equation $x=g(x)$ by using the iteration $x_{n+1}=g(x_n)$. Fixed point iteration, roughly speaking, behaves nicely if the absolute value of $g'(x)$ is small for $x$ near the solution of $g(x)=x$. In particular, for well-behaved functions, if $g'(r)=0$ at the root $r$, and $g''(r)\ne 0$, we get quadratic convergence. (If $g''(r)=0$, we get better than quadratic convergence.)

The Newton Method for solving $f(x)=0$ arranges for fast convergence by using fixed point iteration to solve $g(x)=x$, where $$g(x)=x-\frac{f(x)}{f'(x)}.$$ For nice functions $f$, if $r$ is the root we seek and $f'(r)\ne 0$, then $g'(r)=0$, so the convergence is fast.

In our particular example, $g(x)=x(2-Ax)$, and the root is $1/A$. Your calculation shows that $g'(1/A)=0$, while $g''(1/A)\ne 0$, so we get quadratic convergence, but no better. The calculations are correct.

Remark: As happens often with the Newton Method, when it is good, it is very very good. But it can be horrid. The convergence is quadratic in this case if our initial estimate $x_0$ is close enough to $1/A$. However, take for example $A=1$. It is easy to find initial estimates $x_0$ for which the Newton Method does not converge.

share|improve this answer

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