1

So I have been reading numerical analysis and I encountered this:

Assume that $ g $ is continuously differentiable, $ x ^ * = g ( x ^ * ) $, $ g ' ( x ^ * ) \ne 0 $, $ g ' ( x ^ * ) \ne 1 $. Previously given formula does not define $ \phi ( x ^ * ) $ as for $ x = x ^ * $ the value of the denominator is $ 0 $. Define $ \phi ( x ^ * ) = x ^ * $. Let us find $ \phi ' ( x ^ * ) = \lim \limits _ { x \to x ^ * } \dfrac { \phi ( x ) - \phi ( x ^ * ) } { x - x ^ * } $. According to Lagrange's formula, $$ g \big( g ( x ) \big) - g ( x ) = g ' ( \xi ) \big( g ( x ) - x \big) \text , \qquad \xi \in \big( x , g ( x ) \big) \text , $$ and if $ x \to x ^ * $, then $ g ( x ) \to g ( x ^ * ) = x ^ * $, hence $ \xi \to x ^ * $. Therefore $$ \begin {align*} \phi ( x ) & = \frac { x g \big( g ( x ) \big) - x g ( x ) + x g ( x ) - g ( x ) ^ 2 } { g \big( g ( x ) \big) - g ( x ) - \big( g ( x ) - x \big) } = \\ & = \frac { x g ' ( \xi ) \big( g ( x ) - x \big) - g ( x ) \big( g ( x ) - x \big) } { \big( g ' ( \xi ) - 1 \big) \big( g ( x ) - x \big) } = \\ & = \frac { x g ' ( \xi ) - g ( x ) } { g ' ( \xi ) - 1 } \text , \end {align*} $$ and to abtain the last equality, we use the fact that $ g ( x ) \ne 0 $ for $ x \ne x ^ * $, which holds if $ x $ is in a small enough neighborhood of $ x ^ * $ taking into account $ g ' ( x ^ * ) \ne 0 $. Using the expansion $ g ( x ) = g ( x ^ * ) + g ' ( \xi _ 1 ) ( x - x ^ * ) $, $ \xi _ 1 \in ( x , x ^ * ) $ where we also substitute $ g ( x ^ * ) $ with $ x ^ * $, we get $$ \begin {align*} \phi ( x ) - \phi ( x ^ * ) & = \frac { x g ' ( \xi ) - g ( x ) } { g ' ( \xi ) - 1 } - x ^ * = \\ & = \frac { x g ' ( \xi ) - x ^ * - g ' ( \xi _ 1 ) ( x - x ^ * ) - x ^ * g ' ( \xi ) + x ^ * } { g ' ( \xi ) - 1 } = \\ & = \frac { \big( g ' ( \xi ) - g ' ( \xi _ 1 ) \big) ( x - x ^ * ) } { g ' ( \xi ) - 1 } \text . \end {align*} $$ Now $$ \lim _ { x \to x ^ * } \frac { \phi ( x ) - \phi ( x ^ * ) } { x - x ^ * } = \lim _ { x \to x ^ * } \frac { g ' ( \xi ) - g ' ( \xi _ 1 ) } { g ' ( \xi ) - 1 } = \frac { g ' ( x ^ * ) - g ' ( x ^ * ) } { g ' ( x ^ * ) - 1 } = 0 \text , $$ which means that $ \phi ' ( x ^ * ) = 0 $ and under such assumptions Steffensen's method converges faster than any geometric progression.

I don't understand why can say $ g ( x ) \to g ( x ^ * ) = x $.

Because I think everything is correct but I am not quite sure why I can say that one specific thing.

Mohsen Shahriari
  • 6,718
John.Doh
  • 101
  • 5

1 Answers1

1

This is not exactly Steffensens method for root finding $f(x)=0$, as that looks like $$ x_+=x-\frac{f(x)^2}{f(x+f(x))-f(x)} $$ Your formula uses the (admittedly closely related) Aitken's delta-squared process for speeding up convergence of linearly convergent fixed-point iterations. $$ x_+=\phi(x)=x-\frac{(\Delta_g x)^2}{\Delta_g^2x}=x-\frac{(g(x)-x)^2}{g(g(x))-2g(x)+x} $$ Both formulas are Newton-like steps, thus one can not in general guarantee convergence. But as in the case of the secant method, one can under the assumption of convergence make claims on the speed of convergence.

As we assume that $x_n\to x^*$, the continuity of $g$ provides $g(x_n)\to g(x^*)$.

In the Steffensen case $f$ twice continuously differentiable one can directly see, employing Taylor expansions around $x$, \begin{align} f(x+a)&=f(x)+f'(x)a+\frac12f''(x+\theta a)a^2\\ f(x+f(x))&=f(x)+f'(x)f(x)+\frac12f''(\bar x)f(x)^2\\ 0=f(x^*)&=f(x)+f'(x)(x^*-x)+\frac12f''(\tilde x)(x^*-x)^2\\[2em]\hline \phi(x)&=x+\frac{f'(x)(x^*-x)+\frac12f''(\tilde x)(x^*-x)^2}{f'(x)+\frac12f''(\bar x)f(x)}\\[1em] &=x^*+\frac12(x-x^*)\frac{f''(\tilde x)(x-x^*)+f''(\bar x)f(x)}{f'(x)+\frac12f''(\bar x)f(x)} \end{align} where the second term is $O((x-x^*)^2)$ or semi-precisely $$\phi(x)-x^*\approx\frac{f''(x^*)(1+f'(x^*))}{2f'(x^*)}(x-x^*)^2 $$

As both methods are connected by $f(x)=g(x)-x$, the same quadratic convergence applies to the Aitken process.

Lutz Lehmann
  • 126,666