Numerical Methods - Study Notes
Lesson summary
Numerical analysis reaches approximate solutions by repeated use of the four basic operations of algebra. Its starting point is the study of finite differences of a function \( y = f(x) \) whose arguments \( x_0, x_0 + h, x_0 + 2h, \ldots, x_0 + nh \) are in increasing order and equally spaced with interval h. The values \( y_0, y_1, \ldots, y_n \) are called the entries.
Forward differences
- First differences: \( \Delta y_0 = y_1 - y_0,\ \Delta y_1 = y_2 - y_1 \); in general \( \Delta y_n = y_{n+1} - y_n \).
- Second differences: \( \Delta^2 y_n = \Delta y_{n+1} - \Delta y_n \); third differences \( \Delta^3 y_n = \Delta^2 y_{n+1} - \Delta^2 y_n \).
- In function form: \( \Delta f(x) = f(x+h) - f(x) \) and \( \Delta^k f(x) = \Delta^{k-1} f(x+h) - \Delta^{k-1} f(x) \).
- The differences are set out diagonally in a forward difference table, with \( \Delta y_0, \Delta^2 y_0, \Delta^3 y_0, \ldots \) on the leading diagonal.
Properties of \( \Delta \)
- \( \Delta c = 0 \) for a constant c.
- \( \Delta \) is distributive: \( \Delta[f(x) + g(x)] = \Delta f(x) + \Delta g(x) \).
- \( \Delta[c f(x)] = c\,\Delta f(x) \).
- \( \Delta^m \Delta^n f(x) = \Delta^{m+n} f(x) \) (stated without proof).
Standard results
| Function | Difference |
|---|---|
| \( e^{ax} \) | \( \Delta e^{ax} = e^{ax}(e^{ah} - 1) \) |
| \( e^{x} \) | \( \Delta^2 e^{x} = (e^{h} - 1)^2 e^{x} \) |
| \( \log x \) | \( \Delta \log x = \log\left(1 + \frac{h}{x}\right) \) |
| \( \frac{1}{x} \), h = 1 | \( \Delta^n \frac{1}{x} = \frac{(-1)^n n!}{x(x+1)\cdots(x+n)} \) |
Backward differences
- \( \nabla y_1 = y_1 - y_0,\ \nabla y_2 = y_2 - y_1 \); in general \( \nabla y_n = y_n - y_{n-1} \). The symbol \( \nabla \) is read nepla.
- \( \nabla f(x) = f(x) - f(x-h) \) and \( \nabla^k y_n = \nabla^{k-1} y_n - \nabla^{k-1} y_{n-1} \).
- \( \nabla f(x+h) = \Delta f(x) \) and in general \( \nabla^n f(x+nh) = \Delta^n f(x) \).
Shifting operator E
- \( Ef(x) = f(x+h) \), \( E^2 f(x) = f(x+2h) \), \( E^n f(x) = f(x+nh) \), \( E^{-n} f(x) = f(x-nh) \); also \( E^n y_0 = y_n \).
- E is also called the displacement operator. It is distributive, \( E[c f(x)] = cE f(x) \), \( E^m E^n f(x) = E^{m+n} f(x) \) and \( E^n E^{-n} f(x) = f(x) \).
Relations between the operators
| Relation | Reason |
|---|---|
| \( \Delta \equiv E - 1 \), \( E \equiv 1 + \Delta \) | \( \Delta f(x) = Ef(x) - f(x) \) |
| \( \Delta E \equiv E \Delta \) | both give \( f(x+2h) - f(x+h) \) |
| \( \nabla \equiv 1 - E^{-1} \) | \( \nabla f(x) = f(x) - E^{-1} f(x) \) |
| \( \nabla \equiv \frac{E - 1}{E} \) | same relation rewritten |
Finding missing terms
- If k values of y are known, the data fit a polynomial of degree k - 1, so the k-th differences are zero.
- Expand \( (E-1)^k y_0 = 0 \) with Pascal's triangle coefficients. With four known values: \( y_4 - 4y_3 + 6y_2 - 4y_1 + y_0 = 0 \).
- For two missing values write the equation at \( y_0 \) and at \( y_1 \) and solve the pair.
Interpolation
- Interpolation: estimating y for an x between the extreme given values. Extrapolation: estimating y for an x outside the given values.
- Graphic method: plot the points, draw a free hand curve and read the value. Drawback: the value read is only an estimate.
- Algebraic methods: Newton's (Gregory-Newton) formulae and Lagrange's formula.
Newton's forward formula (equal intervals)
\( y_{(x = x_0 + nh)} = y_0 + \frac{n}{1!}\Delta y_0 + \frac{n(n-1)}{2!}\Delta^2 y_0 + \frac{n(n-1)(n-2)}{3!}\Delta^3 y_0 + \cdots \), with \( n = \frac{x - x_0}{h} \). Used near the beginning of the table. The first two terms give linear interpolation, the first three parabolic interpolation.
Newton's backward formula (equal intervals)
\( y_{(x = x_n + nh)} = y_n + \frac{n}{1!}\nabla y_n + \frac{n(n+1)}{2!}\nabla^2 y_n + \frac{n(n+1)(n+2)}{3!}\nabla^3 y_n + \cdots \), with \( n = \frac{x - x_n}{h} \). Used near the end of the table.
Lagrange's formula (equal or unequal intervals)
\( y = \frac{(x - x_1)(x - x_2)\cdots(x - x_n)}{(x_0 - x_1)(x_0 - x_2)\cdots(x_0 - x_n)} y_0 + \cdots + \frac{(x - x_0)(x - x_1)\cdots(x - x_{n-1})}{(x_n - x_0)(x_n - x_1)\cdots(x_n - x_{n-1})} y_n \)
Common exam traps
- \( \Delta(x^2) = 2x + 1 \) but \( \nabla(x^2) = 2x - 1 \) when h = 1.
- In the backward formula n is negative for a value inside the table.
- Grouped data such as marks are first converted to a less-than cumulative frequency table before interpolating.
- Do not use Newton's formulae when the x values are unequally spaced.