Así que estoy estudiando SICP (Estructura e Interpretación de los Programas de Ordenador) y haciendo uno de los ejercicios que se basa en el punto fijo método para encontrar el punto fijo de $f(x)$. En un determinado ejercicio pregunta se le pide para encontrar la raíz de $x^x = 1000$ por el método de punto fijo. Así que lo transformó en algo parecido a $ x = \frac{\log 1000}{\log x} $, para el uso de la mano derecha de funcionar como una entrada para el método. Por lo que se describen dos formas de estimar la próxima supongo que una es $x_{n+1} = f(x_n)$ y la otra es $x_{n+1} = \frac{1}{2}(x_n + f(x_n))$. Traté de encontrar los puntos fijos de otras funciones también , parece que le gusta siempre el segundo método converge rápidamente. Es éste siempre el caso, o sólo una coincidencia, que podría fallar por otras funciones o hay una rigurosa prueba de por qué sucede esto ?
Respuestas
¿Demasiados anuncios?
Promedio de esta manera no siempre acelerar el proceso, pero yo no diría que es sólo una coincidencia. De hecho, podemos determinar exactamente cuando este proceso ayudará a que mediante el examen de la derivada de $f$ en el punto fijo.
Supongamos que $x_0$ es un punto fijo de $f$. Por lo tanto, $f(x_0)=x_0$. Deje $\lambda=f'(x_0)$. Decimos que $x_0$ es
- atractiva si $|\lambda|<1$,
- repulsivo si $|\lambda|>1$, o
- neutro si $|\lambda|=1$.
En el atractivo caso, el valor de $\lambda$ indica que la tasa de atracción. Específicamente, $$\left|f^n(x)-x_0\right| \sim |\lambda|^n\left|x-x_0\right|.$$ Al $\lambda=0$, la tasa de atracción es mejor que la exponencial para cualquier base. Este caso es a veces llamado super-atractivo.
Ahora vamos a $F(x)=(x+f(x))/2$. A continuación, $$F'(x_0) = \frac{1+\lambda}{2}.$$
Ahora, en su caso $$f(x)=\log(1000)/\log(x), \: x_0 \approx 4.555, \text{ and } \: f'(x_0) \approx -0.659.$$ Thus, $F'(x_0) \aprox 0.170259$ y vemos la aceleración.
Para producir un contra-ejemplo a tu conjetura, simplemente necesitamos una función de $f$ con un punto fijo $x_0$ donde $f'(x_0) = 0$. Para ser concretos, vamos a $f(x)=2x(1-x)$. Entonces $f(1/2)=1/2$, $f'(1/2) = 0$, y $F'(1/2)=1/2$. Por lo tanto, la convergencia de la iteración de $f$ se debe más rápido que el de $F$. Permite demostrar, a través de la iteración tanto de $x_1=0.4$: $$ \begin{array}{l|l|l} \text{} & f^n\text{(0.4)} & F^n\text{(0.4)} \\ \hline 0 & 0.4 & 0.4 \\ 1 & 0.48 & 0.44 \\ 2 & 0.4992 & 0.4664 \\ 3 & 0.499999 & 0.482071 \\ 4 & 0.5 & 0.490714 \\ 5 & 0.5 & 0.495271 \\ 6 & 0.5 & 0.497613 \\ \end{array} $$
En general, podemos esperar que este promedio técnica para mejorar la convergencia exactamente cuando $$\left|\frac{1+\lambda}{2}\right| < \min(1,\left|\lambda\right|).$$ Al $\lambda$ es real esto significa que $-3<\lambda<-1/3$. En caso de que $-3<\lambda<-1$, la iteración de $f$ no se puede esperar a converger a $x_0$ aún iteración de $F$.
Me gustaría añadir otra respuesta, ya que hubo un poco de confusión con el signo de $\lambda$ en la respuesta de la Marca de McClure. Sin embargo, en general estoy de acuerdo con su respuesta.
Asumir, que la iteración de punto fijo dado por $x^{k+1} =f(x^k)$ oscila alrededor del punto fijo $x^*$ que satisface $x^*=f(x^*)$. Esto significa, que si $x^*-x^k<0$ $x^*-x^{k+1}=x^*-f(x^k)>0$ y viceversa. Sin embargo, todavía queremos $f$ a ser contractiva, es decir, \begin{align} |f(x)-f(y)| \leq \lambda |x-y| \end{align} con $\lambda \in [0,1)$.
Consideremos ahora su promedio de iteración $x^{k+1} = \frac12(x^k+f(x^k))$ cuando el promedio no iteración oscila. A continuación, el error está dado por \begin{align} |x^*-x^{k+1}|&=|x^*- \frac12(x^k+f(x^k))| \\ &=\frac12|x^*-x^k+x^*-f(x^k)| \\ &=\frac12|x^*-x^k+f(x^*)-f(x^k)| \end{align} Sabemos, que $x^*-x^k$ $f(x^*)-f(x^k)$ tienen distinto signo. W. l.o.g. suponga $x^*-x^k>0$,$0>f(x^*)-f(x^k) = -\lambda (x^*-x^k)$. Así \begin{align} \frac12|x^*-x^k+f(x^*)-f(x^k)| &\leq \frac12 |x^*-x^k-\lambda(x^*-x^k)| \\ &=\frac12 |1-\lambda||x^*-x^k| \end{align} Así llegamos a la conclusión, que para el esquema original, tenemos \begin{align} |x^*-x^{k+1}| \leq\lambda |x^*-x^k| \end{align} y para el promedio de esquema \begin{align} |x^*-x^{k+1}| \leq\frac12|1-\lambda| |x^*-x^k| \end{align} Así, por $\lambda<1/3$ el esquema inicial converge más rápido que el promedio, sin embargo, para $1/3\leq \lambda <1$ tenemos $\frac12|1-\lambda|<1$. Por lo tanto el promedio de esquema de converge, incluso si el esquema inicial no si $1<\lambda<3$.
Esta respuesta debe ser una pequeña extensión de la respuesta de Marc McClure para el caso de que el original de la iteración oscila alrededor del punto fijo.
