Question about newton's interpolation and rootfinding Suppose we want to solve $f(x) = 0$. We start from the newtons interpolation formula on two points, say $x_n$ and $x_{n-1}$.


${\bf Attempt.}$ Since we are given two points say $(x_n, y_n)$ and $(x_{n-1},y_{n-1})$, the Newton interpolant is given by
  $$ p_1(x) = y_{n-1}  + \frac{y_n - y_{n-1}}{x_n-x_{n-1} } (x-x_{n-1}) $$
  In terms of divided differences, we have $p_1(x) = f[x_{n-1}] + f[x_{n-1},x_n] (x-x_{n-1})$. How can we express the exact $f$? Im kind of confused on this question.
  Next, notice that 
  $$ p_1(x_{n+1}) = y_{n-1}  + \frac{y_n - y_{n-1}}{x_n-x_{n-1} } (x_{n+1}-x_{n-1})  =0$$
  So, $$ y_{n-1} (x_n - x_{n-1}) = (x_{n-1} - x_{n+1} )(y_n -y_{n-1} ) $$
$$x_{n+1} (y_n-y_{n-1}) = x_{n-1}(y_n - y_{n-1}) + y_{n-1} x_{n-1} - y_{n-1} x_n $$
$$ x_{n+1} = \frac{x_{n-1} f(x_n) - x_n f(x_{n-1}) }{f(x_n) - f(x_{n-1}) } $$
  which is the algorith for secant method. This gives (b). For part c), I have a question, by $p_2$, does this mean the newton interpolant polynomial of degree 2? So, if so, if $x_{n+1}$ is approximate root and $\xi$ is the exact root, then we have using part b)
  \begin{align*}
x_{n+1} - \xi &= \frac{x_{n-1} f(x_n) - x_n f(x_{n-1}) }{f(x_n) - f(x_{n-1}) } - \xi \\
&= \frac{x_{n-1} f(x_n) - x_n f(x_{n-1}) - \xi(f(x_n) - f(x_{n-1}) ) }{f(x_n) - f(x_{n-1}) } \\
&= \frac{ f(x_n)( x_{n-1} - \xi) - f(x_{n-1}) (x_n - \xi) }{f(x_n) - f(x_{n-1}) } \\
\end{align*}
  here I get stuck as I dont see a way to expres products of errors as required. I see $A$ will involve the $f(x_{n}), f(x_{n-1})$, how do we derive this?

 A: Let $\xi$ denote the root and let $x_0 \not = x_1$ denote the initial approximation. We assume that $f(x_1) \not = f(x_2)$ such that the secant step
$$x_2 = x_1 - \frac{x_1 -x_0}{f(x_1)-f(x_0)} f(x_1) = x_1 - \frac{f(x_1)}{f[x_0,x_1]}$$ is well-defined. Let $e_i = \xi - x_i$ denote the error at the $i$th iteration. Our goal is develop an error formula which connects $e_2$ to $e_1$ and $e_0$. We have 
\begin{align}
e_2 &= \xi - x_2 = \xi - x_1 + \frac{f(x_1)}{f[x_0,x_1]} = e_1  - \frac{f(\xi)-f(x_1)}{f[x_0,x_1]} = e_1 - \frac{f[x_1,\xi]e_1}{f[x_0,x_1]}  \\ &= e_1 \left(1 - \frac{f[x_1,\xi]}{f[x_0,x_1]}\right) = - e_1 \left( \frac{f[x_1,\xi]-f[x_0,x_1]}{f[x_0,x_1]} \right) = -e_1 e_0 \frac{f[x_0,x_1,\xi]}{f[x_0,x_1]}
\end{align}
A sanity check is in order before we proceed. In the limit where $x_0 \rightarrow x_1$, the secant step becomes a Newton step and $e_1 \rightarrow e_0$. Our formula reduces to 
$$ e_2 = - e_0^2 \frac{f[x_0,x_0,\xi]}{f'(x_0)} = -\frac{1}{2} e_0^2  \frac{f''(\theta)}{f'(x_0)},$$
for at least one value of $\theta$. In other words, we recover the error formula for Newton's method.

In general, we have
$$e_{n+1} =  -e_n e_{n-1} \frac{f[x_{n-1},x_n,\xi]}{f[x_{n-1},x_n]}.$$
In the event of convergence, we have 
$$ f[x_{n-1},x_n] \rightarrow f'(\xi), \quad n\rightarrow \infty, \quad n \in \mathbb{N} $$ and $$ f[x_{n-1},x_n,\xi] \rightarrow \frac{1}{2} f''(\xi), \quad n\rightarrow \infty.  \quad n \in \mathbb{N}$$
We make the natural assumptions that $f'(\xi) \not = 0$ and $f''(\xi) \not = 0$ and define $$A = - \frac{1}{2}\frac{f''(\xi)}{f'(\xi)}$$ This definition allows us to write 
$$ e_{n+1} \approx A e_{n} e_{n-1}$$
but we cannot expect equality as this is only an approximation. Many texts will ignore this distinction and simply proceed from $$e_{n+1} = A e_{n} e_{n-1}.$$ We shall not make this mistake. Instead, we exploit the fact that
$$ \left| \frac{f[x_{n-1},x_n,\xi]}{f[x_{n-1},x_n]} \right| \rightarrow |A|, \quad n\rightarrow \infty, \quad n \in \mathbb{N}.$$
Given $\epsilon > 0$, there exists $N = N(\epsilon)$ such for all $n \ge N$ we have
$$ \left| \frac{f[x_{n-1},x_n,\xi]}{f[x_{n-1},x_n]} \right| \leq |A| + \epsilon =: C(\epsilon).$$
In reality, there is no harm in assuming that $N=1$. If necessary, we simply discard the first finitely many approximations and renumber the rest. From our error formula we deduce
$$ |e_{n+1}| \leq |e_n||e_{n-1}| C(\epsilon).$$
It follows that 
$$ C(\epsilon) |e_{n+1}| \leq (C(\epsilon) |e_n|) (C(\epsilon) |e_{n-1}|).$$
At this point we pause to recognize that we must have
$$ C(\epsilon) |e_n| \leq g_n$$
where 
$$ g_0 = C(\epsilon) |e_0|, \quad  g_1 = C(\epsilon) |e_1|, \quad g_{n+1} = g_{n} g_{n-1}.$$
We now impose the vital conditions that $$g_0 < 1, \quad g_1 < 1$$ to ensure $$g_n \rightarrow 0_+, \quad n \rightarrow \infty, \quad n \in \mathbb{N}.$$
This is what we will mean when we say that $x_0$ and $x_1$ are sufficiently close to $\xi$.

By applying the logarithm we find the Fibonacci sequence
$$ \log g_{n+1} = \log g_{n} + \log g_{n-1},$$
We have
$$ \log g_n = a_0 \lambda^n + a_1 \mu^n $$ 
where
$$ \lambda = \frac{1+\sqrt{5}}{2}, \quad \mu= \frac{1-\sqrt{5}}{2} $$
and 
$$ \begin{bmatrix} 1 & 1 \\ \lambda & \mu \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} \log g_0 \\ \log g_1 \end{bmatrix}. $$
We have 
$$
\begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \frac{1}{\mu - \lambda} \begin{bmatrix} \mu & -1 \\ -\lambda & 1 \end{bmatrix} \begin{bmatrix} \log g_0 \\ \log g_1 \end{bmatrix}.
$$
so $a_0 < 0$. We stress that $a_0 < 0$ also follows from $g_n \rightarrow 0_+$, because $\lambda > 1$ and $|\mu| < 1$. We can now conclude
$$ |e_n| \leq \frac{1}{C(\epsilon)} \exp( a_0 \lambda^n + a_1 \mu^n) $$
At this point, we are very nearly done. We consider the right hand side expression and define 
$$ y_n = \frac{1}{C(\epsilon)} \exp( a_0 \lambda^n + a_1 \mu^n).$$
Then $$\frac{y_{n+1}}{y_n^\lambda} = C(\epsilon)^{\lambda-1} \frac{\exp( a_0 \lambda^{n+1} + a_1 \mu^{n+1})}{\exp( a_0 \lambda^{n+1} + a_1 \lambda \mu^n).} \rightarrow C(\epsilon)^{\lambda-1} \not = 0, \quad n \rightarrow \infty$$
This shows that the auxiliary sequence $y_n$ converges to zero and the order is $\lambda$. By definition, it follows that $|e_n|$ converges to zero with order at least $\lambda$.
 I have a few comments regarding the original exercise which prompted the question above. I have no idea what $p_2$ is. The text contains a few oddities and it is plausible that $p_2$ is simply a typographical error. Subquestion (c) asks for a conclusion which is not entirely correct. I have supplied the correct answer. Subquestion (d) asks for a conclusion which is not entirely correct. I have pushed the analysis as far as I can. The underlying issue is fundamental. The mathematical definition of order $p$ convergence is beautiful, but essentially useless for the analysis of some algorithms such as the secant method and even bisection. Newton's method is the only exception which comes to mind. Why? Normally, we work with upper bounds for the error and we can show that the upper bounds decay to zero with order $p$. In such cases, we say that the original errors tend to zero with an order that is at least $p$.
A: Insert the Taylor expansion
$$
f(x_k)=f(ξ+e_k)=0+f'(ξ)e_k+\frac12f''(ξ)e_k^2+...
$$
However, apart from not knowing what $p_2$ is relative to $p_1$, it also does not make systematic use of $p_2(x_{n+1})=0$ as suggested.
