Пресс-релиз популярных книг

Авторы: 111 А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я

Книги: 164 А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я

На сайте 111 авторов, 92 книг, 72 статей, 5913 глав.

Numerical Integration

Back

___ Introduction

After transformation to a canonical element ___ typical integrals in the element sti_ness

or mass matrices _cf_ ________ have the forms

Q ZZ

____ __NsNTt

det_Je_d_d__ _____a_

where ____ __ depends on the coe_cients of the partial di_erential equation and the

transformation to __ _cf_ Section ____ The subscripts s and t are either nil_ __ or

_ implying no di_erentiation_ di_erentiation with respect to __ or di_erentiation with

respect to __ respectively_ Assuming that N has the form

NT _N__N__ _ _ _ _Nnp __ _____b_

then _____a_ may be written in the more explicit form

Q ZZ

____ __

_____

_N__s_N__t _N__s_N__t _N__s_Nnp_t

_ _ _

_Nnp_s_N__t _Nnp_s_N__t _Nnp_s_Nnp_t

_____

det_Je_d_d__

_____c_

Integrals of the form _____b_ may be evaluated exactly when the coordinate trans_

formation is linear _Je is constant_ and the coe_cients of the di_erential equation are

constant _cf_ Problem _ at the end of this section__ With certain coe_cient functions and

transformations it may be possible to evaluate _____b_ exactly by symbolic integration_

however_ we_ll concentrate on numerical integration because_

_ it can provide exact results in simple situations _e_g__ when _ and Je are constants_

and

_ Numerical Integration

_ exact integration is not needed to achieve the optimal convergence rate of _nite

element solutions ____ __ ____ and Chapter ___

Integration is often called quadrature in one dimension and cubature in higher dimen_

sions_ however_ we_ll refer to all numerical approximations as quadrature rules_ We_ll

consider integrals and quadrature rules of the form

I ZZ

f___ __d_d_ _

Wif__i_ _i__ _____a_

where Wi_ are the quadrature rule_s weights and __i_ _i_ are the evaluation points_ i

__ __ _ _ _ _ n_ Of course_ we_ll want to appraise the accuracy of the approximate integration

and this is typically done by indicating those polynomials that are integrated exactly_

De_nition ______ The integration rule _____a_ is exact to order q if it is exact when

f___ __ is any polynomial of degree q or less_

When the integration rule is exact to order q and f___ __ _ Hq_______ the error

E I _

Wif__i_ _i_ _____b_

satis_es an estimate of the form

E _ Cjjf___ __jjq___ _____c_

Example ______ Applying ______ to _____a_ yields

Q _

Wi___i_ _i_N__i_ _i_NT __i_ _i_ det_Je__i_ _i___

Thus_ the integrand at the evaluation points is summed relative to the weights to ap_

proximate the given integral_

Problems

__ A typical term of an element sti_ness or mass matrix has the form

_i_jd_d__ i_ j__ __

Evaluate this integral when __ is the canonical square ____ __ _ ____ __ and the

canonical right __ unit triangle_

____ One_Dimensional Quadrature _

___ One_Dimensional Gaussian Quadrature

Although we are primarily interested in two_ and three_dimensional quadrature rules_

we_ll set the stage by studying one_dimensional integration_ Thus_ consider the one_

dimensional equivalent of ______ on the canonical ____ __ element

I Z _

f___d_

Wif__i_ _ E_ ______

Most classical quadrature rules have this form_ For example_the trapezoidal rule

I _ f____ _ f___

has the form ______ with n __ W_ W_ __ ___ __ __ and

E _

_f_____

_ _ _ ____ ___

Similarly_ Simpson_s rule

I _

_f____ _ f___ _ f____

has the form ______ with n __ W_ W__ W_ ____ ___ __ __ __ __ and

E _

f_iv ___

_ _ _ ____ ___

Gaussian quadrature is preferred to these Newton_Cotes formulas for _nite element

applications because they have fewer function evaluations for a given order_ With Gaus_

sian quadrature_ the weights and evaluation points are determined so that the integration

rule is exact _E __ to as high an order as possible_ Since there are _n unknown weights

and evaluation points_ we expect to be able to make ______ exact to order _n _ __ This

problem has been solved ___ _ and the evaluation points _i_ i __ __ _ _ _ _ n_ are the roots

of the Legendre polynomial of degree n _cf_ Section _____ The weights Wi_ i __ __ _ _ _ _ n_

called Christo_el weights_ are also known and are tabulated with the evaluation points

in Table ____ for n ranging from _ to _ A more complete set of values appear in

Abromowitz and Stegun ____

Example ______ The derivation of the two_point _n __ Gauss quadrature rule is

given as Problem _ at the end of this section_ From Table ____ we see that W_ W_ _

and ___ __ __p__ Thus_ the quadrature rule is

Z _

f___d_ _ f____p__ _ f___p___

This formula is exact to order three_ thus the error is proportional to the fourth derivative

of f _cf_ Theorem _____ Example ____ and Problem _ at the end of this section__

Numerical Integration

n _i Wi

_ _______ _____ _____ _______ _____ _____

_ _______ ____ ___ _______ _____ _____

_ _______ _____ _____ _______ _____ _____

______ __ ___ _______ _____ ____

_______ ____ ___ _____ ____ __

______ ____ ____ ______ ___ ___

_ _______ _____ _____ ______ _____ _____

_____ _____ ____ _____ ___ ___

______ ____ __ ______ ____ ____

______ ____ _____ _____ ____ ____

_____ ___ __ _____ _____ ____

_____ ____ _____ _______ ___ _____

Table _____ Christo_el weights Wi and roots _i_ i __ __ _ _ _ _n_ for Legendre polynomials

of degrees _ to ____

Example ______ Consider evaluating the integral

I Z _

e_x_

erf___ ____________ ______

by Gauss quadrature_ Let us transform the integral to ____ __ using the mapping

_ _x _ _

to get

_ Z _

e__ ___

_ _

d__

The two_point Gaussian approximation is

I _ _I

_e__ ____p_

_ _

_ e__ ____p_

_ _

Other approximations follow in similar order_

Errors I _ _I when I is approximated by Gaussian quadrature to obtain _I appear in

Table ____ for n ranging from _ to _ Results using the trapezoidal and Simpson_s rules

are also presented_ The two_ and three_point Gaussian rules have higher orders than the

corresponding Newton_Cotes formulas and this leads to smaller errors for this example_

____ One_Dimensional Quadrature _

n Gauss Rules Newton Rules

Error Error

_ _______ __

_ _______ _ _______ __

_ _______ _ ______ _

_______ __

_ _____ __

__________

Table _____ Errors in approximating the integral of Example ____ by Gauss quadrature_

the trapezoidal rule _n __ right_ and Simpson_s rule _n __ right__ Numbers in

parentheses indicate a power of ten_

Example ______ Composite integration formulas_ where the domain of integration _a_ b_

is divided into N subintervals of width

_xj xj _ xj___ j __ __ _ _ _ _N_

are not needed in _nite element applications_ except_ perhaps_ for postprocessing_ How_

ever_ let us do an example to illustrate the convergence of a Gaussian quadrature formula_

Thus_ consider

I Z b

f_x_dx

where

Ij Z xj

xj__

f_x_dx_

The linear mapping

x xj__

_ _ _

_ xj

_ _ _

transforms _xj___ xj _ to ____ __ and

_xj

_ Z _

f_xj__

_ _ _

_ xj

_ _ _

_d__

Approximating Ij by Gauss quadrature gives

Ij _

_xj

Wif_xj__

_ _ _i

_ xj

_ _ _i

We_ll approximate ______ using composite two_point Gauss quadrature_ thus_

_xj

_e__xj_____xj___p_ _

_ e__xj_____xj___p_ _

Numerical Integration

where xj____ _xj _ xj______ Assuming a uniform partition with _xj __N_ j

__ __ _ _ _ _N_ the composite two_point Gauss rule becomes

I _

_e__xj_________Np_ _

_ e__xj_________Np_ _

The composite Simpson_s rule_

I _

__ _

N__

Xi____

e_xj _ _

N__

Xi____

e_xj _ e___

on N__ subintervals of width __x has an advantage relative to the composite Gauss rule

since the function evaluations at the even_indexed points combine_

The number of function evaluations and errors when ______ is solved by the compos_

ite two_point Gauss and Simpson_s rules are recorded in Table _____ We can see that

both quadrature rules are converging as O___N__ ____ Chapter ___ The computations

were done in single precision arithmetic as opposed to those appearing in Table _____

which were done in double precision_ With single precision_ round_o_ error dominates the

computation as N increases beyond _ and further reductions of the error are impossible_

With function evaluations de_ned as the number of times that the exponential is evalu_

ated_ errors for the same number of function evaluations are comparable for Gauss and

Simpson_s rule quadrature_ As noted earlier_ this is due to the combination of function

evaluations at the ends of even subintervals_ Discontinuous solution derivatives at inter_

element boundaries would prevent such a combination with _nite element applications_

N Gauss Rules Simpson_s Rule

Fn_ Eval_ Abs_ Error Fn_ Eval_ Abs_ Error

_ _______ _ _ ______ __

_ ______ __ _ _______ _

_ _ _______ _ _ _______ __

_ __ _____ __ __ ____ ___

Table _____ Comparison of composite two_point Gauss and Simpson_s rule approxima_

tions for Example _____ The absolute error is the magnitude of the di_erence between

the exact and computational result_ The number of times that the exponential function

is evaluated is used as a measure of computational e_ort_

As we may guess_ estimates of errors for Gauss quadrature use the properties of

Legendre polynomials _cf_ Section _____ Here is a typical result_

____ One_Dimensional Quadrature _

Theorem ______ Let f___ _ C_n____ ___ then the quadrature rule ______ is exact to order

_n _ _ if _i_ i __ __ _ _ _ _ n_ are the roots of Pn____ the nthdegree Legendre polynomial_

and the corresponding Christo_el weights satisfy

P_n

__i_ Z _

Pn___

_ _ _i

d__ i __ __ _ _ _ _ n_ _____a_

Additionally_ there exists a point _ ____ __ such that

f__n _ _

_n_ Z _

__ _ _i__d__ _____b_

Proof_ cf_ ___ Sections ____ _

Example ______ Using the entries in Table ____ and _____b__ the discretization error

of the two_point _n __ Gauss quadrature rule is

fiv_ _

_ Z _

__ _

____ _

__d_

fiv_ _

___

_ _ ____ ___

Problems

__ Calculate the weights W_ and W_ and the evaluation points __ and __ so that the

two_point Gauss quadrature rule

Z _

f_x_ _ W_f____ _W_f____

is exact to as high an order as possible_ This should be done by a direct calculation

without using the properties of Legendre polynomials_

__ Lacking the precise information of Theorem _____ we may infer that the error in

the two_point Gauss quadrature rule is proportional to the fourth derivative of f___

since cubic polynomials are integrated exactly_ Thus_

E Cfiv_ __ _ ____ ___

We can determine the error coe_cient C by evaluating the formula for any function

f_x_ whose fourth derivative does not depend on the location of the unknown point

_ In particular_ any quartic polynomial has a constant fourth derivative_ hence_

the value of is irrelevant_ Select an appropriate quartic polynomial and show that

C _____ as in Example ____

_ Numerical Integration

___ Multi_Dimensional Quadrature

Integration on square elements usually relies on tensor products of the one_dimensional

formulas illustrated in Section ___ Thus_ the application of ______ to a two_dimensional

integral on a canonical ____ __ _ ____ __ square element yields the approximation

I Z _

__ Z _

f___ __d_d_ _ Z _

Wif__i_ __d_

Wi Z _

f__i_ __d_

and

I Z _

__ Z _

f___ __d_d_ _

WiWjf__i_ _j__ ______

Error estimates follow the one_dimensional analysis_

Tensor_product formulas are not optimal in the sense of using the fewest function

evaluations for a given order_ Exact integration of a quintic polynomial by ______ would

require n _ or a total of _ points_ A complete quintic polynomial in two dimensions

has __ monomial terms_ thus_ a direct _non_tensor_product_ formula of the form

I Z _

__ Z _

f___ __d_d_ _

Wif__i_ _i_

could be made exact with only _ points_ The __ coe_cients Wi_ _i_ _i_ i __ __ _ _ _ _ __

could potentially be determined to exactly integrate all of the monomial terms_

Non_tensor_product formulas are complicated to derive and are not known to very high

orders_ Orthogonal polynomials_ as described in Section ___ are unknown in two and

three dimensions_ Quadrature rules are generally derived by a method of undetermined

coe_cients_ We_ll illustrate this approach by considering an integral on a canonical right

__ triangle

I ZZ

f___ __d_d_

Wif__i_ _i_ _ E_ ______

Example ______ Consider the one_point quadrature rule

f___ __d_d_ W_f____ ___ _ E_ ______

Since there are three unknowns W__ ___ and ___ we expect ______ to be exact for any linear

polynomial_ Integration is a linear operator_ hence_ it su_ces to ensure that ______ is

exact for the monomials __ __ and __ Thus_

____ Multi_Dimensional Quadrature _

_ If f___ __ __

Z _

_ Z ___

___d_d_

W__

_ If f___ __ __

Z _

_ Z ___

___d_d_

W____

_ If f___ __ __

Z _

_ Z ___

___d_d_

W____

The solution of this system isW_ ___ and __ __ ____ thus_ the one_point quadrature

rule is

f___ __d_d_

_ _ E_ _____

As expected_ the optimal evaluation point is the centroid of the triangle_

A bound on the error E may be obtained by expanding f___ __ in a Taylor_s series

about some convenient point ____ ___ _ __ to obtain

f___ __ p____ __ _ R____ __ _____a_

where

p____ __ f____ ___ _ ___ _ ___

_ __ _ ___

_f____ ___ _____b_

and

R____ __

___ _ ___

_ __ _ ___

__f___ ___ ___ __ _ ___ _____c_

Integrating _____a_ using _____

E ZZ

_p____ __ _ R____ ___d_d_ _

_p__

_ _ R__

___

Since _____ is exact for linear polynomials

E ZZ

R____ __d_d_ _

R__

Not being too precise_ we take an absolute value of the above expression to obtain

jEj _ ZZ

jR____ __jd_d_ _

_jR__

_j_

__ Numerical Integration

For the canonical element_ j_ _ __j _ _ and j_ _ __j _ __ hence_

jR____ __j _ _ max

j_j__ jjD_fjj___

where

jjfjj___ max

____ ___ jf___ __j_

Since the area of __ is ____

jEj _ _ max

j_j__ jjD_fjj____ _____

Errors for other quadrature formulas follow the same derivation ____ Section _____

Two_dimensional integrals on triangles are conveniently expressed in terms of trian_

gular coordinates as

f_x_ y_dxdy Ae

Wif_ i

_ i

_ _ E ______

where _ i

_ i

_ are the triangular coordinates of evaluation point i and Ae is the area of

triangle e_ Symmetric quadrature formulas for triangles have appeared in several places_

Hammer et al_ ___ developed formulas on triangles_ tetrahedra_ and cones_ Dunavant __

presents formulas on triangles which are exact to order ___ however_ some formulas have

evaluation points that are outside of the triangle_ Sylvester ____ developed tensor_product

formulas for triangles_ We have listed some quadrature rules in Table ____ that also

appear in Dunavant ___ Strang and Fix ____ and Zienkiewicz _____ A multiplication factor

M indicates the number of permutations associated with an evaluation point having a

weight Wi_ The factor M _ is associated with an evaluation point at the triangle_s

centroid _____ ____ _____ M _ indicates a point on a median line_ and M indicates

an arbitrary point in the interior_ The factor p indicates the order of the quadrature rule_

thus_ E O_hp___ where h is the maximum edge length of the triangle_

Example ______ Using the data in Table ____ with _______ the three_point quadrature

rule on the canonical triangle is

f___ __d_d_

_f_____ ___ ___ _ f____ ___ ____ _ f____ ____ ____ _ E_

The multiplicative factor of __ arises because the area of the canonical element is ___ and

all of the weights are ____ The quadrature rule can be written in terms of the canonical

variables by setting _ _ and _ _ _cf_ _____ and ________ The discretization error

associated with this quadrature rule is O_h___

____ Multi_Dimensional Quadrature __

n Wi i

_ i

M p

_ _________________ _________________ _________________ _

_________________ _

_ _________________ ___ ____ _

____ _

_________________ _________________ _________________ _

_________________ _

_________________ ________________ _________________

_________________ _

_______________ ______________ ________________

________________ _

________________ ________________ ____________

____________ _

_ _________________ _________________ _________________ _

_________________ _

_______________ _______________ ______________

______________ _

_______________ _________________ _____________

_____________ _

__ ______________ _______________ ______________

______________ _

______________ ______________ ______________

______________ _

_______________ ______________ ________________

____________

__ ____________ _________________ _________________ _

_________________ _

______________ ______________ _____________

_____________ _

_______________ ______________ _______________

_______________ _

________________ ____________ _____________

_____________

Table _____ Weights and evaluation points for integration on triangles ___

__ Numerical Integration

Quadrature rules on tetrahedra have the form

ZZZ

f_x_ y_ z_dxdydz Ve

Wif_ i

_ i

_ _ E ______

where Ve is the volume of Element e and _ i

_ i

_ are the tetrahedral coordinates of

evaluation point i_ Quadrature rules are presented by Jinyun ___ for methods to order

six and by Keast ___ for methods to order eight_ Multiplicative factors are such that

M _ for an evaluation point at the centroid ____ ___ ___ ____ M for points on

the median line through the centroid and one vertex_ M for points on a line between

opposite midsides_ M __ for points in the plane containing an edge an and opposite

midside_ and M _ for points in the interior _Figure ______

n Wi i

_ _ __ _ M p

_ _________________ _________________ _________________ _

_________________ _________________ _

_________________ ____________ _______________ _

_______________ _______________

_ __________________ _________________ _________________ _

_________________ _________________ _

________________ _________________ ____

____ ____

__ _________________ _________________ _________________

_________________ _________________ _

________________ ______________ _______________

_______________ _______________

________________ _____________ _____________

_______________ _______________

__ ________________ _________________ _________________ _

_________________ _________________ _

_____________ _________________ _________________

_________________ _________________

_____________ _________________ _________________

_________________ _________________

_____________ ____________ ____________

_________ _________

Table _____ Weights and evaluation points for integration on tetrahedra ___ ___

____ Multi_Dimensional Quadrature __

___________

P C

124

Figure _____ Some symmetries associated with the tetrahedral quadrature rules of Table

_____ An evaluation point with M _ is at the centroid _C__ one with M is on a

line through a vertex and the centroid _e_g__ line _ _ P_____ one with M is on a line

between two midsides _e_g__ line Q__ _ Q____ and one with M __ is in a plane through

two vertices and an opposite midside _e_g__ plane _ _ _ Q___

Problems

__ Derive a three_point Gauss quadrature rule on the canonical right __ triangle

that is accurate to order two_ In order to simplify the derivation_ use symmetry

arguments to conclude that the three points have the same weight and that they

are symmetrically disposed on the medians of the triangle_ Show that there are

two possible formulas_ the one given in Table ____ and another one_ Find both

formulas_

__ Show that the mapping

_ _ u

_ _

__ _ u___ _ v_

transforms the integral ______ from the triangle __ to one on the square __ _

u_ v _ __ Find the resulting integral and show how to approximate it using a

tensor_product formula_

_ Numerical Integration

Bibliography

___ M_ Abromowitz and I_A_ Stegun_ Handbook of Mathematical Functions_ volume __

of Applied Mathematics Series_ National Bureau of Standards_ Gathersburg_ ___

___ S_C_ Brenner and L_R_ Scott_ The Mathematical Theory of Finite Element Methods_

Springer_Verlag_ New York_ ____

___ R_L_ Burden and J_D_ Faires_ Numerical Analysis_ PWS_Kent_ Boston_ _fth edition_

_____

__ D_A_ Dunavant_ High degree e_cient symmetrical Gaussian quadrature rules for the

triangle_ International Journal of Numerical Methods in Engineering_ ____________

_____

___ P_C_ Hammer_ O_P_ Marlowe_ and A_H_ Stroud_ Numerical integration over simplexes

and cones_ Mathematical Tables and other Aids to Computation_ ___________ ____

__ E_ Isaacson and H_B_ Keller_ Analysis of Numerical Methods_ John Wiley and Sons_

New York_ ___

___ Y_ Jinyun_ Symmetric Gaussian quadrature formulae for tetrahedronal regions_

Computer Methods in Applied Mechanics and Engineering_ _________ ____

___ P_ Keast_ Moderate_degree tetrahedral quadrature formulas_ Computer Methods in

Applied Mechanics and Engineering_ __________ ____

___ G_ Strang and G_ Fix_ Analysis of the Finite Element Method_ Prentice_Hall_ En_

glewood Cli_s_ _____

____ P_ Sylvester_ Symmetric quadrature formulae for simplexes_ Mathematics of Com

putation_ _________ _____

____ R_ Wait and A_R_ Mitchell_ The Finite Element Analysis and Applications_ John

Wiley and Sons_ Chichester_ _____

_ Numerical Integration

____ O_C_ Zienkiewicz_ The Finite Element Method_ McGraw_Hill_ New York_ third

edition_ _____

Chapter _

Пресс-релиз популярных книг

Numerical Integration

Популярные книги

Популярные статьи

Навигация