Welcome to Numerical Methods (P2.9)!
Hello! Numerical methods might sound intimidating, but they are incredibly practical. This chapter is all about finding approximate solutions to problems that are too difficult or impossible to solve exactly using standard algebra or calculus.
Think of numerical methods as mathematical shortcuts or powerful estimation tools. We use them all the time in real-world applications, from engineering complex structures to predicting climate change.
Don't worry if this seems tricky at first; we will break down each technique step-by-step!
1. Locating Roots of Equations
Finding an Interval containing a Root (Sign Change Method)
When you are asked to solve an equation \(f(x) = 0\), finding the roots (the solutions) can be tough. The first step in numerical methods is often to find a small interval where a root is guaranteed to exist.
The Principle of Sign Change
If a function \(f(x)\) is continuous in an interval \([a, b]\), and \(f(a)\) and \(f(b)\) have opposite signs (one is positive, one is negative), then there must be at least one root between \(x=a\) and \(x=b\).
Analogy: Imagine crossing a river. If you start on the positive bank (above \(y=0\)) and finish on the negative bank (below \(y=0\)), you must have crossed the water line (the x-axis, where \(f(x)=0\)) at least once.
Step-by-Step Process
- Define the function \(f(x) = 0\).
- Choose two values, \(a\) and \(b\), often given in the question, or chosen by looking at a graph.
- Calculate \(f(a)\) and \(f(b)\).
- If \(f(a)\) and \(f(b)\) have opposite signs (a sign change), then a root exists in the interval \((a, b)\).
Crucial Point: This method only works if \(f(x)\) is continuous over the interval. If the function has a break or an asymptote (like \(\frac{1}{x}\) around \(x=0\)), a sign change might occur without a root existing. However, in this course, functions are generally assumed to be continuous unless stated otherwise.
If \(f(x)\) changes sign between \(a\) and \(b\), a root lies between \(a\) and \(b\), provided the function is continuous. This technique helps us "zoom in" on the answer.
2. Simple Iterative Methods
Using Recurrence Relations: \(x_{n+1} = g(x_n)\)
Once we know roughly where the root is, we can use an iterative method to find a much more accurate approximation. Iteration means doing something over and over again.
The Iterative Process
To solve \(f(x) = 0\), we first rearrange the equation into the form: $$\mathbf{x = g(x)}$$
We then turn this into a recurrence relation: $$\mathbf{x_{n+1} = g(x_n)}$$
You start with an initial guess, \(x_0\). You plug \(x_0\) into the right side to get the next approximation, \(x_1\). You repeat this process, using the previous answer to generate the next one, until the answers stop changing (they converge).
Example: To find the root of \(x^3 - x - 7 = 0\).
We could rearrange this as \(x^3 = x + 7\).
If we make \(x\) the subject: \(x = \sqrt[3]{x+7}\).
The recurrence relation is: \(x_{n+1} = \sqrt[3]{x_n + 7}\).
Convergence: Will the sequence find the root?
Not all rearrangements of \(f(x)=0\) will lead to a successful iteration! Whether the sequence converges (heads towards the root) or diverges (shoots away) depends on the gradient of \(g(x)\) near the root.
The condition for convergence is that the magnitude of the gradient of \(y=g(x)\) must be less than 1 near the root: $$\mathbf{|g'(x)| < 1}$$
Visualising Iterations: Staircase and Cobweb Diagrams
We can illustrate the iteration \(x_{n+1} = g(x_n)\) by drawing two graphs: \(y = g(x)\) and \(y = x\). The intersection of these two graphs is the solution to \(x = g(x)\).
How to Draw the Diagram (for any iteration)
- Start at \(x_0\) on the \(x\)-axis.
- Move vertically to the curve \(y = g(x)\). This point's height is \(y = g(x_0) = x_1\).
- Move horizontally from this point to the line \(y = x\). This finds \(x_1\) on the \(x\)-axis (because \(y=x\)).
- Move vertically back to the curve \(y = g(x)\). This finds \(x_2\).
- Repeat the process.
Types of Convergence
The shape of the path created depends on the gradient \(g'(x)\) near the root:
1. Staircase Diagram (Monotone Convergence):
- Occurs if \(0 < g'(x) < 1\).
- The values of \(x_n\) move steadily towards the root without overshooting. It looks like steps climbing toward the intersection point.
2. Cobweb Diagram (Oscillating Convergence):
- Occurs if \(-1 < g'(x) < 0\).
- The values of \(x_n\) overshoot the root each time, but the oscillations get smaller and smaller, winding in towards the root, like a cobweb.
Did you know? If \(|g'(x)| > 1\), the sequence diverges—the steps/oscillations get bigger and move away from the root. If the question asks you to comment on convergence, this is what you should consider!
1. Rearrange \(f(x)=0\) to \(x=g(x)\).
2. Iterate using \(x_{n+1}=g(x_n)\).
3. Convergence is guaranteed if \(|g'(x)| < 1\) near the root.
3. Numerical Integration: Estimating Area
Numerical integration is used to estimate the value of a definite integral \(\int_a^b f(x) \, dx\), which represents the area under the curve between \(x=a\) and \(x=b\).
A. The Mid-Ordinate Rule
The Mid-Ordinate Rule approximates the area under the curve using a set of rectangles. Unlike the Trapezium Rule (which uses the ends of the strips), the height of each rectangular strip is calculated at the midpoint of the strip's width.
Step-by-Step for the Mid-Ordinate Rule
Suppose we want to estimate \(\int_a^b f(x) \, dx\) using \(n\) strips.
- Calculate Strip Width (\(h\)): $$h = \frac{b - a}{n}$$
- Find the Midpoints:
For each strip, find the x-coordinate of its midpoint. If the strips run from \(x_0\) to \(x_n\), the midpoints are \(m_1, m_2, \dots, m_n\).
Example: If the first strip is from \(x=2\) to \(x=4\), the midpoint \(m_1\) is \(3\). - Apply the Formula:
The area is the sum of the areas of the rectangles: width \(\times\) height.
$$Area \approx h \times [f(m_1) + f(m_2) + \dots + f(m_n)]$$
Geometrical Interpretation: This method uses rectangles. Whether the estimate is an overestimate or an underestimate depends on how the curve bends (its concavity) over the interval, but it often provides a better estimate than the simpler Trapezium Rule because the errors on either side of the midpoint tend to cancel out.
B. Simpson's Rule
Simpson's Rule is usually the most accurate numerical integration method required in this course. Instead of using straight lines or rectangles, it uses segments of parabolas (quadratics) to fit the curve across pairs of strips.
Simpson's Rule uses the following weights for the ordinates (the heights, \(y\)):
Essential Requirement for Simpson's Rule
Simpson's rule must be applied over an even number of strips (\(n\)). This means you need an odd number of ordinates (\(y_0, y_1, \dots, y_n\)).
Simpson's Rule Formula
For \(n\) strips (where \(n\) is even) and strip width \(h = \frac{b - a}{n}\): $$\int_a^b f(x) \, dx \approx \frac{h}{3} [(y_0 + y_n) + 4(y_{odd}) + 2(y_{even})]$$
Let's break down the components:
- \((y_0 + y_n)\): The sum of the First and Last ordinates.
- \(4(y_{odd})\): Four times the sum of the ordinates with odd subscripts (\(y_1 + y_3 + y_5 + \dots\)).
- \(2(y_{even})\): Two times the sum of the ordinates with even subscripts (\(y_2 + y_4 + y_6 + \dots\)). (Do not include \(y_0\) or \(y_n\) here!)
Memory Aid (Simpson's Coefficients):
The multipliers go: 1, 4, 2, 4, 2, 4, 2, ..., 4, 1.
Step-by-Step for Simpson's Rule
- Calculate Strip Width (\(h\)): Ensure \(n\) is even. \(h = \frac{b - a}{n}\).
- List all Ordinates: Calculate \(y_0, y_1, y_2, \dots, y_n\) by substituting the corresponding \(x\)-values into \(f(x)\).
- Apply the Pattern: Sum the first and last (coefficient 1), sum the odds (coefficient 4), and sum the interior evens (coefficient 2).
- Multiply: Multiply the total sum by \(\frac{h}{3}\).
Common Mistake to Avoid: Always check that you are using an even number of strips (N). If the question asks for 5 ordinates, N=4 (even strips), and Simpson's Rule can be used. If the question asks for 5 strips, you cannot use Simpson's Rule!
C. Improving the Estimate
The accuracy of a numerical integration estimate (Mid-ordinate, Trapezium, or Simpson's) is usually improved by increasing the number of steps (\(n\)) used.
If you double the number of strips, \(h\) is halved, and the approximation of the curve becomes much finer, getting closer to the true area.
We use rectangles (Mid-ordinate) or parabolas (Simpson's) to approximate complex areas. Simpson's Rule requires an even number of strips and provides the greatest accuracy for the methods learned.