Minta házi feladat

Contents

A Cholesky-felbontás elkészítése

A házi feladatban a Cholesky-felbontást elkészítő algoritmust valósítottam meg az alábbi függvénnyel

function U=CholeskyFelbontas(A)
% Elkészíti egy pozitív definit szimmetrikus mátrix Cholesky-felbontását,
% azaz azon U felső háromszög mátrixot, melyre U^T*U=A.

if A(1,1)<0 
            error('A mátrix nem pozitív definit');
end
U=zeros(size(A));
U(1,1)=sqrt(A(1,1));

for i=1:size(A,1)
    for j=1:i-1
        U(i,j)=(A(i,j)-dot(U(i,1:j-1),U(j,1:j-1)))/U(j,j);
        s=A(i,i)-dot(U(i,1:i-1),U(i,1:i-1));
        if s<0 
            error('A mátrix nem pozitív definit');
        else
            U(i,i)=sqrt(s);
        end
    end
end
U=U';

A függvényt működését az alábbi példán szemléltethetjük

A=[16 -4 4; -4 10 -1; 4 -1 2]

A =

    16    -4     4
    -4    10    -1
     4    -1     2

U=CholeskyFelbontas(A)

U =

     4    -1     1
     0     3     0
     0     0     1

Ekkor valóban U1*U'=A,

U'*U-A

ans =

     0     0     0
     0     0     0
     0     0     0

Továbbá tényleg csak pozitív definit mátrixokra működik, például az

A=[16 -4 4; -4 10 -1; 4 -1 -10]

A =

    16    -4     4
    -4    10    -1
     4    -1   -10

indefinit mátrixra meghívva hibaüzenetet kapunk.

Futásidő tesztelése a Gauss-eliminációhoz képest

Ehhez felhasználjuk a Gauss-eliminációt elkészítő függvényt

function [L, U]=simaGauss(A)

U=A;
L=eye(size(A,1));

for i=1:size(A,2)-1
    if A(i,i)==0
        error('A főátlóba 0 került!');
    end
    
    gausstr=eye(size(A,1));
    gausstr(i+1:end,i)= -U(i+1:end,i)./U(i,i);
    U=gausstr*U;
    L(i+1:end,i)=-gausstr(i+1:end,i);
end

A teszteléshez pozitív definit mátrixsorozatot készítünk, majd ellenőrizzük rajta a felbontás elkészítésének idejét.

meret=12;
futasidoChol=zeros(1, meret);
futasidoGauss=zeros(1, meret);

for j=1:meret
    i=j*40;
    A=rand(i);
    B=A'*A; % szimmetrikus, pozitív definit véletlen mátrix
    tic
    simaGauss(B);
    futasidoGauss(j)=toc;

    tic
    CholeskyFelbontas(B);
    futasidoChol(j)=toc;
end
plot(40:40:meret*40,futasidoGauss,'b', 40:40:meret*40, futasidoChol,'r')
xlabel('A mátrix mérete')
ylabel('Felbontás elkészítése (mp)')
title('Az LU és Cholesky felbontások összehasonlítása')
legend('LU','Cholesky')

A futásidőkön látszik, hogy nagyméretű mátrixokra a Cholesky-felbontás elkészítése gyorsabb. Viszont az sqrt() függvény kiszámítása több időt igényel, mint az alapműveletek, ezt látjuk kis méretű mátrixokra.

Published with MATLAB® R2018b