One spatial dimension: first order . 78

We analyze first the one-dimensional case that allows a better interpretation of the steps that are necessary to develop the FV approach or conservation laws. To this aim, we define a one-dimensional

grid as a non uniform subdivision of the domain into subintervals of dimension h_i = dx_i, where T_i is the i-th subdivision or Finite Volume cell. We denote by x_ithe center of the i-th cell and with x₁₊¹ and x₁₋¹ 2

2 its right and left boundary points (see Figure 3.1). We have the following relationships:

Ω = [a, b] =

We want to discretize the one-dimensional conservation law:

u_t+ f (u)_x = 0 x∈ [a, b] and t ∈ [0, T ], (3.13)

u(x, 0) = φ(x) t = 0. (3.14)

We redo the steps done in multidimension using now standard calculus. Integrate the equation in space over the domain and in time over the subinterval [t^k, t^k+1] = ∆t_k:

Z t^k+1 t^k

Z

Ω (u_t+ f (u)_x) dx dt = 0;

Using properties (3.10) and (3.12) together with the linearity of the integral operator we obtain:

Z t^k+1 t^k

Z x_j+1/2 x_j−1/2

(ut+ f (u)x) dx dt = 0, i = 1, . . . , N.

Define the cell average at time t^kas:

u^k_h =A^h(u(t^k)) = 1

and exchange the time derivative and the space integral in the first term to obtain after integration and use of simple left evaluation of the temporal integral in the second term (Forward Euler):

u^k+1_h,i = u^k_h,i− ∆t_k

∆x_i G^k_h,i+1/2− G^kh,i−1/2 . (3.15)

We note that this equation is consistent with (3.9) as the outward unit normals in x_j+1/2and and x_j−1/2 are 1 and -1, respectively.

Now we need to evaluate the fluxes G^k_h,i+1/2and G^k_h,i−1/2. These are obtained by solving a Riemann problem at each cell interface ` = i− 1/2 and ` = i + 1/2, i.e., find the solution of equation (3.13) where the initial conditions are given by constant states u^L and u^R just on the left and on the right of x_`. Since we are using an explicit time-stepping scheme, the left and right conditions are the numerical approximations of the cell averages at the previous time step u^k_h, and thus the Riemann problem can be written as:

Problem 3.4 (1D Riemann problem on x− `). Find the solution u^∗ of the equation:

ut+ f (u)x = 0 x = x`

subject to the following initial conditions:

u(x, 0) =

(u^L = u^k_{h,`−1/2</sub> = u<sup>k</sup><sub>h,i−1</sub>; if x < x<sub>`}, u^R = u^k<sub>h,`+1/2</sub> = u<sup>k</sup><sub>h,i+1</sub>; if x > x`.

The solution to this Riemann problem returns the value of u^∗that must be used to evaluate the numer-ical flux. As a result, the numernumer-ical flux can be written as a function of u^L and u^R, i.e., the left and right states of the local Riemann Problem:

G^k_h,i+1/2(u^k_h,L, u^k_h,R) = G^k_h,i+1/2(u^k_h,i, u^k_h,i+1).

In the case of the standard Godunov Scheme, G^k_h,i+1/2 = f (u^∗), i.e., the flux function evaluated at the solution of the Riemann problem. The resulting scheme displays first order convergence in both space and time, i.e., the norm of the error tends to zero linearly as ∆t and ∆x tend to zero:

u^k_h,i− u(xⁱ, t_k)

≤ C¹∆t +C²∆x.

Moreover, it can be shown that this approach is “monotone” and has “bounded variation” (BV). To understand the concept of BV functions, i.e., functions that have bounded variations, more details on functional analysis are needed. This is beyond the scope of this notes and will not be pursued further.

We refer the reader to specialized literature such as Evans [4], Bressan [2] for theoretical results on the theory of hyperbolic PDEs, LeVeque [9], Eymard et al. [5] for the theory of numerical methods, Hirsch [6], Toro [12] for more applied numerical approaches.

Remark 3.5. The one-dimensional finite volume method in equation (3.15) can be summarized in the following three distinct steps that are common to all Finite Volume approaches:

1. reconstruction: reconstruct the solution using piecewise (constant) cell-based interpolation;

2. evolution: evolve the solution by a step ∆t in time using the Riemann Problem solver at each cell interface, i.e., calculating numerically the flux outgoing or incoming through the cell boundary;

3. averaging: average the evolved solution over each cell.

These three steps are visualized in Figure 3.2 in the one-dimensional case.

Different numerical flux functions G characterize different schemes. The most well-known schemes are:

i−⁵2 i− 2 i−³2 i− 1 i−¹2 i i i + 1 i +¹₂ i + 2i + 3/2 reconstruction

i−⁵2 i− 2 i−³2 i− 1 i−¹2 i i i + 1 i +¹₂ i + 2i + 3/2

f⁰(x)∆t

evolution

i−⁵2 i− 2 i−³2 i− 1 i−¹2 i i i + 1 i +¹₂ i + 2i + 3/2

averaging

FIGURE 3.2: The one-dimensional finite volume method subdivided in three steps: 1. reconstruction (top), 2. evolution (middle), 3. averaging (bottom).

Godunov

G_h,i+1/2(u_h,i, u_h,i+1) = f (u^∗)

where u^∗ is the solution of the local Riemann problem.

Lax-Friedrichs

G_h,i+1/2(u_h,i, u_h,i+1) = ∆t

2∆x (u_h,i− u^h,i+1) + 1

2(f (u_h,i) + f (u_h,i+1)) Lax-Wendroff

G^k_h,i+1/2= f (u_h,i) + f (u_h,i+1)

2 − ∆t

2∆xA_i+1/2(f (u_h,i+1)− f(u^h,i))

where A_1+1/2 the Jacobian of f evaluated at x_i+1/2. This Jacobian can be calculated either analytically as f⁰((uh,i+ uh,i+1)/2) or numerically as

A_i+1/2 = (_{f (u}

h,i+1)−f (uh,i

u_h,i+1)−u_h,i if u_h,i+1)− u^h,i 6= 0 f (u_h,i+1) otherwise.

The latter scheme is second order accurate in space and time while the first two schemes are only first order accurate.

Remark 3.6. We would like to stress here that Godunov method is the only scheme in the above list that requires the solution of Riemann problems. The Lax-Friedrichs and Lax-Wendroff, in fact, do not require this step. These latter schemes are part of what is called the “central”, as opposed to “upwind”

schemes, as described in ? ].

Example 3.7 (Riemann solver for Burger equation). For Burger equation we can define the following exact Riemann solver:

1: procedure BURGER RS(u_L, u_R) .

2: λ ← ^{f (u}_u^R_R^{)−f (u}−u_L^L)

3: if u_L> 0 AND u_R > 0 then

4: u^∗ ← u^L

5: else if UL > 0 AND uR< 0 then

6: if λ > 0 then

7: u^∗ ← u^L

8: else

9: u^∗ ← u^R

10: end if

11: else . Should be uL< 0 AND uL < uR

12: u^∗ ← 0

13: end if

14: G← f(u^∗) = ¹₂(u^∗)² return G

15: end procedure

Second order accuracy in time can be achieved by employing a higher order explicit time integration such as the Runge method, a two-step Euler-based procedure. For Godunov scheme the following we have the following:

u^k+1/2_h,i = u^k_h,i− ∆tk

2∆x_i G^k_h,i+1/2− G^kh,i−1/2

 u^k+1_h,i = u^k_h,i− ∆t_k

∆x_i h

G^k+1/2_h,i+1/2− G^k+1/2h,i−1/2

i .

Obtaining second order in space needs higher order (linear) interpolation of the cell based values, and thus the reconstruction of the solution gradient, to obtain second order accurate left and right states for the Riemann solution. This yields a spatially second order accurate evaluation of the numerical flux, leading to globally second order accurate schemes. We would like to remark here that second order accuracy can be achieved only away from the discontinuity, where only constant reconstruc-tion guarantees monotonicity. Thus, to avoid the introducreconstruc-tion of oscillareconstruc-tion, we need to develop an appropriate gradient reconstruction.

3.3.2 One spatial dimension: second order gradient reconstruction

Higher order of convergence of the spatial discretization is obtained in general by employing higher order interpolation schemes. Second order interpolation is obtained by using linear polynomials to evaluate left and right states at cell interfaces. In this one-dimensional case, this can be obtained by

i−⁵2 i− 2 i−³2 i− 1 i−¹2 i i i + 1 i +¹₂ i + 2i + 3/2

FIGURE 3.3: Linearly interpolated left and right states at cell interfaces: dotted lines represent the centered difference gradients, solid lines the reconstructed cell-based linear solution. Oscillations may occur if the solution is not sufficiently smooth, i.e., the variation of subsequent cell values is large.

performing cell-based linear interpolation starting from cell values. For cell k the linear interpolant can be written as:

π_iu_h(x) = u^k_h,i+ (x− x^j)· ∇ u^kh,i. (3.16)

The cell gradient can be evaluated by interpolation using neighboring cell values as interpolation points. For example, we could the values of u of the neighboring cells at the two cell interfaces (up-wind or down(up-wind differences) or using the two cell neighbors (central difference). In general this approach leads to oscillations if the solution is not smooth enough, as Figure 3.3 clearly shows. One way to overcome this problem is to directly correct these oscillations once they have been detected.

This approach is called “slope-limiting” and consists in using first order interpolation when oscilla-tions occur. This amounts to setting the gradient to zero in (3.16). Hence the reconstruction step using slope-limited linear interpolation can be written as:

π_iu_h(x) = u^k_h,i+ (x− x^j)· φ(∇ u^kh,i)

where the function φ(·) is the slope-limited gradient in cell i. Typical slope limiting functions are defined in terms of “upwind”, “central” and and “downwind” gradients. In our one-dimensional case, they are written as:

∇^uuh = u_h,i− u^h,i−1

1

2(∆x_i−1+ ∆x_i); ∇^cuh = u_h,i+1− u^h,i−1

1

2(∆x_i−1+ ∆x_i+1) + ∆x_i; ∇^duh = u_h,i+1− u^h,i

1

2(∆x_i+ ∆x_i+1). For all limiters, φ = 0 if the upwind and downwind gradients change slope sign, i.e.,∇uu_h· ∇du_h <

0. This implies that the central cell value u^k_h,i is a local maximum or minimum, so that only φ = 0 will produce non-oscillatory results (see Figure3.3). Setting:

x =∇^uu_h, y =∇^du_h, z =∇^cu_h, then the following limiters can be listed:

MINMOD: (van Leer)

φ(x, y, z) = minmod(x, y) =







x if | x |<| y | and xy > 0;

y if | x |>| y | and xy > 0;

0 if xy≤ 0.

MC - Monotonized Central Difference (van Leer):

φ(x, y, z) = minmod(2 minmod(x, y), z) SUPERBEE (Roe):

φ(x, y, z) = maxmod(minmod(2x, y), minmod(x, 2y)), where

maxmod(x, y) =







x if | x |>| y | and xy > 0;

y if | x |<| y | and xy > 0;

0 if xy ≤ 0.

Liu: 1. let:

u^L_i−1/2 = π_i−1u_h(x_i−1/2); u^R_i+1/2 = π_i+1u_h(x_i+1/2);

2. φ(x, y, z) = largest gradient among the three candidates x, y, z such that the reconstructed edge values π_iu_h(x_i−1/2) and π_iu_h(x_i+1/2) satisfy:

u^L_i−1/2 ≤ πiu_h(x_i−1/2)≤ uh,i and u_h,i≤ πiu_h(x_i+1/2)≤ u^Ri+1/2,

A Finite Difference Approximations of first and second deriva-tives in R

¹

.

The finite difference method (FD) is used to approximate derivatives of functions. We consider here the derivation of the one dimensional standard approximations of the first and second derivatives of a function u(x) : I → R. To do so with simplicity we subdivide the interval I with a regular partition with n subintervals of size ∆x, and indicate with the index j the nodes of the subdivision, j = 0, 1, . . . , n. The coordinates of the boundary of each subinterval are given by the coordinates of two successive nodes, xj and xj+1 = x_j + ∆x. We denote by u_h,j the numerical approximation of the solution at node x_j: u_h,j ≈ u(x^k). Assuming u(x) sufficiently regular, we can write the following Taylor expansions:

u(x_j+1) = u(x_j+ ∆x) = u(x_j) + ∆xu_x(x_j) + ∆x²

2 u_xx(x_j) +O ∆x³
u(x_j−1) = u(x_j− ∆x) = u(x^j)− ∆xu^x(x_j) + ∆x²

2 u_xx(x_j) +O ∆x³

The first derivative can be factored after subtracting the second equation from the first, to yield:

u_x(x_j) = u(x_j+1)− u(xj−1)

2∆x +O ∆x²
.

Then a second order “central” approximation to the first derivative is given by:

u_x(x_j)≈ u_h,j+1− uh,j−1

2∆x .

On the other hand, the first derivative can be obtained from the first or the second of the two Taylor series expansions:

u_x(x_j) = u(x_j+1)− u(x^j)

∆x +O (∆x) ,

u_x(x_j) = u(x_j)− u(x^j−1)

∆x +O (∆x) ,

yielding forward or backward first order approximations:

u_x(x_j)≈ u_h,j+1− u^h,j

∆x ,

u_x(x_j)≈ u_h,j− uh,j−1

∆x .

Summing the two Taylor series expressions, we obtain a second order approximation of the second derivative:

u_xx(x_j) = u(x_j+1)− 2u(xj) + u(x_j−1)

∆x² +O ∆x²
,

u_xx(x_j)≈ u_h,j+1− 2uh,j + u_h,j−1

∆x² .

B Fortran program: Godunov method for Burgers equation

47 r e a l ( k i nd = d o u b l e ) , a l l o c a t a b l e : : u v a r ( : ) , g r a d ( : ) , uvarm ( : )

94 c a l l d e t o u t p u t ( n c e l l s , n f a c e s , t i m e , x c o o r d , u v a r )

95

96 enddo

97 98

99 end program b u r g e r s e q u a t i o n

Fortran/1D limiters/periodic BC var dx/burgers equation.f90

1 module g l o b a l s

2 i m p l i c i t none

3 i n t e g e r , par amete r : : s i n g l e = k i n d ( 1 . 0 e0 )

4 i n t e g e r , par amete r : : d o u b l e = k i nd ( 1 . 0 d0 )

5

6 i n t e g e r : : o u t p u t = 8 , i n p u t = 1 , d e b u g =10

7

8 end module g l o b a l s

Fortran/1D limiters/periodic BC var dx/Globals.f90

1 s u b r o u t i n e r e a d d a t a ( n c e l l s , n f a c e s , n p r t , t s t y p e , l i m i t e r , xmin , xmax , CFL , tmax )

2 u s e g l o b a l s

3 i m p l i c i t none

4 i n t e g e r : : n c e l l s , n f a c e s , n p r t , t s t y p e , l i m i t e r

5 r e a l ( k i nd = d o u b l e ) : : xmin , xmax , CFL , tmax

6

7 open ( u n i t = i n p u t , f i l e = ’ i n p u t . d a t ’ )

8 r e a d ( i n p u t ,∗ ) n c e l l s

9 r e a d ( i n p u t ,∗ ) n p r t

10 r e a d ( i n p u t ,∗ ) t s t y p e

11 r e a d ( i n p u t ,∗ ) l i m i t e r

12 r e a d ( i n p u t ,∗ ) xmin

13 r e a d ( i n p u t ,∗ ) xmax

14 r e a d ( i n p u t ,∗ ) CFL

15 r e a d ( i n p u t ,∗ ) tmax

16 c l o s e ( i n p u t )

17

18 n f a c e s = n c e l l s + 1

19

20 w r i t e ( o u t p u t , 1 0 0 0 ) n c e l l s , n f a c e s , t s t y p e , l i m i t e r , xmin , xmax , CFL , tmax

21 r e t u r n

22 1000 f o r m a t ( &

23 ’ # n c e l l s = ’ , I 1 0 , / , &

24 ’ # n f a c e s = ’ , I 1 0 , / , &

25 ’ # t s t y p e = ’ , I 1 0 , / , &

26 ’ # 0 −> 1 s t o r d e r Expl Eul ’ , / , &

27 ’ # 1 −> 2nd o r d e r Runge ’ , / , &

28 ’ # l i m i t e r = ’ , I 1 0 , / , &

29 ’ # 0 −> 1 s t o r d e r Godunov ’ , / , &

30 ’ # 1 −> 2nd o r d e r minmod ’ , / , &

Fortran/1D limiters/periodic BC var dx/read data.f90

1 s u b r o u t i n e i n i t ( n c e l l s , n f a c e s , xmin , xmax , CFL , d e l t a x , d e l t a t , &

38

39 end s u b r o u t i n e i n i t

Fortran/1D limiters/periodic BC var dx/init.f90

1 s u b r o u t i n e d e t o u t p u t ( n c e l l s , n f a c e s , t i m e , x c o o r d , u )

2 u s e g l o b a l s

3 i m p l i c i t none

4

5 i n t e g e r : : n c e l l s , n f a c e s

6 r e a l ( k i nd = d o u b l e ) , d i m e n s i o n ( n c e l l s ) : : u

7 r e a l ( k i nd = d o u b l e ) , d i m e n s i o n ( n f a c e s ) : : x c o o r d

8 r e a l ( k i nd = d o u b l e ) : : t i m e , d e l t a x

9

10 r e a l ( k i nd = d o u b l e ) : : a h a l f = 0 . 5 d0

11

12 i n t e g e r : : i

13

14 w r i t e ( o u t p u t , ’ ( a , e15 . 5 ) ’ ) ’ # t i m e = ’ , t i m e

15 do i = 1 , n c e l l s

16 d e l t a x = ( x c o o r d ( i + 1 )−x co or d ( i ) )

17 w r i t e ( o u t p u t , ’ ( 2 e15 . 5 ) ’ ) ( x c o o r d ( i ) + x c o o r d ( i + 1 ) )∗ a h a l f , u ( i )

18 end do

19

20 end s u b r o u t i n e d e t o u t p u t

Fortran/1D limiters/periodic BC var dx/det output.f90

1 s u b r o u t i n e G o d u n o v 2 n d o r d e r ( n c e l l s , n f a c e s , l i m i t e r , CFL , x c o o r d , g r a d , num flux , u v a r , uvarm )

2 u s e g l o b a l s

3 i m p l i c i t none

4

5 ! e x c h a n g e v a r i a b l e s

6 i n t e g e r : : n c e l l s , n f a c e s , l i m i t e r

7 r e a l ( k i nd = d o u b l e ) : : CFL

8 r e a l ( k i nd = d o u b l e ) : : x c o o r d ( n f a c e s ) , g r a d ( n c e l l s ) , u v a r ( n c e l l s ) , uvarm ( n c e l l s )

9 r e a l ( k i nd = d o u b l e ) : : n u m f l u x ( n f a c e s )

10

11 ! h e r e we work on c e l l s

12 c a l l g r a d r e c o n s t r u c t i o n ( n f a c e s , n c e l l s , l i m i t e r , x c o o r d , uvarm , g r a d )

13

14 ! h e r e we work on f a c e s

15 c a l l r i e m a n s o l v e ( n f a c e s , n c e l l s , x c o o r d , g r a d , uvarm , n u m f l u x )

16

17 ! h e r e we work on c e l l s

18 c a l l e v o l v e ( n c e l l s , n f a c e s , CFL , u v a r , uvarm , n u m f l u x )

19

20 end s u b r o u t i n e G o d u n o v 2 n d o r d e r

Fortran/1D limiters/periodic BC var dx/godunov 2nd order.f90

47 g r a d c a n d i d a t e ( 2 ) = ( u dwnwnd − u upwind ) / ( d e l t a x c e l l + a h a l f ∗ ( d e l t a x u p w i n d

Fortran/1D limiters/periodic BC var dx/grad reconstruction.f90

1 s u b r o u t i n e r i e m a n s o l v e ( n f a c e s , n c e l l s , x c o o r d , g r a d , u v a r , n u m f l u x )

36 u l e f t = u v a r ( i c e l l l e f t ) + a h a l f∗ d e l t a x l e f t ∗ g r a d ( i c e l l l e f t )

37 end i f

38 i f ( i f a c e . ge . n f a c e s ) t h e n

39 ! r i g h t b o u n d a r y

40 i c e l l r i g h t = 1

41 d e l t a x r i g h t = x c o o r d ( 2 )−x co or d ( 1 )

42 u r i g h t = u v a r ( i c e l l r i g h t ) − a h a l f ∗ d e l t a x r i g h t ∗ g r a d ( i c e l l r i g h t )

43 e l s e

44 d e l t a x r i g h t = x c o o r d ( i f a c e + 1 )−x co or d ( i f a c e )

45 u r i g h t = u v a r ( i c e l l r i g h t ) − a h a l f ∗ d e l t a x r i g h t ∗ g r a d ( i c e l l r i g h t )

46 end i f

47

48 ! Riemann s o l v e r

49 c a l l R S b u r g e r ( u l e f t , u r i g h t , u s t a r )

50 ! f l u x c a l c u l a t i o n

51 n u m f l u x ( i f a c e ) = f l u x ( u s t a r )

52 end do

53

54 r e t u r n

55 end s u b r o u t i n e r i e m a n s o l v e

Fortran/1D limiters/periodic BC var dx/rieman solve.f90

1 s u b r o u t i n e e v o l v e ( n c e l l s , n f a c e s , CFL , u v a r , uvarm , n u m f l u x )

2 u s e g l o b a l s

3 i m p l i c i t none

4

5 ! e x c h a n g e v a r i a b l e s

6 i n t e g e r : : n c e l l s , n f a c e s

7 r e a l ( k i nd = d o u b l e ) : : CFL

8 r e a l ( k i nd = d o u b l e ) : : u v a r ( n c e l l s ) , uvarm ( n c e l l s ) , n u m f l u x ( n f a c e s )

9

10 ! l o c a l v a r i a b l e s

11 i n t e g e r : : i c e l l , f a c e l e f t , f a c e r i g h t

12

13 ! e v o l u t i o n ( u p d a t e ) : d o n e on c e l l s

14 do i c e l l = 1 , n c e l l s

15 f a c e l e f t = i c e l l

16 f a c e r i g h t = i c e l l +1

17 uvarm ( i c e l l ) = u v a r ( i c e l l ) − &

18 CFL∗ ( numflux ( f a c e r i g h t ) − numflux ( f a c e l e f t ) )

19 enddo

20

21 r e t u r n

22 end s u b r o u t i n e e v o l v e

Fortran/1D limiters/periodic BC var dx/evolve.f90

1 f u n c t i o n s l o p e l i m i t ( l i m i t e r , d e l t a x , u u p w i n d , u c e l l , u dwnwnd , g r a d c a n d i d a t e )

2 u s e g l o b a l s

Fortran/1D limiters/periodic BC var dx/slope limit.f90

1 f u n c t i o n L i u ( d e l t a x , u c e l l , u u p w i n d , u dwnwnd , g r a d c a n d i d a t e )

2 u s e g l o b a l s

3 i m p l i c i t none

52 i m p l i c i t none

12 r e a l ( k i nd = d o u b l e ) : : j a c l e f t , j a c r i g h t , f l e f t , f r i g h t , l a m b d a

Fortran/1D limiters/periodic BC var dx/RS burger.f90

1 f u n c t i o n f l u x ( u )

17 i m p l i c i t none

18

19 r e a l ( k i nd = d o u b l e ) : : j a c , u

20

21 j a c = u

22

23 r e t u r n

24 end f u n c t i o n j a c

Fortran/1D limiters/periodic BC var dx/flux burger.f90

C Memorization of 2D Computational Meshes.

1

2

3 4 5

6 7 89 10 1

2 3

4 5

6 7

8 910 1 39

102 12

11 5

14

15

134 17

16 7

19

18

6 8

Cellconnectivity Tiv1v2v3 1142 2243 3154 4346 5574 6764 7587 8679 98107 107109 Vertexcoordinates vkx1x2 11.50.5 21.02.0 33.03.5 43.01.5 54.00.0 65.04.0 76.02.0 87.00.0 97.03.0 108.02.0

Edgeconnectivity fkv1v2 121 232 315 463 558 696 7810 8109 914 1042 1143 1254 1346 1457 1574 1676 1787 1879 19107

Edge-cellconnectivity fkTLTR 110 220 330 440 570 680 790 8100 913 1012 1124 1235 1346 1457 1556 1668 1779 18810 19910 Cell-Cellconnectivity Tif1f2f3 19101 210112 33129 411134 5141512 6161315 751714 816186 971917 1019818

Triangulation of a two-dimensional polygonal domain with cell, node, and edge global numbering, and the data structures needed to completely characterize the geometry and topology of the mesh.

D Review of linear algebra

In the following a scalar number (integer, real or complex) will generally indicated using lowercase Greek letters, e.g.:

α∈ I β ∈ R α ∈ C.

A vector, identified as an ordered n-ple of numbers (e.g., reals) will be named using lowercase English letter, and we will use the following equivalent notations:

x∈ Rⁿ x =

The number xi ∈ R is the i-th element (component) of vector x.

A matrix is identified by a table of numbers (e.g., reals) with n rows and m columns. It will be denoted with a uppercase letter of the English alphabet using the following equivalent notations:

A[n×m] A =

The number a_ij ∈ R is the ij-th element (component) of matrix A. In most cases we will use square matrices (m = n). A vector can be considered as a matrix with 1 column (m = 1). The use of a column vector is a convention, and we can define vectors more properly as element of vector spaces.

However, we will always use the previous notation in the discussion of the properties of vectors and matrices that are important for our developments.

Matrix sum. The sum of two matrices of the same dimension (row and column) is defined as the matrix have elements that are sums of the corresponding elements of the terms of the sum. In formula, given A, B, C ∈ R^n×m, we can write:

C = A± B := {a^ij ± b^ij}.

Product of a matrix by a scalar. The product of a matrix (or vector) by a scalar is defined again element-wise as:

αA ={αaij}.

Transpose matrix. Given a matrix A ∈ R^n×m, the matrix obtained by exchanging rows with columns is called the transpose of matrix and is indicated as A^T ∈ R^m×n:

A ={a^ij} A^T ={a^ji}.

In the complex field A ∈ C^n×n the operation of transposition must be accompanied by the operation of complex conjugation:

A ={a^ij} A^∗ = A^T ={a^ji}.

Zero (null) matrix. The zero matrix (vector) is a matrix with all elements equal to zero, and is the

“identity” element of the sum:

A = 0⇐⇒ a^ij = 0 i, j = 1, . . . , n.

Identity matrix. The identity matrix I is a matrix with unitary diagonal elements and zero non-diagonal elements:

I_[n×n] I :=













1 0 . . . 0 0 0 1 . . . 0 0 . . . . 0 0 . . . 1 0 0 0 . . . 0 1











 .

Positive (non-negative) matrix. A matrix is called “positive” (“non-negative”)⁸if all the elements are non-negative with at least one positive element:

A > 0⇒ a^ij ≥ 0.

Scalar product between two vectors. Given two vectors x, y ∈ Rⁿ, the sum of the product of corresponding elements is called the “scalar product” between x and y:

x^Ty =hx, yi = x · y :=

n

X

i=1

x_iy_i.

We will use also different notation such as:

hx, yi or x · y.

8The property of a matrix of being positive should not be confused with the property of being positive definite that will be seen in a few paragraphs.

A more formal definition of a scalar product (or inner product) is as follows. Given a vector space V ⊂ Cⁿ( o Rⁿ), the scalar (or inner) product between two elements x, y ∈ V , denoted by hx, yi, is a map:

h·, ·i : V × V → C ( o R)

that satisfies the following defining properties:

• (Hermitian Symmetry) hx, yi = hy, xi where (·) denotes complex conjugate;

• (Linearity) hαx + βy, zi = α hx, zi + β hy, zi;

• (positivity) hx, xi > 0 for each x ∈ Cⁿ(or Rⁿ) andhx, xi = 0 only if x = 0.

Matrix product. The product between two matrices, the row-by-column product, is given by the matrix whose components are the scalar products between the rows of the first matrix and the columns of the second matrix (though of as vectors):

A_[n×p] ={a^ij} B_[p×m]={b^ij} C_[n×m] ={c^ij}

C = AB c_ij := X

k=1,p

a_ikb_kj, i = 1, . . . , n j = 1, . . . , m.

The matrix-vector product is a special case of the matrix product with the vector though of as a n× 1 matrix. It is easy to check that, in the real field Rⁿ, the scalar product has the following property⁹:

hx, Ayi =A^Tx, y

hAx, yi =x, A^Ty .

Determinant of a matrix. Given a square matrix A[n×n], the determinant det (A) is the scalar given by the sum of all the products obtained taking as factors one element of each row and one element of each column:

det (A) :=X ±a^1,i1a_2,i2· · · aⁿ,in,

where i₁, i₂, . . . , i_n are different permutations of the first n natural numbers and the sign is given by the order of the permutation.

Trace of a matrix. Given a square matrix A_[n×n], the trace Tr (A) is the scalar given by the sum of all the diagonal elements

Tr (A) :=X

i=1

na_ii.

9Obviously, in Rⁿthe scalar product is commutative, i.e.:hx, Ayi = hAy, xi or x^TAy = (Ay)^Tx

Inverse of a square matrix. Given a square matrix A_[n×n], with det (A) 6= 0, the “inverse” matrix A⁻¹ is the matrix such that:

A⁻¹A = AA⁻¹ = I.

Singular matrix. A matrix is “singular” if it does not have an inverse. A singular matrix has a null determinant and vice-versa.

Orthogonal or unitary matrix. A matrix is orthogonal or unitary if:

U^T = U⁻¹.

Properties of operations between square matrices.

1. AB 6= BA (Matrices for which the commutativity properties of the product is valid are called

“commutative”).

2. A + B = B + A

3. (A + B) + C = A + (B + C) 4. (AB)C = A(BC)

5. A(B + C) = AB + BC; (A + B)C = AC + BC 6. (AB)^T = B^TA^T

7. (AB)⁻¹ = B⁻¹A⁻¹ 8. (A^T)⁻¹ = (A⁻¹)^T.

Symmetric Matrix. A matrix is called “symmetric” if it is equal to its transpose:

A = A^T;

it is called “skew-symmetric” if it is the negative of its transpose:

A =−A^T.

Every matrix can be decomposed as the sum of its symmetric and skew-symmetric parts:

A = 1

2(A + A^T) + 1

2(A− A^T).

Positive Definite Matrix. A matrix A_[n×n] is called “positive definite” (“semi-positive definite”) if:

x^TAx =hx, Axi > 0 (hx, Axi ≥ 0) ∀x 6= 0.

M-Matrix. A matrix is of type M or an M -matrix if:

1. it is non-singular;

2. all the diagonal elements are positive;

3. all the extra-diagonal elements are negative or zero.

An M -matrix has the important property that its inverse is a positive matrix.

D.1 Vector spaces, linear independence, basis

Vector Space. A vector space V over the scalar field R is a set of vectors where the operation of sum between two vectors and multiplication by a (real) scalar are defined. These operations must satisfy the following axioms¹⁰ for every x, y ∈ V and α, α¹, α₂ ∈ R:

1. x + y = y + x;

2. x + (y + z) = (x + y) + z;

3. the “zero” vector is the identity element of the sum between vectors: x + 0 = 0 + x = x;

4. for each x there exists a unique vector−x such that x + (−x) = 0;

5. 1x = x;

6. (α₁α₂)x = α₁(α₂x);

7. α(x + y) = αx + αy;

8. (α₁+ α₂)x = α₁x + α₂x.

Example of vector spaces:

• R^k, the set of all vectors with k components with the classic operations of sum and product by a scalar (the k-dimensional Eucledian space);

• R^∞the set of vectors with infinite elements (with the same operations as before);

10We note that these properties act in such a way that most of the elementary operations that we usually carry out in the scalar field will be valid also in a vector space.

• the space of matrices m × n; in this case the elements of the vector space are matrices and the operations are the usual ones;

• the space of continuous functions f(x) defined in the interval 0 ≤ x ≤ 1 (examples of elements of this space are f (x) = x² and g(x) = sin(x), for which we have (f + g)(x) = x²+ sin(x) and every multiple such as 3x² or− sin(x) belong to the same space). The vectors of the space are in this case functions and thus have “infinite dimensions”.

Vector Subspace. A subspace S ⊂ V of the vector space V is a subset of V with the following properties:

1. the sum of every two vectors x, y∈ S, z = x + y, is an element of S;

2. the product of every x∈ S by a scalar α ∈ R is an element of S: z = αx, z ∈ S.

We say that the subspace S is “closed” under the operations of addition and multiplication by a scalar.

An example of a vector subspace is a plane (affine to the vector space R² is thought isolated but it is contained in R³).

Linear independence. We say that k vectors v_i are “linear independent” if all the linear combina-tions of these vectors (except the trivial combination all zero coefficients) result in a non-zero vector:

α₁v₁+ α₂v₂+· · · + α^kv_k6= 0 excluding the case α₁ = α₂ =· · · = α^k = 0.

Otherwise the vectors are said “linearly dependent”.

The following property is true: a set of k vectors belonging to R^mmust necessarily be linearly depen-dent if k > m.

Span. If a vector space V is formed by all linear combinations of the vectors v₁, v₂, . . . , v_n, we say that these vectors “generate” the space V and we write:

V = span{v¹, v₂, . . . , v_n}.

In other words, every vector of V other than v₁, v₂, . . . , v_ncan be written as a linear combination of the generating vectors:

w∈ V ⇒ w = α¹v₁+ . . . α_nv_n=

n

X

i=1

α₁v₁.

Basis. A minimal set of vectors is a basis of the vector space V if:

1. the vectors are linearly independent;

2. the vectors generate V .

−y x

y

x−y

FIGURE D.1: Left panel: vectors x and y are orthogonal. We use Pythagoras’ theorem: vectors x and−y form the sides of a right triangles so that by (D.1) it is easy to see that equation D.2 is valid.

Right panel: orthogonal projection of subspace V (formed by one single vector) into the subspace W (the plane).

Dimension of a vector space. A vector space possesses an infinite number of bases, but each basis is made up by the same number of vectors. This number is called the “dimension” of the space V (dim (V )). For example, a basis of the three-dimensional space R³is formed by the set of coordinate vectors e₁, e₂, e₃, where e₁ = (1, 0, 0)^T, e₂ = (0, 1, 0)^T, e₃ = (0, 0, 1)^T, with obvious extension to the generic dimension n and we write:

n = dim(V ).

Every set containing linearly independent vectors of V can extended to a basis (if necessary adding appropriate vectors). Vice-versa, every set of V -generating vectors can be reduced to a basis (if necessary deleting appropriate vectors).

D.1.1 Orthogonality

We introduce first the concept of length of a vector x, denoted by kxk (see also the more general and formal definition of norm of vectors in Section D.4. Intuitively, in R², we can decompose the vector (assumed as a position vector with respect to standard Cartesian axis) along the principal axis, x = (x₁, x₂). In this case it is easy to define the length using Pythagoras’ theorem:

kxk² = x²₁+ x²₂,

and by direct extension to Rⁿwe obtain:

kxk² = x²₁+ x²₂+ . . . + x²_n.

Orthogonal vectors. Two vectors x and y in R² are orthogonal if the angle formed by their inter-section is equal to π/2 (Figure D.1):

kxk²+kyk² =kx − yk². (D.1)

If we write the previous equation component-wise we have immediately that the products between components in different positions must be zero (sum of double-products), from which we have the general condition of orthogonality in R^h:

x^Ty =hx, yi = 0. (D.2)

This quantity is the scalar product. We can show directly that if n vectors are all orthogonal then they are linearly independent.

Orthogonal Spaces Two subspaces V and W of Rⁿ are “orthogonal” if every vector v ∈ V is orthogonal to every vector w∈ W .

Orthogonal Complement. Let V ⊂ Rⁿ, the space of all vectors that are orthogonal to all vectors of V is called the “orthogonal complement” of V and is denoted by V^⊥.

Null Space and Range of a Matrix. The set of all vectors x ∈ Rⁿ such that Ax = 0 is called the

“null space” or “kernel” of matrix A and is denoted by Ker (A).

The set of all vectors x ∈ Rⁿ such that Ax 6= 0 is called “image” or “range” of matrix A and is

The set of all vectors x ∈ Rⁿ such that Ax 6= 0 is called “image” or “range” of matrix A and is

Nel documento Notes on theory and numerical methods for hyperbolic conservation laws (pagine 78-108)