Lecture on Numerical Analysis

Lecture on Numerical Analysis

Dr.-Ing. Michael Dumbser

Numerical Integration (Quadrature) of Functions - Motivation

a b x

f

    













b

a

n i

i n

i x

x

d h

x f h dx

x f dx

x f

i

i 1

1

1 0

) (

) ( )

(

1





^{b }

a

dx x

f ( ) ?

h

n a h  b 

h i a

x_i   

Task: compute approximately

Solution strategy:

• Divide interval [a;b] into n smaller subintervals

• Approximate f(x) by interpolation polynomials on the subintervals, e.g. using Lagrange interpolation

• Integrate these polynomials exactly on each subinterval and sum up

• So-called Newton-Cotes formulae

Transformation of the Integration Interval







0 1

0

)

~( :

) (

) (

1f x dx h f x_i h d h f  d

x

x

i

i

The computation of numerical quadrature formulae for each sub-interval can be technically considerably simplified using the following variable substitution:

 h x

x  _i  h  x_i1  x_i h ddx 



Therefore, it is sufficient, without the loss of generality, to consider from now on the case of numerical integration in the reference interval [0;1].

...

)

~(

1

0



The Newton-Cotes Formulae

The integral of f(x) is approximated in the following steps:

1. First, the function f(x) is interpolated by a polynomial of degree k inside each sub-interval. The interpolation points are distributed in an equidistant manner in each sub-interval.

2. Second, the interpolation polynomial is integrated analytically.

3. Steps 1 and 2 produce an approximation of the integral of f(x) in terms of the function values f_i at the interpolation points and the step size h.

The Trapezium or Trapezoid Rule

a b

f

h

n a

h  b ^x_i ^{ a }^{i 1}^h

Use linear interpolation polynomials, i.e. polynomials of degree one in the subintervals [x_i;x_i+1]  [0;1]:

   

0 1

0 1

0 1

1

1 

 



 

   _ 

 P f_i f_i

f

  ₁

1

0

1 2

1 2

1

 

^{P  d}  ^{fi fi}

   ₁

1 2

1

 

^  ^{i i}

x

x

f h f

dx x P

i

i

x

    ₁

1   f_i 1  f_i P

The Simpson Rule

(Originally Discovered by Johannes Kepler in 1615)

a b

f

h

n a

h  b ^x_i ^{ a }^{i 1}^h

Use quadratic interpolation polynomials, i.e. polynomials of degree two:

      

  

  

     

  ₂¹²

1 1

21 21

12 12 2

1 0 1

0 1

0

1 0

1 0 0

1

21







 







 

 





 



 











 



i i

i

f f

f P

f

  ₁

1

0

2 6

1 3

2 6

1

2

1 

 



 ^{P  d}  ^{fi fi fi x}^{1 2 }  ₆





x

f f

h f dx

x P

i

i

x

 

 



 























 

2 1

2 2 2

2 4

1 3

2

2

1 i

i i

f f

f P

The 3/8 Rule

Use cubic interpolation polynomials, i.e. polynomials of degree three:

       

       

   

   

       

  ¹₃ ₃²³

3 2 1 1

32 31 23 32

31

13 32 13 13

23 23

31

32 13

3

1 1

0 1

0 1

0

1 0

1 0

1 0

1 0 0

0

1

3 2

3 1











 











 

 









 











 



 

























 



i i i i

f f

f f

P f

  ₁

1

0

3 8

1 8

3 8

3 8

1

3 2 3

1  

  



 ^{P  d}  ^{fi fi fi fi}

 

   



 

















23 2 3

2 1 3 9

2 1 34 3 272

32 2 35 3 272

92 119

2 3

29 3

32

3

2 1































 

 i i

i i

f f

f f

P

Isaac Newton

Sir Isaac Newton - (* 4. January 1643 in Woolsthorpe;

† 31. March 1727 in Kensington)

• Physicist, Mathematician, Astronomer and Philosopher

• Together with Leibniz, Newton is one of the inventors of infinitesimal calculus (differentiation and integration)

• 1667: Fellow of Trinity College, Cambridge

• 1687: Philosophiae Naturalis Principia Mathematica.

Newton discovered the universal law of gravitation and the laws of motion of classical mechanics

• 1704: Opticks. A corpuscular theory of light.

• From 1703 president of the Royal Society

• Buried in Westminster abbey in London

The Gaussian Quadrature Formulae

The previously derived formulae were all of the form

and were very easy to obtain since an equidistant spacing of the nodes was imposed and only the weights _j had to be computed. The aim of the Gaussian quadrature formulae is now to obtain an optimal quadrature formula with a given number of points by making also the nodes an unknown in the derivation procedure of the quadrature formula and to come up with an optimal set of nodes x_j and weights w_j.

An explicit construction strategy for Gaussian integration formulae:

(1) Using M quadrature points, we have M unknowns for the positions and also M unknowns for the weights, i.e. a total of 2M unknowns.

(2) We need 2M equations to determine uniquely the 2M unknowns.

(3) The equations are obtained by requiring that the integration formula is exact for polynomials from degree 0 up to degree 2M-1 !

 

 

M j

j f d

f    

 



1 1

0 1

1



  M

j

j

The Gaussian Quadrature Formulae

This means we have 2M equations of the form to solve for _j and _j.

For P_i(), any polynomial of degree i can be used, in particular also the monomial ⁱ.

  i

 

M j

j

i d P

P    

 



1 1

0

1 2

...

1 ,

0 

 M

j

Example 1: One integration point, i.e. M = 1, leading to the two equations:

  ^{1 1} ₀

 

1 1

0 1

0

0       

 











 ^M _j

j

jP d

d P

  1

 

1 1

0 1

0

1 2

1    







       

 

j M

j

jP d

d P

1 1

1

2 1

1  

 1



The Gaussian Quadrature Formulae

Example 2: Two integration points, i.e. M = 2, leading to the 4 equations:

2 1

1

0

1

1     

 ^d

2 2 1

1 1

0 2

1    



     

 ^d

1 3 , 1

1 3 , 1

1    



   



2 2 2 2

1 1 1

0 2

3

1    



     

 ^d

3 2 2 3

1 1 1

0 3

4

1    



     

 ^d

The Gaussian Quadrature Formulae

A more efficient and more general way of obtaining the Gaussian quadrature formulae makes use of so-called orthogonal polynomials L_i(), which are the so-called Legendre polynomials.

 ^



1

0

) ( ) (

,g f  g  d f

The set of polynomials L_i() is called orthogonal, if it satisfies the relation





 i  j

L

L_{i j} 0 if

, 

First, we define the scalar-product of two functions f and g as follows:

With this scalar product available, we can define the L₂ norm of a function f as

f f f  ,

The Gaussian Quadrature Formulae

The polynomials L_i() can be constructed via Gram-Schmidt orthogonalization from the monomials M₀ = 1, M₁ = ², M₃ = ³, … M_n = ⁿ as follows:

We first use the analogy of the scalar product of two functions with the scalar product already known for vectors:

 ^



i

i

i b

a b

a,  a  a,a

The Gram-Schmidt orthogonalization then proceeds as follows:

: L M  M1

0

, L0 L

M , L⁰ L⁰

M M

L  

M1

The Gaussian Quadrature Formulae

Instead of performing orthogonalization of vectors, we now perform the orthogonalization of functions as follows:

1 : )

0(  L

0 0

0 1 0

1

1 ,

) , ( )

( L L

L L M

M

L    



M1 M₁

0 0

0 2 0

1 1

1 2 1

2

2 ,

, ,

) , ( )

( L L

L L M

L L

L L M

M

L     

0 0

0 3 0

1 1

1 3 1

2 2

2 3 2

3

3 ,

, ,

, ,

) , ( )

( L L

L L M

L L

L L M

L L

L L M

M

L      

L L

L L

The Gaussian Quadrature Formulae

Using the orthogonality property of the Legendre polynomials, we find that



 



^{1 ( )}  ^{1, 1}_{0 else}^{if 0}

0

L i d

L_i   _i

The Gaussian quadrature formulae are written as

) ( )

(

1 1

0

j n

j

j f d

f    

 



If we now apply formula (2) to the integrals given in (1), we obtain the following

linear equation system for the weights _j, if we suppose the positions _j to be known:

(1)

(2)



 



 

  0 else

0 if

) 1 ( )

(

1 1

0

L i d

L ⁿ _{i j}

j

j

i     ⁽³⁾

) (

with _{i j}

i

j e L L

L      _(3‘)

The Gaussian Quadrature Formulae

Theorem:

If the n positions _j are given be the n roots of the polynomial L_n ( L_n( _j ) = 0 ), and the weights are given by the solution of system (3), then the Gaussian quadrature rules are exact for polynomials up to degree 2n-1, i.e.

Proof:

Suppose p() is an arbitrary polynomial of the space of polynomials of degree 2n-1, i.e.

Then we can write the polynomial p() as

1

) 2

( P_n p 

) ( )

( ) ( )

( L  q  r 

p  _n  q(),r()P_n1 )

( )

( ^ ^n1^kLk 

q ^r() ^ ^n1 ^kLk()

 



 ⁿ

j

j j p d

p

1 1

0

) ( )

(   

The Gaussian Quadrature Formulae

Proof (continued):

We have

We also have

  ₀

1

0 1

0

, 1 ,

) ( )

( ) ( )

(            

 ^{p d Ln q r d Ln q r}





) (

1 1

j j

j n n

j

j j

n j

j p   L  q  r 

   

 





 ^







 ¹

0 1

1

) ( )

( ⁿ

k

j k k n

j

j j

n j

j p    L 



0 1

1 0 1

) ( )

(    

    

 







n j

j k j n

k

k j

n j

j p L

This finishes the proof. QED

Integration of Improper Integrals

If the integration interval goes to infinity, it can be very useful to change the integration variables use the following substitution:

2 2

2

1 ) 1

( ,

) 1 (

1 1

) 1 (

1

1 1

1 1

1 dt g t dt g t f t t

t f t

t dt f t

dx x f

a

b a

b b

a

b

a





 



 

 



 



 



 



 

   



2

1 1

1

t dt

dx t x

x  t     

Example:

  



  







 



 



 

0

1 0

1

2

1 1 1

)

( dt g t dt

t f t

dx x f

 0 ab

If the integrand is singular at a known position c, than it is usually useful to split the integral as:





 







b

c c

a b

a

dx x f dx

x f dx

x f





) ( )

( )

(