MATH.20:5 - Archetypal Grounding

MATH.20:5.1 - Bound a shortest path before completing a search

Consider a finite directed graph with nonnegative edge weights and at least one path from s to t. Its shortest path length D is attained: cycles can be removed without increasing length, leaving one of finitely many simple paths.

Any particular s-to-t path of length U gives D≤U. For a lower bound, assign a number p(v) to each node such that, for every edge from u to v,

p(v)-p(u)≤w(u,v).

Along any path, add these inequalities. The intermediate potentials cancel, giving p(t)-p(s)≤path length. Therefore p(t)-p(s)≤D≤U.

Take nodes s,a,b,t and these edges:

The path s-a-t gives U=7. Choose p(s)=0, p(a)=2, p(b)=3, p(t)=4. The edge differences are respectively 2,2,3,1,1, each no larger than its edge weight. Thus 4≤D≤7.

The equality cases suggest s-a-b-t. It has length 4, meeting the lower bound, so D=4. The proof of optimality uses a feasible path and the comparison applying to every path; it does not need a list of every possible path.

Changed condition. Add an edge s-to-t of weight 1. The old potential violates its new edge inequality, since 4>1; its lower bound is invalid for the enlarged graph. The old path still supplies upper bound 4, and the new edge improves that to 1. The potentials p(s)=p(a)=p(b)=0, p(t)=1 satisfy every new edge inequality, proving D=1. Only the comparison affected by the new edge had to be replaced.

MATH.20:5.2 - Convert a residual to the error actually requested

Suppose Ax=b has an invertible linear map A, and an available approximation is xhat. Define its residual by r=A xhat-b. Then

xhat-x=A⁻¹r.

If the chosen vector norm and induced operator norm give ||A⁻¹||≤K, it follows that

||xhat-x||≤K||r||.

The bound K is the missing comparison between residual and solution error. It can come from a proved estimate of the inverse action; forming the entire inverse is unnecessary when a cheaper bound is available.

For a concrete case, A is diagonal with entries 1 and 0.001, b=(1,1), and xhat=(1,999). Use the maximum absolute coordinate as the vector norm. The inverse scales the coordinates by 1 and 1000, so its operator norm is 1000. The residual is (0,-0.001); the bound on solution error is 1. The actual solution (1,1000) attains that error.

A requested error of at most 0.01 therefore requires a residual bound of at most 0.00001 under this comparison. The apparent smallness of 0.001 was insufficient for that request.

Changed condition. Let the second diagonal entry become zero and b=(1,0). The equation fixes the first coordinate and leaves the second arbitrary. Residual zero cannot bound distance to a specified second-coordinate value: solutions with arbitrarily different second coordinates have the same residual. A request about the first coordinate alone is still answerable. Return that determined component or supply an additional condition selecting the second.

The method has derived an error relation and exposed its failure condition. A numerical method can now decide how accurately to obtain the residual and the approximation; the bound itself has not selected a solver.

MATH.20:5.3 - Enclose a set and improve the consequence

Let S be the disk {(x,y): x²+y²≤1}. The work needs the largest value of g(x,y)=x+y, but first seeks cheaper comparable sets.

The diamond L={(x,y): |x|+|y|≤1} lies inside S, because x²+y²≤(|x|+|y|)²≤1. The square U=[-1,1]×[-1,1] contains S, because each coordinate square is at most one. Thus L⊆S⊆U.

Over L, x+y≤|x|+|y|≤1, attained at (1,0). Over U, x+y≤2. Therefore the maximum over S lies between 1 and 2. Its existence follows, for example, from continuity of g on the compact disk.

The point (1,1) attaining the outer bound is outside S. To tighten that bound, retain the relation between the coordinates:

(x+y)²≤2(x²+y²)≤2,

where the first inequality follows from (x-y)²≥0. Hence x+y≤sqrt(2). The point (1/sqrt(2),1/sqrt(2)) belongs to S and attains this value, completing the comparison.

The inner set supplied feasible values; the outer set supplied a restriction on all feasible values. A better inequality and its equality case closed the gap. The same inclusion method can enclose a feasible region, a family of functions or another set, with the corresponding proof of membership and bound on the requested operation.