Numerical methods are implementations of mathematical algorithms, but constructed with special consideration for accuracy of solutions and computational run-time. In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument.

As a course

Python

Pre-Lectures: 4 lowest scores will be dropped (used 4). they can be completed for 100% credit by the following Tuesday at the start of the class time.

HW: The 2 lowest scores will be dropped. (used 2)

MP: There will be a total of 5 individual MPs, combined they will count towards 10% of your final grade. There is no drop of MP scores.

Quiz: the lowest score will be dropped (used)

Group activity: lowest score will be dropped

Problem set

1. Consider number of operations that produce errors

   

   (a) the first has more severe cancelation error since it is been rounded before subtraction (b) the first has fewer operations (2, compared with 3)

2. Monte Carlo simulation to determine the matrix conditioning by sampling vectors

3. Partial pivoting does NOT improve the conditioning of solving a linear system. It does make LU factorization less sensitive to inexact arithmetic

4. Consider a Markov process based on a transition graph G with adjacency matrix A. Then the steady-state may depend on the initial state. The simplest example being a disconnected transition graph.

5. ABCE are true. A is talking about the i-th variable.

   

Math

• Def. Orthogonal (or orthonormal) matrix
  • Def. Square matrices are called orthogonal if and only if the columns are mutually orthogonal to one another and have a 2-norm of 1 (i.e., orthonormal columns)
  • $A ^ {-1} = A ^ T, \det A = \pm 1$
  • All singular values are 1 (since $M=M I I$ will be a decomposition)
  • $||Qv||_2^2 = (Qv)^T(Qv) = v^T v = ||v||_2^2$ → 2-norm preserving
• Matrix norm
  • Frobenius norm $||A||_F$: entry-wise matrix norm. Treat matrix as vector. It relates to SVD in that $||A||_F = \sqrt{\sum \sigma_i^2}$
    • Note that $||A||_F = \sqrt {tr(AA^T)}$
  • Induced matrix norm $||A|| := \max_{||x||=1} ||Ax||$, which is induced from a specific vector norm $|| \cdot ||$.
    • When 1-norm is used, $||A||1$ is the maximum column sum of absolute $\max_j \sum_i |a{ij}|$.
      • Pick $\vec x = [ 0 \dots 0, 1, 0 , \dots ,0]^T$
    • When 2-norm is used, $||A||_2$ is the maximum singular value $\sigma_1$ in SVD. When A is symmetric real matrix, it’s the eigenvalue of maximum absolute value.
      • Proof. $\| {\bf A} \|2 = \max{\|\mathbf{x}\|=1} \|\mathbf{A x}\| = \max_{\|\mathbf{x}\|=1} \|\mathbf{U \Sigma V}^T {\bf x}\| =\max_{\|\mathbf{x}\|=1} \|\mathbf{ \Sigma V}^T {\bf x}\| = \max_{\|\mathbf{V}^T{\bf x}\|=1} \|\mathbf{ \Sigma V}^T {\bf x}\| =\max_{\|y\|=1} \|\mathbf{ \Sigma} y\|= \max_{||y||=1} \sqrt{y^T \Sigma^2 y} =\max_{||y||=1} \sqrt{ \sum_i y_i^2 d_i^2 } \le \max_{||y||=1} \sqrt{ (\sum_i y_i^2) \max_i d_i^2 }=||d||_\infty$. The upperbound can be achieved when we take the eigenvector corresponding to the biggest absolute eigenvalue as y.
      • Most complete proof
      • Therefore, $\| {\bf A}^{-1} \|_2= \frac{1}{\sigma_n}, \| {\bf A}^{+} \|_2= \frac{1}{\sigma_r}$ for full rank A and other non-zero A respectively.
    • When $\infty$-norm is used, $||A||_\infty$ is the maximum row sum of absolute.
      • Pick $\vec x = [\pm1, \pm1, \dots, \pm1]^T, ||\vec x||_\infty=1$ such that it yields sum of absolute of the row with maximum sum of absolute
    • Submultiplicativity by definition: $||Ax|| \le ||A||\ ||x||$ and $||AB|| \le ||A||\ ||B||$.
    • Triangle inequality as a norm. $||A+B|| \le ||A|| + ||B||$
• Adjacency matrix notation:
  • graph theory and social network analysis (sociology, political science, economics, psychology): usually $A_{ij}$: $v_i \rightarrow v_j$
  • [THIS COURSE HERE] other applied science (dynamical systems, physics, network science): usually $A_{ij}$: $v_i \leftarrow v_j$. Allowed matrix left multiplication.
• Def. Speed of convergence: An iterative method converges with rate $r$ if: $\lim_{k\to\infty} \frac{\|e_{k + 1}\|}{\|e_{k}\|^{\mathbf r}} = C, \quad 0 < C < \infty$
  • r=1 → linear convergence. Gains a constant number of accurate digits each step
  • 1<r<2 → superlinear convergence
  • r=2 → quadratic convergence. Doubles the number of accurate digits in each step. C does not matter much.

Randomness

Error and Number representation

Sparse matrix

Condition numbers: Is your problem sensitive to errors (perturbation) in the input?

LU Decomposition