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 L=CholeskyFelbontas(A) % Elkészíti egy pozitív definit szimmetrikus mátrix Cholesky-felbontását, % azaz azon L alsó háromszög mátrixot, melyre L*L^T=A. if A(1,1)<0 error('A mátrix nem pozitív definit'); end L=zeros(size(A)); L(1,1)=sqrt(A(1,1)); for i=1:size(A,1) for j=1:i-1 L(i,j)=(A(i,j)-dot(L(i,1:j-1),L(j,1:j-1)))/L(j,j); s=A(i,i)-dot(L(i,1:i-1),L(i,1:i-1)); if s<0 error('A mátrix nem pozitív definit'); else L(i,i)=sqrt(s); end end end
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
L=CholeskyFelbontas(A)
L = 4 0 0 -1 3 0 1 0 1
Ekkor valóban L*L'=A, hiszen
L*L'-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')+2*i*eye(i); % 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.