Simple modification of Newton's method problem

48 Views Asked by At

Since you can transform Newton's recurrence relation to the original equation $f(x)=0$ by considering the limiting case as $n$ tends to infinity, it's not surprising you can also do it the other way around (if you know what you are doing). Starting with $f(x)=0$, you can transform it to an equation with an $x$ on the LHS that will play the role of $x_{n+1}$ and some $g(x)$ on the RHS where you can replace the $x$ with $x_{n}$. If you do it just right, you get the same recurrence relation just as if you applied the Newton's method directly. For example, take $f(x)=x^2-x-1$:

Newton's recurrence relation would be:

$$x_{n+1}=\frac{x_{n}^2+1}{2x_{n}-1}$$

And by starting with $f(x)=0$ we can get the same:

$$x^2-x-1=0$$ $$x^2-x=1$$ $$x^2-x+x^2=1+x^2$$ $$2x^2-x=x^2+1$$ $$x=\frac{x^2+1}{2x-1}$$ $$x_{n+1}=\frac{x_n^2+1}{2x_n-1}$$

Now, suppose you don't know what you are doing. Suppose that, in the third step you "parametrize" the recurrence as such (you pick some $a\neq1$):

$$x^2-x+a x^2=1+a x^2$$ $$(a+1)x^2-x=ax^2+1$$ $$x=\frac{ax^2+1}{(a+1)x-1}$$ $$x_{n+1}=\frac{ax_{n}^2+1}{(a+1)x_{n}-1}$$

Does this converge to the same values as Newton's recurrence relation? If not, how can you test for which values of $a$ it does and for which ones it doesn't? And since it converging for a single $a\neq1$ would imply these non-Newton recurrence relations can sometimes work, how far can you push them? For example, $x_{n+1}=x_n^2-1$ most definitely doesn't work. But how can you check to be sure?