El método de Newton - encontrar el punto de partida adecuado

Question

Tengo algunos problemas para resolver un problema en mi libro de texto:

Dada la siguiente función: $$f(x) = x^{-1} - R$$ Suponga $R > 0$. Escribir un breve algoritmo para encontrar $1/R$ por el método de Newton aplicado a $f$. No use la división o la exponenciación en el algoritmo. Para los positivos $R$, lo que los puntos de partida son adecuados?

OK, así que me las he arreglado para resolver la primera parte del problema. Utilizando el método de Newton y reordenando términos que he conseguido:

$$x_{n+1} = x_{n}(2 - Rx_{n})$$

Este es correcta según el libro, y puedo usar mi algoritmo estándar para el método de Newton con esta expresión. Hasta ahora tan bueno.

El problema es la segunda parte, donde se supone que debo encontrar un punto de partida. Me imaginé que si $x_{1} = -x_{0}$, luego las iteraciones del ciclo. Así que luego me sale:

$$\begin{align*} -x_{0} &= x_{0}(2 - Rx_{0})\\ -3x_{0} &= - Rx_{0}^2\\ -3 &= -Rx_{0}\\ x_{0} &= 3/R \end{align*}$$

Por lo tanto, mi respuesta sería que debemos tener $x_{0} < 3/R$. Mi libro, sin embargo, dice:

Si $R > 1$, entonces el punto de partida $x_{0}$ debe estar cerca de la $0$ pero menor que $1/R$.

Entonces, ¿qué hay de malo en mi razonamiento aquí? Si alguien me puede ayudar, lo agradecería muchísimo!

Answer 1

Presumo que la restricción sobre la división se aplica a la elección de un punto de partida así?

La función de $f$ es estrictamente decreciente en el dominio $(0,\infty)$, $\lim_{x \downarrow 0} f(x) = \infty$, $\lim_{x\to \infty} f(x) = -R$, por lo tanto, no existe una única $x^*$ tal que $f(x^*) = 0$. La imagen a continuación muestra el comportamiento de $R=10$.

Además, $f$ es estrictamente convexa en su dominio, lo que significa que, en este caso, si una iteración $x_n$ satisface $x_n < x^*$, entonces es fácil mostrar que $x_n < x_{n+1} \leq x^*$. Además, si $x_n>x^*$, y si $x_{n+1}$ se encuentra en el dominio de $f$,$x_{n+1} \leq x^*$.

Así, la única restricción real en un punto de partida es asegurarse de que $x_1 \in (0, \infty)$, de modo que las iteraciones posteriores están bien definidos. En este caso, usted tiene $x_1 = x_0(2-R x_0)$, dando $x_1>0$ fib $x_0 < \frac{2}{R}$.

Así que la respuesta es que el método de Newton se reunirán el fib de empezar con $0 < x_0 < \frac{2}{R}$ o, ya que no se permite la división, elija $x_0>0$ tal que $R x_0 < 2$.

Es instructivo mirar la iteración de Newton sí mismo. En este caso, $\phi(x) = x(2-Rx)$ define el esquema de iteración (es decir, $\phi_{n+1} = \phi(x_n)$). Sabemos que la solución es un punto fijo de $\phi$$\phi(\frac{1}{R}) = \frac{1}{R}$, lo que da $\phi(x) - \phi(\frac{1}{R}) = - R (x-\frac{1}{R})^2$. Así que tenemos $|\phi(x) - \phi(\frac{1}{R})| = (R |x-\frac{1}{R}|) |x-\frac{1}{R}|$. Esta es una contracción cada vez que $x \in (0, \frac{2}{R})$. Sin embargo, como $x$ se acerca a $\frac{1}{R}$, el 'error' del término (es decir, la distancia entre el $x_n$ y la solución de $\frac{1}{R}$) de las gotas con el cuadrado del error anterior (haciendo caso omiso de la $R$ por simplicidad), que da el método de Newton su llamado cuadrática tasa de convergencia.

Answer 2

Los puntos que usted puede converger a donde se

$$x=x(2-Rx)$$ $$x=0\ \text{ or }\ x=\frac 1 R$$

Lo que quieres son los puntos donde la aplicación de la función se acercarán a $\frac 1 R$ de lo que eran anteriormente. Así que lo que quieres es donde:

$$|f(x+\epsilon)-f(x)|<|\epsilon|$$

Así que si usted se muda $\epsilon$ $x$ (aquí se $x=\frac 1 R$), la aplicación de la función que lleva más de cerca. Para que esto funcione de una manera estable, se debe trabajar para arbitrariamente pequeño $\epsilon$. Aplicando esto a su relación de recurrencia:

$$f(x)=x(2-Rx)$$ $$(x+\epsilon)(2-Rx-R\epsilon)-x(2-Rx)<\epsilon$$

$$2\epsilon-2Rx\epsilon-R\epsilon^2<\epsilon$$ $$2-2Rx-R\epsilon<1,\ \ \epsilon>0$$ $$2-2Rx-R\epsilon>1, \epsilon<0$$ conectar $x=\frac 1 R$, obtenemos que $$|\epsilon|<\frac 1 R$$

Para los puntos dentro de $(0,\frac 2 R)$ convergerán a$\frac 1 R$. Por lo que puedo decir (he comprobado un par de valores de $R$ en un equipo) esto parece funcionar.

Answer 3

Funciona también para $x_0 > 1/R$, pero tal vez la convergencia no es el más rápido. Mira lo que sucede por varias $x-0$ en Newtons iteración, como Ed sugirió.

1. Para $x_0 < 0$ solución diverge. Por supuesto: $x_0(2-Rx_0) < x_0$.
2. Para $x_n \geq 2/R$ obtener $x_n < 0$ y solución diverge.

(tangente siempre cruz del eje x, a menos que si $f'(x) = 0$, lo que sólo es cierto para $x \rightarrow \infty$)

Ahora, inserte $x_0 = 1/R + \Delta x, \Delta x > 0$: $$ (1/R + \Delta x)(2 - R(1/R+\Delta x)) $$ $$ 1/R (1+R\Delta x)(1-R\Delta x) = 1/R - \Delta x^2 R $$ Aviso, que se obtiene el mismo resultado si $x_0 = 1/R - \Delta x$. Esta pruebas, que la velocidad de convergencia es el mismo para $1/R + \Delta x$$1/R - \Delta x$, debido a $x_1$ son los mismos. También la inserción de $\Delta x > \pm 1/R$ le da la divergencia.

Tal vez hay razones por las que debería ser $x_0 < 1/R$ (por ejemplo, la velocidad de convergencia). Usted puede experimentar con el código siguiente en Mathematica o Wolfram Alpha (insertar números en lugar de R, x_0, max_n):

NestList[N [# (2 - R*#)] &, x_0, max_n]

Answer 4

La función de $f(x) = x^{-1}$ es monótonamente decreciente para $x > 0$. El método de Newton funciona siguiendo una recta tangente a la función en un cierto punto al eje de las x, la informática, el cruce por cero de la recta tangente, y repitiendo el proceso en que el nuevo valor.

¿Qué pasa si usted toma un gran valor inicial para $x_0$, decir $x_0 > 1/R$? Dibuje una recta tangente, y seguir de nuevo a la $x$-eje. No puede cruzar la $x$-eje en cualquier punto de $x > 0$. Que te pone en toda una región diferente de la función de $1/x$, y puede que no siempre convergen a su raíz.