C.1: Extrapolación de Richardson

Hay muchos procedimientos de aproximación en los que uno primero elige un tamaño de paso\(h\) and then generates an approximation \(A(h)\) to some desired quantity \(\cA\text{.}\) For example, \(\cA\) might be the value of some integral \(\int_a^b f(x)\,\, d{x}\text{.}\) For the trapezoidal rule with \(n\) steps, \(\Delta x=\tfrac{b-a}{n}\) plays the role of the step size. Often the order of the error generated by the procedure is known. This means

\[ \cA=A(h)+Kh^k+K_1h^{k+1}+K_2h^{k+2}+\ \cdots \tag{E1} \nonumber \]

con\(k\) ser alguna constante conocida, llamada el orden del error, y\(K,\ K_1,\ K_2,\ \cdots\) siendo algunas otras constantes (generalmente desconocidas). Si\(A(h)\) es la aproximación a\(\cA=\int_a^b f(x)\,\, d{x}\) producida por la regla trapezoidal con\(\Delta x=h\text{,}\) entonces\(k=2\text{.}\) Si se usa la regla de Simpson,\(k=4\text{.}\)

Primero supongamos que\(h\) es lo suficientemente pequeño como para que los términos\(K'h^{k+1}+K''h^{k+2}+\ \cdots\) en (E1) sean lo suficientemente pequeños ¹ Normalmente, no tenemos acceso a, y no nos importa, el error exacto. Solo nos importa su orden de magnitud. Entonces, si\(h\) is small enough that \(K_1h^{k+1}+K_2h^{k+2}+\ \cdots\) is a factor of at least, for example, one hundred smaller than \(Kh^k\text{,}\) then dropping \(K_1h^{k+1}+K_2h^{k+2}+\ \cdots\) would not bother us at all. eso dejarlos caer esencialmente no tiene impacto. Esto daría

\[ \cA=A(h)+Kh^k \tag{E2} \nonumber \]

Imagínese que sabemos\(k\text{,}\) pero que no sabemos\(A\) o\(K\text{,}\) y pensamos en (E2) como una ecuación que las incógnitas\(\cA\) y\(K\) tienen que resolver. Puede parecer que tenemos una ecuación en las dos incógnitas\(K\text{,}\)\(\cA\text{,}\) pero ese no es el caso. La razón es que (E2) es (esencialmente) verdadero para todas las opciones (suficientemente pequeñas) de\(h\text{.}\) Si escogemos algunos\(h\text{,}\) dicen\(h_1\text{,}\) y usamos el algoritmo para determinar\(A(h_1)\) entonces (E2), con\(h\) reemplazado por\(h_1\text{,}\) da una ecuación en las dos incógnitas\(\cA\) y\(K\text{,}\) y si luego escogemos alguna\(h\text{,}\) palabra diferente\(h_2\text{,}\) y usamos el algoritmo una segunda vez para determinar\(A(h_2)\) entonces (E2), con\(h\) reemplazado por\(h_2\text{,}\) da una segunda ecuación en las dos incógnitas\(\cA\) y\(K\text{.}\) Las dos ecuaciones determinarán entonces ambas\(\cA\) y \(K\text{.}\)

Para ser más concretos, supongamos que hemos escogido algún valor específico de\(h\text{,}\) y hemos elegido\(h_1=h\)\(h_2=\tfrac{h}{2}\text{,}\) y y que hemos evaluado\(A(h)\) y\(A(h/2)\text{.}\) Entonces las dos ecuaciones son

\ begin {align*}\ ca&=A (h) +kH^k\ tag {E3a}\\\ CA&=A (h/2) +K\ grande (\ tfrac {h} {2}\ grande) ^k\ etiqueta {E3b}\ end {align*}

Ahora es fácil de resolver para ambos\(K\) y\(\cA\text{.}\) Para obtener\(K\text{,}\) solo restar (E3b) de (E3a).

\ begin {align*} (\ textrm {E3a}) - (\ textrm {E3b}) :&\ quad 0=A (h) -A (h/2) +\ grande (1-\ tfrac {1} {2^k}\ grande) kh^k\\ implíes&\ quad K=\ frac {A (h/2) -A (h)} {[1-2^ {-k}] h^k}\ etiqueta {E4a}\ final {alinear*}

Para obtener\(\cA\) multiplicar (E3b) por\(2^k\) y luego restar (E3a).

\ begin {alinear*} 2^k (\ textrm {E3b}) - (\ textrm {E3a}) :&\ quad [2^k-1]\ Ca=2^kA (h/2) -A (h)\\\ implíes&\ quad\ Ca=\ frac {2^kA (h/2) -A (h)} {2^k-1}\ etiqueta {E4b}\ end {align*}

La generación de una aproximación “nueva mejorada” para\(\cA\) de dos\(A(h)\) con diferentes valores de\(h\) se llama Richardson ² La extrapolación de Richardson fue introducida por el inglés Lewis Fry Richardson (1881-1953) en 1911. Extrapolación. Aquí hay un resumen

Ecuación C.1.1 Extrapolación de Richardson

Let\(A(h)\) Ser una\(h\) aproximación de tamaño de paso a\(\cA\text{.}\) If

\[ \cA=A(h)+K h^k \nonumber \]

entonces

\[ K=\frac{A(h/2)-A(h)}{[1-2^{-k}]h^k}\qquad \cA=\frac{2^kA(h/2)-A(h)}{2^k-1} \nonumber \]

Esto funciona muy bien ya que, al calcular\(A(h)\) para dos diferentes\(h\), podemos eliminar el mayor término de error en (E1), y así obtener una aproximación mucho más precisa a\(\cA\) por poco trabajo adicional.

Ejemplo C.1.2 Extrapolación de Richardson con la regla trapezoidal

Aplicando la regla trapezoidal (1.11.6) a la integral\(\cA=\int_0^1\frac{4}{1+x^2}\, d{x}\) con tamaños de escalón\(\frac{1}{8}\) y\(\frac{1}{16}\) (es decir, con\(n=8\) y\(n=16\)) da, con\(h=\frac{1}{8}\text{,}\)

\[ A(h)=3.1389884945\qquad A(h/2)=3.1409416120 \nonumber \]

Entonces (E4b), con nos\(k=2\text{,}\) da la aproximación “nueva mejorada”

\[ \frac{2^2\times 3.1409416120 -3.1389884945}{2^2-1}=3.1415926512 \nonumber \]

Vimos en el Ejemplo 1.11.3 que\(\int_0^1\frac{4}{1+x^2}\, d{x}=\pi\text{,}\) así esta nueva aproximación realmente está “mejorada”:

• \(A(1/8)\)está de\(\pi\) acuerdo con dos decimales,
• \(A(1/16)\)está de\(\pi\) acuerdo con tres decimales y
• la nueva aproximación concuerda\(\pi\) con ocho decimales.

Tenga cuidado con eso (E3b),\(\cA=A(h/2)+K\big(\tfrac{h}{2}\big)^k\text{,}\) es decir\(K\big(\frac{h}{2}\big)^k\) es decir que es (aproximadamente) el error en\(A(h/2)\text{,}\) no el error en No se\(\cA\text{.}\) puede obtener una aproximación “aún más mejorada” usando (E4a) para calcular\(K\) y luego agregar\(K\big(\frac{h}{2}\big)^k\) a la “nueva mejorada”\(\cA\) de (E4b) — hacerlo simplemente\(\cA+K\big(\tfrac{h}{2}\big)^k\text{,}\) no da una más precisa\(\cA\text{.}\)

Ejemplo C.1.3 Ejemplo 1.11.16 revisitado

Supongamos nuevamente que deseamos utilizar la regla de Simpson (1.11.9)\(\int_0^1 e^{-x^2}\,\, d{x}\) para evaluar dentro de una precisión de\(10^{-6}\text{,}\) pero que no necesitamos el grado de certeza que nos proporciona el Ejemplo 1.11.16. Observe que necesitamos (aproximadamente) que\(|K|h^4 \lt 10^{-6}\text{,}\) así si podemos estimar\(K\) (usando nuestro truco de Richardson) entonces podemos estimar el requerido\(h\text{.}\) Una estrategia comúnmente utilizada, basada en esta observación, es

• primero aplique la regla de Simpson dos veces con un número relativamente pequeño de pasos y
• luego use (E4a), con\(k=4\text{,}\) para estimar\(K\) y
• luego use la condición\(|K| h^k\le 10^{-6}\) para determinar, aproximadamente, el número de pasos requeridos
• y finalmente aplicar la regla de Simpson con el número de pasos recién determinados.

Implementemos esta estrategia. Primero estimamos\(K\) aplicando la regla de Simpson con tamaños de paso\(\tfrac{1}{4}\) y\(\tfrac{1}{8}\text{.}\) Escribiendo\(\tfrac{1}{4}=h'\text{,}\) obtenemos

\[ A(h')=0.74685538 % 0.746855379790987 \qquad A(h'/2)=0.74682612 %0.746826120527467 \nonumber \]

de manera que (E4a), con\(k=4\) y\(h\) reemplazado por\(h'\text{,}\) rendimientos

\[ K=\frac{0.74682612 - 0.74685538}{[1-2^{-4}](1/4)^4} %=-\frac{0.000031211}{(1/4)^4} =-7.990\times 10^{-3} \nonumber \]

Queremos usar un tamaño de paso\(h\) obedeciendo

\[ |K|h^4\le 10^{-6} \iff 7.990\times 10^{-3} h^4\le 10^{-6} \iff h \le\root{4}\of{\frac{1}{7990}} =\frac{1}{9.45} \nonumber \]

como, por ejemplo,\(h=\tfrac{1}{10}\text{.}\) Aplicando la regla de Simpson con\(h=\tfrac{1}{10}\) da

\[ A(1/10) = 0.74682495 \nonumber \]

La respuesta exacta, a ocho decimales, es\(0.74682413\) así que el error en\(A(1/10)\) es de hecho poco menos\(10^{-6}\text{.}\)

Supongamos ahora que cambiamos de opinión. Queremos una precisión de\(10^{-12}\text{,}\) en lugar de Ya\(10^{-6}\text{.}\) hemos estimado\(K\text{.}\) Así que ahora queremos usar un tamaño de paso\(h\) obedeciendo

\ begin {align*} |k|h^4\ le 10^ {-12} &\ iff 7.99\ times 10^ {-3} h^4\ le 10^ {-12}\ &\ iff h\ le\ raíz {4}\ de {\ frac {1} {7.99\ times 10^9}} =\ frac {1} {299.0}\ end {align*}

como, por ejemplo,\(h=\tfrac{1}{300}\text{.}\) Aplicando la regla de Simpson con\(h=\tfrac{1}{300}\) da, a catorce decimales,

\[ A(1/300) = 0.74682413281344 \nonumber \]

La respuesta exacta, a catorce decimales, es\(0.74682413281243\) así que el error en\(A(1/300)\) es de hecho poco más\(10^{-12}\text{.}\)