Dynamic Programming, Approximation in Function Space, Successive Approximations

Dynamic Programming

Dynamic programming is a powerful mathematical technique used for solving complex problems by breaking them down into smaller, overlapping subproblems. The core idea is to solve each subproblem only once and store its solution. When the same subproblem is encountered again, the stored solution is retrieved, thus avoiding redundant computations. This approach is particularly effective for optimization problems where decisions are made sequentially.

The methodology of dynamic programming typically involves two main phases:

1. Forward Recursion (or Bottom-Up Approach): This phase starts by solving the smallest subproblems and then uses their solutions to build up solutions for larger subproblems. It proceeds from the initial state to the final state.
2. Backward Recursion (or Top-Down Approach): This phase starts by defining the solution for the final state and then works backward to determine the solutions for preceding states. This often involves using a recursive function with memoization (storing computed results).

Key Concepts in Dynamic Programming:

• Optimal Substructure: A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems.
• Overlapping Subproblems: A problem has overlapping subproblems if the same subproblems are solved multiple times during the computation of the overall solution.

The Bellman Equation (Principle of Optimality:

Developed by Richard Bellman, the principle of optimality is the fundamental concept behind dynamic programming. It states that an optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision. This principle can be mathematically formulated using the Bellman equation.

For a problem with stages $k = 1, 2, ..., n$, let $f_k(x)$ be the optimal value of the objective function from stage $k$ onwards, given that the state at stage $k$ is $x$. The Bellman equation describes the relationship between the optimal value at stage $k$ and the optimal value at stage $k+1$:

$$f_k(x) = \min_{y} \{c(x, y) + f_{k+1}(y)\}$$

Here:

• $f_k(x)$ is the optimal value starting from state $x$ at stage $k$.
• $y$ represents the decision or action taken at stage $k$.
• $c(x, y)$ is the immediate cost or reward of taking action $y$ from state $x$.
• $f_{k+1}(y)$ is the optimal value from the next stage, given the resulting state is $y$.
• The minimization (or maximization, depending on the problem) is over all possible decisions $y$ available from state $x$.

The base case is usually $f_{n+1}(x) = 0$ (if $n$ is the last stage) or some terminal cost/reward function.

Example: Shortest Path Problem

Consider finding the shortest path from a starting node S to a destination node D in a directed acyclic graph (DAG) with non-negative edge weights. Dynamic programming can be applied here.

Let $d(v)$ be the length of the shortest path from S to node $v$. We can compute $d(v)$ for all nodes $v$ in topological order.

If we consider nodes in a specific order, say $v_1, v_2, ..., v_N$, where $v_1$ is S:

• $d(v_1) = 0$
• For $k = 2, ..., N$, $d(v_k) = \min \{d(v_i) + w(v_i, v_k)\}$ for all $v_i$ such that there is an edge from $v_i$ to $v_k$, and $w(v_i, v_k)$ is the weight of the edge.

This approach iteratively builds the shortest path distances from the source to all other reachable nodes.

Example: Knapsack Problem

The 0/1 Knapsack problem is a classic example. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. In the 0/1 version, you can either take an item or not.

Let $W$ be the maximum weight capacity of the knapsack.

Let $n$ be the number of items.

Let $w_i$ be the weight of item $i$, and $v_i$ be the value of item $i$.

We define $dp[i][j]$ as the maximum value that can be obtained using the first $i$ items with a knapsack capacity of $j$.

The recurrence relation is:

• If $w_i > j$ (item $i$ is too heavy to fit in a knapsack of capacity $j$):

$$dp[i][j] = dp[i-1][j]$$

• If $w_i \le j$ (item $i$ can fit):

$$dp[i][j] = \max(dp[i-1][j], v_i + dp[i-1][j-w_i])$$

This means we either don't include item $i$ (value is $dp[i-1][j]$) or we include item $i$ (value is $v_i$ plus the maximum value we can get from the remaining capacity $j-w_i$ using the previous $i-1$ items).

The base cases are $dp[0][j] = 0$ for all $j$, and $dp[i][0] = 0$ for all $i$. The final answer is $dp[n][W]$.

Approximation in Function Space

Approximation in function space is a broad area of mathematics that deals with approximating complex functions using simpler, more manageable functions. This is crucial in various fields, including numerical analysis, approximation theory, and functional analysis, where exact solutions are often intractable or computationally too expensive.

The goal is to find a function from a simpler class (e.g., polynomials, splines, trigonometric polynomials) that is "close" to a given function $f$ in some sense. The "closeness" is measured by a norm or a metric defined on the space of functions.

Function Spaces:

A function space is a set of functions, typically equipped with a structure that allows for mathematical operations like addition and scalar multiplication, making it a vector space. Common function spaces include:

• $C[a, b]$: The space of all continuous functions on the interval $[a, b]$, with the maximum norm $\|f\|_\infty = \max_{x \in [a,b]} |f(x)|$.
• $L^p[a, b]$: The space of functions whose $p$-th power is integrable on $[a, b]$, with the $L^p$ norm $\|f\|_p = \left(\int_a^b |f(x)|^p dx\right)^{1/p}$.
• The space of polynomials of degree at most $n$, denoted by $P_n$.

Approximation Methods:

Several methods are used to approximate functions:

1. Polynomial Approximation: Approximating a function $f$ using a polynomial $P(x)$.
• Taylor Polynomials: Provide local approximations around a point. The $n$-th degree Taylor polynomial for $f(x)$ around $a$ is $T_n(x) = \sum_{k=0}^n \frac{f^{(k)}(a)}{k!}(x-a)^k$. This is an exact representation if $f$ is a polynomial of degree at most $n$.
• Weierstrass Approximation Theorem: States that for any continuous function $f$ on $[a, b]$ and any $\epsilon > 0$, there exists a polynomial $P(x)$ such that $|f(x) - P(x)| < \epsilon$ for all $x \in [a, b]$. This guarantees the existence of polynomial approximations but doesn't provide a constructive method for finding the "best" one.
• Chebyshev Polynomials: Offer a way to find the "best" polynomial approximation in the $L_\infty$ norm (minimax approximation). The Chebyshev polynomial of the first kind, $T_n(x)$, has the property that it minimizes the maximum absolute deviation from zero on $[-1, 1]$ among all monic polynomials of degree $n$.
2. Spline Approximation: Using piecewise polynomial functions to approximate a function. Splines are often preferred over global polynomials because they can achieve high accuracy locally without exhibiting the wild oscillations that high-degree polynomials might.
• B-splines: A fundamental basis for spline spaces, offering desirable properties like local support.
• Cubic Splines: Commonly used, providing $C^2$ continuity (continuous second derivatives), which leads to smooth approximations.
3. Trigonometric Approximation: Approximating functions using sums of sines and cosines.
• Fourier Series: For periodic functions, a Fourier series represents the function as an infinite sum of sines and cosines. Truncating this series provides an approximation.

Measures of Approximation Error:

The quality of an approximation is measured by an error criterion. Common error norms include:

• $L_\infty$ (Uniform or Chebyshev) norm: $E_\infty(f, P) = \|f - P\|_\infty = \max_{x \in [a,b]} |f(x) - P(x)|$. Minimizing this norm is called minimax approximation.
• $L_2$ (Root Mean Square) norm: $E_2(f, P) = \|f - P\|_2 = \left(\int_a^b |f(x) - P(x)|^2 dx\right)^{1/2}$. This is related to the method of least squares.
• $L_1$ norm: $E_1(f, P) = \|f - P\|_1 = \int_a^b |f(x) - P(x)| dx$.

Example: Approximating $e^x$ on $[0, 1]$

We want to approximate $f(x) = e^x$ on $[0, 1]$.

Using Taylor Polynomial: The Taylor expansion of $e^x$ around $0$ is $e^x = \sum_{k=0}^\infty \frac{x^k}{k!}$.

Let's use a 3rd-degree Taylor polynomial around $0$: $P_3(x) = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} = 1 + x + 0.5x^2 + 0.1667x^3$.

The error is $R_3(x) = e^x - P_3(x) = \frac{e^c}{(3+1)!}x^{3+1}$ for some $c \in (0, x)$. On $[0, 1]$, the maximum error occurs at $x=1$, where $c \in (0, 1)$. The maximum value of $e^c$ is $e^1 = e$. So, the maximum absolute error is approximately $\frac{e}{24} \approx \frac{2.718}{24} \approx 0.113$.

Using Best Uniform Approximation (Minimax): Finding the polynomial $P(x)$ of degree 3 that minimizes $\max_{x \in [0,1]} |e^x - P(x)|$ is a more complex problem, often solved using algorithms like the Remez algorithm. The resulting polynomial will generally yield a smaller maximum error than the Taylor polynomial.

Successive Approximations

Successive approximations, also known as iterative methods or the method of successive substitutions, is a general technique used to find solutions to equations, particularly those that cannot be solved directly or analytically. It involves starting with an initial guess and iteratively refining it until a desired level of accuracy is reached.

This method is widely applied in solving systems of linear equations, non-linear equations, differential equations, and integral equations.

General Principle:

The core idea is to rewrite the original equation $F(x) = 0$ into an equivalent form $x = G(x)$. Then, we start with an initial guess $x_0$ and generate a sequence of approximations using the iterative formula:

$$x_{k+1} = G(x_k)$$

If the sequence $\{x_k\}$ converges to a limit $x^*$, and $G$ is continuous, then $x^* = G(x^*)$, which means $x^*$ is a solution to the original equation $x = G(x)$.

Convergence Criteria:

For the iterative method $x_{k+1} = G(x_k)$ to converge to a unique solution $x^*$, the function $G(x)$ must satisfy certain conditions in a neighborhood around $x^*$. A common sufficient condition for convergence is that $G(x)$ is a contraction mapping. This means there exists a constant $L < 1$ such that for all $x$ in the neighborhood:

$$|G(x) - G(y)| \le L|x - y|$$

If this condition holds, then the sequence will converge regardless of the initial guess $x_0$ within that neighborhood. The constant $L$ provides a bound on the rate of convergence.

Alternatively, if $|G'(x^*)| < 1$, the iteration will converge locally. If $|G'(x^*)| > 1$, it will diverge. If $|G'(x^*)| = 1$, convergence is not guaranteed.

Applications:

1. Solving Non-linear Equations: Finding roots of equations like $x^2 - \cos(x) = 0$.

Rewrite as $x^2 = \cos(x)$, so $x = \pm \sqrt{\cos(x)}$. This form isn't ideal for iteration. A better form might be $x = \cos(x)/x$ or $x = \arccos(x^2)$, depending on the expected root location. A common rearrangement is $x = \cos(x)$. Let $G(x) = \cos(x)$. If we start with $x_0 = 0.5$, then:

• $x_1 = \cos(0.5) \approx 0.8776$
• $x_2 = \cos(0.8776) \approx 0.6390$
• $x_3 = \cos(0.6390) \approx 0.8021$
• $x_4 = \cos(0.8021) \approx 0.6947$
• ...and so on, converging to the fixed point.

The derivative is $G'(x) = -\sin(x)$. For the root around $0.739$, $|G'(0.739)| = |-\sin(0.739)| \approx |-0.673| < 1$, so convergence is expected.

2. Solving Systems of Linear Equations:

Consider the system $Ax = b$. We can rewrite this using iterative methods like Jacobi or Gauss-Seidel. For example, splitting $A = D + L + U$ (Diagonal, Lower triangular, Upper triangular), we can get:

• Jacobi Method: $x^{(k+1)} = D^{-1}(b - (L+U)x^{(k)})$.
• Gauss-Seidel Method: $(D+L)x^{(k+1)} = b - Ux^{(k)}$.

These methods generate successive approximations for the solution vector $x$. Convergence is often guaranteed if the matrix $A$ is strictly diagonally dominant.

3. Solving Differential Equations:

For an initial value problem $y'(t) = f(t, y(t))$, $y(t_0) = y_0$, Picard's method of successive approximations is used. It converts the differential equation into an integral equation:

$$y(t) = y_0 + \int_{t_0}^t f(\tau, y(\tau)) d\tau$$

The sequence of approximations is defined by:

• $y_0(t) = y_0$ (initial guess)
• $y_{k+1}(t) = y_0 + \int_{t_0}^t f(\tau, y_k(\tau)) d\tau$

Under suitable conditions on $f$ (e.g., Lipschitz continuity), this sequence converges to the unique solution of the differential equation.

Example: Finding $\sqrt{2}$

We want to find $x = \sqrt{2}$. This is equivalent to solving $x^2 = 2$, or $x^2 - 2 = 0$.

We can rewrite $x^2 - 2 = 0$ as $x = 2/x$. Let $G(x) = 2/x$. Starting with $x_0 = 1$:

• $x_1 = G(x_0) = 2/1 = 2$
• $x_2 = G(x_1) = 2/2 = 1$
• $x_3 = G(x_2) = 2/1 = 2$

This iteration oscillates and does not converge. This indicates that $G(x) = 2/x$ is not a suitable function for successive approximations to find $\sqrt{2}$ because it's not a contraction mapping in the relevant interval.

Let's try a different rearrangement of $x^2 - 2 = 0$. A common technique for finding square roots is the Babylonian method, which is a specific case of Newton's method. Newton's method itself can be viewed as a form of successive approximation.

For $f(x) = x^2 - 2$, Newton's iteration is $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{x_k^2 - 2}{2x_k} = x_k - \frac{x_k}{2} + \frac{1}{x_k} = \frac{x_k}{2} + \frac{1}{x_k}$.

Let $G(x) = \frac{x}{2} + \frac{1}{x}$. Start with $x_0 = 1$:

• $x_1 = \frac{1}{2} + \frac{1}{1} = 1.5$
• $x_2 = \frac{1.5}{2} + \frac{1}{1.5} = 0.75 + 0.6667 = 1.4167$
• $x_3 = \frac{1.4167}{2} + \frac{1}{1.4167} = 0.70835 + 0.7059 = 1.41425$

This sequence quickly converges to $\sqrt{2} \approx 1.41421356$. The function $G(x) = \frac{x}{2} + \frac{1}{x}$ satisfies the contraction mapping property for $x \ge \sqrt{2}$.