19
$\begingroup$

An absolute value expression such as $|ax-b|$ can be rewritten in two cases as $|ax-b|=\begin{cases} ax-b & \text{ if } x\ge \frac{b}{a} \\ b-ax & \text{ if } x< \frac{b}{a} \end{cases}$, so an equation with $n$ separate absolute value expressions can be split up into $2^n$ cases, but is there a better way?

For example, with $|2x-5|+|x-1|+|4x+3|=13$, is there a better way to handle all the possible combinations of $x\ge\frac{5}{2}$ versus $x<\frac{5}{2}$, $x\ge 1$ versus $x< 1$, and $x\ge-\frac{3}{4}$ versus $x<-\frac{3}{4}$?

  • 0
    @J. Mangaldan: The plot is also a good way to verify the answers. There are something like 24 signed-number operations involved in my algebraic solution below, so even with 99% accuracy per operation, that's only a 78.6% chance of correct calculations throughout.2010-08-23

2 Answers 2

25

For an equation with $n$ absolute values, the $n$ places where each absolute value splits into 2 cases divide the number line into $n+1$ regions where, within each region, each absolute value can be replaced by either the expression inside the absolute value or its opposite. Each resulting equation can then be solved, restricting solutions to the corresponding region on the number line.

In the given example,

$\small{\begin{matrix} \leftarrow & -\frac{3}{4} & \text{---} & 1 & \text{---} & \frac{5}{2} & \rightarrow \\ \begin{matrix}-(2x-5)-(x-1)\\-(4x+3)=13\end{matrix} & \begin{matrix}|\\|\end{matrix} & \begin{matrix}-(2x-5)-(x-1)\\+(4x+3)=13\end{matrix} & \begin{matrix}|\\|\end{matrix} & \begin{matrix}-(2x-5)+(x-1)\\+(4x+3)=13\end{matrix} & \begin{matrix}|\\|\end{matrix} & \begin{matrix}(2x-5)+(x-1)\\+(4x+3)=13\end{matrix} \\ -7x+3=13 & | & x+9=13 & | & 3x+7=13 & | & 7x-3=13 \\ x=-\frac{10}{7} & | & x=4\notin[-\frac{3}{4},1] & | & x=2 & | & x=\frac{16}{7}\notin[\frac{5}{2},\infty) \end{matrix}}$

So, the solutions are $x=-\frac{10}{7}$ and $x=2$ (the values that were solutions to an equation for a particular region and were within that region).

  • 0
    See my answer: what you propose is a special case of the CAD algorithm.2010-08-24
9

This is merely a very special case of the powerful CAD (cylindrical algebraic decomposition) algorithm for quantifier elimination in real-closed fields, e.g. see Jirstrand's paper [1] for a nice introduction.

[1] M. Jirstrand. Cylindrical algebraic decomposition - an introduction. 1995
Technical report S-58183, Automatic Control group, Department of Electrical Engineering
Linkoping University, Linkoping, Sweden.
Freely available here or here.

  • 1
    When you put it that way, then I certainly agree.2010-08-24