img022 (47)

26

	ra« “u	0	0 •	■ 0
	«^(i) “21	a^(2) “22	0 •	• 0
L =	“li*	a(^2) “32	a(^3) . "33	• 0
	4	a^(2) ^Un2	a'W . ^Qn 3	• a ^unn

W trakcie realizacji algorytmu Gaussa dla wyznaczenia rozwiązania pewnego zadanego układu równań liniowych elementy macierzy L nie są na ogół zapamiętywane, gdyż nie są wykorzystywane w następnym etapie podstawiania wstecz. Okazuje się jednak [6, 7, 8, 19], że macierze U i L związane są następującą, niezwykle ważną z punktu widzenia jej wykorzystania, relacją²¹

L U = A .    (2.36)

Przekształcenie danej macierzy kwadratowej A do postaci iloczynu L ■ U, gdzie L jest pewną macierzą trójkątną dolną, a U macierzą trójkątną górną, jest nazywane przekształceniem LU lub rozkładem (dekompozycją) LU macierzy A na iloczyn czynników L i U [6, 7, 8, 19]. Nietrudno zauważyć, że jeżeli dla zadanej macierzy kwadratowej A istnieje przedstawienie w postaci iloczynu L ■ U, gdzie L i U są macierzami trójkątnymi, odpowiednio dolną i górną, to macierz A ma nieskończenie wiele różnych rozkładów na iloczyn czynników L i U. Istotnie, niech D\ i D₂ będą dowolnymi macierzami diagonalnymi, takimi, że D\ D₂ = /, gdzie / jest n x K-wymiarową macierzą jednostkową. Wówczas

L U = L D_x D₂ U = {L D_x)•(/>, -U)=L -U ,    (2.37)

gdzie L i U są nowymi macierzami trójkątnymi, odpowiednio dolną i górną, będącymi czynnikami rozkładu LU macierzy A.

Etap eliminacji w przód algorytmu eliminacji Gaussa jest w istocie algorytmem otrzymywania rozkładu LU dla danej nieosobliwej macierzy kwadratowej A po ewentualnym niezbędnym przestawieniu części jej wierszy (lub wierszy i kolumn). W przypadku ciągu operacji elementarnych przekształcających dany układ równań liniowych (2.33) do postaci (2.27), macierz U otrzymuje się w postaci macierzy trójkątnej górnej z jedynkami na głównej przekątnej, natomiast macierz L przyjmuje postać macierzy trójkątnej dolnej z elementami niezerowymi na głównej przekątnej.

W przypadku ciągu operacji elementarnych opisanych w podrozdziale 2.1 w związku z realizacją przekształcenia danego układu równań (2.33) do postaci (2.16), macierz A zostaje przekształcona w macierz trójkątną górną

^2> Jeżeli dla danej macierzy A istnieje przedstawienie w postaci iloczynu L ■ U pewnej macierzy trójkątnej dolnej L i macierzy trójkątnej górnej U, gdzie elementami diagonalnymi macierzy U są jedynki, to otrzymuje się det A = det L ■ det U = det L = 6 j • /₂₂ • ... • l_m.