For large linear systems Ax=b with A∈En×n and b,x∈En, the solution x is usually not easy to find. So we would like to decompose A into a simpler form made of triangular matrices, i.e.
we look for matrices P,L,R∈En×n such that PA=LR,
PLR (often U)=^ is a permutation matrix (contains only 1 and 0)=^ is a left triangular matrix (lower triangular matrix)=^ is a right triangular matrix (upper triangular matrix)L=1∗⋮∗0⋱⋱⋯⋯⋱⋱∗0⋮01R=∗0⋮0⋯⋱⋱⋯⋯⋱⋱0∗⋮∗
Remark
Let A,P,L,R∈En×n. P stores the row swaps needed for pivoting, L stores the elimination steps that turn A into row echelon form, R is the row echelon form of A.
Remark
Let A,P,L,R∈En×n and b,c,x∈En.
The original system Ax=b can now be solved more easily:
Solve Lc=Pb for c by forward substitution, i.e. "Gauss" (L∣Pb) from top to bottom.
Solve Rx=c for x by back substitution, i.e. "Gauss" (R∣c) from bottom to top.
Remark
That the relation from the remark above gives the correct solution x∈En for A,P,P−1,L,R∈En×n can also be seen from
Ax=P−1PAx=P−1LRx=P−1Lc=P−1Pb=b.
Satz
For a regular square matrix A∈En×n there exists an LU decomposition, i.e.
∃P,L,R∈En×n:PA=LR.
RemarkLU decomposition light (i.e. without pivoting)
Assumption: no row swaps needed and A has no zero column
Given: A∈En×n
Wanted: L∈En×n,R∈En×n such that: A=LR
Write down the scheme (A∣𝟙)
Transform A using Gaussian elimination (WITHOUT row swaps!) until you reach row echelon form. You do all of this only on the left-hand side of the augmented matrix.
Show solutionHide solution13228641413100010001⇝(ii)−l21⋅(i)⇝(iii)−l31⋅(i)⇝(iii)−l32⋅(ii)1022264213130010001100222425132010001100220423132011001⟹A=13228641413=132011001100220423=LR.
(ii) Wanted: x∈Rn:Ax=b.
Show solutionHide solution
We proceed as suggested in the remark above (forward and back substitution):
Given: A∈En×n
Wanted: P∈Rn×n,L∈En×n,R∈En×n such that: PA=LR
Write down the scheme (𝟙∣A∣𝟙). On the left you keep track of the row swaps, in the middle you "Gauss", and on the right you keep track of the ratios.
Pivot in the current column j, i.e. determine the index ip∈{j,j+1,...,n} with ∣aipj∣=i∈{j,j+1,...,n}max∣aij∣. If ∣aipj∣=0, stop: no LU decomposition exists. Otherwise compute PijA=A in the middle, where Pij∈Rn×n is multiplied from the left onto the matrix on the left of the scheme, and on the right-hand side you have to swap the ratios accordingly (except in the first step).
If you have to pivot at the start, the result of the step looks as follows: (𝟙∣A∣𝟙)⇝(Pij∣A∣𝟙)
Otherwise, the result of the step looks as follows:
Transform A using Gaussian elimination (WITHOUT row swaps!) until you reach row echelon form. You do all of this only on the left-hand side of the augmented matrix.
If a zero entry shows up on the main diagonal again during the computation, you have to pivot again, i.e. repeat the second step. Then keep "Gaussing".
Show solutionHide solution1000100013−601086−16−17100010001⇝pivot:P21⇝(ii)−l21⋅(i)⇝pivot:P32010100001−630018−166−17100010001010100001−600018−16−2−171−210010001001100010−600081−16−17−210−21010001⇝(iii)−l32⋅(ii)001100010−600080−16−178110−210181001PA=0011000103−601086−16−17=10−210181001−600080−16−1781=LR
(ii) Wanted: x∈Rn:Ax=b.
Show solutionHide solution
We proceed as suggested in the remark above (forward and back substitution):
is called a field if the following holds ∀x,y,z∈E:
K1E together with addition + is an abelian group.
(Its neutral element is denoted by 0, the inverse of a∈E by −a; cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;+⟩ is an abelian group):
(i) (associativity) (x+y)+z=x+(y+z)
(ii) (neutral element) ∃e∈E:x+e=e+x=x
(iii) (inverse element) ∃x′∈E:x+x′=x′+x=e
(iv) (abelian ⇔ commutativity) x+y=y+x
K2 Writing E∗:=E∖{0}, for x,y∈E∗ we also have x⋅y∈E∗, and E∗ together with the multiplication obtained this way is an abelian group.
(Its neutral element is denoted by 1, the inverse of x∈E∗ by x−1 or 1/x. One writes y/x=x−1y=yx−1.
Cf. Discrete Mathematics, 5. Algebra, Definitions 5.7 and 5.8: ⟨E;⋅⟩ is an abelian group)
(cf. Discrete Mathematics, 5. Algebra: Definition 5.26 and Theorem 5.23)
Remark
Mostly we will work with the fields R or C. Another field familiar to us computer scientists is the smallest finite field Z2, which contains only {0,1}.
Definition
A vector spaceV over E (or E-vector space; VS) is a nonempty set V together with two operations:
V1V together with addition is an abelian (commutative) group (the neutral element is called the zero vector and is denoted by 0, and the negative is denoted by −x; cf. Discrete Mathematics, 5. Algebra: ⟨V;+⟩ is an abelian group):
(i) (associativity) (x+y)+z=x+(y+z)
(ii) (neutral element) ∃e∈V:x+e=e+x=x
(iii) (inverse element) ∃x′∈V:x+x′=x′+x=e
(iv) (abelian ⇔ commutativity) x+y=y+x
V2 Multiplication by scalars must be compatible with the other operations as follows:
(i) (distributivity I) (α+β)x=αx+βx
(ii) (distributivity II) α(x+y)=αx+αy
(iii) (associativity) (αβ)x=α(βx)
(iv) (compatibility with 1) 1x=x
Example 3
n-dimensional vectors form a vector space over E.
m×n matrices form a vector space over E.
Pn:={polynomials in one variable with coefficients in E of degree at most n} form a vector space over E.
Definition
Let V be a vector space, U⊆V,U={}. U is called a subspace (vector subspace, linear subspace) if it is closed under addition and scalar multiplication, i.e. if ∀x,y∈U and ∀α∈E:
U1x+y∈U
U2αx∈U.
Remark
Every subspace U contains the zero vector, i.e.
U00∈U.
Satz
Every subspace is a vector space.
Example 4
To show:W=⎩⎨⎧x1x2x3∈R3x1+x2+x3=0⎭⎬⎫ is a vector space.
Remark
We have two options:
Check whether V1 and V2 from the vector space definition are satisfied
Use the Satz above and show only U1 and U2
Show solutionHide solution
Proof:
We carry out the proof with the second option.
So by the Satz it suffices to show that W is a subspace.
Let x=x1x2x3,y=y1y2y3∈W,λ∈E
U0000∈W, since 0+0+0=0, (U0 follows trivially)
U1x+y=x1+y1x2+y2x3+y3∈W,
since (x1+y1)+(x2+y2)+(x3+y3)=x1+x2+x3=0(x1+x2+x3)+y1+y2+y3=0(y1+y2+y3)=0
U2λx=λx1λx2λx3∈W, since λx1+λx2+λx3=λx1+x2+x3=0(x1+x2+x3)=0
Or instead of showing U1 and U2 separately, you can also show the "all in one" variant:
U1/U2x−λy=x1−λy1x2−λy2x3−λy3∈W,
since (x1−λy1)+(x2−λy2)+(x3−λy3)=x1+x2+x3=0(x1+x2+x3)−λy1+y2+y3=0(y1+y2+y3)=0□
Injectivity, Surjectivity, Bijectivity
Definition
A map f:X→Y is called injective if
∀x1,x2∈X:x1=x2⇒f(x1)=f(x2).
(In words: different elements of X are mapped to different images in Y.)
Definition
A map f:X→Y is called surjective if
∀y∈Y∃x∈X:f(x)=y.
(In words: every element of Y is "hit" by f.)
Definition
A map f:X→Y is called bijective if
∀y∈Y∃!x∈X:f(x)=y.
(In words: every element of Y is "hit" by fexactly once.)