Problem 8 - Numerical Computing

Put appropriate words/number in $(A)\sim(I)$.

1.

Concerning the Newton method for a nonlinear equation $f(x)=\frac{1}{x}-a=0\; (a>0)$, when the initial value is set in the interval $(A)$, it converges to $x=\frac{1}{a}$ with the order of convergence $(B)$.

2.

Apply the trapezoidal formula to the integral $I=\int_0^1 e^x dx$ by dividing the interval into $N$ equal bins. The truncation error is proportional to $N$ to the power $(C)$.

3.

When solving an ordinary differential equation $\frac{dy}{dx}=-2xy, y(0)=1$ by the forward Euler method with interval $h$, the truncation error at $x=1$ is proportional to $h$ to the power $(D)$.

4.

(Choose appropriate words by greek letters from the candidates shown below. If multiple candidates are applicable, select the rightmost one.)

• The inverse of a nonsingular upper triangular matrix is (E).
• The inverse of a nonsingular band matrix is (F).
• The product of an upper triangular matrix and a lower triangular matrix is (G).
• The product of a lower triangular matrix and an upper triangular matrix is (H).
• A matrix which is upper and lower triangular is (I). Candidates: $\alpha$) dense matrix, $\beta$) upper triangular matrix, $\gamma$) lower triangular matrix, $\delta$) band matrix, $\epsilon$) diagonal matrix.

1.

$x_{n+1}=x_n - \frac{\frac{1}{x_n}-a}{-\frac{1}{x_n^2}} = 2x_n - ax_n^2$
$e_n = \vert x_n - \frac{1}{a}\vert$
$e_{n+1} = \vert x_{n+1} - \frac{1}{a}\vert=\vert 2x_n - ax_n^2 -\frac{1}{a}\vert=a\left( x_n - \frac{1}{a}\right)^2$
$e_{n+1}/e_n^2 = a$
Thus $(B) = 2$.
$e_{n+1} = a e_n^2 = a e_0^{2^{n+1}}$
$\vert a(x_0 - \frac{1}{a})\vert < 1 \Leftrightarrow \vert x_0 - \frac{1}{a}\vert < \frac{1}{a}$
Thus $(A) = [0,\frac{2}{a}]$.

2.

$\int_{x_i}^{x_{i+1}} e^x dx = \frac{1}{2}(x_{i+1} - x_i)(e^{x_i} + e^{x_{i+1}})$
If $x_{i+1} - x_i = \frac{1}{N} = h$, the step lenght, then, the composite trapezium rule gives:
$\int_0^1 e^x dx \approx \frac{1}{2}h(e^0 + 2(e^h + e^{2h} + \cdots + e^{1-h}) + e^1) = I_T(n)$
According to Hildebrand, with $x_i < \xi_i < x_{i+1}$:
$\int_{x_i}^{x_{i+1}} e^x dx = \frac{1}{2}h(e^{x_i} + e^{x_{i+1}}) - \frac{1}{12}h^3 f''(\xi_i)$
$\int_0^1 e^x dx = I_T(n) - \frac{1}{12}h^3 \sum_{i=0}^{n-1} f''(\xi_i) = I_T(n) - \frac{1}{12}h^2f''(\xi)$
With $0< \xi <1$ and $\sum_{i=0}^{n-1} f''(\xi_i) = N f''(\xi)$.
$\left\vert \hbox{Error in trapezium rule}\right\vert < \frac{1}{12}\frac{1}{N^2}\max_{0 \leq x \leq 1}\vert f''(x)\vert$
Thus $(C) = -2$.

3.

$y(x_{r+1}) = y(x_r) + hy'(x_r) + \frac{h^2}{2}y''(x_r) + O(h^3)$
$y(x_{r+1}) \approx y(x_r) - 2 h x_r y(x_r)$
$y_{r+1} = y_r - 2 h x_r y_r$
$y(x_{r+1}) - y_{r+1} = \frac{h^2}{2}y''(x_r) + O(h^3)$
In particular: $y(1) - y_{r_i + 1} = - h^2 y_{r_i} + O(h^3)$
Thus $(D) = 2$.

4.