Notebook 9 – Math 2121, Fall 2020
There is a bounded region of space in
Our goal today is to uncover a formula for this volume. But first we need to better understand what the
A
However our definitions work, they should associate a volume of
The
In
Consider the following
2×2 Array{Float64,2}:
3.76 -0.68
0.54 1.37
xxxxxxxxxx
A = rand(-5:0.01:5, 2, 2)
Here is a picture of the parallelogram spanned by the columns of
How can we characterize this parallelogram?
Well, every point inside the parallelogram has the form
with
The
Then we define the volume of an
Next issue: how is volume defined in
The definition should obey our intuition that the volume of a rectangular region is
and volume should be invariant under translation.
That is, if
should have volume
where
Finally, if we have two regions in
Here is one definition of the volume of a region
The true volume of
To define limit superior, we need calculus; you can think of this as just the maximum.
This conforms with our usual definiton of area in two dimensions.
But in
3.76
0.54
-0.68
1.37
3.08
1.91
xxxxxxxxxx
A[1,1], A[2,1], A[1,2], A[2,2], A[1,1] + A[1,2], A[2,1] + A[2,2]
5.518399999999999
x
# outer rectangle - triangles
(3.76 + 0.68) * 1.91 - 0.54 * 3.76 - 0.68 * 1.37
Here is an alternate, probabilistic definition of volume that is more amenable to estimation.
Consider a region
to be
Now sample many points uniformly at random from the region
With enough random points, this approximate volume will converge to the true volume.
When our matrix
We just check if
Thus, we can try to implement the probabilistic definition to estimate the matrix volume.
volume_estimates (generic function with 1 method)
xxxxxxxxxx
function volume_estimates(A, lower_bound, upper_bound, trials)
# the region R being used in this method is u + rect(L1, L2, ..., Ln) where
#
# L1 = L2 = ... = Ln = upper_bound - lower_bound
# u = [lower_bound; lower_bound; ...; lower_bound]
#
(n, p) = size(A)
n == p
estimates = []
sample_region_size = (upper_bound - lower_bound)^n
# let's only record the cumulative estimate every 1000 trials
interval = maximum([Int(floor(trials/1000)) 1])
count = 0
v = rand(lower_bound:0.00001:upper_bound, n, trials)
w = A^-1 * v
for j=1:trials
# column j of v belongs to the matrix volume if and only if
# column j of w = A^-1 * v has all entries between 0.0 and 1.0
if 0.0 <= minimum(w[1:end,j]) && maximum(w[1:end,j]) <= 1.0
count += 1
end
if j % interval == 0
append!(estimates, count / j * sample_region_size)
end
end
return estimates
end
estimate_bounds (generic function with 2 methods)
xxxxxxxxxx
function estimate_bounds(A, trials=1000)
# we get more accurante volume estimates but using a smaller region R
# this method estimates optimal choices for lower_bound, upper_bound
# so that R is as small as possible while containing the paralllelogram of A
lower_bound, upper_bound = 0.0, 0.0
for i=1:trials
w = A * rand(0:1, size(A)[1], 1)
lower_bound = minimum([lower_bound minimum(w)])
upper_bound = maximum([upper_bound maximum(w)])
end
return (lower_bound, upper_bound)
end
5000
xxxxxxxxxx
trials = 5000
2×2 Array{Float64,2}:
3.76 -0.68
0.54 1.37
xxxxxxxxxx
matrix = A
-0.68
3.76
xxxxxxxxxx
lower, upper = estimate_bounds(matrix)
The following graph shows what happens when we sample a large number
The resulting plots should estimate the volume of our matrix.
5.606547839999998
xxxxxxxxxx
estimates[end]
5.5184
xxxxxxxxxx
det(A)
The punchline in this last graph: the volume of our matrix is the absolute value of the determinate.
Thus the physical interpretation of
This works in any dimension, not just
4×4 Array{Float64,2}:
-3.399 -3.273 -3.141 -1.812
-4.421 -4.434 -4.815 -2.708
4.941 4.193 -3.494 -1.508
0.11 0.338 0.775 4.577
xxxxxxxxxx
M = rand(-5:0.001:5, 4, 4)
-16.378
9.134
xxxxxxxxxx
hlower, hupper = estimate_bounds(M)
10000000
xxxxxxxxxx
htrials = 10000000
-14.494864906292989
xxxxxxxxxx
det(M)
14.869115720278915
xxxxxxxxxx
hestimates[end]
Next time: what is the physical interpretation of the sign of