Ngô Quốc Anh

June 7, 2009

Perturbation in linear systems

In this small topic, I will show several traditional results regarding to the perturbation in matrix algebra. This comes from the study of the stability of solving system of linear equations in Numerical Analysis.

Let us consider the following matrix-form linear system Ax=b. We split into three cases

  • Perturbation on b

If \delta b is a small perturbation on b, then \delta x is a small perturbation on x in the sense that the following system A(x + \delta x) = b + \delta b holds true. This together with the fact that Ax =b gives A \delta x = \delta b. By some simple calculation, one has

\displaystyle\begin{gathered}\frac{{\left\| {\delta x} \right\|}}{{\left\| x \right\|}} = \frac{{\left\| {{A^{ - 1}}\left( {\delta b} \right)} \right\|}}{{\left\| x \right\|}}\leq\frac{{\left\| {{A^{ - 1}}} \right\|\left\| {\delta b} \right\|}}{{\left\| x \right\|}} \hfill \\ \qquad= \frac{{\left\| {{A^{ - 1}}} \right\|\left\| A \right\|\left\| {\delta b} \right\|}}{{\left\| A \right\|\left\| x \right\|}}\leq\frac{{\left\| {{A^{ - 1}}} \right\|\left\| A \right\|\left\| {\delta b} \right\|}}{{\left\| {Ax} \right\|}} \hfill \\ \qquad= \frac{{\left\| {{A^{ - 1}}} \right\|\left\| A \right\|\left\| {\delta b} \right\|}}{{\left\| b \right\|}}. \hfill \\ \end{gathered}

Thus

\displaystyle\frac{{\left\| {\delta x} \right\|}}{{\left\| x \right\|}}\leq\left\| {{A^{ - 1}}} \right\|\left\| A \right\|\frac{{\left\| {\delta b} \right\|}}{{\left\| b \right\|}}.

  • Perturbation on A.

If \delta A is a small perturbation on A, then \delta x is a small perturbation on x in the sense that the following system (A + \delta A)(x+\delta x) = b holds true. This together with the fact that Ax =b gives \left( {\delta A} \right)x + A\left( {\delta x} \right) + \left( {\delta A} \right)\left( {\delta x} \right) = 0. By some simple calculation, one has

\displaystyle\begin{gathered}\left\| {\delta x} \right\| = \left\| {{A^{ - 1}}\left( {\left( {\delta A} \right)\left( x \right) + \left( {\delta A} \right)\left( {\delta x} \right)} \right)} \right\| \hfill \\ \qquad\leq\left\| {{A^{ - 1}}} \right\|\left\| {\left( {\delta A} \right)\left( x \right) + \left( {\delta A} \right)\left( {\delta x} \right)} \right\| \hfill \\ \qquad\leq \left\| {{A^{ - 1}}} \right\|\left( {\left\| {\delta A} \right\|\left\| x \right\| + \left\| {\delta A} \right\|\left\| {\delta x} \right\|} \right). \hfill \\ \end{gathered}

Thus

\displaystyle\left\| {\delta x} \right\|\left( {1 - \left\| {{A^{ - 1}}} \right\|\left\| {\delta A} \right\|} \right) \leqslant \left\| {{A^{ - 1}}} \right\|\left\| {\delta A} \right\|\left\| x \right\|

which implies that

\displaystyle\frac{{\left\| {\delta x} \right\|}}{{\left\| x \right\|}} \leqslant \frac{{\left\| {{A^{ - 1}}} \right\|\left\| {\delta A} \right\|}}{{1 - \left\| {{A^{ - 1}}} \right\|\left\| {\delta A} \right\|}} = \frac{{\left\| A \right\|\left\| {{A^{ - 1}}} \right\|\frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}}}{{1 - \left\| A \right\|\left\| {{A^{ - 1}}} \right\|\frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}}}.

  • Perturbation on A and b.

If \delta A is a small perturbation on A and \delta b is a small perturbation on b, then \delta x is a small perturbation on x in the sense that the following system (A + \delta A)(x+\delta x) = b + \delta b holds true. This together with the fact that Ax =b gives A\left( {\delta x} \right) + \left( {\delta A} \right)x + \left( {\delta A} \right)\left( {\delta x} \right) = \delta b. By some simple calculation, one has

\displaystyle\begin{gathered}\left\| {\delta x} \right\| = \left\| {{A^{ - 1}}\left( {\delta b - \left( {\delta A} \right)\left( x \right) - \left( {\delta A} \right)\left( {\delta x} \right)} \right)} \right\| \hfill \\ \qquad\leqslant \left\| {{A^{ - 1}}} \right\|\left\| {\delta b - \left( {\delta A} \right)\left( x \right) - \left( {\delta A} \right)\left( {\delta x} \right)} \right\| \hfill \\ \qquad\leqslant \left\| {{A^{ - 1}}} \right\|\left( {\left\| {\delta b} \right\| + \left\| {\delta A} \right\|\left\| x \right\| + \left\| {\delta A} \right\|\left\| {\delta x} \right\|} \right) \hfill \\ \end{gathered}

which implies that

\displaystyle\left\|{\delta x}\right\|\left({1-\left\|{{A^{-1}}}\right\|\left\|{\delta A}\right\|}\right)\leqslant\left\|{{A^{-1}}}\right\|\left({\left\|{\delta b}\right\|+\left\|{\delta A}\right\|\left\| x\right\|}\right).

Thus,

\displaystyle\begin{gathered}\frac{{\left\| {\delta x} \right\|}}{{\left\| x \right\|}} \leqslant \frac{{\left\| {{A^{ - 1}}} \right\|\left( {\frac{{\left\| {\delta b} \right\|}}{{\left\| x \right\|}} + \left\| {\delta A} \right\|} \right)}}{{1 - \left\| {{A^{ - 1}}} \right\|\left\| {\delta A} \right\|}} \hfill \\ \qquad= \frac{{\left\| A \right\|\left\| {{A^{ - 1}}} \right\|\left( {\frac{{\left\| {\delta b} \right\|}}{{\left\| A \right\|\left\| x \right\|}} + \frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}} \right)}}{{1 - \left\| A \right\|\left\| {{A^{ - 1}}} \right\|\frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}}} \hfill \\ \qquad\leqslant \frac{{\left\| A \right\|\left\| {{A^{ - 1}}} \right\|\left( {\frac{{\left\| {\delta b} \right\|}}{{\left\| {Ax} \right\|}} + \frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}} \right)}}{{1 - \left\| A \right\|\left\| {{A^{ - 1}}} \right\|\frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}}} \hfill \\ \qquad\leqslant \frac{{\left\| A \right\|\left\| {{A^{ - 1}}} \right\|\left( {\frac{{\left\| {\delta b} \right\|}}{{\left\| b \right\|}} + \frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}} \right)}}{{1 - \left\| A \right\|\left\| {{A^{ - 1}}} \right\|\frac{{\left\| {\delta A} \right\|}}{{\left\| A \right\|}}}}. \hfill \\ \end{gathered}

In the literature, the expression \|A^{-1}\|\|A\| is called the condition number of the matrix A, denoted by K(A). It is easy to see that K(A) \geq 1. If K(A) is small then the system Ax=b is called to be well-posed. Alternatively, in the case when 1 \ll K(A), the system Ax=b is ill-posed.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: