Mathematics Question

1. Krylov Subspace: [5 marks each]

Consider the linear system Ax

b where A ∈ R

n×n

is non

–

singular and b ∈ R

(a) Consider a generic Krylov subspace method that generates iterates as

xk ∈ x0 + Kk (A, r0), 1 ≤ k ≤ t,

where r0

b b Ax0 and t is the grade of r0 with respect to A. Show that

Span{r0, r1,

. . .

, rkk1} ⊆ Kk (A, r0), k ≤ t, where ri

b b Axi

(b) Assuming A 0, consider the oblique projection framework where Wk

AKk,

and show that Span{r0, r1,

. . .

, rkk1}

Kk (A, r0), k ≤ t.

again the oblique projection framework. Show that hr0, rki

krkk

, 0 ≤ k ≤ t.

(d) Consider the case where A is symmetric (but not necessarily positive defifinite), and

recall the tridiagonal matrix Tk from the Lanczos process. Show that

Tk 0 ⇐⇒ hw, Awi > 0, ∀w ∈ Kk (A, r0)

2. Conjugate Direction Methods: [5 marks each]

For a given A ∈ R

n×n

, A 0, a collection of k non

–

zero vectors {p0, p1,

. . .

, pk}, where

k ≤ n n 1, are called A

–

conjugate, if

hpi, Apj i

0, i

(a) Show that {p0, p1,

. . .

, pk} are linearly independent.

(b) Given a collection of linearly independent vectors {v0, v1,

. . .

, vk}, design a Gram

Schmidt procedure to form a set of A

–

conjugate vectors {p0, p1,

. . .

, pk} such that

Span {v0, v1,

. . .

, vi}

Span {p0, p1,

. . .

, pi} , i

0, 1,

. . .

, k.