Algebra, zadanie nr 4275

Autor	Zadanie / 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