Iterative Methods [H]
Iterative Methods
When an equation cannot be solved exactly by algebraic methods, a numerical approach called iteration produces a sequence of values that converge toward the solution. A recursive (iterative) formula of the form \( x_{n+1} = f(x_n) \) generates each new approximation from the previous one. Starting from an initial estimate \( x_0 \) (or \( x_1 \)), repeated substitution produces values that (when the formula is well-chosen) home in on the true root.
Suffix Notation
The subscript \( n \) is an index — \( x_n \) is the \(n\)-th approximation. The formula \( x_{n+1} = f(x_n) \) says: "the next approximation is found by applying the function \( f \) to the current approximation." This is applied repeatedly:
\[ x_1 \xrightarrow{f} x_2 \xrightarrow{f} x_3 \xrightarrow{f} x_4 \xrightarrow{f} \cdots \to \text{root} \]Why Iteration Works
To solve \( g(x) = 0 \), rearrange into the form \( x = f(x) \). A fixed point of \( f \) — a value where \( f(x) = x \) — is a solution to the original equation. The iteration converges when the gradient of \( f \) at the fixed point has magnitude less than 1.
Verifying a Root to a Given Accuracy
To show a root lies in an interval \( [a, b] \) to a stated number of decimal places:
- Identify the interval of width \( 10^{-d} \) centred on the claimed root (where \( d \) is the number of d.p.).
- Show \( g(a) \) and \( g(b) \) have opposite signs — this proves a root lies between them by the change-of-sign principle.
Worked Examples
Use the formula \( x_{n+1} = \dfrac{2}{x_n^2} + 1 \) with \( x_1 = 1.5 \) to find \( x_2 \), \( x_3 \) and \( x_4 \) to 4 d.p.
\[ x_2 = \frac{2}{1.5^2}+1 = \frac{2}{2.25}+1 = 0.8889+1 = 1.8889 \] \[ x_3 = \frac{2}{1.8889^2}+1 = \frac{2}{3.5679}+1 = 0.5606+1 = 1.5606 \] \[ x_4 = \frac{2}{1.5606^2}+1 = \frac{2}{2.4355}+1 = 0.8213+1 = 1.8213 \]The values are converging (oscillating) toward the fixed point. Continuing the iteration would yield greater precision.
Show that the equation \( x^3 + x - 5 = 0 \) can be written as \( x = \sqrt[3]{5-x} \) and hence find an iterative formula.
\[ x^3 = 5-x \implies x = \sqrt[3]{5-x} \]Iterative formula: \( x_{n+1} = \sqrt[3]{5-x_n} \). Starting from \( x_1 = 1.5 \):
\[ x_2 = \sqrt[3]{5-1.5} = \sqrt[3]{3.5} \approx 1.5183 \] \[ x_3 = \sqrt[3]{5-1.5183} \approx \sqrt[3]{3.4817} \approx 1.5164 \]The sequence converges to approximately \( x \approx 1.516 \).
Show that the equation \( x^3 + x - 5 = 0 \) has a root between 1.5 and 1.52, and that it rounds to 1.52 to 2 d.p.
Let \( g(x) = x^3 + x - 5 \).
\[ g(1.5) = 3.375 + 1.5 - 5 = -0.125 quad (\text{negative}) \] \[ g(1.52) = 3.5118 + 1.52 - 5 = 0.032 quad (\text{positive}) \]Sign change in \( [1.5, 1.52] \) confirms a root in this interval. To verify it rounds to 1.516 to 3 d.p.: check \( g(1.5155) < 0 \) and \( g(1.5165) > 0 \) (sign change across the rounding boundary).
Key Takeaways
- Iterative formula \( x_{n+1} = f(x_n) \): substitute the current approximation to get the next one. Repeat until values stabilise to the required accuracy.
- Suffix notation: \( x_n \) is the \(n\)-th approximation. \( x_1 \) (or \( x_0 \)) is the starting value given in the question.
- To rearrange an equation into iterative form: rewrite \( g(x) = 0 \) as \( x = f(x) \) by isolating \( x \) on one side.
- Change-of-sign test: if \( g(a) \) and \( g(b) \) have opposite signs and \( g \) is continuous, a root lies between \( a \) and \( b \).
- To verify a root to \( d \) decimal places, show a sign change across the \( d \)th decimal place boundary (e.g. \( [1.515, 1.525] \) for a root of 1.52 to 2 d.p.).