Home COMP 350 Summary of Final Exam Topics

Summary of Final Exam Topics CC-BY-NC

Maintainer: admin

1IEEE floating-point arithmetic

1.1IEEE floating-point representation

  • Single

  • Double

  • Hidden bit techniques

  • subnormal numbers

  • normalized numbers

  • machine epsilon

  • gap between two consecutive floating point numbers

  • rounding for different modes

  • bounds on absolute error

  • bounds on relative error

1.2IEEE rules

  • Computed value of sum/difference/production/difference of x and y
    is the rounded value of the theoretical operation.

  • Numerical cancellation

2Solving linear equations

2.1Algorithms

  • GENP

  • GEPP

  • cost analysis for GENP and GEPP

2.2Theoretical results

  • if we use GEPP, then usually the residual
    $|| r|| \leq o(\epsilon)||A||||x_c||$. where $r = b-Ax_c$, and that
    $\frac{||x-x_c||}{||x||} = o(\epsilon ||A||\cdot||A^{-1}||$

2.3Algorithms for tridiagonal linear system

  • Algorithm design for tridiagonal linear system.

  • If tridiagonal matrix is strictly dominant by column GEPP same as
    GENP.

3Solving $f(x) = 0$

  • Why iterative methods

  • 3 methods

    • Bisection: should know formula <- linear convergence rate

    • Newton method: should know how to prove convergence, "usually"
      quadratic convergence rate.

    • Secant: should also know the formula <- super linear convergence
      rate

  • Comparison of the three methods. The advantages of each of them. (i.e.,
    rate of convergence)

4Polynomial interpolation

$P(x) = y_i, i= 0,1,\dots,n$ , need to know the existence and uniqueness
of the polynomial interpolation

4.1Mehods of interpolation

  • Vandermonde approach

  • Lagrange approach

  • Newton approach

4.2Polynomial evaluation

Idea of nested multiplication. given some x’s, give an efficient method to
evaluate the polynomial.

4.3Runge function $f(x) = \frac{1}{1+25x^2}, x\in [-1,1] $

We showed that as the degree of the polynomial increases, the
interpolation gets worse. This function indicates that high-degree
polynomial interpolation is dangerous.

5Spline interpolation

Linear spline and cubic spline.

6Least square approximation

$\min_c \sum_{i=0}^m (y_i - \sum_{j=0}^n c_j \phi_j (x_i))^2 = ||y-Ac||_2^2$

The LS solution satisifies normal equation $A^T Ac = A^T y$

7Numerical integration

$$I = \int_a^b f(x)dx$$

  • Rectangle Rule: need to know how to derive

  • Trapezoid Rule: need to know how to derive

  • Midpoint Rule: need to know how to derive

  • Simpson's Rule: need to know how to derive

  • Adaptive Simpson's Rule: need to know the motivation and idea (how does
    it work)

  • Gaussian quadratic rule: method of derivation, and advantages

Need to know order of error for all of these. Need to know how to prove
the error for the rectangle rule using the mean value theorem.

8Numerical solution for ODEs

  • Euler’s method: need to know error analysis and derivation

  • Trapezoidal Euler’s method: need to know derivation

  • Midpoint Euler’s method: need to know derivation

  • Taylor series method (not tested)

  • Runge-Kutta methods of order 2 and 4 (advantages of this)