Ellipsoidal outer-bounding under model uncertainty is a natural extension of state estimation for models with unknown-but-bounded errors. The technique described in this paper applies to linear discrete-time dynamic systems. Many difficulties arise because of the non-convexity of feasible sets. Analytical optimal or suboptimal solutions are presented, which are counterparts in this context of uncertainty to classical approximations of the sum and intersection of ellipsoids.