Finding a function from Newton iteration

Question

We have the following Newton iteration for a certain function we need to identify:

$$x_{n+1}=2x_n-x_n^2y$$

Here is what I've done so far:

Implementing Newton's method recurrence...

$$x_{n+1}=x_n-{{f(x)} \over {f^{'}(x)}}$$

so we have from 1 and 2

$$x_n-{{f(x)} \over {f^{'}(x)}}=2x_n-x_n^2y$$

$$-{{f(x)} \over {f^{'}(x)}}=x_n-x_n^2y$$

$${{f(x)} \over {f^{'}(x)}}=x_n^2y-x_n$$

$${{f(x)} \over {f^{'}(x)}}= x_n^2(y - {{1} \over {x_n}})$$

$${{f(x)} \over {f^{'}(x)}}= x_n^2(y - {{1} \over {x_n}})$$

$${{f(x)} \over {f^{'}(x)}}= {{y - {{1} \over {x_n}}} \over {{1} \over {x_n^2}}} $$

so

$$f(x) = y - {{1} \over {x}} $$

I think that there must be a more rigorous and straightforward way of going from $${{f(x)} \over {f^{'}(x)}}=x_n^2y-x_n$$

Am I missing something?

Also in general, what is the purpose of the fixed-point iteration anyway? $$x_{n+1}=2x_n-x_n^2y$$

Answer 1

The formula is a way to implement division without having a division operation on the chip. With some good initial guess a good enough result can be achieved before the 5th iteration.

It is more common to use this iteration to refine an inverse matrix.

You could also directly recognize the square in the equation and complete it. Then $$ 1-yx_{n+1}=(1-yx_n)^2 $$ which directly highlights the quadratic convergence to $\frac1y$.

Answer 2

If there exists a function $f$, we get $$\frac{f'(x)}{f(x)}=\frac{1}{x^2y-x}=\frac 1y\left(\frac{1}{x}+\frac{1}{y-x}\right)=\frac 1y\left(\frac{1}{x}-\frac{1}{x-y}\right).$$ Integration gives $$\ln|f(x)|=\frac 1y\ln\ \left|\frac{x}{x-y}\right|+C.$$ Hence, $$f(x)=D\cdot\left(\frac{x}{x-y}\right)^{1/y}.$$