LTL.rar_LTL_TRANSFORMATION

High Performance Algorithms – Exercise 3

1) Assuming that A is not positive definite , that is vector z exits in which:

there exists a lower triangular matrix L such that

. After placing the

That is of course cannot be right because

for every matrix B.

2) In a mathematical sense, if a vector z exists in which

then there is no L

such that

for z =

and A has Cholesky factorization L =

.

This is assuming we allow zeros in the diagonal of L.

In the floating point sense assuming the Cholesky factorization is backward stable

then it is not possible for

to be positive definite if A is not, otherwise applying the

algorithm on

suppose to give us Null because A does not have a factorization and

this is true for all matrices close to

thus all matrices close to

are not positive

We can see

as expected. From the above equations we will try to find L

and T.

The first equation is exactly a factorization of

into LTL form, meaning we can

First we can take out

using

we can find the part in the

multiplication of L and T.

We will now find

multiplication of

the right most column, this is because

possible the algorithm receives the first column of L. using the fist column of L and

the fact that T is tridiagonal we can find

first and last columns and the columns in the middle (

For columns 2 to n – 1:

This is again due to the fact that