Numerical methods: iteration for solving equations

Algebra • Solving equations and inequalities

Flashcards

Test your knowledge with interactive flashcards

Graphical check - purpose

Click to reveal answer

Graphing y=g(x) and y=x provides a visual check because intersections correspond to fixed points and slope near intersection indicates likely convergence.

Key concepts

What you'll likely be quizzed about

Fixed-point iteration: definition and process

Fixed-point iteration rewrites f(x)=0 as x=g(x) and generates a sequence x_{n+1}=g(x_n). Each iteration uses the previous approximation to compute the next approximation and attempts to move closer to a value x* that satisfies x*=g(x*). The iterative process starts from an initial guess x_0. Repeated application of g produces x_1, x_2, x_3, and so on, with the intention that the sequence converges to a fixed point that solves the original equation.

Forming an iterative formula from f(x)=0

Multiple rearrangements of f(x)=0 produce different g(x) functions, so algebraic manipulation selects a suitable g(x) for iteration. Rearrangements such as x = x - k f(x) or isolating x on one side both produce candidate g(x) functions. Choice of rearrangement affects convergence. A rearrangement that simplifies evaluation and yields |g'(x)|<1 near the root increases the chance of convergence.

Convergence criterion and derivative test

Local convergence for fixed-point iteration requires |g'(x)|<1 at the fixed point; the derivative test provides a practical check. If |g'(x*)|<1 then small errors shrink each iteration and the sequence converges locally to x*. If |g'(x*)|>1 then errors tend to grow and the iteration diverges. If |g'(x*)|≈1 then convergence may be slow or uncertain and alternative methods or rearrangements become necessary.

Error control and stopping criteria

Practical iteration uses stopping rules to produce a useful approximation. Common criteria include limiting the absolute difference |x_{n+1}-x_n| below a tolerance, limiting the residual |f(x_n)| below a tolerance, or performing a fixed number of iterations. Selection of tolerance depends on required accuracy and error propagation. A stricter tolerance produces a more accurate approximation but requires more iterations.

Limitations and failure modes

Iteration can fail when g(x) does not satisfy the convergence condition, when the initial guess is too far from the root, or when g(x) introduces singularities or undefined values within the iteration range. Oscillation between values or growth without bound indicates divergence. Graphical inspection of g(x) and f(x) or calculation of g'(x) on an interval provides early indication of potential problems. Alternative methods such as bisection or Newton–Raphson become preferable if fixed-point iteration fails.

Key notes

Important points to keep in mind

Form f(x)=0 and rearrange to x=g(x) to apply fixed-point iteration.

Check |g'(x)|<1 near the root to predict local convergence.

Use |x_{n+1}-x_n| or |f(x_n)| as stopping criteria with a chosen tolerance.

Choose an initial guess close to the expected root to improve convergence chances.

Avoid rearrangements that introduce division by expressions that can be zero in the iteration interval.

Include a maximum iterations limit to prevent non-terminating processes.

Graph y=g(x) and y=x to visualise fixed points and slope behaviour.

Use relaxation x_{n+1}=x_n - k f(x_n) to stabilise updates when required.