This problem considers the situation of when the matrix is tri-diagonal, symmetric and positive definite. The equation to solve is
Ax
=
z, where
A
is given in (3.18). Because the matrix is symmetric and positive definite,
i
> 0 and
i
=
i−1.
(a) Show that the elements of the Cholesky factorization can be determined using an algorithm of the form
where
(
) =
(
) and
() =
( + 1). Note that instead of working with the matrix U, only the diagonal and upper diagonal entries are computed (since all the other entries are zero).
(b) Assuming the Cholesky factorization has been det ermined, show that the algorithm for solving the equation can be written as
(c) Use your algorithm from parts (a) and (b) to solve the matrix equation in the case of when
i
= 3,
i
=
i
= 1, and
=100,000. Also, take
z
=
Ax, where
x
= (1, 1, ··· , 1)
T
. It is only necessary to report the values of
(1) and
(2) (to 16 digits). Also, report the computed value of ||r||
∞
and ||e||
∞
.
(d) Using the same matrix as in part (c), use your algorithm to solve the matrix equation when
x
= (1, −1, 1, −1, ··· , −1)
T
. It is only necessary to report the values of
(1) and
(2) (to 16 digits). Moreover, you must give a compelling explanation of why you believe you answer is correct (within the limits of double precision).