# Item 04

A *fix-point-iteration review*. See Numerical Analysis, 2nd edition by Timothy Sauer.

* Definition 1: The real number $r$ is a fix-point of the function $g(x)$ if $g(r)=r$.
* Algorithm 1: Fixed-Point-Iteration: Let $x_0$ be the initial guess. Compute $x_{i+1} = g(x_i)$, for $i=0,1,2,3,\dots$. Notice that this fixed-point-iteration may or may not converge to $r$.
* Definition 2: Let $e=|r-x_i|$ be the error at iteration $i$. If $0 < \lim_{i \rightarrow \infty} \frac{e_{i+1}}{e_i} = S < 1$, the fixed-point-iteration $x_{i+1} = g(x_i)$ is said to obey linear convergence with rate $S$.
* Theorem 1: Assume that $g(x)$ is continuously differentiable and that $S=|g'(x)|<1$. Then the fixed-point-iteration $x_{i+1}=g(x_i)$ converges at least linearly with rate $S$ to the fixed point $r$ for the initial guesses sufficiently close to $r$.

---

* **Question 1**: Prove that a continuously differentiable function $g(x)$ satisfying $|g'(x)|<1$ on a closed interval cannot have two fixed points on that interval.

__Dem__:

By contradiction, let's asume that $g(x)$ has two fixed points, $x_1$ and $x_2$, with $x_1 \neq x_2$ on the interval $[a,b]$, and that $|g'(x)|< 1 \, \forall (x \in [a,b])$, then we have that:
$$
g(x_1) = x_1 \qquad g(x_2) = x_2 \,.
$$

Given, this two points, by the [mean value theorem](https://en.wikipedia.org/wiki/Mean_value_theorem), there should exist a point $c \in [x_1,x_2]$ so that:
$$
g'(c) = \frac{g(x_1)-g(x_2)}{x_1-x_2} = \frac{x_1-x_2}{x_1-x_2} = 1
$$
as $c \in [x_1,x_2] \Rightarrow c \in [a,b]$, we have a contradiction, since we said that $|g'(x)|<1 \, \forall (x \in [a,b])$.

---

* **Question 2**: Given that $f(x)$ has a root near $x_0$. Derive three different fix-point-iterations that may converge to $f(r)=0$ and state the restrictions of $f(x)$ needed, if any. Assume that $f(x)$ has as many derivatives as you may need.

(1) We have the trivial options (as $x \rightarrow r$):
\begin{align}
0 &= f(x)
\\ x &= \underbrace{\pm f(x) + x}_{g(x)} 
\end{align}
it requires that $|g'(r)| = |\pm f'(r) + 1| \leq 1$, we may choose the sign of $\pm$.

(2) We expand the Taylor series arround $x_0$:
\begin{align}
f(x) &= f(x_0) + f'(x_0)(x-x_0) + \dots
\\  0 &= f(x_0) + f'(x_0)(x-x_0)  \qquad \qquad \text{as $x\rightarrow r$}
\\ f'(x_0)x &= -f(x_0) + f'(x_0) x_0 
\\ x &= -\frac{f(x_0)}{f'(x_0)} + x_0
\\ x &= \underbrace{x_0 - \frac{f(x_0)}{f'(x_0)}}_{g(x_0)} 
\end{align}
Which corresponds to the Newton's method. It doens't have restrictions.

(2) We expand the Taylor series arround $x_0$:
\begin{align}
f(x) &= f(x_0) + f'(x_0)(x-x_0) + \frac{1}{2}f''(x_0)(x-x_0)^2
\\ 0 &= f(x_0) + f'(x_0)(x-x_0) + \frac{1}{2}f''(x_0)(x-x_0)^2 &\text{as $x\rightarrow r$}
\\ 0 &= f'(x_0) + f''(x_0)x - f''(x_0)x_0 &\text{after $\frac{d(\cdot)}{dx}$}
\\ f''(x_0)x &= f''(x_0)x_0 - f'(x_0)
\\ x &= \underbrace{x_0 - \frac{f'(x_0)}{f''(x_0)}}_{g(x_0)}
\end{align}
Which is the [Newton's method in optimization](https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization).

It requires $f''(r)$ to exist, and if we make $|g'(r)| <1$ that results in:
$$
|f'(r) f'''(r)| < |f''(r)|
$$

---

* **Question 3**: Derive a unsuccessful and a successful fix-point-iteration for finding the root of $x^3+x=1$ near $x_0=1$.

Our unsuccessful fix-point-iteration would be:
\begin{align}
x^3+x &= 1
\\ x &= 1-x^3
\\ \text{we make } g(x) &= 1-x^3
\end{align}
it won't converge as $g'(x) = -3x^2$ and $g'(1) = -3$.

Our successful one:
\begin{align}
x^3+x &= 1
\\ x(x^2+1) &= 1
\\ x^2+1 &= \frac{1}{x}
\\ x^2 &= \frac{1}{x}-1
\\ x &= \sqrt{\frac{1}{x}-1}
\\ \text{we make } g(x) &= \sqrt{\frac{1}{x}-1}
\end{align}
it will converge as $g'(x) = -\frac{1}{2} \left( x^{-1}-1 \right)^{-\frac{1}{2}}x^{-2}$ and $g'(1) = 0$.

---

* Algorithm 2: Newton's method: Let $x_0$ be the initial guess. Compute $x_{i+1} = \hat{g}(x_i)$, for $i=0,1,2,3,\dots$, where $\hat{g}=x-(f'(x))^{-1}f(x)$ and $(f'(x))^{-1}$ is the inverse of $f'(x)$, i.e. $(f'(x))^{-1} = 1/f'(x)$.
* Definition 3: Let $e = |r-x_i|$ be the error at iteration $i$. If $\lim_{i \rightarrow \infty} \frac{e_{i+1}}{e_i^2} = M < \infty$, the method is said to be quadratically convergent.

---

* **Question 4**: Prove that Newton's method is quadratically convergent as long as $f'(r) \neq 0$.

**Dem**:

We have that $g(x) = x - \frac{f(x)}{f'(x)}$. Expanding a Taylor's series around $r$:
\begin{align}
g(x_i) &= g(r) + g'(r)(x_i-r) + \frac{1}{2}g''(r)(x_i-r)^2 + \dots 
\\ x_{i+1} &= r + g'(r)(x_i-r) + \frac{1}{2}g''(r)(x_i-r)^2 + \dots
\end{align}

We can see that:
\begin{align}
g'(x) &= 1 - \frac{f'(x)f'(x)-f(x)f''(x)}{(f'(x))^2}
\\ g'(r) &= 1 - \frac{f'(r)f'(r)-f(r)f''(r)}{(f'(r))^2}
\\ &= 1 - \frac{f'(r)f'(r)}{(f'(r))^2} = 1-1 = 0
\end{align}

So, retaking the previous equation:
\begin{align}
g(x_i) &= g(r) + g'(r)(x_i-r) + \frac{1}{2}g''(r)(x_i-r)^2 + \dots 
\\ x_{i+1} &= r \frac{1}{2}g''(r)(x_i-r)^2 + \dots
\\ x_{i+1}-r &= \frac{1}{2}g''(r)(x_i-r)^2 + \dots
\\ \frac{x_{i+1}-r}{(x_i-r)^2} &= \frac{1}{2}g''(r) + \dots
\\ \frac{e_{i+1}}{e_i^2} &= \frac{1}{2}g''(r) + \dots
\end{align}

And the method has quadratic convergence at rate $M = \frac{1}{2}g''(r)$.

---

* **Question 5**: Explain when Newton's method show linear convergence and also explain how it can be fixed.

When $f'(r)=0$ we have that:
\begin{align}
g'(x) &= 1 - \frac{f'(x)f'(x)-f(x)f''(x)}{(f'(x))^2}
\\ &= 1-\frac{{(f'(x))^2}}{{(f'(x))^2}}+\frac{f(x)f''(x)}{(f'(x))^2}
\\ &= 1-1+\frac{f(x)f''(x)}{(f'(x))^2}
\\ &= \frac{f(x)f''(x)}{(f'(x))^2}
\end{align}
using L'Hopital (because $f(r)=0$ too).
\begin{align}
g(r) &= \frac{f'(r)f''(r)+f(r)f'''(r)}{2f'(r)f''(r)} 
\\ &= \frac{1}{2}+\frac{f(r)f'''(r)}{2f'(r)f''(r)}
\\ &= \frac{1}{2}+\frac{f(r)f'''(r)}{2f'(r)f''(r)}
\\ &= \frac{1}{2}+\frac{f'(r)f'''(r)+f(r)f^{(4)}(r)}{2f''(r)f''(r)+2f'(r)f'''(r)}
\\ &= \frac{1}{2}+' \qquad \text{as long as $f''(x)\neq 0$}
\end{align}
we see that the method has linear convergence because $|g'(r)|=\frac{1}{2} \neq 0$.

If we make our $g(x)= x - \alpha \frac{f'(x)}{f''(x)}$, we will see that the derivate will be:
\begin{align}
g'(x) &= 1 - \alpha\frac{f'(x)f'(x)-f(x)f''(x)}{(f'(x))^2}
\\g'(r) &= 1 - \alpha \left(1-\frac{1}{2} \right)
\end{align}
and we just have to make $\alpha = 2$ so that $g'(x)=0$. In general, we have to make $a$ equal to the multiplicity of the root 


```python

```

e33750fbe8c7ea23ed202552b94db2bc798af027
ipynb
Jupyter Notebook
t1_questions/item_04.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
t1_questions/item_04.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
t1_questions/item_04.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
Qwen/Qwen-72B
1. YES
2. YES