  We introduce a new family of strong linearizations of matrix
polynomials---which we call "block Kronecker pencils"---and perform a backward
stability analysis of complete polynomial eigenproblems. These problems are
solved by applying any backward stable algorithm to a block Kronecker pencil,
such as the staircase algorithm for singular pencils or the QZ algorithm for
regular pencils. This stability analysis allows us to identify those block
Kronecker pencils that yield a computed complete eigenstructure which is
exactly that of a slightly perturbed matrix polynomial. The global backward
error analysis in this work presents for the first time the following key
properties: it is a rigurous analysis valid for finite perturbations (i.e., it
is not a first order analysis), it provides precise bounds, it is valid
simultaneously for a large class of linearizations, and it establishes a
framework that may be generalized to other classes of linearizations. These
features are related to the fact that block Kronecker pencils are a particular
case of the new family of "strong block minimal bases pencils", which are
robust under certain perturbations and, so, include certain perturbations of
block Kronecker pencils. We hope that this robustness property will allow us to
extend the results in this paper to other contexts.
