Método Cholesky em MATLAB

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

M�todo Cholesky/Cholesky (1).ppt
*
Fatoração Cholesky
Profa. Dra. Marli de Freitas Gomes Hernandez
CESET-UNICAMP
*
Andre-Louis Cholesky
(15 de outubro de 1875 – 31 de agosto de 1918)
 Ele serviu às forças armadas francesas como engenheiro geodésico. 
 
	Para resolver sistemas de equações condicionadas ao método dos mínimos quadrados, Cholesky inventou um procedimento computacional muito engenhoso que imediatamente se revelou extremamente útel, hoje chamado de Método de Cholesky. 
	A Fatorização Cholesky (ou Decomposição Cholesky) toma uma matriz simétrica positiva definida A e a escreve como A = LL’, onde L é uma matriz triangular inferior com diagonal positiva e L‘ é a matriz transposta de L . Para resolver Ax = b, resolve-se a forma LL'x = b fazendo y = L’x, ficabdo Ly = b, que é resolvida para y e em seguida, y = L'x é resolvida para obter a solução x. 
	A beleza do método é a trivialidade para resolver equações do tipo Mx = b quando M é uma matriz triangular.
*
Objetivo
Resolver um Sistema de equações lineares do tipo: 
onde aij ,i = 1,2,..., n e j=1,2,...,n coeficientes,
 bi, i = 1,2,...,n constantes,
 xj, j=1,2,...,n incógnitas.
*
Sistema na forma Matricial
Sistema na forma de equações lineares
Colocar o sistema de equações lineares (1.1) na forma matricial
A deve ser simétrica(aij= aji , i ≠ j.) positiva definida (ou seja, todos os autovalores são maiores do que zero)
Logo existe uma única matriz triangular inferior G nxn com diagonal positiva, tal que 
A =GT G 
*
Fatoração Cholesky
*
*
*
Algoritmo Cholesky
Matriz A deve ser simétrica positiva definida(todos os autovalores positivos diferentes de zero)
*
Programa Cholesky em MATLAB
% Determinar a Matriz R tal que A=(R’)R, A simétrica positiva definida
clear all % limpar memoria
clc % limpar tela 
disp('entre com o tamanho da matriz quadrada nxn')
n = input( 'n = ')
disp('entre com da matriz quadrada nxn, simétrica e positiva definida')
A = input( 'A = ')
G = zeros(4);
g(1,1) = sqrt(A(1,1));
for j = 2:n
 g(1,j) = A(1,j)/g(1,1);
end
for i = 2:n
 g(i,i) = A(i,i);
 for k = 1:i-1
 g(i,i) = g(i,i) - g(k,i)^2;
 end
 g(i,i) = sqrt(g(i,i));
 for j=i+1:n
 g(i,j) = A(i,j);
 for k = 1:i-1
 g(i,j) = g(i,j)-g(k,i)*g(k,j);
 end
 g(i,j) = g(i,j)/g(i,i);
 end
end
*
Programa Cholesky em MATLAB
clear all % limpar memoria
clc % limpar tela 
disp('entre com o tamanho da matriz quadrada nxn')
n = input( 'n = ')
disp('entre com da matriz quadrada nxn, simétrica e positiva definida')
A = input( 'A = ')
% Determinar a Matriz R tal que A=(R’)R, A simétrica positiva definida
for i=1:n
 for j=i:n
 r(i,j) = A(i,j);
 if i == j 
 if i > 1
 for k=1:i-1
 r(i,j) = r(i,j) - r(k,i)^2; 
 end
 end
 r(i,j)=sqrt(r(i,j));
 else
 if i > 1
 for k=1:i-1
 r(i,j) = r(i,j) - r(k,i)*r(k,j); 
 end
 end
 r(i,j) = r(i,j)/r(i,i);
 end
 end
end
*
Exemplo 
*
Bibliografia
[1] ANTON, H. & BUSBY, R. Algebra Linear Contemporânea. Editora Bookman. Porto Alegre. 2006.
[2] RUGGIERO, M.G. & LOPES, V.L.R. Cálculo Numérico – Aspectos Computacionais, Pearson Education. São Paulo. 1996.
[3] http://www-history.mcs.st-andrews.ac.uk/Biographies/Cholesky.html
Duas versões do Cholesky com detecção de ERROS está em anexo. 
M�todo Cholesky/cholesky.m
%cholesky
clear all % limpar memoria
clc % limpar tela 
disp('entre com o tamanho da matriz quadrada nxn, n > 0')
n = input( 'n = ')
disp('entre com da matriz quadrada nxn, simétrica e positiva definida')
A = input( 'A = ')
% Determinar a Matriz R tal que A=(R’)R, A simétrica positiva definida
% testar simetria da matriz A
for i=1:n
 for j=i+1:n
 if(A(i,j)~=A(j,i))
 disp('ERRO: matriz A assimétrica')
 c=input('digite CONTROL^C '); % forma de parar o programa
 end
 end
end
% Determinar G tal que A=G'G
if A(1,1) < 0 
 disp('ERRO: raiz quadrada de numero negativo g(i,i).')
 c=input('digite CONTROL^C '); % forma de parar o programa
else
 if A(1,1) == 0
 disp('ERRO: divisão por 0 no cálculo de g[i,j]/g(i,i).')
 c=input('digite CONTROL^C '); % forma de parar o programa
 else
 g(1,1)=sqrt(A(1,1));
 for j=2:n
 g(1,j)= A(1,j)/g(1,1);
 end
 for i=2:n
 g(i,i)=A(i,i);
 for k= 1:i-1
 g(i,i) =g(i,i) - g(k,i)^2;
 end
 if g(i,i) < 0 
 disp('ERRO: raiz quadrada de numero negativo g(i,i).')
 c=input('digite CONTROL^C'); % forma de parar o programa
 else
 if g(i,i) == 0
 disp('ERRO: divisão por 0 no cálculo de g[i,j]/g(i,i).')
 c=input('digite CONTROL^C'); % forma de parar o programa
 else
 g(i,i)=sqrt(g(i,i));
 for j=i+1:n
 g(i,j)=A(i,j);
 for k=1:i-1
 g(i,j)=g(i,j)-g(k,i)*g(k,j);
 end
 g(i,j)=g(i,j)/g(i,i);
 end
 end
 end
 end
 end
end
% Outra forma de programar o Cholesky
% Determinar R tal que A=R'R
for i=1:n
 for j=i:n
 r(i,j) = A(i,j);
 if i == j 
 if i > 1
 for k=1:i-1
 r(i,j) = r(i,j) - r(k,i)^2; 
 end
 end
 if r(i,i) < 0 
 disp('ERRO: raiz quadrada de numero negativo g(i,i).')
 c=input('digite CONTROL^C'); % forma de parar o programa
 else
 if r(i,i) == 0
 disp('ERRO: divisão por 0 no cálculo de g[i,j]/g(i,i).')
 c=input('digite CONTROL^C'); % forma de parar o programa
 else
 r(i,j)=sqrt(r(i,j));
 end
 end
 else
 if i > 1
 for k=1:i-1
 r(i,j) = r(i,j) - r(k,i)*r(k,j); 
 end
 end
 r(i,j) = r(i,j)/r(i,i);
 end
 end
end
M�todo Cholesky/Cholesky.pptx
Fatoração Cholesky
Profa. Dra. Marli de Freitas Gomes Hernandez
CESET-UNICAMP
Andre-Louis Cholesky
(15 de outubro de 1875 – 31 de agosto de 1918)
 Ele serviu às forças armadas francesas como engenheiro geodésico. 
 
	Para resolver sistemas de equações condicionadas ao método dos mínimos quadrados, Cholesky inventou um procedimento computacional muito engenhoso que imediatamente se revelou extremamente útel, hoje chamado de Método de Cholesky. 
	A Fatorização Cholesky (ou Decomposição Cholesky) toma uma matriz simétrica positiva definida A e a escreve como A = LL’, onde L é uma matriz triangular inferior com diagonal positiva e L‘ é a matriz transposta de L . Para resolver Ax = b, resolve-se a forma LL'x = b fazendo y = L’x, ficabdo Ly = b, que é resolvida para y e em seguida, y = L'x é resolvida para obter a solução x. 
	A beleza do método é a trivialidade para resolver equações do tipo Mx = b quando M é uma matriz triangular.
Objetivo
Resolver um Sistema de equações lineares do tipo: 
onde aij ,i = 1,2,..., n e j=1,2,...,n coeficientes,
 bi, i = 1,2,...,n constantes,
 xj, j=1,2,...,n incógnitas.
Sistema na forma Matricial
Sistema na forma
de equações lineares
Colocar o sistema de equações lineares (1.1) na forma matricial
A deve ser simétrica(aij= aji , i ≠ j.) positiva definida (ou seja, todos os autovalores são maiores do que zero)
Logo existe uma única matriz triangular inferior G nxn com diagonal positiva, tal que 
A =GT G 
Fatoração Cholesky
Algoritmo Cholesky
Matriz A deve ser simétrica positiva definida(todos os autovalores positivos diferentes de zero)
Programa Cholesky em MATLAB
% Determinar a Matriz R tal que A=(R’)R, A simétrica positiva definida
clear all % limpar memoria
clc % limpar tela 
disp('entre com o tamanho da matriz quadrada nxn')
n = input( 'n = ')
disp('entre com da matriz quadrada nxn, simétrica e positiva definida')
A = input( 'A = ')
G = zeros(4);
g(1,1) = sqrt(A(1,1));
for j = 2:n
 g(1,j) = A(1,j)/g(1,1);
end
for i = 2:n
 g(i,i) = A(i,i);
 for k = 1:i-1
 g(i,i) = g(i,i) - g(k,i)^2;
 end
 g(i,i) = sqrt(g(i,i));
 for j=i+1:n
 g(i,j) = A(i,j);
 for k = 1:i-1
 g(i,j) = g(i,j)-g(k,i)*g(k,j);
 end
 g(i,j) = g(i,j)/g(i,i);
 end
end
Programa Cholesky em MATLAB
clear all % limpar memoria
clc % limpar tela 
disp('entre com o tamanho da matriz quadrada nxn')
n = input( 'n = ')
disp('entre com da matriz quadrada nxn, simétrica e positiva definida')
A = input( 'A = ')
% Determinar a Matriz R tal que A=(R’)R, A simétrica positiva definida
for i=1:n
 for j=i:n
 r(i,j) = A(i,j);
 if i == j 
 if i > 1
 for k=1:i-1
 r(i,j) = r(i,j) - r(k,i)^2; 
 end
 end
 r(i,j)=sqrt(r(i,j));
 else
 if i > 1
 for k=1:i-1
 r(i,j) = r(i,j) - r(k,i)*r(k,j); 
 end
 end
 r(i,j) = r(i,j)/r(i,i);
 end
 end
end
Exemplo 
Bibliografia
[1] ANTON, H. & BUSBY, R. Algebra Linear Contemporânea. Editora Bookman. Porto Alegre. 2006.
[2] RUGGIERO, M.G. & LOPES, V.L.R. Cálculo Numérico – Aspectos Computacionais, Pearson Education. São Paulo. 1996.
[3] http://www-history.mcs.st-andrews.ac.uk/Biographies/Cholesky.html
Duas versões do Cholesky com detecção de ERROS está em anexo.