  We present a certified version of the Natural-Norm Successive Constraint
Method (cNNSCM) for fast and accurate Inf-Sup lower bound evaluation of
parametric operators. Successive Constraint Methods (SCM) are essential tools
for the construction of a lower bound for the inf-sup stability constants which
are required in {\it a posteriori} error analysis of reduced basis
approximations. They utilize a Linear Program (LP) relaxation scheme
incorporating continuity and stability constraints. The natural-norm approach
{\em linearizes} inf-sup constant as a function of the parameter. The
Natural-Norm Successive Constraint Method (NNSCM) combines these two aspects.
It uses a greedy algorithm to select SCM control points which adaptively
construct an optimal decomposition of the parameter domain, and then apply the
SCM on each domain.
  Unfortunately, the NNSCM produces no guarantee for the quality of the lower
bound. The new cNNSCM provides an upper bound in addition to the lower bound
and let the user control the gap, thus the quality of the lower bound. The
efficacy and accuracy of the new method is validated by numerical experiments.
