P3 6.2 - Iterative solutions

Iteration and fixed point

An iteration repeats a calculation using its latest output. In

$x_n$ is the current approximation and $x_{n+1}$ is the next. A fixed point $\alpha$ satisfies $\alpha=g(\alpha)$: the update leaves it unchanged.

Worked example 1: deriving a supplied square-root form

Show that a positive root of $x^2-x-1=0$ satisfies $x=\sqrt{x+1}$, and state the corresponding iteration.

Plan. Isolate $x^2$, then take the positive square root because the required root is positive.

Answer. Use $x_{n+1}=\sqrt{x_n+1}$ from a supplied suitable starting value. The update is real when $x_n\ge-1$.

Check. A positive fixed point satisfies $x^2=x+1$, which rearranges back to $x^2-x-1=0$. Taking the positive square root is justified for this root.

Worked example 2: a changed linear coefficient

Show that a positive root of $x^2-2x-1=0$ satisfies $x=\sqrt{2x+1}$, and state the iteration.

Plan. Isolate the square and use the positive branch again.

Answer. $x_{n+1}=\sqrt{2x_n+1}$, real when $x_n\ge-\frac12$.

Check. Squaring a positive fixed point gives $x^2=2x+1$, exactly the original equation after rearranging. The branch condition rules out introducing a negative fixed value.

Watch out

Write $x_{n+1}=\sqrt{2x_n+1}$, not $x_{n+1}=\sqrt{2n+1}$. The input is the current approximation's value, not its position in the sequence.

Initial approximation

An initial approximation, such as $x_0=1$, starts the iteration. One update gives $x_1$, two updates give $x_2$, and so on. The rule and starting index must both be retained.

Worked example 3: starting below the root

Use $x_{n+1}=\sqrt{x_n+1}$, with $x_0=1$, to find $x_1,x_2,x_3,x_4$ to six decimal places.

Plan. Apply the square-root update four times, carrying unrounded values into each new calculation.

Answer. $1.414214,\ 1.553774,\ 1.598053,\ 1.611848$, respectively.

Check. Reversing the final update gives $x_4^2-1=x_3$, to the working precision. Each listed term is larger than its predecessor in this calculation.

Worked example 4: starting above the root

Use $x_{n+1}=\sqrt{x_n+1}$, with $x_0=1.8$, to find $x_1,x_2,x_3,x_4$ to six decimal places.

Plan. Keep the update unchanged and use the new starting approximation.

Answer. $1.673320,\ 1.635029,\ 1.623277,\ 1.619653$, respectively.

Check. Again $x_4^2-1=x_3$. The values decrease here, while Example 3's increase; both are approaching the same region near $1.618$.

Exam tip

Use the iteration specified in the question. A calculator's equation-solver answer does not show the requested successive approximations. Retain full precision in stored values and display the requested rounding.