Clase 6 - Solución de ecuaciones no lineales (3)

Método de la secante

Continuamos con el mismo problema de resolver una ecuación no lineal. Hasta ahora vimos
el método de bisección y el método de Newton. Recordemos que la iteración del método de

22
Newton está dada por:
f (xn )
xn+1 = xn − 0 para n ≥ 0. (1)
f (xn )

20
Si bien este método tiene convergencia cuadrática local, tiene como desventaja que requiere
la evaluación de la derivada de la función f en cada iteración. Uno de los métodos más
conocidos que evita esto es el método de la secante.

F
La idea del método de la secante consiste en reemplazar f 0 (xn ) en la iteración de Newton

A
(1) por una aproximación dada por el cociente incremental, dado por la pendiente de la recta
secante que pasa por los puntos (xn , f (xn )) y (xn + h, f (xn + h)):

M
f 0 (xn ) ≈ an =
f (xn + h) − f (xn )
h
,
A
para algún h suficientemente pequeño.
-F

Para evitar evaluar f en un punto adicional (xn + h) se elige h = xn−1 − xn , entonces:

f (xn + h) − f (xn ) f (xn−1 ) − f (xn ) f (xn ) − f (xn−1 )

an = = = .
h xn−1 − xn xn − xn−1
o
ic

Ver Figura 1.

-O   ȈT Ȉ

Ȉ
ȈFÿ Ȉ
Ȉ

ér
um
.N

 %"<   <
2M}tM„fJ¾fyM„€„MDf}y¾
}U¾ŒMJDy¾tMa}L¾
A

Figura 1: Interpretación gráfica del método secante.


ࢳ
ࢳ& ࢳࢳ ࢳ&J
%<ࢳ‚
&ࢳࢳࢳ&

ࢳ
 ¬ ˪‹
­ 3˪  ࢳࢳ
©ø
૵
 ࢄࢳf4ࢳ7 D i ࢳ6Mࢳ႒

Así, la iteración del método secante consiste en:


Ě - -ă,™T
Ě
4 \ 
Ě‫ݩݣ‬ 3C
Ě  @Ě
f (xn )
×
ࢳ&: xn+1
%ࢳ n − f (x )−
= x
ࢳࢳf4 ࢳf
:Ž
(xn−1
para n ≥ 1, ࢳVࢳX€ࢳ
%
ࢳ)&
ϲ_ࢳV&%ࢳ
ࢳ)
u
)
n
႒ %Ljࢳ%
_1ࢳ
x −x n n−1

©ø
૵ ©
૵ h†  Ž
ϣȧ—Ѭ
yå %ࢳ
v

es decir,  Ě ӌ
v

xn − xn−1
o
ࢳࢳ&̰ ̰%
ࢳࢳ%Š
1ࢳ
ࢳ&
ࢳ&%ࢳࢳ 
)ࢳА
ࢳ  ­˪
˪

©૵{
Ěʲ4Ě 
Ě

n+1 = xn − f (xn ) para n ≥ 1.
#ʲ
xЯࢳV%ࢳࢳ (2)
f (x ) − f (x )
n n−1
,  UĚ
ѬĚ
{Ě š @Ě
GJ ႁ႒ D i ࢳ .Ǎ
4Ě  b Ú
Ě
v
f֨

1
T 
ࢳ
ࢳ (  ࢳVࢳ, TĚ &
4&
ࢳĚ )ࢳ, ›  ĖĚࢳ  ࢳ ࢳ%ࢳ63ࢳ&
þ
 Algoritmo del método de la secante

Dados los siguientes datos de entrada y parámetros algorítmicos: x0 y x1 las primeras 2

aproximaciones iniciales de r, el número máximo de iteraciones permitido M, δ la tolerancia
para el error e (en la variable x) y ε la tolerancia para los valores funcionales.
input x0, x1, M, δ , ε

22
f 0 ← f (x0)
f 1 ← f (x1)

20
output 0, x0, f 0
output 1, x1, f 1

F
for k = 2, 3, . . . , M do
if | f 0| > | f 1| do

A
x0 ↔ x1; f 0 ↔ f 1
endif
s ← (x1 − x0)/( f 1 − f 0)
M
A
x1 ← x0
-F

f1 ← f0
x0 ← x0 − f 0 ∗ s
f 0 ← f (x0)
o

output k, x0, f 0
ic

if |x1 − x0| < δ or | f 0| < ε then STOP

ér

end do
um

Observaciones:
1. En el algoritmo los puntos x0 y x1 pueden intercambiarse para lograr que | f (x0 )| ≤ | f (x1 )|.
Así, para el par {xn−1 , xn } se satisface que | f (xn )| ≤ | f (xn−1 )|, y para el par siguiente
.N

{xn , xn+1 } se tiene que | f (xn+1 )| ≤ | f (xn )|. Esto garantiza que la sucesión {| f (xn )|} es no
creciente.
2. El algoritmo se detiene por el número máximo de iteraciones permitidas, por satisfacer la
A

tolarancia para los valores funcionales, o por la tolerancia en la diferencia de dos aproxima-
ciones sucesivas.
3. En cuanto al análisis de errores, es posible probar que:
en+1 ≈ ceαn = (c enα−1 ) e1n ,
√
donde α = (1 + 5)/2 = 1.618334... Como 1 < α < 2 se dice que el método de la secante
tiene convergencia superlineal. Además, por recurrencia
2
en+1 ≈ ceαn ≈ c1+α eαn−1
√ √
donde α 2 = (1 + 5)2 /4 = (3 + 5)/2 = 2.618334..., esto dice que dos iteraciones de
método de la secante es mejor que una iteración del método de Newton.

2
 Iteración de punto fijo

En esta sección veremos que es un punto fijo de una función dada, como encontrarlos numé-
ricamente y cuál es la conexión con el problema de determinar raíces de funciones.

Definición 1. un punto fijo de una función g es un número p, en el dominio de g, tal que

g(p) = p.

22
Por un lado, si p es una raíz de una función f , esto es, f (p) = 0, entonces es posible definir
diferentes funciones g con un punto fijo en p, por ejemplo: g(x) = x − f (x), o g(x) = x +

20
3 f (x).
Por otro lado, si g tiene un punto fijo en p, esto es, g(p) = p, entonces la función f (x) =
x − g(x) tiene una raíz en p.

F
Aunque estamos interesados en el problema de determinar soluciones de una ecuación no

A
lineal, o equivalentemente, encontrar raíces de funciones no lineales veremos que la forma de
la iteración de punto es muy fácil de estudiar y analizar. Además algunas opciones de punto

M
fijo dan origen a técnicas matemáticas y computacionales muy poderosas para determinar
raíces.
A
Ejemplo 1: se busca determinar los posibles puntos fijos de la función g(x) = x2 − 2 en el
-F

intervalo [−2, 3].

Para esto se plantea la ecuación g(x) = x, es decir, se debe resolver la ecuación cuadrática
x2 − 2 = x, o sea, x2 − x − 2 = 0. Luego es fácil verificar que x = −1 y x = 2 son puntos fijos
(g(p) = p) pues
o

g(−1) = (−1)2 − 2 = −1 g(2) = (2)2 − 2 = 2.

ic

Ver Figura 2.
ér
um
.N
A

Figura 2: Puntos fijos de g.

A continuación veremos un resultado que da condiciones suficientes para la existencia y

unicidad del punto fijo.

Teorema 1.

3
 1. Si g ∈ C[a, b] (es decir, g es una función continua en el intervalo [a, b]) y g(x) ∈ [a, b]
para todo x ∈ [a, b] entonces existe p ∈ [a, b] tal que g(p) = p. (EXISTENCIA)

2. Si además existe g0 (x) para todo x ∈ (a, b) y existe una constante positiva k < 1 tal que
|g0 (x)| ≤ k para todo x ∈ (a, b), entonces el punto fijo en (a, b) es único. (Ver Figura 3).
(UNICIDAD)

22
20
F
A
Figura 3: Unicidad del punto fijo.

Demostración.
M
A
-F

1. Si g(a) = a o g(b) = b, el punto fijo está en uno de los extremos del intervalo y ya
estaría probado.
Supongamos que esto no es cierto, entonces g(a) > a y g(b) < b. Sea h(x) = g(x) − x
una función definida en [a, b], que además es continua en [a, b] pues g y x lo son y resta
o

de funciones continuas es una función continua. Además, por lo anterior, tenemos que
ic

h(a) = g(a) − a > 0 y h(b) = g(b) − b < 0.

ér

Entonces, por el Teorema del Valor Intermedio, existe p ∈ (a, b) tal que h(p) = 0, esto
es, g(p) = p y por lo tanto p es un punto fijo de g.
um

2. Ahora supongamos que existen dos puntos fijos distintos p y q en [a, b], es decir, p, q ∈
[a, b], p 6= q tal que g(p) = p y g(q) = q. Por el Teorema del Valor Medio existe ξ
entre p y q, y por lo tanto en [a, b] tal que
.N

g(p) − g(q) = g0 (ξ )(p − q).

Luego usando la hipótesis que |g0 (x)| ≤ k < 1 tenemos que

A

|p − q| = |g(p) − g(q)| = |g0 (ξ )||p − q| ≤ k|p − q| < |p − q|,

lo que es una contradicción que provino de suponer que habrían dos puntos fijos dis-
tintos en [a, b], y por lo tanto el punto fijo es único.

Analicemos la existencia y unicidad de punto fijo en los siguientes ejemplos.

(x2 − 1) x2 1
Ejemplo 1: considerar g(x) = = − en el intervalo [−1, 1].
3 3 3

4
 Es fácil ver g tiene un mínimo absoluto en x = 0 y g(0) = −1/3. Además tiene máximos
absolutos en x = −1 y x = 1 donde g(−1) = 0 y g(1) = 0. Además, claramente g es continua
2 2
en [−1, 1] y |g0 (x)| = x ≤ para todo x ∈ [−1, 1]. Por lo tanto existe un único punto fijo
3 3
p de g en el intervalo [−1, 1]. Para determinar p, planteamos

p2 − 1

22
g(p) = p, ⇒ = p, ⇒ p2 − 3p − 1 = 0,
3
√ √
(3 − 13) (3 13)

20
cuyas raíces son p1 = = −0,302776... y p2 = = 3,302776... El único
2 2
punto fijo es claramente p1 pues este punto está en [−1, 1] en cambio p2 no. Ver Figura 4.

F
A
M
A
-F
o
ic

Figura 4: Puntos fijos del Ejemplo 1.

ér

Notar en el gráfico que p2 también es un punto fijo de g en el intervalo [3, 4]. Sin embargo,
8
um

g(4) = 5 y g0 (4) = > 1, por lo que no se satisfacen las hipótesis del teorema anterior en
3
el intervalo [3, 4]. Esto dice que tales hipótesis son condiciones suficientes para garantizar la
existencia y unicidad de un punto fijo, pero no son necesarias.
.N

Ejemplo 2: considerar g(x) = 3−x = e−(ln 3)x en el intervalo [0, 1].

Su derivada es g0 (x) = −(ln 3)e−(ln 3)x = −(ln 3)3−x < 0, por lo tanto g es decreciente en el
A

intervalo [0, 1]. Entonces,

1
g(0) = 1 ≥ g(x) ≥ = g(1),
3
y por el teorema anterior, existe un punto fijo en [0, 1]. Por otro lado, g0 (0) = − ln 3 =
−1.0986... y por lo tanto no se puede usar el teorema anterior para garantizar unicidad pues
|g0 (x)| ≮ 1 en el intervalo (0, 1). Ver Figura 5.
Idea del algoritmo de punto fijo

Para calcular aproximadamente el punto fijo de una función g primero se inicia con una
aproximación inicial p0 y calculando pn = g(pn−1 ) para n ≥ 1 se obtiene una sucesión de

5
 22
20
Figura 5: Puntos fijos del Ejemplo 1.

F
aproximaciones {pn }. Si la función g es continua y la sucesión converge entonces lo hace a

A
un punto fijo p de g pues

p = lı́m pn = lı́m g(pn−1 ) = g( lı́m pn−1 ) = g(p).

n→∞
Mn→∞ n→∞
A
Algoritmo del método de punto fijo
-F

Dados los siguientes datos de entrada y parámetros algorítmicos: p0 una aproximación ini-
cial, el número máximo de iteraciones permitido M y δ la tolerancia para el error e (en la
variable x)
o

input p0 , M, δ
ic

output 0, p0
i←1
ér

while i ≤ M then do
p ← g(p0 )
um

output i, p
if |p − p0 | < δ then STOP
.N

i ← i+1
p0 ← p
end while
A

Observaciones:
1. El algoritmo es muy fácil de implementar.
2. los criterios de parada utilizados son la distancia entre dos iteraciones sucesivas y el nú-
mero máximo de iteraciones.

Teorema 2.

6
 Sea g ∈ C[a, b] tal que g(x) ∈ [a, b] para todo x ∈ [a, b]. Supongamos que existe g0 (x) para
todo x ∈ (a, b) y existe una constante positiva 0 < k < 1 tal que |g0 (x)| ≤ k para todo x ∈
(a, b), entonces para cualquier p0 ∈ [a, b] la sucesión definida por pn = g(pn−1 ), para n ≥ 1,
converge al único punto fijo p en (a, b).

Demostración. Por el teorema anterior, se sabe que bajo estas hipótesis existe un único punto

22
fijo p ∈ [a, b]. Como g(x) ∈ [a, b] para todo x ∈ [a, b], la sucesión de aproximaciones {pn }
está bien definida para todo n, es decir, pn ∈ [a, b] para todo n.

20
Para probar la convergencia se usará el Teorema del Valor Medio en lo siguiente

|pn − p| = |g(pn−1 ) − g(p)| = |g0 (ξn )||pn−1 − p| ≤ k|pn−1 − p|,

F
luego, por recurrencia, se tiene que

A
|pn − p| ≤ k|pn−1 − p| ≤ k2 |pn−2 − p| ≤ · · · ≤ kn |p0 − p|.

M
Como 0 < k < 1 entonces lı́m kn = 0, luego
n→∞
A
lı́m |pn − p| ≤ lı́m kn |p0 − p| = |p0 − p| lı́m kn = 0,
n→∞ n→∞ n→∞
-F

y por lo tanto, la sucesión {pn } converge al punto fijo p.

Corolario 1. Si g es una función que satisface las hipótesis del teorema anterior, se tienen
las siguientes cotas de error
o
ic

|pn − p| ≤ kn máx{p0 − a, b − p0 }
kn
|pn − p| ≤ 1−k |p1 − p0 | para todo n≥1
ér
um

Demostración. La demostración puede consultarse en el libro de Burden-Faires.

.N

Análisis de error en métodos de punto fijo

A

Supongamos que p es un punto fijo de una función g y que {pn } es la sucesión, que converge
a p, definida por pn+1 = g(pn ).
Sea pn una aproximación del punto fijo p, es decir pn = p + h, y consideremos el desarrollo
de Taylor de g centrado en p:
00 (p)
pn+1 = g(pn ) = g(p + h) = g(p) + g0 (p)(pn − p) + g 2 (pn − p)2 + . . .
(r−1) (p) (r)
(3)
+ g(r−1)! (pn − p)r−1 + g r!(ξn ) (pn − p)r ,

para algún ξn entre pn y p.

7
 Supongamos ahora que g0 (p) = g00 (p) = · · · = g(r−1) (p) = 0 pero g(r) (p) 6= 0, entonces

g(r) (ξn ) g(r) (ξn ) r

en+1 = pn+1 − p = g(pn ) − g(p) = (pn − p)r = en ,
r! r!
esto es,
g(r) (ξn ) r

22
en+1 = en ,
r!
y tomando límite se obtiene

20
|en+1 | |g(r) (p)|
lı́m = = C,
n→∞ |en |r r!

F
por lo tanto el método tiene orden de convergencia (al menos) r.
Conclusión: si las derivadas de la función de iteración de punto fijo se anulan en el punto

A
fijo p hasta el orden (r − 1) entonces el método tiene orden de convergencia (al menos) r.

M
Usando este resultado se obtienen tres corolarios interesantes que relacionan el método de
A
Newton con el método de punto fijo para una función f que satisface las hipótesis del teorema
de convergencia de Newton.
-F

Corolario 2. Si f es una función que tiene una raíz simple p, entonces el método de Newton
es un método de punto fijo y tiene orden de convergencia (al menos) 2.
o
ic

f (x)
Demostración. Sea g(x) = x − , la función de iteración del método de Newton. Es claro
f 0 (x)
ér

que si p es una solución de f (x) = 0, entonces p es un punto fijo de g pues

f (p)
um

g(p) = p − = p,
f 0 (p)

ya que f (p) = 0 y f 0 (p) 6= 0.

Ahora calculemos g0 (x) y luego evaluemos en p:
.N

( f 0 (x))2 − f 00 (x) f (x) f 00 (x) f (x) f 00 (x) f (x)

g0 (x) = 1 − = 1 − 1 + = ,
( f 0 (x))2 ( f 0 (x))2 ( f 0 (x))2
A

entonces
f 00 (p) f (p)
g0 (p) = = 0,
( f 0 (p))2
y por lo tanto el método tiene orden de convergencia (al menos) 2.

Corolario 3. Si p es una raíz de multiplicidad r ≥ 2 de f , entonces el método de Newton

tiene orden 1.

8
 f (x) 0 f (x) f 00 (x)
Demostración. Ya vimos que si g(x) = x − entonces g (x) = .
f 0 (x) ( f 0 (x))2
Ahora, supongamos que p es una raíz de multiplicidad r de f , esto es, f (x) = (x − p)r h(x),
con h una función tal que h(p) 6= 0 y r ≥ 2.
La derivada primera de f es

22
f 0 (x) = r(x − p)r−1 h(x) + (x − p)r h0 (x) = (x − p)r−1 rh(x) + (x − p)h0 (x) ,
 

y la derivada segunda de f es

20
f 00 (x) = r(r − 1)(x − p)r−2 h(x) + 2r(x − p)r−1 h0 (x) + (x − p)r h00 (x),
= (x − p)r−2 r(r − 1)h(x) + 2r(x − p)h0 (x) + (x − p)2 h00 (x) .
 

F
Luego

A
(x − p)r h(x)(x − p)r−2 r(r − 1)h(x) + 2r(x − p)h0 (x) + (x − p)2 h00 (x)
 
0
g (x) = ,

entonces M (x − p)2r−2 [rh(x) + (x − p)h0 (x)]2

h(p)r(r − 1)h(p) r − 1
A
g0 (p) = = 6= 0,
r2 (h(p))2 r
-F

pues r ≥ 2.

Por último, modificando levemente la función de iteración del método de Newton se puede
o

recuperar la convergencia cuadrática aún en casos de raíces múltiples.

ic

Corolario 4. Si p es una raíz de multiplicidad r ≥ 2 de f , entonces la siguiente modificación

ér

del método de Newton recupera la convergencia cuadrática:

f (xn ) f (x)
xn+1 = xn − r , esto es, g(x) = x − r .
um

f 0 (xn ) f 0 (x)

Demostración. Usando las expresiones de f , f 0 y f 00 obtenidas en el corolario anterior, se

tiene que
.N

( f 0 (x))2 − f 00 (x) f (x) f (x) f 00 (x)

g0 (x) = 1−r = 1−r+r 0
( f 0 (x))2 ( f (x))2
r r−2 r(r − 1)h(x) + 2r(x − p)h0 (x) + (x − p)2 h00 (x)
 
(x − p) h(x)(x − p)
A

= 1−r+r
(x − p)2r−2 [rh(x) + (x − p)h0 (x)]2
h(x) r(r − 1)h(x) + 2r(x − p)h0 (x) + (x − p)2 h00 (x)
 
= 1−r+r .
[rh(x) + (x − p)h0 (x)]2

Evaluando en el punto fijo p se obtiene

h(p)r(r − 1)h(p)
g0 (p) = 1 − r + r = 1 − r + (r − 1) = 0,
r2 (h(p))2

y por lo tanto el método de Newton modificado tiene convergencia (al menos) cuadrática.