Autor Tema: Límites de error del Método de Newton

0 Usuarios y 1 Visitante están viendo este tema.

21 Enero, 2022, 09:09 pm
Leído 349 veces

Marcos Castillo

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,277
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola, estimado Rincón

Me he liado la manta tirando del hilo con una cita del libro de texto. Cito primero

Citar
TEOREMA 7 Límites de error del Método de Newton
Supongamos que \( f \), \( f' \) y \( f'' \) son continuas en un intervalo \( I \) que contiene a \( x_n \), \( x_{n+1} \) y a una raíz \( x=r \) de \( f(x)=0 \). Supongamos también que existen constantes \( K \) y \( L>0 \) tales que para todo \( x \) perteneciente a \( I \) se cumple

(i) \( |f''(x)\leq{K}| \) y

(ii) \( |f'(x)|\geq{L} \)

Entonces,

(a) \( |x_{n+1}-r|\leq{\dfrac{K}{2L}|x_{n+1}-x_n|^2} \) y

(b) \( |x_{n+1}-r|\leq{\dfrac{K}{2L}|x_{n}-r|^2} \)

Las condiciones (i) y (ii) aseguran que cerca de \( r \) la pendiente de \( y=f(x) \) no es demasiado pequeña y que no cambia con  demasiada rapidez. Si \( K/(2L)<1 \), el teorema demuestra que \( x_n \) converge rápidamente a \( r \) cuando \( n \) se hace lo suficientemente grande para que \( |x_n-r|<1 \).

La demostración del Teorema 7 depende del Teorema del Valor Medio. No la daremos aquí ya que este teorema es de uso práctico limitado. (...)

Y vengo yo y encuentro un texto en inglés que lo explica; y además me hago un lío

Dos problemas: está en inglés, y no lo entiendo; y pregunta: ¿alguien podría proporcionarme un texto en castellano que me lo explicara?
Un tercer problema: voy a adjuntar el texto en inglés, pero desconozco si es un enlace.

Bueno, ahí va. ¡Un saludo! 
No man is an island (John Donne)

21 Enero, 2022, 09:58 pm
Respuesta #1

Abdulai

  • Moderador Global
  • Mensajes: 2,662
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
El traductor de google te traduce PDFs, pero no le gusta la simbología extraña (la matemática :) ) , asi que para leerlo vas a tener que tener abiertos/impresos los dos textos: El traducido para el texto y el en inglés para las fórmulas.

23 Enero, 2022, 12:38 pm
Respuesta #2

Marcos Castillo

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,277
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola, estimado Rincón

He tirado por la calle del medio. He intentado traducir el texto, y concretar las dudas resaltando en rojo o subrayando allí donde tengo dudas. Y finalmente, las preguntas.

0.1 Método de Newton y el Teorema del Valor Medio

El método de Newton para calcular los ceros de funciones es un buen ejemplo de aplicación práctica del Teorema del Valor Medio. Sea \( f(x) \) una función real con dos derivadas continuas. Buscamos una raíz de \( f \), es decir, un punto \( \hat{x} \) tal que \( f(\hat{x})=0 \). En el método de Newton, el cual es geométrico, consideramos la curva \( y=f(x) \). Esta curva cruza el eje \( x \) en el punto \( (x,f(x)) \). Sea \( x_0 \) la estimación inicial para la raíz. Para mejorar en la estimación dibujamos la línea tangente a la curva \( y=f(x) \) que pasa sobre el punto \( (x_0,f(x_0)) \) de la curva. Esta línea tangente satisface la ecuación

\( y-f(x_0)=f'(x_0)(x-x_0) \)

La línea tangente atraviesa el eje \( x \) en el punto

\( x_1=x_0-\dfrac{f(x_0)}{f'(x_0)} \)

y tomamos \( x_1 \) como nuestra estimación mejorada de la raíz \( \hat{x} \). Ahora repetimos con \( x_1 \) este procedimiento para obtener una estima mejorada \( x_2 \), y así sucesivamente. Por lo tanto tenemos la secuencia \( \{x_n\} \) tal que

\( x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}\qquad{n=0,1,...,} \)

Necesitamos dar condiciones que garanticen que la secuencia convergerá a una raíz de \( f(x) \), y den información acerca de la tasa de convergencia. Para analizar este procedimiento definimos una función apropiada \( T(x) \) de esta forma

\( T(x)=x-\dfrac{f(x)}{f'(x)} \)

Todavía no estableceremos el dominio \( D \) de esta función, pero es claro que requiere \( f'(x)\neq{0} \) para todo \( x\in{D} \). Entonces \( \hat{x} \) será un punto fijo de \( T \) (\( T(\hat{x})=\hat{x} \)) si y sólo si \( f(\hat{x})=0 \). Para obtener la tasa de crecimiento de la iteración calculamos la derivada de \( T(x) \):

\( T'(x)=\dfrac{f(x)f''(x)}{[f'(x)]^2} \)

Como \( T'(\hat{x})=0 \), en la vecindad de la raíz seremos capaces de seleccionar una constante de decaimiento \( c<1 \), tal que la raíz sea un benevolente punto fijo de \( T \). En particular sea \( D=[\hat{x}-r,\hat{x}+r] \), donde \( |T'(x)|\leq{c<1} \) para todo \( x\in{D} \). (Si \( f'(\hat{x})\neq{0} \) siempre podemos encontrar una \( r \) tal que la desigualdad se cumpla para la constante \( c \) dada). Entonces si \( u,v\in{D} \), el Teorema del Valor Medio da \( T(u)-T(v)=T'(\tilde{u})(u-v) \), para algún \( \tilde{u}\in{D} \) entre \( u \) y \( v \). Por lo tanto \( |T(u)-T(v)|\leq{c\;|u-v|} \) para todo \( u,v\in{D} \). En particular

\( |x_n-\hat{x}|\leq\;c\;|x_{n-1}-\hat{x}|\leq...\leq\;c^n\;|x_0-\hat{x}| \)

Por lo tanto si \( x_0\in{D} \) entonces así son todos los \( x_n\in{D} \) y \( x_n\rightarrow{\hat{x}} \) cuando \( n\rightarrow{\infty} \)

La convergencia del algoritmo de Newton es de hecho mucho más rápido que el indicado desde este análisis. Esto se debe al hecho de que \( T'(\hat{x})=0 \). Podemos, de hecho, probar convergencia cuadrática.

Supongamos que podemos que podemos encontrar \( A,\;B \), números finitos positivos tal que \( B>|f''(x)| \) para todo \( x\in{D} \), y \( A<|f'(x)| \) para todo \( x\in{D} \), y establezcamos \( C=B/A \). Por el Teorema del Valor Medio hay un punto \( \tilde{x}_n\in{D} \), entre \( \hat{x} \) y \( x_n \), tal que

\( f(x_n)=f(x_n)-f(\hat{x})=f'(\tilde{x}_n)(x_n-\hat{x}) \)

así \( x_n-\hat{x}=f(x_n)/f(\hat{x}_n) \). Además, el Teorema del Valor Medio aplicado a \( f'(x) \) depara un punto \( \breve{x}_n \) entre \( x_n \) y \( \tilde{x}_n \) tal que

\( \color{red}f'(x_n)-f'(\tilde{x}_n)=f''(\breve{x}_n)(x_n-\tilde{x}_n) \)

Entonces

\( |x_{n+1}-\hat{x}|=|(x_{n+1}-x_n)+(x_n-\hat{x})|=\left |{\dfrac{f(x_n)}{f'(\tilde{x}_n)}-\dfrac{f(x_n}{f'(x_n)}}\right | \)

\( \left |{\dfrac{f(x_n)}{f'(x_n)f'(\tilde{x}_n)}\left({f'(x_n)-f'(\tilde{x}_n)}\right)}\right |=\left |{\dfrac{x_n-\hat{x}}{f'(x_n)}(f'(x_n)-f'(\tilde{x}_n))}\right | \)

\( \left |{(x_n-\tilde{x}_n)(x_n-\hat{x})\dfrac{f''(\color{green}\breve{x}_n\color{black})}{f'(x_n)}}\right |\color{red}\leq{C\color{black}\;|x_n-\hat{x}|^2} \)

Por lo tanto \( |x_{n+1}-\hat{x}|\leq{C\;|x_n-\hat{x}|^2} \) y la convergencia es cuadrática. Esto significa que el número de dígitos de precisión en nuestra aproximación casi dobla con cada iteración.

Ejemplo 1 Aproximamos \( \sqrt{7} \) empleando el método de Newton para encontrar la raíz positiva de la función

\( f(x)=x^2-7 \)

Aquí el paso de iteración es dado por la función

\( T(x)=x-\dfrac{f(x)}{f'(x)}=\dfrac{x}{2}+\dfrac{7}{2x} \)

Sea \( D=\{x:2\leq x\leq 7\} \) y elegimos la aproximación inicial \( x_0=2 \). Nótese que

\( \left |{\dfrac{f(x)f''(x)}{(f'(x))^2}}\right |=\left |{\dfrac{x}{2}+\dfrac{7}{2x}}\right |\leq{\dfrac{3}{8}}=c \)

Para \( x\in{D} \). Por lo tanto

\( |x_n-\color{red}\sqrt{2}\color{black}|\leq\dfrac{3}{8}|x_{n-1}-\sqrt{7}|\leq\;...\;\leq\left({\dfrac{3}{8}}\right)^n|2-\sqrt{7}|\rightarrow{0} \)

cuando \( n\rightarrow{\infty} \). La tasa de convergencia es más rápida que esta, sin embargo. Realmente \( |f''(x)|=2=B \) y \( |f'(x)|=|2x|\geq 4=A \) para todo \( x\in{D} \). Por lo tanto, estableciendo \( C=\dfrac{B}{A}=\dfrac{1}{2} \), tenemos

\( |x_{n+1}-\sqrt{7}|\leq\dfrac{1}{2}|x_n-\sqrt{7}|^2\qquad{n=0,1,...,} \)

y el número de dígitos de precisión garantizada más que se duplica con cada iteración. Realmente, tenemos (calculando los primeros 10 dígitos)

\( x_0=2 \)
\( x_1=2.75 \)
\( x_2=2.647727273 \)
\( x_3=2.645752048 \)
\( x_4=2.645751311 \)

Aquí, \( x_4 \) es correcto hasta más de 10 dígitos (si calculamos a tantos decimales) y \( (x_4)^2=7.0000000000 \). Como \( x_3 \) tiene 6 dígitos de precisión, \( x_5 \) tendría 24 dígitos de precisión.

Preguntas

1- ¿Por qué \( C\in{\Bbb Q} \)?¿por qué \( B<A \)?
2- El Teorema del Valor Medio, ¿se puede aplicar a primeras, segundas,... derivadas, como lo hace en este caso?
3- En el ejemplo, para determinar \( A \) y \( B \), emplea la negación de lo que afirma en la teoría. ¿Cómo se concilian los dos enunciados?
4- He resaltado \( \sqrt{2} \). ¿Es una errata?.

¡Un saludo!

Editado en verde
No man is an island (John Donne)

23 Enero, 2022, 07:47 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,075
  • País: es
  • Karma: +0/-0
Hola

1- ¿Por qué \( C\in{\Bbb Q} \)?¿por qué \( B<A \)?

No entiendo esta pregunta. ¿A qué parte del texto se refiere?.

Citar
2- El Teorema del Valor Medio, ¿se puede aplicar a primeras, segundas,... derivadas, como lo hace en este caso?

A cualquier función que cumpla las hipótesis, que sea derivable. Si \( g(x)=f'(x) \) es una función que cumple las hipótesis le puedes aplicar el teorema y no hay nada de especial. Su derivada será \( g'(x)=f''(x) \).

Citar
3- En el ejemplo, para determinar \( A \) y \( B \), emplea la negación de lo que afirma en la teoría. ¿Cómo se concilian los dos enunciados?

No entiendo porque dices que se emplea la negación de los resultados.

Citar
4- He resaltado \( \sqrt{2} \). ¿Es una errata?.

Si, debería de ser \( \sqrt{7} \).

Saludos.

24 Enero, 2022, 07:35 am
Respuesta #4

Marcos Castillo

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,277
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino

1- ¿Por qué \( C\in{\Bbb Q} \)?¿por qué \( B<A \)?

No entiendo esta pregunta. ¿A qué parte del texto se refiere?.


No lo menciona. Y no lo mantengo. Creo que estamos en los reales. Por otra parte, me empeño en sonsacar información sobre la relación entre \( A \) y \( B \).



2- El Teorema del Valor Medio, ¿se puede aplicar a primeras, segundas,... derivadas, como lo hace en este caso?


A cualquier función que cumpla las hipótesis, que sea derivable. Si \( g(x)=f'(x) \) es una función que cumple las hipótesis le puedes aplicar el teorema y no hay nada de especial. Su derivada será \( g'(x)=f''(x) \).


Perfecto. No encontraba en internet esta respuesta explícita.


No entiendo porque dices que se emplea la negación de los resultados.


Parte teórica:

\( A,B>0\Rightarrow{A,B\in{\Bbb{R}^+}} \)

\( C=\dfrac{B>|f''(x)|}{A<|f'(x)|} \), \( \forall{x\in{D}} \)

Encuentro diferente el enfoque del ejemplo

\( C=\dfrac{|f''(x)|=2=B}{|f'(x)|=|2x|\geq 4} \), \( \forall{x\in{D}} \)

No sé. No lo concilio. Es primero un \( > \) y luego un \( = \) para \( B \); y primero un \( < \) y luego un \( \geq{} \) para \( A \).

¡Un saludo!
No man is an island (John Donne)

24 Enero, 2022, 10:51 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,075
  • País: es
  • Karma: +0/-0
Hola

Parte teórica:

\( A,B>0\Rightarrow{A,B\in{\Bbb{R}^+}} \)

\( C=\dfrac{B>|f''(x)|}{A<|f'(x)|} \), \( \forall{x\in{D}} \)

Encuentro diferente el enfoque del ejemplo

\( C=\dfrac{|f''(x)|=2=B}{|f'(x)|=|2x|\geq 4} \), \( \forall{x\in{D}} \)

En la teoría donde pone las desigualdades perfectamente podría incluir el igual, es decir,

\( |f''(x)|\leq B \) en lugar de \( |f''(x)|<B \)
\( |f'(x)|\geq A \) en lugar de \( |f'(x)|>A \)

Entonces si \( |f''(x)|=2 \) se cumple que \( |f''(x)|\leq 2. \)
Y la otra desigualdad: \( |f'(x)|=2x\geq 4 \).

Saludos.

25 Enero, 2022, 08:31 pm
Respuesta #6

Marcos Castillo

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,277
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

En el mensaje inicial del hilo citaba mi libro de texto


TEOREMA 7 Límites de error del Método de Newton
Supongamos que \( f \), \( f' \) y \( f'' \) son continuas en un intervalo \( I \) que contiene a \( x_n \), \( x_{n+1} \) y a una raíz \( x=r \) de \( f(x)=0 \). Supongamos también que existen constantes \( K \) y \( L>0 \) tales que para todo \( x \) perteneciente a \( I \) se cumple

(i) \( |f''(x)|\leq{K} \) y

(ii) \( |f'(x)|\geq{L} \)

Entonces,

(a) \( |x_{n+1}-r|\leq{\dfrac{K}{2L}|x_{n+1}-x_n|^2} \) y

(b) \( |x_{n+1}-r|\leq{\dfrac{K}{2L}|x_{n}-r|^2} \)

Las condiciones (i) y (ii) aseguran que cerca de \( r \) la pendiente de \( y=f(x) \) no es demasiado pequeña y que no cambia con  demasiada rapidez. Si \( K/(2L)<1 \), el teorema demuestra que \( x_n \) converge rápidamente a \( r \) cuando \( n \) se hace lo suficientemente grande para que \( |x_n-r|<1 \).

La demostración del Teorema 7 depende del Teorema del Valor Medio. No la daremos aquí ya que este teorema es de uso práctico limitado. (...)
 

¿Por qué (i) y (ii) aseguran que cerca de \( r \) la pendiente de \( y=f(x) \) no es demasiado pequeña y que no cambia con  demasiada rapidez?. Debería aportar mi esfuerzo por explicarlo: ¿demasiado pequeña es \( <25º \) respecto a la abscisa?¿por debajo de estas inclinaciones el Método de Newton no representa más efectividad que, por ejemplo, el Método de la Bisección?; ¿ que no cambia con demasiada rapidez significa que está lejos de un punto de inflexión, cosa que no conviene al Método de Newton, como por ejemplo \( y=x^{1/3} \)?

PS: En cuanto al artículo que traduje, creo que tengo dos certidumbres. Por una parte, hay una errata, la de la raíz cuadrada de dos; por otra parte está el hecho de que cambiando \( < \) por \( \leq \) y \( > \) por \( \geq \) para mí resulta más comprensible el texto; por otra la incógnita es la naturaleza de \( C \), en concreto, ¿debe ser menor el numerador que el denominador? Es obvio que de esta forma la tasa de convergencia es superior. Pero no queda claro en el artículo, o yo soy incapaz de encontrar evidencia de ello. Al respecto el libro de texto tampoco es muy explícito. O yo no lo veo.

¡Un saludo!
No man is an island (John Donne)

25 Enero, 2022, 09:08 pm
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,075
  • País: es
  • Karma: +0/-0
Hola

¿Por qué (i) y (ii) aseguran que cerca de \( r \) la pendiente de \( y=f(x) \) no es demasiado pequeña y que no cambia con  demasiada rapidez?. Debería aportar mi esfuerzo por explicarlo: ¿demasiado pequeña es \( <25º \) respecto a la abscisa?

Que no es demasiado pequeña es una expresión informal. Simplemente quiere decir que tenemos controlado cuan pequeña va a ser la pendiente, de manera que no se va a acercar a cero más de un límite que tenemos controlado. La pendiente es la derivada. El control consiste en exigir:

\( |f'(x)|\geq{L} \)

Como mínimo esa pendiente valdrá \( L \).

Citar
¿por debajo de estas inclinaciones el Método de Newton no representa más efectividad que, por ejemplo, el Método de la Bisección?;

No creo que proceda aquí comparar un método con otro. Habría que comparar errores. Se puede hacer, pero no te va ayudar a comprender lo que está acotando aquí.

Citar
¿ que no cambia con demasiada rapidez significa que está lejos de un punto de inflexión, cosa que no conviene al Método de Newton, como por ejemplo \( y=x^{1/3} \)?

Pues significa que la pendiente no crece o mengua "demasiado deprisa"; es decir que tenemos controlado lo rápido que puede variar. Ese control es a través de la derivada de la pendiente, que mide como cambia ésta y corresponde a la segunda derivada. Es a través de la cota:

\( |f''(x)|\leq{K} \)

Nos dice que la razón de cambio de la pendiente a lo sumo es \( K \).

El interés de esas cotas es porque después se demuestra esta cota del error:

\( |x_{n+1}-\hat{x}|\leq{C\;|x_n-\hat{x}|^2} \)

donde \( C=K/L \). Para garantizar que el erro disminuya interesa que ese cociente sea pequeño, en particular menor que uno; por tanto el denominador \( L \) "grande", es decir, que el valor mínimo de la pendiente no sea demasiado pequeño y el valor de \( K \) pequeño, es decir, que la variación de la pendiente no sea demasiado grande.

Citar
PS: En cuanto al artículo que traduje, creo que tengo dos certidumbres. Por una parte, hay una errata, la de la raíz cuadrada de dos; por otra parte está el hecho de que cambiando \( < \) por \( \leq \) y \( > \) por \( \geq \) para mí resulta más comprensible el texto; por otra la incógnita es la naturaleza de \( C \), en concreto, ¿debe ser menor el numerador que el denominador?

Si, para garantizar que la cota va disminuyendo el error. Pero ojo, es una acotación, no una igualdad. Entonces pudiera ser incluso que aunque ese cociente fuese mayor que uno, la convergencia igualmente fuese buena; pero no lo tendríamos garantizado.

Saludos.

25 Enero, 2022, 11:16 pm
Respuesta #8

Marcos Castillo

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,277
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Uf, genial, Luis. Sigo adelante. ¡Lo he entendido!

Un saludo
No man is an island (John Donne)