2

Assume $f:[a,b]\to\mathbb R$ is twice differentiable and $f'f''\not=0$ on the interval. Assume $f(a)<0<f(b)$. Let $x_0$ be the point of intersection of the $x$-axis with the line through the points $(a,f(a))$ and $(b,f(b))$. Assume for definiteness that $f''>0$. Let $$x_{n+1}=x_n-\frac{f(x_n)}{f(b)-f(x_n)}(b-x_n)$$

How can we see the sequence is monotonic?

p.s. If $f''<0$ we would have $a$ in place of $b$ in the formula.

Attempt: As in the deleted answer from "Mammoth," by the mean value theorem $f(b)-f(x_n)=f'(c_n)(b-x_n)$ for some $c_n\in(x_n,b)$. Therefore, $x_{n+1}-x_n=-\frac{f(x_n)}{f'(c_n)}$. Then $\{x_n\}$ is monotonic exactly when $\frac{f(x_n)}{f'(c_n)}$ does not change sign. However, $f'$ does not change sign, so $\{x_n\}$ is monotonic exactly when $f(x_n)$ does not change sign.

Alternatively, $f(b)-f(x_n)=f'(c_n)(b-x_n)$ for some $c_n\in(x_n,b)$. Therefore, $$x_{n+1}=x_n-\frac{f(x_n)}{f(b)-f(x_n)}(b-x_n)=x_n-\frac{f(b)+f(x_n)-f(b)}{f(b)-f(x_n)}(b-x_n)=b-\frac{f(b)}{f'(c_n)}$$ So $$x_{n+1}-x_n=-f(b)[\frac1{f'(c_n)}-\frac1{f'(c_{n-1})}]$$

Now, $x_n$ is monotonic exactly when $f(c_n)$ is monotonic. Since $f'$ is strictly monotonic this is equivalent to the sequence $c_n$ being monotonic.

EDIT: I have the geometrical intuition but really, I would appreciate an analytical proof.

superAnnoyingUser
  • 4,379

2 Answers2

2

Assume $f(a)<0<f(b)$ and $f'(x)>0$, $\>f''(x)>0$. Then convexity implies $f(x_0)<0$, since the graph of $f$ is below the secant connecting $\bigl(a,f(a)\bigr)$ and $\bigl(b,f(b)\bigr)$. According to the recursion formula the point $x_1$ is the point where the line connecting $\bigl(x_0,f(x_0)\bigr)$ and $\bigl(b,f(b)\bigr)$ intersects the $x$-axis (check this!). It follows that $x_1>x_0$. Moreover we are now in the situation we were in at the start, with $a$ replaced by $x_0$. By induction it follows that the $x_n$ form an increasing sequence with $f(x_n)<0$ for all $n$, and it should not be difficult to show that $\xi:=\lim_{n\to\infty} x_n$ is the unique zero of $f$ in $[a,b]$.

Christian Blatter
  • 226,825
0

Perhaps I miss something, but this is a counter example : let $$f :[-1,1] = x\mapsto -x^2+3x$$

$f'$ and $f''$ have no zeros in $[-1,1]$.

Then $x_0=\frac{1}{3}$, $x_1=\frac{-1}{5}$ and $x_2=\frac{1}{11}$, that is not monotonic !

Xoff
  • 10,310
  • Ah, you are not missing anything, I am missing part of the conditions. The thing is, if $f''<0$, then the formula for $x_{n+1}$ should have the point $a$ instead of the point $b$. – superAnnoyingUser Jul 10 '14 at 06:37