Question

Write a function in Matlab that takes as input the number n and a symmetric tridiagonal matrix given as two vectors: n×1 vector v representing the main diagonal and (n−1)×1 vector w representing the upper diagonal. Have this function output the Cholesky factor of the matrix as a vector for the main diagonal and a vector for the upper diagonal and output the number of flops and, separately, the number of square roots used as well. Use only basic programming.

(a) Write out or print out your function.

(b) Run the case with v =2*ones(10,1), w = -ones(9,1) and write out or print out all your results.

(c) Rune the case with v =2*ones(100,1), w =-ones(99,1) and write out or print out your results just for the number of flops and square roots used. How many times more flops are used than in the previous case?

Answer 1

Part a) The Matlab function Cholesky_factor.m

function[V,W,flp,sqt]= Cholesky_factor(n,v,w)
    flp = 0;sqt = 0; % initially flp and sqt are zeros
    V(1) = sqrt(v(1));% First element C11
    sqt = 1; % found one sqrt above
    for i = 2:n % for the computation of elements 2 to n-1
        W(i-1) = w(i-1)/V(i-1); % one devision involved
        flp = flp +1; % for the devision
        V(i) = sqrt(v(i)-W(i-1)^2);
       flp = flp+1; % one substraction
       sqt = sqt+1; % one sqrt involved
    end
end

Part b)

>> v =2*ones(10,1);
>> w = -ones(9,1);
>> n =10;
>> [V,W,flp,sqt]= Cholesky_factor(n,v,w)

V =

    1.4142    1.2247    1.1547    1.1180    1.0954    1.0801    1.0690    1.0607    1.0541    1.0488

W =

   -0.7071   -0.8165   -0.8660   -0.8944   -0.9129   -0.9258   -0.9354   -0.9428   -0.9487

flp =

    18

sqt =

    10

>> A=diag(V)+diag(W,-1);
>> A*A'

ans =

    2.0000   -1.0000         0         0         0         0         0         0         0         0
   -1.0000    2.0000   -1.0000         0         0         0         0         0         0         0
         0   -1.0000    2.0000   -1.0000         0         0         0         0         0         0
         0         0   -1.0000    2.0000   -1.0000         0         0         0         0         0
         0         0         0   -1.0000    2.0000   -1.0000         0         0         0         0
         0         0         0         0   -1.0000    2.0000   -1.0000         0         0         0
         0         0         0         0         0   -1.0000    2.0000   -1.0000         0         0
         0         0         0         0         0         0   -1.0000    2.0000   -1.0000         0
         0         0         0         0         0         0         0   -1.0000    2.0000   -1.0000
         0         0         0         0         0         0         0         0   -1.0000    2.0000

Part c)

>> v =2*ones(100,1);
>> w =-ones(99,1);
>> n =100;
>> [V,W,flp,sqt]= Cholesky_factor(n,v,w);

flp =

   198

sqt =

   100

198-18 = 180 flops are more