Consider we're applying Newton's method to a complex function (I don't think the function matters …) $f(x) = x^n-pw x^{n-1}- p w^{-1} x -1 + 2p$ with $0<p<1$ and $w=e^{2\pi i /n}$ (we want to find $\lambda$ such that $\lambda^n-pw \lambda^{n-1}- p w^{-1} \lambda -1 + 2p=0$):
$$x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}$$
with $x_0=1$.
By Taylor's theorem,
\begin{equation*}
|f(x_{i+1})| \leq \frac{1}{2} \max_{0 \leq u \leq 1} |f''(u x_i + (1-u) x_{i+1})| \ \left|\frac{f(x_i)}{f'(x_i)}\right|^2.
\end{equation*}
Where does this bound come from?
What I've done:
Suppose the method converges to a root $x^*$. This root can be expressed as a convex combination of $x_i$ and $x_{i+1}$, that is, $x^* = u x_i + (1-u) x_{i+1}$. Let $\delta_i = |x^* – x_{i+1}| \leq |x_{i+1}-x_i| = \left| \frac{f(x_i)}{f'(x_i)}\right|.
\\
$By Taylor's theorem, since $f(x^*)=0$,
$$ f(x_{i+1})=f'(x^*)\delta_i + \frac12 f''(x^*)\delta_i^2 \leq f'(x^*)\delta_i + \frac12 f''(x^*)\left| \frac{f(x_i)}{f'(x_i)}\right|^2.$$
It is very close from what I want, but I don't know how to get rid of $f'(x^*)$.
I don't know if it helps, but this comes from Lemma $3$ of this paper.
Best Answer
You are right that the specific function doesn't matter here, you only need it to be regular enough (and your function is smooth because it's a polynomial).
Fix $i\geq 0$. Taylor's theorem with Lagrange's remainder states that $$f(x_{i+1}) = f(x_i) + f'(x_i)(x_{i+1}-x_i) + \frac 1 2 f''(\xi_u)(x_{i+1}-x_i)^2$$ for some $\xi_u = ux_i+(1-u)x_{i+1}$ and some $u \in (0,1)$. But since $f'(x_i) \neq 0$ we get $$f(x_i) + f'(x_i) (x_{i+1} -x_i) = f(x_i) + f'(x_i)\left(- \frac{f(x_i)}{f'(x_{i})} \right) =0, $$ so $$|f(x_{i+1})| = \frac 1 2 |f''(\xi_u)| |x_{i+1} - x_i|^2 \leq \frac1 2M\left|\frac{f(x_i)}{f'(x_{i})}\right|^2, $$ where $M := \max_{0\leq u \leq 1} |f''(\xi_u)|$. Is this what you were looking for?