Core Concepts and Fundamentals - Introduction to Scientific Computing

Foundational Theorems¶

Forward and Backward Error¶

The Contraction Mapping Principle¶

Theorem 5 (Banach Fixed Point Theorem)

Let $(X, d)$ be a complete metric space and $T: X \to X$ a contraction mapping, i.e., there exists $q \in [0, 1)$ such that

d(T(x), T(y)) \leq q \cdot d(x, y) \quad \text{for all } x, y \in X.

(10)

Then:

$T$ has a unique fixed point $x^* \in X$
For any starting point $x_0 \in X$ , the iteration $x_{n+1} = T(x_n)$ converges to $x^*$
The convergence is geometric: $d(x_n, x^*) \leq q^n \cdot d(x_0, x^*)$
A priori bound: $d(x_n, x^*) \leq \frac{q^n}{1-q} d(x_0, x_1)$
A posteriori bound: $d(x_n, x^*) \leq \frac{q}{1-q} d(x_{n-1}, x_n)$

Proof 1

Existence and convergence: The sequence $\{x_n\}$ is Cauchy. For $m > n$ :

d(x_n, x_m) \leq \sum_{k=n}^{m-1} d(x_k, x_{k+1}) \leq \sum_{k=n}^{m-1} q^k d(x_0, x_1) \leq \frac{q^n}{1-q} d(x_0, x_1)

(11)

Since $q < 1$ , this tends to 0 as $n \to \infty$ . By completeness, $x^* = \lim_{n \to \infty} x_n$ exists.

Taking limits in $x_{n+1} = T(x_n)$ and using continuity of $T$ (contractions are Lipschitz, hence continuous):

x^* = \lim_{n \to \infty} x_{n+1} = \lim_{n \to \infty} T(x_n) = T\left(\lim_{n \to \infty} x_n\right) = T(x^*)

(12)

Uniqueness: If $T(x^*) = x^*$ and $T(y^*) = y^*$ , then

d(x^*, y^*) = d(T(x^*), T(y^*)) \leq q \cdot d(x^*, y^*)

(13)

Since $q < 1$ , this forces $d(x^*, y^*) = 0$ , so $x^* = y^*$ .

Convergence rate: $d(x_n, x^*) = d(T(x_{n-1}), T(x^*)) \leq q \cdot d(x_{n-1}, x^*) \leq q^n d(x_0, x^*)$ .

A posteriori bound: Let $m \to \infty$ in the Cauchy estimate with $n$ replaced by $n-1$ .

Remark 2 (Where We Use the Banach Fixed Point Theorem)

This theorem is THE foundation for iterative methods throughout scientific computing:

Application	Space $X$	Contraction $T$
Fixed-point iteration	$\mathbb{R}$ or $[a,b]$	$g(x)$ with $\|g'\|_\infty < 1$
Newton’s method (local)	Neighborhood of root	Newton map near simple root
Picard iteration for ODEs	$C([0,T])$	Integral operator
Iterative linear solvers	$\mathbb{R}^n$	$x \mapsto Mx + c$ with $\rho(M) < 1$
Implicit function theorem	Banach space	Contraction from IFT proof

The a posteriori bound is particularly useful: it gives a computable error estimate from consecutive iterates.

The Neumann Series¶

Proof 2

Convergence: Since $\|a^k\| \leq \|a\|^k$ (submultiplicativity of the norm in a Banach algebra) and $\|a\| < 1$ , the series $\sum_{k=0}^\infty a^k$ converges absolutely, hence converges in the complete space $\mathcal{A}$ .

Verification: The partial sums $S_n = \sum_{k=0}^n a^k$ satisfy

(1 - a) S_n = S_n (1 - a) = 1 - a^{n+1}

(15)

As $n \to \infty$ , $\|a^{n+1}\| \leq \|a\|^{n+1} \to 0$ , so $(1 - a) \sum_{k=0}^\infty a^k = 1$ .

Spectral radius version: Gelfand’s formula gives $\rho(A) = \lim_{k \to \infty} \|A^k\|^{1/k}$ . If $\rho(A) < 1$ , then for any $r$ with $\rho(A) < r < 1$ , we have $\|A^k\| \leq C r^k$ for large $k$ , ensuring convergence.

Remark 3 (Where We Use the Neumann Series)

The Neumann series is the operator-theoretic generalization of the geometric series $\frac{1}{1-r} = \sum_{k=0}^\infty r^k$ for $|r| < 1$ .

Application	Banach Algebra	Element $a$
Iterative linear solvers	$\mathbb{R}^{n \times n}$	Iteration matrix $M$
Perturbation of inverses	$\mathcal{B}(X)$	$A^{-1}\Delta A$ for perturbed $A + \Delta A$
Integral equations	$\mathcal{B}(L^2)$	Integral operator $K$
ODE stability	$\mathbb{C}^{n \times n}$	$hA$ in implicit methods
Resolvent	$\mathcal{B}(X)$	$\lambda^{-1}A$ for $

Key insight: The condition $\rho(M) < 1$ (not $\|M\| < 1$ ) is necessary and sufficient for convergence. This is why spectral radius, not norm, controls iterative methods.

Proof 3

Write $A + \Delta A = A(I + A^{-1}\Delta A)$ . Since $\|A^{-1}\Delta A\| \leq \|A^{-1}\| \|\Delta A\| < 1$ , the Neumann series gives

(A + \Delta A)^{-1} = (I + A^{-1}\Delta A)^{-1} A^{-1} = \sum_{k=0}^\infty (-A^{-1}\Delta A)^k A^{-1}

(17)

The bound follows from estimating $\|(I + A^{-1}\Delta A)^{-1} - I\|$ .