Numerical solution of equations

Numerical Solution of Equations (P3/Paper 3)

Welcome to the exciting world of Numerical Methods! This chapter is all about finding solutions (roots) to equations that are too complex to solve using standard algebraic techniques, like the quadratic formula or simple factorization. Since we can't find the exact answer, we use methods to find highly accurate approximations. This is crucial in applied mathematics and science!

Don't worry if this sounds complicated—we are just learning ways to make educated guesses that get better and better!

---

1. Locating Roots: The Starting Point

Before we can start approximating a root, we need to know roughly where it is. We have two main ways to establish a root's location:

1.1 The Sign Change Rule (The "Crossing the Axis" Test)

The simplest and most reliable way to locate a root is by testing values on either side of it.

Suppose you have an equation \(f(x) = 0\). If you find two values, \(a\) and \(b\), such that:

• \(f(a)\) is positive (e.g., \(f(a) > 0\))
• \(f(b)\) is negative (e.g., \(f(b) < 0\))
• The function \(f(x)\) is continuous between \(a\) and \(b\) (meaning no gaps or breaks).

...then there must be at least one root (solution) of \(f(x) = 0\) lying between \(x=a\) and \(x=b\).

Analogy: Imagine you are walking across a valley. If you start on a hill (positive height) and finish on the other side below sea level (negative height), you must have crossed sea level (zero height) at some point, assuming you didn't jump over the valley!

Important Prerequisite Check: You must ensure the function is continuous. For all the functions we deal with in the 9709 syllabus (polynomials, exponentials, logs, trig functions), this is usually true, unless the interval includes a vertical asymptote (like for \(y = \tan x\) or \(y = 1/x\)).

1.2 Locating Roots Using Graphical Methods

Sometimes, locating the root is easier visually, especially when the equation is complicated.

If you have an equation \(f(x) = 0\), you can often rearrange it into two separate, simpler functions:

\(y_1 = g(x)\) and \(y_2 = h(x)\)

The roots of the original equation \(f(x)=0\) are the \(x\)-coordinates of the points of intersection between the graphs \(y_1\) and \(y_2\).

Example: To find the roots of \(e^x - x^2 = 0\), we rearrange it to \(e^x = x^2\). We then sketch:

• \(y_1 = e^x\) (The exponential curve)
• \(y_2 = x^2\) (The parabola)

By sketching these, you can visually estimate how many roots exist and their approximate location (e.g., "one root near \(x=-0.7\) and one root near \(x=1.3\)").

---

2. The Iterative Process: Getting Closer and Closer

Once you know a root is near a value \(x_0\), we use iteration to refine that guess many times until we reach the required accuracy.

2.1 The Iterative Formula \(x_{n+1} = F(x_n)\)

The core of numerical iteration is transforming the equation \(f(x) = 0\) into a rearrangement of the form \(x = F(x)\).

This allows us to define a sequence of approximations:

\(x_{n+1} = F(x_n)\)

• You start with an initial guess, \(x_0\).
• You calculate the next approximation: \(x_1 = F(x_0)\).
• Then: \(x_2 = F(x_1)\).
• And so on: \(x_n\) gets calculated, giving you \(x_{n+1}\).

If this sequence of values (\(x_0, x_1, x_2, \dots\)) gets closer and closer to a single fixed value, we say the sequence converges to the root, \(\alpha\). Since \(x_{n+1} \approx x_n\) when \(n\) is large, we find that \(\alpha = F(\alpha)\), which is exactly the solution to the original equation.

2.2 Rearranging \(f(x)=0\) to \(x = F(x)\)

For any single equation \(f(x)=0\), there are usually many ways to rearrange it into the form \(x = F(x)\).

Example: Solve \(x^3 - 2x - 5 = 0\)

Rearrangement A:

\(x^3 = 2x + 5\)
\(x = (2x + 5)^{1/3}\)

This gives the iteration: \(x_{n+1} = (2x_n + 5)^{1/3}\)

Rearrangement B:

\(2x = x^3 - 5\)
\(x = \frac{x^3 - 5}{2}\)

This gives the iteration: \(x_{n+1} = \frac{x_n^3 - 5}{2}\)

Did you know? Not all rearrangements work! If you pick the wrong rearrangement, the iteration might diverge (move further away from the root). In your exams, you will usually be given a specific rearrangement to use, or asked to find one that seems likely to work.

---

3. Performing Iteration and Determining Accuracy

3.1 Step-by-Step Iteration (Calculator Skills)

Using the iteration formula efficiently is a critical skill, usually done with the ANS button on your calculator.

Process Checklist:

1. Start with \(x_0\): Input the initial guess (often given in the question, e.g., \(x_0 = 1\)). Press [=].
2. Input \(F(x)\): Type the iteration formula, using ANS in place of \(x_n\).
   Example (for \(x_{n+1} = (2x_n + 5)^{1/3}\)): Type \((2 \times \text{ANS} + 5)^{1/3}\).
3. Iterate: Press [=] repeatedly. The first press gives \(x_1\), the second gives \(x_2\), and so on.
4. Record: Write down the sequence of values until they stabilize (i.e., stop changing to the required number of decimal places).

Example Iteration: Starting with \(x_0 = 1\), the sequence might be:
\(x_0 = 1.000000\)
\(x_1 = 1.709976\)
\(x_2 = 1.883395\)
\(x_3 = 1.918967\)
\(x_4 = 1.925893\)
\(x_5 = 1.927282\)
\(x_6 = 1.927558\)
\(x_7 = 1.927613\)
\(x_8 = 1.927624\)

At this point, if asked for the answer correct to 4 decimal places (4 d.p.), the answer is \(1.9276\).

3.2 Proving the Root is Accurate (The Final Sign Change Test)

The iteration process gives you a value that seems stable. To prove this value is correct to a specific degree of accuracy (e.g., 3 decimal places), you must return to the original function \(f(x)\) and use the sign change rule over a small interval.

Suppose you are asked to show the root is \(\alpha = 1.928\) correct to 3 d.p.

This means the true root must lie between the lower bound and the upper bound of this approximation:

• Lower bound: \(1.9275\)
• Upper bound: \(1.9285\)

Step-by-step Proof:

1. Define the original function \(f(x)\). (e.g., if we solved \(x^3 - 2x - 5 = 0\), then \(f(x) = x^3 - 2x - 5\)).
2. Calculate \(f(\text{Lower Bound})\): Find \(f(1.9275)\).
3. Calculate \(f(\text{Upper Bound})\): Find \(f(1.9285)\).
4. Check the signs: If the signs are opposite, then the true root lies in that interval, confirming that when rounded to 3 d.p., the root is indeed \(1.928\).

Common Mistake to Avoid: Students sometimes try to check the sign change using the iterative function \(F(x)\). You must use the original function \(f(x)\).

---

4. Graphical Interpretation of Iteration (Convergence)

The behaviour of the iterative sequence \(x_{n+1} = F(x_n)\) can be visualized by plotting the graphs of \(y = x\) and \(y = F(x)\).

The root \(\alpha\) is the point of intersection, since \(x = F(x)\).

4.1 Visualizing Convergence and Divergence

To visualize the sequence, we draw a path that alternates between the line \(y=x\) and the curve \(y=F(x)\):

1. Start at \(x_0\) on the \(x\)-axis.
2. Move vertically to the curve \(y = F(x)\). This height is \(y_0 = F(x_0) = x_1\).
3. Move horizontally from the curve to the line \(y = x\). The \(x\)-coordinate here is now \(x_1\).
4. Move vertically from the line \(y = x\) back to the curve \(y = F(x)\). This height is \(y_1 = F(x_1) = x_2\).
5. Repeat steps 2, 3, 4.

The resulting shape can show two main types of successful iteration (convergence) or failure (divergence).

Staircase Convergence

If the path forms a series of steps (like a staircase) leading towards the root, the iteration is successful.

This happens when the curve \(y=F(x)\) has a shallow, positive gradient near the root.

Cobweb Convergence

If the path spirals in towards the root (like a cobweb), the iteration is successful.

This happens when the curve \(y=F(x)\) has a shallow, negative gradient near the root.

Divergence (Failure)

If the path moves away from the intersection point, the iteration fails to converge. This occurs when the curve \(y=F(x)\) is too steep near the root.

Note for Advanced Students: While you are not required to know the formal mathematical condition for convergence (which relates to the magnitude of the derivative \(|F'(x)|\)), you are expected to understand that iterations can fail to converge, and the graphical method helps visualize why certain rearrangements work better than others.