Assignment #3: Vector Spaces

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

 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||