algorytm.org

Metoda Choleskiego

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Metoda Choleskiego
Ocena użytkowników:***** / 19
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 08 sierpnia 2005 21:44

Metoda Choleskiego pozwala rozwiązać układ n równań liniowych z n niewiadomymi:
\sum_{j=1}^{n}{a_{ij}x_j = b_i} \text{, gdzie} i=1,2,...,n
w którym macierz współczynników jest symetryczna i dodatnio określona, tzn:
a) A=AH, a dla rzeczywistych A=AT
b) dla każdego x należącego do Cn zachodzi: xHAx>0, a dla rzeczywistych xTAx>0
Metoda wyznaczania rozwiązania układu równań liniowych, zwana metodą Choleskiego, polega na znalezieniu dla jego macierzy współczynników A macierzy trójkątnej dolnej:
\begin{bmatrix} l_{11} & 0 & ... & 0\\ l_{21} & l_{22} & ... & 0\\ ... & ... & ... & ...\\ l_{n1} & l_{n2} & ... & l_{nn} \end{bmatrix}
takiej, że A =LLT.

Obliczamy ją z następujących wzorów:
l_{kk} = \sqrt{a_{kk}-\sum_{j=1}^{k-1}{l_{kj}^2}}\\\\ l_{ik} = \frac{a_{ik}-\sum_{j=1}^{k-1}{l_{ij}l_{kj}}}{l_{kk}}
dla k=1,2...n oraz i=k+1,k+2...,n, czyli budujemy dla nich zagnieżdżoną iterację, w której szybciej zmieniającym się wyrazem jest pierwszy. Czyli dla n=3, otrzymamy: l[1,1], l[2,1], l[3,1], l[2,2], l[3,2], l[3,3]. Następnie obliczamy rozwiązanie na podstawie wzorów:
y_i = \frac{b_i-\sum_{j=1}^{i-1}{l_{ij}y_j}}{l_{ii}}, i=1,2,...,n\\ x_i = \frac{y_i-\sum_{j=i+1}^{n}{l_{ji}x_j}}{l_{ii}}, i=n,n-1,...,1
Ponieważ, w powyższych wzorach występują operacje pierwiastkowania, jak i dzielenia, należy program zabezpieczyć przed niepożądanymi danymi. Jeżeli okaże się, że podczas obliczania nastąpi próba nieprawidłowej operacji (dzielenie przez zero, pierwiastkowanie liczb ujemnych), oznacza to, że dana macierz nie jest dodatnio określona. Należy też pamiętać o sprawdzeniu symetryczności macierzy współczynników A przed przystąpieniem do obliczeń.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 września 2012 19:29
Komentarze
photo
+7 # Saimon 2009-09-08 16:11
Przydałby się przykład
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Maria 2011-12-14 00:26
Dołączam się do Saimona z prośbą o przykład.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz