Math 601 - Fall 2000

1. u₁ := v₁ (|| v₁ ||)^-1 equivalently v₁ = r₁₁u₁, r₁₁ = || v₁ ||

2. u₂ := (v₂ - < v₂, u₁ > u₁) r₂₂^-1 equivalently v₂ = r₁₂u₁ + r₂₂u₁,
   where r₁₂ = < v₂, u₁ > and r₂₂ = || v₂ - < v₂, u₁ > u₁ ||

3. u_k := (v_k - < v_k, u₁ > u₁ - ... - < v_k, u_k-1 > u_k-1 ) r_kk^-1 equivalently v_k = r_1ku₁ + ... + r_kku_k,
   where r_jk = < v_k, u_j > and r_kk = || v_k - < v_k, u₁ > u₁ - ... - < v_k, u_k-1 > u_k-1 ||.

4. Repeat the step above for k = 3, 4, ... n. The result is an orthonormal (o.n.) basis that replaces the v_j's.

r11 r12  r13  ... r1n
0   r22  r23  ... r2n
0    0   r33  ... r3n
...
0    0   0   ... rnn

Ac=d,   where A_jk= < w_k, w_j >,   d_j = < v , w_j >.

The matrix A is called the Gram matrix for the basis of w's; it is always invertible. (See problem 1, Assignment 4.)

Orthonormal case If the basis {u₁, ... , u_n} (u's replace w's) is orthonormal, then A = I and x = d; that is, the minimizer has the form
u* = < v , u₁ > u₁+ ... + < v , u_n > u_n

Finite element method We want to illustrate the finite element method with a simple example. Solve the ODE - y'' = f(x), y(0) = y(1) = 0. We take the space V to be all continuous functions g(x) defined on [0,1] having a piecewise continuous derivative g'(x) and satisfying g(0) = g(1) = 0. The inner product for this space is < f , g > = S₀¹ f'(x)g'(x) dx. The subspace U comprises all piecewise linear functions in V, with possible discontinuities in the derivatives at 0, 1/n, 2/n, ... (n-1)/n, 1. These are linear B-splines; the possible discontinuities are called knots. A (non-orthogonal) basis is
w_j(x) = B(n x - j), j = 1, ..., n-1,
where B(x) is the piecewise linear function defined this way:

B(x) = 0 if x < -1 or x > 1;
B(x) = 1 + x if -1 <= x < 0;
B(x) = 1 - x if 0 < x <= 1.

We want to minimize || y - u ||. Relative to {w₁, ... , w_n-1}, the normal equations are Ac = d, where
d_j = < y, w_j > = S₀¹ f(x) w_j(x) dx (integrate by parts)
A_jk = < w_k, w_j >
From here on, one must compute d, A, and solve Ac = d for c. In this case, one can show that u*(x) is just the the piecewise linear function that is 0 at x=0, and c_j at x= j/n, j=1, .. , n-1, and 0 at x = 1. One can thus plot u* by ``connecting the dots.'' A specific example will be included in Assignment 4.

Infinite sets of orthonormal vectors See §4 in my notes on Function spaces (PS) (PDF).

1. Positivity: || u || >= 0, and || u || = 0 implies u = 0.
2. Positive homogeneity: || cu || = |c| || u ||
3. Triangle inequality: || u + v || <= || u || + || v ||

1. V = C[a,b], || f || = max_{a <= x <= b} |f(x)|

2. V = Rⁿ, || x ||_p = (|x₁|^p + ... + |x_n|^p)^1/p, 1 <= p

3. V = Rⁿ, || x ||_infinity = max_{k = 1 ... n} |x_k|, p = infinity

1. Homogeneity L[cu] = cL[u]
2. Additivity L[u+v] = L[u] + L[v]

cos(t)  -sin(t) 

sin(t)   cos(t)

[ L[v] ]_D = c₁[ L[v₁] ]_D + c₂[ L[v₂] ]_D + ... + c_n[ L[v_n] ]_D = M_L[v]_B
where
M_L = [ [ L[v₁] ]_D, ... , [ L[v_n] ]_D ]

Sums K+L is defined by (K+L)[v] = K[v] + L[v].

Scalar multiples cL is defined by (cL)[v] = c(L[v]).

Products If K : V -> U and L : U -> W are linear, then we define LK via LK[v] = L[K[v]]. (This is composition of functions). The transformation defined this way, LK, is linear, and maps V -> W. Note: LK is not in general equal to KL.

Inverses Let L : V -> V be linear. As a function, if L is both one-to-one and onto, then it has an inverse K V -> V. One can show that K is linear, and LK = KL = I, the identity transformation. We write K = L^-1.

Associated matrices

M_{K + L} = M_K + M_L

M_cL = c M_L

M_LK = M_L M_K

M_L^-1 = (M_L)^-1

Polynomials in L : V -> V We define powers of L in the usual way: L² = LL, L³ = LLL, and so on. A polynomial in L is then the transformation
p(L) = a₀I + a₁L + ... + a_mL^m
Later on we will encounter the Cayley-Hamilton theorem, which says that if V has dimension n, then there is a degree n (or less) polynomial p for which p(L) is the 0 transformation.

• For A, the problem of finding eigenvalues and eigenvectors decouples. One can first find the roots of p_A(l), and then solve a linear system to get the eigenvectors.
• If the scalars are the complex numbers, then the Fundamental Theorem of Algebra implies that p_A has at least one root. Consequently, A has at least one eigenvalue.
• To find the eigenvalues and eigenvectors of a linear transformation L, choose a basis for V and find the matrix of L relative to this basis, M_L. The eigenvalues of L are precisely those of M_L; the eigenvectors of L have coordinates corresponding to the eigenvectors of M_L.

1. Multilinearity. Let A =[a₁,a₂,...,a_n]. Then det([a₁,a₂,...,a_n]) is a linear function of column a_k, if all other columns are held fixed.
2. Alternating function. Interchanging two columns changes the sign of the determinant.
3. det(I) = 1, I = identity matrix.

1. If two columns of A are equal, then det(A)=0.
2. If a column of A has all 0's, then det(A)=0.
3. Product rule
   If A and B are n×n matrices, then det(AB)=det(A)det(B).
4. A is singular if and only if det(A) = 0.
5. det(A^-1) = (det(A))^-1

...

x_n = det([a₁,a₂,..., a_n-1, y])/det(A).

2 -3 1
1 -2 1
1 -3 2

1 -1  3
1  0  1
1  1  0

0  0  0
0  1  0
0  0  1

0   0   0
0  -2   0
0   0  -6

1 2
0 1

Af₁ = zf₁
Af₂ = zf₂ + f₁
...

Af_m = zf_m + f_m-1

2  1 -1
0  2  3
0  0  2

1. The eigenvalues of a selfadjoint matrix are real.
2. Eigenvectors corresponding to distinct eigenvalues are orthogonal.
3. Every selfadjoint matrix is diagonalizable.
4. Every selfadjoint matrix has an orthonormal basis relative to which it is diagonal. Equivalently, there is an orthogonal matrix S such that S^TA S is a diagonal matrix. An n×n matrix S is said to be orthogonal if S^T = S^-1; this amounts to saying that the columns form an orthonormal basis for Rⁿ.

• Condition number   The condition number of a square, invertible matrix A is defined by
  cond(A) = s₁/s_n.
  It measures how many significant digits are preserved when one tries to solve Ax = b. For example, if b is known to 6 digits and cond(A) = 10³, then x is known to 6 -3 = 3 digits.

• Numerical rank   The rank of A is r, the number of (positive) singular values. The numerical rank of A is
  rank(A,t) = # of singular values greater than a tolerance t.
  Again, this is useful in working with problems having finite precision.

• Least squares   The solution to finding a minimum of || Ax - b || is easily done with the SVD. First we rewrite the problem using the SVD for A.
  || Ax - b || = || USV^Tx -UU^T b ||
  || Sz - c ||,   z = V^Tx   c = U^T b

  Then we note that
  || Sz - c ||² = SUM_{k = 1...r} (s_kz_k - c_k )² + SUM_{k = r+1...n} c_k².

  Choosing z_k = c_k/s_k for k = 1 ... r and z_k = 0 for k = r+1 ... n not only solves the problem, but also gives the solution x = Vz with smallest length || x || = || z ||.

• The input space basis   The matrix A^TA is real and symmetric, so there is an orthonormal basis of eigenvectors relative to which it is diagonal. Let the eigenvalues of A^TA be z₁, ..., z_n, and the corresponding basis of eigenvectors be {v₁, ..., v_n}. The eigenvalues are nonnegative, as this calculation shows:

  A^TA v_k = z_k v_k
  v_k^T A^T A v_k = z_k v_k^T v_k
  || A v_k ||² = z_k || v_k ||²
  || A v_k ||² = z_k   (|| v_k || =1 )

  This calculation also shows that a vector v is in the null space of A if and only if it is an eigenvecor corresponding to the eigenvalue 0. If r = rank(A), then "rank + nullity = # of columns" tells us that the the nullity(A) = n - r. This means that there are r eigenvectors for the remaining eigenvalues. List these as z₁ >= z₂ >= ... >= z_r > 0. Our input basis is now chosen as {v₁, ..., v_r, v_r+1, ..., v_n }. The numbering is the same as that for the eigenvalues. We now define the matrix V via
  V = [ v₁ ... v_r v_r+1 ... v_n ].

• The output space basis   For k = 1, ..., r, let
  u_k = A v_k / || A v_k ||
  u_k = A v_k / z₁^1/2
  We can also write this as the following equation:
  A v_k = z_k^1/2 u_k .
  The u_k's are orthonormal, for k = 1, ..., r. Again, we see this from these equations.
  u_j^T u_k = v_j^T A^T A v_k / z_j^1/2 z_k^1/2
  u_j^T u_k = z_k v_j^T v_k / z_j^1/2 z_k^1/2
  The orthonormality of the v's implies that the right side above is 0 unless j = k, in which case it is 1. Thus, the u's are orthonormal. Fill this set out with m - r vectors to form an orthonormal basis for the output space, R^m. This gives us the basis {u₁, .., u_r, u_r+1, .., u_m}. As before, we define the m×m orthogonal matrix
  U = [u₁, .., u_r, u_r+1, .., u_m].

• The matrix of A relative to the new bases   We let S be M_A. We compute it via the formula for the matrix of a linear transformation.
  S = [ [Av₁]_U [Av₂]_U ... [Av_r]_U [Av_r+1]_U ... [Av_n]_U ]
  The v's with k = r+1,...,n, are all in the null space of A. Thus the last n - r vectors are 0, and so are their corresponding columns relative to the basis of u's. The other vectors we get from the definition of the u's for k = 1, ..., r. The end result is this.

  S = [ [z₁^1/2 u₁]_U [z₂^1/2 u₂]_U ... [z_k^1/2 u_r]_U [ 0 ]_U ... [ 0 ]_U ]

  S = [ z₁^1/2 [u₁]_U ... z_r^1/2 [u_r]_U   0 ... 0 ]

  S = [ z₁^1/2 e₁ ... z_r^1/2 e_r 0 ... 0 ].

  If we let s_k = z_k^1/2 for k = 1, ..., r, we get the same S as the one given in the statement of the theorem. These s_k's are the singular values of A. The matrix S is related to A via multiplication by change-of-basis matrices. The matrix U changes from new output to old output bases, and V changes from new input to old input bases. Since V^T = V^-1, we have that V^T changes from old input to new input bases. In the end, this gives us A =USV^T

 2  -2
 1   1
-2   2

 9  -7
-7   9

 4 0
 0 21/2
 0 0

 2-1/2   2-1/2
-2-1/2   2-1/2

u₁ = A v₁ / z₁^1/2
u₁ = 2^-1/2 (4, 0, -4)^T/4
u₁ =( 2^-1/2 , 0, - 2^-1/2 )^T.

A simlar calculation gives us
u₂ =( 0, 1, 0 )^T.

We now have to add to these to a "fill" vector
u₃ =( 2^-1/2 , 0, 2^-1/2 )^T
to complete the new output basis. This finally yields U =

 2-1/2 0  2-1/2
 0    1  0
-2-1/2 0  2-1/2

• Orthogonal and orthonormal sets; orthonomal bases; orthogonal matrices
• Gram-Schmidt procedure
• QR factorization of a matrix
• Least squares. Be able to derive the normal equations. Be able to solve the various LS problems that we've discussed.
• p-norms

• Characteristic polynomial.
• Cayley-Hamilton Theorem.
• Diagonalization. Be able to diagonalize a matrix or to explain why it cannot be done.
• Adjoint of a linear transformation. Diagonalization of selfadjoint matrices by orthogonal matrices. Be able to show that the eigenvalues of a selfadjoint matrix are real, and that eigenvectors corresponding to distinct eigenvalues are orthogonal.
• Triangular forms. Upper triangular, block upper triangular, and jordan normal form. Know the algorithm for triangularizing a matrix.

Space	Basis	Components
V	covariant	contravariant
V*	contravariant	covariant

(dy¹)² + (dy²)² + (dy³)² - (dx¹)² -(dx²)² - (dx³)² = SUM_j,k 2s_j,kdx^jdx^k

where s_j,k = ½(D_xju^k + D_xku^j + SUM_i D_xjuⁱD_xkuⁱ) is the strain tensor. (In the linear theory of elasticity, the products are neglected.) The strain tensor is also second order, but it is purely covariant.

(ds)² = SUM_j,k g_j,k dw^jdw^k.

The tensor g_j,k is called the metric tensor. It is purely covariant, and has order 2.

(ds)² = dw^TJ^Tg_u J dw  =   dw^Tg_w dw.
Consequently, we have that g_w = J^Tg_u J. This also can be derived via the covariance of the metric tensor. The matrices involved are all square and n×n. Taking the determinants for both sides, and then taking square roots yields

det(g_w)^1/2 = |det(J)| det(g_u )^1/2,   J = u´(w)

The quantity det(J) is called the Jacobian determinant, and is often writtem as

.

det(g_u )^1/2 du¹...duⁿ = det(g_u )^1/2 |det(u´(w))| dw¹...dwⁿ.

Recall that we also have det(g_w)^1/2 = |det(J)| det(g_u )^1/2,   J = u´(w). Substituting this into the last equation then gives us

det(g_u )^1/2 du¹...duⁿ = det(g_w )^1/2 dw¹...dwⁿ,

which shows that the combination det(g_u )^1/2 du¹...duⁿ is invariant under coordinate transformations. This is often called the invariant volume element.

    Vdt
        f₁du¹                         f₂du²

The mass of the fluid crossing the base in time t to dt is then density×volume, or
(µVdt)·f₁×f₂ du¹du²
Thus the mass per unit time crossing the base is F·N du¹du², where F = µV, and N = f₁×f₂ is the standard normal. Recall that the area of the surface element is dS = |N|du¹du². Consequently the mass per unit time crossing the base is F·n dS, where n is the unit normal. Integrating over the whole surface then yields

This surface integral is called the the flux of the vector field F.

Green's Theorem Let C be a piecewise smooth simple closed curve that is the boundary of its interior region R. If F(x,y) = A(x,y)i + B(x,y)j is a vector-valued function that is continuously differentiable on and in C, then

To state this theorem, we also need to define the curl of a vector field
F(x)=A(x,y,z)i + B(x,y,z)j +C(x,y,z)k.
We will assume that F has continuous partial derivatives. The curl is then defined by

There is an important connection between the Jacobian derivative of a vector field and the curl of that vector field. Namely, the antisymmetric part of the Jacobian derivative has components of the curl for entries.

This is important because it gives us the following formula. For any two vectors b and c in R³,
c ^T(F-(F')^T)b = curl F · b × c .
This is useful in proving Stokes' theorem, which we now state.

Stokes' Theorem  Let S be an orientable surface bounded by a simple closed positively oriented curve C. If F is a continuously differentiable vector-valued function defined in a region containing S, then

Divergence Theorem  Let V be region in 3D bounded by a closed, piecewise smooth, orientable surface S; let the outward-drawn normal be n. Then,

Using the Divergence Theorem, we can write this in terms of a volume integral.

Since there are no sources or sinks in S, any mass entering or leaving the volume enclosed by S must pass through S. Thus, the rate at which mass of fluid inside of S changes in time is the negative of the flux.

Interchanging the time derivative and the triple integral and bringing everything under the same integral, we have that

This equation holds for all regions in which the fluid is source free. It follows that the integrand must be 0, otherwise we could pick a small cube restricted to a region in which it was positive (or negative). The whole integral would then be positive (or negative). Hence, we arrive at the following equation, known as the equation of continuity:

• Jacobian derivative
• Chain rule
• Inverse function theorem

• Transformation laws, dual spaces and dual bases
• Examples of tensors: stress, strain, and metric tensors

• Jacobi's Theorem.

• Area element
• Normals - unit and standard
• Flux and density integrals
• Parametrizations of simple surfaces

• Initial value and boundary value problems. See Z/T VI.2.
• Separation of variables.
  • Laplace's equation in the disk. See § VII.2, § VII.7.
  • Fourier series. See § VII.8.
  • Vibrating string. See § VIII.8.
  • Vibrating drumhead. See § VIII.10.
  • Eigenvalue problems and eigenfunction expansions. See § VIII.10
• D'Almebert's solution to the one-dimensional wave equation.