Further Details: Error Bounds for Linear Equality Constrained Least Squares Problems

In this subsection, we will summarize the available error bound. The reader may also refer to [2,13,18,50] for further details.

Let $\widehat {x}$ be the solution computed by the driver xGGLSE (see subsection 4.6). It is normwise stable in a mixed forward/backward sense [18,13]. Specifically, $\widehat {x} = \bar {x} + \Delta \bar {x}$, where $\bar {x}$ solves $\min\{\Vert b + \Delta b - (A + \Delta A)x \Vert _2: \; (B + \Delta B)x = d \}$, and

$\parbox{2in}{ \begin{eqnarray*} \Vert \Delta \bar {x} \Vert _2 & \... ... \Delta A \Vert _F & \leq & q(m,n,p)\epsilon\Vert A\Vert _F, \end{eqnarray*} }$     $\parbox{2in}{ \begin{eqnarray*} \Vert \Delta b \Vert _2 & \leq & q... ...t \Delta B \Vert _F & \leq & q(m,n,p)\epsilon\Vert B\Vert _F, \end{eqnarray*}}$

q(m,n,p) is a modestly growing function of m, n, and p. We take q(m,n,p) = 1 in the code fragment above. Let $X^{\dagger}$ denote the Moore-Penrose pseudo-inverse of X. Let $\kappa_B(A) = \Vert A \Vert _F \Vert (AP)^\dagger \Vert _2$( = CNDAB above) and $\kappa_A(B) = \Vert B \Vert _F \Vert B^\dagger_A \Vert _2$( = CNDBA above) where $P = I - B^\dagger B$ and $B^\dagger_A = (I - (AP)^\dagger A)B^\dagger$. When $q(m,n,p)\epsilon$ is small, the error $x-\hat{x}$ is bounded by

$$% latex2html id marker 15239\frac{ \Vert x-\hat{x} \Vert ... ...rt r \Vert _2 }{ \Vert A \Vert _F \Vert x \Vert _2 } \right\}.$$

When B = 0 and d = 0, we essentially recover error bounds for the linear least squares (LS) problem:

$$\frac{ \Vert x-\widehat {x} \Vert _2 }{ \Vert x \Vert _2 } ... ...rt _2 }{ \Vert A \Vert _F \Vert x \Vert _2 } \right) \right\},$$

where $\kappa(A) = \Vert A \Vert _F \Vert A^\dagger \Vert _2$. Note that the error in the standard least squares problem provided in section 4.5.1 is

$$% latex2html id marker 13969\frac{ \Vert x-\widehat {x} \... ...^2(A)\frac{ \Vert r \Vert _2 }{ \Vert Ax \Vert _2 }\right\}\\$$

since $\sin(\theta) = \frac{ \Vert A\widehat {x}-b \Vert _2 }{ \Vert b \Vert _2 }$. If one assumes that q(m,n) = p(n) = 1, then the bounds are essentially the same.