Elliott C. Back: Internet & Technology

COMS 421: Numerical Analysis Study Guide for Prelim 1

Posted in Code, Cornell University by Elliott Back on November 15th, 2004.

COMS 421 Prelim 1 Sheet. I am posting the CS 421 Study Sheet I used for Prelim 1. Hope someone finds it useful:

COMS 421 CRIB SHEET
PRELIM 1, 09/20/2004

Hallmarks of scientific computing:

Compute with real numbers
Concern with accuracy & efficiency
Very large problems

Three branches of scientific computing:

Numerical linear algebra
Differential equations
Optimization

Linear Algebra Review:

  • A Subspace of R^n^ is a set S in R^n^ such that (a) Ψ is in S and (b), for all (x, y) in S and for all (alpha, beta) in R, alpha * x + beta * y is also in S.
  • Thm: S, T are subspaces, then if S is a subspace of T, dim(S) < dim(T)
  • Vector x in R^n^ is a Linear Combination of v1…vn if there exists B1 … Bn s.t. x = B1v1 + … + Bnvn.
  • The Span of {v1 … vn} is all vectors in Rn that are linear combinations of {v1 … vn}. A span is a subspace.
  • Vectors v1 … vn are Linearly Independent if the only way to express 0 as a linear combination is with 0s for coefficients.
  • {v1 … vk} in S form a Basis of S if they (a) span S, and (b) are linearly independent. Standard basis: {e1 … e2}.
  • A Linear Transformation is a fxn T : R^n^ to R^m^ s.t. for all (x, y) in R^n^ and all (alpha, beta) in R, T(alpha*x + beta*y) = alpha*T(x) + beta*T(y)
  • Rowspace is the span of rows, Range is span of columns. dim(rowspace) = dim(range) = rank(A). rank(A) ? min(m, n).
  • Thm: These statements are equivalent:
    1. A is nonsingular
    2. Rank(A) = n
    3. Ax = b has a solution x for all b
    4. Ax = Ψ has the only solution x = Ψ
  • A^T^ is A where A(i, j) -> A(j, i).
  • (A * B)^T^ = B^T^*A^T^

Gaussian Elimination with Partial Pivoting

 For k = 1:n
    [scrap, offset] = max( abs( A( k:n, k)));
    pivot = k + offset -1;

    A([pivot, k], k:n) = A([k, pivot], k:n);
    L([pivot, k], l:k-1) = L([k, pivot], l:k-1);

    P(k) = pivot;
    Piv = A(k, k);

    L(k+1:n, k) = A(k+1:n, k) / piv;
    L(k, k) =1;

    A(k+1:n, k:n) = A(k+1:n, k:n) – L(k+1:n, k) * A(k, k:n);
End

Note, P*PT = I, so A = PT * L * U

Thm: Let P1 … Pn be the sequence of swaps performed by GEPP. Then GEPP is same is P*A followed by plain gauss LU

Thm: If GEPP encounters a 0 pivot, A is singular, U is singular.

  • Factor A as PTLU
  • Let b’ = Pb’
  • Solve Lw = b’ for w
  • Solve Ux = w for x

Catastrophic Cancellation: Subtracting two numbers nearly equal in magnitude.

Vector Norm is a function denoted ||x||.

  • norm(x) ? 0, norm(x) = 0 iff x = 0
  • || a * x || = | a | * || x ||
  • || x + y || ? || x || + || y ||

The Inner Product of x, y is the sum of the pairwise products of entries. Also called “dot product.” x,y are orthogonal if x dot y =0. The nullspace of A is the set of x s.t. Ax = 0.

Thm: For any A, range(A) and nullspace (A^T^) are orthogonal complements:

x in range(a), y in nullspace(A^T^) -> x^T^ y = 0
p in R^m^ -> p = x + y | x in range(A), y in nullspace(A^T^)

Plain Gaussian Elimination:
For k = 1:n
    piv = A(k, k);
    For i = k+1:n
        mult = A(i, k) / piv;
        For j = k:n
            A(i, j) = A(i, j) – mult * A(k, i);
         End
        L(i, k) = mult;
    End
     L(k,k) = 1;
End

Total FLOPS: 2/3 n3 + O(n2)

Forward Substitution:

For i=1:n
    w(i) = (b(i) – L(i, 1:i-1)) * w(1:i-1) / L(i, i);
End

Total FLOPS: n2 + O(n)

Vector p-Norm: (| x1 | p + … + | xn | p)( 1 / p )

  • p = 1 -> || x ||1 = | x1 | + … + | xn |
  • p = Infinity -> || x ||infinity = max( x )

Induced Matrix Norm: Given vector norm || _ ||__ is given by:

  • || A ||? = sup( || A x ||? / || x ||? ), sup is max value across set of all possible x, where x is not 0
  • The induced matrix norm satisfied all 3 norm properties
  • || A x || ? || A || * || x ||
  • || A * B || ? || A || * || B || (submultiplicativity)
  • Thm: define N(A) = max of i=1:m of the sum from j to n of | A(i, j) |, then || A ||infinity = N(A)
  • Thm: define M(A) = max of j=1:n of the sum from i to m of | A(i, j) |, then || A ||1 = M(A)

A problem is ill-conditioned if a solution is sensitive to small perturbations of the input data.

Let Ax = b, with nonsingular A. x’ solves (A + E) x’ = b + e, and || E || / || A || ? delta, || e || / || b || ? delta. Then ||x’ – x|| / || x || < = 2* delta * cond(A)  + O(delta2)