Numerical Methods (NM)

    Solutions of equations

      TO DO: Rate of convergence - NMe3; not covered until chapter 6

    e1-4 Bisection method:

    • 1) Find an interval estimate (two xx-coordinates which straddle the root, one each side). These can be confirmed by checking for a change of sign
    • 2) Find the mid-point and calculate f(x)f(x)
    • 3) Out of the three xx-coordinates now available, find the smallest interval which has a change of sign
    • 4) Repeat steps 2 and 3 until the root is approximated to the required accuracy
    • 5) Stop once the left and right interval are equal when rounded to the required number of decimal places/significant figures

    Newton-Raphson method:

    • This method draws a tangent at a starting approximation. The xx-coordinate where this tangent intersects the xx-axis is used as the approximation for the next iteration. As the iterations progress, the value of xx should converge towards the true value
    • The initial approximation is written as x0x_0
    • Use the following equation (2nd page of the exam formula booklet):
      xn+1=xnf(xn)f(xn)x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}
    • In most cases, if two iterations produce the same approximation when rounded to the required number of decimal places/significant figures, no further iterations will be required. To confirm this, use the change of sign method to check the error bounds (like in the C3 coursework)
    • This method has second order convergence

    Secant method:

    • This is similar to the Newton-Raphson method, but doesn't require differentiation. Instead, two points are connected to create an approximation for the tangent to the curve. The xx-intercept of this tangent then creates the next point
    • 1) Start with two xx-estimates; x0x_0 and x1x_1. They can be either straddling the root or with both on the same side of it
    • 2) Calculate x2x_2 with
      x2=x0f(x1)  x1f(x0)f(x1)  f(x0)x_2 = \frac{x_{0}f(x_{1})\ -\ x_{1}f(x_{0})}{f(x_{1})\ -\ f(x_{0})}
    • You must memorize this equation. The order of the subscripts is 0110 10
    • In terms of xrx_r and xr1x_{r-1}:
      xr+1=xr1f(xr)  xrf(xr1)f(xr)  f(xr1)x_{r+1} = \frac{x_{r-1}f(x_{r})\ -\ x_{r}f(x_{r-1})}{f(x_{r})\ -\ f(x_{r-1})}

      Quick secant method on a Casio calculator:

    • Enter x0x_0 and save to memory slot A
    • Enter x1x_1 and save to memory slot B
    • Use the secant formula with As and Bs (e.g. for f(x)=4x35x+1f(x) = 4x^3 - 5x + 1):
      A(4B35B+1)  B(4A35A+1)(4B35B+1)(4A35A+1)\frac{A(4B^{3}-5B+1)\ -\ B(4A^{3}-5A+1)}{(4B^{3}-5B+1)-(4A^{3}-5A+1)}
    • Press =
    • Now save this to slot C
    • Copy the contents of slot B to slot A [ALPHA+B, STO+A (note: don't press ALPHA before pressing A on the second step)]
    • Copy the contents of slot C to slot B [ALPHA+C, STO+B (same applies here)]
    • Use the up arrow (if you followed the above steps exactly you'll need to press it 3 times) to return to the equation in terms of A and B
    • Now repeat again from the step 'press ='
    • Summary: save x0x_0 to A and x1x_1 to B. Enter the equation and press =. Save the answer to slot C. Copy slot B to A and then C to B. Return to the original equation, press = and repeat.

    False position (linear interpolation) method:

    • This method uses two starting approximations, one each side of the root
    • It then connects them with the line to approximate a tangent, and uses the intersection of that line with the xx-axis as the next value. This value is used alongside whichever starting approximation is on the opposite side of the root to it - so a change of sign check is required after each iteration
    • aa and bb are used as the approximations, the root must between these two values
    • The formula is the same as with the secant method:
      c=af(b)bf(a)f(b)f(a)c = \frac{af(b)-bf(a)}{f(b)-f(a)}
    • After applying this formula, check the sign on aa, bb and cc and use cc, and either aa or bb (the signs must be different)
    • This method has first order convergence

    Fixed-point iteration method (rearranging to x=g(x)x=g(x) form):

    • 1) Rearrange the equation, e.g. f(x)=0f(x) = 0 into the form x=g(x)x = g(x)
    • 2) Now use this as an iterative formula; xn+1=g(xn)x_{n+1} = g(x_{n}), repeating for the necessary number of iterations
    • If the value of xx diverges from the root, try another rearrangement - this method only works when |g(x)|<1|g'(x)| < 1


      v1-5 Notation:

      • XX is the symbol for an approximation of xx


      • Error =Xx\ = X - x
      • Absolute error =|error|=|Xx|\ = |\rm{error}| = |X - x|
      • Relative error =Xxx\ = \frac{X - x}{x}
      • Absolute relative error =|Xxx|\ = |\frac{X-x}{x}|
      • Percentage error =|Xxx|×100\ = |\frac{X-x}{x}| \times 100


      • The interval 1.25 xx 1.35 can be written as [1.25, 1.35]
      • The interval 1.25 xx < 1.35 can be written as [1.25, 1.35) - the bracket represents greater than/less than, and square bracket is greater than or equal to/less than or equal to

      Function error propogation:

      • If there is an error in xx, then f(x)f(x) will also contain this error. The ±\pm will be the error in xx multiplied by f(x)f'(x). As a formula this is written as f(x+h)f(x)+hf(x)f(x + h) \approx f(x) + hf'(x)
      • For example, if we know that x=3±2x = 3 \pm 2, h=2h = 2
        - So the median value is f(x)f(x)
        - The upper bound is approximately f(x+2)f(x+2)
        - If we don't have the original function definition, f(x+2)f(x+2) can be approximated with the above formula

      Numerical differentiation

        c1-2 The forward difference method:

        • This method calculates the gradient of a tangent drawn to the curve at the point xx. To measure the gradient of the tangent, it uses a second point f(x+h)f(x + h)
        • f(x)f'(x) \approx f(x+h)  f(x)h\frac{f(x + h)\ -\ f(x)}{h} where hh is a small number
        • As hh decreases, the approximation will become more accurate provided that f(x)f(x) can be calculated to a high accuracy

        The central difference method:

        • This method instead calculates the gradient of a line drawn through f(xh)f(x - h) and f(x+h)f(x + h)
        • f(x)f'(x) \approx f(x+h)  f(xh)2h\frac{f(x + h)\ -\ f(x - h)}{2h}

        Numerical integration

          c3-4 The midpoint rule:

          • This method splits the curve into equal width strips, makes each strip a rectangle up to the height of the curve, and sums the area of each rectangle
          • Use Mn=h(sum of f(midpoint))M_n = h \, (\mathrm{sum\ of\ } f(\mathrm{midpoint})) where nn is the number of strips and hh is the strip width
          • nn is usually a power of 22, starting at n=20=1n = 2^0 = 1
          • This is a second-order method, because absolute error is proportional to h2h^2. Therefore, doubling nn would reduce the error by a factor of 22=42^2 = 4

          The trapezium rule:

          • This method creates trapezia of equal width touching the curve, and sums their areas
          • Use the formula Tn=h2(f0+fn+2(f1+f2+f3+...+fn1))T_n = \frac{h}{2}(\, f_0 + f_n + 2(f_1 + f_2 + f_3 + ... + f_{n-1})\,) where nn is the number of strips, hh is the width of each strip and fkf_k is f(a+kh)f(a + kh) (aa is the lower bound of the integral)
          • A shortcut is to use the relationship T2n=Tn+Mn2T_{2n} = \frac{T_n + M_n}{2}. With this method, you only need to compute the first trapezium rule estimate provided that you have more midpoint rule estimates
          • Like the midpoint rule, this method is also second-order

          Simpson's rule:

          • The midpoint rule is about twice as accurate as the trapezium rule for nn strips
          • The midpoint and trapezium rule estimates will straddle the exact answer
          • These two properties can be used to derive the Simpson's rule formula to more accurately determine the value of the integral without increasing the strip count
          • S2n=S_{2n} = 2Mn+Tn3\frac{2M_n + T_n}{3}
          • The following can also be derived: S2n=S_{2n} = 4T2nTn3\frac{4T_{2n} - T_n}{3}
          • Simpson's rule is fourth-order. In other words, doubling nn would reduce the error by a factor of 24=162^4 = 16
          • With two successive Simpson's estimates, the formula S=S_\infty = 16S2nSn15\frac{16S_{2n} - S_n}{15} will extrapolate it to infinity for the absolute best estimate with this strip count [coursework only, not required in the exam]

          Approximations to functions

            f1-2 Newton's forward difference interpolation:

            • This method is used to create a polynomial equation to fit a set of points which are equally spaced in the xx axis
            • The xx coordinates are called x0,x1,x2,...x_0, x_1, x_2, ... and the yy coordinates for these xx values are called f0,f1,f2,...f_0, f_1, f_2, ...
            • 1) Create a finite difference table as shown below:
              xix_ifif_iΔfi\Delta f_iΔ2fi\Delta^2 f_i
              =f1f0= f_1 - f_0
              x1x_1f1f_1=Δf1Δf0= \Delta f_1 - \Delta f_0
              =f2f1= f_2 - f_1
              Continue this for as many columns as necessary until you reach a value of 00.
              If all of the values in Δkfi\Delta ^k f_i are equal, then the polynomial is of kkth order
            • 2) Now use Newton's interpolating polynomial:
                 f(x)=f0+f(x) = f_0 + xx0h\frac{x - x_0}{h}Δf0+\Delta f_0 + (xx0)(xx1)2!h2\frac{(x - x_0)(x - x_1)}{2!h^2}Δ2f0+\Delta^2 f_0 + (xx0)(xx1)(xx2)3!h3\frac{(x - x_0)(x - x_1)(x - x_2)}{3!h^3}Δ3f0+...\Delta^3 f_0 + ...
            • Remember that you may not have to simplify this if you are only asked to find f(x)f(x) for a value of xx - just substitute this xx value into the unsimplified interpolating polynomial

            Lagrange's method:

            • This method does not require equally spaced points
            • Lowercase letters are used to represent xx coordinates and uppercase letters represent yy coordinates: e.g. (a,A),(b,B),(c,C),...(a, A), (b, B), (c, C), ...
            • For a quadratic, f(x)=f(x) = A(xb)(xc)(ab)(ac)\frac{A(x-b)(x-c)}{(a-b)(a-c)} ++ B(xc)(xa)(bc)(ba)\frac{B(x-c)(x-a)}{(b-c)(b-a)} ++ C(xa)(xb)(ca)(cb)\frac{C(x-a)(x-b)}{(c-a)(c-b)}
            • With higher order polynomials, the above can be extended (e.g. for a cubic, the first term would be A(xb)(xc)(xd)(ab)(ac)(ad)\frac{A(x-b)(x-c)(x-d)}{(a-b)(a-c)(a-d)})
            • In the exam, the required degree will be n1n - 1 where nn is the number of points