1.Ecuaciones no lineales - ocwus.us.esocwus.us.es/matematica-aplicada/algebra-numerica/... · Proporcionan la soluci on mediante un numero nito de operaciones ele-mentales. ax2 +

1. Ecuaciones no lineales

Dada una funcion no nula f : C→ C, resolver la ecuacion f(x) = 0 es hallar

los valores x que anulan a dicha funcion. A estos valores x se les denomina

raıces o soluciones de la ecuacion, o tambien, ceros de la funcion f(x).

Los metodos de resolucion de ecuaciones y sistemas de ecuaciones se clasifican

en

• Metodos directos

Proporcionan la solucion mediante un numero finito de operaciones ele-

mentales.

ax2 + bx+ c = 0 =⇒ x =−b±

√b2 − 4ac

2a

• Metodos iterados

Construyen una sucesion (xn) convergente a la solucion x de la ecuacion

o del sistema.

Sin embargo, el siglo XIX, Abel probo que no existe ninguna formula equi-

valente (en termino de raıces) para resolver ecuaciones de grado superior a

cuatro.

Ademas, si la ecuacion no es polinomica no podemos resolverla mas que me-

diante metodos iterados que, incluso en el caso de las polinomicas de grado no

superior a cuatro, son mas eficientes.

Definicion 1.1 [Multiplicidad de una raız]

Una solucion x de la ecuacion f(x) = 0 se dice que tiene multiplicidad n si

f(x) = f ′(x) = f ′′(x) = · · · = f (n−1(x) = 0 y f (n(x) 6= 0

Si la multiplicidad es 1, diremos que se trata de una raız simple.

1

2 Ecuaciones no lineales

Todos los metodos numericos de resolucion de ecuaciones presentan dificulta-

des cuando la ecuacion tiene raıces multiples, ya que todos ellos se basan en

los cambios de signo de la funcion y estos son difıcilmente detectables en un

entorno de una raız multiple.

Ese hecho nos lleva a un mal condicionamiento del problema.

1.1 Errores y condicionamiento en problemas

numericos

Cualquier problema numerico se resuelve a traves de un algoritmo que nos

proporciona unos resultados a partir de unos datos iniciales. Es decir, se trata

de realizar un proceso del tipo

Datos =⇒ Algoritmo =⇒ Resultados

Dado que cualquier algoritmo puede cometer errores, no solo por el algoritmo

en sı, sino porque los datos pueden venir afectados de algun tipo de error

(redondeo, etc.) es muy importante el estudio de los distintos tipos de error

que puedan cometerse con vista a la fiabilidad de los resultados.

Definicion 1.2 [Errores absoluto y relativo]

Supongamos que el valor exacto de un dato es x y disponemos de un valor

aproximado x.

• Se denomina error absoluto de x a la distancia que lo separa del valor

exacto x, es decir |x− x|.

Observese que si solo disponemos del dato de que el error es, por ejemplo,

de 1m. no sabemos nada acerca de la fiabilidad del resultado, ya que no

es lo mismo decir que se ha cometido un error de un metro al medir la

altura de una persona que al medir la distancia entre dos galaxias.

Debemos reflejar de alguna manera “lo que se esta evaluando” en el dato

del error.

• Se denomina error relativo de x al cociente entre el error absoluto y el

objeto evaluado, es decir,

∣∣∣∣x− xx∣∣∣∣. En el caso x = 0 solo se utiliza el

error absoluto.

Errores y condicionamiento en problemas numericos 3

En la mayorıa de los procesos numericos utilizaremos como error el error abso-

luto ya que lo que nos interesa conocer es el numero de cifras decimales exactas

que posee la solucion de un determinado problema.

Evidentemente cualquier algoritmo que trabaje con unos datos afectados de

algun tipo de error nos proporcionara unos resultados que tambien vendran

afectados de errores. Estos errores pueden depender solo de los datos iniciales

o tambien del proceso que se ha realizado.

Supongamos que, queremos evaluar f(x) y damos un dato aproximado x. Es

evidente que, en general, si x 6= x sera f(x) 6= f(x).

Dado que f(x)− f(x) ' (x− x)f ′(x), se tiene que

|f(x)− f(x)| ' |x− x| · |f ′(x)|

por lo que aunque el error del dato sea muy pequeno, si la derivada f ′(x) es

muy grande, el resultado obtenido f(x) puede diferir mucho del valor exacto

f(x).

Para el problema inverso, es decir conocido f(x) buscar el valor de x (resolver

una ecuacion) se tendra que

|x− x| ' 1

|f ′(x)||f(x)− f(x)|

por lo que si |f ′(x)| fuese muy pequeno el error de la solucion puede ser muy

grande.

Ademas el problema no esta en el algoritmo que se aplique para evaluar f(x)

sino en el propio problema a resolver.

Definicion 1.3 [Condicionamiento de un problema]

Diremos que un problema esta mal condicionado si pequenos errores en los

datos producen grandes errores en los resultados.

Se trata entonces de definir algun numero que nos indique el condicionamiento

del problema. A este numero lo llamaremos numero de condicion del problema

y lo denotaremos por κ.

En el ejemplo anterior es evidente que

κ(x) = |f ′(x)|


Ası pues, un problema (en ambos sentidos) estara mejor condicionado mientras

mas se acerque a 1 su numero de condicion.

Ejemplo 1.1 Si queremos calcular la tangente de 89◦59′ lo primero que de-

bemos hacer es expresar el angulo en radianes, por lo que necesariamente

debemos redondear el dato (el numero π hay que redondearlo), por lo que el

dato vendra afectado de un error de redondeo.

Utilicemos el metodo que utilicemos, dado que | tg x−tg x| ' |1+tg 2 x|·|x−x|y tg x→ +∞ cuando x→ π, el problema estara mal condicionado.

Sin embargo si tenemos en cuenta que tg (a + b) =tg a+ tg b

1− tg a tg bpodemos

reducir nuestro problema al calculo de la tangente de 44◦59′ resultando este

un proceso bien condicionado, ya que tg 45 = 1. �

Definicion 1.4 [Estabilidad de un algoritmo]

Respecto al algoritmo que se utiliza para resolver un determinado problema,

diremos que es inestable cuando los errores que se cometen en los diferentes

pasos del algoritmo hacen que el error total que se genera sea muy grande.

Si, por el contrario los errores que se producen en los distintos pasos no alteran

de forma significativa el resultado del problema, diremos que el algoritmo es

estable.

Ejemplo 1.2 Supongamos que se quiere calcular la integral

I10 =

∫ 1

0

x10

a+ xdx

Llamando In =

∫ 1

0

xn

a+ xdx observamos que

In =

∫ 1

0

xn

a+ xdx =

∫ 1

0

xn−1(x+ a− a)

a+ xdx =

=

∫ 1

0

xn−1(x+ a)

a+ xdx− a

∫ 1

0

xn−1

a+ xdx =

∫ 1

0

xn−1dx− a∫ 1

0

xn−1

a+ xdx =

=

[xn

n

]1

0

− aIn−1 =1

n− aIn−1

Errores y condicionamiento en problemas numericos 5

por lo que podemos pensar en la posibilidad de calcular I10 de forma recursiva

mediante el siguiente algoritmo:

Algoritmo

I0 = ln

a+ 1

a

In =1

n− aIn−1

Sin embargo, dado que para a = 10 es I0 = ln11

10= 0.09531017980432 . . .

y el numero 0.09531017980432 . . . no podemos introducirlo en el ordenador

de manera exacta, debemos cometer algun error introduciendo un numero

aproximado I0 de tal forma que cometemos un error inicial ε0 = |I0 − I0|.

El error εn que se cometera al calcular In vendra dado por

εn = |In − In| =∣∣∣∣ 1n − aIn−1 − (

1

n− aIn−1)

∣∣∣∣ = | − a(In−1 − In−1)| = |a|εn−1

es decir,

εn = |a|εn−1 = |a|2εn−2 = · · · = |a|nε0

por lo que si tomamos las 10 primeras cifras decimales de I0, es decir, si

tomamos

I0 = 0.0953101798 con ε0 < 10−10

obtendremos un error en la decima iteracion

ε10 < 1010 · 10−10 = 1

en otras palabras,

I10 no tiene ninguna cifra decimal exacta

Se trata pues de un algoritmo muy inestable. �

Observese que si el algoritmo es inestable no va a generar un resultado fiable,

por lo que deberemos utilizar otro algoritmo. Sin embargo, por muy estable

que sea el algoritmo, si el problema esta mal condicionado lo unico que pode-

mos hacer es plantear un problema equivalente al nuestro pero con la seguridad

de que se trata de un problema bien condicionado.


1.2 Metodo y algoritmo de la biseccion: ana-

lisis de errores

Teorema 1.1 [Teorema de Bolzano]

Si f es una funcion continua en el intervalo cerrado [a, b] y f(a) · f(b) < 0,

existe un punto α ∈ (a, b) en el cual f(α) = 0.

Nuestro problema se reduce a localizarla. Para ello, supongamos que esta

separada, es decir, que en el intervalo [a, b] es la unica raız que existe. Esto

podemos garantizarlo, por ejemplo, viendo que f ′(x) 6= 0 en todo el intervalo,

ya que entonces, el Teorema de Rolle nos garantiza la unicidad de la raız.

Teorema 1.2 [Teorema de Rolle]

Si f(x) es una funcion continua en el intervalo [a, b], derivable en (a, b) y

f(a) = f(b), existe un punto α ∈ (a, b) para el que f ′(α) = 0.

En efecto, si f(x) tuviese dos raıces α1 y α2 en el intervalo [a, b], verificarıa

las hipotesis del teorema de Rolle en el intervalo [α1, α2] ⊂ [a, b], por lo que

deberıa existir un punto α ∈ (α1, α2) =⇒ α ∈ (a, b) en el que se anulara la

derivada, por lo que si f ′(x) 6= 0 en todo el intervalo [a, b], no pueden existir

dos raıces de la ecuacion en dicho intervalo.

Metodo de la biseccion o dicotomıa

Supongamos que tenemos separada una raız x de la ecuacion f(x) = 0 en el

intervalo [a1, b1] = [a, b] es decir

sig f(a) 6= sig f(b) y f ′(x) 6= 0 ∀x ∈ [a, b]

Tomando el punto medio x1 =a1 + b1

2

• Si f(x1) = 0, hemos encontrado la solucion: x = x1.

• Si f(x1) 6= 0, solo en uno de los dos subintervalos [a1, x1] o [x1, b1] se pro-

ducira un cambio de signo en los extremos y el teorema de Bolzano nos

asegura que la raız se encuentra en el subintervalo en el que se produce

dicho cambio de signo, al cual lo renombramos como [a2, b2]

Metodo y algoritmo de la biseccion: analisis de errores 7

Reiterando el procedimiento podemos construir una sucesion de interva-

los [an, bn] con amplitudes

|bn − an| =|b− a|

2n−→ 0 cuyos puntos medios xn −→ x

Cota del “error a priori”

El error cometido, tomando como raız de la ecuacion el punto medio xn del

intervalo [an, bn] obtenido en la en la iteracion n-esima, viene dado por

εn ≤b− a

2n

por lo que si b − a = 1 y n = 10 se tiene que ε10 ≤1

210< 10−3, es decir,

en 10 iteraciones obtenemos tres cifras decimales exactas, por lo que podemos

estimar el error de una determinada iteracion sin necesidad de realizarlas pre-

viamente.

Lo verdaderamente importante de esta formula del error a priori es que nos

permite conocer el numero de iteraciones que van a ser necesarias para obtener

la raız con una determinada precision.

Ası, por ejemplo, si queremos obtener la solucion de la ecuacion f(x) = 0 en

el intervalo [a, b] de amplitud 1 con 14 cifras decimales exactas, debera ser

εn ≤1

2n< 10−14 ⇐⇒ 2n > 1014 =⇒ n ≥ 47

es decir, deberemos detenernos en la iteracion 47.

Algoritmo de la biseccion

Para i = 1, . . . , n, . . ., Ii = [ai, bi] y mi =ai + bi

2(punto medio de Ii) con

I1 = [a, b] y Ii+1 =

[ai,mi] si sig(f(ai)) 6= sig(f(mi))

[mi, bi] si sig(f(bi)) 6= sig(f(mi))

El proceso debe repetirse hasta que

f(mi) = 0 o bien bi − ai < ε con ε > 0 prefijado.

Un algoritmo para MatLab con entradas a, b, ε y f(x) y salida la raız m serıa

el siguiente:


Algoritmo de la Biseccion

while (b-a)/2>εm = a+(b-a)/2;

if f(m) == 0

a = m;

b = m;

end

if sign f(a) == sign f(m)

a = m;

else

b = m;

end

end

m

El hecho de calcular el punto medio de [a, b] como m = a+ (b−a)/2 es debido

a que para valores muy pequenos de a y b puede darse el caso de que (a+ b)/2

se encuentre fuera del intervalo.

Metodo de la “Regula falsi”

Una variante del metodo de la biseccion es el metodo de la regula falsi , de la

falsa posicion o metodo de la cuerda consistente en dividir el intervalo [a, b] en

dos subintervalos [a, c] ∪ [c, b] donde el punto c, a diferencia del punto medio

del metodo de la biseccion, es el punto de corte de la recta secante que pasa

por los puntos (a, f(a)) y (b, f(b)) con el eje de abscisas OX.

f(b)

f(a)

(c, 0)

(a, f(a))

(b, f(b))

O

Y

X

��

tt

tFigura 1.1: Metodo de la regula falsi.


La pendiente de dicha secante viene determinada por

m =f(b)− f(a)

b− a=

0− f(b)

c− b

Segun se utilicen los puntos (a, f(a)) y (b, f(b)) o (c, 0) y (b, f(b)) respectiva-

mente.

Despejando el valor de c obtenemos que

c = b− f(b) · b− af(b)− f(a)

=af(b)− bf(a)

f(b)− f(a)

pudiendose dar los mismos casos que en el metodo de la biseccion, es decir:

• Si f(c) = 0 la raız buscada es c.

• Si f(a) y f(c) tienen signos contrarios, la raız se encuentra en el intervalo

[a, c].

• Si son f(c) y f(b) los que tienen signos contrarios, la raız esta en el

intervalo [c, b].

El algoritmo con entradas a, b, ε y f(x) y salida la raız c serıa el siguiente:

Algoritmo de la Regula falsi

c = a;

while abs f(c)>εc = (a*f(b)-b*f(a))/(f(b)-f(a));

if f(c) == 0

a = c;

b = c;

end

if sign f(a) == sign f(c)

a = c;

else

b =c;

end

end

c


En este caso las amplitudes de los intervalos [an, bn] no se van reduciendo a la

mitad como en el caso del metodo de dicotomıa, por lo que ya no es valida

la formula del error a priori, siendo necesario encontrar otra forma de poder

estimar el error que se comete en cada iteracion.

Error “a posteriori”

Supongamos conocido que la funcion f(x) tiene un cero en el intervalo [a, b] y

que por cualquier metodo hemos aproximado la solucion como xn.

Lo primero que se nos ocurre para comprobar si es valido el resultado es

calcular f(xn) y, en general, obtendremos que f(xn) 6= 0 ya que no tendremos

exactamente la raız x sino una aproximacion.

Supongamos que obtenemos f(xn) = 2.2345.

¿estamos cerca o lejos de la raız buscada?

Si la pendiente de la funcion en dicho punto f ′(xn) es grande estaremos cerca

de ella, pero si es pequena estaremos lejos.

f(x)f(x)

x xxn

Figura 1.2: El error es inversamente proporcional a la pendiente.

Ası pues, el error es inversamente proporcional a la pendiente de la funcion,

en otras palabras,

ε ≈ |f(xn)||f ′(x)|

¿Donde debemos medir la pendiente?

Si la medimos en un punto en concreto puede que sea muy grande y pensemos

que estamos muy cerca de la solucion cuando aun estamos muy lejos.


xn

f(x)

f(x)

xx

Figura 1.3: Se debe tomar el mınimo valor de la pendiente.

Debemos, por tanto, tomar el mınimo valor de la pendiente en todo el intervalo,

para decir que

εn ≤|f(xn)|

mınx∈(a,b)

|f ′(x)|(1.1)

Veamos ahora una justificacion formal de la formula anterior.

Teorema 1.3 [Teorema del valor medio]

Si f(x) es una funcion continua en el intervalo [a, b] y derivable en (a, b),

existe un punto c ∈ (a, b) tal quef(b)− f(a)

b− a= f ′(c).

Sea x una solucion de la ecuacion f(x) = 0 y sea xn una aproximacion de ella

obtenida por un metodo iterado cualquiera.

Supongamos f(x) continua en el intervalo cerrado [xn, x] o [x, xn] (dependiendo

de que x sea mayor o menor que xn) y derivable en el abierto.

Existe entonces un punto c ∈ (xn, x) o c ∈ (x, xn) tal que

f(x)− f(xn)

x− xn

= f ′(c).


Como f(x) = 0, nos queda que x− xn = −f(xn)

f ′(c), obteniendose:

εn =|f(xn)||f ′(c)|

≤ |f(xn)|mın

x∈{

(x, xn)

(xn, x)

|f ′(x)|≤ |f(xn)|

mınx∈(a,b)

|f ′(x)|con

(x, xn)

(xn, x)

}∈ (a, b)

Lo unico que debemos exigir es que la derivada de la funcion no se anule en

ningun punto del intervalo (a, b).

Tengase en cuenta que si la funcion esta mal condicionada es decir, si |f ′(x)| es

muy grande, el calculo de f(xn) estara muy mal condicionado ya que cualquier

error en el valor de xn hace que lo que estemos calculando sea f(xn) en un

punto x′n muy cercano a xn verificandose que

|f(x′n)− f(xn)| ' |x′n − xn| · |f ′(xn)|

es decir, puede que obtengamos por ejemplo que f(xn) = k y sin embargo su

verdadero valor difiera mucho de k debido a la fuerte pendiente existente en

dicho punto, con lo que obtendremos una cota erronea del error.

Debemos, por tanto, asegurarnos de que nuestro problema esta bien condicio-

nado, es decir, no existen en el intervalo pendientes muy grandes (condiciona-

miento directo) ni muy pequenas (condicionamiento inverso) para garantizar

la fiabilidad del “error a posteriori”.

Aplicando el metodo de la regula falsi al calculo de la raız de 3, se obtienen

14 cifras decimales exactas, en solo 14 iteraciones frente a las 47 necesarias

mediante el metodo de la biseccion.

Sin embargo, en el metodo de la regula falsi la convergencia no tiene porque

ser mas rapida que en el de la biseccion.

Ambos metodos son de convergencia lenta siendo necesario, por tanto, buscar

otros metodos cuya convergencia sea mas rapida.

Dichos metodos estan basados en el denominado Teorema del punto fijo que

estudiamos en la siguiente seccion.

Punto fijo e iteracion funcional 13

1.3 Punto fijo e iteracion funcional

Definicion 1.5 [Funcion contractiva]

Una funcion f : R→ R se dice contractiva si verifica que

|f(x1)− f(x2)| ≤ q |x1 − x2| ∀ x1, x2 ∈ R con q < 1

q recibe el nombre de factor de contractividad.

Lema 1.4 [Caracterizacion de las funciones contractivas]

Si una funcion f(x) continua en [a, b] y derivable en (a, b) verifica que

|f ′(x)| ≤ q < 1 ∀x ∈ [a, b]

es contractiva en dicho intervalo.

Demostracion. Para cualquier par de puntos x1, x2 ∈ [a, b]

f(x1)− f(x2) = (x1 − x2)f′(c) con c ∈

{[x1, x2]

[x2, x1]=⇒ c ∈ [a, b]

|f(x1)− f(x2)| = |x1 − x2| · |f ′(c)| ≤ q |x1 − x2| con q < 1

por lo que es contractiva en [a, b].

Definicion 1.6 [Punto fijo]

Se dice que x es un punto fijo de la funcion f(x) si f(x) = x.

Teorema 1.5 [Teorema del punto fijo]

Sea ϕ(x) una funcion continua en [a, b], derivable en (a, b), con ϕ([a, b]) ⊆ [a, b]

tal que |ϕ′(x)| ≤ q < 1 ∀x ∈ [a, b], y sea x0 un punto cualquiera del intervalo

[a, b]. La sucesion

x0, x1, x2, . . . , xn, . . . con xn+1 = ϕ(xn)

converge al unico punto fijo de la funcion ϕ(x) en [a, b].


Demostracion.

• Convergencia

xn+1 − xn = ϕ(xn)− ϕ(xn−1) = (xn − xn−1)ϕ′(c) con c ∈

{[xn, xn+1]

[xn+1, xn]

y por tanto, con c ∈ [a, b].

|xn+1 − xn| = |xn − xn−1| · |ϕ′(c)| ≤ q|xn − xn−1|

por lo que

|x2 − x1| ≤ q|x1 − x0||x3 − x2| ≤ q|x2 − x1| ≤ q2|x1 − x0|

...

|xn+1 − xn| ≤ qn|x1 − x0|...

|x0|+ |x1 − x0|+ |x2 − x1|+ · · ·+ |xn+1 − xn|+ · · · ≤

≤ |x0|+ |x1 − x0|+ q|x1 − x0|+ · · ·+ qn|x1 − x0|+ · · · =

= |x0|+ |x1 − x0|(1 + q + · · ·+ qn + · · ·) con q < 1 =⇒

|x0|+ |x1 − x0|+ · · ·+ |xn+1 − xn|+ · · · ≤ |x0|+ |x1 − x0|1

1− q

por lo que la serie

Sn = x0 + (x1 − x0) + (x2 − x1) + · · ·+ (xn+1 − xn) + · · ·

es convergente por ser absolutamente convergente. Dado que

S1 = x0

S2 = x0 + (x1 − x0) = x1

...

Sn+1 = Sn + (xn − xn−1) = xn

...

la convergencia de Sn nos garantiza la de la sucesion (xn).


• Convergencia al punto fijo

x = limxn =⇒ ϕ(x) = ϕ(limxn) = limϕ(xn) = lim xn+1 = ϕ(x)

es decir

ϕ(x) = x =⇒ x = limxn es punto fijo de ϕ(x) en [a, b]

• Unicidad

Sea x′ otro punto fijo de ϕ(x) en [a, b]].

|x−x′| = |ϕ(x)−ϕ(x′)| = |(x−x′)ϕ′(c)| = |(x−x′)| · |ϕ′(c)| con c ∈ [a, b]

|x− x′|(1− |ϕ′(c)|) = 0

y dado que |ϕ′(c)| ≤ q < 1 =⇒ 1 − |ϕ′(c)| 6= 0, obtenemos que

|x− x′| = 0 y, por tanto, que x = x′.

En otras palabras, x es el unico punto fijo de la funcion ϕ(x) en el

intervalo [a, b].

Interpretacion geometrica del teorema del punto fijo

Dependiendo de los valores que toma ϕ′(x) en el intervalo [a, b], podemos

distinguir cuatro casos:

a) ϕ′(x) < −1 b) − 1 < ϕ′(x) < 0

c) 0 < ϕ′(x) < 1 d) ϕ′(x) > 1

pudiendose observar (vease la Fig. 1.4) que en los casos (a) y (d) la sucesion

resulta ser divergente ya que |ϕ′(x) > 1|.

En los casos (b) y (c), en los que |ϕ′(x)| ≤ q < 1 el metodo converge

monotonamente en (b) y de forma oscilatoria en (c).

Aplicacion a la resolucion de ecuaciones

Si se desea resolver la ecuacion f(x) = 0, se escribe esta de la forma x = ϕ(x),

donde ϕ(x) es una funcion contractiva, y partiendo de un determinado valor

inicial x0, se construye la sucesion xn+1 = ϕ(xn).


Figura 1.4: Esquema de la convergencia para el teorema del punto fijo.

El teorema del punto fijo nos garantiza la convergencia de esta sucesion al

punto fijo de la funcion ϕ(x) o lo que es lo mismo, a la raız de la ecuacion

f(x) = 0.

Para acotar el error de una determinada iteracion utilizamos la formula (1.1)

del error “a posteriori”.

Ejemplo 1.3 El calculo de la raız cuadrada de 3 equivale al calculo de la raız

positiva de la ecuacion x2 = 3. Aunque mas adelante veremos metodos cuya

convergencia es mas rapida, vamos a realizar los siguientes cambios:

x2 = 3 =⇒ x+ x2 = x+ 3 =⇒ x(1 + x) = 3 + x =⇒ x =3 + x

1 + x

Es decir, hemos escrito la ecuacion de la forma x = ϕ(x) con

ϕ(x) =3 + x

1 + x

Dado que sabemos que la raız de 3 esta comprendida entre 1 y 2 y que

|ϕ′(x)| = 2

(1 + x)2≤ 2

22=

1

2< 1 para cualquier x ∈ [1, 2]


|ϕ′(x)| = 2

(1 + x)2≥ 2

32=

2

9para cualquier x ∈ [1, 2]

podemos garantizar que partiendo de x0 = 1 el metodo convergera a la raız

cuadrada de 3 y que el “error a posteriori” sera fiable.

Ası pues, partiendo de x0 = 1 y haciendo xn+1 =3 + xn

1 + xn

obtenemos:

x1 = 2

x2 = 1.66666666666667

x3 = 1.75000000000000

x4 = 1.72727272727273

x5 = 1.73333333333333

x6 = 1.73170731707317

x7 = 1.73214285714286

x8 = 1.73202614379085

x9 = 1.73205741626794

x10 = 1.73204903677758

x11 = 1.73205128205128

x12 = 1.73205068043172

x13 = 1.73205084163518

x14 = 1.73205079844084

x15 = 1.73205081001473

x16 = 1.73205080691351

x17 = 1.73205080774448

x18 = 1.73205080752182

x19 = 1.73205080758148

x20 = 1.73205080756550

x21 = 1.73205080756978

x22 = 1.73205080756863

x23 = 1.73205080756894

x24 = 1.73205080756886

x25 = 1.73205080756888

x26 = 1.73205080756888

El error vendra dado por εn <|f(xn)|

mınx∈[1,2]

|f ′(x)|donde f(x) = x2 − 3, por lo que

ε26 <|x2

26 − 3|2

= 4.884981308350688 · 10−15 < 10−14

es decir,√

3 = 1.73205080756888 con todas sus cifras decimales exactas. �

Habıamos visto que el metodo de la regula falsi solo necesitaba de 14 iteraciones

mientras que ahora hemos necesitado 26.

¿A que se debe que la convergencia haya sido muy lenta?

La respuesta es bien sencilla: a la mala eleccion de la funcion ϕ(x).

¿De que dependera la velocidad de convergencia?


Orden de convergencia

• ϕ(x) =x

2en [−1, 1] es contractiva ya que |ϕ′(x)| = 1

2< 1 ∀x ∈ [−1, 1]

x0 = 1 =⇒ x1 = 0′5 ⇒ x2 = 0′25 ⇒ x3 = 0′125 =⇒ x4 = 0′0625 · · ·

Observamos que la convergencia a cero es lenta y ello es debido a que

ϕ′(0) 6= 0 =⇒ convergencia lineal o de primer orden.

• ϕ(x) =x2

4en [−1, 1] es contractiva: |ϕ′(x)| =

∣∣∣x2

∣∣∣ ≤ 1

2< 1 ∀x ∈ [−1, 1]

x0 = 1 ⇒ x1 = 0′25 ⇒ x2 = 0′015625 ⇒ x3 = 6′105 . . . · 10−5 · · ·

La convergencia a cero es ahora rapida debido a que

ϕ′(x) =x

2⇒ ϕ′(0) = 0

ϕ′′(x) =1

2⇒ ϕ′′(0) 6= 0

⇒ convergencia de segundo orden.

• ϕ(x) =x3

6en [−1, 1] es contractiva: |ϕ′(x)| =

∣∣∣∣x2

2

∣∣∣∣ ≤ 1

2< 1 ∀x ∈ [−1, 1]

x0 = 1 ⇒ x1 = 0′16666 ⇒ x2 = 0′00077 ⇒ x3 = 7′6565 · 10−11 · · ·

La convergencia a cero es ahora muy rapida debido a que

ϕ′(x) =x2

2⇒ ϕ′(0) = 0

ϕ′′(x) = x ⇒ ϕ′′(0) = 0

ϕ′′′(x) = 1 ⇒ ϕ′′′(0) 6= 0

=⇒ convergencia de tercer orden.

EL orden de convergencia nos lo da el orden de la primera derivada de la

funcion ϕ(x) que no se anula en su punto fijo x.

La funcion ϕ(x) =3 + x

1 + xque obtuvimos para calcular

√3 en el Ejemplo 1.3

verifica que

ϕ′(x) =1

(1 + x)2=⇒ ϕ′(

√3) =

1

(1 +√

3)26= 0

por lo que ha resultado una convergencia de primer orden (similar a la de los

metodos de la biseccion y la regula falsi).

Analisis del metodo de Newton-Raphson 19

¿Como elegir una funcion de iteracion ϕ(x) que nos garantice una convergen-

cia, al menos, de segundo orden?

Vamos a ver como el metodo de Newton-Raphson, generalmente conocido como

metodo de Newton, nos permite escribir la ecuacion f(x) = 0 de la forma

x = ϕ(x) de tal manera que la convergencia sea, al menos de segundo orden.

1.4 Analisis del metodo de Newton-Raphson

Si tratamos de resolver la ecuacion f(x) = 0 y lo que obtenemos no es la

solucion exacta x sino solo una aproximacion xn tal que x = xn +h tendremos

que

f(x) ' f(xn) + h · f ′(xn) =⇒ h ' − f(xn)

f ′(xn)=⇒ x ' xn −

f(xn)

f ′(xn)

obteniendose la denominada formula de Newton-Raphson

xn+1 = xn −f(xn)

f ′(xn)(1.2)

Hemos transformado la ecuacion f(x) = 0 en x = ϕ(x) con

ϕ(x) = x− f(x)

f ′(x)

Si partiendo de x0 ∈ [a, b] la sucesion (xn) con xn+1 = ϕ(xn) = xn −f(xn)

f ′(xn)converge entonces ϕ(x) es contractiva.

Ademas:

limxn+1 = limxn −f(limxn)

lim f ′(xn)=⇒ f(limxn)

lim f ′(xn)= 0 =⇒ f(limxn) = 0

es decir, limxn = x.

Interpretacion geometrica: Metodo de la tangente

Si trazamos la tangente a la curva y = f(x) en el punto (xn, f(xn)) obtenemos

la recta

y = f(xn) + f ′(xn)(x− xn)


que corta al eje y = 0 en el punto de abscisa

x = xn −f(xn)

f ′(xn)

que es precisamente el valor de xn+1 de la formula de Newton-Raphson.

En otras palabras, xn+1 viene determinado por el punto en el que la tangente

a la curva y = f(x) en (xn, f(xn)) corta al eje de abscisas, por lo que este

metodo es tambien conocido como metodo de la tangente.

xx0x1x2

y = f(x)

Figura 1.5: Interpretacion geometrica del metodo de Newton.

Orden de convergencia

Si el metodo converge, ϕ(x) = x− f(x)

f ′(x)es contractiva y ademas

ϕ′(x) = 1− f ′2(x)− f(x)f ′′(x)

f ′2(x)=f(x)f ′′(x)

f ′2(x)con f ′(x) 6= 0 =⇒ ϕ′(x) = 0

El metodo de Newton es, al menos, de segundo orden.

Cota del error: Error “a priori”

La diferencia entre la solucion exacta x y la aproximacion xn+1 viene dada por

en+1 = x− xn+1 = x− xn +f(xn)

f ′(xn)= en +

f(xn)

f ′(xn)

Dado que

0 = f(x) = f(xn + en) = f(xn) + f ′(xn)en +f ′′(t)

2e2n con t ∈

{(x, xn)

(xn, x)


Si f ′(x) 6= 0 ∀x ∈ [a, b] podemos dividir entre f ′(xn) 6= 0 obteniendose

0 =f(xn)

f ′(xn)+ en +

f ′′(t)

2e2n = en+1 +

f ′′(t)

2e2n

Tomando valores absolutos:

εn+1 =|f ′′(t)|

2|f ′(xn)|ε2

n ≤ k ε2n con k ≥ max |f ′′(x)|

2 mın |f ′(x)|

es decir, en cada iteracion dispondremos, aproximadamente, del doble de cifras

decimales exactas que en la iteracion anterior, que es lo que significa el hecho

de ser una convergencia de segundo orden.

Ademas, podemos obtener, multiplicando por k,

kεn+1 ≤ k2ε2n = (kεn)2 ≤ (kεn−1)

4 ≤ (kεn−2)8 ≤ · · · ≤ (kε0)

2n+1

=⇒

εn ≤1

k(kε0)

2n

con k ≥ max |f ′′(x)|2 mın |f ′(x)|

lo que nos proporciona una cota del error “a priori”, pudiendose garantizar la

convergencia siempre que kε0 < 1 es decir, si ε0 ≤1

k.

Algoritmo

Una vez realizado un estudio previo para ver que se cumplen las condiciones

que requiere el metodo, establecer el valor inicial x0 y calcular el valor de

m = mınx∈[a,b]

|f ′(x)|, el algoritmo, que tiene por entradas los valores de a, b, x, ε,

f(x) y m y por salida la raız x, es el siguiente:

Algoritmo de Newton

e = abs (f(x)/m);

while e>εx = x-f(x)/f′(x);

e = abs (f(x)/m);

end

x


Ejemplo 1.4 En el Ejemplo 1.3 calculamos la raız de 3 con 14 cifras decimales

exactas en 26 iteraciones. Vamos a ver como se disminuye considerablemente

el numero de iteraciones cuando se utiliza la formula de Newton-Raphson.

Partimos de la ecuacion f(x) = x2 − 3 = 0, por lo que la formula de Newton-

Raphson nos dice que

xn+1 = xn −f(xn)

f ′(xn)= xn −

x2n − 3

2xn

=x2

n + 3

2xn

=1

2

(xn +

3

xn

)

Dado que la raız de 3 es un numero comprendido entre 1 y 2 y la funcion

f ′(x) = 2x no se anula en dicho intervalo, podemos aplicar el metodo de

Newton tomando como valor inicial x0 = 2. (Mas adelante veremos porque

debemos tomar 2 como valor inicial), obteniendose:

x0 = 2

x1 = 1.75000000000000

x2 = 1.73214285714286

x3 = 1.73205081001473

x4 = 1.73205080756888

El error vendra dado, al igual que en el Ejemplo 1.3 por εn <|f(xn)|

mınx∈[1,2]

|f ′(x)|,

por lo que

ε4 <|x2

4 − 3|2

= 4.884981308350688 · 10−15 < 10−14

es decir,√

3 = 1.73205080756888 con todas sus cifras decimales exactas. �

La formula xn+1 =1

2

(xn +

A

xn

)es conocida como formula de Heron ya que

este matematico la utilizaba para aproximar la raız cuadrada de un numero

real positivo A hacia el ano 100 a.C. pues sabıa que si disponıa de un valor

aproximado xn y este fuese mayor que la raız buscada, necesariamente A/xn

serıa menor que su raız y viceversa, por lo que la media entre ambos debıa ser

una mejor aproximacion que xn. En otras palabras, en cada iteracion tomaba

como aproximacion de la raız la media aritmetica entre el valor xn anterior y

el cociente A/xn.


Analisis de la convergencia: Regla de Fourier

Hay que tener en cuenta que la naturaleza de la funcion puede originar difi-

cultades, llegando incluso a hacer que el metodo no converja.

Ejemplo 1.5 Tratemos de determinar, por el metodo de Newton-Raphson, la

raız positiva de la funcion f(x) = x10−1, tomando como valor inicial x0 = 0.5.

La formula de Newton-Raphson es, en este caso,

xn+1 = xn −x10

n − 1

10x9n

.

Aplicando el algoritmo se obtienen los valores

x1 = 51.65

x2 = 46.485

x3 = 41.8365

x4 = 37.65285

x5 = 33.887565

x10 = 20.01026825685012

x20 = 6.97714912329906

x30 = 2.43280139954230

x40 = 1.00231602417741

x41 = 1.00002393429084

x42 = 1.00000000257760

x43 = 1

Puede observarse que la convergencia es muy lenta y solo se acelera (a partir

de x40) cuando estamos muy cerca de la raız buscada. �

• Si en las proximidades de la raız existe un punto de inflexion, las itera-

ciones divergen progresivamente de la raız.

��

��

��

��9x0x1

x2x

Figura 1.6: En las proximidades de un punto de inflexion puede diverger.


• El metodo de Newton-Raphson oscila en los alrededores de un maximo

o un mınimo local, persistiendo o llegando a encontrarse con pendientes

cercanas a cero, en cuyo caso la solucion se aleja del area de interes.

�

x0 x1x

y = f(x)

Figura 1.7: En las proximidades de un extremo local puede oscilar o diverger.

¿Quiere decir eso que el metodo de Newton puede ser divergente?

El metodo de Newton siempre converge en las proximidades de la raız. El

problema surge cuando se toma un valor inicial x0 inadecuado (proximo a un

punto crıtico).

¿Como podemos saber que el valor inicial x0 es adecuado?

La eleccion de x0: Regla de Fourier

Si la funcion f(x) cambia de signo en los extremos de un intervalo [a, b] y

ademas, en dicho intervalo, no se anulan ni f ′(x) ni f ′′(x), nos aseguramos

de que en [a, b] existe una unica raız de la ecuacion f(x) = 0 y no existen

extremos locales ni puntos de inflexion.

Por otra parte, como no nos interesa que x0 este situado cerca de un extremo

local, vamos a estudiar los diferentes casos con que podemos encontrarnos

y elegir, en cada uno de ellos, un valor adecuado para x0 (aquel que no se

encuentre cercano a un extremo local).


f ′(x) > 0f ′′(x) < 0

f ′(x) > 0f ′′(x) > 0

f ′(x) < 0f ′′(x) > 0

f ′(x) < 0f ′′(x) < 0

ab

ab a

ba

b

x0 = a x0 = b x0 = a x0 = b

Figura 1.8: Los cuatro casos posibles

Observese que en cualquiera de los cuatro casos (vease la Figura 1.8) hemos

optado por elegir, como valor inicial x0, el extremo en el que la funcion tiene

el mismo signo que su segunda derivada.

Este resultado, que formalizamos a continuacion en forma de teorema es co-

nocido como regla de Fourier.

Teorema 1.6 [Regla de Fourier]

Sea f(x) una funcion continua y dos veces derivable [a, b]. Si sig f(a) 6= sig f(b)

y sus dos primeras derivadas f ′(x) y f ′′(x) no se anulan en [a, b] existe una

unica raız de la ecuacion f(x) = 0 en dicho intervalo y se puede garantizar la

convergencia del metodo de Newton tomando como valor inicial x0 el extremo

del intervalo en el que la funcion y su segunda derivada tienen el mismo signo.

1.4.1 Metodo de Newton generalizado

Cuando el metodo de Newton converge lentamente se debe a que la raız que

estamos aproximando es multiple.

Supongamos que x fuese una raız doble de f(x). La funcion de iteracion

ϕ(x) = x− f(x)

f ′(x)del metodo de Newton verifica que

ϕ′(x) = 1− f ′ 2(x)− f(x)f ′′(x)

f ′ 2(x)=f(x)f ′′(x)

f ′ 2(x)

ϕ′(x) es una indeterminacion del tipo 00

que resulta ser distinta de cero, por lo


que la convergencia es de primer orden. De ahı su lentitud.

¿Serıa posible alguna modificacion en el metodo para que la convergenciavolviese a ser, al menos, de segundo orden?

• La raız x de f(x) tambien lo es de g(x) =f(x)

f ′(x)pero con la particularidad

de que

ϕ(x) = x− g(x)

g′(x)

verifica que ϕ′(x) y ϕ′′(x) tienden a cero cuando x lo hace a x, por lo

que al aplicar el metodo de Newton a la funcion g(x) obtenemos x con

una convergencia de, al menos, tercer orden.

Este proceso tiene el inconveniente de que si f(x) es, por ejemplo, un

polinomio, g(x) es una funcion racional, por lo que se complican los

calculos.

• Sea x una raız de multiplicidad k de la ecuacion f(x) = 0.

Si en vez de hacer xn+1 = xn −f(xn)

f ′(xn)hacemos

xn+1 = xn − kf(xn)

f ′(xn)(1.3)

donde k representa el orden de la primera derivada que no se anula para

x = x (multiplicidad de la raız x), la convergencia vuelve a ser, al menos,

de segundo orden.

En la practica, el problema es que no conocemos k pero podemos determinar

su valor estudiando las derivadas de la funcion f(x).

Ejemplo 1.6 Para resolver la ecuacion x − senx = 0 comenzamos por ex-

presarla de la forma x = senx, por lo que las soluciones seran los puntos de

interseccion de la curva y = senx con y = x (Fig.1.9).

Aunque es conocido que la solucion de la ecuacion es x = 0, supondremos que

solo conocemos que esta comprendida entre -1 y 1 y vamos aplicar el metodo

de Newton.

xn+1 = xn −xn − senxn

1− cosxn

=senxn − xn cosxn

1− cosxn


y = x

y = senx

1

-1

0

��

��

��

��

Figura 1.9: Las graficas de y = x e y = senx.

Comenzando con x0 = 1 se obtiene:

x0 = 1

. . . . . . . . . . . . . . . . . . . . .

x10 = 0.016822799 . . .

f ′(x10) = 0.0001 . . .

f ′′(x10) = 0.016 . . .

f ′′′(x10) = 0.9998 . . .

. . . . . . . . . . . . . . . . . . . . .

x20 = 0.0000194 . . .

f ′(x20) = 0.00000001 . . .

f ′′(x20) = 0.0019 . . .

f ′′′(x20) = 0.9999 . . .

Como la convergencia es muy lenta, hace pensar que se trata de una raız

multiple. Ademas, como la primera y la segunda derivadas tienden a cero y

la tercera lo hace a 1, parece que nos encontramos ante una raız triple, por lo

que aplicamos el metodo generalizado de Newton.

xn+1 = xn − 3xn − senxn

1− cosxn

que comenzando, al igual que antes, por x0 = 1 se obtiene:

x0 = 1

x1 = −0.034 . . .

x2 = 0.000001376 . . .

x3 = 0.00000000000009 . . .

que se ve que converge rapidamente a x = 0. �


1.5 Un problema mal condicionado: ceros de

un polinomio

Si queremos resolver la ecuacion P (x) = 0 el problema viene condicionado por

los valores de |P ′(x)| (su numero de condicion), por lo que si la derivada es

muy pequena el problema estara mal condicionado, pero si la derivada es muy

grande cualquier metodo se hace muy lento, por lo que lo ideal serıa que la

derivada estuviese muy proxima a 1, pero claro esta, ese derivada ha de estar

muy proxima a 1 en todas las raıces del polinomio, cosa que es estadısticamente

casi imposible. Por tanto, el calculo de los ceros de un polinomio es un ejemplo

de problema mal condicionado. Sin embargo, vamos a estudiar como podemos

aproximar un determinado cero del polinomio.

Hemos visto que uno de los mayores problemas que presenta la resolucion de

una ecuacion es encontrarnos que posee raıces multiples ya que, en un entorno

de ellas, o bien la funcion no cambia de signo, o bien se aproxima demasiado

a cero y, por tanto, cualquier metodo puede dar soluciones erroneas.

En el caso de las ecuaciones algebraicas (Pn(x) = 0) este problema puede

solventarse buscando otra ecuacion que posea las mismas raıces que la dada

pero todas ellas simples, es decir, eliminando las raıces multiples.

Eliminacion de las raıces multiples

Por el teorema fundamental del Algebra sabemos que Pn(x) posee n raıces y,

por tanto, puede ser factorizado de la forma

Pn(x) = a0(x− x1)(x− x2) · · · (x− xn)

donde {x1, x2, . . . , xn} son los ceros del polinomio.

Si existen raıces multiples, las podemos agrupar para obtener:

Pn(x) = a0(x− x1)m1(x− x2)

m2 · · · (x− xk)mk

donde mi (i = 1, 2, . . . k) representa la multiplicidad de la raız xi y verificando-

se que m1 +m2 + · · ·mk = n

Derivando esta expresion obtenemos:

P ′(x)=na0(x− x1)m1−1 · · · (x− xk)mk−1Qk−1(x)

con Qk−1(xi) 6= 0 i = 1, 2, . . . , k

Un problema mal condicionado: ceros de un polinomio 29

Por tanto, si x es una raız de la ecuacion P (x) = 0 con multiplicidad k, es

tambien una raız de P ′(x) = 0 pero con multiplicidad k − 1.

D(x) = mcd [P (x), P ′(x)] = (x− x1)m1−1 · · · (x− xk)mk−1

por lo que

Q(x) =P (x)

D(x)= a0(x− x1)(x− x2) · · · (x− xk)

Es decir, hemos encontrado un polinomio cuyas raıces son las mismas que las

de P (x) pero todas ellas simples.

Ejemplo 1.7 El polinomio P (x) = x3 − 5x2 + 8x− 4 = (x− 1)(x− 2)2 tiene

la raız 1 simple y la 2 doble.

D(x) = mcd (P (x), P ′(x)) = mcd (x3 − 5x2 + 8x− 4, 3x2 − 10x+ 8) = x− 2

por lo que

Q(x) =P (x)

D(x)= x3 − 3x+ 2 = (x− 1)(x− 2)

que tiene las mismas raıces que P (x) pero todas simples. �

Acotacion de las raıces

Si ya conocemos que una ecuacion solo tiene raıces simples y queremos calcu-

larlas, parece apropiado que un primer paso consista en detectar donde pueden

encontrarse. Ası por ejemplo, si son reales, determinar intervalos de una am-

plitud reducida en los que se encuentren las raıces de la ecuacion.

Dada una ecuacion f(x) = 0 (en general com-pleja) se denomina acotar las raıces a bus-car dos numeros reales positivos r y R talesque r ≤ |x| ≤ R para cualquier raız x de laecuacion.Geometricamente consiste en determinar unacorona circular de radios r y R dentro de lacual se encuentran todas las raıces.En el caso real se reduce a los intervalos(−R,−r) y (r, R).


Proposicion 1.7 Si x es una raız de la ecuacion

P (x) = a0xn + a1x

n−1 + · · ·+ an−1x+ an = 0

se verifica que:

|x| < 1 +A

|a0|siendo A = max

i≥1|ai|

Demostracion. Sea P (x) = a0xn + a1x

n−1 + · · · + an−1x + an. Tomando

modulos tenemos

|P (x)| = |a0xn + a1x

n−1 + · · ·+ an−1x+ an| ≥

≥ |a0xn| − |a1x

n−1 + · · ·+ an−1x+ an| ≥

+ · · ·+ |an−1x|+ |an|]

=

= |a0xn| −

[|a1| · |xn−1|+ · · ·+ |an−1| · |x|+ |an|

]≥

≥ |a0xn| − A [|x|n−1 + · · ·+ |x|+ 1]

(Para considerar el ultimo parentesis como una progresion geometrica habrıa

que anadir los terminos que, probablemente, falten en P (x) y suponer que,

ademas, es |x| 6= 1).

|P (x)| ≥ |a0| · |x|n − A|x|n − 1

|x| − 1

Dado que el teorema es trivial para |x| < 1, supondremos que |x| > 1 y

entonces:

|P (x)| > |a0| · |x|n − A|x|n

|x| − 1= |x|n

(|a0| −

A

|x| − 1

)Como la expresion anterior es cierta para cualquier |x| > 1, sea |x| > 1 con

P (x) = 0. Entonces

0 > |x|n(|a0| −

A

|x| − 1

)=⇒ |a0| −

A

|x| − 1< 0 =⇒

|a0| <A

|x| − 1=⇒ |x| − 1 <

A

|a0|=⇒

|x| < 1 +A

|a0|con |x| > 1

Es evidente que esta cota tambien la verifican las raıces x con |x| < 1.


Proposicion 1.8 [Regla de Laguerre]

Consideremos la ecuacion

P (x) = a0xn + a1x

n−1 + · · ·+ an−1x+ an = 0

Sean C(x) = b0xn−1 + · · ·+ bn−2x+ bn−1 el cociente y r el resto de la division

de P (x) entre x− c.

Si r ≥ 0 y bi ≥ 0 para 0 ≤ i ≤ n − 1, el numero real c es una cota superior

para las raıces positivas de la ecuacion. (Trivialmente lo es tambien para las

raıces negativas).

El procedimiento consiste en comenzar con la cota obtenida anteriormente

(que no suelen ser muy buena) e ir disminuyendola hasta afinarla todo lo que

podamos.

Ejemplo 1.8 Consideremos la ecuacion 2x4 − 9x3 − x2 + 24x+ 12 = 0.

Sabemos que

|x| < 1 +A

|a0|siendo A = max

i≥1|ai| =⇒ |x| < 1 +

24

2= 13

por lo que cualquier raız real del polinomio debe estar en el intervalo (−13, 13).

Aplicando la regla de Laguerre obtenemos:

2 −9 −1 24 12

4 8 −4 −20 16

2 −1 −5 4 28

2 −9 −1 24 12

5 10 5 20 240

2 1 4 48 252

Dado que para x = 4 se obtienen valores negativos no podemos garantizar que

4 sea una cota superior para las raıces positivas de la ecuacion, pero para x = 5

todos los valores obtenidos han sido positivos, por lo que podemos garantizar

que las raıces reales de la ecuacion se encuentran en el intervalo (−13, 5).

No debemos confundir el hecho de que la regla de Laguerre no nos garantice

que 4 sea una cota superior de las raıces positivas y 5 sı lo sea, con que la


ecuacion deba tener alguna raız en el intervalo (4, 5). En otras palabras, 4

puede ser una cota superior para las raıces positivas de la ecuacion aunque la

regla de Laguerre no lo garantice. De hecho, la mayor de las raıces positivas

de nuestra ecuacion es x = 3.56155281280883 . . . < 4. �

Separacion de las raıces

Las cotas obtenidas anteriormente nos delimitan la zona en la que debemos

estudiar la existencia de soluciones de la ecuacion pero, en realidad, lo que mas

nos acerca a nuestro problema (resolver la ecuacion) es separar cada raız en un

intervalo. A este proceso se le conoce como separacion de raıces y estudiaremos

un metodo que se conoce como metodo de Sturm que nos permite separar las

raıces de una ecuacion.

1.5.1 Sucesiones de Sturm

Definicion 1.7 [Sucesion de Sturm]

Una sucesion de Sturm en [a, b] es un conjunto de funciones continuas en dicho

intervalo f0(x), f1(x), . . . , fn(x) que cumplen las siguientes condiciones:

• fn(x) 6= 0 cualquiera que sea x ∈ [a, b]. Es decir, el signo de fn(x)

permanece constante en el intervalo [a, b].

• Las funciones fi(x) y fi+1(x) no se anulan simultaneamente. En otras

palabras, si fi(c) = 0 entonces fi−1(c) 6= 0 y fi+1(c) 6= 0.

• Si fi(c) = 0 entonces fi−1(c) y fi+1(c) tienen signos opuestos, es decir,

fi−1(c) · fi+1(c) < 0. (Engloba al apartado anterior).

• Si f0(c) = 0 con c ∈ [a, b] entoncesf0(x)

f1(x)pasa de negativa a positiva

en c. (Esta bien definida en c por ser f1(c) 6= 0 y es creciente en dicho

punto).

Construccion de una sucesion de Sturm para un polinomio

La construccion de una sucesion de Sturm es, en general, complicada. Sin

embargo, cuando se trabaja con funciones polinomicas, el problema es mucho

mas simple ademas de que siempre es posible construir una sucesion de Sturm

valida para cualquier intervalo.


Dada la ecuacion algebraica Pn(x) = 0, partimos de

f0(x) = Pn(x) y f1(x) = P ′n(x)

Para determinar las demas funciones de la sucesion vamos dividiendo fi−1(x)

entre fi(x) para obtener

fi−1(x) = ci(x) · fi(c) + ri(x)

donde ri(x) tiene grado inferior al de fi(x) y hacemos

fi+1(x) = −ri(x)

Como el grado de fi(x) va decreciendo, el proceso es finito. Si se llega a un

resto nulo (el proceso que estamos realizando es precisamente el del algoritmo

de Euclides) la ecuacion posee raıces multiples y se obtiene el maximo comun

divisor D(x) de Pn(x) y P ′n(x). Dividiendo Pn(x) entre D(x) obtenemos una

nueva ecuacion que solo posee raıces simples.

La sucesionfi(x)

D(x)es una sucesion de Sturm para la ecuacion

P (x)

D(x)= Q(x) = 0

que posee las mismas raıces que P (x) = 0 pero todas simples.

Si llegamos a un resto constante, no nulo, es este quien nos determina la

finalizacion del proceso. Hemos obtenido, de esta manera, una sucesion de

Sturm valida para cualquier intervalo [a, b].

Teorema 1.9 [Teorema de Sturm]

Sea f0(x), f1(x), . . . , fn(x) una sucesion de Sturm en el intervalo [a, b] y

consideremos las sucesiones

sig[f0(a)] sig[f1(a)] · · · sig[fn(a)]

sig[f0(b)] sig[f1(b)] · · · sig[fn(b)]

teniendo en cuenta que si alguna de las funciones se anula en uno de los

extremos del intervalo [a, b] pondremos en su lugar, indistintamente, signo +

o - y denotemos por N1 al numero de cambios de signo de la primera sucesion

y por N2 al de la segunda (siempre es N1 ≥ N2).

En estas condiciones, el numero de raıces reales existentes en el intervalo [a, b]

de la ecuacion f0(x) = 0 viene dado por N1 −N2.


Ejemplo 1.9 Vamos a construir una sucesion de Sturm que nos permita se-

parar las raıces de la ecuacion x4 + 2x3 − 3x2 − 4x− 1 = 0.

f0(x) = x4 + 2x3 − 3x2 − 4x− 1. f ′0(x) = 4x3 + 6x2 − 6x− 4.

f1(x) = 2x3 + 3x2 − 3x− 2.

2x4 + 4x3 − 6x2 − 8x− 2 |2x3 + 3x2 − 3x− 2

− 2x4 − 3x3 + 3x2 + 2x x ‖ 1

x3 − 3x2 − 6x− 2 multiplicando por 2

2x3 − 6x2 − 12x− 4

−2x3 − 3x2 + 3x+ 2

−9x2 − 9x− 2

f2(x) = 9x2 + 9x+ 2.

18x3 + 27x2 − 27x− 18 |9x2 + 9x+ 2

− 18x3 − 18x2 − 4x 2x+ 1

9x2 − 31x− 18

− 9x2 − 9x− 2

−40x− 20

f3(x) = 2x+ 1.

18x2 + 18x+ 4 |2x+ 1

− 18x2 − 9x 9x ‖ 9

9x+ 4 multiplicando por 2

18x+ 8

− 18x− 9

−1

f4(x) = 1.

−∞ −3 −2 −1 0 1 2 +∞f0(x) = x4 + 2x3 − 3x2 − 4x− 1 + + − − − − + +

f1(x) = 2x3 + 3x2 − 3x− 2 − − 0 + − 0 + +

f2(x) = 9x2 + 9x+ 2 + + + + + + + +

f3(x) = 2x+ 1 − − − − + + + +

f4(x) = 1 + + + + + + + +

cambios de signo 4 4 3 3 1 1 0 0


Sabemos, por ello, que existe una raız en el intervalo (−3,−2), dos raıces en

el intervalo (−1, 0) y una cuarta raız en el intervalo (1, 2).

Como f0(−1) = −1 < 0, f0(−0.5) = 0.0625 > 0 y f0(0) = −1 < 0 podemos

separar las raıces existentes en el intervalo (−1, 0) y decir que las cuatro raıces

de la ecuacion dada se encuentran en los intervalos

(−3− 2) (−1,−0.5) (−0.5, 0) y (1, 2) �

Si, una vez eliminadas las raıces multiples y separadas las raıces, queremos

resolver la ecuacion, utilizaremos el metodo de Newton.

Al aplicarlo nos encontramos con que tenemos que calcular, en cada paso, los

valores de P (xn) y P ′(xn) por lo que vamos a ver, a continuacion, un algo-

ritmo denominado algoritmo de Horner que permite realizar dichos calculos

en tiempo lineal.

1.5.2 Algoritmo de Horner

Supongamos un polinomio P (x) y un numero real (en general tambien puede

ser complejo) x0 ∈ R. Si dividimos P (x) entre x− x0 sabemos que el resto es

un polinomio de grado cero, es decir, un numero real, por lo que

P (x) = (x− x0)Q(x) + r con

r ∈ R

y

gr[Q(x)] = gr[P (x)]− 1

Haciendo x = x0 obtenemos que

P (x0) = 0 ·Q(x0) + r =⇒ P (x0) = r

Este resultado es conocido como teorema del resto y lo enunciamos a conti-

nuacion.

Teorema 1.10 [Teorema del resto]

El valor numerico de un polinomio P (x) para x = x0 viene dado por el resto

de la division de P (x) entre x− x0.


Algoritmo de Horner

Consideremos el polinomio P (x) = a0xn + a1x

n−1 + · · ·+ an−1x+ an.

Si llamamos bi (0 ≤ i ≤ n− 1) a los coeficientes del polinomio cociente

P (x)− P (x0)

x− x0

= Q(x) = b0xn−1 + b1x

n−2 + · · ·+ bn−2x+ bn−1

se tiene que

b0 = a0

b1 = a1 + x0b0

b2 = a2 + x0b1...

bn−1 = an−1 + x0bn−2

r = P (x0) = an + x0bn−1

Este procedimiento para calcular el polinomio cociente Q(x) y el valor nume-

rico de P (x0) es conocido como algoritmo de Horner.

Ademas, dado que

P (x) = Q(x)(x− x0) + P (x0) =⇒ P ′(x) = Q′(x)(x− x0) +Q(x)

se tiene que

P ′(x0) = Q(x0)

y el calculo de Q(x0) es analogo al que hemos realizado para P (x0), es decir,

aplicando el algoritmo de Horner a Q(x) obtenemos

Q(x) = C(x)(x− x0) +Q(x0) donde Q(x0) = P ′(x0).

Regla de Ruffini

Una regla util para hacer los calculos a mano es la conocida regla de Ruffini

que consiste en disponer las operaciones como se indica a continuacion.

a0 a1 a2 · · · an−1 an

x0 x0b0 x0b1 · · · x0bn−2 x0bn−1

b0 b1 b2 · · · bn−1 P (x0)

Sistemas de ecuaciones no lineales 37

Si utilizamos la regla de Ruffini solo tenemos que volver a dividir por x0, como

se muestra a continuacion, para obtener el valor de P ′(x0).

a0 a1 a2 · · · an−2 an−1 an

x0 x0b0 x0b1 · · · x0bn−3 x0bn−2 x0bn−1

b0 b1 b2 · · · bn−2 bn−1 P (x0)

x0 x0c0 x0c1 · · · x0cn−3 x0cn−2

c0 c1 c2 · · · cn−2 P ′(x0)

Ejemplo 1.10 Consideremos el polinomio P (x) = 2x4 + x3 − 3x2 + 4x − 5

y vamos a calcular los valores de P(2) y P’(2). Aplicando reiteradamente al

regla de Ruffini obtenemos

2 1 −3 4 −5

2 4 10 14 36

2 5 7 18 31

2 4 18 50

2 9 25 68

por lo que

P (2) = 31 y P ′(2) = 68 �

Evidentemente, la regla de Ruffini nos es util para realizar calculos a mano

con una cierta facilidad, pero cuando los coeficientes de P (x) y el valor de x0

no son enteros sino que estamos trabajando con varias cifras decimales, deja

de ser efectivo y debemos recurrir al algoritmo de Horner en una maquina.

1.6 Sistemas de ecuaciones no lineales

Dado un sistema de ecuaciones no lineales

f1(x1, x2, . . . , xm) = 0

f2(x1, x2, . . . , xm) = 0

...

fm(x1, x2, . . . , xm) = 0


podemos expresarlo de la forma f(x) = 0 donde x es un vector de Rm y f una

funcion vectorial de variable vectorial, es decir:

f : D ⊂ Rm → Rm

o lo que es lo mismo, f = (f1, f2, . . . , fm) con fi : Rm → R para 1 ≤ i ≤ m.

Ejemplo 1.11 Considerese el sistema

x2 − 2x− y + 0.5 = 0

x2 + 4y2 − 4 = 0

��t t1

-1

-0.5

1

2-2

-1

f2(x)

f1(x)

Figura 1.10: Grafica del sistema.

Podemos considerarlo como la ecuacion f(x) = 0 (observese que 0 representa

ahora al vector nulo, es decir, que 0 = (0, 0)T ) con x = (x, y)T y f = (f1, f2)

siendo f1(x) = x2 − 2x− y + 0.5

f2(x) = x2 + 4y2 − 4 �

Como hemos transformado el sistema en una ecuacion del tipo f(x) = 0, parece

logico que tratemos de resolverla por algun metodo paralelo a los estudiados

para ecuaciones no lineales como puedan ser la iteracion funcional o el metodo

de Newton.


Si buscamos un metodo iterado basado en el teorema del punto fijo, debemos

escribir la ecuacion f(x) = 0 de la forma x = F (x) (proceso que puede rea-

lizarse de muchas formas, la mas sencilla es hacer F (x) = x + f(x)) para,

partiendo de un vector inicial x0 construir la sucesion de vectores

xn+1 = F (xn)

x1n+1 = F1(x

1n, x

2n, . . . , x

mn )

x2n+1 = F2(x

1n, x

2n, . . . , x

mn )

...

xmn+1 = Fm(x1

n, x2n, . . . , x

mn )

En el Ejemplo 1.11 podemos hacer

x2 − 2x− y + 0.5 = 0 =⇒ 2x = x2 − y + 0.5 =⇒ x =x2 − y + 0.5

2

x2 + 4y2 − 4 = 0 =⇒ x2 + 4y2 + y − 4 = y =⇒ y = x2 + 4y2 + y − 4

es decir,

x = F (x) con

x = (x, y)T

y

F (x) = (x2 − y + 0.5

2, x2 + 4y2 + y − 4)T

Si x es una solucion de la ecuacion y xn+1 es una aproximacion obtenida, se

tiene que

‖x− xn+1‖ = ‖F (x)− F (xn)‖ = ‖F ′(α)(x− xn)‖ ≤ ‖F ′(α)‖ · ‖x− xn‖

por lo que si ‖F ′(x)‖ ≤ q < 1 para cualquier punto de un determinado entorno

de la solucion, se tiene que

‖x− xn+1‖ ≤ ‖x− xn‖

y la sucesion

x0,x1, . . . ,xn, . . .

converge a la unica raız de la ecuacion x = F (x) en la bola considerada

(intervalo de Rm).


Es importante observar que:

• Se ha utilizado el concepto de norma vectorial al hacer uso de ‖x−xn‖.

• Se ha utilizado una version del teorema del valor medio para varias va-

riables al decir que

‖F (x)− F (xn)‖ ≤ ‖F ′(α)‖ · ‖(x− xn)‖

• Se ha utilizado el concepto de norma matricial al hacer uso de ‖F ′(α)‖ya que F ′(x) es la matriz jacobiana de la funcion F , es decir

F ′(x) =

∂F1

∂x1

· · · ∂F1

∂xm

.... . .

...

∂Fm

∂x1

· · · ∂Fm

∂xm

• Se supone que ‖F ′(α)(x − xn)‖ ≤ ‖F ′(α)‖ · ‖x − xn‖ o de forma mas

general, que para cualquier matriz A (cuadrada de orden n) y cualquier

vector de Rn se verifica que

‖Ax‖ ≤ ‖A‖ · ‖x‖

• Que el teorema del punto fijo es generalizable a funciones vectoriales de

variable vectorial.

1.6.1 Metodo de Newton para sistemas

Consideremos la ecuacion f(x) = 0 (donde f es una funcion vectorial de

variable vectorial) equivalente a un sistema de ecuaciones no lineales.

Sea x la solucion exacta del sistema y xn una aproximacion de ella. Si deno-

tamos por h = x− xn se tiene que

x = xn + h

y haciendo uso del desarrollo de Taylor obtenemos que

0 = f(x) = f(xn + h) ' f(xn) + f ′(xn)h


de donde

h ' −f ′−1(xn)f(xn)

y, por tanto

x ' xn − f ′−1(xn)f(xn).

Esta aproximacion es que utilizaremos como valor de xn+1, es decir

xn+1 = xn − f ′−1(xn)f(xn)

Observese entonces que cada iteracion del metodo de Newton se reduce al

calculo del vector h correspondiente y este no es mas que la solucion del sistema

de ecuaciones lineales

f ′(xn)h+ f(xn) = 0

En el Ejemplo 1.11 se tiene que f(x) = 0 con x = (x, y)T y f = (f1, f2)T donde

f1(x) = x2 − 2x− y + 0.5 y f2(x) = x2 + 4y2 − 4

Tomando como valor inicial x0 = (−0.5, 1)T se tiene que

f(x0) = (0.75, 0.25)T

J(x) =

2x− 2 −1

2x 8y

=⇒ f ′(x0) = J(x0) =

−3 −1

−1 8

por lo que debemos resolver el sistema −3 −1

−1 8

h11

h21

=

−0.75

−0.25

cuya solucion es h1 =

h11

h21

=

0.25

0

y, por tanto

x1 = x0 + h1 =

−0.25

1

Aplicando de nuevo el metodo se obtiene

f(x1) =

0.0625

0.0625

f ′(x1) = J(x1) =

−0.25 −1

−0.5 8


obteniendose el sistema −0.25 −1

−0.5 8

h12

h22

=

−0.0625

−0.0625

cuya solucion es h2 =

h12

h22

=

0.022561 . . .

−0.006 . . .

y, por tanto

x2 = x1 + h2 =

−0.227439 . . .

0.994 . . .

En definitiva, podemos observar que la resolucion de un sistema de ecuaciones

no lineales mediante el metodo de Newton se reduce, en cada iteracion, a la

resolucion de un sistema de ecuaciones lineales por lo que el tema siguiente lo

dedicaremos al estudio de dichos sistemas de ecuaciones.

Bibliografıa

[1] Burden, R.L. y Faires, J.D. Analisis Numerico (Sexta edicion). Interna-

cional Thomson Ed. 1998.

[2] Golub, G.H. y Van Loan, C.F. Matrix Computations (Third edition). Johns

Hopkins University Press

[3] Hager, W. Applied Numerical Linear Algebra. Ed. Prentice-Hall Interna-

tional. 1988.

[4] Kincaid, D. y Cheney, W. Analisis Numerico. Ed. Addison-Wesley Ibe-

roamericana. 1994.

[5] Noble, D. y Daniel, J.W. Algebra Lineal Aplicada. Ed. Prentice-Hall. 1989.

[6] Watkins, D.S. Fundamentals of MATRIX Computations. John Wiley &

Sons. 1991.

43

Documents

1.Ecuaciones no lineales - ocwus.us.esocwus.us.es/matematica-aplicada/algebra-numerica/... · Proporcionan la soluci on mediante un numero nito de operaciones ele-mentales. ax2 +