Advanced Numerical Methods with Matlab 2
Description
More details
Other editions
Additional editions
Persons
Bouchaib Radi is Professor of Higher Education in the Faculty of Science and Technology of Settat Hassan First University in Morocco. His work specializes in material forming processes, optimization and reliability.
Content
Preface ix
Part 1. Solving Equations 1
Chapter 1. Solving Nonlinear Equations 3
1.1 Introduction 3
1.2 Separating the roots 3
1.3 Approximating a separated root 4
1.3.1 Bisection method (or dichotomy method) 4
1.3.2 Fixed-point method 6
1.3.3 First convergence criterion 7
1.3.4 Iterative stopping criteria.8
1.3.5 Second convergence criterion (local criterion) 9
1.3.6 Newton's method (or the method of tangents) 10
1.3.7 Secant method 12
1.3.8 Regula falsi method (or false position method) 17
1.4 Order of an iterative process.19
1.5 Using Matlab 19
1.5.1 Finding the roots of polynomials 19
1.5.2 Bisection method 21
1.5.3 Newton's method 22
Chapter 2. Numerically Solving Differential Equations 25
2.1 Introduction 25
2.2 Cauchy problem and discretization 27
2.3 Euler's method 30
2.3.1 Interpretation 30
2.3.2 Convergence 30
2.4 One-step Runge-Kutta method 31
2.4.1 Second-order Runge-Kutta method 32
2.4.2 Fourth-order Runge-Kutta method 33
2.5 Multi-step Adams methods 36
2.5.1 Open Adams methods 36
2.5.2 Closed Adams formulas 39
2.6 Predictor-Corrector method.41
2.7 Using Matlab 43
Part 2. Solving PDEs 47
Chapter 3. Finite Difference Methods 49
3.1 Introduction 49
3.2 Presentation of the finite difference method 51
3.2.1 Convergence, consistency and stability 53
3.2.2 Courant-Friedrichs-Lewy condition 56
3.2.3 Von Neumann stability analysis 57
3.3 Hyperbolic equations 58
3.3.1 Key results 59
3.3.2 Numerical schemes for solving the transport equation 63
3.3.3 Wave equation 66
3.3.4 Burgers equation 68
3.4 Elliptic equations 72
3.4.1 Poisson equation 72
3.5 Parabolic equations 74
3.5.1 Heat equation 74
3.6 Using Matlab 76
Chapter 4. Finite Element Method 83
4.1 Introduction 83
4.2 One-dimensional finite element methods 83
4.3 Two-dimensional finite element methods 88
4.4 General procedure of the method 93
4.5 Finite element method for computing elastic structures 93
4.5.1 Linear elasticity 93
4.5.2 Variational formulation of the linear elasticity problem 97
4.5.3 Planar linear elasticity problems 99
4.5.4 Applying the finite element method to planar problems 101
4.5.5 Axisymmetric problems.105
4.5.6 Three-dimensional problems 107
4.6 Using Matlab 107
4.6.1 Solving Poisson's equation 108
4.6.2 Solving the heat equation.111
4.6.3 Computing structures 112
Chapter 5. Finite Volume Methods 117
5.1 Introduction 117
5.2 Finite volume method (FVM) 118
5.2.1 Conservation properties of the method 118
5.2.2 The stages of the method.119
5.2.3 Convergence 120
5.2.4 Consistency 120
5.2.5 Stability 120
5.3 Advection schemes 121
5.3.1 Two-dimensional FVM. 126
5.3.2 Convection-diffusion equation 129
5.3.3 Central differencing scheme 131
5.3.4 Upwind (decentered) scheme 133
5.3.5 Hybrid scheme 136
5.3.6 Power-law scheme 136
5.3.7 QUICK scheme 137
5.3.8 Higher-order schemes 139
5.3.9 Unsteady one-dimensional convection-diffusion Equation 140
5.3.10 Explicit scheme 142
5.3.11 Crank-Nicolson scheme.142
5.3.12 Implicit scheme 143
5.4 Using Matlab 144
Chapter 6. Meshless Methods. 147
6.1 Introduction 147
6.2 Limitations of the FEM and motivation of meshless methods 148
6.3 Examples of meshless methods148
6.3.1 Advantages of meshless methods 149
6.3.2 Disadvantages of meshless methods150
6.3.3 Comparison of the finite element method and meshless methods 151
6.4 Basis of meshless methods 151
6.4.1 Approximations 151
6.4.2 Kernel (weight) functions.152
6.4.3 Completeness 152
6.4.4 Partition of unity 152
6.5 Meshless method (EFG) 153
6.5.1 Theory 153
6.5.2 Moving Least-Squares Approximation 153
6.6 Application of the meshless method to elasticity 163
6.6.1 Formulation of static linear elasticity 163
6.6.2 Imposing essential boundary conditions 165
6.7 Numerical examples 170
6.7.1 Fixed-free beam 170
6.7.2 Compressed block 171
6.8 Using Matlab 173
Part 3. Appendices 179
Appendix 1181
Appendix 2189
Bibliography 195
Index 199
1
Solving Nonlinear Equations
1.1. Introduction
Let F: R R be a function defined on a subset D ? R. Suppose that we wish to find the roots of the equation F(x) = 0, if they exist. Most theorems that guarantee the existence of roots for equations of the form F(x) = 0 do not specify a way to construct these roots, and we are usually not capable of solving the problem analytically, except in a few special cases. Therefore, we often need to resort to numerical methods to find approximate solutions of the equation F(x) = 0 [RAD 09, BAK 76].
There are many possible numerical methods to choose from, and each has its own advantages and disadvantages (we will only present the most common methods in this chapter). Before trying to solve a problem numerically, we need to know that the solution exists and is unique [QUA 04, RAD 10]. Therefore, the process of numerically solving the equation F(x) = 0 can be divided into two parts:
- 1) First, we must show the existence of real-valued solutions and separate each solution that we wish to approximate in an interval [a, b] ? D.
- 2) Second, we must choose a numerical method to approximate the isolated roots.
1.2. Separating the roots
DEFINITION.- We say that the root of the equation F(x)= 0 is separable if there exists an interval [a, b] ? D, such that is the only root contained in [a, b].
If so, the root ? [a, b] is said to be separated or isolated. In practice, we can separate the roots of the equation F(x) = 0 either graphically (by looking for the points at which the graph of F intersects with the axis) or analytically, by applying the intermediate value theorem (see the appendix on standard results from analysis, Appendix 2).
EXAMPLE.-
- 1) The equation x3 - 6x + 2 = 0 has three real roots that are separated by the intervals [-3, -2], [0,1] and [2,3].
- 2) The equation ex sin x - 1 = 0 ? sin x = e-x has two roots that are separated by the intervals [0,1] and [3,4].
- 3) The equation x ln x - 1 = 0 has a single root in [1,2].
- 4) The equation 2x4 + 3x3 - 4x - 5 = 0 has two real roots separated by the intervals [-2, -1] and [1,2].
- 5) The equation (1+x)e1-x - 3/2 = 0 has two real roots separated by the intervals [-1,0] and [1, 2].
1.3. Approximating a separated root
In this section, we will assume that the root has already been isolated by the interval [a, b].
We will present some of the standard methods that can be used to find an approximate value for , and we will study their properties and rates of convergence. Concretely, when we speak of approximating up to ?, we mean finding an approximate value that is known to satisfy (where ? is a small real number; the smaller this ?, the more precise the algorithm).
1.3.1. Bisection method (or dichotomy method)
Suppose that is a simple separable root in [a, b] (F(a)F(b) < 0). The bisection method constructs a sequence of intervals In = [an, bn] from the initial interval [a, b], such that each In contains and has a width equal to half of the width of In - 1.
The underlying idea of the method is to construct the following three sequences (an), (bn), and (xn):
Define , and for n = 1:
- - If F(an-1)F(xn-1) < 0, define .
- - If F(an-1)F(xn-1) > 0, define .
- - If F(an-1)F(xn-1) = 0, then : this means that we have found the exact solution, hence the process is terminated.
In this way, at each iteration, we select the half-interval that contains the root . After n iterations, we have found an interval containing with width .
THEOREM.- The sequence (xn) constructed by the bisection algorithm converges to the root .
An upper bound for the error committed by approximating by xn is given by: .
REMARK.-
- 1) Similarly, the sequences (an) and(bn) converge to , and .
- 2) To guarantee a precision of ? when approximating by xn, we can simply pick n, such that: .
This method has the following properties:
- - straightforward algorithm (based on the intermediate value theorem);
- - can be applied to non-analytic functions;
- - cannot be applied to double roots;
- - cannot be applied to multiple equations;
- - very slow (to achieve high precision, we need a high number of iterations).
Owing to these limitations, we need other methods in some situations.
EXAMPLE.- Suppose that we wish to find a zero of the following function using the bisection method:
This function satisfies f(0) = -1, f(2) = 0.818595. It is continuous on [0, 2], and f(0)f(2) < 0. By the intermediate value theorem, the equation f(x) = 0 has at least one root a ? [0,2]. We can therefore use this interval to initialize the bisection method. Applying this method to f on the interval [0,2], we find:
i xi i xi 1 1.000000 7 1.109375 2 1.500000 8 1.117188 3 1.250000 9 1.113281 4 1.125000 10 1.115234 5 1.062500 11 1.114258 6 1.093750 12 1.114258An approximate value for the root of f is therefore given by x12 = 1.114258.
1.3.2. Fixed-point method
DEFINITION.- The solutions of the equation f(x) = x are said to be the fixed points of the function f.
THEOREM.- If f is continuous on [a, b] and f([a, b]) ? [a, b], then f has at least one fixed point between a and b (in other words, ? c ?] a, b[/ f(c) = c).
Suppose that ? [a, b] is an isolated root of the equation F(x) = 0. The fixed-point method defines and studies a function f such that is a fixed point of f (i.e. such that F(x) =0 ? f(x) = x).
EXAMPLE.- For example, for the function , we can define .
Now, instead of searching for as a root of F(x), we can find it as a fixed point of f(x) by taking advantage of the following property:
If the recursive sequence (xn) defined by x0 arbitrary; xn= f(xn-1), n = 1, converges, then its limit is a fixed point of the function f (see Figure 1.1).
Figure 1.1. Fixed-point method
The idea of the method is to choose a function f for the original function F, such that:
- - .
- - The sequence (xn) defined by x0 ? [a, b]; xn= f(xn-1) for n = 1 converges to .
The problem of approximating up to ? is therefore reduced to that of computing xn, such that .
REMARK.- For any given function F(x) = 0, there are an infinite number of choices of f such that F(x) = 0 is equivalent to f(x) = x (e.g. f(x) = x + ?F(x); ? ? R*) . The challenge of the fixed-point method lies in choosing f in such a way that the sequence (xn) converges, and does so as quickly as possible. There are two natural criteria for selecting the best function: convergence and rate of convergence. The choice of the initial point x0 also influences both of these criteria.
EXAMPLE.- Suppose that we wish to compute the value of . This is equivalent to finding the positive root of the function
that is, solving a nonlinear equation.
It is easy to check that is a fixed point of the function simply by noting that . Moreover, . We can therefore define the sequence x0 ? [1, 2] and xn+1 = ?(xn), and apply the mean value theorem to deduce that ?? ? [1,2], such that
Therefore,
This shows that the sequence xn converges to the root a. We need to perform 34 iterations of the fixed-point method to compute an approximate value for that is accurate to ten digits after the decimal point.
