Embed Size (px)
Citation preview
Universidad Nacional de Tucumán
FACULTAD DE CIENCIAS EXACTAS
Y TECNOLOGIA
2
MAGISTER EN
METODOS
NUMERICOS Y
COMPUTACIONALES
EN INGENIERIA
MATEMATICA
NUMERICA
Tema 2Resolución de ecuaciones no lineales
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
OBJETIVOS
Familiarizarse con los métodos numéricos de búsqueda de raíces de ecuaciones no lineales
Aprender a usar Matlab para resolver problemas de ciencias e ingeniería que involucren el cálculo de raíces
Tema 2Resolución de ecuaciones no lineales
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Planteo del problema. Característica de losalgoritmos: medida de la velocidad de convergen-cia, valores iniciales y criterio de aproximación.Iteración funcional. Aproximaciones sucesivas.Métodos de iteración de dos puntos: falsaposición, secante y bisección. Método deNewton-Raphson. Promoción de la convergencia,algoritmo de Aitken. Raíces de polinomios,deflación, métodos para raíces reales ycomplejas. Aplicación empleando Matlab.
TEMAS
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PLANTEO DEL PROBLEMA
Dada una función f(x) de una única variable x, encontrar la raíz de la ecuación
f(x) = 0
significa encontrar el valor x*, tal que verifique esa igualdad
f(x*) = 0
Si f(x) es un polinomio de orden n
f(x) = an x n + an-1x n-1 +
+ … + a1x + a0,
La ecuación f(x) = 0 tiene nraíces (reales o complejas)
Raíz
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PLANTEO DEL PROBLEMA
Si f(x) es una función trascendente, elproblema de la existencia y unicidad de lasolución de la ecuación es complejo.
No tiene solución
Tiene 1 raíz
Tiene 2 raíces
Tiene 3 raíces
Tiene infinitas raíces
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PLANTEO DEL PROBLEMA
Gráficamente se ve distintas situaciones cuando se analiza a f(x) en un intervalo acotado.
No tiene solución
Tiene 1 raíz
Tiene 2 raíces
Tiene 3raíces
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PLANTEO DEL PROBLEMA
Puede haber situaciones en las que existan raíces múlti-ples. En ese caso, f(x) y la derivada f’(x) se anulan parael valor de la raíz.
Raíz Doble
Raíz Triple
Esto es importante ya que puede condicionar la solución numérica
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PLANTEO DEL PROBLEMA
La estrategia a emplear en diferente en cada caso
(A) Se necesita calcular una determinada raízreal de la función f(x)
(B) La función en cuestión es un polinomio P(x) y se necesita
evaluar todas sus raíces
Son dos las situaciones que pueden
surgir:
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
CALCULO DE UNA RAIZ - ALGORITMOS
1) Determinación de intervalo de búsqueda, esto es, los límites superior e inferior en el que la raíz puede estar. Esto en general se podrá conocer, cuando la ecuación se vincula al modelo de un sistema físico.
2) Selección y aplicación de un método numérico apropiado para determinar la raíz con la exactitud adecuada.
(A) Métodos de cómputo de una raíz real de la
función f(x).
Involucra dos pasos:
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
CALCULO DE UNA RAIZ - ALGORITMOS
(A) Métodos de cómputo de una raíz real de la función f(x).
Métodos CerradosBISECCION
REGULA FALSI
Métodos AbiertosSUSTITUCION SUCESIVA
NEWTON-RAPHSONSECANTE
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA BISECCION
Paso 1: Elegir xL y xU los extremos del intervalo entre los que se encuentra la raíz, verficando que se cumpla que f(xL)*f(xU) < 0.
Paso 2: Estimar la raíz en la mitad del intervalo (bisección).
xM = 0.5*(xL + xU)Paso 3: Determinar el nuevo intervalo de búsqueda.
if f(xM)*f(xL) < 0xU = xM
eslexL = xM
endPaso 4: Repetir la iteración hasta lograr la presición
requerida
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA BISECCION
o x
f(x)
xU
xL
xM=0.5(xL+xU)
Nuevo intervalo
de búsqueda
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA BISECCION
(1)El algoritmo genera una sucesiónSn = x0, x1, x2, ..., xn que representa las sucesivas aproximaciones a la raíz real x*.
(2)Dos aspectos asociados a la sucesión Sn son importantes: convergencia y velocidad de convergencia.
(3)Hay que establecer algún criterio para decidir cuando una aproximación de la raíz real tiene la precisión adecuada.
El análisis del algoritmo permite mostrar las siguientes características, comunes a todos los métodos:
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
ALGORITMOS DE BUSQUEDA DE RAICESCONVERGENCIA
Una sucesión de las sucesivas aproximaciones Sn = x0, x1, x2, ..., xn es convergentea la raíz real x* si se cumple que: *Snlim
nx
El error ek que se comete en la iteración k es:
La sucesión converge con velocidad r si
existe el límite y C es una constante no nula
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
ALGORITMOS DE BUSQUEDA DE RAICESCONVERGENCIA
r = 1 Convergencia lineal ( C < 1)
r > 1 Convergencia superlinear
r = 2 Convergencia cuadrática
Con convergencia lineal, se gana un dígito de precisión en cada iteración.
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
ALGORITMOS DE BUSQUEDA DE RAICESCONVERGENCIA
Las dos medidas de exactitud de la solución obtenida son:
El error en la ecuación f(x) = 0 debe ser menor que una cantidad
(tolerancia) especificada. 2Tolf(x)
El requisito de error de la variable independiente se expresa por medio
de la aproximación de dos iteraciones sucesivas en forma
relativa (tolerancia) o número de cifras significativas (m)
m
k
1kk
11kk
10x
xx
Tolxx
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
ALGORITMOS DE BUSQUEDA DE RAICESCONDICION DEL SISTEMA
f(x) bien condicionada
f(x) mal condicionada
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA BISECCION
a
b
x1
x2
a
b
¿Cuándo se detiene el proceso? 11 εxx kk 2)( εxf o
Raíz, cuyo valor se
desconoce
x*
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA BISECCION
(1)Es probablemente el método más simple y robusto, que asegura la obtención de la raíz con una precisión determinada en un número finito de iteraciones
(2)La velocidad de convergencia puede ser relativamente lenta (lineal).
Las características más relevantes del método son:
0.5log
ab
10log
iter de Nro
m
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA REGULA FALSI
o x
y
(xM,0)xL
xU
)f(x)f(x
xx)f(xxx
LU
LUUUM
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA REGULA FALSIPaso 1: Elegir xL y xU los extremos del intervalo entre
los que se encuentra la raíz, verficando que se cumpla que f(xL)*f(xU) < 0.
Paso 2: Estimar la raíz usando una aproximación lineal (la recta que pasa por los puntos extremos).
Paso 3: Determinar el nuevo intervalo de búsqueda.if f(xM)*f(xL) < 0
xU = xM
elsexL = xM
endPaso 4: Repetir hasta lograr la precisión requerida
)f(x)f(x
xx)f(xxx
LU
LUUUM
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA REGULA FALSI
ab
(a+b)/2
x*
(a, f (a))
(b, f (b))
abf(a)f(b)
f(a)ax
¿Es este método superior al de la
Bisección?
abf(a)f(b)
f(a)ax
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA REGULA FALSI
(1)Método robusto, que asegura la obtención dela raíz con una precisión determinada en unnúmero finito de iteraciones.
(2)Requiere 2 puntos iniciales.
(3)Convergencia superlineal.
(4)Convergencia lentacon funcionesaltamente convexaso cóncavas.
Las características más relevantes son:
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE SUSTITUCION SUCESIVA
Este método se conoce también como Método de las Iteraciones Funcionales o Método delPunto fijo.
0f(x)Si la ecuación a resolver es:
g(x)x Se la re-escribe como:
Se genera la ley de recurrencia
como: )g(xx k1k
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE SUSTITUCION SUCESIVA
0f(x)
Si la ecuación a resolver es:
g(x)x
Se la re-escribe como:
f(x)y
g(x)y
xy
RAÍZ
Paso 1: Elegir una aproximación inicial x0 (guess).
Paso 2: Calcular la siguiente aproximación con:
Paso 3: Repetir hasta lograr la precisión requerida
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE SUSTITUCION SUCESIVA
)g(xx k1k
X*
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE SUSTITUCION SUCESIVA
Existen infinitas posibilidadespara elegir la función g(x).
Podrían definirse las funciones g(x):
Para la función:
¿Con qué criterio se elige g(x)?
x
y y = x
x
y y = x
x
y y = x
x
y y = x
x* x*
x* x*
y=g(x)
y=g(x)
y=g(x)y=g(x)
x0
p0
x1
p1
x0
p0
x1
p1
x0
p0
x1
p1
x0
p0
x1
p1
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE SUSTITUCION SUCESIVA
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE SUSTITUCION SUCESIVA
(1)La condición para que el método sea convergente es que (Teorema 2.3, Burden y Faires)
(2)Se puede probar que tiene convergencia lineal. (Teorema 2.7, Burden y Faires)
(3)Este método resulta particularmente útil cuando se debe resolver un conjunto de ecuaciones en secuencia, en el que en la primera se propone una aproximación inicial y con la última se verifica si es correcta.
b)(a,x 1 (x)g'
• Paso 1: Elegir una aproximacion inicial x0 (guess).
• Paso 2: Calcular la siguiente aproxi-mación con:
• Paso 3: Repetir hasta lograr la precisión requerida
METODO DE NEWTON RAPHSON
)(xf'
)f(xxx
k
kk1k
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Desarrollando al expansión de Taylor hasta el término de orden cuadrático, con x0 x*，
2
0000 )(!2
)())(()()( xx
fxxxfxfxf
， pertenece a
(x,x0)Haciendo x = x* y despreciando el término cuadrático (x* x0)
2
)*)(()(*)(0 000 xxxfxfxf )(
)(*
0
00
xf
xfxx
LINEAL
x
y
x*x0
)(xf
)f(xxx
i
ii1i
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE NEWTON RAPHSON
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE NEWTON RAPHSON
(1)Requiere un solo valor inicial y no espreciso encontrar un intervalo en el que seencuentre la raíz.
(2)Convergencia cuadrática. Esto indica que sise dan las condiciones, la convergencia esrápida.
(3)Tiene problemas de convergencia, porejemplo si f’’(x) = 0 en las proximidades dela raíz x* o cuando hay raíces múltiples.
(4)El algoritmo permite la estimación de raícescomplejas si el valor inicial es un complejo.
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE
NEWTON RAPHSON
Tres casos en los que el Método falla
para encontrar la
raíz
f’’(x) = 0 en adyacencias de x*
Con valores iníciales en la
proximidades de f’(x) = 0
Cuando la función oscila en las proximidades x*
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE NEWTON RAPHSONAciertos y fallos
x*
x0x0
x0
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE NEWTON RAPHSONRegla de Fourier
SI en el intervalo [a,b] existe una raíz x* de laecuación f(x) = 0 y que f’(x) y f’’(x) no se anulanen ningún punto del intervalo [a,b] (ambas deri-vadas tienen signo constante en dicho intervalo).
ENTONCES el método de Newton-Raphson esconvergente a la única raíz x* siempre que setome como valor inicial a:
Esta regla es una condición suficiente paragarantizar la convergencia, pero no es necesaria,
x0 = a si f(a) f’’(a) > 0
x0 = b si f(b) f’’(b) > 0
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE NEWTON RAPHSONRegla de Fourier
La Regla de Fourier indica cómo elegir el punto inicial x0
• Paso 1: Elegir una aproximación inicial x0 (guess).
• Paso 2: Calcular la siguiente aproxi-mación con:
• Paso 3: Repetir hasta lograr la precisión requerida
METODO DE LA SECANTE
)f(x)f(x
)x)(xf(xxx
k1k
k1kkk1k
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Surge como variación del método de Newton Raphson.La pendiente de la recta (derivada) se estima por diferencias finitas entre dos puntos.
x0x1
TANGENTE
SECANTE
Pendiente TANGENTE Pendiente SECANTE
1
1 )()()(
kk
kkk
xx
xfxfxf
)()(
))((
1
11
kk
kkkkk
xfxf
xxxfxx
Método de Newton
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA SECANTE
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
METODO DE LA SECANTE
(1)Requiere dos valores iniciales. No es preciso acotar un intervalo en el que se encuentre la raíz x*.
(2)Convergencia superlineal. Se puede probar que el orden de convergencia es 1.62.
(3)Tiene problemas de convergencia similaresa los del método de Newton Raphson.
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
1ª Iter.
METODOS LA FALSA POSICION Y DE LA SECANTE - COMPARACION
2ª Iter.
f(x) = ln(x).
Regula Falsi Secante
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
COMPARACION ENTRE METODOSMétodo Ventajas Desventajas
Bisection
Fácil de implementar. RobustoGarantiza una reducción del eror de estimación del 50 % en cada iteración
Convergencia linear
Sustitución Suceciva
Puede ser muy eficiente dependiendo de la fórmula de recursión empleada.Requiere un solo punto para iniciar la iteración.
Puede diverger.La ecuación de recursión que garantiza convergencia puede no ser obvia.La performance depende de la ecuación de recursión.
Newton Raphson
Convergencia local cuadrática.Requiere un solo punto para iniciar la iteración.
Puede diverger cuando f’(x) es muy pequeña o muy grande.Requiere el cómputo de f’(x).
Secante
Convergencia casi cuadrática (1.628).Fácil de implementar.
Puede diverger cuando el gradiente de la función es muy pequeño o muy grande.Sensible a la estimación inicial de la pendiente.
Regula falsi
Fácil de implementar.Robustez, con garantía de convergencia.
La velocidad de convergencia puede ser muy baja, especial-mente para funciones altamente cóncavas o convexas.
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
COMPARACION ENTRE
METODOS
Velocidad de convergencia.
Caso de la ecuación:
0xx)exp(f(x)
0.567...x*
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
RAICES MULTIPLES
37x5xxf(x)
1)1)(x3)(x(xf(x)
23
310x12x6xxf(x)
1)1)(x1)(x3)(x(xf(x)
234
PROBLEMASLas funciones no cambian de signo en la raíz cuando tienen multiplicidad par. f’(x) se aproxima a cero con muy baja velocidad de convergencia(la pendiente es nula en raíces múltiples).
Raíz Triple
Raíz Doble
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
RAICES MULTIPLESExtensión del Método de Newton-Raphson
El método original de Newton-Raphson:
)(xf'
)f(xxx
k
kk1k
El Método de Newton para raíces
mútiples resulta: )(xu'
)u(xxx
k
kk1k
Introduciendo una nueva función u(x) que se anula cuando f(x)
se hace cero:(x)f'
f(x)u(x)
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA La fórmula
de recurrencia resulta:
RAICES MULTIPLES
Recupera la convergencia original del método de Newton (cuadrática)
La extensión del método de la secante para raíces múltiples resulta en forma análoga:
)u(x)u(x
)x)(xu(xxx
k1k
k1kkk1k
)(x')f'f(x)(xf'
)(x)f'f(xxx
kk
2
k
kkk1k
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
RAICES MULTIPLESOtra Extensión del Método de Newton-
Raphson
El método de Newton-Raphson: )(xf'
)f(xxx
k
kk1k
Ralston y Rabinowitz proponen que seintroduzca un coeficiente m que representa lamultiplicidad de la raíz. Se puede lograrconvergencia cuadrática.
El Método para raíces mútiples resulta: )(xf'
)f(xmxx
k
kk1k
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PROMOCION DE LA CONVERGENCIA
Paso 1: Elegir una aproximacion inicial x0 (guess).
Paso 2: Calcular dos aproximaciones:
Paso 3: Evaluar la raíz corregida con la expresión:
El método de sustitución sucesiva puede no converger. Yen caso se convergencia, en alguno casos puede hacerlo abaja velocidad. Para mejorar la convergencia existenmétodos. El más conocido es el Método de Aitken:
210
2
010
x2xx
)x(xxx
ˆ
)g(xx ; )g(xx 12 01
Seguir empleando:k1k2k
2
2k1k2k1k
x2xx
)x(xxx
x
y
y = xy = g(x)
x* x0
P(x0, x1)
x1 x2
x̂
P(x1, x2)
210
2
010
x2xx
)x(xxx
ˆ
PROMOCION DE LA CONVERGENCIA
Interpretación gráfica del
Método de Aitken
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PROMOCION DE LA CONVERGENCIA
Paso 1: Elegir una aproximacion inicial x0 (guess).
Paso 2: Calcular dos aproximaciones:
Paso 3: Evaluar la raíz con la expresión:
Una variante menor en la forma de aplicar el algoritmode Delta de Aitken es el Método de Steffensen queproduce buenos resultados:
210
2
010
x2xx
)x(xxx
ˆ
)g(xx ; )g(xx 12 01
Paso 4: Haga xx0 ˆ
y vuelva al Paso 1
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
PROMOCION DE LA CONVERGENCIA
La iteración funcional calcula de xk con:
Otra forma para expresar el algoritmo de Aitken seconoce como Método de Wegstein
)g(xx 1kk
El gradiente de g(x) se puede estimar en xk con:
Y esto mejora la estima-ción de la función para la próxima iteración:
Resultando:
s
xx
xgxg
dx
xdg
1kk
1kk
xk
111 kkkkk xxxsxgxg
1s
sqqxxq)g(1x kk1k
;
RAICES DE POLINOMIOS
Los polinomios son funciones de relevancia enmodelos matemáticos en ciencias e ingeniería.El teorema fundamental del álgebra y suscorolarios siguen las siguientes reglas:
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Un polinomio de orden n tiene n raíces que pueden ser reales o complejas, simples o múltiples.
Si los coeficientes del polinomio son reales, y el orden es impar, al menos hay una raíz real.
Si los coeficientes del polinomio son reales, hay una raíz compleja, el conjugado también es raíz.
RAICES DE POLINOMIOS
Para el polinomio:
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Si x* es una raíz encontrada por alguno de los procedimientos de búsqueda de raíces, entonces:
Las raíces de Q(x) son también raíces de P(x). Este procedimiento se denomina deflación polinomial.
0axaxaxaxP 01
1n
1n
n
n
0bxbxbxb*xx
Q(x) *xxxP
01
2n
2n
1n
1n
0x*bx*xbb
x*xbbx*xbbxbxP
010
2n
2n3n
1n
1n2n
n
1n
RAICES DE POLINOMIOS
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Así se obtienen los coeficientes del polinomiodeflacionado Q(x) al que se le puede aplicarde nuevo un algorimo de búsqueda de raíces.Este procedimiento se conoce como DivisiónSimétrica. (Regla de Ruffini)
Comparando coeficientes:
*xbab
*xbab
*xbab
*xbab
ab
110
221
2n2n3n
1n1n2n
n1n
RAICES DE POLINOMIOS
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
La División Simétrica empleada en conjunción con unmétodo de búsqueda de raíz (por ej. Método deNewton, permite encontrar recursivamente las raícesde P(x).
)Q(x)(xP'
(x))Q'x(xQ(x)(x)P'
kk
k
Derivando P(x)
RR))Q(xx(x)P(x
R)Q(x)x(xP(x)
kkkk
k
Teorema del resto
La derivada P’(xk), para aplicar el Método de Newtonse puede estimar con Q(xk).
RAICES DE POLINOMIOS
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Notar: Se requiere una aproximación inicial de la raízen cada etapa. Una vez encontrada la primera, sesuele emplear ésta como aproximación de la siguiente.
El algoritmo (Newton-Hörner) parte de un valorinicial de raíz x0:
1.Se calcula P(xk)
2.Se calculan los coeficientes de Q(x) usandoDivisión Simétrica.
3.Se estima P’(xk) = Q(xk)
4.Se aplica la fórmula de Newton Raphson
xk+1 = xk- P(xk)/Q(xk)
5.Se controla convergencia y se vuelve a 1 deser necesario
RAICES DE POLINOMIOSM
AG
IS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Para raíces complejas y polinomio de coeficientesreales, se debe trabajar con factores cuadráticos:
qpxxxx)xx(xx)x-)(xx-(x
jbax , jbax
2
2121
2
21
21
Entonces, el polinomio P(x) original de orden n sedeflaciona en dos órdenes al dividirlo por el factorcuadrático.
Como antes, al multiplicar e igualar coeficientes seobtiene:
Bp)A(x
)bxb...xbxq)(bpx(x
Residuoq)Q(x)px(xP(x)
01
3n
3n
2n
2n
2
2
RAICES DE POLINOMIOS
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
210
321
2n3n2n3n
2n1n3n
n2n
qbpbaB
qbpbaA
qbpbab
pbab
ab
Para que p y q correspondan a lasraíces de P(x), el residuo debe sernulo, es decir, se debe cumplir:
0q)B(p,
0q)A(p,
El Método de Bairstow, es uno de los algoritmos que emplea este esque-ma de deflación, calcu-lando las raíces de a pares.
El algoritmo de Bairstow resuelve este sistemano-lineal empleando el Método de Newton parados incógnitas.
FUNCIONES DE MATLAB
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
fzeroEncuentra la raíz de una función de una variable
Sintaxisx = fzero(fun,x0) x = fzero(fun,x0,options) x = fzero(fun,x0,options,P1,P2,...)
Algoritmofzero es un comando en un archivo M. El algoritmo se debe a T. Dekker, que usa una combinación de los métodos de la bisección, de la secante y de la interpolación inversa cuadrática. (Forsythe, G. E., M. A. Malcolm, and C. B. Moler, Computer Methods for Mathematical Computations, Prentice-Hall, 1976).
LimitacionesEncuentra raíces de funciones continuas que cambian de signo, cortando el eje de las abscisas.
FUNCIONES DE MATLAB
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
rootsEncuentra todas las raíces de un polinomio con coeficientes reales.
Sintaxisr = roots(c)Con c el vector de los coeficientes del polinomio ordenados de mayor grado al término independiente.
AlgoritmoSe computan las raíces a partir de los autovalores de una matriz que tiene dicho polinomio característico.
Tema 2Resolución de ecuaciones no lineales
MA
GIS
TE
R E
N M
ET
OD
OS
N
UM
ER
IC
OS
Y
CO
MP
UTA
CIO
NA
LE
S E
N IN
GE
NIE
RIA
Planteo del problema. Característica de losalgoritmos: medida de la velocidad de convergen-cia, valores iniciales y criterio de aproximación.Iteración funcional. Aproximaciones sucesivas.Métodos de iteración de dos puntos: falsaposición, secante y bisección. Método deNewton-Raphson. Promoción de la convergencia,algoritmo de Aitken. Raíces de polinomios,deflación, métodos para raíces reales ycomplejas. Aplicación empleando Matlab
TEMAS
Universidad Nacional de Tucumán
FACULTAD DE CIENCIAS EXACTAS
Y TECNOLOGIA
2
MAGISTER EN
METODOS
NUMERICOS Y
COMPUTACIONALES
EN INGENIERIA
MATEMATICA
NUMERICA
