Numerical Analysis: A Programming Approach

✍ Scribed by Vinay Vachharajani

• Publisher: BPB Publications
• Year: 2018
• Tongue: English
• Leaves: 596
• Category: Library

✦ Synopsis

Learn the concept of algorithms from beginners to advanced level

Key Features

Chapters include objectives, learning outcomes, multiple choice questions, exercises for practice and solutions.

Programs are written in C Language for Numerical methods.

Topics are explained with suitable examples.

Arrangement (Logical order), clarity, detailed presentation and explanation of each topic with numerous solved and unsolved examples.

Concise but lucid and student friendly presentation for derivation of formulas used in various numerical methods.

Description
In the present scenario where the knowledge of computers has become an absolute necessity, there has been an increasing desire for numerical answers to any applied problem. This has led to high demand for courses in numerical analysis. Many real world problems are solved first by converting them into mathematical models and then applying analytical methods to solve that model. In several cases, where ordinary analytical methods fail, numerical methods can give the result.
The book is divided into twelve chapters, describing the concept of computer arithmetic, errors, iterative methods to find the roots of transcendental and algebraic equations, curve fitting, numerical differentiation, integration, and so on.
In the book the major emphasis is given on numerous solved and unsolved examples. Many topics in this book such as process graph, cubic spline method, Taylor series, Legendre and Chebyshev polynomials, Gauss - Chebyshev integration method and boundary value problems make this book unique.

What will you learn

Concept of numbers and their accuracy, binary and decimal number system, limitations of floating point representation.

Concept of error and their types, propagation of errors through process graph.

Iterative methods for finding the roots of algebraic and transcendental equations with their convergence, methods to solve the set of nonlinear equations, methods to obtain complex roots.

Concept of matrices, the direct and iterative methods to solve a system of linear algebraic equations.

Finite differences, interpolation and extrapolation methods, cubic spline, concept of curve fitting.

Differentiation and integration methods.

Solution of ordinary and partial differential equations

Who this book is for
This book is designed to serve as a textbook for the undergraduate as well as post graduate students of Mathematics, Engineering, Computer science (MCA, BCA), Information Technology and M.Sc. (IT).

Table of Contents
1. Computer Arithmetic
2. Error Analysis
3. Solution of Algebraic and Transcendental Equations
4. Solution of System of Linear Equations and Eigen value Problems
5. Finite Differences
6. Interpolation
7. Curve Fitting and Approximation
8. Numerical Differentiation
9. Numerical Integration
10. Difference Equations
11. Numerical Solution of Ordinary Differential Equations

✦ Table of Contents

Preface
About the Author
Table of Contents
1. Computer Arithmetic
1.1 Introduction
1.2 Numbers and their Accuracy
1.2.1 Significant Digits
1.2.2 Accuracy and Precision
1.2.3 Rounding – off and Chopping a Number
1.3 Classic Theorems of Numerical Methods
1.4 Number System
1.4.1 Decimal Number System
1.4.2 Binary Number System
1.4.3 Conversion of Decimal to Binary Number
1.4.4 Conversion of Binary to Decimal Number
1.5 Floating Point Representation
1.6 Storage of Real Number in Computer Memory
1.7 Arithmetic Operations on Normalized Floating Point Numbers
1.7.1 Addition
1.7.2 Subtraction
1.7.3 Multiplication
1.7.4 Division
1.8 Limitations of Floating Point Representation
1.9 Programs in C
Exercises
2. Error Analysis
2.1 Introduction
2.2 Errors (Data Error, Truncation Error, Round-off Error)
2.2.1 Absolute Error, Relative Error and Percentage Error
2.3 General Formula for Estimation of Errors
2.4 Errors on Fundamental Operations of Arithmetic
2.4.1 Errors on Addition Operation
2.4.2 Errors on Subtraction Operation
2.4.3 Errors on Multiplication Operation
2.4.4 Errors on Division Operation
2.5 Error in a Series Approximation
2.6 Process Graph
2.7 Program in C
Exercises
Answers
3.Solution of Algebraic and Transcendental Equations
3.1 Introduction
3.2 Important Properties of Equation
3.2.1 Descarte’s Rule of Sign
3.3 Methods of Solution
3.3.1 Direct Method
3.3.2 Graphical Method
3.3.3 Trial and Error Method
3.3.4 Iterative Method
3.4 Termination Criterion
3.5 Bisection Method (Bolzano Method)
3.5.1 Convergence of Bisection Method
3.6 Regula Falsi Method (False Position Method)
3.6.1 Convergence of False Position Method
3.7 Fixed Point Method (Successive Approximation Method)
3.7.1 Criterion of Convergence
3.7.2 Different Cases of Convergence
3.7.3 Convergence of Fixed Point Method
3.7.4 Aitken’s Δ₂ Method
3.7.5 Finding a Square Root of a Number Using Fixed Point Method
3.8 Newton – Raphson Method (Tangent Method)
3.8.1 Analytical Derivation of Newton Raphson Formula
3.8.2 Criterion of Convergence
3.8.3 Different Cases of Divergence
3.8.4 Convergence of Newton Raphson Method
3.8.5 Finding pth Root Using Newton Raphson Formula
3.8.6 Generalized Newton’s Method for Multiple Roots
3.9 Secant Method (Chord Method)
3.9.1 Convergence of Secant Method
3.9.2 Difference Between False Position Method and Secant Method
3.10 Solution of Polynomial Equations
3.10.1 Birge – Vieta Method
3.10.2 Graeffe’s Root Squaring Method
3.11 Budan’s Theorem
3.12 Ramanujan Method
3.13 Methods of Finding Complex Roots
3.13.1 Muller’s Method
3.13.2 Lin – Bairstow’s Method
3.14 System of Non – linear Equations
3.14.1 Newton – Raphson Method
3.14.2 Fixed Point Method
3.15 Programs in C
Exercises
Answers
4. Solution of System of Linear Equations and Eigen value Problems
4.1 Introduction
4.2 Matrices
4.2.1 Special Types of Matrices
4.2.2 Matrix Operations
4.2.3 Inverse of a Matrix
4.3 Solution of Simultaneous Linear Algebraic Equations
4.3.1 Direct Methods
Matrix Inversion Method
Gauss Elimination Method
Gauss Elimination with Pivoting
Gauss- Jordan Method
Triangularization Method
Dolittle LU Decomposition Method
Crout’s LU Decomposition Method
Crout’s Method for Finding the Inverse of Matrix
Cholesky Reduction Method
4.3.2 Iterative Methods
Convergence Criteria for Iterative Methods
Jacobi Iteration Method
Gauss – Seidel Method
Relaxation Method
4.3.3 Ill – Conditioned System of Equations
4.3.4 Method for Ill – Conditioned System of Equations
4.4 Eigen values and Eigen Vectors
4.5 Power Method for Approximating Eigen values
4.6 Programs in C
Exercises
Answers
5.Finite Differences
5.1 Introduction
5.2 Forward Differences
5.2.1 Results on Forward Difference Operator
5.3 Backward Differences
5.4 Central Differences
5.5 Other Operators
Shift Operator E
Averaging Operator μ
Differential Operator D
5.5.1 Relation between Δ, ∇, E, δ, μ and D
5.6 Differences of a Polynomial
5.7 Factorial Notation
5.7.1 Reciprocal Factorial
5.7.2 Expressing a Polynomial in Factorial Notation
5.7.3 Inverse Operator of Δ
5.8 Error Propagation
5.9 Summation of a Series
5.9.1 Montmort’s Theorem
Exercises
Answers
6. Interpolation
6.1 Introduction
6.1.1 Error in Interpolation
6.2 Newton’s Forward Difference Interpolation Formula
6.2.1 Estimation of Error in Newton’s Forward Interpolation Formula
6.3 Newton’s Backward Difference Interpolation Formula
6.3.1 Estimation of Error in Newton’s Backward Interpolation Formula
6.4 Central Difference Interpolation Formula
6.4.1 Gauss’s forward interpolation formula
6.4.2 Gauss’s backward interpolation formula
6.4.3 Stirling’s Interpolation Formula
6.4.4 Bessel’s Interpolation Formula
6.4.5 Laplace – Everett Interpolation Formula
Relation Between Bessel’s and Laplace – Everett Formulae
6.5 Interpolation with Unequal Intervals
6.5.1 Lagrange’s Interpolation Formula
Advantages of Lagrange’s Interpolation Formula
Disadvantages of Lagrange’s Formula
6.5.2 Inverse Interpolation
Lagrange’s Inverse Interpolation Formula
Inverse Interpolation Using Method of Successive Approximations
6.5.3 Error in Lagrange’s Interpolation Formula
6.5.4 Divided Differences
Properties of Divided Differences
6.5.5 Newton’s Divided Difference Interpolation Formula
6.6 Hermite Interpolating Polynomial
6.7 Piecewise Polynomial Interpolation
6.7.1 Piecewise Linear Interpolation
6.7.2 Piecewise Cubic Interpolation
6.8 Cubic Spline Interpolation
6.9 Double Interpolation
6.10 Programs in C
Exercises
Answers
7. Curve Fitting and Approximation
7.1 Introduction
7.2 Method of Group Averages
7.2.1 Equation Involving Three Constants
7.3 Principle of Least Squares
7.3.1 Fitting a Straight Line by Method of Least Squares
7.3.2 Fitting a Second Degree Curve y = a + bx + cx^2
7.3.3 Fitting a Geometric Curve y = ax^b
7.3.4 Fitting an Exponential Curve y = ae^{bx} and y = ab^x
7.4 Calculation of the Sum of the Squares of the Residuals
7.5 Method of Moments
7.6 Approximation of Functions
7.6.1 Taylor Series Representation
7.6.2 Legendre Polynomials
7.6.3 Chebyshev Polynomials
Properties of Chebyshev Polynomials
Chebyshev Polynomial Approximation
Lanczos Economization of Power Series
7.7 Programs in C
Exercises
Answers
8.Numerical Differentiation
8.1 Introduction
8.2 Function Tabulated at Equal Intervals
8.2.1 Derivatives Using Newton’s Forward Difference Formula
8.2.2 Derivatives Using Newton’s Backward Difference Formula
8.3 Derivatives using Central Difference Formulae
8.3.1 Derivatives Using Stirling’s Formula
8.3.2 Derivatives Using Bessel’s Formula
8.4 Derivatives using Lagrange’s Interpolating Polynomial For Equidistant Intervals
8.5 Function Tabulated at Unequal Intervals
8.5.1 Derivatives Using Newton’s Divided Difference Formula
8.5.2 Derivatives Using Lagrange’s Interpolating Polynomial
8.6 Maxima and Minima of a Tabulated Function
8.7 Partial Derivatives
8.8 Richardson’s Extrapolation Method
8.9 Programs in C
Exercises
Answers
9.Numerical Integration
9.1 Introduction
9.2 Newton-Cote’s Quadrature Formula
9.3 Trapezoidal Rule
9.3.1 Composite Trapezoidal Rule
9.3.2 Error in Trapezoidal Rule
9.3.3 Geometrical Interpretation of Trapezoidal Rule
9.4 Simpson’s One – Third Rule
9.4.1 Composite Simpson’s One – Third Rule
9.4.2 Error in Simpson’s One – Third Rule
9.4.3 Geometrical Interpretation of Simpson’s One – Third Rule
9.5 Simpson’s Three – Eighths Rule
9.5.1 Composite Simpson’s Three – Eighths Rule
9.6 Boole’s Rule
9.6.1 Composite Boole’s Rule
9.7 Weddle’s Rule
9.7.1 Composite Weddle’s Rule
9.8 Numerical Integration using Cubic Splines
9.9 Romberg’s Method
9.10 Euler – Maclaurin Summation Formula
9.11 Methods Based on Undetermined Co-efficients
9.11.1 Gauss – Legendre Integration Method
9.11.2 Gauss – Chebyshev Integration Method
9.12 Double Integrals
9.12.1 Trapezoidal Rule
9.12.2 Simpson’s Rule
9.13 Programs in C
Exercises
Answers
10.Difference Equations
10.1 Introduction
10.2 Definitions
10.3 Linear Difference Equations
10.3.1 Properties of Linear Difference Equations
10.3.2 Rules for Finding Complementary Function
10.3.3 Rules for Finding Particular Integral
Exercises
Answers
11.Numerical Solution of Ordinary Differential Equations
11.1 Introduction
11.2 Basic Terminologies of Differential Equations
11.3 Single - Step Methods
11.3.1 Picard’s Method
Picard’s Method For Simultaneous First Order Differential Equations
11.3.2 Taylor Series Method
Taylor Series Method for Simultaneous First Order Differential Equations
Taylor Series Method for Second Order Differential Equation
11.3.3 Euler’s Method
Geometrical Interpretation
Improved Euler Method
Modified Euler’s Method
11.3.4 Runge – Kutta Methods
First Order Runge – Kutta Method
Second Order Runge – Kutta Method
Third Order Runge – Kutta Method
Fourth Order Runge – Kutta Method
Runge – Kutta Method for Simulataneous First Order Differential Equations
Runge – Kutta Method for the Solution of a Second – Order Differential Equation
11.4 Multi – Step Methods
11.4.1 Milne - Simpson’s Predictor – Corrector Method
11.4.2 Adam – Bashforth’s Predictor – Corrector Method
11.4.3 Difference between Runge – Kutta Method and Predictor – Corrector Method
11.5 Boundary Value Problems
11.5.1 Finite – Difference Method
11.6 Programs in C
Exercises
Answers
12.Numerical Solution of Partial Differential Equations
12.1 Introduction
12.2 Classification of Second Order Partial Differential Equations
12.3 Finite Difference Approximations to Partial Derivatives
12.4 Elliptic Equations and Solution of Laplace Equation by Finite Differences
12.4.1 Liebmann’s Iteration Process for Solving Laplace Equation
12.4.2 Solution of Poisson Equation
12.4.3 Solution of Laplace Equation by Relaxation Method
12.5 Bender – Schmidt’s Method for Solving Parabolic Equation
12.6 Crank – Nicolson’s Method for Solving Parabolic Equation
12.7 Difference Equation for Solving Hyperbolic Equation
12.8 Programs in C
Exercises
Answers
APPENDIX - I. Case Studies / Applications
1.Application of System of Linear Equations and Gauss – Jordan method to Environmental Science
2.Application of Eigenvalues and Eigenvectors and Diagonalization to Environmental Science
APPENDIX - II. Synthetic Division
Bibliography
Index
A, B, C, D
E, F, G, H, I
J, L, M, N, O, P
Q, R, S, T, U, W