A map B:En×En→E,(v,w)↦B(v,w) is called a bilinear form (BLF) on En if it is linear in both arguments: ∀u,v,w∈En,∀λ∈E:
B(u+v,w)=B(u,w)+B(v,w),B(λu,v)=λB(u,v)
B(u,v+w)=B(u,v)+B(u,w),B(u,λv)=λB(u,v).
Definition
Let B be a BLF mapping to R. B is called symmetric if B(v,w)=B(w,v) and alternating if B(v,w)=−B(w,v), for ∀v,w∈En.
Definition
A map B:En×En→E,(v,w)↦B(v,w) is called sesquilinear on En if it is linear in the second argument and semilinear in the first argument: ∀u,v,w∈En,∀λ∈E:
B(u+v,w)=B(u,w)+B(v,w),B(λu,v)=λB(u,v)
B(u,v+w)=B(u,v)+B(u,w),B(u,λv)=λB(u,v).
Definition
A sesquilinear form B mapping to C is called Hermitian if B(v,w)=B(w,v).
Definition
A sesquilinear form B is called positive definite if
B(v,v)>0for every v∈En with v=0.
Remark
A symmetric, positive definite BLF is called a Euclidean inner product.
Definition
An inner product is a map ⟨⋅,⋅⟩:En×En→E,(v,w)↦⟨v,w⟩=∑k=1nvkwk such that: ∀u,v,w∈En,∀λ∈E:
⟨v+λw,u⟩=⟨v,u⟩+λ⟨w,u⟩ (bilinearity or sesquilinearity)
⟨v,w⟩=⟨w,v⟩ (symmetry or Hermitian)
⟨v,v⟩≥0 (positive semidefinite)
⟨v,v⟩≥0 and ⟨v,v⟩=0⇔v=0 (positive definite)
Definition
The length or Euclidean norm of a vector x∈En is the non-negative real number ∥x∥ defined by
∥x∥:=⟨x,x⟩=xHx=k=1∑n∣xk∣2.
Remark
Let x,y∈Rn and α∈[0,π] the angle between x and y, then:
⟨x,y⟩=∥x∥∥y∥cos(α).
Definition
Let B={bi}i∈I be a basis of V, ⟨⋅,⋅⟩ an inner product on V.
B is called orthogonal⇔⟨bk,bl⟩=0,∀k=l
In words: the basis vectors "are ⊥ to each other".
B is called orthonormal (ONB) ⇔⟨bk,bl⟩=δkl={1,k=l0,k=l
In words: the basis vectors "are ⊥ to each other" and have length 1.
Remark
Let V be a vector space with inner product ⟨⋅,⋅⟩, B={bi}i∈I a basis of V. By the definition of a basis, you can write every v∈V as v=∑i∈Iαibi. If B is an ONB, then αi=⟨bi,v⟩,∀i∈I, ⇒ the coordinates of v with respect to B are ⟨bi,v⟩.
The Outer Product and the Orthogonal Projection
Remark
inner product: ∀x,y∈En:⟨x,y⟩=xHy∈E
outer product: ∀x∈Em,∀y∈En:xyH∈Em×n
Satz
The orthogonal projectionPYx of x∈En onto the line through the origin spanned by y is:
PYx:=∥y∥21yyHx=uuHx with u:=∥y∥y
y-direction: PYx=αy,α∈E (PYx is a point on y).
x-direction: (x−PYx)⊥y.
Remarkprojection matrix
PYx:=∥y∥21yyHx=uuHx with u:=∥y∥y
PYH=PY (symmetric/Hermitian)
PY2=PY (idempotent; this is an alternative definition of a projection)
Gram-Schmidt Process
Satz
Every vector space of finite or at least countable dimension has an ONB. (i.e. it can be constructed with Gram-Schmidt)
AlgorithmGram-Schmidt process
Let V be a Euclidean/unitary vector space with dim(V)=n<∞
Given:W=span{v1,...,vm}⊂V,{vi}i=1m basis of W is linearly independent
Wanted 1:w1,...,wm such that W=span{w1,...,wm} and {wi}i=1m ONB of W is orthonormal
Wanted 2:w1,...,wm,wm+1,...,wn such that V=span{w1,...,wn} and {wi}i=1n ONB of V is orthonormal.
Given: the vector space P2 over R with inner product ⟨p,q⟩P=−1∫1p(t)q(t)dt and monomial basis B={1,t,t2}. Here: V=W=P2
Wanted: an ONB that is orthogonal with respect to ⟨⋅,⋅⟩P⇒ we have to orthonormalise 1,t,t2 with respect to ⟨⋅,⋅⟩P.
w3′=t2−⟨t2,21⟩21−⟨t2,23t⟩23t=t2−21∫−1121⋅t2dt−23t∫−1123t⋅t2dt=t2−21[321t3]−11−23t[2341t4]−11=t2−31−0=t2−31w3=∥w3′∥Pw3′=845(t2−31)because∥w3′∥P=∫−11(t2−31)2dt=[5t5−92t3+9t]−11=458W(3)={21,23t,845(t2−31)} is an ONB of P2.
QR Decomposition
Remark
Let A∈Em×n. Assume rank(A)=n≤m (full rank). Then there exists an orthogonal/unitary matrix Q=(Q1∣Q2) with Q∈Em×m,Q1∈Em×n,Q2∈Em×(m−n) and there exists an upper triangular matrix R1∈En×n, and with 0∈E(m−n)×n, such that
A=Q⋅(R10)=:QR
Remark
Since R=(R10), A=QR=Q1R1.
Remarkconnection between QR decomposition and least squares
For the residual r we have r=y−i=1∑n⟨qi,y⟩qi, where {qi}i=1n denotes the columns of Q1.
Remark
If the inner product under consideration is the standard inner product, then:
The 2-norm condition number (condition for short) of a matrix A∈En×n is given by
κ2=min{∣ω∣}max{∣ω∣},
where ω is the eigenvalue of A (holds for symmetric/Hermitian regular A).
In particular, the condition number is always greater than or equal to 1.
Remark
We always want the condition to be as small as possible, because then the implementation is numerically most stable, i.e. a large condition is bad and undesirable.
Remark
The QR decomposition is unique for m≥n and rank(A)=n if you fix the signs of the diagonal entries of the triangular matrix.
Remarknormal equations vs. QR decomposition
Normal equations
Pro:
"nice" to compute by hand
AHA is Hermitian positive definite ⇒ can be exploited for the Cholesky decomposition
Con:
If A is ill-conditioned, AHA is quadratically ill-conditioned. ⇒ Cholesky delivers useless results (rounding errors massively amplified, implementation unstable)
QR decomposition
Pro:
can be implemented in a numerically stable way (the method depends less on the condition)