Parte 1. Resoluci´on de una ecuacion f x) = 0 · 2009. 2. 13. · Parte 1. Resoluci´on de una...

Parte 1. Resolucion de una ecuacionf (x) = 0

Gustavo Montero

Escuela Universitaria PolitecnicaUniversidad de Las Palmas de Gran Canaria

Curso 2006-2007

Planteamiento del problema. Separacion de raıces

Metodos de Biparticion y de Punto Fijo

Metodos de Newton-Raphson, de la Secante y de RegulaFalsi

Analisis de la rapidez y condiciones de convergencia

Generalizacion del metodo de Newton para raıces complejas

Resumen

Planteamiento del problema. Separacion de raıces

Metodos de Biparticion y de Punto Fijo

Metodos de Newton-Raphson, de la Secante y de RegulaFalsi

Analisis de la rapidez y condiciones de convergencia

Generalizacion del metodo de Newton para raıces complejas

Resumen

Planteamiento del problema

Encontrar los ceros de la funcion f (x), es decir, las raıces de la ecuacionf (x) = 0

Ejemplo

d = z1 − z0 =h−z0nα

α =log

h−z0d

log n

zn−1 =h−z0nα (n − 1)α + z0

log (n−1)log n

=log

h−z0−Dd

logh−z0

d

Llamando

0BB@k =

logh − z0 − D

d

logh − z0

d

1CCA, se puede

comprobar facilmente que (0 ≤ k < 1). De esta forma,la ecuacion se transforma en

n = 1 + nk

Separacion de raıces

Existencia de raıces: Teorema de BolzanoSupongamos que f ∈ C [a, b] y f (a)f (b) < 0. Entonces existe un numeroc ∈ (a, b) tal que f (c) = 0.

Unicidad de raıces: Teorema de RollePara que en un intervalo existan mas de una raız, necesariamente se debecumplir el teorma de Rolle tomando como extremos dos de las raıces ySuponiendo que f ∈ C [a, b] y es derivable en (a, b).

Ecuaciones polinomicas

P(x) = a0xn + a1x

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

Teorema de acotacion

Si λ = maxi

˛ai

a0

˛, todas las raıces reales y complejas z de la ecuacion polinomica

verifican |z| ≤ λ + 1

Sucesion de SturmSean f0, f1, ..., fm, m + 1 funciones reales continuas en [a, b], con f0 ∈ C1 [a, b]. Se diceque estas funciones forman una sucesion de Sturm en [a, b] si se verifican lassiguientes condiciones:

I f0 no tiene ceros multiples en [a, b].

I fm no se anula en [a, b].

I Si para algun r ∈ [a, b] y algun j(0 < j < m), se tiene fj (r) = 0, entoncesfj−1(r)fj+1(r) < 0.

I Si para algun r ∈ [a, b] se tiene f0(r) = 0, entonces f ′0 (r)f1(r) > 0.

Ecuaciones polinomicas

Teorema de SturmSi {f0, f1, ..., fm} es una sucesion de Sturm en [a, b] y si a y b no son raıces def0(x) = 0, el numero de raıces de esta ecuacion comprendidas en (a, b) es igual a ladiferencia entre el numero de cambios de signo que hay en {f0(a), f1(a), ..., fm(a)} y en{f0(b), f1(b), ..., fm(b)}.

Obtencıon en la practica de una sucesion deSturm

I f0(x) = P(x)

I f1(x) = P′(x)

I −Resto

„f0(x)

f1(x)

«I ......................

I −Resto

„fm−2(x)

fm−1(x)

«Siendo fm+1 = 0.

Separacion de raıces

Si sabemos que todas las raıces deP(x) = 0 estan en [a, b], podemosdividir el intervalo en dos,»a,

a + b

2

–y

»a + b

2, b

–, y aplicar

el teorema de Sturm para saber elnumero de raıces que tiene cadauno. Aplicando esta tecnicasucesivamente podemos aislarcada raız en un intervalo.

Planteamiento del problema. Separacion de raıces

Metodos de Biparticion y de Punto Fijo

Metodos de Newton-Raphson, de la Secante y de RegulaFalsi

Analisis de la rapidez y condiciones de convergencia

Generalizacion del metodo de Newton para raıces complejas

Resumen

Metodo de Biparticion

Algoritmo

Supongamos que f (a)f (b) < 0a0 = a, b0 = b

c0 =a0 + b0

2

Si f (a0)f (c0) < 0 entoncesa1 = a0, b1 = c0Caso contrario a1 = c0, b1 = b0........................

cn =an + bn

2

Si f (an)f (cn) < 0 ⇒ an+1 = an ,bn+1 = cnSi f (cn) = 0 ⇒ cn es cero de fSi f (an)f (cn) > 0 ⇒ an+1 = cn ,bn+1 = bn

Representacion grafica

Convergencia

Sea f ∈ C [a, b], con f (a)f (b) < 0. En el n-esimo paso, el metodo de biparticion aproxima una raız con un error

maximo deb − a

2n.

Metodo de Punto Fijo

DefinicionSe dice que x es un punto fijo de g(x) si x = g(x).Por tanto, obtener un punto fijo es equivalente a resolver laecuacion x − g(x) = 0

Algoritmo

Elegir un x0 ∈ [a, b]xn+1 = g(xn)xn+1 → xn

Representacion grafica

Planteamiento del problema. Separacion de raıces

Metodos de Biparticion y de Punto Fijo

Metodos de Newton-Raphson, de la Secante y de RegulaFalsi

Analisis de la rapidez y condiciones de convergencia

Generalizacion del metodo de Newton para raıces complejas

Resumen

Metodo de Newton-Raphson

Representacion grafica

Algoritmo

Elegir un x0 ∈ [a, b]

xn+1 = xn −f (xn)

f ′(xn)xn+1 → xn

Convergencia (condicion debil)

˛g ′(x)

˛=|f (x)f ′′(x)||f ′(x)|2

≤ c < 1 ∀x ∈ (x∗ − δ, x∗ + δ) .

Metodo de la Secante

Deduccion del algoritmo

f ′(xn) ≈f (xn)− f (xn−1)

xn − xn−1

Algoritmo

Elegir un x0 ∈ [a, b]xn+1 =

xn −f (xn) (xn − xn−1)

f (xn)− f (xn−1)xn+1 → xn

Representacion grafica

Metodo de Regula Falsi

Representacion grafica

Algoritmo

Elegir un a0 = a, b0 = b

cn = bn −f (bn) (bn − an)

f (bn)− f (an)Si f (an)f (cn) < 0 ⇒ an+1 = an , bn+1 = cnSi f (cn) = 0 ⇒ cn es cero de fSi f (an)f (cn) > 0 ⇒ an+1 = cn , bn+1 = bn

Planteamiento del problema. Separacion de raıces

Metodos de Biparticion y de Punto Fijo

Metodos de Newton-Raphson, de la Secante y de RegulaFalsi

Analisis de la rapidez y condiciones de convergencia

Generalizacion del metodo de Newton para raıces complejas

Resumen

Velocidad de convergencia

Orden de una raızSupongamos que f (x) y sus derivadas f ′(x), ..., f (M)(x) estan definidas y soncontinuas en un intervalo centrado en el punto x∗. Se dice que f (x) = 0 tiene unaraız de orden M en x = x∗ sif (x∗) = 0, f ′(x∗) = 0, ..., f (M−1)(x∗) = 0, f (M)(x∗) 6= 0

Orden de convergencia

Supongamos que {xn}∞n=0 converge a x∗ y sea En = x∗ − xn para cada n ≥ 0. Siexisten dos constantes positivas A > 0 y R > 0 tales que

limn→∞

|x∗ − xn+1||x∗ − xn|R

= limn→∞

|En+1||En|R

= A,

entonces se dice que la sucesion converge a x∗ con orden de convergencia R y elnumero A se llama constante asistotica del error.Si R = 1 se llama convergencia linealSi R = 2 se llama convergencia cuadratica

Orden de convergencia de algunos metodos

Orden de convergencia del metodo de Newton-Raphson

I Si el grado de multiplicidad de x∗ es M = 1 entonces se obtiene convergencia cuadratica:

|En+1| ≈˛f ′′(x∗)

˛2 |f ′(x∗)|

|En|2

I Si el grado de multiplicidad de x∗ es M > 1 entonces se obtiene convergencia lineal:

|En+1| ≈M − 1

M|En|

Orden de convergencia del metodo de la Secante

I Si el grado de multiplicidad de x∗ es M = 1 entonces se obtiene una orden de convergencia igual a 1.618:

|En+1| ≈

˛˛ f ′′(x∗)

2f ′(x∗)

˛˛0.618

|En|1.618

Metodo de Newton-Raphson acelerado para raıces multiples

xn+1 = xn − Mf (xn)

f ′(xn)siendo M es grado de multiplidad de la raız x∗.De esta forma, obtenemos convergencia cuadratica a x∗,

Planteamiento del problema. Separacion de raıces

Metodos de Biparticion y de Punto Fijo

Metodos de Newton-Raphson, de la Secante y de RegulaFalsi

Analisis de la rapidez y condiciones de convergencia

Generalizacion del metodo de Newton para raıces complejas

Resumen

Planteamiento del problema

Ecuacion compleja

Sea f : C → C , con f ∈ C2 [C , C ].f (z) = 0 z = x + iy , f (z) = u(x , y) + iv(x , y)

Metodo de Newton

zn+1 = zn −f (zn)

f ′(zn)

Condicion de Cauchy-Riemann

∂f

∂x=

∂u

∂x+ i

∂v

∂x=

∂f

∂z

∂z

∂x=

∂f

∂z

∂f

∂y=

∂u

∂y+ i

∂v

∂y=

∂f

∂z

∂z

∂y= i

∂f

∂z

Por tanto,

∂f

∂z=

∂u

∂x+ i

∂v

∂x=

∂v

∂y− i

∂u

∂y

∂u

∂x=

∂v

∂y,

∂v

∂x= −

∂u

∂y

Obtencion de la parte real e imaginaria de la raız

Obtencion del algoritmo

zn+1 = xn+1 + i yn+1 = xn + i yn −u(xn, yn) + i v(xn, yn)

∂u(xn, yn)

∂x+ i

∂v(xn, yn)

∂x

Parte real

xn+1 = xn −u(xn, yn)

∂u(xn, yn)

∂x− v(xn, yn)

∂u(xn, yn)

∂y»∂u(xn, yn)

∂x

–2

+

»∂u(xn, yn)

∂y

–2

Parte compleja

yn+1 = yn −v(xn, yn)

∂u(xn, yn)

∂x+ u(xn, yn)

∂u(xn, yn)

∂y»∂u(xn, yn)

∂x

–2

+

»∂u(xn, yn)

∂y

–2

Planteamiento del problema. Separacion de raıces

Metodos de Biparticion y de Punto Fijo

Metodos de Newton-Raphson, de la Secante y de RegulaFalsi

Analisis de la rapidez y condiciones de convergencia

Generalizacion del metodo de Newton para raıces complejas

Resumen

Resumen

I Al resolver una ecuacion debemos localizar la zona (intervalo) de existencia decada raız y si es posible separar cada una de ellas en intervalos diferentes.

I En el caso de ecuaciones polinomicas, el metodo de Sturm junto con labiseccion permite separar las raıces en intervalos diferentes.

I Disponemos de una gran variedad de metodos. En cada caso debemos elegir elmas adecuado. En cuanto a rapidez, el metodo de Newton-Raphson gana al serde orden 2. Sin embargo, no siempre es posible disponer de la derivada de lafuncion de forma explıcita. Entonces habrıa que pensar en otros metodos.

I Hay que tener cuidado con las raıces multiples. La convergencia puede ser muylenta. Debemos aplicar Newton-Raphson Acelerado.

I En caso de raıces complejas, debemos aplicar la version generalizada deNewton-Raphson.