Parte 1. Resolución de una ecuacion f x) = 0 · 2009. 2. 13. · Parte 1. Resolución de una ecuacion f(x) = 0 Gustavo Montero Escuela Universitaria Politécnica Universidad de

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






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.






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







Resumen

Metodo de Newton-Raphson


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


Metodo de Regula Falsi


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






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∗,






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






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.

Documents

Parte 1. Resolución de una ecuacion f x) = 0 · 2009. 2. 13. · Parte 1. Resolución de una ecuacion f(x) = 0 Gustavo Montero Escuela Universitaria Politécnica Universidad de