Software error compensation is becoming an increasingly important aspect of numerically controlled machine tools. Currently, the error models are identified using the least-squares criterion. This criterion does not necessarily reflect the evaluation criteria of a machine's performance. In this paper, we develop a method for identifying the error model of a machine tool using a Chebyshev norm. The model parameter identification procedure becomes a linear program, and the resulting error models minimize the maximum error of the machine across its workspace thus affording strict bounds on the errors produced by the machine.