Consider the equation $f(x) = xe^x-1=0$. We wanna solve it using successive approx method, solving the fix point problem $x=e^{-x}$
I don't understand Banach's theorem, how can I solve this? Any idea, hints, steps?
from $f(x)=0$, I have $-x = \ln x$;
This is a classical problem in numerical analysis. It seeks to teach the student that not all iterations are equally useful and that alternatives should be explored. Here there are at least two possibilities to explore. Specifically,
The first iteration is doomed to fail as $\ln$ is only defined for positive values of $y$.
The second iterations is much more favorable. First of all, it is well defined because $h$ maps $\mathbb{R}$ into $\mathbb{R}$. But much more is true.
Specifically, we have \begin{equation} \mathbb{R} \overset{h}{\rightarrow} (0,\infty) \overset{h}{\rightarrow} (0,1) \overset{h}{\rightarrow} (e^{-1},1) \subset [e^{-1},1] \overset{h}{\rightarrow} [e^{-1}, e^{-e^{-1}}] \subset [e^{-1},1]. \end{equation} It follows that $h$ maps $I = [e^{-1},1]$ into itself. The chain of reasoning hinges on the fact that $h$ is decreasing.
Moreover, the restriction of $h$ to the interval $I$ is a contraction. We prove this by showing that there exists $L \in (0,1)$ such that $|h'(z)| \leq L$ and then one would follow through by applying the mean value theorem to show that \begin{equation} |h(u) - h(v)| \leq L |u-v| \end{equation} for any $u,v \in I$. As for the derivative itself, we have $h'(z) = -e^{-z}$, so $|h'(z)| \leq e^{-e^{-1}} < 1$ for all $z$. It follows that $L = e^{-e^{-1}} <1 $ will suffice.
At this point we could deploy Banach's theorem to show that the fixed-point iteration $z_{k+1} = h(z_k)$ is convergent and that the limit lies in $I$. The strength of Banach's theorem is that it frees us from exhibiting the limit and proving convergence. Without Banach's theorem we must do so manually.
We now show that there exists a unique point $\xi \in I$ such that $\xi = h(\xi)$. To that end we define an auxiliary function $\phi : I \rightarrow \mathbb{R}$ given by $\phi(z) = z - h(z)$. It is clear that $\phi(e^{-1}) = e^{-1} - e^{-e^{-1}} < 0$ and $\phi(1) = 1 - e^{-1} > 0$. By continuity, $\phi$ must have at least one zero in $I$. This zero is necessarily unique, because $\phi$ is strictly increasing.
We can now prove manually that $z_{k} \rightarrow \xi$. Without loss of generality, we can assume that $z_0 \in I$. (Otherwise we simply discard the first couple of terms as they can not affect the question of convergence.) Then $z_k \in I$ for all $k$. Since $h(\xi) = \xi$ we have \begin{equation} |\xi - z_{k+1}| = |h(\xi) - h(z_k)| \leq L |\xi - z_k| \end{equation} By induction of $k$ we conclude that \begin{equation} |\xi - z_{k}| \leq L^k |\xi - z_0| \end{equation} It follows that $z_k \rightarrow \xi$ as $k \rightarrow \infty$, because $L < 1$.