# Overdetermined set of quadratic equations

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?

• 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 z Commented Aug 3, 2011 at 12:17

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.

• Oops - my answer may not be to OP's question. However, I like my result anyway, so I will leave it in:) Commented Aug 8, 2011 at 22:58

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.

• I think your are right, i have three unknowns x, y and z and more than three equations. Geometrically it seems that these are spheres and in general would not intersect in a point. So I have to find a point that in the overlapping region that minimizes the error in least squares sense. I hope my analysis is correct. Any ideas? Commented Aug 5, 2011 at 15:18
• You are right that these are spheres and they need not intersect in a point-in fact will not if there are errors. There may even not be any region where all the spheres overlap. But given a trial point $(x,y,z)$ you can assess the error in each equation like $e_1=(x - a_1)^2 + (y - b_1)^2 + (z - c_1)^2 - W_1$ and so on. Then the total squared error is $f(x,y,z)=\sum e_i^2.$ This is what you would feed to the function minimizer. Commented Aug 5, 2011 at 15:24
• Yes, you are correct. Generally speaking, they may not have overlapping region as well. Thanks for the help. Commented Aug 5, 2011 at 15:30