Problem 5 - Numerical Computing

Let us find $\sqrt{a} \; (a>0)$ using Newton's method.

1.

Give the Newton iteration for the equation $f(x)=x^2-a=0$ and analyze the convergence behavior of the $n$-th approximation $x_n$ to $\sqrt{a}$. Assume $x_0 > 0$.

2.

Give the Newton iteration for the equation $g(x)=x - \frac{a}{x}=0$ and analyze the convergence behavior of the $n$-th approximation $x_n$ to $\sqrt{a}$. Assume $x_0 > 0$.

3.

Let $z_{n+1}$ be the arithmetic mean of the $x_{n+1}$ given by the above question 1. and the $x_{n+1}$ given by the above question 2., assuming the same $x_n$. Analyze the error of $z_{n+1}$.

1.

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^2 - a}{2x_n} = \frac{x_n^2 + a}{2x_n}$
$e_n = \vert x_n - \sqrt{a}\vert$
$e_{n+1} = \vert x_{n+1} - \sqrt{a}\vert = \left\vert\frac{x_n^2 + a}{2x_n} - \... ... + a}{2x_n}\right\vert = \left\vert \frac{(x_n - \sqrt{a})^2}{2x_n} \right\vert$
$\frac{e_{n+1}}{e_n^2} = \frac{1}{2x_n} \xrightarrow[n\rightarrow +\infty]{} \frac{1}{2\sqrt{a}}$
Thus, the $n$-th approximation converges quadratically.

2.

$x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)} = x_n - \frac{x_n - \frac{a}{x_n}}{1+\f... ...}{x_n}} = \frac{x_n^3 + ax_n - x_n^3 + ax_n}{x_n^2 + a} = \frac{2ax_n}{x_n^2+a}$
$e_n = \vert x_n - \sqrt{a}\vert$
$e_{n+1} = \vert x_{n+1} - \sqrt{a}\vert = \left\vert\frac{2ax_n}{x_n^2+a} + \f... ...a}\right\vert = \left\vert \frac{-\sqrt{a}(x_n-\sqrt{a})^2}{x_n^2+a}\right\vert$
$\frac{e_{n+1}}{e_n^2} = \frac{\sqrt{a}}{x_n^2+a} \xrightarrow[n\rightarrow \infty]{} \frac{\sqrt{a}}{2a}$
Thus, the $n$-th approximation converges quadratically.

3.

$z_{n+1} = \frac{1}{2}\left(\frac{x_n^2 + a}{2x_n} + \frac{2ax_n}{x_n^2+a}\right) = \frac{1}{2}\left(\frac{4ax_n^2+x_n^4 + 2x_n^2a + a^2}{2x_n^3 + 2ax_n}\right)$
$= \frac{1}{2}\left(\frac{(x_n^2 + a)^2+4ax_n^2}{2x_n(x_n^2+a)}\right)$