Assignment #3: Vector Spaces (back to full lecture notes)

In this assignment you will work with vector spaces, including vector spaces of functions.

    1. Use the appropriate operators to calculate a basis for the following vector spaces.

      V1 := span {
       
      3
      2
      5
      0
      8
       
      ,
       
      1
      0
      -6
      7
      5
       
      ,
       
      0
      0
      1
      0
      1
       
      ,
       
      -6
      -4
      -10
      0
      -16
       

      }


      V2 := span {
       
      1
      0
      -4
      0
       
      ,
       
      2
      0
      3
      1
       
      ,
       
      1
      0
      -6
      7
       
      ,
       
      0
      0
      1
      0
       
      ,
       
      4
      0
      8
      -5
       
      ,
       
      -1
      0
      -1
      0
       

      }


      V3 := span {
       
      1
      3
      -9
       
      ,
       
      -2
      -6
      18
       
      ,
       
      4
      0
      0
       
      }

      S1 := {
       
      3
      2
      5
      0
      8
       
      ,
       
      1
      0
      -6
      7
      5
       
      ,
       
      0
      0
      1
      0
      1
       
      ,
       
      -6
      -4
      -10
      0
      -16
       
      }


      S2 := {
       
      1
      0
      -4
      0
       
      ,
       
      2
      0
      3
      1
       
      ,
       
      1
      0
      -6
      7
       
      ,
       
      0
      0
      1
      0
       
      ,
       
      4
      0
      8
      -5
       
      ,
       
      -1
      0
      -1
      0
       
      }


      S3 := {
       
      1
      3
      -9
       
      ,
       
      -2
      -6
      18
       
      ,
       
      4
      0
      0
       
      }


      \decompose ((rref (\augment S1))) - {
       
      0
      0
      0
      0
      0
       
      }
      \decompose ((rref (\augment S2))) - {
       
      0
      0
      0
      0
       
      }
      \decompose ((rref (\augment S3))) - {
       
      0
      0
      0
       
      }

    2. Complete the following argument showing that span{ [1;2], [2;4] } = span {[3;6]} using the propositions provided in the verifier. Hint: find an explicit vector x R2 and add it to the second premise in place of undefined; use a similar approach (and a similar but distinct proposition) when building the part of the argument for the other direction of ⊂.

      ∀ x R2,
      x = \undefined # Find an explicit vector to put here.

      implies

      # ...
      \augment (
       
      1
      2
       
      ,
       
      2
      4
       
      ) ⋅ x =
       
      3
      6
       
        and # Hint (keep this in your argument).

      # ...

      span{
       
      1
      2
       
      ,
       
      2
      4
       
      } = span {
       
      3
      6
       
      }

      ∀ x R2,
      {
       
      1
      2
       
      ,
       
      2
      4
       
      } ⊂ span {
       
      3
      6
       
      }   and

      \augment (
       
      1
      2
       
      ,
       
      2
      4
       
      ) ⋅ x
      =
       
      3
      6
       
        and
      x
      =
       
      1
      1
       

      implies
      \augment (
       
      1
      2
       
      ,
       
      2
      4
       
      ) ⋅
       
      1
      1
       
      =
       
      3
      6
       
        and
       
      3
      6
       
      span {
       
      1
      2
       
      ,
       
      2
      4
       
      }   and
      {
       
      3
      6
       
      }
      span {
       
      1
      2
       
      ,
       
      2
      4
       
      }   and
      span{
       
      1
      2
       
      ,
       
      2
      4
       
      }
      span {
       
      3
      6
       
      }   and
      span {
       
      3
      6
       
      }
      span{
       
      1
      2
       
      ,
       
      2
      4
       
      }   and
      span{
       
      1
      2
       
      ,
       
      2
      4
       
      }
      =
      span {
       
      3
      6
       
      }

    3. Complete the following argument: show that the assumptions imply that the spans are equivalent.

      ∀ a,b,c,d,v,v',w,w' R2, ∀ A,B R2×2,
      A
      =
      \augment(w,w')   and
      B
      =
      \augment(v,v')   and
      A ⋅ a
      =
      v   and
      A ⋅ b
      =
      v'   and
      B ⋅ c
      =
      w   and
      B ⋅ d
      =
      w'

      implies
      # ...
      span {w,w'} = span {v,v'}


      ∀ a,b,c,d,v,v',w,w' R2, ∀ A,B R2×2,
      A
      =
      \augment(w,w')   and
      B
      =
      \augment(v,v')   and
      A ⋅ a
      =
      v   and
      A ⋅ b
      =
      v'   and
      B ⋅ c
      =
      w   and
      B ⋅ d
      =
      w'

      implies
      \augment(w,w') ⋅ a
      =
      v   and
      \augment(w,w') ⋅ b
      =
      v'   and
      \augment(v,v') ⋅ c
      =
      w   and
      \augment(v,v') ⋅ d
      =
      w'   and
      v
      span {w,w'}   and
      v'
      span {w,w'}   and
      w
      span {v,v'}   and
      w'
      span {v,v'}   and
      {v,v'}
      span {w,w'}   and
      {w,w'}
      span {v,v'}   and
      span {v,v'}
      span {w,w'}   and
      span {w,w'}
      span {v,v'}   and
      span {w,w'}
      =
      span {v,v'}


  1. Find the order 9 polynomial that exactly fits the following data. Your solution must be in the form of a vector in R10 that represents the coefficients of the polynomial.

    P := {
     
    -1
    31
     
    ,
     
    -4
    268327
     
    ,
     
    1
    17
     
    ,
     
    -5
    -1520701
     
    ,
     
    3
    389147
     
    ,
     
    -3
    78869
     
    ,
     
    -6
    -19979509
     
    ,
     
    5
    29571949
     
    ,
     
    0
    -1
     
    ,
     
    -2
    5027
     
    }

    Hint: you can make your answer shorter by using a comprehension to generate a one-row matrix containing the different powers of x. For example:

    x := 2
    \augment (
     
    xk
     
    | k {0 ... 9})

    P := {
     
    -1
    31
     
    ,
     
    -4
    268327
     
    ,
     
    1
    17
     
    ,
     
    -5
    -1520701
     
    ,
     
    3
    389147
     
    ,
     
    -3
    78869
     
    ,
     
    -6
    -19979509
     
    ,
     
    5
    29571949
     
    ,
     
    0
    -1
     
    ,
     
    -2
    5027
     
    }


    # This is the right-hand side of the equation.
    w := (\augment (
     
    y
     
    |
     
    x
    y
     
    P))


    # We generate the matrix using a nested comprehension.

    S := ( (\augment (
     
    x^(9-k)
     
    | k {0 ... 9})) |
     
    x
    y
     
    P )


    # This is the matrix in the left-hand side of the equation.
    M := (\augment S)

    # The matrix is invertible, so we can multiply both sides
    # of the equation by the inverse of M to obtain the
    # solution.
    (M^(-1)) ⋅ w

    # Alternatively, we can find the rref of the augmented
    # matrix.
    rref \augment(M,w)

    # The solution vector has the x9 coefficient as its first entry.
    # If we had used
     
    xk
     
    instead of
     
    x^(9-k)
     
    in our formula for S,
    # this would be reversed.

  2. Consider the order 3 polynomial f(x) = 2x3 + 5x2 - 3x + 1.

    1. Find the order 2 polynomial that is the closest least squares approximation of f on the set {-2,0,2,4,8,16}.

      { 2 (x3) + 5 (x2) - 3 x + 1 | x {-2,0,2,4,8,16} }

    2. Compute the error of the approximation from part (a) above on the domains {-2,0,2,4,8,16} and {-16,-8,-4,-2,-1,0}.


    Solution to #3 (both parts):

    # The points to which we're trying to find an approximately
    # fitting function.
    Points3a := {
     
    x
    2 (x3) + 5 (x2) - 3 x + 1
     
    | x {-2,0,2,4,8,16} }


    # The right-hand side of the overdetermined system.
    v := (\augment {
     
    y
     
    |
     
    x
    y
     
    Points3a })


    # The matrix on the left-hand side of the overdetermined system.
    M := (\augment {
     
    x2, x, 1
     
    |
     
    x
    y
     
    Points3a})


    # The orthonormal matrix that can be used to compute projections
    # onto the span of the columns of M.
    A := \augment \orthonormal \decompose (rref M)

    # The projection of v onto the span of the columns of M.
    w := A ⋅ A ⋅ v


    # Part (a):
    # The solution to the system below contains the coefficients
    # for the least squares approximation. The top entry corresponds
    # to the x2 coefficient.
    FullMatrix := rref \augment (M, w)

    # We could isolate the actual coefficients in a 3-component
    # vector, but this is not required.
    approx := (\augment (\decompose ((FullMatrix ⋅
     
    0
    0
    0
    1
     
    )) - {
     
    0
     
    }))


    # Part (b):
    # The error on the initial domain is defined as follows.
    ||v - w||

    # Below is an alternative formula.
    ||v - M ⋅ approx||

    # To compute the error of the approximation on the second
    # domain, we must first generate the points and build the
    # corresponding matrix:

    Points3b
    :=
    {
     
    x
    2 (x3) + 5 (x2) - 3 x + 1
     
    | x {-16,-8,-4,-2,-1,0} }

    M3b := (\augment {
     
    x2 x 1
     
    |
     
    x
    y
     
    Points3b})


    # Then, M3b ⋅ approx gives us the outputs of the function
    # on the new data points. We compute the error in the same way.
    ||v - M3b ⋅ approx||