Algebra, zadanie nr 4275
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
123abc post贸w: 4 |  2016-02-04 22:47:09Udowodni膰 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