I am solving old exams and I came across the following question:
Let $$ x_{n+1} = x_{n} - \alpha\frac{f(x_{n})}{f'(x_{n})} \;\;,\;\; f(x_{n}) \gt0 \;\;,\;\; f'(x_{n}) \neq0 $$ Is it true that there exists an $0 \lt \alpha \lt 1$ such that $f(x_{n+1}) \lt f(x_{n})$ for all $n$?
I vaguely remember we discussed this in class and the answer was (to my surprise) "yes", but I didn't understand the reason and didn't write the explanation down.
Can you point me in the right direction?
Thanks! :)
Hinit: What you meant is called halley method such that the Algorithm can be written as follow :$$ x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}[1-\frac{f(x_{n})}{f'(x_{n})}\frac{f''(x_{n})}{2f'(x_{n})}]^{-1}$$
Also you can check this pdf page 5 (4.2 Householder’s iteration) may help
you to understand well your modified Algorithm .
Let's expand $f(x_{n+1})$ using Taylor formula with Lagrange remainder term: $$ f(x_{n+1}) = f\left(x_n - \alpha \frac{f(x_n)}{f'(x_n)}\right) = f(x_n) - \alpha f'(x_n) \frac{f(x_n)}{f'(x_n)} + f''(\xi) \frac{\alpha^2 f^2(x_n)}{2(f'(x_n))^2} = \\ =(1 - \alpha) f(x_n) + \frac{\alpha^2}{2}\frac{f^2(x_n)}{(f'(x_n))^2}f''(\xi) \leqslant (1 - \alpha) f(x_n) + \frac{\alpha^2}{2}\frac{f^2(x_n)}{(f'(x_n))^2}M_2 $$ where $M_2 = \max\limits_{\xi \in [a,b]} |f''(\xi)|$. Thus $$ q \equiv \frac{f(x_{n+1})}{f(x_n)} \leqslant 1 - \alpha + \frac{\alpha^2}{2} \frac{f(x_n)}{(f'(x_n))^2} M_2 $$ I state that exists some $\alpha$ that for every $x_n$ the value of $q \in (0, 1)$: $$ \left|q - 1 + \alpha\right| \leqslant \frac{\alpha^2}{2} \frac{f(x_n)}{(f'(x_n))^2} M_2 \leqslant \frac{\alpha^2}{2} \frac{M_0 M_2}{m_1^2} $$ where $m_1 = \max\limits_{\xi \in [a,b]} |f'(\xi)|$ and $M_0 = \max\limits_{\xi \in [a,b]} |f(\xi)|$. Let $\beta \equiv \frac{M_0M_2}{m_1^2}$. Then $$ \left|q - 1 + \alpha\right| \leqslant \frac{\beta \alpha^2}{2}. $$ By taking sufficiently small $\alpha$ we can ensure that $q$ stays in interval $(0,1)$. The actual value for $\alpha$ can be $\alpha = \frac{1}{\beta}$ for $\beta \geqslant 2$ and $\alpha = \frac{1}{2}$ for $\beta < 2$.
Note that uniform value for $\alpha$ depends on uniform estimates for derivatives taken over some domain containing all points $x_n$.
