Numerical Mathematics Part 1: Nonlinear Equations, Interpolation, and Integration

Numerical Mathematics (Numerics) focuses on the numerical calculation of solutions to mathematical problems.
It serves as a link between pure mathematics, computer science, and engineering sciences.
It develops algorithms and methods to solve problems that lack exact theoretical solutions, such as integrating complex functions or solving higher-order partial differential equations.
Quote by Immanuel Kant: "In every pure natural science, there is only as much actual science as there is mathematics applied in it."

The primary goal is determining roots (zeros) of equations where $f(x) = 0$ . This is often reframed as a "nullstelle" (zero) problem for functions of one or more variables.
Definition 1.1 (Zero/Nullstelle): Let $D \subset \mathbb{R}^n$ and $f: D \rightarrow \mathbb{R}^n$ . An element $x = (x_1, \dots, x_n) \in D$ is a zero of $f$ if $f(x) = 0$ .

Developed by Sir Isaac Newton (1643–1727). It is an iterative method motivated by geometric intuition.
Geometric Motivation: In a point $x^{(0)}$ (the starting approximation), a tangent $t_0(x)$ is placed on the function $f(x)$ . The zero of this tangent, $x^{(1)}$ , is calculated as a better approximation of the actual zero $x^*$ .
Tangent Equation: $t_0(x) = f(x^{(0)}) + f'(x^{(0)})(x - x^{(0)})$ .
Iteration Formula: $x^{(i+1)} = x^{(i)} - \frac{f(x^{(i)})}{f'(x^{(i)})}$ , assuming $f'(x^{(i)}) \neq 0$ .
Convergence:
- Quadratic Convergence: If $x^*$ is a simple zero ( $f'(x^*) \neq 0$ ), the error decreases such that $|x^{(i+1)} - x^*| \leq C \cdot (x^{(i)} - x^*)^2$ . Effectively, the number of correct decimal places doubles at each step.
- Linear Convergence: If $x^*$ is a multiple zero ( $f'(x^*) = 0$ ), the error decreases linearly: $|x^{(i+1)} - x^*| \leq C \cdot |x^{(i)} - x^*|$ with C < 1.

The Heron-Method (Babylonian Method): Used to calculate square roots (e.g., $\sqrt{2}$ ). It is a special case of the Newton method applied to $f(x) = x^2 - a$ .
Formula: $x^{(i+1)} = \frac{1}{2} (x^{(i)} + \frac{a}{x^{(i)}})$ .
Stability and Divergence: The method does not always converge. Cycles can occur where the algorithm toggles between two values (e.g., $x^{(2)} = x^{(0)}$ and $x^{(3)} = x^{(1)}$ ).
Theorem 1.1: For a polynomial of degree at least 2 with only real roots, starting with any value larger than the largest zero guarantees a strictly monotonically decreasing sequence converging to that zero.

Used when the derivative $f'(x)$ is difficult or impossible to determine.
Approximates the derivative using a secant between two points: $f'(x) \approx \frac{f(x^{(i)}) - f(x^{(i-1)})}{x^{(i)} - x^{(i-1)}}$ .
Two-Term Recursion: Requires two starting values $x^{(0)}$ and $x^{(1)}$ .
Formula: $x^{(i+1)} = \frac{f(x^{(i)}) x^{(i-1)} - x^{(i)} f(x^{(i-1)})}{f(x^{(i)}) - f(x^{(i-1)})}$ .

Solves systems of nonlinear equations where the number of variables equals the number of output variables.
Jacobi-Matrix (Functional Matrix): Versatile matrix containing all first-order partial derivatives.
Matrix Definition: $J_f(x) = \begin{pmatrix} \frac{\partial f_1}{\partial x_1} & \dots & \frac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \dots & \frac{\partial f_n}{\partial x_n} \end{pmatrix}$ .
Multidimensional Iteration: $x^{(i+1)} = x^{(i)} - [J_f(x^{(i)})]^{-1} f(x^{(i)})$ .
Practical Implementation: Explicitly inverting the matrix is computationally expensive. Instead, solve the linear system: $J_f(x^{(i)}) \cdot y = -f(x^{(i)})$ and then update $x^{(i+1)} = x^{(i)} + y$ .

Polynomial (Definition 2.1): A function $p(x) = a_n x^n + \dots + a_1 x + a_0$ . The set of all polynomials of degree at most $n$ is denoted by $\Pi_n$ .
Interpolation Problem: Given $n+1$ support points (Sttzstellen) x_0 < x_1 < \dots < x_n and support values (Sttzwerte) $f_0, f_1, \dots, f_n$ , find a polynomial $P \in \Pi_n$ such that $P(x_i) = f_i$ .
Existence and Uniqueness (Theorem 2.1): There is exactly one such polynomial for any given set of distinct points.

Uses Lagrange-Polynomials of degree $n$ (Definition 2.2): $L_k(x) = \prod_{i=0, i \neq k}^{n} \frac{x - x_i}{x_k - x_i}$ .
Fundamental Property: $L_k(x_i) = 1$ if $i=k$ , and $0$ if $i \neq k$ .
Interpolation Formula: $P(x) = \sum_{k=0}^{n} f_k L_k(x)$ .
Disadvantage: If points are added, all Lagrange polynomials must be recalculated.

Used in Computer-Aided Design (CAD). These focus on approximating control points rather than strict interpolation.
Bernstein-Polynomials (Definition 2.6): $\beta_{n,k}(t) = \binom{n}{k} t^k (1 - t)^{n-k}$ for $t \in [0, 1]$ .
Properties of Bernstein-Polynomials:
- Sum to 1 (Partition of unity): $\sum_{k=0}^{n} \beta_{n,k}(t) = 1$ .
- Strictly positive for $t \in (0, 1)$ .
- Exact maximum at $t = \frac{k}{n}$ .
Bezier-Curve (Definition 2.7): $B(t) = \sum_{k=0}^{n} b_k \beta_{n,k}(t)$ , where $b_k$ are control points.
Key Characteristics:
- Endpoint Interpolation: The curve starts at $b_0$ and ends at $b_n$ .
- Convex Hull Property: The entire curve lies within the convex hull of its control points.
- Convexity Preservation: If the control polygon is convex, the curve is convex.

A recursive, numerically stable method to calculate points on a Bezier curve for a fixed $t$ .
Recursive step: $p_i^{(k)} = (1 - t) p_{i-1}^{(k-1)} + t p_i^{(k-1)}$ .
The final point $p_n^{(n)}$ is the curve point $B(t)$ .

Barycentric Coordinates (Definition 2.12): A point $P$ in a triangle defined by non-collinear points $T_1, T_2, T_3$ can be uniquely represented as $P = \tau_1 T_1 + \tau_2 T_2 + \tau_3 T_3$ where $\tau_1 + \tau_2 + \tau_3 = 1$ .
Geometric Interpretation: $P$ is the "center of gravity" if masses $\tau_i$ are placed at the corners $T_i$ .
Bezier Surfaces: Defined over triangular parameter regions using Bernstein polynomials in barycentric coordinates: $B(P) = \sum_{(i_1, i_2, i_3) \in N_n} b_{i_1, i_2, i_3} \beta_{i_1, i_2, i_3}(P)$ .

The Trapezoidal Rule: Approximates the integral $I = \int_{a}^{b} f(x) dx$ by dividing the interval into $n$ parts with step size $h$ .
Trapezoidal Sum Formula: $T(h) = \frac{h}{2} [f(x_0) + 2 f(x_1) + \dots + 2 f(x_{n-1}) + f(x_n)]$ .
Romberg Method: Improves the results of the trapezoidal rule through Richardson extrapolation.
Algorithm:
1. Calculate trapezoidal sums $T_{0,i} = T(h_i)$ with $h_i = \frac{h_0}{2^i}$ .
2. Use the recursion: $T_{k,i} = \frac{4^k T_{k-1, i+1} - T_{k-1, i}}{4^k - 1}$ .
Advantages: This method significantly increases the order of convergence. For example, if the error of the trapezoidal rule is $O(h^2)$ , the Romberg columns provide higher-order approximations like $O(h^4), O(h^6), \dots$ .
Asymptotic Development: The principle works because the error of the trapezoidal rule can be written as $T(h) = I + c_1 h^2 + c_2 h^4 + \dots$ . This is the secret of the convergence acceleration in Romberg's method.
General Application: The Romberg principle (Verallgemeinertes Romberg-Verfahren) can be applied to any sequence of approximations that possesses an asymptotic development, such as numerical differentiation or approximating constants like $e$ .