[PDF] Numerical Methods IIT Kanpur. SAUMYEN GUHA. Numerical.

View - Download Numerical Methods

Previous PDF

Next PDF

1

Professor

Department of Civil Engineering

IIT Kanpur

SAUMYEN GUHA

Numerical

Methods

FOR ENGINEERING AND SCIENCE

Professor

Department of Civil Engineering

IIT Kanpur

RAJESH SRIVASTAVA‹2[IRUG8QLYHUVLW\3UHVV

Prefaceiii

1. Introduction 1

2. System of Linear Equations 19

3. Solution of Nonlinear Equations 103

4. Approximations of Functions 162

5. Numerical Differentiation and Integration 252

6. Ordinary Differential Equations 315

7. Partial Differential Equations 429

8. Advanced Topics 492

References 588

Index589

Prefaceiii

1. INTRODUCTION 1

1.1 Introduction1

1.2 Errors5

1.3 Error Propagation and Condition Number of a Problem9

1.4 Condition Number of an Algorithm13

2. SYSTEM OF LINEAR EQUATIONS19

2.1 Introduction19

2.1.1 Properties of Matrices20

2.1.2 Eigenvalues and Eigenvectors27

2.1.3 Matrix Norms31

2.2 Solution of Linear Systems35

2.2.1 Direct Methods35

2.2.2 Iterative Methods63

2.2.3 Scaling and Equilibration74

2.3 Computation of Eigenvalues82

2.3.1 Power Method82

2.3.2 Inverse Power Method85

2.3.3 Inverse Power Method with Shift87

2.3.4 Faddeev Leverrier Method87

2.3.5 Similarity Transformation89

3. SOLUTION OF NONLINEAR EQUATIONS103

3.1 Introduction103

3.1.1 Numerical Techniques104

3.2 Bracketing Methods106

3.2.1 Bisection Method (Interval Halving)107

3.2.2 Linear Interpolation Method (Regula Falsi or False Position)109

3.2.3 Other Possible Methods113

3.2.4 Remarks114

3.3 Open Methods116

3.3.1 Fixed-point Iteration (Successive Substitution or One-point Iteration)

117

3.3.2 Newton-Raphson Method (or Tangent Method)120

3.3.3 Secant Method126

3.3.4 Muller"s Method128

3.3.5 Steffensen"s Method131

3.3.6 Aitken Extrapolation132

3.4 Complex Roots and Multiple Roots136

3.4.1 Bairstow Method138

3.4.2 Multiple Roots143

3.5 Design of Methods of Arbitrary Order146

3.6 Introduction to System of Nonlinear Equations149

3.7 Solution Methods151

3.7.1 Fixed-point Iteration152

3.7.2 Newton Method154

3.7.3 Secant Method156

4. APPROXIMATIONS OF FUNCTIONS162

4.1 Introduction162

4.2 Approximation of Functions163

4.2.1 Taylor"s Series167

4.2.2 Method of Least Squares170

4.3 Geometric Interpretation of Functions and Orthogonal Polynomials173

4.3.1 Legendre Polynomials179

4.3.2 Minimax Approximation183

4.3.3 Tchebycheff Polynomials183

4.4 Approximation of Data193

4.4.1 Interpolation193

4.4.2 Gram"s Polynomials202

4.4.3 Unevenly Spaced Grid Points205

4.5 Spline Interpolation211

4.5.1 Linear Splines211

4.5.2 Quadratic Splines212

4.5.3 Cubic Splines215

4.5.4 Hermite Interpolation220

4.6 Regression224

4.6.1 Least-squares Regression225

4.6.2 Non-linear Regression231

4.7 Periodic Functions239

4.7.1 Continuous Case 243

4.7.2 Discrete Case 247

5. NUMERICAL DIFFERENTIATION AND INTEGRATION252

5.1 Introduction252

5.2 Numerical Differentiation253

5.2.1 Evenly Spaced Grid Points253

5.2.2 Unevenly Spaced Grid Points266

5.2.3 Amplitude and Phase Error267

5.3 Numerical Integration275

5.3.1 Discrete Case275

5.3.2 Continuous Case292

5.3.3 Improper Integrals306

6. ORDINARY DIFFERENTIAL EQUATIONS315

6.1 Introduction315

6.2 Derivation of Methods for IVPs321

6.2.1 Multi-Step Methods322

6.2.2 Backward Difference Formulae (BDF)330

6.2.3 Runge-Kutta Methods333

6.3 Error Analysis of Methods for IVPs342

6.3.1 Truncation Error342

6.3.2 Stability Analysis350

6.3.3 Phase Error369

6.4 Applications of Various Methods376

6.4.1 Startup of Non-self Starting Methods377

6.4.2 Combination of Methods: Predictor Corrector Schemes385

6.5 Higher-order and System of IVPs388

6.5.1 Stability of a System of IVPs and Stiff Systems402

6.6 Boundary Value Problems416

6.6.1 Shooting Method417

6.6.2 Direct Method420

7. PARTIAL DIFFERENTIAL EQUATIONS429

7.1 Introduction429

7.2 Characteristics of PDE432

7.3 Numerical Methods for PDEs437

7.3.1 Diffusion and Advective-Diffusion Equation437

7.3.2 Laplace Equation455

7.3.3 First Order Wave Equation466

7.3.4 Second Order Wave Equation470

7.3.5 Diffusion Equation in 2-D474

7.4 Stability Analysis481

7.4.1 Von Neumann Stability Analysis485

8. ADVANCED TOPICS492

8.1 Introduction492

8.2 Approximation using Rational Functions493

8.2.1 Interpolation495

8.2.2 Regression498

8.2.3 Approximation of a Given Function500

8.3 B-splines505

8.3.1 Cubic Spline510

8.4 Multivariate Functions513

8.4.1 Interpolation513

8.4.2 Integration521

8.5 Fast Fourier Transform528

8.5.1 Discrete Fourier Transform533

8.6 Uncertainty in Parameters Estimated from Regression539

8.7 Method of Weighted Residuals550

8.7.1 Point Collocation (or Collocation) Method553

8.7.2 Subdomain Collocation (or Subdomain) Method554

8.7.3 Least Squares Method554

8.7.4 Method of Moments554

8.7.5 Galerkin Method555

8.7.6 Finite Element Method561

8.8 Spatial Discretization on Irregular Boundary567

8.8.1 Grid Layout567

8.8.2 Finite Difference Approximation on a Non-uniform Grid570

8.8.3 Second and Third Type Boundary Conditions on Irregular Boundary574

8.9 Multi-grid Method576

8.9.1 Direct Injection582

8.9.2 Full Weighting582

References588

Index589

1 Many real world problems, from computing the income tax to the design of∑ the nuclear bomb, depend on simulation and prediction through complex mathem∑atical models and a large amount of data. Mathematical modelling utilizes phys∑ical laws to develop equations representing system behaviour. In some cases, a phenomenon may be very difficult or hazardous or expensive to model experimentally but may yield to reasonably accurate mathematical modelling. The mathematical model representing a physical system may be solved usin∑g experimental, analytical, and numerical methods or a combination of them∑. However, rarely does one obtain an exact solution because of the approximations introduced in the process at various stages. The mathematical model may, knowingly or inadvertently, involve some simplifying assumptions; the experimental procedure may have limitations∑ in the accuracy of measurement; the analytical solution may involve irrational ∑numbers or infinite series; and the numerical solution invariably contains error∑s due to limited precision of computers. The objective, therefore, is to obtain a reasonably accurate solution with optimum use of resources. The desired accuracy and efficiency would, of course, depend on the physical problem and must take into account both the nature of the p∑roblem and the intended use of the answer. In experimental methods, we reproduce the system using full-size or scal∑ed

models and obtain the solution by measuring and (if needed) scaling th∑e relevant‹2[IRUG8QLYHUVLW\3UHVV

variables or parameters. There is generally an excellent representation of the physical system but the process is typically slow and often expensive. Scaling ef fects are sometimes non-linear and complicated that need to be properly accounted for in the interpretation of results. Measurement accuracy, cost, and scalability often restrict the application of such models. Analytical solutions, if possible, are very useful for understanding the response of the system. However, they are often limited to very simple geometry and finding a solution can often be extremely difficult. Sometimes, the analytical solution may involve an infinite series, which may require summation of a large numbe r of terms for desired accuracy and may be time consuming to evaluate. More often than not, it is impossible to obtain a closed form solution o f the complex mathematical models. Instead, one relies on a large number of numerical calculations to obtain an approximation to the solution of the model. Th e branch of mathematics that deals with transformation of the mathematical problems to numerical calculations is often termed as Numerical Methods. Essentially, a numerical method transforms a mathematical problem into a set of computations involving addition, subtraction, multiplication, and divisi on. Mathematical analysis that helps determine the proximity of the approxim ate solution, obtained using a numerical method, to the exact solution is te rmed as

Numerical Analysis.

Numerical methods use numbers to simulate mathematical processes and hen ce, may be used to solve extremely complex systems. The solution is often qu ick and is easily adapted for parametric sensitivity studies. With the rapid advancement of computers, numerical methods have become an invaluable engineering tool. Some situations in which numerical methods would be the method of choice are: integration of a function for which either the integral cannot be expres sed as analytical expressions or it is too cumbersome and time consuming to eva luate, solution of differential equations for complicated geometry, and/or boundary conditions, large systems of equations, repeated solution of the same system under changing conditions, etc. Moreover, as an engineer, one is likely to come across many software packages to perform numerical simulations, the use of whic h would probably be the most efficient means for solving engineering problems. One may be tempted to use these packages as black-boxes but a meaningful use of these would require thorough understanding of the underlying numerical methods Sometimes, an engineer may have to develop his or her own software for n umerical simulations due to the prohibitive cost, lack of flexibility, and poor computational efficiency of available packages. Even when the available packages are s uitable for a particular problem, a working knowledge of numerical methods is va luable in

case any difficulties or unreasonable results are encountered. We may also come‹2[IRUG8QLYHUVLW\3UHVV

across new mathematical models, which require a new software for solutio ns. The use of a numerical method is equally an art and a science (or shall we say, mathematics!). It is desirable to have the ability to select (and poss ibly modify) a numerical method for a specific problem. We will try to illustrate the basic concepts with an example. Let us ass ume Joker drops the wheel of Bat-mobile from the top of the Vampire State Building and Batman is looking out of the window at the 13th floor, which is 666 m below the top. As the wheel passes by the window he reports to the police. How lo ng after Joker drops the wheel, the police are going to receive the call? Transforming any practical problem into a mathematical model requires a s eries of assumptions, such as:

1. Assume the initial downward velocity to be zero (reasonable assumption).

2. Ignore all resistances due to air, wind, boundary layer around the building, etc.

(questionable).

3. Assume that the acceleration due to gravity remains constant from the to

p of the building to the ground level (reasonable).

4. Assume the time taken between viewing the object and making the call to

be zero (reasonable, don"t forget we are talking about Batman!).

5. We do not worry about what the Joker was doing at the top of the Vampire

State Building with the wheel.

Using assumptions 2 and 3, the model for the problem can be formulated a s a differential equation as follows: 2 2 dhgdt= (1.1) where h is the distance travelled in time t and g is the gravitational acceleration. Integrating this equation and using assumptions 1 and 4, we obtain an al gebraic equation as 2htg= (1.2) where t now represents the time when the police receives the call. If g is taken as

9.81 m/sec

2 , one can compute t (in sec) for h = 666 m. Now, let us try to calculate this time, which is

2 666 9.81×. After performing one multiplication and one

division, one arrives at approximately

135.77982

. Since one cannot write or store (in a computer) infinitely many digits after the decimal, we nee d to chop or round-off this number. We intend to apply a numerical method and use a computer to compute the

square root of the rounded-off number. Recall, a numerical method as well as a‹2[IRUG8QLYHUVLW\3UHVV

computer only does simple algebraic operations. How does one compute sq uare root of a number (rational or irrational) by addition, subtraction, mu ltiplication, and division? We invoke our mathematical knowledge to transform the square root problem into a language that computer can understand, namely, +, -, ×, and It is possible to generate a sequence that converges to the square root of a number. One can then get arbitrarily close to the required value by progressing further and further in the sequence. For example, to compute the square root of a nu mber a (a > 0), one can write two different iterative sequences as follows:

Sequence 1:

1n n axx (1.3)

Sequence 2:

1 1 2 nn n axxx (1.4) It is easy to see that if the sequences converge, their limits (l) will be equal to 1 .a However, the primary concern is whether they converge? One is often interested to know that before one does a few iterations and discovers t hat the sequence is not converging. For example, for any initial guess x 0 > 0, Sequence 1 oscillates between x 0 and a/x 0 and does not converge to .a

On the other hand, for Sequence 2:

For any initial guess x

0 > 0, 2 1 22
nn n n xx x a xa since, (x n - a) 2 ≥ 0. This means x n+1 ≥ a. So, the sequence is bounded.

Also, for n ≥ 2,

2 1 102
n nn n xaxxx 10 since, , and 0 n xanx ≥? >. So, the sequence is decreasing. This analysis shows that Sequence 2 is a monotonically decreasing sequence that is bounded below (Cauchy sequence) and thus convergent. For example, to find the square root of 135.77982, we start with an initial guess of the square root as x 0 = 12 (we know that the square of 12 is 144, therefore the desired root should be close to 12). Subsequent iterations (with an eight digit acc uracy) using

Eq. (1.4) result in the values x

1 = 11.657493, x 2 = 11.652461, x 3 = 11.652460, x 4 = 11.652460. Thus, the square root of 135.77982 is obtained in only 4 itera tions 1 Put x n + 1 = x n = l.‹2[IRUG8QLYHUVLW\3UHVV as 11.652460. Assuming that we have no idea about the approximate answer, we may start from a very different value, say, x 0 = 1. It would take us 10 iterations to arrive at the root. Similarly, starting from an initial guess of 100, we would again converge to the correct answer in 10 iterations. We have now seen two computational schemes, Eqs (1.3) and (1.4), for finding the square root of a number. Subsequent mathematical analysis showed that one scheme, Eq. (1.4), converges to the true solution, whereas the other o ne, Eq. (1.3), does not. The computational scheme of Eq. (1.4) that converges to the true solution can be termed as a numerical method for computing the square root of a number. The mathematical analysis conducted to determine whether the computation al scheme converges or not is called numerical analysis. Using the numerical method described above, one can solve the algebraic form of the model for the problem of Joker dropping the wheel [Eq. (1.2)]. However, Batman being a very precise person wants to know the precision of your calcula tion. So, we need to know where the errors are and how to estimate them. In any problem-solving exercise, one encounters errors in many forms and shapes. Some errors may add-up and some may cancel each other to give a net erro r in the final result. Different forms of errors can be classified as follows:

1. Error in the model or model error.

2. Error in the data or data error.

3. Truncation error.

4. Round-off error.

Let us discuss these errors with the help of the example cited in the pr evious section. Mathematical model of a physical process is more often than not a spherical cow. One can minimize assumptions and make it a cylindrical horse at best but rarely, if ever, they represent the true physical process. This is because, the physic al processes are often too complex or some of the processes cannot be chara cterized. For example, the assumptions 1 and 2 may not be valid for the problem of Joker dropping the wheel. Errors imparted in the final result due to these as sumptions or as a result of approximations in the model formulation are termed as model errors. The value of gravitational acceleration (g) was taken as 9.81 m/sec 2 . The value of g at the site may be 9.80897653879 m/sec 2 , which was approximated as

9.81 m/sec

2 . Similarly, the distance between the window and the rooftop was taken as 666 m. If one measures more accurately, it may be 665.99 m or 666.04 m. These errors in the data also lead to some error in the final result, which is known as data error.‹2[IRUG8QLYHUVLW\3UHVV Many of the processes of mathematics, such as differentiation, integrati on, and the evaluation of series, imply the use of a limit which is an infinite process. The machine has finite speed and can only do a finite number of operations i n a finite length of time. This leads to a truncation error in the process. To illustrate truncation error, let us consider the Taylor"s series expansion of a function h(t) at (t + Δt),

22 33 44

234
()()2! 3! 4!dh tdh tdh tdhht t ht tdtdt dt dtΔΔΔ+Δ = +Δ + + + +???(1.5) Using this, one can express h(t) at (t + 2Δt) and at (t - Δt) as follows:

22 33 44

234
(2 ) (2 ) (2 )(2) ()(2)2! 3! 4!dh tdh tdh tdhht t ht tdtdt dt dtΔΔΔ+Δ= + Δ + + + +??? (1.6)

22 33 44

234
()()2! 3! 4!dh t d h t d h t d hht t ht tdtdt dt dtΔΔΔ-Δ = -Δ + - + -???(1.7) Using various combinations of Eqs (1.5)-(1.7), one can approximat e the second derivative in the differential form of the model problem Eq. (1.1) in different ways: 224
22 4
2

12ht t ht ht t

dht dh dttdt+Δ - + -Δ (1.8) 2324
22 34
227

12ht t ht t ht

dhdh t dhtdttdt dt+Δ- +Δ+ (1.9) If we consider the first term on the right-hand side as the approximatio n of the second derivative, we make some error. This error is due to approximation of an infinite series by a finite number of terms or in other words, due to tr uncation of the series. Error encountered in this way is termed as truncation error. As seen from these equations, the truncation error is proportional to (Δt)quotesdbs_dbs17.pdfusesText_23

[PDF] numerical methods for scientific and engineering computation 4th edition pdf

[PDF] numerical methods for solving system of nonlinear equations

[PDF] numerical methods in civil engineering book pdf

[PDF] numerical methods journal pdf

[PDF] numerical methods practical applications

[PDF] numerical methods problems and solutions pdf

[PDF] numerical solution of partial differential equations python

[PDF] numerical techniques

[PDF] numericals on indexing in dbms

[PDF] numero de cour de cassation rabat

[PDF] numéro de sécurité sociale 13 chiffres

[PDF] numéro de sécurité sociale 15 chiffres

[PDF] numéro de sécurité sociale belgique

[PDF] numéro de sécurité sociale carte vitale

[PDF] numéro de sécurité sociale français