3

Let $P_{i} = (x_i,y_i,z_i)$ n points in $\mathbb{R}^3$. Show that the point $P=(x,y,z)$ that minimize the sum of the squares of the distances to the points $P_i$ is the gravity center $( x = \frac{1}{n} \sum x_{i}, y = \frac{1}{n} \sum y_{i}, z = \frac{1}{n} \sum z_{i})$

Here's my "attempt":

I need to find the point that minimize the following:

$ \sum\limits _{i=1}^{n} d²(P,P_{i}) = d²(P,P_1) + ... + d²(P,P_n) $

Every term above is positive, but I can't simply choose every one as zero, since then I'll get that every point is the same. I can't also use propery of norms, since I have the square here... Graphically I'm convinced that the "spatial mid point" of all of them will be the minimizator, but how can I mathematicaly prove it?

I also tried to differentiate the function using multivalued analysis, but I failed calculating the derivative. Should I use chain rule?

Can someone please give me a hint? Thanks.

2 Answers2

1

Recall that $$ f_i(x,y,z) := d(P, P_i)^2 = (x-x_i)^2 + (y-y_i)^2 + (z-z_i)^2 $$ Hence, the partial derivatives are \begin{align*} \partial_x f_i(x,y,z) &= 2(x-x_i) \\ \partial_y f_i(x,y,z) &= 2(y-y_i) \\ \partial_z f_i(x,y,z) &= 2(z-z_i) \end{align*} Hence, the derivatives of $f := \sum_{i=1}^n f_i$, the function we want to minimize, are \begin{align*} \partial_x f(x,y,z) &= 2nx-2\sum_{i=1}^n x_i \\ \partial_y f(x,y,z) &= 2ny-2\sum_{i=1}^n y_i \\ \partial_z f(x,y,z) &= 2nz-2\sum_{i=1}^n z_i \\ \end{align*} Hence, $\partial_i f(x,y,z) = 0$ for $i \in \{x,y,z\}$ holds iff $$ x = \frac 1n \sum_i x_i, \quad y = \frac 1n \sum_i y_i, \quad z = \frac 1n \sum_i z_i. $$ As $|f| \to \infty$ for $|(x,y,z)|\to\infty$, this unique critical point is a global minimum. This was to be proved.

martini
  • 84,101
  • Thanks! But the last line is kind of weird to me, even though I understood what you did. What is the standard procedure for verifying the type of extremal points when dealing with multivalued functions? –  Mar 18 '16 at 20:54
  • 1
    The standard procedure is first to determine the critical points, that is the points where $Df(x,y,z) = 0$. Then (as in one dimension), one has to argue whether the critical point is a minimum/maximum/no extremum. – martini Mar 18 '16 at 20:56
  • My question was specificaly about that last part. While in one variable I could just see if $f''(x)>0$ for a maximum point, what is the standard method for a multivalued function? Can I affirm that $\det Hess(f(x)) > 0$ imply $x$ is minimum? –  Mar 18 '16 at 21:13
  • 1
    No, thats not sufficient. If you want to have a look at the second derivative (which is not necessary here, due to the shape of the function), you have to show, that $D^2f(x)$, the Hessian, is positive definite. – martini Mar 18 '16 at 21:14
0

First compute the partial derivatives of $d^2(P,P_i)=(x-x_i)^2+(y-y_i)^2+(z-z_i)^2$. You get:

$$ \partial_x d^2(P,P_i)=2(x-x_i)\\ \partial_y d^2(P,P_i)=2(y-y_i)\\ \partial_z d^2(P,P_i)=2(z-z_i) $$

From this you get

$$\partial_x\left( \sum\limits _{i=1}^{n} d²(P,P_{i}) \right)=2 \sum\limits_{i=1}^{n} (x-x_i)=2\left(nx-\sum\limits_{i=1}^{n} x_i\right) $$

Notice that this is zero when $x=\frac{1}{n} \sum x_{i}$. Proceed similiar for $\partial_y$ and $\partial_z$. Then you have to verify that this is indeed a minimium.

Maik Pickl
  • 2,037