From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: 3D Geometry problem
Date: 27 Dec 1999 08:24:08 GMT
Newsgroups: sci.math.num-analysis
Keywords: determine locations of points given bipartite distances
In an earlier article, Ed McBride asked how to determine
the locations of nine points given (1) all the distances from four of them
to the other five (2) the premise that the four are planar (3) normalization
conditions to remove ambiguity because of invariance under Euclidean motion.
I responded, optimistically and without really thinking about the particulars,
> I guess this looks to me like 20 quadratic equations in 20 unknowns. If
> you have a good estimate of the solution (e.g. if the positions are
> moving continuously and you merely need to update them to reflect
> new measurements) then a continuation method ought to work well. If
> instead you're working ab initio you could probably make an elimination
> theory / Groebner basis analysis to diagonalize the system of equations,
> but I doubt this would be fast, which was stated as a requirement.
When I actually went to try some examples I realized the situation was
rather like another one I had once considered, in which the following
observation is made: the fact that the points lie in R^3 puts algebraic
constraints on the possible interpoint distances. Therefore, the twenty
observed distances are not necessarily independent pieces of information.
Consequently if the measured distances are true there are actually
insufficient data to determine the positions uniquely!
To take a specific example, consider the case in which the four points
on a plane are near the corners of a 40x40 square, and the other five
points are more or less stacked above the center of the square. I picked
some values at random for the values a_{i,j} = dist(P_i, P_j)^2 in
this ballpark:
a15:=999;a16:=1001;a17:=1005;
a25:=1099;a26:=1102;a27:=1115;a28:=1131;a29:=1137;
a35:=1201;a36:=1207;a37:=1225;a38:=1251;a39:=1253;
a45:=1506;a46:=1502;a47:=1523;a48:=1554;a49:=1578;
Notice that a18 and a19 are not given; that's because they can be
determined from the other data. A few minutes' calculations by Magma
show that a18 = 59199/59, a19 = 59441/59. So only 18 of the equations give
independent information, and the solution set is 2-dimensional (i.e., NOT a
finite set of vectors in R^20). In this particular problem, we may for
example choose (x4,y4) at will, solve for x2 from
x2^2 - 44/81*x2*x4 + 341/2052*x4^2 + 341/2052*y4^2 = 10153/171,
and then compute x3 = 152/71*x2 - 22/71*x4, y3=-22/71*y4. Similar but
messier formulas also exist for the coordinates of each of the remaining five
points, always in terms of x2, x4, y4. The last two are more or less
arbitrary (we must choose point #4 in a certain region if we want the
coordinates of all points to be real).
While it is perhaps unexpected that this should be the conclusion in
the problem at hand, it is clear that this phenomenon must arise
in more general problems. If we have a set of n points and a set of m
points in R^k and we know all n*m distances between the pairs,
we might expect to determine all k*(n+m) coordinates of the points
(modulo the action of the Euclidean group, of dimension k*(k+1)/2 ).
But if the distances are chosen randomly these equations are nearly
certain to be inconsistent except for small n and m. Indeed, if
n = k + n' and m = k + m' for positive n' and m' with
n'*m' > k*(k-1)/2 , we have k^2 + (n'+m')*k + (n'*m') 'random' equations
in (3/2)*k^2 - (1/2)*k + (n'+m')*k unknowns, which will be inconsistent.
Here's the specific example I had encountered before: taking k=3
we see that for example n=m=5 will lead to an over-constrained
system in general, and that even when the n*m distances are chosen
correctly, the generic situation should lead to a unique solution
for the positions of the ten points. In brief, this means the following:
an arrangement of 25 hinged beams joining each of five points to each
of five other points will be rigid in R^3 (even though it contains
no triangles).
Returning to the original problem in this thread, let me simply note
that it will evidently be necessary to collect more data before the
positions of the nine points can be determined. Probably the points
can be quickly located once sufficient data are provided.
dave
==============================================================================
[The original poster responded that, in fact, there were _eight_ above-ground
points in addition to the four on the ground, and all 32 pairs of distances
were known. It was expected that with this extra information, the solution
would surely be unique. Not so. --djr]
==============================================================================
[A version of this letter was sent by me, around Dec 29 1999, in response to
the original poster's attempt to recover positions from distances starting with
the four points and the eight points roughly in two squares. The following
experiment shows that, in fact, the solution is still not unique. --djr]
OK, I ran some numbers.
Your description of the data set you ran was a little unclear but the
following points make a set consistent with your verbal description.
It really doesn't matter, I suppose, just what the pattern is, but what I did
was to take (1) P1 = origin, P2 on x-axis, P3, P4 on xy-plane;
(2) P1, P2, P3, P4 form a square of diagonal=20, plus random noise;
(3) P5 through P8 are the vertices and midpoints of a square of side 30 and
height 14, tucked into the first quadrant, again plus random noise.
Here are my nominal positions (coordinates in columns):
[0 14 15 2 2 13 31 29 30 16 1 0]
[ ]
P := [0 0 13 16 -1 2 0 15 29 27 28 17]
[ ]
[0 0 0 0 14 14 15 14 16 13 14 14]
The 4*8 distances between them range from 14.18 to 44.69; actually their
squares are nice integers; here are the squares of the distances:
[201 369 1186 1262 1997 1154 981 485]
[ ]
[341 201 514 646 1353 902 1149 681]
[ ]
[561 321 650 396 737 366 617 437]
[ ]
[485 513 1322 926 1209 486 341 201]
I want to stress that I didn't do anything on purpose to make this
example 'special'. While the theory supports the claims that I make below,
you should really create more examples to test them, since it is possible
that I by accident chose an example which is 'degenerate' in a way
I cannot perceive.
OK, try whatever method you want to take those last 32 numbers and try
to recover the 29 unknown coordinates. I used elimination theory on the
32 equations in 29 variables. It goes pretty fast. First I look for
relations among x2, x3, and y3 and find the _only_ one to be
3531/392*x2^2 - 214/21*x2*x3 + x3^2 + y3^2 - 39/2 = 0
In particular, this tells me already that there are not unique values for
these three variables!
Actually I'll let you in on a little number-theorists' secret: you can
describe _all_ the solutions (x2,x3,y3) to this last equation parameterically:
Take arbitrary rational m and n and compute
x2=14*(1-676*m+119626*m^2+156*n-66768*m*n+13482*n^2)/(-119626*m^2+63558*n^2+1),
x3=3*(598130*m^2+317790*n^2+5-550836*m*n-2782*m)/(-119626*m^2+63558*n^2+1),
y3=-13*(119626*m^2+63558*n^2-1-276060*m*n+642*n)/(-119626*m^2+63558*n^2+1),
For example, m=n=0 gives the triple (14,15,13) with which we began.
Special bonus: if m,n are rational, so are x2,x3,y3 -- we can do our
computations with exact arithmetic.
Next I use elimination to find relations among sets of variables
{x2, x3, y3, x_i, y_i, z_i} for i=4,5,...,12. This turns out to be nice
in every case. The simplest case i=4 leads to the solution
{x4 = -107/91*x2+16/13*x3, y4 = 16/13*y3, z4=0}
The other 8 are very similar to the case i=5 where I find
{x5 = -28/10593*(-214*x2*x3+26073+21*x3^2+21*y3^2)/x2,
y5 = 1/21186*(1460088*x3-3813480*x2-1391*x2*x3^2+10593*x2*y3^2+
1176*x3^3+1176*x3*y3^2)/y3/x2}
and determine z5 from z5^2 = 201 - (x5^2 + y5^2).
So there are _oodles_ of possible solutions. Pick any x2, x3, y3 satisfying
that one quadratic equation (e.g. pick any rational m,n and plug into
the parameterization I gave); then use formulas like those shown to
determine (x4,y4), (x5,y5), ..., (x12,y12); then compute the z's just
so that the 8 points have the right distance from the origin.
This last step puts some inequalities on the m's and n's since we must
be extracting square roots of _positive_ numbers. There are many parts of
the m-n plane where this process will work OK. I sat down and figured out
the region containing the origin m=n=0 where all the square roots could
be extracted. (It's pretty small in these coordinates.) For your amusement
I took a walk around the edge of the acceptable region to find some
solutions to the original problem which are markedly different. I will
give them below.
I should emphasize that the solutions are _exact_: the points match all
the 32 interpoint distances on the nose. I did not report the results
this way because it's too long to write, but each of the solutions below
lists 12 points whose x and y coordinates are rational and whose
z coordinates are either rational or square roots of rational numbers.
As you look at these solutions you might watch to see how individual points
among the 12 move around in space (the solutions are actually snapshots
of a continuous loop of solutions). Check out which points come nearly
down to the plane z=0 (all but two eventually do) and which go high
(point #9 gets as high as z=27). There may be other interesting patterns
too; I didn't check. It might be cool to animate this! (I can compute the
coordinates essentially instantly.)
So I don't know what you are really doing with this computation, but
you're going to need some more information to determine positions.
You've still got two degrees of freedom, and so need two more _independent_
bits of data. I'm guessing more airborne points won't help at all;
maybe another point on the ground would help. Certainly a couple of
distances e.g. among the points on the ground would help.
dave
Note: ts(x,y) was my Maple routine to find the points corresponding to
m=x/1000, n=y/1000. So ts(0,0) gives the 12 original points (you would
see here the transpose of the matrix P, above).
> ts(.28,.12);
[ 0 0 0 ]
[ 11.81476540 0 0 ]
[ 12.87093688 12.08754438 0 ]
[ 1.949066294 14.87697769 0 ]
[-.01740697290 -1.976504293 14.03898600]
[ 13.01713031 1.021068441 14.08941936]
[ 34.34637312 -1.504451800 2.015757620]
[ 31.97645726 14.66947332 4.930794398]
[ 33.16141518 29.70548685 3.860646941]
[ 16.57200411 27.84582569 10.19699324]
[-1.202364906 29.23343438 11.17857920]
[-2.387322840 17.42388262 13.25552730]
> ts(.09,.23);
[ 0 0 0 ]
[13.62215978 0 0 ]
[14.24552784 11.07190448 0 ]
[1.515692535 13.62695936 0 ]
[1.672394027 -3.708762981 13.58116988]
[12.97750294 .1706740508 14.16175441]
[31.47677204 -1.593417516 13.88070037]
[29.42129770 15.95381814 11.91062251]
[30.44903486 32.42427645 4.303786008]
[16.06071446 29.62161674 4.314310293]
[.6446568536 30.30893098 7.871030574]
[-.3830803197 17.36090190 13.54445772]
> ts(-1.1,.03);
[ 0 0 0 ]
[31.02197931 0 0 ]
[30.87443226 12.56706094 0 ]
[1.522907984 15.46715192 0 ]
[13.25452500 -2.677248111 4.260271077]
[18.21874725 1.359690723 5.935359293]
[26.34202003 .8184794538 22.16817702]
[25.43943417 16.16549075 18.80191741]
[25.89072710 30.73266662 19.54925710]
[19.57262605 27.47556318 4.000717073]
[12.80323207 27.23693906 8.673315381]
[12.35193913 15.77311409 9.145407142]
> ts(-1.17, -.33);
[ 0 0 0 ]
[31.19718890 0 0 ]
[31.65090507 17.69640911 0 ]
[2.272551136 21.78019582 0 ]
[13.35480254 3.095529469 3.614823137]
[18.29114476 5.794399138 .9268021472]
[26.36879563 5.135228090 21.54799410]
[25.47127885 16.06440679 18.84539170]
[25.92003722 26.39398214 25.07008929]
[19.63741990 24.29471586 13.34685435]
[12.90604417 24.35428350 14.87625284]
[12.45728579 16.22854512 8.151708655]
> ts(-1.03, -1.6);
[ 0 0 0 ]
[20.24817171 0 0 ]
[24.34582849 27.51779183 0 ]
[6.155806792 33.86805149 0 ]
[6.666983604 12.08893790 3.226284225]
[14.27260855 12.77339541 1.460484406]
[26.71817665 10.62941284 18.95137513]
[25.33533575 17.84897495 17.36475901]
[26.02675620 24.39625887 26.91524689]
[16.34686990 24.38407953 17.09375646]
[5.975563155 25.85578396 16.63643836]
[5.284142708 20.72576490 5.245998980]
> ts(-1.0,-2.1);
[ 0 0 0 ]
[16.73330992 0 0 ]
[22.29281473 28.31491092 0 ]
[7.761880084 34.84912114 0 ]
[4.183382176 13.28248999 2.659844620]
[13.38658230 13.24133729 3.803472295]
[28.44636433 10.00188048 16.63630800]
[26.77305521 17.14662378 15.84918950]
[27.60970978 23.44537624 26.17285350]
[15.89654598 24.33251978 17.58488861]
[3.346727619 26.72598574 15.98502739]
[2.510073063 21.80459944 1.805263554]
> ts(-.8, -2.2);
[ 0 0 0 ]
[13.89584963 0 0 ]
[19.92681488 26.54874092 0 ]
[8.186234680 32.67537344 0 ]
[1.910449467 12.53873493 6.334848799]
[12.99289524 11.90451104 7.646390671]
[31.12780650 7.483547364 12.69079124]
[29.11281636 15.21093211 13.53039056]
[30.12031144 21.87504597 24.72345454]
[16.01538045 23.57254072 18.48899439]
[.9029543944 26.93023352 15.96706600]
[-.1045406749 21.73511588 3.545956697]
> ts(-.6, -2.0);
[ 0 0 0 ]
[12.83605751 0 0 ]
[18.56396144 24.87987146 0 ]
[7.755005802 30.62138026 0 ]
[.9646409068 11.41110307 8.358001831]
[12.96209417 10.65867717 9.347551326]
[32.59429041 5.817360592 9.474732070]
[30.41293528 14.07683222 11.78542164]
[31.50361284 21.18107728 23.57719965]
[16.23412688 23.08872976 18.90406525]
[-.1260366640 26.77481976 16.25094280]
[-1.216714233 21.23810690 5.697580337]
> ts(-.2, -1.33);
[ 0 0 0 ]
[11.86330465 0 0 ]
[16.23973558 21.24424160 0 ]
[6.038206458 26.14675890 0 ]
[.03110419968 8.332530088 11.47030840]
[13.01231008 8.011909054 11.63997851]
[34.25428333 3.259372783 1.421464759]
[31.89406408 12.83040574 8.952617740]
[33.07417370 21.20139563 21.29788387]
[16.55263895 22.72205976 19.07139596]
[-1.149005425 26.27455294 17.00963414]
[-2.329115052 19.73935464 9.483306465]
==============================================================================
From: Ed McBride
Subject: Re: Sample set of 12 points (LONG)
Date: Thu, 30 Dec 1999 09:19:51 -0700
Newsgroups: [missing]
To: Dave Rusin
[deletia --djr]
> > For various reasons, we are limited to eight upper and four lower
> > points.
I sort of lied here. We "could" do nearly anything, but the electronics
(multiplexing all the signals) limits us to these numbers, and the cost
of re-doing the system is not warranted unless we can first solve all
this opther stuff and convince ourselves we can sell a whole bunch of
systems.
> > Distances among upper points is not feasible, but all six
> > distances between lower points "could" be obtained. However, if any
> > five were known, then their locations are also known, and then each
> > upper point is also known from simple trig. So, can we make this thing
> > work with one lower distance? Or, if not, two? Or...
>
> No one distance will suffice.
>
> Any two distances would give a finite solution set; you'd have to hope
> that the various solutions are either sufficiently different that you can
> tell which ones are wrong, or sufficiently close that it doesn't matter
> which is really the right configuration.
>
> Any set of three distances would have a unique solution unless you are
> deucedly unlucky. There is the little matter of noisy data which would then
> conflict and have to be reconciled; I'd have to give that some more thought.
Did you answer the above three questions as a result of something that
was implicit in the previous work you did, or did this require aditional
analysis?
>
> This has been an interesting question. I was even able to explain the
> problem to my teenagers. I told them to imagine there were 8 Mars landers
> with little transmitters and 4 Mars rovers with litte receivers about
> whose positions we knew nothing except that the rovers were on the ground
> and from the transmissions we could determine distances. They thought
> that was a pretty cool problem. They also said not to lose the landers
> this time :-)
Good point. You may have noted that I work in "real" units whenever
possible, and try to avoid anything that reminds me of all those people
who got so good surrendering to Germans.
>
> It's also a little like a toy I saw this year consisting of zillions of
> little plastic sticks hinged together to make a four-foot soccer-ball sort
> of thing except the pattern of sticks was more complicated than the usual
> pentagons and hexagons of the soccer ball. One can push in on the sides
> and the thing collapses to a one-foot ball of folded sticks. Here all the
> distances between hinge points stay constant but there is this one-parameter
> family of possible positions for the whole configuration.
Yeah, I've been using a similar analogy here. I think of your
development of many (How many BTW?) distinct exact solutions as a whole
bunch of elastic sticks that are stable at one exact length each. So
they deform to get from one solution to another, but lock back to their
original lengths at each new solution.
Hope you all have a great New Years. Ed
==============================================================================
[Actual application calibrating a triangulating device involving 4 roving
transmitters and 8 fixed receivers. During the calibration the 8 receivers'
locations are completely unknown; road crews position the 4 transmitters
more or less in specified nominal positions on the floor. The goal is to
determine the positions of all objects, in particular the 8 fixed receivers
in the air, without assuming the on-the-floor distances have been
measured accurately if at all. Below, we succeed if given at least two
distances on the floor sharing a common vertex. --djr]
==============================================================================
From: Dave Rusin
Subject: Got a nice solution for you
Date: Tue, 4 Jan 2000 12:33:10 -0600 (CST)
Newsgroups: [missing]
To: emcbride@wybron.com
First of all I must tell you that I tried some examples last night and
discovered that adding the lengths of the two diagonals does NOT seem
sufficient information to determine positions. I haven't quite figured out
why that happens.
But then I put away the keyboard for a little while and found that it's
actually quite easy to analyze this whole thing with pencil and paper.
You can probably turn this into a fast and robust algorithm -- still
requiring at least two additional measurements, of course, but using them
efficiently.
Here's my analysis. We're trying to locate four points on the ground and
let's say N of them in the air. As before I'll set up coordinates so
that one of the ground points -- I'll call it u_0 -- is at the origin,
so that the positions of all the other points can be thought of as vectors
in R^3. Call the ground vectors u_1, u_2, u_3 (so their z-coordinates are
zero) and the other points v_j (j=1, 2, ..., N).
Now, you start with 4N equations telling you the squares of certain
distances. These distances are the lengths of vectors between points, which
in turn are differences of the position vectors, that is, our equations
have the form
D_{i,j} = || u_i - v_j ||^2
for some positive constants D_{i,j} which your instruments will measure
very accurately. I'm going to have to assume you begin with at least some
additional data. It will be sufficient to have the crew measure two distances
from the point we called u_0; that is, they are measuring the lengths
of, say, u_1 and u_2, giving two more equations
a_1 = || u_1 ||^2
a_2 = || u_2 ||^2
You can have the guys measure the distance from the origin to the remaining
ground point too, but I'll show how that distance can be computed from the
others. Probably it would be profitable to have them measure all three,
then use the redundant measurement to improve accuracy with a least-squares
fit somewhere along the way. I'll get to that later, I think.
Anyway, you now have 4N+2 quadratic equations in 3N+5 variables. But it
makes sense to rewrite these equations by simply subtracting one (from each
set of four) from the others. That is, for each j we replace our four
equations above with these four:
D_{0,j} = || u_0 - v_j ||^2 = ||v_j||^2 (the old i=0 one)
D_{i,j}-D_{0,j} = || u_i - v_j ||^2 - || v_j ||^2 (for i=1,2,3)
Now, ||v||^2 = < v, v > where the pointy brackets indicate an inner product
(dot product) so when we expand this last line we get, after some manipulation,
D_{i,j}-D_{0,j}-a_i = -2 < u_i, v_j >
Since the z-coordinate of u_i is zero, this last equation involves only
the first two coordinates of v_j, and is linear in them. So the strategy
is to ignore the first equation D_{0,j}=... until the very end, and then
use it to compute the z-coordinate of v_j after its x- and y-coordinates
are computed from the other equations. I'm setting aside exactly N
equations which I will use to solve (uniquely) for the N remaining
(positive) variables z_j. In what follows then, I will have only 3N+2
equations in 2N unknowns x_j, y_j, plus the 5 unknown coordinates of
the u_i's.
Let's not make any use of the two known values of the a_i just yet;
treat them as variables. Those 3N equations may now be simply written
in matrix form as A X = B where X is the 2 by N matrix whose columns
are the unknowns [x_j, y_j]' , A is the 3 by 2 matrix whose rows are
the coordinates of the u_i, and B is the 3 by N matrix whose (i,j)
entry is (-1/2)(D_{i,j}-D_{0,j}-a_i).
Some elementary linear algebra
shows that since A and X have rank at most 2, so must B, so that
every 3x3 submatrix of it has determinant zero. Well, any of those 3x3
minors has a determinant which is linear in the a_i; in particular, this
is now your equation to determine a_3 if you are given a_1 and a_2.
(Depending on the accuracy of your hardware you may find that the different
minors give slightly different linear relations among the a_i. It's
probably a good idea, from a robustness point of view, to compute many or
all of the minors and select an optimal linear relation by averaging or
some kind of least-squares fit. This also gives you a chance to fudge data
if you _do_ have the guys measure all three a_i's: assume an unknown
relative error in each measurement, then determine the errors which
make the matrix B as close to singular as possible. I'll leave this
part to you...) However you do it, the rank-2 condition and the knowledge
of at least two of the a_i are enough to let us treat the matrix B
now as known.
Also note that for any column vector C, the equation A X = C is only
solvable if C lies in the column-space of A, that is, it's in the
plane (through the origin) spanned by the two columns of A. Applying
this reasoning to each column C of the matrix B, we see _all_ those
columns lie in the same plane as the columns of A. Of course, unless you're
very unlucky, any two of those columns of B ought to span the same plane.
That's handy since the matrix B is now known, and therefore we can
actually compute the plane in question.
So now you can address the computation of A . Recall its rows contain
the five unknown coordinates of the points u_1, u_2, u_3 on the floor.
But now you have five pieces of information about those coordinates!
(1) || u_i ||^2 = a_i for i=1, 2, 3 (the numbers a_i now known)
(2) the x-coordinates of the three vectors give a point in this special plane
(3) so do the y-coordinates (note: y-coordinate of u_1 is assumed to be zero).
So use (1) to compute the vector u_1, then use (2) and (3) to express
the x- and y-coordinates (respectively) of u_3 in terms of those of u_2,
plug into the appropriate equation of (1) and end up with just two
quadratic equations to solve in the two coordinates of u_2. (This is actually
very easy in this problem.) Then work backwards to get the coordinates of u_3,
and hence the whole matrix A, and then the matrix X=A\B (which
contains the x- and y-coordinates of the vectors v_j). Finally use
those long-discarded equations D_{0,j}=||v_j||^2 to compute the
z-coordinates of the v_j.
Observe that the solutions now _are_ unique at each step (using positivity
of z_j at the end) except possibly for the solution of two quadratics
in two unknowns. These turn out to be unique too, given appropriate sign
conventions.
I will do an example for you. Recall the data I sent once before, with
these interpoint distance D_{i,j}:
[201 369 1186 1262 1997 1154 981 485]
[ ]
[341 201 514 646 1353 902 1149 681]
D := [ ]
[561 321 650 396 737 366 617 437]
[ ]
[485 513 1322 926 1209 486 341 201]
From this I compute the matrix B:
[ -70+a1/2, 84+a1/2, 336+a1/2, 308+a1/2, 322+a1/2,126+a1/2,-84+a1/2,-98+a1/2]
[-180+a2/2, 24+a2/2, 268+a2/2, 433+a2/2, 630+a2/2,394+a2/2,182+a2/2, 24+a2/2]
[-142+a3/2,-72+a3/2, -68+a3/2, 168+a3/2, 394+a3/2,334+a3/2,320+a3/2,142+a3/2]
The rank-2 condition is expressed by setting the determinant of the first
3 columns to zero:
-38304 + 6916 a3 - 8512 a2 + 8132 a1 = 0.
Well, the last time I worked with these data I didn't assume I knew any
more distances. This time I will assume it to be known that the
squared distance from u0 to u1 is 196 and the squared distance from u0
to u2 (across the diagonal) is 394. From this eqaution I then conclude
(correctly!) that the squared distance to the fourth ground point is 260.
With these data, the matrix B becomes a bunch of scalars:
[ 28 182 434 406 420 224 14 0]
[ ]
[ 17 221 465 630 827 591 379 221]
[ ]
[-12 58 62 298 524 464 450 272]
It does indeed have rank 2, and in fact a row vector which annihilates it
on the left is [107, -112, 91]. In other words, the plane containing all
those columns is the plane 107x - 112y + 91z = 0. From the assumed
matrix equation A X = B we then see A is also annihilated by this
vector.
Well, here's A, of course:
[X1 0 ]
[ ]
A := [X2 Y2]
[ ]
[X3 Y3]
so now these five coordinates are just about known. Our equations are
(1) X1^2 = 196, X2^2+Y2^2=394, X3^2+Y3^2=260
(2) 107 X1 - 112 X2 + 91 X3 = 0
(3) 107 *0 - 112 Y2 + 91 Y3 = 0
So I see X1=14[*], X3 = -214/13+16/13*X2, Y3 = 16/13*Y2. All that's left is
X2^2+Y2^2=394 and 45796-6848*X2+256*X2^2+256*Y2^2 = 43940
and in fact you'll never have a Y2 except squared, so we can subtract
and rewrite this this way:
146660 - 6848 X2 = 43940 and Y2^2 = 394 - X2^2
whose solution is X2=15, Y2=13[*]
[*]Note: I'm assuming you know which are the positive directions for the
axes so we use the positive square root.
Working back, I get X3=2, Y3=16, so that the equation A X = B reads
[14 0]
[ ] [x1 y1 x2 y2 x3 y3 x4 y4]
[15 13] * [ ] =
[ ] [x5 y5 x6 y6 x7 y7 x8 y8]
[ 2 16]
[ 28 182 434 406 420 224 14 0]
[ ]
= [ 17 221 465 630 827 591 379 221]
[ ]
[-12 58 62 298 524 464 450 272]
which has the unique solution X =
[ 2 13 31 29 30 16 1 0]
[ ]
[-1 2 0 15 29 27 28 17]
Finally using the distances from the origin (the top row of D) we see
eg. x_1^2 + y_1^2 + z_1^2 = 201 becomes simply z_1^2 = 201-2^2-(-1)^2=196
so z_1 = 14; likewise I compute all the z_i = [14, 14, 15, 14, 16, 13, 14, 14]
Check your old messages: you'll see I have faithfully recovered all the
coordinates of the original points.
I'm glad you're finding the elimination theory to be interesting.
There's a bit of material at http://www.math-atlas.org/index/13PXX.html
which you may find useful. When all is said and done I don't think it's
really necessary in this computation, now, but it's good to keep in
mind for the future.
By the way, I think you've gotten the wrong idea about mathematicians.
Many of us work on applied problems. I don't personally feel very well
qualified to comment on industrial matters, but I do enjoy seeing the
connections to the physical world. I have colleagues here who help
design airplane wings and paper processing plants and all manner of things.
It's cool. In fact, I'm envious of your exposure to such a variety of
circumstances. But a few decades of academic work have left me more
confident dealing with more theoretical matters, so the closest I seem
to get is as intermediary between camps, as I am in the present circumstance.
dave
==============================================================================
From: Ed McBride
Subject: Re: Got a nice solution for you
Date: Tue, 04 Jan 2000 12:04:53 -0700
Newsgroups: [missing]
To: Dave Rusin
Dave,
Got it and printed it. Scanned it, but too fast to understand. I'll
read it in detail tomorrow.
>
> I'm glad you're finding the elimination theory to be interesting.
> There's a bit of material at http://www.math-atlas.org/index/13PXX.html
Right, your web page is high on my list of priorities, I hope tomorrow
morning, or tonight if I get my other stuff done.
[deletia --djr]
> Many of us work on applied problems. I don't personally feel very well
> qualified to comment on industrial matters, but I do enjoy seeing the
> connections to the physical world. I have colleagues here who help
> design airplane wings and paper processing plants and all manner of things.
Seriously, I always thought THE most important stuff you folks did was
in the area of uniqueness, and as you did here, determining whether a
solution exists, stuff like that. It's awfully nice to "know" that
there are N linearly independent solutions to an Nth order O.D.E. and
exactly one particular solution, and all the other things you've done
over the years. Try to understand how valuable your solution was;
without it, I'm still trying iterative numerical solutions, and thinking
I'm getting stuck at local minima, and never even considering that there
are multiple solutions (It is STILL difficult for me to visualize the
tinker toy being assembled in many different ways and all the sticks
staying the same length).
> It's cool. In fact, I'm envious of your exposure to such a variety of
> circumstances. But a few decades of academic work have left me more
> confident dealing with more theoretical matters, so the closest I seem
> to get is as intermediary between camps, as I am in the present circumstance.
Well, it seems to me you're doing a great job of it!
Ed
==============================================================================
From: Ed McBride
Subject: Solution
Date: Wed, 05 Jan 2000 11:29:24 -0700
Newsgroups: [missing]
To: rusin@math.niu.edu
Dave,
I read what you sent, and almost everything makes sense.
Congratulations on finding a very clever solution! My biggest problem
is that I do linear algebra by example, never having "learned"
everything. So I'm starting the following:
1. Re-write what you sent using subscript notation, and putting in all
the rationale to force me to understand rather than mimic.
2. Go through your example carefully, making sure I can get all the
answers.
3. Write a "program", probably in Mathematica, and make sure it can do
your example.
4. The final solution has to be in C to go into the processor, but I
fortunately don't have to write it, merely provide the algorithm. so
this step is pretty trivial, especially for ME.
I did something very stupid, and erased your message after printing
it. So I can't ask or respond cleverly. Anyway,
You use the notation X = A \ B. Since our original matrix equation was
A X = B, I started to think your equation was X = (A inverse) B. But A
isn't square, so it doesn't have an inverse. Is it a 2 by 3 matrix that
pre-multiplies A to yield a 2 by 2 Identity matrix? Whatever it is, is
it straightforward to calculate it from A?
You are correct about knowing directions. I envision the points in a
sort-of square, with one diagonal running left-to-right across the
stage. Point 1 (0,0,0) will be at the left vertex. Point 2 (x2,0,0)
will be at the right vertex. Point 3 (x3,y3,0) will be the vertex such
that x3 > 0 and y3 > 0. Point 4 (x4,y4,0) will be such that x4 > 0, y4
< 0.
I got very confused in your linear algebra tutorial, second paragraph.
(1) What is a plane (through the origin) spanned by the two columns of
A? (2) How can A X = C be valid for a column vector C? A is 3 by 2, X
is 2 by 8, so why doesn't C have to be 3 by 8?
In your example, I follow where you calculate B(numbers plus a1,a2,a3).
Then use the rank-2 condition to get an equation involving a1,a2,a3 and
use the two known ones to calculate the unknown one (I don't see why all
the higher-order terms in the a's went away, but I haven't worked
through the determinant yet.) Then you use the a's to get B(numbers
only ). Then you somehow determined a row vector [107,-112,91] that
"annihilates it on the left". I understand that if you multiply this
row vector times B you get a 1 by 8 (row vector) with all zeroes. And if
you multiply it by A you get a 1 by 2 with all zeroes which you use,
along with the three distances, to find A. But this row vector is
obviously not unique. I would have used the first two columns of B, set
the row vector equal to [1,y,z] and multiplied to give me two
simultaneous equations for y and z. You obviously have a more clever
way, but I haven't been able to figure it out. Trade secret?
Time to get to work.
[deletia --djr]
Thanks again,
Ed
==============================================================================
From: Dave Rusin
Subject: Re: Solution
Date: Thu, 6 Jan 2000 15:29:47 -0600 (CST)
Newsgroups: [missing]
To: emcbride@wybron.com
> So I'm starting the following
Let me know if anything is unclear. I hammered out the example in Maple;
my Mathematica syntax is pretty rusty, but perhaps you could make the
translations.
>erased your message
I keep copies. If you want me to resend it just remind me which you want.
By the way, I will probably throw this correspondence into the morass at
my web site in case someone else has a similar problem some day. If you
want me to remove all traces to your name, let me know; otherwise I'll
just strip the letters to the mathematical content and retain some of
the headers. You may have already seen how I do this with other entries
at the website.
> You use the notation X = A \ B
I probably shouldn't do that; it's supposed to mean A^(-1) B, I guess.
What I meant was the solution to the equation A X = B. In fact (assuming
the first two rows of A are linearly independent) you can just drop the
last row from the whole equation -- the other steps are supposed to
guarantee that the same linear relation holds among the rows of A as
among the rows of B. If we refer to these depeditated matrices as
A' and B' then the solution to A X = B is X = (A')^(-1) (B').
> I envision the points in a sort-of square,
You know, if you intend to ask the road crew to measure all _three_
distances from the vertex called (0,0), it might make sense to ask them
to spread out the beltpacks into a Y shape. Attach three of them to
the "origin" one with canvas straps, and ask them just to pull tight
on those other three. The angles don't matter at all (they could even
have the four vertices at the corners of a square as you originally
proposed) as long as those 2 or three distances are accurate. By picking
a "Y" as the nominal shape, you get a good spread of the points on the
floor, which I imagine (I haven't run experiments) would give the
smallest error in the computed locations for a given error in the
measurements caused by the road crew.
> I got very confused in your linear algebra tutorial, second paragraph.
> What is a plane (through the origin) spanned by the two columns of A?
Take the numbers in the columns to be coordinates of two points in 3-space;
those two points lie on a unique plane through the origin.
> (2) How can A X = C be valid for a column vector C?
My bad. This X is not the same X as in the previous discussion. I
just mean "the problem A*(an unknown vector) = (a known vector) is
solvable iff the known vector is in the span of the columns of A".
> I would have used the first two columns of B, set
> the row vector equal to [1,y,z] and multiplied to give me two
> simultaneous equations for y and z. You obviously have a more clever
> way, but I haven't been able to figure it out. Trade secret?
If the magicians explain all their tricks no one will come to watch :-)
Actually I did just exactly what you did, and then cleared denominators
at the end. Strictly speaking that's unwise, since there is always the
possibility that the first coordinate of the vector you're looking for
will be a 0. Numerical analysis types will tell you there are more
stable methods of solving this kind of equation using matrix factorizations
and so on. I'm sort of hoping not to have to get into these details on
the assumption that you have a well-prepared library of function calls
at your disposal (e.g. LAPACK or something) or are willing to get the
routines from netlib or GAMS . See www.math-atlas.org/index/65-XX.html
[deletia --djr]
dave