Raices_2024

Vista previa del material en texto

Aproximación de Raíces
MÉTODOS COMPUTACIONALES EN
INGENIERÍA I
Aproximación de Raíces
Facultad de Ingeniería
Universidad Nacional del Comahue
web page: http://pedco.uncoma.edu.ar/
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Introducción
En esta unidad, se considera uno de los problemas
básicos del cálculo numérico, la búsqueda de raíces.
La misma consiste en hallar para una función f , una raíz o
solución de la ecuación de la forma
f (x) = 0
Una raíz de esta ecuación se denomina también cero de
la función f .
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Bisección
Representación Gráfica
Sea f una función continua definida en el intervalo [a,b]
con f (a) y f (b) de distinto signo. Por el Teorema del Valor
Intermedio, existe un valor p ∈ [a,b] tal que f (p) = 0.
Aunque el procedimiento funcionará con más de una raíz
en dicho intervalo, a efectos prácticos del mismo se
supondrá que dicha raíz es única.
El punto medio de [a,b], aproxima a la raíz con la
siguiente expresión
p1 = a1 +
b1 − a1
2
=
a1 + b1
2
(1)
Dependiendo del signo de f (p1) y de f (a), se elegirá el
nuevo intervalo.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Bisección
Representación Gráfica
Hacer a1 = a, b1 = b y
p1 = (a1 + b1)/2.
Si f (p1) = 0, entonces p = p1 y se
encontró la raíz.
Si f (p1) ̸= 0, entonces f (p1) tiene el
mismo signo que f (a1) o f (b1).
Cuando f (p1) y f (a1) tienen el
mismo signo, p ∈ (p1, b1) y se hace
a2 = p1 y b2 = b1.
Cuando f (p1) y f (a1) tienen signo
opuesto, p ∈ (a1, p1) y se hace
a2 = a1 y b2 = p1.
Luego, se repite el proceso en el
intervalo [a2, b2].
Método de Bisección
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Bisección
Pseudocódigo
Obtener x tal que f (x) = 0 para f continua en [a, b] con f (a) y f (b) de distinto
signo
ENTRADA: extremos a y b, tolerancia TOL, número máximo de iteraciones N
SALIDA: solución aproximada p o mensaje de error
Paso 1: Tomar i = 1, FA = f (a)
Paso 2: Mientras i ≤ N realizar pasos 3 a 6
Paso 3: Tomar p = a + (b − a)/2 (cálculo de pi )
FP = f (p)
Paso 4: Si FP = 0 o (b − a)/2 < TOL entonces
SALIDA (p) (algoritmo finalizado satisfactoriamente) PARAR
Paso 5: Tomar i = i + 1
Paso 6: Si FA · FP > 0 tomar a = p y FA = FP (Cálculo de ai y bi )
sino tomar b = p
Paso 7: SALIDA (El algoritmo fracasó despues de iterar, N, veces) (algoritmo finalizado sin
éxito) PARAR
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Bisección
Cota del Error
Sea f ∈ C[a,b] y f (a) · f (b) < 0. El método de Bisección
genera una sucesión {pn}∞n=1 que tiende al cero p de f con
|pn − p| ≤
b − a
2n
para n ≥ 1
Luego, la cota del error es
En ≤
b − a
2n
El método de Bisección es un método que converge
linealmente.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Bisección
Ejemplo
Determinar la cantidad de iteraciones necesarias para resolver
f (x) = x3 + 4x2 − 10x = 0 con [a,b] = [1,2] y exactitud de
10−3
Buscamos N tal que
|pN − p| ≤ 2−N(b − a) = 2−N < 10−3
Utilizando logaritmos
2−N < 10−3 ⇒ log10 2−N < log10 10−3 = −3
−N log10 2 < −3 ⇒ N >
3
log10 2
≈ 9.96
Por lo tanto se necesitan unas 10 iteraciones para lograr
una aproximación exacta dentro de una tolerancia de 10−3.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Bisección
Algunas observaciones
Puede utilizarse como criterio de parada el error relativo
como alternativa al Paso 4 del algoritmo siempre que
pN ̸= 0, es decir
|pN−pN−1|
|pN | < TOL
El método siempre converge a la solución, luego puede
utilizarse para elegir aproximaciones iniciales de los
métodos que convergen localmente.
La cota del error es bastante conservativa, es decir, en
general el error es significativamente menor.
Una alternativa para disminuir los errores de redondeo en
el cálculo del punto medio es pn = an + (bn − an)/2.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Un punto p es un punto fijo para una función dada g si g(p) = p.
Los problemas de búsqueda de raíces y los problemas de punto fijo
son equivalentes en el siguiente sentido:
Dado un problema de búsqueda de raíces f (p) = 0, se puede
construir una función g con un punto fijo en p de diferentes
maneras, por ejemplo como g(x) = x − f (x) o como
g(x) = x + 3f (x).
Inversamente, si la función g tiene un punto fijo en p, luego la
función definida por f (x) = x − g(x) tiene un cero en p.
La forma de punto fijo, es en general más simple de analizar y muchas
elecciones de la función g derivan en poderosas herramientas de
búsqueda de raíces.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Ejemplo
La función g(x) = x2−2 en [−2,3]
tiene puntos fijos en x = −1 y x =
2 porque
g(−1) = (−1)2 − 2 = −1
g(2) = (2)2 − 2 = 2
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Teorema de existencia y unicidad
Teorema:
Si g ∈ C[a,b] y g(x) ∈ [a,b],
para toda x ∈ [a,b], entonces
g tiene un punto fijo en [a,b].
Y si además g′(x) existe en
(a,b) y existe una constante
positiva k < 1 con |g′(x)| ≤ k
para toda x ∈ (a,b)
entonces el punto fijo en
[a,b] es único.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Ejemplo
Sea g(x) = (x2 − 1)/3 en [−1,1], por el teorema del valor
extremo se establece que el mínimo absoluto de g ocurre
en x = 0 y g(0) = −1/3.
El máximo absoluto de g ocurre en x = ±1 y tiene el valor
g(±1) = 0.
La función g es continua y para toda x ∈ (−1,1)
|g′(x)| = |2x |
|3|
≤ 2
3
,
Por lo tanto, g satisface todas las hipótesis del teorema y
tiene un punto fijo único en [−1,1].
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Iteración Funcional
Para aproximar un punto fijo de una función g se parte de
una aproximación inicial p0
Se genera una sucesión {pn}∞n=0 donde pn = g(pn−1) para
cada n ≥ 1.
Si la sucesión converge a p y si g es continua, entonces
p = ĺım
n→∞
pn = ĺımn→∞ g(pn−1) = g( ĺımn→∞ pn−1) = g(p)
y obtenemos una solución con x = g(x).
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Representación Gráfica
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Pseudocódigo
Obtener p = g(p) dada una aproximación p0
ENTRADA: aproximación inicial p0, tolerancia TOL, número máximo de iteraciones N
SALIDA: solución aproximada p o mensaje de error
Paso 1: Tomar i = 1
Paso 2: Mientras i ≤ N realizar pasos 3 a 6
Paso 3: Tomar p = g(p0) (cálculo de pi )
Paso 4: Si |p − p0| < TOL entonces
SALIDA (p) (algoritmo finalizado satisfactoriamente)
PARAR
Paso 5: Tomar i = i + 1
Paso 6: Tomar p0 = p (se define un nuevo valor inicial)
Paso 7: SALIDA (El algoritmo fracasó despues de iterar, N, veces) (algoritmo finalizado sin
éxito)
PARAR
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Cotas del Error
Si se satisfacen las hipótesis del Teorema, luego las cotas
del error al aproximar p con pn están dadas por
|pn − p| ≤
kn
1 − k
|p1 − p0|, ∀ n ≥ 1
Observaciones: La desigualdad relaciona la tasa con la
cuál la sucesión converge a la cota k de la derivada
primera.
La tasa de convergencia depende del factor kn. A menor
valor de k , será más rápida la convergencia, la cual será
lenta al acercarse k a 1.
En general, la iteración de punto fijo converge linealmente.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Iteración de Punto Fijo
Ejemplo
La ecuación x3 + 4x2 − 10 = 0 tiene una raíz única en
[1,2].
Podemos convertirla en la forma x = g(x) con manejo
algebraico obteniendo por ejemplo
x = ±1
2
(10 − x3)1/2Con esta elección de g iniciando con p0 = 1.5
obtendremos la solución aproximada en 30 iteraciones.
Si por ejemplo calculamos
p1 = g(p0) =
1
2
(10 − p03)1/2 = 1.286953768
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Newton-Raphson
Interpretación Gráfica
Gráficamente, la técnica consiste
en calcular la recta tangente a f que
pasa por el punto (p0, f (p0)), donde
p0 es una aproximación a la raíz
buscada.
f ′(p0) =
f (p0)− 0
p0 − p1
despejando se obtiene la ecuación
de recurrencia
p1 = p0 −
f (p0)
f ′(p0) Método de Newton-Raphson
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Newton-Raphson
Desarrollo mediante polinomio de Taylor
Puede obtenerse la ecuación de recurrencia mediante Taylor.
Sea f ∈ C2[a, b] y sea p0 ∈ [a, b] una aproximación a la solución p de
f (x) = 0 tal que f ′(p0) ̸= 0 y |p − p0| pequeño.
El primer polinomio de Taylor para f (x) alrededor de p0 y evaluando
x = p
f (p) = f (p0) + (p − p0)f ′(p0) +
(p − p0)2
2
f ′′(ξ(p))
donde ξ(x) ∈ (p, p0). Dado que f (p) = 0, se obtiene
0 = f (p0) + (p − p0)f ′(p0) +
(p − p0)2
2
f ′′(ξ(p))
Resolviendo para p se tiene p ≈ p1 = p0 − f (p0)f ′(p0) .
El Método de Newton resulta dado p0
pn = pn−1 −
f (pn−1)
f ′(pn−1)
, n ≥ 1
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Newton-Raphson
Pseudocódigo
Obtener x tal que f (x) = 0 dada f diferenciable y una aproximación inicial p0
ENTRADA: aproximación inicial p0, tolerancia TOL, número máximo de iteraciones N
SALIDA: solución aproximada p o mensaje de error
Paso 1: Tomar i = 1
Paso 2: Mientras i ≤ N realizar pasos 3 a 6
Paso 3: Tomar p = p0 − f (p0)/f ′(p0) (cálculo de pi )
Paso 4: Si |p − p0| < TOL entonces
SALIDA (p) (algoritmo finalizado satisfactoriamente)
PARAR
Paso 5: Tomar i = i + 1
Paso 6: Tomar p0 = p (se define un nuevo valor inicial)
Paso 7: SALIDA (El algoritmo fracasó despues de iterar, N, veces) (algoritmo finalizado sin
éxito)
PARAR
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Newton-Raphson
Teorema y observaciones
Teorema: Sea f ∈ C2[a, b]. Si p ∈ [a, b] tal que f (p) = 0 y f ′(p) ̸= 0,
entonces existe un número δ > 0 tal que la serie que genera la
ecuación de recurrencia converge a p para cualquier aproximación
incial p0 ∈ [p − δ, p + δ].
Observaciones: Se puede concluir entonces, que bajo ciertas
condiciones el método de Newton converge si se parte de una
aproximación inicial suficientemente cercana obteniendo en general
convegencia cuadrática.
Fallas del método de Newton:
Cuando la raíz r tiene multiplicidad mayor a 1.
Cuando el punto inicial se encuentra cerca de un máximo o un
mínimo local.
Cuando la raíz es cercana a un punto de inflexión de la función.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de la Secante
Desarrollo
En muchos problemas, es difícil determinar f ′(x) además de requerir
más operaciones que para evaluar f (x).
Para evitar calcular la derivada en el método de Newton Raphson, se
reemplaza:
f ′(pn−1) =
f (x)− f (pn−1)
x − pn−1
con x → pn−1
Si se reemplaza x = pn−2 entonces
f ′(pn−1) ≃
f (pn−1)− f (pn−2)
pn−1 − pn−2
Reemplazando en la ecuación del método de Newton se obtiene,
reordenando
pn = pn−1 −
f (pn−1)(pn−1 − pn−2)
f (pn−1)− f (pn−2)
El orden de convergencia será (1 < λ < 2) en general λ ≃ 1.6, se dice
entonces que la convergencia es superlineal.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de la Secante
Pseudocódigo
Obtener x tal que f (x) = 0 dadas dos aproximaciones iniciales p0 y p1
ENTRADA: aproximaciones iniciales p0, p1, tolerancia TOL, número máximo de
iteraciones N
SALIDA: solución aproximada p o mensaje de error
Paso 1: Tomar i = 2; q0 = f (p0); q1 = f (p1);
Paso 2: Mientras i ≤ N realizar pasos 3 a 6
Paso 3: Tomar p = p1 − q1(p1 − p0)/(q1 − q0) (cálculo de pi )
Paso 4: Si |p − p1| < TOL entonces
SALIDA (p) (algoritmo finalizado satisfactoriamente)
PARAR
Paso 5: Tomar i = i + 1
Paso 6: p0 = p1
q0 = q1
p1 = p
q1 = f (p)
Paso 7: SALIDA (El algoritmo fracasó despues de iterar, N, veces) (algoritmo finalizado sin
éxito) PARAR
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de la Secante y Falsa Posición
Representación Gráfica
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de la Secante y Falsa Posición
Representación Gráfica
El método de falsa posición genera aproximaciones del mismo modo
que el método de la secante pero ofrece una prueba que asegura que
la raíz quede entre dos iteraciones sucesivas.
Primero elegimos las aproximaciones iniciales p0 y p1 con
f (p0) · f (p1) < 0.
La aproximación p2 se obtiene al igual que con secante como la
intersección en x de la línea que une (p0, f (p0)) y (p1, f (p1)).
Calcularemos p3 verificando f (p2) · f (p1).
Si el producto es negativo entonces p1 y p2 encierran la raíz y elegimos
la raíz como la intersección en x de la línea que une (p1, f (p1)) y
(p2, f (p2)).
En caso contrario, elegimos p3 como la intersección en x de la línea
que une (p0, f (p0)) y (p2, f (p2)).
De esta forma se sigue sucesivamente.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Método de Falsa Posición
Pseudocódigo
Obtener x tal que f (x) = 0 dadas dos aproximaciones iniciales p0 y p1
ENTRADA: aproximaciones iniciales p0, p1, tolerancia TOL, número máximo de
iteraciones N
SALIDA: solución aproximada p o mensaje de error
Paso 1: Tomar i = 2; q0 = f (p0); q1 = f (p1);
Paso 2: Mientras i ≤ N realizar pasos 3 a 6
Paso 3: Tomar p = p1 − q1(p1 − p0)/(q1 − q0) (cálculo de pi )
Paso 4: Si |p − p1| < TOL entonces
SALIDA (p) (algoritmo finalizado satisfactoriamente)
PARAR
Paso 5: Tomar i = i + 1; q = f (p)
Paso 6: Si q · q1 < 0 entonces tomar p0 = p1; q0 = q1
Paso 7: Tomar p1 = p; q1 = q
Paso 8: SALIDA (El algoritmo fracasó despues de iterar, N, veces) (algoritmo finalizado sin
éxito) PARAR
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Aproximación de Raíces
Ejemplos
Problema: Resolver f (x) = x3 + 4x2 − 10 = 0 en [1, 2] con Punto Fijo
La ecuación tiene una raíz única en [1, 2].
Se pueden pensar diferentes opciones de punto fijo:
(a) x = g1(x) = x − x3 − 4x2 + 10
(b) x = g2(x) = 12 (10 − x
3)1/2
(c) x = g3(x) = x − x
3+4x2−10
3x2+8x
Con p0 = 1.5 se obtiene: (a) diverge, (b) converge en 30 iteraciones, (c)
converge en 4 iteraciones.
Caso (a): g1 no mapea [1, 2] en si mismo y además |g′1(x)| > 1 allí.
Caso (b): |g′2(x)| ≈ 2.12 falla la condición de cota. Debió considerarse
[1, 1.5].
Caso (c): Su convergencia rápida se debe a que esta elección de g3 es
la iteración para Newton.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
Aproximación de Raíces
Aproximación de Raíces
Análisis del Error
Convergencia: Supongamos que {pn}∞n=0 es una sucesión
que converge a p, con pn ̸= p para toda n. Si existen
constantes positivas λ y α con
ĺım
n→∞
|pn+1 − p|
|pn − p|α
= λ
entonces {pn}∞n=0 converge a p con orden α y una constante
de error asintótica λ.
En general, una sucesión con alto orden de convergencia
converge más rápidamente que una con orden más bajo.
FAIN-UNCOMA
MÉTODOS COMPUTACIONALES EN INGENIERÍA I
	Aproximación de Raíces