1.1 Normed spaces

Preliminary Topics

In this chapter we present the main notions from functional analysis, linear alge- bra...which are relevant for the lecture.

1.1 Normed spaces

LetV be a (linear) vector space.

Definition 1.1.1 A functionalk · k :V → Ris a norm onV overRif it satisfies the following:

i)kλxk=|λ|kxk, for allx∈V, λ ∈R. ii)kx+yk ≤ kxk+kyk,for allx, y ∈V.

iii)kxk= 0⇒x= 0.

Ifk · ksatisfies only i)-ii) it is called a seminorm.

Remark 1.1.1 Ifk · kis a norm on a vector spaceV, it follows from i) and ii) that kxk ≥ 0 ∀x ∈ V. Often is this property included in the definition of the norm, but it is not necessary.

LetV a vector space and k · k_V a norm on it. The norm induces a metric on V defined by d(x, y) = kx−yk_V. Using this metric we can define a topology, which is called the topology given by the normk · kV.

Definition 1.1.2 A normed space(V,k · k_V)is a topological vector spaceV, with the topology given by the normk · k_V.

1

Definition 1.1.3 A linear vector space V is called complete if every Cauchy se- quence is convergent to an element of V. A normed vector space which is complete is called a Banach space.

Definition 1.1.4 A subspaceE ofV is closed iff V \E is open, or, equivalently, for any sequence{x_n}_n∈N⊂E, ifx_n →xthenx∈E. The closure of a subspace (set)E is denoted byEand is the smallest set which containsE and is closed.

E ={x∈V|∃ {x_n}_n∈N⊂Ewith x_n→x}.

Proposition 1.1.1 Any complete space is closed. A subspace of a Banach space is complete iff is closed.

Proposition 1.1.2 Any normed space is either a Banach space or is dense in a Banach space.

Definition 1.1.5 Two normsk · k1,k · k2 are equivalent if there existsm, M > 0 s.t. there holds

mkxk₁ ≤ kxk₂ ≤Mkxk₁ ∀x∈V.

Proposition 1.1.3 i) Any two norms on a finite dimensional space are equivalent.

ii) Any finite dimensional normed space is a Banach space.

Definition 1.1.6 Let(E,k · k_E)and(V,k · k_V)two normed spaces. A map (oper- ator)f :E →V is called:

i) linear iff(αx+βy) = αf(x) +βf(y), ∀α, β ∈R, x, y ∈E.

ii) continuous if for all sequences {x_n}n∈N ⊂ E, lim

n→∞x_n = x^∗ there holds

n→∞lim f(xn) =f(x^∗).

iii) bounded if is linear and there existsC >0s.t. kf(x)k_V ≤Ckxk_E, ∀x∈V. Definition 1.1.7 Let(E,k · k_E)and(V,k · k_V)two normed spaces. We define

L(E,V) := {f :E →V|f(·) linear and continuous},and E⁰ := L(E,R) = {f :E →R|f(·)linear and continuous}

E⁰is called the dual space ofE. We endow the spaces above with the norms kfk_L(E,V) := sup

x∈E,x6=0

kf(x)k_V,and kfk_E⁰ := sup

x∈E,x6=0

|f(x)|.

Proposition 1.1.4 i)(L(E,V),k · k_L(E,V))is a normed space.

ii) If (V,k · k_V)is a Banach space, then(L(E,V),k · k_L(E,V))is also a Banach space. Especially,(E⁰,k · kE⁰)is always a Banach space.

Definition 1.1.8 Letf :E →V a linear operator. We define i)Ker(f) ={x∈E|f(x) = 0}=: the kernel off(·).

ii) Im(f) = f(E) = {f(x)|x ∈ E} =: the image off(·). The kernel and the image are subspaces ofV.

Proposition 1.1.5 Let f ∈ L(E,V)and kfk = kfk_L(E,V) the operator norm.

There holds i)kfk= sup

kxk_E≤1

kf(x)k_V = sup

kxk_E=1

kf(x)k_V. ii)kf(x)k_V ≤ kfkkxk_E.

Proposition 1.1.6 Let (E,k · kE) and (V,k · kV) two normed spaces and f :E →V a linear operator. The following affirmations are equivalent:

i)f(·)is continuous.

ii)f(·)is continuous at0.

iii)f(·)is bounded.

Proposition 1.1.7 Let(E,k · k_E)and(V,k · k_V)two normed spaces, with E finite dimensional. Then any linear operatorf :E →V is continuous.

1.2 Banach fix point theorem

Definition 1.2.1 Let(E,k·k_E)and(V,k·k_V)two normed spaces andf :E →V. The functionf is called Lipschitz continuous if there exists a constantL_f >0such that

kf(x)−f(y)k_V ≤L_fkx−yk_E, for allx, y ∈E. (1.1) Theorem 1.2.1 (Banach fix point theorem) Let V a Banach space, U ⊆ V a subspace andf :U →V. If

• U is closed

• f(·)is a contraction with Lipschitz constantL_f <1

• f(U)⊆U

then f(·) has an unique fix point x^? ∈ U. Moreover, the sequence x_n :=

f(xn−1), n≥1withx₀ ∈U arbitrary, converges tox^?. There holds also kx_k−x^?k_V ≤ L

1−Lkx_k−xk−1k_V a posteriori error estimate (1.2) kx_k−x^?k_V ≤ L^k

1−Lkx₁−x₀k_V a priori error estimate (1.3) Proof. We will show that the sequence defined by x_n := f(xn−1), n ≥ 1, x0 ∈ U arbitrary, converges to x^? ∈ U. We show the sequence is Cauchy, the result will then follow because the space is Banach and the set U is closed. There holds fork ≥2

kx_k−xk−1k=kf(xk−1)−f(xk−2)k ≤Lkxk−1−xk−2k ≤. . .≤L^k−1kx₁−x₀k (1.4) because f is a contraction. By using (1.4) and that L < 1, it follows for any m, n∈N, m≥n

kxm−xnk = kxm−xm−1+xm−1−xm−2+. . .+xn+1−xnk

≤ kx_m−xm−1k+kxm−1 −xm−2k+. . .+kx_n+1−x_nk

≤ (L^m−1+L^m−2 +. . .+Lⁿ)kx₁−x₀k

≤ Lⁿ 1

1−Lkx₁−x₀k. (1.5)

From (1.5) we get immediately that the sequence{x_n}_nis Cauchy. The space is Banach, then{x_n}_nconverges to x^? ∈ V. Butx_n ∈ U for alln, and the setU is closed, thenx^? ∈U. We have shown the convergence, we will prove now also the estimates. We have

kxk−x^?k = kf(xk−1)−f(x^?)k

≤ Lkxk−1−x^?k

≤ Lkx_k−xk−1k+Lkx_k−x^?k. (1.6) From (1.6) it immediately follows (1.2). We still have to show the a priori error estimate (1.3). There holds

kx_k−x^?k = kf(xk−1)−f(x^?)k

≤ Lkxk−1−x^?k ≤. . .≤L^k−1kx₁−x^?k. (1.7)

On the other hand we have

kx₁−x^?k=kf(x₀)−f(x^?)k ≤Lkx₀−x^?k ≤Lkx₁ −x^?k+Lkx₁−x₀k.

From above we get

kx₁−x^?k ≤ L

1−Lkx₁−x₀k. (1.8)

The result (1.3) follows then from (1.7) and (1.8). Q. E. D.

Corollary 1.2.1 LetV a Banach space andf : V → V a contraction with Lips- chitz constant L_f < 1. Thenf(·)has an unique fix pointx^? ∈ V. Moreover, the sequencex_n := f(x_n−1), n ≥ 1with x₀ ∈ U arbitrary, converges tox^? and the estimates (1.2) and (1.3) hold.

Definition 1.2.2 Let V a vector space. h·,·i : V × V → R is called an inner (scalar) product onV overRif:

i)hx, xi ≥0∀x∈V and hx,xi= 0⇒x = 0.

ii)hαx+βy, zi=αhx, zi+βhy, zi ∀x, y, z ∈V and ∀α, β ∈R. iii)hx, yi=hy, xi ∀x, y ∈V.

In the case of inner product overCthe property iii) must be replaced by iii)⁰ hx, yi=hy, xi ∀x, y ∈V.

Definition 1.2.3 A vector spaceV together with an inner product on it is called a pre-Hilbert space. Every pre-Hilbert space is a normed space with

kvk_V :=p hv, vi.

A pre-Hilbert space which is complete is called a Hilbert space.

1.3 Inequalities

We will make use of the following inequalities:

Lemma 1.3.1 (Cauchy-Schwarz inequality) Let a_i, b_i ∈ R, i = 1, . . . , n. There holds

n

X

i=1

a_ib_i

!2

≤

n

X

i=1

a²_i

! _n X

i=1

b²_i

!

. (1.9)

Lemma 1.3.2 (Jensen inequality) Letf :R→R. Then

i) iff is convex, i.e.f(ax+ (1−a)y)≤af(x) + (1−a)f(y)for alla∈[0,1]

andx, y ∈R, there holds

f(

n

X

i=1

λ_ix_i)≤

n

X

i=1

λ_if(x_i), (1.10)

for allλ_i ∈[0,1],Pn

i=1λ_i = 1andx_i ∈R,i∈ {1, . . . , N}.

ii) iff is concave, i.e.f(ax+(1−a)y)≥af(x)+(1−a)f(y)for alla∈[0,1]

andx, y ∈R, there holds

f(

n

X

i=1

λ_ix_i)≥

n

X

i=1

λ_if(x_i), (1.11)

for allλ_i ∈[0,1],Pn

i=1λ_i = 1andx_i ∈R,i∈ {1, . . . , N}.

Proof. We consider the casef convex, the other being absolutely similar. We prove the result by induction. Forn= 2, the inequality (1.11) is just the definition of convexity. Suppose now the inequality (1.11) holds forn−1and prove it forn.

Letλ_i ∈[0,1],Pn

i=1λ_i = 1andx_i ∈R,i∈ {1, . . . , N}. By using the hypothesis of induction we have

f(

n

X

i=1

λ_ix_i) = f(

n−2

X

i=1

λ_ix_i+ (λn−1+λ_n)(λn−1xn−1

λ_n−1+λ_n + λ_nx_n λ_n−1+λ_n))

≤

n−2

X

i=1

λ_if(x_i) + (λ_n−1+λ_n)f(λ_n−1x_n−1

λn−1+λ_n + λ_nx_n λn−1 +λ_n)

≤

n−2

X

i=1

λ_if(x_i) +λn−1f(xn−1) +λ_nf(x_n).

Q. E. D.

Lemma 1.3.3 (Young inequality) Leta, b ∈R+ andp, q >0,1 p+ 1

q = 1. There holds

ab≤ a^p p + b^q

q . (1.12)

Proof. The functionlnis concave, also there holds forp, q >0,1 p+ 1

q = 1 ln

a^p p + b^q

q

≥ 1

plna^p+ 1 qlnb^q, and the result (1.12) follows straightforward.

Q. E. D.

Corollary 1.3.1 (Generalized Young inequality) Let λ_i ∈ [0,1], i ∈ {1, . . . , N} withPn

i=1

1

λ_i = 1anda_i, i∈ {1, . . . , N}positive numbers. There holds

n

Y

i=1

a_i ≤

n

X

i=1

a^λ_iⁱ

λ_i . (1.13)

Proof. It follows immediately by applying the Jensen inequality for the ln function.

Q. E. D.

Lemma 1.3.4 (H¨older integral inequality) Let againp, q > 0,1 p + 1

q = 1andΩ be a domain inR^d,f, g: Ω→Rwith|f|^p and|g|^qintegrable two functions onΩ.

Then we have:

Z

Ω

|f g|dx≤ Z

Ω

|f|^pdx

1/pZ

Ω

|g|^qdx 1/q

. (1.14)

Forp=q = 2, the inequality above becomes Z

Ω

|f g|dx≤ Z

Ω

|f|²dx

1/2Z

Ω

|g|²dx 1/2

, (1.15)

and is called Cauchy-Schwarz integral inequality.

Lemma 1.3.5 (H¨older inequality) Let againp, q > 0,1 p + 1

q = 1andx₁, . . . x_n real numbers. Then there holds

n

X

i=1

|x_iy_i| ≤

n

X

i=1

|x_i|^p

!1/p n

X

i=1

|y_i|^q

!1/q

. (1.16)

Lemma 1.3.6 (Minkowski integral inequality) Let nowp ≥ 1,Ωbe a domain in R^dandf, g: Ω→Rwith|f|^p,|g|^pintegrable, two functions onΩ. Then we have:

Z

Ω

|f +g|^pdx 1/p

≤ Z

Ω

|f|^pdx 1/p

+ Z

Ω

|g|^pdx 1/p

. (1.17)

Lemma 1.3.7 (Minkovski inequality) Let againp ≥ 1and x₁, . . . x_n real num- bers. Then there holds

n

X

i=1

|x_i +y_i|^p ≤

n

X

i=1

|x_i|^p

!1/p

+

n

X

i=1

|y_i|^p

!1/p

. (1.18)

Lemma 1.3.8 (Gronwall integral inequality) Letb(·) : [0, T]→ Rbe a decreas- ing function and leth(·) : [0, T] → R be a positive function. Let nowf(·)be a function on[0, T]which satisfies a.e.t ∈[0, T]the integral inequality

f(t)≤b(t) + Z t

0

h(s)f(s)ds. (1.19)

Then there holds

f(t)≤b(t)e^R0th(s)ds. (1.20) for a.e.t ∈[0, T].

Proof. From (1.19), by multiplying withh(t)e^−R0th(s)ds,h≥0we get h(t)e^−R0th(s)dsf(t)−h(t)e^−R0th(s)ds

Z t 0

h(s)f(s)ds ≤ h(t)e^−R0th(s)dsb(t)

⇒

Z t 0

h(s)f(s)dse⁻

Rt 0h(s)ds

⁰

≤ b(t)h(t)e⁻

Rt 0h(s)ds

⇒

Z t 0

h(s)f(s)dse^−R0th(s)ds ≤ Z t

0

b(s)h(s)e^−R0sh(u)duds

⇒

Z t 0

h(s)f(s)ds ≤ Z t

0

b(s)h(s)e^Rsth(u)duds.

(1.21) Using (1.21) in (1.19) we get

f(t)≤b(t) + Z t

0

b(s)h(s)e^Rsth(u)duds.

By usingb(s)≤b(t), the above becomes f(t) ≤ b(t)

1 +

Z t 0

h(s)e^Rsth(u)duds

≤ b(t)

1 + Z t

0

−e^Rsth(u)du0 ds

≤ b(t)

1−1 +e^R0th(u)du

. (1.22)

Q. E. D.

Corollary 1.3.2 (Gronwall integral inequality) Letf(·)a no-negative function on [0, T]which satisfies a.e. t∈[0, T]the integral inequality

f(t)≤C₁ Z t

0

f(s)ds+C₂ (1.23)

for constantsC₁, C₂ ≥0. Then there holds

f(t)≤C₂e^C1t (1.24)

for a.e. t∈[0, T].

Lemma 1.3.9 (Discrete Gronwall inequality) Leta_n, λ_npositive numbers for all integersn∈NandB ≥0. Ifλ_n <1∀n ∈Nand

a_n≤B+

n

X

k=0

λ_ka_k ∀n∈N, (1.25)

then there holds

a_n≤Be

n

X

k=0

λ_k 1−λ_k

∀n ∈N. (1.26)

For proving the discrete Gronwall lemma we need an auxiliary result, whose proof is immediately by induction.

Lemma 1.3.10 Letλ_n∈[0,1)for all integersn∈N. Then we have 1 +λ₀e

λ0

1−λ0 +...+λ_ne

λ0

1−λ0+...+_1−λn^λn

≤e

λ0

1−λ0+...+_1−λn^λn

. (1.27)

We can now give a proof for the discrete Gronwall lemma.

Proof. We do this by induction. Forn = 0we havea₀

(1.25)

≤ B+λ₀a₀ ⇒a₀ ≤ B/(1−λ₀)and because

e^1−λλ ≥ λ

1−λ + 1 = 1

1−λ, (1.28)

forλ ∈[0,1)(we usede^x ≥x+ 1 ∀x≥0), we get (1.26). We assume now that (1.26) holds forn ≤k

a_n ≤Be

n

X

i=0

λ_i 1−λ_i

, (1.29)

and we prove it forn =k+ 1. We have ak+1

(1.25)

≤

k

X

i=0

λ_i

1−λ_k+1ai+ B 1−λ_k+1

(1.29)

≤

k

X

i=0

λ_i 1−λ_k+1e

i

X

j=0

λ_j 1−λj

B+ B

1−λ_k+1

(1.27)

≤ B

1−λ_k+1e

k

X

i=0

λ_i 1−λi

(1.28)

≤ Be

k+1

X

i=0

λ_i 1−λ_i

⇒(1.26).

Q. E. D.

We give now also a generalization of the triangle integral inequality for the case of functions valued in a Banach spaceX, namely the Bochner inequality (for the proof see Yoshida [11], Chapter V.

Proposition 1.3.1 (Bochner inequality) Letf : [t₁, t₂] → X an integrable func- tion andX a Banach space. There holds

Z t2

t1

f(t)dt X

≤ Z t2

t1

kfk_X dt. (1.30)

Lemma 1.3.11 Under the assumption (A1) we have

n

X

j=1

(b(x^j)−b(x^j−1))x^j ≥ −C|x⁰|²+

2|xⁿ|², (1.31) for any real sequencex^j,j ∈ {1, . . . , n}.

Proof. Sinceb⁰≥, one has ((b(x)−b(y))x≥

Z x y

sb⁰ds and Z x

0

sb⁰(s)ds≥ 2x², for any realsxandy. Furthermore,

n

X

j=1

(b(x^j)−b(x^j−1))x^j ≥

n

X

j=1

Z x^j x^j−1

sb⁰(s)ds

= Z xⁿ

0

sb⁰(s)ds− Z x⁰

0

sb⁰(s)ds≥ −C|x⁰|²+ 2|xⁿ|², where the constantC is half of the Lipschitz constant ofb(·). Q. E. D.

The following lemma is very useful for the proof of convergence for numerical schemes for nonlinear parabolic partial differential equations (when both the term with the time derivative and the second order term in space are nonlinear, as e.g.

in the case of the Richards equation). The lemma which was first first presented in [2]. The proof, which is elementary, can be found also in [3], p. 1685.

Lemma 1.3.12 Letuⁿ, vⁿ be real numbers,n ∈ {1, . . . N}. Suppose that|uⁿ− uⁿ⁻¹| ≤Cuτ andΘ : R→ Ris such that0 ≤Θ⁰ ≤CΘ⁰ <∞and|Θ⁰⁰| ≤CΘ⁰⁰. Then

Θ(uⁿ)−Θ(vⁿ)−Θ(uⁿ⁻¹) + Θ(vⁿ⁻¹)

τ (uⁿ−vⁿ)

= Ruⁿ

vⁿ Θ(µ)−Θ(vⁿ)dµ−Ruⁿ⁻¹

vⁿ⁻¹ Θ(µ)−Θ(vⁿ⁻¹)dµ

τ −E,

where

E ≤C{(uⁿ−vⁿ)²+ (uⁿ⁻¹−vⁿ⁻¹)²+τ²}, for someCdepending onC_u, C_Θ⁰ andC_Θ⁰⁰.

1.4 Examples of normed spaces

In this section we present some important normed spaces.

We define for1≤p < ∞the p-norm onRⁿby

kxk_p :=

n

X

i=1

|x_i|^p

!1/p

(1.32)

Proposition 1.4.1 For all 1 ≤ p < ∞, k kp is indeed a norm onRⁿ. Moreover, (Rⁿ,kk_p)is a Banach space.

Forp=∞we define

kxk∞:=maxⁿ

i=1 |x_i| (1.33)

Proposition 1.4.2 k k∞ is a norm on Rⁿ. Moreover, (Rⁿ,k k∞) is a Banach space.

All the above spaces are finite dimensional. As examples of infinite dimen- sional Banach spaces we considerC[0,1] :={f : [0,1]→R|f continuous}with the norm

kfk∞ = max

x∈[0,1]|f(x)|. (1.34)

and the Sobolev spaces

L^p(Ω) :={f : Ω→R|f measurable andkfk_p <∞}, whereΩis an open set inR^d,(d∈N, d≥1)and the norm

kfk_p :=

Z

Ω

|f(x)|^pdx 1/p

. (1.35)

1.5 Linear algebra

In this section we give some definitions and theorems from linear algebra. We begin with a few definitions.

Definition 1.5.1 A matrixA∈R^n,nis called

• positive (semidefinite) if

hAx, xi ≥0,∀x∈Rⁿ. (1.36)

• definite if

hAx, xi= 0 ⇒ x= 0. (1.37)

• positive definite if it is positive and definite.

Definition 1.5.2 A matrixA∈R^n,nis called inverse monotone if

Ax≤Ay⇒x≤y, ∀x, y ∈Rⁿ. (1.38) Definition 1.5.3 A matrixA ∈ R^n,nis called M-matrix, if it is inverse monotone anda_ij ≤0∀i, j ∈ {1, . . . , n}.

Proposition 1.5.1 A matrix is inverse monotone if and only if its inverse has only positive entries.

Proposition 1.5.2 (Properties of positive-definite matrices) A real symmetricn× n-matrixA = (a_ij)it is called positive definite(s.p.d.), whenh~x, A~xi>0for all 0 6= ~x ∈ Rⁿ, whereh~x, ~yi := Pn

i=1x_iy_i is the euclidean scalar product. Show that the following affirmations hold true:

• a_ii>0fori= 1, . . . , n.

• a²_ij < a_iia_jj fori6=j ∈ {1, . . . , n}.

• All the eigenvalues are real and positive. The matrix is invertible..

• All matrices of size(n−k)×(n−k)obtained from A through cutingk-rows and the correspondingk-columns are symmetric and positive definite.

• Let us consider the block decomposition A =

B ~a

~a^> a_nn

with the(n− 1)×(n−1)-blockB. Show thatBis invertible and it holdsa_nn >h~a, B⁻¹~ai.

Proposition 1.5.3 Let A ∈ R^n,n positive semidefinite and regular. Then A is positive definite.

Proposition 1.5.4 LetA ∈R^n,n,B ∈R^m,n withm≤nandrang(B) =m. IfA is positive definite then alsoBAB^T is positive definite.

Remark 1.5.1 As a consequence of Proposition 1.5.4, ifB ∈ R^m,n withm ≤ n andrang(B) = mthen there holds

• BB^T is positive definite and especiallydet(BB^T)6= 0.

• Ifm < n, thendet(B^TB) = 0.

Proposition 1.5.5 (a) Let A ∈ R^n,n. Gauss algorithm is realizable (without pivoting)⇔the main minorsdet(A_kk)6= 0for allk.

(b) Letx_i ∈R, i= 1, .., nwithx_i 6=x_j fori6=jandA∈R^n,ndefined by:

A:=

















1 1 ... 1

x1 x2 ... xn

. . ... .

. . ... .

. . ... .

xⁿ⁻¹₁ xⁿ⁻¹₂ ... xⁿ⁻¹_n















 .

Show through induction that

det(A) = Y

n≥i>j≥1

(xi−xj).

Is the Gauss algorithm us forArealizable (without pivoting)? Why?

Definition 1.5.4 A∈R^n,nis called weak diagonal dominant, when there holds

|a_ii| ≥

n

X

j=1;j6=i

|a_ij| ∀i.

If the inequality above is strict for alli, we call the matrix strong diagonal domi- nant.

Proposition 1.5.6 (a) Leti, k ∈ {1, ..., n}, i6=kanda, b∈Rⁿwith 06=|a_i| ≥

n

X

j=1;j6=i

|a_j|, |b_k| ≥

n

X

j=1;j6=k

|b_j|

be given. Letc∈Rⁿby defined by c_j =b_j − b_i

a_ia_j, j = 1, ..., n.

Show that it also holds

|c_k| ≥

n

X

j=1;j6=k

|c_j|.

(b) Show that if A ∈ R^n,n is weak diagonal dominant and regular, then the Gauss algorithm is realizable (without pivoting).

Proposition 1.5.7 Let A ∈ R^n,n symmetric. A is positive definite iff the Gauss elimination without pivot search is applicable and the n-pivots are positive.

Proof. Schwarz, pg. 41. Q. E. D.

Remark 1.5.2 A (strong) diagonal dominant matrix with positive diagonal en- tries is positive definite.

Proposition 1.5.8 (The Hurwitz criteria for positive definiteness)

Let A = (a_ij) be a real symmetric n×n matrix with then main determinants det







a11 · · · a1i

... . .. ... a_i1 · · · a_ii





,i= 1, . . . n, positive. Show thatAis positive definite.

Proposition 1.5.9 LetA∈R^n,n(strong) diagonal dominant. ThenAis regular.

Proposition 1.5.10 Let A ∈ R^n,n positive definite with a_ij ≤ 0, ∀i, j ∈ {1, . . . , n}withi6=j. ThenAis a M-matrix.

1.6 Matrix norm

Proposition 1.6.1 Let(E,k · k_E),(V,k · k_V)be two normed spaces and k · ka norm on L(E,V). We say thatk · kis compatible withk · k_E,k · k_V if there holds

kT xkV ≤ kTkkxkE ∀T ∈L(E,V). (1.39) Definition 1.6.1 (Matrix norm) A matrix norm is a functionk k:R^n,n →R,A→ kAkwith the following properties

i)kλAk=|λ|kAk ∀λ ∈R, A∈R^n,n. ii)kA+Bk ≤ kAk+kBk ∀A, B ∈R^n,n. iii)kAk= 0⇒A= 0_n.

iv)kABk ≤ kAkkBk ∀A, B ∈R^n,n(submultiplicity).

It follows from i)-iii) that alsokAk ≥ 0, ∀A ∈ R^n,n. Let us remember, that onL(E,V) we defined the operator normkTk := sup_x∈E,x6=0 kT xkV

kxk_E . It is well known, that L(Rⁿ,R^m) = R^m,n, and of course L(Rⁿ,Rⁿ) = R^n,n. Moreover, each matrixA∈R^n,ncan be identified with a operatorT ∈L(Rⁿ,Rⁿ). It is now natural to ask: is the operator norm also a matrix norm?

Proposition 1.6.2 Let (X,k k_X),(Y,k k_Y)and(Z,k k_Z) be three normed spaces andT ∈ L(X,Y), S ∈ L(Y,Z)two linear and bounded operators. Then there holds

kS◦Tk_L(X,Z) ≤ kSk_L(Y,Z)kTk_L(X,Y) (1.40) Proof. Letx∈X. There holds

kS◦T xkZ ≤ kSk_L(Y,Z)kT xkY ≤ kSk_L(Y,Z)kTk_L(X,Y)kxkX (1.41) It follows

sup

x∈X,x6=0

kS◦T xk_Z

kxk_X ≤ kSk_L(Y,Z)kTk_L(X,Y) ⇒(1.40).

Q. E. D.

Corollary 1.6.1 The operator norm is submultiplicative, and therefore it is a ma- trix norm.

Using the above results one can define some matrix norms:

kAk1 = sup

x∈Rⁿ,x6=0

kAxk₁

kxk₁ (column sum norm) (1.42) kAk∞ = sup

x∈Rⁿ,x6=0

kAxk∞

kxk_∞ (row sum norm) (1.43) kAk₂ = sup

x∈Rⁿ,x6=0

kAxk2

kxk₂ (euclidean norm) (1.44) kAk_p = sup

x∈Rⁿ,x6=0

kAxk_p kxkp

, p≥1. (1.45)

Definition 1.6.2 When the matrix norm is defined by a vector norm (as above), we say that the matrix norm is induced by the vector norm.

Proposition 1.6.3 The following affirmations hold true

kAk₁ = max

j=1,...,n n

X

i=1

|a_ij| (column sum norm) (1.46)

kAk∞ = max

i=1,...,n n

X

j=1

|a_ij| (row sum norm) (1.47) kAk₂ ≤ p

kAk₁kAk∞ (1.48)

kABk_p ≤ kAk_pkBk_p. (1.49)

Not all matrix norms are induced by a vector norm. For example theFrobenius norm, defined by

kAk_F :=

n

X

i,j=1

a²_ij

!1/2

(1.50) is not induced by any vector norm onRⁿ.

We introduce now thespectral radiusof a matrix

ρ(A) := max

λeigenvalue ofA

|λ| (1.51)

and the spectrum of A

σ(A) := {λ∈C|λeigenvalue ofA} (1.52)

Remark 1.6.1 The spectral radius is not a norm. Let e.g. A =

0 1 0 0

, we haveρ(A) = 0but obviouslyA6= 0₂.

Lemma 1.6.1 Let(E,k · kE),(V,k · kV) be two normed spaces with E finite di- mensional. Then, for the operator norm there holds

kTk= max

x∈E,kxk_E=1kT xk_V. (1.53)

Therefore it existsx∈Ewithkxk_E = 1such thatkTk=kT xk_V.

Proof. LetB_(0,1) :={x∈Ekxk_E = 1}be the unit ball in E.B_(0,1) is bounded and closed, E finite dimensional thereforeB_(0,1) is compact, which implies

sup

x∈B_(0,1)

= max

x∈B_(0,1).

Q. E. D.

Proposition 1.6.4 LetA∈R^n,n. Then there holds kAk₂ =p

ρ(A^TA). (1.54)

Proof. Q. E. D.

Remark 1.6.2 One can define more generally, forA ∈ R^n,m thekAkas a oper- ator norm fromR^m toRⁿ. The submultiplicativity condition makes but not much sense in this case (you can not multiply matrices inR^n,m, if m 6=n). The propo- sition above remains valid forA ∈R^n,m.

The next proposition is very important when studying the convergence of iterative solvers for linear systems.

Proposition 1.6.5 LetA∈R^n,n. Then

ρ(A)≤ kAk (1.55)

for any matrix norm. Moreover, for all >0it exists a matrix norm induced by a vector norm which satisfies

kAk ≤ρ(A) +. (1.56)

Proof. We prove first (1.55). Let λ ∈ Cbe the biggest eigenvalue of A and v ∈Cⁿa eigenvector associated toλ. LetB ∈C^n,nbe the matrix defined by B :=

vv^T. There holds

kABk=kAvv^Tk=k(Av)v^Tk=kλvv^Tk=|λ|kBk. (1.57) By using the submultiplicativity of the matrix norm (which we actually defined for R^n,nbut the definition can be extended to C^n,n without problems), i.e. kABk ≤ kAkkBkwe obtain from (1.57)

|λ|kBk=kABk ≤ kAkkBk ⇒

|λ| ≤ kAk ⇒ρ(A)≤ kAk.

For the second inequality (1.56) we refer to Skript Num I + II, Hoffmann

University Hamburg. Q. E. D.

Definition 1.6.3 We say that a matrix normk · kis compatible with a vector norm k · k_Rⁿ if there holds for allx∈RⁿandA∈R^n,n

kAxk_Rⁿ ≤ kAkkxk_Rⁿ. (1.58)

[1] R. A. ADAMS,Sobolev Spaces, Academic Press, New York, 1975.

[2] T. ARBOGAST, An error analysis for Galerkin approximations to an equa- tion of mixed elliptic-parabolic type, Technical Report TR90-33, Department of Computational and Applied Mathematics, Rice University, Houston, TX, 1990.

[3] T. ARBOGAST, M. OBEYESEKERE AND M. F. WHEELER, Numerical methods for the simulation of flow in root-soil systems, SIAM J. Num. Anal.

30 (1993), pp. 1677-1702.

[4] F. BREZZI AND M. FORTIN, Mixed and Hybrid Finite Element Methods, Springer Verlag, New York, 1991.

[5] Z. CHEN,Finite Element Methods and Their Applications, Springer Verlag, 2005.

[6] L. C. EVANS,Partial Differential Equations, American Mathematical Soci- ety, Providence, 1998.

[7] P. KNABNER AND L. ANGERMANN, Numerical methods for elliptic and parabolic partial differential equations, Springer Verlag, 2003.

[8] A. QUARTERONI AND A. VALLI, Numerical approximations of partial dif- ferential equations, Springer-Verlag, 1994.

[9] A. QUARTERONI, R. SACCO AND F. SALERI, Numerical mathematics, Springer-Verlag, New York, 2000.

[10] B. RYNNE AND M. YOUNGSON, Linear functional analysis, Springer- Verlag, 2000.

20

[11] YOSHIDA,Functional Analysis.