We now consider methods of preconditioning which al low a preconditionedequation
solved exactly in part or in whole. One type of method involves preconditioning
a vector so
that it is SD. See the methods in Sections 6 and 7. Another type eliminates the
which are not SD so that the problem can be partially solved. The latter type
regarded as preconditioning so that certain quantities are zeroed. It involves
an interval matrix, so it is perhaps misleading to call it preconditioning. See
in Sections 8 and 9.
Then the interval vector y = x + q is the nearest SD interval vector to x in
Assume x is not SD. However, assume that at least one component of x is strictly
"strictly SD", we mean that the the interval is SD and neither endpoint is zero.
having an endpoint which is zero is SD , but not strictly SD. Let j be the index
is the component of largest mignitude. The mignitude of
Define the vector v(j) with components
and define the matrix
Then is SD.
Therefore, is known exactly when
has been determined.
In what follows, we do not actually use the interval vector (such as x) which we
condition so as to be SD. Instead, we use an unspecified real vector
However, if we
precondition so that the interval vector x is SD, then the sign of any component
has the sign we impose on the corresponding component of x.
Suppose we precondition a matrix A by multiplying by a real matrix
can be irregular even when A is regular and
is nonsingular. The four
we describe below all use some kind of preconditioning and in two cases
interval matrix. In each method, we assume that
is such that M is regular.
A virtue of the preconditioning method just described is that the
differs from the identity in only one row. Contrast this with preconditioning
using the inverse
of the center of A: See Section 1.
in (5.2) will be used as a preconditioner. The smaller the norm of the
vector v(j) used to define
, the closer
is to the identity. The enlargement of the solution set by preconditioning is less when
is nearer the identity.. If more than one
component of x is strictly SD, it is some times possible to define a matrix
which is nearer the identity. We omit the details.
6. Third method
Our third method is obtained by introducing preconditioning into our first
we have obtained crude bounds xB on the solution to Ax = b and find that at
component of xB is SD. Then the corresponding component of the hull h is SD.
we can de termine a matrix V as in Section 5 such that V xB is SD. This assures
that V h is
Define y = V x and . Then the solution y of My = b is SD and its hull
be found using the first method (in Section 3). We then obtain x as
Presumably any kind of preconditioning can enlarge the solution set. It is
compare the method using this kind of preconditioning with a method in Section 1
get the crude bounds xB. The latter method requires considerably less computing.
To get xB, we can precondition by multiplying by an approximate inverse of the
of A. The closer
is to the identity, the less the preconditioning step
tends to enlarge
the solution set. The closer xB is to being SD, the less the method just
the solution set. (A measure of how far xB is from SD is the norm of the vector
Section 5.) The amount to which preconditioning enlarges the solution set
depends on how
far the preconditioner is from the identity matrix. Therefore, the comparative
of results when preconditioning by or by
depends strongly on the nature of the
problem. A similar statement holds for the methods discussed below.
7. Fourth method
In the third method, we introduced a preconditioning procedure which produced an
whose solution was SD. Therefore, we could apply the first method. In the same
can precondition so that the new equation can be solved by the second method (in
4). That is, the preconditioning is such that a row of the inverse of the
generated matrix is
The exact inverse P of A will usually be regular when A is regular. Assume it
assume that the bound PB (obtained as in Section 4) on P is regular.
Then for any i =
1,...:, n, at least one component of the ith row
of PB must
be SD. From Section 5,
we can determine a matrix V such that
V is SD. This implies
that is SD.
Assume that we have determined V such that row i of PV is SD. To precondition
Ax = b, we multiply by the matrix
: (Note that
is exactly known from
V is known.) The new coefficient matrix is
. Row i of the inverse
of M is SD.
We can compute the ith component of the hull of
using the second method
(see Section 4).
It is not necessary to verify that row i of the inverse of M is SD. If it were
not be SD, it would still be correct to proceed as if it were.
Note that the result will generally not be a sharp bound on the corresponding
component of the hull since preconditioning by
tends to enlarge the
There are two other reasons why a solution obtained by this method can fail to
First, the computed bounds on the inverse will generally not be sharp. The
matrix V is determined so that a row of the bound PB is SD. Since PB
is not a sharp bound
on P, the matrix V generally causes an "overshoot" when changing a non -SD
SD. Therefore, preconditioning A by causes too large a change in A.
The other cause of loss of sharpness is more subtle. It occurs because P
which are not inverses of matrices in A. The loss of sharpness is similar in
nature to that
8. Fifth method
Assume that one or more component of the crude bound xB is SD. Then
component(s) of the hull h are SD. For simplicity, assume that for some integer
k, we have
for i = 1, ..., k and
is SD for i = k+1,
..., n: Partition A, x, and b conformally
so that the equation Ax = b takes the form
Here xT = (yT , zT ) where y has k components
and z has n - k components: The hull of
the solution set of this system is such that the interval solution z is SD.
Perform interval Gaussian elimination, but stop when
is zeroed The result is
equation of the form
This equation can be written as the system
Since z is SD, we can compute z sharply from the equation
using the first
method (in Section 3). We can then compute bounds on y by backsolving
When we perform the interval Gaussian elimination to obtain (8.2) from (8.1),
widths will tend to grow, and we should precondition. Suppose we precondition by
tiplying Ax = b by an approximate inverse of the center of A. Then there is no
using the method just described because we can determine the hull of such a
system sharply using the hull method. See .
Instead, we should precondition by an approximate inverse of the center of
where I denotes an identity matrix of order n -k. This tends to enlarge the
solution set by
less than preconditioning by an approximate inverse of the center of the entire
9. Sixth method
We now consider a method which can be regarded as a kind of dual of the fifth
Suppose we compute crude bounds on the inverse P of A as described in Sections 1
4. To simplify discussion we fix our attention on the first row of P. We also
assuming that is SD for j = 1, ..., k and
that for j = k + 1,..., n:
Partition A as
where is k by k and
is n-k by n-k: We can perform Gaussian
elimination on A in
such a way that becomes zero. This is
achieved by multiplying by a matrix of the form
This matrix need not be explicitly generated. However, the operations to obtain
also be performed on b so that the new equation is BAx = Bb.
The first row of the inverse PB-1 of BA is such that its first k
components are the
same as those of P and, by assumption, are SD. The last n - k components of the
row of PB-1 are zero (and hence SD). Since the first row of the
inverse of BA is SD, we
can determine the first component of the solution of BAx = Bb by the second
Other components of x can be bounded in a similar way.
Start solving your Algebra Problems
in next 5 minutes!
Download (and optional CD)
Click to Buy Now:
2Checkout.com is an authorized reseller
of goods provided by Sofmath
Attention: We are
currently running a special promotional offer
for Algebra-Answer.com visitors -- if you order
Algebra Helper by midnight of
you will pay only $39.99
instead of our regular price of $74.99 -- this is $35 in
savings ! In order to take advantage of this
offer, you need to order by clicking on one of
the buttons on the left, not through our regular
If you order now you will also receive 30 minute live session from tutor.com for a 1$!
You Will Learn Algebra Better - Guaranteed!
Just take a look how incredibly simple Algebra Helper is:
: Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:
Step 2 :
Let Algebra Helper solve it:
Step 3 : Ask for an explanation for the steps you don't understand:
Algebra Helper can solve problems in all the following areas:
simplification of algebraic expressions (operations
with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots
(radicals), absolute values)