Overdetermined set of quadratic equations

Question

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?

Answer 1

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.

Answer 2

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.