The Conjugate Gradient Method - Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory - page 222

In addition, suppose the solution of the saddle point problem is denoted by (u ∗ ,λ ∗ ) .
Now substituting the iteration formula for u k into (5.5) and using (5.3), we get

q k = g − BA − 1 (f − B t λ k − 1 ) = BA − 1 B t (λ k − 1 − λ ∗ ).

This means that

λ k − λ k − 1 =− αq k = αBA − 1 B t (λ ∗ − λ k − 1 ).

Thus the Uzawa algorithm is equivalent to applying the gradient method to the
reduced equation using a fixed step size (cf. Problem 2.6). In particular, the iteration
converges for

BA − 1 B t − 1 . α< 2

The convergence results of §§2 and 3 can be carried over directly. We need
to use a little trick in order to get an efficient algorithm. The formula (2.5) gives
the step size

q k q k
(B t q k ) A − 1 B t q k .

α k =

However, if we were to use this rule formally, we would need an additional multi-
plication by A − 1 in every step of the iteration. This can be avoided by storing an
auxiliary vector. - Here we have to pay attention to the differences in the sign.

5.2 Uzawa Algorithm (the variant equivalent to the gradient method).
Let λ 0 ∈ R

m

and Au 1 = f − B t λ 0 .

For k = 1 , 2 ,... , compute

q k = g − Bu k ,
p k = B t q k ,
h k = A − 1 p k ,
λ k = λ k − 1 − α k q k ,

q k q k

k =

p k h k ,

u k + 1 = u k + α k h k .

Because of the size of the condition number κ(BA − 1 B t ) , it is often more
effective to use conjugate directions. Since the corresponding factor β k in (3.4)
is already independent of the matrix of the system, the extension is immediately
possible.