From the free course CS323: Numerical Analysis and Computing on Lykke

Introduction to Python and Numerical Computing

Key concepts: Dynamic Typing · List Comprehension · Direct vs. Iterative Methods · Big-O Notation · Asymptotic Analysis

Foundational concepts of Python programming for scientific computing and the motivation behind numerical methods.

Introduction to Python and Numerical Computing

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. This field forms the backbone of modern scientific computing, engineering, and data science. While theoretical mathematics often assumes infinite precision and continuous domains, practical computation happens on hardware with finite constraints. This article explores the transition from mathematical theory to computational implementation using Python, focusing on the fundamental limitations of digital arithmetic and the linear algebraic structures that organize large-scale data.

1. The Motivation: Why "Chalkboard Math" Fails on Silicon

In pure mathematics, formulas are exact. However, when implemented on a computer, even the most robust-looking formulas can produce garbage results. This discrepancy arises from Finite Precision Arithmetic.

1.1. Catastrophic Cancellation

Consider the quadratic formula for $ax^2 + bx + c = 0$:

$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

If $b^2 \gg 4ac$, then $\sqrt{b^2 - 4ac} \approx |b|$. If $b$ is positive, the numerator for one of the roots becomes $-b + \text{something very close to } b$. This is known as Catastrophic Cancellation—the subtraction of two nearly equal numbers, which causes a massive loss of significant digits. In numerical computing, we often rewrite such formulas (e.g., using rationalization) to avoid these operations.

1.2. Direct vs. Iterative Methods

Numerical algorithms generally fall into two categories:

Method Type Description Example
Direct Methods Provide a solution in a finite, pre-determined number of steps. Gaussian Elimination, Cramer's Rule
Iterative Methods Start with a guess and refine it through successive approximations. Newton's Method, Conjugate Gradient

2. Floating-Point Arithmetic and Error Analysis

Digital computers represent real numbers using the Floating-Point Number System, typically following the IEEE 754 standard. A number $x$ is represented as:

$$x = \pm m \times \beta^e$$

Where $m$ is the mantissa (or significand), $\beta$ is the base (usually 2), and $e$ is the exponent.

2.1. Machine Epsilon and Precision

Because the mantissa has a fixed number of bits, there is a limit to how small a difference between two numbers the computer can recognize. This limit is called Machine Epsilon ($\epsilon_{mach}$).

Definition: Machine Epsilon is the smallest positive number $\epsilon$ such that $1 + \epsilon \neq 1$ in the computer's floating-point representation.

2.2. Quantifying Error

When we approximate a real number $x$ with a machine number $\bar{x}$, we measure the error in two ways:

  1. Absolute Error: $E_{abs} = |x - \bar{x}|$
  2. Relative Error: $E_{rel} = \frac{|x - \bar{x}|}{|x|}, \quad x \neq 0$

In scientific computing, relative error is usually more important because it scales with the magnitude of the numbers involved. For double-precision (64-bit) floats, $E_{rel}$ is typically on the order of $10^{-16}$.

AI_DEMOI_DEMO## 3. Order Notation (Big-O)

To compare the efficiency of algorithms or the accuracy of approximations, we use Order Notation. It characterizes the limiting behavior of a function.

3.1. Large $n$ (Asymptotic Complexity)

In the context of algorithm runtime, we say $f(n) = O(g(n))$ as $n \to \infty$ if there exists a constant $C > 0$ such that $|f(n)| \le C|g(n)|$ for all sufficiently large $n$. This tells us how the computational cost scales with input size.

3.2. Small $h$ (Truncation Error)

In numerical calculus (like Taylor series), we care about the error as the step size $h \to 0$. We say an approximation is $O(h^k)$ if the error vanishes at a rate proportional to $h^k$.

Example: Taylor Series Expansion $$f(x+h) = f(x) + hf'(x) + \frac{h^2}{2}f''(x) + O(h^3)$$ If we drop the $h^2$ term, our approximation of $f(x+h)$ has a "first-order" error of $O(h^2)$.

4. Linear Algebra: The Framework of Numerical Computing

Numerical problems are rarely about single numbers; they involve systems of equations represented as vectors and matrices.

4.1. Vectors in $\mathbb{R}^n$

A vector $v \in \mathbb{R}^n$ is an ordered $n$-tuple of real numbers. In Python, we use the NumPy library to handle these efficiently. Unlike standard Python lists, NumPy arrays are contiguous in memory, allowing for SIMD (Single Instruction, Multiple Data) optimizations.

4.2. Matrices and Sparsity

A matrix $A \in \mathbb{R}^{m \times n}$ can be viewed as a collection of column vectors.

  • Dense Matrices: Most entries are non-zero. Stored as 2D arrays.
  • Sparse Matrices: Most entries are zero. Stored using specialized structures (like Compressed Sparse Row - CSR) to save memory and time. This is critical in fields like finite element analysis or social network graphs.

5. Norms and Stability

How do we measure the "size" of a vector or the "sensitivity" of a matrix? We use Norms.

5.1. Vector Norms

A function $|x|$ is a norm if it satisfies:

  1. $|x| \ge 0$ (Positivity)
  2. $|\alpha x| = |\alpha| |x|$ (Homogeneity)
  3. $|x + y| \le |x| + |y|$ (Triangle Inequality)

Common norms include:

  • $L_1$ Norm (Manhattan): $\sum |x_i|$
  • $L_2$ Norm (Euclidean): $\sqrt{\sum x_i^2}$
  • $L_\infty$ Norm (Max): $\max |x_i|$

5.2. Matrix Norms and Condition Numbers

The Condition Number of a matrix $A$, denoted $\kappa(A)$, is defined as: $$\kappa(A) = |A| \cdot |A^{-1}|$$

It measures how much the output $x$ of a linear system $Ax = b$ changes for a small change in the input $b$.

  • If $\kappa(A)$ is small (close to 1), the system is well-conditioned.
  • If $\kappa(A)$ is large, the system is ill-conditioned, and numerical solutions will be highly sensitive to rounding errors. A classic example is the Hilbert Matrix, where the condition number grows exponentially with the size of the matrix.

6. Python Fundamentals for Science

Python is the lingua franca of scientific computing due to its readability and the strength of its ecosystem. Key traits include:

  • Dynamic Typing: Variables do not need explicit type declarations, speeding up development.
  • Interpreted Nature: Code is executed line-by-line, which is ideal for exploratory data analysis in environments like Jupyter.
  • Platform Independence: Python code runs identically on Windows, macOS, and Linux, provided the interpreter is present.

Summary of Python Data Structures for Numerical Work

Structure Mutability Best Use Case
List Mutable General purpose collection of heterogeneous items.
Tuple Immutable Fixed sequences, dictionary keys, returning multiple values.
NumPy Array Mutable Homogeneous numerical data, linear algebra operations.
Dictionary Mutable Key-value mapping, fast lookups.

Source Materials

Study CS323: Numerical Analysis and Computing on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of CS323: Numerical Analysis and Computing · Browse more course pages