Solving Linear Equations

18.1 Introduction

This lecture is about solving linear equations of the form Ax = b, where A is a symmetric positive
semi-definite matrix. In fact, we will usually assume that A is diagonally dominant, and will
sometimes assume that it is in fact positive definite .

We will brie y describe the Chebyshev method for solving such systems, and the related Conjugate
Gradient. We will then explain how these methods can be accelerated by preconditioning. In
the next few lectures, we will see how material from the class can be applied to construct good
preconditioners.

18.2 Approximate Inverses

In undergraduate linear algebra classes , we are taught to solve a system like Ax = b by first
computing the inverse of A, call it C, and then setting x = Cb. However, this can take way too
long. In this lecture, we will see some ways of quickly computing approximate inverses of A, when A
is symmetric and positive semi-definite. By "quickly", we mean that we might not actually compute
the entries of the approximate inverse, but rather just provide a fast procedure for multiplying it
by a vector. I'll talk more about that part later, so let's first consider a reasonable notion of
approximate.

The fact that the inverse C satisfies AC = I is equivalent to saying that all eigenvalues of AC are
1. We will call C an -approximate inverse of A if all eigenvalues of AC lie in In
this case, all eigenvalues of I - AC lie in from which we can see that C can be used to
approximately solve linear systems in A. If we set x = Cb, then

In our construction, we will guarantee that AC is symmetric, and so and

18.3 Chebyshev Polynomials

We will exploit matrices C of the form

Note that one can quickly compute the product Cb : we will iteratiely compute Aib, and then take
the sum . So, if A has m non- zero entries , then this will take O(mt) steps. I should warn you that
I'm ignoring some numerical issues here.

Now, let's find a good choice of polynomials. Recall that we want

to have all its eigenvalues between . Let

Then, for each eigenvalue is an eigenvalue of I - AC. Assuming that A is positive
definite, its eigenvalues all lie between and where So, it suffices to find a
polynomial p with constant term 1 such that for all As in Lecture 8,
we will use Chebyshev polynomials to construct p. We recall that the k-th Chebyshev polynomial,
Tk, has the following properties

1. Tk has degree k.
2.
3. Tk(x) is monotonically increasing for x≥1.
4.

To express p(x) in terms of a Chebyshev polynomial, we should map the range on which we want
p to be small, to [-1, 1]. We will accomplish this with the linear map:

Note that

So, to guarantee that the constant coefficient in p(x) is zero, we should set

We know that To find p(x) for x in this range, we must compute
We will express the result of our computation in terms of the condition number of , which
for a symmetric matrix is

We have

and so by properties 3 and 4 of Chebyshev polynomials,

Thus,

for and so all eigenvalues of I-AC will have absolute value at most
So, to get accuracy in our solution to Ax = b, we need

18.4 Computational properties, and the Conjugate Gradient

The Chebyshev properties have some useful properties that I should mention, but which I will not
prove. The most useful property is that their coefficients have a clean recursive definition. As a
result, we can construct an algorithm, called the Chebyshev method, that just takes as input a
lower bound on and an upper bound on and, after t iterations produces the estimate
obtained from . In particular, the algorithm is iterative, and at each iteration obtain the correct
estimate.

The Chebyshev method is not used much in practice because there is a better method|the Conjugate
Gradient. The CG method adaptively computes the coefficients of the polynomial, and is
guaranteed to compute the optimal coefficients at each iteration. I will now dwell on how it works
now, but I will mention that it is quite efficient, and always at least as good as the Chebyshev
method.

18.5 Preconditioning

So, we know that we can obtain an approximate solution to a system of the form Ax = b in time
depending on But, what if is large? In this case, we can try to precondition A .
That means finding a matrix B that is similar to A, but for which it is easy to solve equations like
Bz = c. We then apply the Chebyshev method, or the Conjugate Gradient, to solve

The running time of the preconditioned method is effected in two ways :

1. At each iteration, in addition to multiplying a vector by A, we must solve a linear system
Bz = c, which we can think of as multiplying by B-1, and

2. The number of iterations now depends the eigenvalues of (B-1A). If A and B are positive
definite, then all the eigenvalues of B-1A will be real and non-negative, so the number of
iterations just depends upon

Note that I am ignoring one detail that B-1A is not symmetric. Please just trust me for now that
this doesn't make much difference, so I can get through the rest of the lecture.

Our goal in preconditioning is to find a matrix B that guarantees that the eigenvalues of B-1A are
not too big, and so that it is easy to solve a linear system in B. It will help if I give a different
characterization of

Prev Next