October 29, 2014 11:19 BC: 9404 – Intro to Comp Maths 2nd Ed. Yang-Comp-Maths2014 page v
Preface
Computational mathematics is essentially the foundation of modern scien-
tific computing. Traditional ways of doing sciences consist of two major
paradigms: by theory and by experiment. With the steady increase in
computer power, there emerges a third paradigm of doing sciences: by
computer simulation. Numerical algorithms are the very essence of any
computer simulation, and computational mathematics is just the science of
developing and analyzing numerical algorithms.
The science that studies numerical algorithms is numerical analysis or
more broadly computational mathematics. Loosely speaking, numerical
algorithms and analysis should include four categories of algorithms: nu-
merical linear algebra, numerical optimization, numerical solutions of dif-
ferential equations (ODEs and PDEs) and stochastic data modelling.
Many numerical algorithms were developed well before the computer
was invented. For example, Newton’s method for finding roots of nonlinear
equations was developed in 1669, and Gauss quadrature for numerical in-
tegration was formulated in 1814. However, their true power and efficiency
have been demonstrated again and again in modern scientific computing.
Since the invention of the modern computer in the 1940s, many numerical
algorithms have been developed since the 1950s. As the speed of com-
puters increases, together with the increase in the efficiency of numerical
algorithms, a diverse range of complex and challenging problems in math-
ematics, science and engineering can nowadays be solved numerically to
very high accuracy. Numerical algorithms have become more important
than ever.
The topics of computational mathematics are broad and the related
literature is vast. It is often a daunting task for beginners to find the
right book(s) and to learn the right algorithms that are widely used in
v
,November 3, 2014 11:34 BC: 9404 – Intro to Comp Maths 2nd Ed. Yang-Comp-Maths2014 page vi
vi Introduction to Computational Mathematics
computational mathematics. Even for lecturers and educators, it is no
trivial task to decide what algorithms to teach and to provide balanced
coverage of a wide range of topics, because there are so many algorithms
to choose from.
The first edition of this book was published by World Scientific Publish-
ing in 2008 and it was well received. Many universities courses used it as
a main reference. Constructive feedbacks and helpful comments have also
been received from the readers. This second edition has incorporated all
these comments and consequently includes more algorithms and new algo-
rithms to reflect the state-of-the-art developments such as computational
intelligence and swarm intelligence.
Therefore, this new edition strives to provide extensive coverage of
efficient algorithms commonly used in computational mathematics and
modern scientific computing. It covers all the major topics including
root-finding algorithms, numerical integration, interpolation, linear algebra,
eigenvalues, numerical methods of ordinary differential equations (ODEs)
and partial differential equations (PDEs), finite difference methods, finite
element methods, finite volume methods, algorithm complexity, optimiza-
tion, mathematical programming, stochastic models such as least squares
and regression, machine learning such as neural networks and support vec-
tor machine, computational intelligence and swarm intelligence such as
cuckoo search, bat algorithm, firefly algorithm as well as particle swarm
optimization.
The book covers both traditional methods and new algorithms with
dozens of worked examples to demonstrate how these algorithms work.
Thus, this book can be used as a textbook and/or reference book, especially
suitable for undergraduates and graduates in computational mathematics,
engineering, computer science, computational intelligence, data science and
scientific computing.
Xin-She Yang
London, 2014
,October 29, 2014 11:19 BC: 9404 – Intro to Comp Maths 2nd Ed. Yang-Comp-Maths2014 page vii
Contents
Preface v
I Mathematical Foundations 1
1. Mathematical Foundations 3
1.1 The Essence of an Algorithm . . . . . . . . . . . . . . . . 3
1.2 Big-O Notations . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Differentiation and Integration . . . . . . . . . . . . . . . 6
1.4 Vector and Vector Calculus . . . . . . . . . . . . . . . . . 10
1.5 Matrices and Matrix Decomposition . . . . . . . . . . . . 15
1.6 Determinant and Inverse . . . . . . . . . . . . . . . . . . . 20
1.7 Matrix Exponential . . . . . . . . . . . . . . . . . . . . . . 24
1.8 Hermitian and Quadratic Forms . . . . . . . . . . . . . . . 26
1.9 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . 28
1.10 Definiteness of Matrices . . . . . . . . . . . . . . . . . . . 31
2. Algorithmic Complexity, Norms and Convexity 33
2.1 Computational Complexity . . . . . . . . . . . . . . . . . 33
2.2 NP-Complete Problems . . . . . . . . . . . . . . . . . . . 34
2.3 Vector and Matrix Norms . . . . . . . . . . . . . . . . . . 35
2.4 Distribution of Eigenvalues . . . . . . . . . . . . . . . . . 37
2.5 Spectral Radius of Matrices . . . . . . . . . . . . . . . . . 44
2.6 Hessian Matrix . . . . . . . . . . . . . . . . . . . . . . . . 47
2.7 Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
vii
, October 29, 2014 11:19 BC: 9404 – Intro to Comp Maths 2nd Ed. Yang-Comp-Maths2014 page viii
viii Introduction to Computational Mathematics
3. Ordinary Differential Equations 51
3.1 Ordinary Differential Equations . . . . . . . . . . . . . . . 51
3.2 First-Order ODEs . . . . . . . . . . . . . . . . . . . . . . 52
3.3 Higher-Order ODEs . . . . . . . . . . . . . . . . . . . . . 53
3.4 Linear System . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5 Sturm-Liouville Equation . . . . . . . . . . . . . . . . . . 58
4. Partial Differential Equations 59
4.1 Partial Differential Equations . . . . . . . . . . . . . . . . 59
4.1.1 First-Order Partial Differential Equation . . . . . 60
4.1.2 Classification of Second-Order Equations . . . . . 61
4.2 Mathematical Models . . . . . . . . . . . . . . . . . . . . . 61
4.2.1 Parabolic Equation . . . . . . . . . . . . . . . . . 61
4.2.2 Poisson’s Equation . . . . . . . . . . . . . . . . . . 61
4.2.3 Wave Equation . . . . . . . . . . . . . . . . . . . . 62
4.3 Solution Techniques . . . . . . . . . . . . . . . . . . . . . 64
4.3.1 Separation of Variables . . . . . . . . . . . . . . . 65
4.3.2 Laplace Transform . . . . . . . . . . . . . . . . . . 67
4.3.3 Similarity Solution . . . . . . . . . . . . . . . . . . 68
II Numerical Algorithms 71
5. Roots of Nonlinear Equations 73
5.1 Bisection Method . . . . . . . . . . . . . . . . . . . . . . . 73
5.2 Simple Iterations . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 Iteration Methods . . . . . . . . . . . . . . . . . . . . . . . 78
5.5 Numerical Oscillations and Chaos . . . . . . . . . . . . . . 81
6. Numerical Integration 85
6.1 Trapezium Rule . . . . . . . . . . . . . . . . . . . . . . . . 86
6.2 Simpson’s Rule . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3 Gaussian Integration . . . . . . . . . . . . . . . . . . . . . 89
7. Computational Linear Algebra 95
7.1 System of Linear Equations . . . . . . . . . . . . . . . . . 95
7.2 Gauss Elimination . . . . . . . . . . . . . . . . . . . . . . 97
