Newton ' método s para raíces cuadradas - precisión dígito (ejercicio de Cheney ' s análisis numérico)

Question

Te agradecería mucho un poco de ayuda para este ejercicio en Kincaid y Cheney Análisis Numérico: "aplicar el método de Newton a $f(x)=x^2-r$ (donde $r>0$). Probar que si $x_n$ $k$ correcto de dígitos después del punto decimal, entonces el $x_{n+1}$ tiene al menos $2k-1$ correcto dígitos, mientras $r>0.006$$k\geq 1$".

En general, si $f''$ es continua y $r$ es una raíz simple de $f$ sostiene que $e_{n+1}=x_{n+1}-\sqrt{r}=\frac{1}{2}\frac{f''(\xi_n)}{f'(x_n)}e_n^2$ donde $\xi_n$ es un número entre el$x_n$$\sqrt{r}$.

Supongo que la condición de que ellos están pidiendo es alcanzado (pero no estoy seguro) cuando $e_{n+1}<e_n^2$. La aplicación de la fórmula anterior da $e_{n+1}=\frac{1}{2x_n}e_n^2<\frac{1}{2r}e_n^2$; esto parece suficiente para encontrar $r$. No sé de donde la $0.006$ proviene.

Por otro lado, el libro de texto sugiere la utilización de $x_{n+1}=\frac{1}{2}(x_n+\frac{r}{x_n}).$ Esta expresión puede ser transformado en uno que involucra $e_{n+1}$ $e_n$ pero no sé cómo hacerlo, de modo que sería más útil que la anterior obligado.

Gracias de antemano por cualquier ayuda.

Answer 1

Por favor, no se desanime por la longitud de la respuesta. Yo no tengo el tiempo para hacerlo más corto!

Considero que se supone asumir y utilizar el resultado general que usted cita, que comienza con "En general".

Uno realmente tiene lo que dijo uno de los medios por $e_k$. A partir de la expresión que usted cita, $e_n$ debe $x_n-\sqrt{r}$.

Así que vamos a empezar a trabajar con el presupuesto. En nuestro caso, tenemos $f(x)=x^2-r$. Por lo $f'(x)=2x$$f''(x)=2$. Por lo tanto para las raíces cuadradas de la general estimación del error se simplifica a $$e_{n+1}=\frac{1}{2}\frac{2}{2x_n}e_n^2=\frac{1}{2x_n}e_n^2$$

Finalmente, se quiere obtener algún tipo de control sobre el término $1/(2x_n)$. Queremos demostrar que esto no es gran.

Supongamos ahora que $x_n$ $k$ correcto de dígitos después del punto decimal. Por lo $|e_n| <0.5\times 10^{-k}$. Eso significa que $$\sqrt{r}-0.5\times 10^{-k} <x_n< \sqrt{r}+0.5\times 10^{-k}$$ Queremos mostrar que $1/(2x_n)$ no es demasiado grande. Si somos pesimistas, suponemos que $x_n$ es incluso menor que la estimación anterior permite. Así que si en nuestro error fórmula tomamos $x_n=\sqrt{r}-0.5\times 10^{-k}$, vamos a obtener una estimación del error que es tan pesimista como sea posible.
Llegamos a la conclusión de que $$|e_{n+1}|<\frac{1}{|2\sqrt{r}-10^{-k}|}(0.5)^2(10^{-2k})$$

Ahora nos preguntamos: ¿cuál es el más pequeño que el$|2\sqrt{r}-10^{-k}|$, posiblemente, podría ser? Que pasaría si $\sqrt{r}$ eran tan pequeños como sea posible, y $10^{-k}$ eran tan grandes como sea posible. Recordemos que $r >.006$, lo $\sqrt{r}>0.077$. Recordemos también que $k\ge 1$, lo $10^{-k}\le 1/10$. De ello se deduce (calculadora) que $$\frac{1}{|2\sqrt{r}-10^{-k}|} <\frac{1}{0.154-0.1} <18.52$$ Llegamos a la conclusión de que $$|e_{n+1}|<(18.52)(0.5)^2(10^{-2k}) <0.464 \times 10^{-(2k-1)}$$ Esta estimación dice que la estimación de $x_{n+1}$ es correcta a, al menos, $2k-1$ decimales.

Estábamos tan pesimista como sea posible, dado que la información sobre $r$. Usted puede ver más de cerca el análisis de que el error se comporta un poco mejor si empezamos por encima de $\sqrt{r}$ que si nos ponemos a continuación. la razón por la que tuvo que insistir en que $r$ no estar demasiado cerca de $0$ es que en ese caso, $1/(|2\sqrt{r}-10^{-k}|)$ podría ser grande.