Numerical Methods and Optimization: Theory and Practice for Engineers (Springer Optimization and Its Applications, 187)

Preface
Acknowledgments
Contents
Nomenclature
1 Interpolation and Approximation
	1.1 Introduction
	1.2 Approximation of a Function by Another Function
		1.2.1 Approximation Functions
		1.2.2 Polynomial Approximation
			1.2.2.1 Interpolation Polynomial of Degree n
			1.2.2.2 Least Squares Polynomial
			1.2.2.3 Minimax Polynomial
			1.2.2.4 Series Expansion
			1.2.2.5 Calculation of Polynomial Pn(x)
	1.3 Determination of Interpolation Polynomials
		1.3.1 Calculation of the Interpolation Polynomial
		1.3.2 Newton Interpolation Polynomial
		1.3.3 Lagrange Interpolation Polynomial
		1.3.4 Polynomial Interpolation with Regularly Spaced Points
			1.3.4.1 Forward Differences
			1.3.4.2 Backward Differences
			1.3.4.3 Central Differences
		1.3.5 Hermite Polynomials
		1.3.6 Chebyshev Polynomials and Irregularly Spaced Points
			1.3.6.1 Minimization of the Maximum Error
			1.3.6.2 Chebyshev Economization
			1.3.6.3 Runge Phenomenon
		1.3.7 Interpolation by Cubic Hermite Polynomial
		1.3.8 Interpolation by Spline Functions
		1.3.9 Interpolation by Parametric Splines
	1.4 Bézier Curves
	1.5 Discussion and Conclusion
	1.6 Exercise Set
2 Numerical Integration
	2.1 Introduction
	2.2 Newton and Cotes Closed Integration Formulas
		2.2.1 Global Integration on Interval [a,b]
		2.2.2 Integration on Subintervals
	2.3 Open Newton and Cotes Integration Formulas
	2.4 Conclusions on Newton and Cotes Integration Formulas
	2.5 Repeated Integration by Dichotomy and Romberg's Integration
	2.6 Numerical Integration with Irregularly Spaced Points
		2.6.1 Reminder on Orthogonal Polynomials
		2.6.2 Gauss–Legendre Quadrature
		2.6.3 Gauss–Laguerre Quadrature
		2.6.4 Gauss–Chebyshev Quadrature
		2.6.5 Gauss–Hermite Quadrature
	2.7 Discussion and Conclusion
	2.8 Exercise Set
3 Equation Solving by Iterative Methods
	3.1 Introduction
	3.2 Graeffe's Method
	3.3 Bernoulli's Method
	3.4 Bairstow's Method
	3.5 Existence of a Root of a Function
	3.6 Bisection and Regula Falsi Methods
		3.6.1 Bisection Method
		3.6.2 Regula Falsi Method
	3.7 Method of Successive Substitutions
	3.8 Newton's Method and Derived Methods
		3.8.1 Newton's Method
		3.8.2 Secant Method
	3.9 Wegstein's Method
	3.10 Aitken's Method
	3.11 Homotopy Method
		3.11.1 Introduction
		3.11.2 Continuation Method
	3.12 Discussion and Conclusion
	3.13 Exercise Set
4 Numerical Operations on Matrices
	4.1 Introduction
	4.2 Reminder About Matrices
	4.3 Reminder on Vectors
	4.4 Linear Transformations and Subspaces
		4.4.1 Gershgorin Theorem
		4.4.2 Cayley–Hamilton Theorem and Consequences
		4.4.3 Power Method
	4.5 Similar Matrices and Matrix Polynomials
	4.6 Symmetric Matrices and Hermitian Matrices
	4.7 Reduction of Matrices Under a Simple Form
	4.8 Rutishauser's LR Method
	4.9 Householder's Method
	4.10 Francis's QR Method
		4.10.0.1 QR Factorization by Gram–Schmidt
		4.10.0.2 QR Householder's Factorization
		4.10.0.3 QR Factorization by Rotation Matrices
		4.10.0.4 Application of QR Factorization
	4.11 Discussion and Conclusion
	4.12 Exercise Set
5 Numerical Solution of Systems of Algebraic Equations
	5.1 Introduction
	5.2 Solution of Linear Triangular Systems
	5.3 Solution of Linear Systems: Gauss Elimination Method
	5.4 Calculation of a Matrix Determinant
	5.5 Gauss–Jordan Algorithm
	5.6 normalnormalLDLT Factorization
	5.7 Cholesky's Decomposition
	5.8 Singular Value Decomposition (SVD)
	5.9 Least Squares Method for Linear Overdetermined Systems
	5.10 Iterative Solution of Large Linear Systems (Jacobi andGauss–Seidel)
	5.11 Solution of Tridiagonal Linear Systems of Equations
	5.12 Solution of Nonlinear Systems: Newton–Raphson Method
	5.13 Solution of Nonlinear Systems by Optimization
	5.14 Discussion and Conclusion
	5.15 Exercise Set
6 Numerical Integration of Ordinary Differential Equations
	6.1 Introduction
		6.1.1 Linear and Nonlinear Ordinary Differential Equations
		6.1.2 Uniqueness of the Solution
	6.2 Initial Value Problems
		6.2.1 One-Step Methods
			6.2.1.1 Euler's Method
			6.2.1.2 A Few Ideas of Numerical Calculation
			6.2.1.3 Runge–Kutta Methods
			6.2.1.4 Semi-Implicit and Implicit Runge–Kutta Schemes
			6.2.1.5 Variable-Step Runge–Kutta–Fehlberg Method
		6.2.2 Multi-Step Methods
		6.2.3 Open Integration Formulas
			6.2.3.1 Closed Integration Formulas
			6.2.3.2 Predictor–Corrector Methods
			6.2.3.3 Backward Differentiation Methods (BDF)
	6.3 Stability of Numerical Integration Methods
	6.4 Stiff Systems
	6.5 Differential–Algebraic Systems
	6.6 Ordinary Differential Equations with Boundary Conditions
	6.7 Discussion and Conclusion
	6.8 Exercise Set
7 Numerical Integration of Partial Differential Equations
	7.1 Introduction
	7.2 Some Examples of Physical Systems
		7.2.1 Heat Transfer by Conduction
		7.2.2 Mass Transfer by Diffusion
		7.2.3 Wave Equation
		7.2.4 Laplace's Equation
	7.3 Properties of Partial Differential Equations
		7.3.1 Generalities
		7.3.2 Well-Posed Problem
		7.3.3 Classification
		7.3.4 Characterization of the Solutions
	7.4 Method of Characteristics
		7.4.1 Linear First Order Partial Differential Equation
		7.4.2 Nonlinear First Order Partial Differential Equation
		7.4.3 Quasi-Linear Second Order Partial Differential Equation
	7.5 Finite Difference Method
		7.5.1 Introduction
		7.5.2 Discretization
			7.5.2.1 Requirement for a Discretization Scheme
			7.5.2.2 Taylor Series Expansion
			7.5.2.3 Example of Discretization
			7.5.2.4 Different Numerical Schemes Applicable to the One-Dimensional Conductive Heat Transfer Equation
			7.5.2.5 Influence of the Boundary Conditions on Numerical Solving
			7.5.2.6 Discretization for the One-Dimensional Conductive Heat Transfer Equation in Cylindrical Geometry
			7.5.2.7 Different Numerical Schemes for the Two-Dimensional Conductive Heat Transfer Equation
	7.6 Automatic Calculation of Partial Derivatives
		7.6.1 Calculation of ( ∂u∂x )0 and ( ∂u∂x )N
		7.6.2 Calculation of ( ∂2 u∂x2 )0 and ( ∂2 u∂x2 )N
		7.6.3 Some Other Differentiation Schemes
			7.6.3.1 Four-Point Scheme
			7.6.3.2 Four-Point Upwind Scheme
			7.6.3.3 Five-Point Upwind Scheme
		7.6.4 Numerical Differentiation by Complex Numbers
	7.7 Method of Lines
		7.7.1 Case of Dirichlet Boundary Conditions
		7.7.2 Case of Boundary Neumann Conditions
		7.7.3 Application of the Method of Lines to the Simulationof a Heat Exchanger
			7.7.3.1 Co-current Heat Exchanger
			7.7.3.2 Counter-Current Heat Exchanger
	7.8 Finite Differences on an Irregular Grid
	7.9 Solution of a Partial Differential Equation by Splines
	7.10 Spectral Methods
		7.10.1 Method of Weighted Residuals
		7.10.2 Radial Basis Functions
		7.10.3 Polynomial Collocation for an Initial Value OrdinaryDifferential Equation
		7.10.4 Method of Weighted Residuals for an Ordinary Differential Equation with Boundary Conditions
		7.10.5 Method of Weighted Residuals for a Partial Differential Equation
	7.11 Moving Grid
		7.11.1 Theory
		7.11.2 Test on an Analytic Function
		7.11.3 Implementation in a Physical Problem
		7.11.4 Short Presentation of the General Framework
		7.11.5 Application to a Liquid Phase Chromatography,Approximation in the Equilibrium Case
		7.11.6 Application to a Liquid Phase Chromatography, Rigorous Treatment for the Case with LDF
			7.11.6.1 Boundary Conditions
			7.11.6.2 PD-Equil Model
			7.11.6.3 PD-LDF Model
			7.11.6.4 Simulation of a Chromatographic Separation
	7.12 Finite Volume Method
		7.12.1 Introduction
		7.12.2 Mesh
		7.12.3 Integration on any Control Volume
		7.12.4 Account of Boundary Conditions at Left
		7.12.5 Account of Boundary Conditions at Right
		7.12.6 Case of an Interface Between Two Solids of DifferentConductivities
		7.12.7 Numerical Solving
		7.12.8 Two-Dimensional Problem
		7.12.9 Extension to Flows
		7.12.10 Conservation Applied to a Control Volume
		7.12.11 SIMPLER Algorithm
	7.13 Finite Element Method
		7.13.1 Step 1: Elements and Nodes
		7.13.2 Step 2: Functions of Polynomial Interpolation
		7.13.3 Steps 3–4: Determination of the Conductance Matrices and Nodal Flux, Determination by Assembling of the Global Conductance Matrix and the Global Equivalent Nodal Flux Vector
			7.13.3.1 Heat Transfer
			7.13.3.2 Linear Elasticity
			7.13.3.3 Heat Transfer (Following)
			7.13.3.4 Treatment of 1D Heat Transfer by Finite Elements
			7.13.3.5 Application to the Entire Domain
		7.13.4 Convergence, Compatibility, Completeness
		7.13.5 Case of Transient Systems
			7.13.5.1 Development of the Method
			7.13.5.2 One-Step Methods
			7.13.5.3 Multiple Step Methods
		7.13.6 Heat Transfer and Fluid Transport in a Tube
		7.13.7 Flow in a Porous Medium
		7.13.8 Diffusion—Chemical Reaction
		7.13.9 Fluid Mechanics
		7.13.10 Two-Dimensional Formulation
		7.13.11 Examples of 2D and 3D Simulations
			7.13.11.1 2D Simulation
			7.13.11.2 3D Simulations
	7.14 Boundary Element Method
		7.14.1 Mathematical Preliminaries
		7.14.2 Potential Problems
		7.14.3 Green's Function Method
		7.14.4 Analytical-Numerical Boundary Element Method
		7.14.5 Boundary Element Method in 2D Heat Transfer
	7.15 Discussion and Conclusion
	7.16 Exercise Set
8 Analytical Methods for Optimization
	8.1 Introduction
	8.2 Mathematical Reminder
	8.3 Introduction
	8.4 Functions of One Variable
		8.4.1 Infinite Interval
		8.4.2 Finite Interval
		8.4.3 Presence of Discontinuities
	8.5 Functions of Several Variables
		8.5.1 Infinite Interval
		8.5.2 Finite Interval
		8.5.3 Presence of Discontinuities
	8.6 Function Subject to Equality Constraints
		8.6.1 Jacobi's Method
		8.6.2 Lagrange Multipliers
		8.6.3 Signification of Lagrange Multipliers
		8.6.4 Conditions of Minimum
		8.6.5 Conditions of Minimum by the Projected Gradient in the Case of Equality Constraints
	8.7 Function Subject to Inequality Constraints
		8.7.1 Use of Slack Variables
		8.7.2 Karush–Kuhn–Tucker (KKT) Parameters
		8.7.3 Conditions of Minimum by the Projected Gradient in the Case of Inequality Constraints
	8.8 Function Subject to Equality and Inequality Constraints
		8.8.1 Setting of the Problem
		8.8.2 Lagrange Duality
	8.9 Sensitivity Analysis
	8.10 Discussion and Conclusion
	8.11 Exercise Set
9 Numerical Methods of Optimization
	9.1 Introduction
	9.2 Functions of One Variable
		9.2.1 Bisection Method
		9.2.2 Newton's Method
		9.2.3 Fibonacci's Method
	9.3 Functions of Several Variables
	9.4 Methods of Direct Search
		9.4.1 Simple One Variable Search
		9.4.2 Simplex Method
		9.4.3 Acceleration Methods
		9.4.4 Nelder–Mead Simplex
		9.4.5 Box Complex
		9.4.6 Genetic Algorithm
	9.5 Gradient Methods
		9.5.1 Case of a Quadratic Function
		9.5.2 Case of a Non-quadratic Function
		9.5.3 Method of Steepest Descent
		9.5.4 Search in a Given Direction normalnormals
			9.5.4.1 Algorithm of Bracketing–Shrinkage
			9.5.4.2 Wolfe Algorithm
			9.5.4.3 Algorithm of Cubic Approximation
			9.5.4.4 Algorithm of the Golden Section
		9.5.5 Conjugate Gradient Method
		9.5.6 Newton–Raphson Method
		9.5.7 Quasi-Newton Method
		9.5.8 Methods for the Sums of Squares
		9.5.9 Gauss–Newton Method
		9.5.10 Levenberg–Marquardt Method
			9.5.10.1 Case of Any Function
			9.5.10.2 Case of a Sum of Squares
		9.5.11 Quasi-Newton Approximation
		9.5.12 Systems of Nonlinear Equations
	9.6 Discussion and Conclusion
	9.7 Exercise Set
10 Linear Programming
	10.1 Introduction
	10.2 Formulation of the Problem Based on Examples
		10.2.1 Use of Slack Variables
		10.2.2 Use of Slack and Artificial Variables
		10.2.3 Conditions of Optimality
	10.3 Solving the Problem: Simplex Tableau
		10.3.1 Geometric Interpretation on Example 10.1
			10.3.1.1 Minimization of f
			10.3.1.2 Maximization of f
			10.3.1.3 Simplex Tableau
		10.3.2 Simplex Tableau with Slack and Artificial Variables
	10.4 Theoretical Solution
	10.5 Case of Simultaneous Inequality and Equality Constraints
	10.6 Duality
		10.6.1 Example of Duality
		10.6.2 Demonstration of the Duality Theorem
		10.6.3 Demonstration of the Duality Theorem Basedon the Lagrangian
	10.7 Interior Point Methods
		10.7.1 Karmarkar Projection Method
			10.7.1.1 Passage from the Standard Form to Karmarkar's Form
			10.7.1.2 Karmarkar's Algorithm
		10.7.2 Affine Transformation
			10.7.2.1 Consequences of the Affine Transformation
			10.7.2.2 Algorithm of Affine Transformation
	10.8 Discussion and Conclusion
	10.9 Exercise Set
11 Quadratic Programming and Nonlinear Optimization
	11.1 Introduction
	11.2 Quadratic Optimization, Karush–Kuhn–Tucker Conditionsand Solution by the Simplex
		11.2.1 First Presentation
		11.2.2 Second Presentation
		11.2.3 Solution Under the Form of a Simplex Problem
	11.3 Quadratic Optimization, Barrier Method
	11.4 Nonlinear Optimization by Successive Quadratic Programming
		11.4.1 Introduction
		11.4.2 Notion of Feasible Region and Tangent Cone
		11.4.3 Successive Quadratic Programming (SQP)
		11.4.4 Specificities and Difficulties of the SQP Problem
			11.4.4.1 Merit Functions
			11.4.4.2 Filter Methods
			11.4.4.3 Reduced Hessian Methods
	11.5 Discussion and Conclusion
	11.6 Exercise Set
12 Dynamic Optimization
	12.1 Introduction
	12.2 Problem Statement
	12.3 Variational Method in the Mathematical Framework
		12.3.1 Variation of the Criterion
		12.3.2 Variational Problem Without Constraints:Fixed Boundaries
		12.3.3 Variational Problem with Constraints: General Case
		12.3.4 Hamilton–Jacobi Equation
	12.4 Dynamic Optimization in Continuous Time
		12.4.1 Variational Methods
		12.4.2 Variation of the Criterion
		12.4.3 Euler Conditions
		12.4.4 Weierstrass Condition and Hamiltonian Maximization
		12.4.5 Hamilton–Jacobi Conditions and Equation
			12.4.5.1 Case with Constraints on Control and State Variables
			12.4.5.2 Case with Terminal Constraints
		12.4.6 Maximum Principle
		12.4.7 Singular Arcs
		12.4.8 Numerical Issues
	12.5 Dynamic Programming (Discrete Time)
		12.5.1 Classical Dynamic Programming
		12.5.2 Hamilton–Jacobi–Bellman Equation
	12.6 Conclusion
	12.7 Exercise Set
Index