-1
$\begingroup$

I am having a set of equations of the form $\begin{align} (x - a_1)^2 + (y - b_1)^2 + (z - c_1)^2 &= W_1\\ (x - a_2)^2 + (y - b_2)^2 + (z - c_2)^2 &= W_2\\ & \vdots \\ (x - a_m)^2 + (y - b_m)^2 + (z - c_m)^2 &= W_m. \end{align}$ Here $a_1,\ldots ,a_m, b_1,\ldots, b_m, c_1,\ldots, c_m$ and $W_1,\ldots, W_m$ are known constants and $m$ can be any number greater than $3$. Hence this is like overdetermined set of quadratic equations in three unknowns $x$, $y$ and $z$.

How can we solve these equations?

  • 1
    If you subtract any two equations you get a linear equation in x,y, and z. With more than three equations this is just inear algebra, solve and check to see that your answer works. With just 3 forlve for x and y and substitute to get a quadratic is z2011-08-03

2 Answers 2

0

If your equations are consistent, the approach of deinst will work. If not, which seems likely given your nonlinear-optimization tag, you have a three dimensional minimization problem. You can create a function of $x,y,z$ which is the sum of the squared errors of all the equations and feed it to your favorite minimizer. Calculating the gradient is pretty easy, so you might want to use one of those methods, but this feels like it might have many minima. Any numerical analysis book will have information, one of my favorites is chapter 10 of Numerical Recipes. The obsolete versions are free.

  • 0
    Yes, you are correct. Generally speaking, they may not have overlapping region as well. Thanks for the help.2011-08-05
3

Looks to me like you have a bunch of 3-D points and you want to fit a sphere to them.

The equation of a sphere is $r^2 = (x-a)^2 + (y-b)^2 + (z-c)^2$. This seems to be nonlinear in its parameters (r, a, b, c).

However if we write it as $r^2 = (x-a)^2 + (y-b)^2 + (z-c)^2 = x^2+y^2+z^2+2\ a\ x+2\ b\ y+2\ c\ z + a^2+b^2+c^2,$ and let $v = a^2+b^2+c^2-r^2$, the equation becomes $0 = x^2+y^2+z^2+2\ a\ x+2\ b\ y+2\ c\ z +v$ which is linear in its parameters (a, b, c, v). Put this into a linear least squares solver, and then get $r$ from $a, b, c,$ and $v$.

This works for any number of dimensions. I used it about 25 years ago to fit circles to data points, and it worked quite well.

I know that this does not do a least squares fit of the sphere to points (which is nonlinear), but it works well and can generate good starting parameters for an exact nonlinear fitting process.

A suggestion I have found useful in practice: If you have many points and they are far from the origin, shift the origin so it is at the center of the points. Otherwise the computation of $r$ from $a$, $b$, $c$, and $v$ can be inaccurate.

  • 0
    Oops - my answer may not be to OP's question. However, I like my result anyway, so I will leave it in:)2011-08-08