Physics

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

1 \section{Refinement cancellation and the cost of extrapolation}
2 \label{f:extrapolation}
3 Coarsening a packet atlas combines exact components of one description. A different use of refinement compares approximations made at several scales. The distinction matters. An algebraic cancellation of leading error terms requires an expansion in a common vector space, and a useful numerical result also requires control of the remaining error and of the sample perturbations.
4 
5 Let $E$ be a real normed vector space and let $f(h)\in E$ be defined for $0<|h|<\delta$. Fix a refinement ratio $b>1$. If $f(h)$ represents operators on different Hilbert spaces, comparison maps must first place them in a common space where the following additions are meaningful. The formulas alone do not construct those maps.
6 
7 The denominators below are positive. Each level is a finite linear combination of the original samples at successively refined scales.
8 
9 \begin{definition}[The actual refinement tower]
10 Set $T_0f(h)=f(h)$ and, for $m\geq0$, define
11 \[
12  T_{m+1}f(h)=\frac{b^{m+1}T_mf(h/b)-T_mf(h)}{b^{m+1}-1}.
13 \]
14 \end{definition}
15 
16 \begin{proposition}[Exact response of a monomial]
17 For $r\in\N$ and $v\in E$,
18 \[
19  T_m(h^rv)=c_{m,r}h^rv,\qquad
20  c_{m,r}=\prod_{k=1}^{m}\frac{b^{k-r}-1}{b^k-1}.
21 \]
22 The empty product equals one. In particular, $c_{m,0}=1$, and $c_{m,r}=0$ for $1\leq r\leq m$.
23 \end{proposition}
24 \begin{proof}
25 At level zero the assertion is the definition. If it holds at level $m$, the next recursion multiplies the coefficient by
26 \[
27  \frac{b^{m+1}b^{-r}-1}{b^{m+1}-1}.
28 \]
29 This appends the next factor to the product. For $r=0$, each factor equals one. For $1\leq r\leq m$, the factor at $k=r$ vanishes.
30 \end{proof}
31 
32 Suppose that a finite expansion is available,
33 \[
34  f(h)=F+\sum_{r=1}^{m}h^rv_r+R(h).
35 \]
36 Linearity and the proposition give the exact identity
37 \[
38  T_mf(h)-F=T_mR(h).
39 \]
40 Only a finite sum has been used. No convergence of an infinite formal series is needed. The size of the right-hand side remains an analytic question.
41 
42 \Needspace{18\baselineskip}
43 \begin{theorem}[A quantified remainder and perturbation bound]
44 Let $p$ be a nonnegative integer and suppose
45 \[
46  \norm{R(h)}\leq C|h|^p,\qquad
47  \norm{g(h)-f(h)}\leq\varepsilon
48  \quad(0<|h|<\delta),
49 \]
50 where $C,\varepsilon\geq0$. Define
51 \[
52  A_{m,p}=\prod_{k=1}^{m}\frac{b^{k-p}+1}{b^k-1}.
53 \]
54 Then, throughout the same punctured interval,
55 \[
56  \norm{T_mg(h)-F}\leq A_{m,p}C|h|^p+A_{m,0}\varepsilon.
57 \]
58 \end{theorem}
59 \begin{proof}
60 The interval is stable under $h\mapsto h/b$. The triangle inequality applied to one tower step gives
61 \[
62  \norm{T_{m+1}R(h)}\leq
63  \frac{b^{m+1}\norm{T_mR(h/b)}+\norm{T_mR(h)}}{b^{m+1}-1}.
64 \]
65 Starting with the stated remainder bound and proceeding by induction multiplies its constant at step $m+1$ by $(b^{m+1-p}+1)/(b^{m+1}-1)$. Hence $\norm{T_mR(h)}\leq A_{m,p}C|h|^p$. Apply the same argument with $p=0$ to $g-f$. Linearity and the triangle inequality separate the two contributions.
66 \end{proof}
67 
68 When $p=m+1$, this proves the expected order improvement under an explicit remainder hypothesis. It also retains the effect of noisy samples. Each factor in $A_{m,0}$ exceeds one, so extrapolation can amplify a uniform sample error even while cancelling several deterministic powers of $h$.
69 
70 \subsection{A complete three-level example}
71 For $b=2$, direct substitution gives
72 \begin{align*}
73  T_1f(h)&=2f(h/2)-f(h),\\
74  T_2f(h)&=\frac{8f(h/4)-6f(h/2)+f(h)}{3},\\
75  T_3f(h)&=\frac{64f(h/8)-56f(h/4)+14f(h/2)-f(h)}{21}.
76 \end{align*}
77 Take the exact scalar polynomial $f(h)=1+2h-3h^2+4h^3$. The responses are
78 \[
79  T_1f(h)=1+\frac32h^2-3h^3,\qquad
80  T_2f(h)=1+\frac12h^3,\qquad T_3f(h)=1.
81 \]
82 These are polynomial identities for every real $h$. If each of the three samples used by $T_2$ has absolute error at most $\varepsilon$, its output error is at most
83 \[
84  \frac{8+6+1}{3}\varepsilon=5\varepsilon.
85 \]
86 This bound is attained by errors with signs matching the three weights. Thus exact removal of the first two powers does not imply a contraction on arbitrary perturbations. For the displayed polynomial, the perturbed second-level approximation has the explicit total bound $|h|^3/2+5\varepsilon$.
87 
88 The calculation supplies a practical reading rule for later refinement claims. An exact coefficient identity, an asymptotic remainder estimate, and a stability bound are separate pieces of evidence. A physical approximation uses all three, together with the comparison maps that make its values commensurable.
89 
90 

Back to source controls

Back to Physics