A Concise Introduction to Numerical Analysis

A. C. Faul

• Publisher: Chapman and Hall/CRC
• Year: 2018
• ISBN:
  9781498712217
• Edition: 1
• Topic: Matematica
• Subtopic: Matematica generale

This textbook provides an accessible and concise introduction to numerical analysis for upper undergraduate and beginning graduate students from various backgrounds. It was developed from the lecture notes of four successful courses on numerical analysis taught within the MPhil of Scientific Computing at the University of Cambridge. The book is easily accessible, even to those with limited knowledge of mathematics.Students will get a concise, but thorough introduction to numerical analysis. In addition the algorithmic principles are emphasized to encourage a deeper understanding of why an algorithm is suitable, and sometimes unsuitable, for a particular problem. A Concise Introduction to Numerical Analysis strikes a balance between being mathematically comprehensive, but not overwhelming with mathematical detail. In some places where further detail was felt to be out of scope of the book, the reader is referred to further reading.The book uses MATLAB ® implementations to demonstrate the workings of the method and thus MATLAB's own implementations are avoided, unless they are used as building blocks of an algorithm. In some cases the listings are printed in the book, but all are available online on the book's page at www.crcpress.com.Most implementations are in the form of functions returning the outcome of the algorithm. Also, examples for the use of the functions are given. Exercises are included in line with the text where appropriate, and each chapter ends with a selection of revision exercises. Solutions to odd-numbered exercises are also provided on the book's page at www.crcpress.com.This textbook is also an ideal resource for graduate students coming from other subjects who will use numerical techniques extensively in their graduate studies.

CHAPTER 1

Fundamentals

1.1 Floating Point Arithmetic

We live in a continuous world with infinitely many real numbers. However, a computer has only a finite number of bits. This requires an approximate representation. In the past, several different representations of real numbers have been suggested, but now the most widely used by far is the floating point representation. Each floating point representations has a base β (which is always assumed to be even) which is typically 2 (binary), 8 (octal), 10 (decimal), or 16 (hexadecimal), and a precision p which is the number of digits (of base β) held in a floating point number. For example, if β = 10 and p = 5, the number 0.1 is represented as 1.0000 × 10⁻¹. On the other hand, if β = 2 and p = 20, the decimal number 0.1 cannot be represented exactly but is approximately 1.1001100110011001100 × 2⁻⁴. We can write the representation as ±d₀.d₁ ⋯ d_{p − 1} × β^e, where d₀.d₁ ⋯ d_{p − 1} is called the significand (or mantissa) and has p digits and e is the exponent. If the leading digit d₀ is non-zero, the number is said to be normalized. More precisely ±d₀.d₁ ⋯ d_{p − 1} × β^e is the number

$\pm \left(d_0+d_1{\beta }^{-1}+d_2{\beta }^{-2}+\mathrm{\cdots }+d_{p-1}{\beta }^{-\left(p-1\right)}\right){\beta }^e,0\le d_i<\beta .$

If the exponents of two floating point numbers are the same, they are said to be of the same magnitude. Let’s look at two floating point numbers of the same magnitude which also have the same digits apart from the digit in position p, which has index p − 1. We assume that they only differ by one in that digit. These floating point numbers are neighbours in the representation and differ by

$1\times {\beta }^{-\left(p-1\right)}\times {\beta }^e={\beta }^{e-p+1}.$

Thus, if the exponent is large the difference between neighbouring floating point numbers is large, while if the exponent is small the difference between neighbouring floating point numbers is small. This means floating point numbers are more dense around zero.

As an example consider the decimal number 3.141592, the first seven digits of π. Converting this into binary, we could approximate it by

$\begin{array}{l}1.1001001000011111101011111100100011\times 2^1=\\ \left(1+1*\frac{1}{2}+0*\frac{1}{4}+0*\frac{1}{8}+1*\frac{1}{16}+0*\frac{1}{32}+0*\frac{1}{64}+\mathrm{\dots }\right)*2^1\approx \mathrm{3.14159200003.}\end{array}$

If we omit the last digit we arrive at

$1.100100100001111110101111110010001\times 2^1\approx \mathrm{3.14159199991.}$

Looking at the conversion to a hexadecimal representation, we get the approximation

$\begin{array}{l}3.243F5F92=\\ 3+2*\frac{1}{16}+4*\frac{1}{{16}^2}+3*\frac{1}{{16}^3}+15*\frac{1}{{16}^4}+5*\frac{1}{{16}^5}+\mathrm{\dots }\approx \mathrm{3.14159200001.}\end{array}$

Omi...