logo

Segmentation 📂Analysis

Segmentation

This post is based on the Riemann-Stieltjes integral. If we set as $\alpha=\alpha (x)=x$, it is the same as the Riemann integral.

Definition

  • If $P^{\ast}$ and $P$ are partitions of $[a,b]$ and satisfy $P \subseteq P^{\ast}$, then $P^{\ast}$ is called a refinement of $P$. Hence, every point in $P$ is a point in $P^{\ast}$.

  • For any two partitions $P_{1}$ and $P_{2}$, $P_{3}=P_{1} \cup P_{2}$ is called the common refinement of $P_{1}$ and $P_{2}$.


Recall how integrals were defined in high school by dividing a given graph into $n$ equal parts, and taking the limit as $n$ goes to infinity. This makes it easy to understand the role of refinements.

Theorem

Let’s say $P^{\ast}$ is a refinement of $P$. Then the following two equations hold:

$$ \begin{align} L(P,f,\alpha) &\le L(P^{\ast},f,\alpha) \label{eq1} \\ U(P^{\ast},f,\alpha) &\le U(P,f,\alpha) \label{eq2} \end{align} $$

Here, $L$ and $U$ are, respectively, the Riemann(-Stieltjes) upper and lower sums.


In other words, as the partition is refined, the lower sum increases and the upper sum decreases.

Proof

Before proving, let’s state the following:


Let’s say $P^{\ast}$ is a refinement of $P$ with just one more point and call this point $x^{\ast}$. Suppose for some $i=1,\cdots ,n$, we have $x_{i-1} < x^{\ast} < x_{i}$.

$\eqref{eq1}$

The Riemann(-Stieltjes) lower sum for $P$ is as follows:

$$ \begin{align*} L(P,f,\alpha) &= \sum \limits _{i=1} ^n m_{i} \Delta \alpha_{i} \\ &= m_{1}\Delta \alpha_{1} + \cdots + m_{i} \left[ \alpha (x_{i}) - \alpha (x_{i-1}) \right] + \cdots + m_{n}\Delta \alpha_{n} \\ &= m_{1}\Delta \alpha_{1} + \cdots + m_{i} \left[ \alpha (x_{i}) -\alpha (x^{\ast}) \right] + m_{i} \left[ \alpha (x^{\ast})- \alpha (x_{i-1}) \right] + \cdots + m_{n}\Delta \alpha_{n} \end{align*} $$

And let’s set the following:

$$ \begin{align*} w_{1} &= \inf f(x) &(x_{i-1} \le x \le x^{\ast}) \\ w_2&= \inf f(x) &(x^{\ast} \le x \le x_{i}) \end{align*} $$

Then, since $m_{i}=\inf f(x)\ \ (x_{i-1} \le x \le x_{i})$, the following holds:

$$ m_{i} \le w_{1} \quad \text{and} \quad m_{i} \le w_2 $$

Therefore, we obtain the following:

$$ \begin{align*} m_{i} \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] + m_{i}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] &\le w_2 \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] + w_{1}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] \\ &= w_{1}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] + w_2 \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] \end{align*} $$

Thus, the following holds:

$$ \begin{align*} L(P,f,\alpha) &= m_{1}\Delta \alpha_{1} + \cdots + m_{i} \left[ \alpha (x_{i}) -\alpha (x^{\ast}) \right] + m_{i} \left[ \alpha (x^{\ast})- \alpha (x_{i-1}) \right] + \cdots + m_{n}\Delta \alpha_{n} \\ &\le w_{1}\Delta \alpha_{1} + \cdots + w_{1}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] + w_2 \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] + \cdots + m_{n}\Delta \alpha_{n} \\ &= L(P^{\ast},f,\alpha) \end{align*} $$

$\eqref{eq2}$

The proof follows the same method as for $\eqref{eq1}$. The Riemann(-Stieltjes) upper sum for $P$ is as follows:

$$ \begin{align*} U(P,f,\alpha) &= \sum \limits _{i=1} ^n M_{i} \Delta \alpha_{i} \\ &= M_{1}\Delta \alpha_{1} + \cdots + M_{i} \left[ \alpha (x_{i}) - \alpha (x_{i-1}) \right] + \cdots + M_{n}\Delta \alpha_{n} \\ &= M_{1}\Delta \alpha_{1} + \cdots + M_{i} \left[ \alpha (x_{i}) -\alpha (x^{\ast}) \right] + M_{i} \left[ \alpha (x^{\ast})- \alpha (x_{i-1}) \right] + \cdots + M_{n}\Delta \alpha_{n} \end{align*} $$

And let’s set the following:

$$ \begin{align*} W_{1} &= \sup f(x)& (x_{i-1} \le x \le x^{\ast}) \\ W_2&= \sup f(x)&(x^{\ast} \le x \le x_{i}) \end{align*} $$ Then, since $M_{i}=\sup f(x)\ \ (x_{i-1} \le x \le x_{i})$, the following holds:

$$ W_{1} \le M_{i} \quad \text{and} \quad W_2 \le M_{i} $$

Therefore, we obtain the following:

$$ \begin{align*} M_{i} \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] + M_{i}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] & \ge W_2 \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] + W_{1}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] \\ &= W_{1}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] + W_2 \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] \end{align*} $$

Thus, the following holds:

$$ \begin{align*} U(P,f,\alpha) &= M_{1}\Delta \alpha_{1} + \cdots + M_{i} \left[ \alpha (x_{i}) -\alpha (x^{\ast}) \right] + M_{i} \left[ \alpha (x^{\ast})- \alpha (x_{i-1}) \right] + \cdots + M_{n}\Delta \alpha_{n} \\ &\ge W_{1}\Delta \alpha_{1} + \cdots + W_{1}\left[ \alpha (x^{\ast}) - \alpha (x_{i-1}) \right] + W_2 \left[ \alpha (x_{i}) - \alpha (x^{\ast}) \right] + \cdots + M_{n}\Delta \alpha_{n} \\ &= U(P^{\ast},f,\alpha) \end{align*} $$