 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability-resit/4/a/solution

Let

e_{n} = x_{n} - x_{*}

for the limit

x_{*}

∣ e_{n + 1} ∣ \leq C ∣ e_{n} ∣^{2}

for a fixed constant

C

; exact asymptotic order two has

∣ e_{n + 1} ∣/∣ e_{n} ∣^{2} \to c

with

0 < c < \infty

For this iteration and

x_{*} = 3

, direct algebra gives

x_{n + 1} - 3 = x_{n} - 6 + \frac{9}{x _{n}} = \frac{( x _{n} - 3 ) ^{2}}{x _{n}} .

Using the stipulated convergence

x_{n} \to 3

, the ratio of successive squared errors is

\frac{∣ e _{n + 1} ∣}{∣ e _{n} ∣ ^{2}} = \frac{1}{∣ x _{n} ∣} ⟶ \frac{1}{3} .

Thus the convergence is quadratic. The iteration is well defined here:

x_{1} = 7/2

, and thereafter

x_{n} > 3

implies

3 < x_{n + 1} < x_{n}

. The initial point is not already the limit, so the error ratio is meaningful.

 New to topics? Read the docs here!