Diễn đàn Hải Dương học

Giương buồm ra biển lớn !


Phương pháp giải ma trận Cholesky

Share

vuieng

****-
****-

Tổng số bài gửi : 93
Danh dự : 1
Join date : 15/01/2008
Age : 29

Phương pháp giải ma trận Cholesky

Bài gửi by vuieng on Wed Mar 26, 2008 10:48 am

Có phương trình A x = b (1)
Tách A = L . U trong đó : L ma trận tam giác dưới, U : ma trận tam giác trên
Khi đó phương trình (1) thành L (U x ) = b
Giải hệ :
L y = b
U x = y

Giải 2 phương trình trên bằng phép thế như sau khi khử Gauss (ma trận tam giác)
Nếu L có đường chéo chính bằng 1 thì gọi là phương pháp Doolittle.
Nếu U có đường chéo chính bằng 1 thì gọi là phương pháp Crout.
Nếu ma trận A đối xứng, xác định dương => L, U là chuyển vị của nhau: phương pháp Cholesky
Chia A thành LU theo Doolittle chỉ áp dụng cho ma trận ba đường chéo :

Code:
u(1,1) = a(1,1)
do i = 1,n-1
    u(i,i+1) = a(i,i+1)
    do i = 2,n
        l(i,i-1) = a(i,i-1)/u(i-1,i-1)
        u(i,i) = a(i,i) - l(i,i-1)*u(i-1,i)   
    enddo
enddo
Crout tương tự. Nếu thỏa đk để dùng được Cholesky thì đơn giản hơn nữa : A = S.chuyển_vị(S)
Chia A thành LU theo Cholesky chỉ áp dụng cho ma trận ba đường chéo :

Code:
s(1,1) = Sqrt(a(1,1));
s(1,2) = a(1,2)/s(1,1);
do i=2,n
    s(i,i) = Sqrt(a(i,i) - Sqr(s(i-1,i)));
    s(i,i+1) = a(i,i+1)/s(i,i);
enddo
Giải thuật là như vậy nhưng mà dù có bộ nhớ lớn cở nào cũng không ai dùng mảng 2 chiều để lưu ma trận chỉ có hai, ba đường chéo cả. Phải refine lại, ví dụ mỗi ma trận chỉ cần lưu đường chéo của nó thôi => L chỉ cần một Vector là đủ (vì đường chéo chính toàn bộ bằng 1)

Phương pháp trên nếu áp dụng cho ma trận không phải 3 đường chéo thì độ phức tạp tính toán lớn hơn cả chục lần, bạn tham khảo thêm các tài liệu về Phương Pháp Tính

tieuminh2510

*****
*****

Tổng số bài gửi : 350
Danh dự : 5
Join date : 15/01/2008
Age : 30

Re: Phương pháp giải ma trận Cholesky

Bài gửi by tieuminh2510 on Wed Mar 26, 2008 9:38 pm

Theo những gì tao biết thì ma trận 3 đường chéo và ma trận Cholesky là khác nhau
Ma trận ba đường chéo có ngoại trừ các phần tử trên 3 đường chéo chính, các phần tử còn lại điều là 0, và tất nhiên khi ta có thể tách A = LU
A: Ma trận 3 đưởng chéo
L: Ma trận tam giác dưới
U: Ma trận tam giác trên
Còn ma trận Cholesky thì là trường hợp đặc biệt của ma trận ba đường chéo khi đó:
A = LL' (L' là chuyển vị của L)



Hoàn toàn khác với công thức tính ma trận 3 đường chéo là:

Code:
        v(i)=a(i,i-1) 
        u(i-1)=a(i-1,i)/l(i-1)
        l(i)=a(i,i)-v(i)*u(i-1)

Cái bài tập tụi mình làm chỉ đơn thuần là ma trận 3 đường chéo thôi, chứ không là ma trận Cholesky

heo ptithcm

-----
-----

Tổng số bài gửi : 1
Danh dự : 0
Join date : 03/03/2010
Age : 26
Đến từ : việt nam

Re: Phương pháp giải ma trận Cholesky

Bài gửi by heo ptithcm on Wed Mar 03, 2010 10:57 am

hay đấy
thanks nhiều:d

Sponsored content

Re: Phương pháp giải ma trận Cholesky

Bài gửi by Sponsored content Today at 8:40 pm


    Hôm nay: Sat Dec 03, 2016 8:40 pm