MATLAB Central Newsreader - Solving equations

Re: Solving equations

Miroslav Balda — Tue, 19 Aug 2008 06:28:02 -0400

"Mazahir " <maz_p5@hotmail.com> wrote in message
<g8bugl$e7c$1@fred.mathworks.com>...
> Hello,
>
> I am finding out the location of a sound source using
> microphones. The co-ordinates of the 3 mics are fixed.
> Suppose the co-ordinates of the 3 mics are (x1,y1),(x2,y2)
> and (x3,y3) and the distance of source of sound from the 1st
> mic to the 2nnd is - del12 and the source of sound from the
> 1st mic to the 3rd is del13. how do i find the location of
> the source (x,y) in MATLAB using the following formula.
>
> del12=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x2-x)^2+(y2-y)^2)
> del13=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
>
> Solving this equation of 2 unknowns simultaneously will give
> me the point (x,y). But i do not know how to do it in
> matlab. I think there is a solution using matrices. Please
> help. thank you.

Hi,

Mazahir, your problem is more complicated, because there is
one equation more:
del23=sqrt((x2-x)^2+(y2-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
Since your measured dels suffer from measurement error, the
three equations are overdetermined for two unknowns [x,y].
It is a problem which can be solved by a least squares
method. there is the code for simulated problem:

x = [14,95,72];
y = [30,18,73];
xy = [x;y];
dxy = [59,27,39]; % approximate distances from corners
d = [dxy(1)-dxy(2),dxy(2)-dxy(3),dxy(3)-dxy(1)]; % deltas
del = @(a,b) sqrt((a-b)'*(a-b));
res = @(z) [del(xy(:,1),z)-del(xy(:,2),z) - d(1)
            del(xy(:,2),z)-del(xy(:,3),z) - d(2)
            del(xy(:,3),z)-del(xy(:,1),z) - d(3)
           ];
[XY,ssq,cnt] = LMFnlsq(res,sum(xy')'/3,'Display',1)

with the solution:

XY =
   73.0034
   33.8819
ssq =
  4.6659e-024
cnt =
     4

The solution is very good, because sum of squares from the
staring point, chosen in the centre of gravity ofthe
triangle, has been ssq=1e3 (!). The function LMFnlsq is from
File Exchange under Id 17534.

Hope it helps.

Mira

Re: Solving equations

Mazahir — Wed, 20 Aug 2008 18:25:04 -0400

"Miroslav Balda" <balda.nospam@cdm.it.cas.cz> wrote in
message <g8dp5i$509$1@fred.mathworks.com>...
> "Mazahir " <maz_p5@hotmail.com> wrote in message
> <g8bugl$e7c$1@fred.mathworks.com>...
> > Hello,
> >
> > I am finding out the location of a sound source using
> > microphones. The co-ordinates of the 3 mics are fixed.
> > Suppose the co-ordinates of the 3 mics are (x1,y1),(x2,y2)
> > and (x3,y3) and the distance of source of sound from the 1st
> > mic to the 2nnd is - del12 and the source of sound from the
> > 1st mic to the 3rd is del13. how do i find the location of
> > the source (x,y) in MATLAB using the following formula.
> >
> > del12=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x2-x)^2+(y2-y)^2)
> > del13=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
> >
> > Solving this equation of 2 unknowns simultaneously will give
> > me the point (x,y). But i do not know how to do it in
> > matlab. I think there is a solution using matrices. Please
> > help. thank you.
>
> Hi,
>
> Mazahir, your problem is more complicated, because there is
> one equation more:
> del23=sqrt((x2-x)^2+(y2-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
> Since your measured dels suffer from measurement error, the
> three equations are overdetermined for two unknowns [x,y].
> It is a problem which can be solved by a least squares
> method. there is the code for simulated problem:
>
> x = [14,95,72];
> y = [30,18,73];
> xy = [x;y];
> dxy = [59,27,39]; % approximate distances from corners
> d = [dxy(1)-dxy(2),dxy(2)-dxy(3),dxy(3)-dxy(1)]; % deltas
> del = @(a,b) sqrt((a-b)'*(a-b));
> res = @(z) [del(xy(:,1),z)-del(xy(:,2),z) - d(1)
> del(xy(:,2),z)-del(xy(:,3),z) - d(2)
> del(xy(:,3),z)-del(xy(:,1),z) - d(3)
> ];
> [XY,ssq,cnt] = LMFnlsq(res,sum(xy')'/3,'Display',1)
>
> with the solution:
>
> XY =
> 73.0034
> 33.8819
> ssq =
> 4.6659e-024
> cnt =
> 4
>
> The solution is very good, because sum of squares from the
> staring point, chosen in the centre of gravity ofthe
> triangle, has been ssq=1e3 (!). The function LMFnlsq is from
> File Exchange under Id 17534.
>
> Hope it helps.
>
> Mira

Hi Mira,

Sorry but I could not understand your solution well. I know
that solving by least square method might be the best option
but can you please describe the solution and the variables
used like d,a,b,z, res, etc.. dxy is the approx. distance
from corners, but distance of what? Also are the values
randomly taken by you?

Also below I am explaining you the problem again in detail,
so that you can get a clear picture.

I have to find the location of a sound source on a 2d plane.
(I am not considering z axis). I have 4 mics the
co-ordinates of which are m1(0,0), m2(0,6), m3(4,6), m4(4,0).
del12 is the difference between the distance from mic 1 to
the source and from mic 2 to the source.
del12=((time taken to reach 1st mic-time taken to reach 2nd
mic) x v sound i.e. 340m/s)/fs i.e. 44000. Therefore, for a
particular set of readings, the calculated del12 = 0.0848.
Similarly, del13 = 0.9098 and del14 = 0.5937

Now solving the equations below simultaneously using least
square method will give me the point.

del12=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x2-x)^2+(y2-y)^2)
del13=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
del14=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x4-x)^2+(y4-y)^2)

Now this is the exact problem which I cant get hang of.

I think 1st solving with just 3 mics and 2 equations will be
good enough to predict the output before going to the 4th mic.

Also what I know is that such systems can also be solved by
techniques such as multilateration. If yes, would that be
easier?

Please do reply soon.

Thank you,
Mazahir

Re: Solving equations

Miroslav Balda — Wed, 20 Aug 2008 20:49:01 -0400

"Mazahir " <maz_p5@hotmail.com> wrote in message
<g8hni0$klf$1@fred.mathworks.com>...
:
SNIP
:
> Hi Mira,
>
> Sorry but I could not understand your solution well. I know
> that solving by least square method might be the best option
> but can you please describe the solution and the variables
> used like d,a,b,z, res, etc.. dxy is the approx. distance
> from corners, but distance of what? Also are the values
> randomly taken by you?
>
>
> Also below I am explaining you the problem again in detail,
> so that you can get a clear picture.
>
> I have to find the location of a sound source on a 2d plane.
> (I am not considering z axis). I have 4 mics the
> co-ordinates of which are m1(0,0), m2(0,6), m3(4,6), m4(4,0).
> del12 is the difference between the distance from mic 1 to
> the source and from mic 2 to the source.
> del12=((time taken to reach 1st mic-time taken to reach 2nd
> mic) x v sound i.e. 340m/s)/fs i.e. 44000. Therefore, for a
> particular set of readings, the calculated del12 = 0.0848.
> Similarly, del13 = 0.9098 and del14 = 0.5937
>
> Now solving the equations below simultaneously using least
> square method will give me the point.
>
> del12=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x2-x)^2+(y2-y)^2)
> del13=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
> del14=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x4-x)^2+(y4-y)^2)
>
> Now this is the exact problem which I cant get hang of.
>
> I think 1st solving with just 3 mics and 2 equations will be
> good enough to predict the output before going to the 4th
mic.
>
> Also what I know is that such systems can also be solved by
> techniques such as multilateration. If yes, would that be
> easier?
>
> Please do reply soon.
>
> Thank you,
> Mazahir

Hi Mazahir,

Since that you have changed your descriptiom of the problem,
I will not return to the previous example, which was set by
my by random distances, which I chose. The solution of your
problem is as follows:

x = [0,0,4,4];
y = [0,6,6,0];
xy = [x;y];
dij = [0.0848,0.99098,0.5937];

del = @(d) sqrt(d'*d);
res = @(z) [del(xy(:,1)-z) - del(xy(:,2)-z) - dij(1)
            del(xy(:,1)-z) - del(xy(:,3)-z) - dij(2)
            del(xy(:,1)-z) - del(xy(:,4)-z) - dij(3)];

[XY,ssq,cnt] = LMFnlsq(res,[2;3],'display',1)

>> test080820
***************************************************************************
  itr nfJ SUM(r^2) x dx l
      lc
***************************************************************************
   0 1 1.3417e+000 2.0000e+000 0.0000e+000

0.0000e+000 1.0000e+000
                        3.0000e+000 0.0000e+000
   1 2 2.6097e-002 2.6290e+000 -6.2904e-001
0.0000e+000 1.0000e+000
                        3.1136e+000 -1.1355e-001
   2 3 2.4987e-002 2.6390e+000 -9.9365e-003
0.0000e+000 1.0000e+000
                        3.1240e+000 -1.0411e-002
   3 4 2.4987e-002 2.6392e+000 -1.9470e-004
0.0000e+000 1.0000e+000
                        3.1240e+000 -3.6993e-005

   4 5 2.4987e-002 2.6392e+000 6.9462e-007
0.0000e+000 1.0000e+000
                        3.1240e+000 -1.9698e-006
XY =
    2.6392
    3.1240
ssq =
    0.0250
cnt =
     4

* xy are coordinates of microphones,
* dij are your calculated differences,
* del is the handle of anonymous function for calculation of
yours sqrt((x1-x)^2 + ....),
* res is the handle to anonymous function that declares
residuals (errors of your equations)
* XY are coordinates of the sound source,
* ssq is a sum of squares of residuals,
* cnt number of calls to res and Jacobian matrix.

You see that ssq is only by approx. 10^2 lower then for the
initial guess. It means that yours delijs are inexact.
Better way would be in taking times of wave approach to
microphones. More over having reading from 4 microphones
could set 6 equations -> residuals and by least squares get
much more accurate coordinates of the source.

I think, that it is all what to say to it.
Hope it helps.

Mira

PS: The time shift makes the communication difficult. Now is
almost 23 o'clock at Pilsen (CZ).

Re: Solving equations

Mazahir — Sun, 24 Aug 2008 19:37:02 -0400

"Miroslav Balda" <miroslav.nospam@balda.cz> wrote in message
<g8hvvt$r50$1@fred.mathworks.com>...
> "Mazahir " <maz_p5@hotmail.com> wrote in message
> <g8hni0$klf$1@fred.mathworks.com>...
> :
> SNIP
> :
> > Hi Mira,
> >
> > Sorry but I could not understand your solution well. I know
> > that solving by least square method might be the best option
> > but can you please describe the solution and the variables
> > used like d,a,b,z, res, etc.. dxy is the approx. distance
> > from corners, but distance of what? Also are the values
> > randomly taken by you?
> >
> >
> > Also below I am explaining you the problem again in detail,
> > so that you can get a clear picture.
> >
> > I have to find the location of a sound source on a 2d plane.
> > (I am not considering z axis). I have 4 mics the
> > co-ordinates of which are m1(0,0), m2(0,6), m3(4,6),
m4(4,0).
> > del12 is the difference between the distance from mic 1 to
> > the source and from mic 2 to the source.
> > del12=((time taken to reach 1st mic-time taken to reach 2nd
> > mic) x v sound i.e. 340m/s)/fs i.e. 44000. Therefore, for a
> > particular set of readings, the calculated del12 = 0.0848.
> > Similarly, del13 = 0.9098 and del14 = 0.5937
> >
> > Now solving the equations below simultaneously using least
> > square method will give me the point.
> >
> > del12=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x2-x)^2+(y2-y)^2)
> > del13=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
> > del14=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x4-x)^2+(y4-y)^2)
> >
> > Now this is the exact problem which I cant get hang of.
> >
> > I think 1st solving with just 3 mics and 2 equations will be
> > good enough to predict the output before going to the 4th
> mic.
> >
> > Also what I know is that such systems can also be solved by
> > techniques such as multilateration. If yes, would that be
> > easier?
> >
> > Please do reply soon.
> >
> > Thank you,
> > Mazahir
>
> Hi Mazahir,
>
> Since that you have changed your descriptiom of the problem,
> I will not return to the previous example, which was set by
> my by random distances, which I chose. The solution of your
> problem is as follows:
>
> x = [0,0,4,4];
> y = [0,6,6,0];
> xy = [x;y];
> dij = [0.0848,0.99098,0.5937];
>
> del = @(d) sqrt(d'*d);
> res = @(z) [del(xy(:,1)-z) - del(xy(:,2)-z) - dij(1)
> del(xy(:,1)-z) - del(xy(:,3)-z) - dij(2)
> del(xy(:,1)-z) - del(xy(:,4)-z) - dij(3)];
>
> [XY,ssq,cnt] = LMFnlsq(res,[2;3],'display',1)
>
> >> test080820
>
***************************************************************************
> itr nfJ SUM(r^2) x dx l
> lc
>
***************************************************************************
> 0 1 1.3417e+000 2.0000e+000 0.0000e+000
>
> 0.0000e+000 1.0000e+000
> 3.0000e+000 0.0000e+000
> 1 2 2.6097e-002 2.6290e+000 -6.2904e-001
> 0.0000e+000 1.0000e+000
> 3.1136e+000 -1.1355e-001
> 2 3 2.4987e-002 2.6390e+000 -9.9365e-003
> 0.0000e+000 1.0000e+000
> 3.1240e+000 -1.0411e-002
> 3 4 2.4987e-002 2.6392e+000 -1.9470e-004
> 0.0000e+000 1.0000e+000
> 3.1240e+000 -3.6993e-005
>
> 4 5 2.4987e-002 2.6392e+000 6.9462e-007
> 0.0000e+000 1.0000e+000
> 3.1240e+000 -1.9698e-006
> XY =
> 2.6392
> 3.1240
> ssq =
> 0.0250
> cnt =
> 4
>
> * xy are coordinates of microphones,
> * dij are your calculated differences,
> * del is the handle of anonymous function for calculation of
> yours sqrt((x1-x)^2 + ....),
> * res is the handle to anonymous function that declares
> residuals (errors of your equations)
> * XY are coordinates of the sound source,
> * ssq is a sum of squares of residuals,
> * cnt number of calls to res and Jacobian matrix.
>
> You see that ssq is only by approx. 10^2 lower then for the
> initial guess. It means that yours delijs are inexact.
> Better way would be in taking times of wave approach to
> microphones. More over having reading from 4 microphones
> could set 6 equations -> residuals and by least squares get
> much more accurate coordinates of the source.
>
> I think, that it is all what to say to it.
> Hope it helps.
>
> Mira
>
> PS: The time shift makes the communication difficult. Now is
> almost 23 o'clock at Pilsen (CZ).
>
>
Hi Mira,

You are right. there is something wrong with my time delays
because the point at which i captured the sound is (1,2) and
the ans = (2,3).
Secondly, as the formulas are :
del12=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x2-x)^2+(y2-y)^2)
del13=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x3-x)^2+(y3-y)^2)
del14=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x4-x)^2+(y4-y)^2)

instead of this complicated method, can i make use of least
square method using matrices and the least square formula to
calculate the location:
x= ((A(transpose)*A)^- 1 )A(transpose) * B

http://www.ee.oulu.fi/~mpa/matreng/ematr5_5.htm
http://www.ee.oulu.fi/~mpa/matreng/eem5_5-1.htm

If yes, then please do let me how do i arrange the elements
in the matrices (It is difficult for me to crack because of
the unknown x and the square root).

Thank you.

- Mazahir

Solving equations

Mazahir — Mon, 18 Aug 2008 13:47:01 -0400

Hello,

I am finding out the location of a sound source using
microphones. The co-ordinates of the 3 mics are fixed.
Suppose the co-ordinates of the 3 mics are (x1,y1),(x2,y2)
and (x3,y3) and the distance of source of sound from the 1st
mic to the 2nnd is - del12 and the source of sound from the
1st mic to the 3rd is del13. how do i find the location of
the source (x,y) in MATLAB using the following formula.

del12=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x2-x)^2+(y2-y)^2)
del13=sqrt((x1-x)^2+(y1-y)^2)- sqrt((x3-x)^2+(y3-y)^2)

Solving this equation of 2 unknowns simultaneously will give
me the point (x,y). But i do not know how to do it in
matlab. I think there is a solution using matrices. Please
help. thank you.

Re: Solving equations

Miguel Torres — Mon, 13 Jul 2009 14:36:03 -0400

In order to solve your equations you need to solve it by the non-linear least-square methodology. In the link below you can find a brief mathematical description which will help you to solve your problem.

http://www.ndt.net/article/ewgae2004/pdf/l58schubert.pdf

Anyhow, you can solve this problem as well with the code provided by Prof. Balda (LMFnlsq function).

Best regards,

Miguel Angel

Re: Solving equations

John D'Errico — Tue, 14 Jul 2009 02:06:02 -0400

"Miguel Torres" <gugugifo@yahoo.com> wrote in message <h3fgoj$jtq$1@fred.mathworks.com>...
> In order to solve your equations you need to solve it by the non-linear least-square methodology. In the link below you can find a brief mathematical description which will help you to solve your problem.
>
> http://www.ndt.net/article/ewgae2004/pdf/l58schubert.pdf
>
> Anyhow, you can solve this problem as well with the code provided by Prof. Balda (LMFnlsq function).
>
>
> Best regards,
>
> Miguel Angel

NO. You do not need nonlinear least squares to solve
this.

While it looks like a nonlinear problem because of the
sqrt, or square terms, it turns out this is not necessary
at all.

There are three circles of known radii, all must have
the same (unknown) center. Call that center (x0,y0).

  (x0 - x1)^2 + (y0 - y1)^2 = r1^2
  (x0 - x2)^2 + (y0 - y2)^2 = r2^2
  (x0 - x3)^2 + (y0 - y3)^2 = r3^2

The only unknowns are x0 and y0. Expand and subtract.

  2*(x2 - x1)*x0 + 2*(y2 - y1)*y0 = r2^2 - r1^2 + x1^2 - x2^2
  2*(x3 - x1)*x0 + 2*(y3 - y1)*y0 = r3^2 - r1^2 + x1^2 - x3^2

You are left with two LINEAR equations in the two
unknowns. Solve. If you have noise in the data, one
option that I recall seems to help is to make it a
least squares problem. Generate the 3x2 linear system:

  2*(x2 - x1)*x0 + 2*(y2 - y1)*y0 = r2^2 - r1^2 + x1^2 - x2^2
  2*(x3 - x1)*x0 + 2*(y3 - y1)*y0 = r3^2 - r1^2 + x1^2 - x3^2
  2*(x3 - x2)*x0 + 2*(y3 - y2)*y0 = r3^2 - r2^2 + x2^2 - x3^2

Again, solve using backslash.

John