logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Algebra, zadanie nr 4275

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

123abc
postów: 4
2016-02-04 22:47:09

Udowodnić za pomocą indukcji matematycznej, że złożoność czasowa algorytmu odwracania macierzy metodą eliminacji Gaussa wynosi o(n^3).


janusz78
postów: 820
2016-02-05 22:00:14

Algorytm odwracania macierzy $ A $ metodą eliminacji Gaussa składa się z następujących przekształceń (kroków)

1.

$ Av^{j}= e^{j}, \ \ e^{j} $ - j-ty wektor bazy kanonicznej

2.

$ LUv^{j} = e^{j} $ rozkładu macierzy $LU $ macierzy $A$ w celu obliczenia $v_{j}$.
tzn. rozwiązania układu

$Lw^{j}=e^{j},$

$ Uv^{j} = w^{j}.$

Stąd wynika, że mamy do rozwiązania następujący układ równań:

$ w^{j}_{j}=1,$

$L_{j+1,j} w^{j}_{j}+ w^{j}_{j+1}=0,$

........................................................

$ L_{nj}w^{j}_{j}+L_{n,j+1}w^{j}_{j+1}+...+w^{j}_{n}=0.$

Na złożoność czasową rozwiązania tego trójkątnego układu, złożonego z $(n - j + 1)$ wierszy i $ (n - j + 1)$ kolumn składa się $(n-j + 1)^{2}$ operacji.

Stąd wynika, że złożoność czasowa algorytmu (konstrukcji wektorów $v_{j}$) jest równa

$ \sum_{n=1}^{n}(n-j+1)^2 = \sum_{k=1}^{n}k^2 = \frac{1}{6}n(n+1)(2n+1) \sim \frac{n^{3}}{3}= O(n^{3}).$

c.b.d.o.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt online: 31 drukuj