ejercicio 1ma1.eii.us.es/material/alg_num_ii_ex_r.pdfejercicio 1 se quiere encontrar una funci on de...
TRANSCRIPT
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
30 de junio de 2006
Ejercicio 1
Se quiere encontrar una funcion de la forma f(x) = ax3 + bx + c que pase por los puntos(1, 4), (−2,−23) y (2, 21).
a) Plantear un sistema de ecuaciones para calcular los coeficientes de f y resolverlo usandola descomposicion LU de la matriz del sistema.
b) Usar una sucesion de Sturm para saber cuantas raıces reales tiene la ecuacion f(x) = 0.
c) Separar dichas raıces por intervalos adecuados para que se den las hipotesis de lascondiciones de Fourier.
d) ¿Cuantas iteraciones son necesarias para obtener las raıces reales con 6 cifras decimalesexactas usando para su calculo el metodo de Newton?
e) Aplicar dicho metodo para calcularlas con una precision de 12 cifras decimales exactasasegurando en cada paso del metodo el numero de cifras que se van obteniendo.
Solucion:
a)
(1, 4) =⇒ a+ b+ c = 4
(−2,−23) =⇒ −8a− 2b+ c = −23
(2, 21) =⇒ 8a+ 2b+ c = 21
=⇒
1 1 1
−8 −2 1
8 2 1
a
b
c
=
4
−23
21
La factorizacion LU de la matriz del sistema viene dada por 1 1 1
−8 −2 1
8 2 1
=
1 0 0
−8 1 0
8 −1 1
1 1 1
0 6 9
0 0 2
1 0 0
−8 1 0
8 −1 1
α
β
γ
=
4
−23
21
=⇒
α
β
γ
=
4
9
−2
1 1 1
0 6 9
0 0 2
a
b
c
=
4
9
−2
=⇒
a
b
c
=
2
3
−1
resultando que
f(x) = 2x3 + 3x− 1
b) Una sucesion de Sturm viene dada por
f(x) = 2x3 + 3x− 1 =⇒ f0(x) = 2x3 + 3x− 1
f ′(x) = 6x2 + 3 =⇒ f1(x) = 2x2 + 1
f0(x) = f1(x) · x+ (2x− 1) =⇒ f2(x) = −2x+ 1
f1(x) = f2(x) · (−x− 1/2) + 3/2 =⇒ f3(x) = −1
−∞ 0 1 ∞2x3 + 3x− 1 − − + +
2x2 + 1 + + + +
−2x+ 1 + + − −−1 − − − −
cambios de signos 2 2 1 1
por lo que solo existe una raız real que se encuentra en el intervalo [0, 1].
c)
f(0) = −1 < 0 y f(1) = 4 > 0
f ′(x) = 6x2 + 1 > 0 ∀x ∈ [0, 1]
f ′′(x) = 12x = 0 para x = 0 ∈ [0, 1]
por lo que no se verifican las condiciones de Fourier en el intervalo [0, 1].
f(0.3) = −0.046 < 0 y f(0.4) = 0.328 > 0
f ′(x) = 6x2 + 1 > 0 ∀x ∈ [0.3, 0.4]
f ′′(x) = 12x > 0 ∀x ∈ [0.3, 0.4]
por lo que ahora si se verifican las condiciones de Fourier debiendose comenzar a iterarcon x0 = 0.4.
d) El error de x0 = 0.4 viene dado por ε0 < 0.1 y el error a priori viene dado por
εn ≤1
k|kε0|2
n
con k =
maxx∈[0.3,0.4]
|f ′′(x)|
2 mınx∈[0.3,0.4]
|f ′(x)|=
f ′′(0.4)
2 · f ′(0.3)= 0.67796610169492
se tiene que
εn ≤1
0.67796610169492(0.067796610169492)2n
< 10−6
por lo que(0.067796610169492)2n
< 0.67796610169492 · 10−6
2n log 0.067796610169492 < log 0.67796610169492− 6 log 10 =⇒ 2n > 5.278
es decirn > log2 5.278 = 2.399
y por tanto, partiendo de x0 = 0.4, se pueden garantizar 6 cifras decimales exactas apartir de la tercera iteracion.
e) Teniendo en cuenta la formula de Newton-Raphson
xn+1 = xn −f(xn)
f ′(xn)
y que el error a posteriori viene dado por
εn ≤|f(xn)|
mınx∈[0.3,0.4]
|f ′(x)|=|f(xn)|
3.54
partiendo de x0 = 0.4 obtenemos:
x1 = 0.31717171717172 con ε1 ≤ 0.00433016037581
x2 = 0.31291796498661 con ε2 ≤ 9.683691476124762 · 10−6
x3 = 0.31290840952702 con ε3 ≤ 4.842592115127995 · 10−11
x4 = 0.31290840947923 con ε4 ≤ 3.136223233404397 · 10−17
por lo quex = 0.312908409479
con sus doce cifras decimales exactas.
Ejercicio 2
Se sabe que un movil en R3 sigue una velocidad instantanea dada por una expresion de laforma V (x, y, z) = ax+ by+ cz en donde a, b, c ∈ R. Con un velocımetro se han tomado losdatos siguientes:
V (1, 2,−53) = −3 V (1, 2,−4) = 2 V (2,−1, 2) = −2
V (1, 0,−2) = −1 V (3, 2,−1) = −2
a) Demostrar que el velocımetro esta desajustado. Es decir, que los datos obtenidos sonincompatibles.
b) Una vez planteado el sistema incompatible y usando las ecuaciones normales de dichosistema, usar el metodo de Cholesky para calcular el grado de desajuste del velocımetro.Es decir, el error al suponer la pseudosolucion como los verdaderos valores de a, b y c.
c) Calcular el error usando transformaciones de Householder en el sistema incompatible.
d) Si λ es un autovalor de la matriz ATA asociado al autovector x, demostrar que λtambien es autovalor de la matriz AAT asociado al autovector Ax.
Solucion:
a) Teniendo en cuenta los datos de las mediciones se tiene que
a+ 2b− 5
3c = −3
a+ 2b− 4c = 2
2a− b+ 2c = −2
a − 2c = −1
3a+ 2b− c = −2
=⇒
1 2 −5/3
1 2 −4
2 −1 2
1 0 −2
3 2 −1
a
b
c
=
−3
2
−2
−1
−2
⇐⇒ Ax = b
y dado que
rg
1 2 −5/3
1 2 −4
2 −1 2
1 0 −2
3 2 −1
= 3 y rg
1 2 −5/3 −3
1 2 −4 2
2 −1 2 −2
1 0 −2 −1
3 2 −1 −2
= 4
el sistema resulta incompatible.
b) Las ecuaciones normales del sistema vienen dadas por
ATAx = ATb ⇐⇒
16 8 −20/3
8 13 −46/3
−20/3 −46/3 250/9
x =
−12
−4
−3
y realizando la factorizacion de Cholesky obtenemos: 4 0 0
2 3 0
−5/3 −4 3
4 2 −5/3
0 3 −4
0 0 3
x =
−12
−4
−3
4 2 −5/3
0 3 −4
0 0 3
x = y =⇒
4 0 0
2 3 0
−5/3 −4 3
y =
−12
−4
−3
=⇒ y =
−32/3
−16/9
por lo que 4 2 −5/3
0 3 −4
0 0 3
x =
−32/3
−16/9
=⇒ x =
−77/108
−46/81
−16/27
y el error de la pseudosolucion viene dado por
‖Ax− b‖ =
∥∥∥∥∥∥∥∥∥∥∥∥
77/36
−479/324
−7/162
53/36
−221/324
∥∥∥∥∥∥∥∥∥∥∥∥= 3.0651
c) La primera transformacion debe transformar el vector
x1 =
1
1
2
1
3
en y1 =
4
0
0
0
0
y viene definida por
v1 =x1 − y1
‖x1 − y1‖=
1
2√
6
−3
1
2
1
3
H1 = I5 − 2v1vT1 =
1
12
3 3 6 3 9
3 11 −2 −1 −3
6 −2 8 −2 −6
3 −1 −2 11 −3
9 −3 −6 −3 3
H1Ax = H1b ⇐⇒
4 2 −5/3
0 2 −4
0 −1 2
0 0 −2
0 2 −1
x =
−3
2
−2
−1
−2
La segunda transformacion debe transformar el vector
x2 =
2
2
−1
0
2
en y2 =
2
3
0
0
0
y viene definida por
v2 =x2 − y2
‖x2 − y2‖=
1√6
0
−1
−1
0
2
por lo que
H2 = I5 − 2v2vT2 =
1
3
3 0 0 0 0
0 2 −1 0 2
0 −1 2 0 2
0 0 0 3 0
0 2 2 0 −1
resultando
H2H1Ax = H2H1b ⇐⇒
4 2 −5/3
0 3 −4
0 0 2
0 0 −2
0 0 −1
x =
−32/3
−10/3
−12/3
Una tercera transformacion debe llevar el vector
x3 =
−5/3
−4
2
−2
−1
a y3 =
−5/3
−4
3
0
0
que viene definida por
v3 =x3 − y3
‖x3 − y3‖=
1√6
0
0
−1
−2
−1
obteniendose
H3 = I5 − 2v3vT3 =
1
3
3 0 0 0 0
0 3 0 0 0
0 0 2 −2 −1
0 0 −2 −1 −2
0 0 −1 −2 2
y, por tanto,
H3H2H1Ax = H3H2H1b ⇐⇒
4 2 −5/3
0 3 −4
0 0 3
0 0 0
0 0 0
x =
−32/3
−16/919/920/9
por lo que el error viene dado por∥∥∥∥∥
(19/920/9
)∥∥∥∥∥ = 3.0651
que es el mismo que el obtenido en el apartado anterior.
d) Si λ es un autovalor de ATA asociado al autovector x sabemos que
ATAx = λx
Multiplicando por A obtenemos
AATAx = A(λx) = λAx ⇐⇒ (AAT )(Ax) = λ(Ax)
lo que nos dice que λ es un autovalor de la matriz AAT asociado al autovector Ax.
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
6 de septiembre de 2006
Ejercicio 1
Queremos aproximar las soluciones de la ecuacion (5− x)ex = 5.
a) Probar, graficamente, que existen dos soluciones, una es x = 0 y la otra x = α seencuentra en el intervalo [1, 5]. Aproximarla realizando dos pasos del metodo de laRegula-Falsi (metodo de la cuerda).
b) ¿Es posible aproximar α aplicando un metodo de iteracion funcional (x = ϕ(x)) sobre
la funcion ϕ1(x) = ln
(5 + xex
5
)partiendo de cualquier punto del intervalo I = [1, 5]?
Justifica tu respuesta.
c) ¿Es posible aproximarla aplicando el metodo sobre la funcion ϕ2(x) = 5− 5
expartiendo
de cualquier punto del intervalo I = [1, 5]? Justifica tu respuesta.
d) ¿Y sobre ϕ2(x) en I = [2, 5]? Justifica tu respuesta.
Solucion:
a) Podemos escribir la ecuacion de la forma 1 − x
5= e−x para ver donde se cortan las
graficas de las funciones
y = 1− x
5y Y = e−x
Por lo que aparte de la solucion x = 0, solo existe otra solucion que se encuentra en elintervalo [1, 5].
Se trata de buscar los ceros de la funcion f(x) = (5− x)ex − 5 en el intervalo [1, 5].
Aplicando el metodo de la Regula-Falsi que establece que, partiendo del intervalo [a, b]con sig f(a) 6= sigf(b) la raız se encuentra en el subintervalo [a, c] con
c = b− f(b) · b− af(b)− f(a)
si sig f(a) 6= sigf(c) o [c, b] si sig f(c) 6= sigf(b) obtenemos que
x1 = 5− f(5)5− 1
f(5)− f(1)= 3.16060279414279
encontrandose la raız en el intervalo [3.16060279414279, 5] y
x2 = 5− f(5)5− 3.16060279414279
f(5)− f(3.16060279414279)= 4.78799912600669
b) Dado que
ϕ′1(x) =(x+ 1)ex
5 + xex=ex + xex
5 + xex
y que siempre que x > ln 5 = 1.609 es ex > 5 se tendrıa que ϕ′1(x) > 1 y, por tanto lafuncion de iteracion no serıa contractiva, por lo que el metodo no serıa convergente.
c) En este caso tenemos que
ϕ′2(x) =5
ex
por lo que si x < ln 5 = 1.609 es ex < 5 y, por tanto, ϕ′2(x) > 1.
Es decir, el metodo tampoco serıa convergente.
d) En el intervalo [2, 5] y dado que si x > 2 es ex > 5 resulta que ϕ′2(x) < 1 por lo queϕ(x) es contractiva y el metodo es convergente.
Ejercicio 2
Se considera la matriz A =
1 −1 1
−1 2 1
1 2 2
a) Calcular su polinomio caracterıstico por el metodo interpolatorio.
b) Separar sus raıces mediante una sucesion de Sturm.
c) ¿Convergera el metodo de la potencia simple comenzando por el vector x0 = (1, 1, 1)T?Justifica la respuesta.
d) Realiza dos iteraciones del metodo de la potencia simple comenzando por el vectorx0 = (1, 5, 8)T y aproxima el autovalor dominante mediante el cociente de Rayleigh.
e) Realiza dos iteraciones del metodo de la potencia inversa comenzando por el vectorx0 = (6, 5,−6)T . ¿De quien es una aproximacion x2?
Solucion:
a) P (λ) = λ3 + a1λ2 + a2λ+ a3 = det(λI − A).
λ = 0 =⇒ a3 = det(−A) = 5
λ = 1 =⇒ 1 + a1 + a2 + a3 = det(I − A) = 5
λ = −1 =⇒ −1 + a1 − a2 + a3 = det(−I − A) = −5
=⇒
a1 = −5
a2 = 4
a3 = 5
P (λ) = λ3 − 5λ2 + 4λ+ 5
b)
f0(λ) = P (λ) =⇒ f0(λ) = λ3 − 5λ2 + 4λ+ 5
f1(λ) = P ′(λ) =⇒ f1(λ) = 3λ2 − 10λ+ 4
9f0(λ) = f1(λ)(3λ− 5) + 13(−2λ+ 5) =⇒ f2(λ) = 2λ− 5
4f1(λ) = f2(λ)(6λ− 5) + (−9) =⇒ f3(λ) = 1
−∞ −1 0 1 2 3 4 +∞f0(λ) = λ3 − 5λ2 + 4λ+ 5 − − + + + − + +
f1(λ) = 3λ2 − 10λ+ 4 + + + − − + + +
f2(λ) = 2λ− 5 − − − − − + + +
f3(λ) = 1 + + + + + + + +
cambios de signo 3 3 2 2 2 1 0 0
Por lo que tiene tres raıces reales que se encuentran en los intervalos
[−1, 0] [2, 3] y [3, 4]
c) Al tener un autovalor dominante (el que se encuentra en el intervalo [3,4]), el metodode la potencia simple resulta convergente.
d)
x0 =
1
5
8
x1 = Ax0 =
4
17
27
x2 = Ax1 =
14
57
92
Una aproximacion del autovalor dominante viene dada por
xT2 Ax2
xT2 x2
= 3.38685028129986
e)
A−1 =1
5
−2 −4 3
−3 −1 2
4 3 −1
x0 =
6
5
−6
x1 = A−1x0 =
−10
−7
9
x2 = A−1x1 =
15
11
−14
El vector obtenido x2 es una aproximacion del autovector de la matriz A asociadoal autovalor de menor valor absoluto, es decir, del autovalor que se encuentra en elintervalo [−1, 0].
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
26 de noviembre de 2006
Ejercicio 1
La grafica de la figura adjunta corresponde a una funcion y = f(x), para la que las raıcespositivas de la ecuacion f(x) = 0 son los puntos α y β del intervalo considerado.
a) Indicar razonadamente un intervalo I1 en el que el metodo de Newton aplicado a laecuacion f(x) = 0 converja a α, partiendo de cualquier α0 de I1. Determinar otrointervalo I2 en el que el metodo converja a β siempre que se tome un punto inicialβ0 ∈ I2.
b) En la notacion del apartado anterior, si se parte de α0 ∈ I1 y de β0 ∈ I2, de modo que|α − α0| = |β − β0|, razonar si alguna de las sucesiones (αn) o (βn), que se obtienencon el metodo de Newton, converge mas rapidamente que la otra.
¿Podrıa indicar una estrategia para conseguir que el orden de convergencia sea al menoscuadratico en cada caso?
c) Supongase construido un proceso iterativo xn+1 = F (xn), para encontrar una solucionde f(x) = 0, y que la funcion de iteracion ha simplificado a F (x) = 2
3x+ 1.
Representar geometricamente el proceso iterativo mediante la red asociada a la sucesion(xn), partiendo de x0 = −3. ¿Se puede asegurar analıticamente la convergencia delmetodo iterativo?
Determinar el valor de α o β al que converge (xn). ¿Podrıa haber sido obtenida lafuncion de iteracion a partir de la expresion F (x) = x − f(x)/f ′(x)? Justificar larespuesta.
Solucion:
a) Si tomamos el intervalo I1 indicado en la siguiente figura, dado que la funcion cambiade signo en los extremos y no existen puntos crıticos, el metodo de Newton convergeratomando como valor inicial cualquier punto del intervalo.
Por la misma razon, el metodo convergera a β siempre que tomemos como valor inicialun punto del intervalo I2. Hay que tener en cuenta, en este caso, que al ser multiplela raız, la convergencia no sera de segundo orden como en el caso de la raız simple α.
b) Como ya se ha indicado anteriormente, al ser multiple la raız β la convergencia no esde segundo orden y, por tanto, mas lenta que en el caso de la raız simple α donde elmetodo de Newton si es de segundo orden.
Una estrategia a seguir en el caso de la raız multiple es usar el metodo de Newton pararaıces multiples
xn+1 = xn − k ·f(xn)
f ′(xn)
donde k representa la multiplicidad de la raız.
c) La grafica adjunta nos da la respuesta: el metodo resulta convergente. Sin disponer demas datos no podemos predecir a cual de las dos raıces convergera la sucesion (xn).
Si converge a α la funcion F (x) no puede ser la resultante de aplicar el metodo deNewton ya que dicho metodo, para la raız α es de segundo orden lo que nos dice queF ′(α) = 0 y en este caso es F ′(α) = 2
36= 0.
Si converge a β sı podrıa darse el caso de que F (x) fuese la funcion de iteracion delmetodo de Newton.
Ejercicio 2
d) Si f(x) es un polinomio de tercer grado cuyas raıces son las autovalores de la matrizcompanera 0 ”companion”, definida por
A =
7 −15 9
1 0 0
0 1 0
Utilizar el cociente de Rayleigh para determinar la aproximacion que se obtiene de laraız simple con cuatro pasos del metodo de la potencia inversa, partiendo de un vectorω0 para el que resultan (A−1)3ω0 = (1, 5
3, 2)T y (A−1)4ω0 = (5
3, 2, 58
27)T .
¿Hubiera sido convergente el metodo de la potencia?
e) Aplicando el algoritmo QR a la matriz del apartado anterior se obtiene la sucesion(T0 = A, T1, T2, T3, . . .), que redondeando a dos dıgitos significativos viene dada por
A =
4′9 −10 15
0′33 1′6 −2′0
0 0′23 0′49
,
4′2 −9′1 16
0′16 2′0 −3′2
0 0′079 0′79
,
3′9 −8′6 16
0′087 2′2 −3′8
0 0′031 0′91
, . . .
¿Se aprecia convergencia o divergencia del metodo?
Si se tiene la factorizacion T3 = QR, siendo, con dos cifras significativas
Q =
0′99 −0′023 0′00029
0′023 0′99 −0′013
0 0′013 0′99
, R =
3′9 −8′6 16
0 2′4 −4′1
0 0 0′96
Calcular el siguiente termino T4 de la sucesion que produce el algoritmo.
f) Si se detiene la sucesion que resulta del algoritmo QR en el termino T4, hallar lasaproximaciones de α y β que se obtendrıan.
Si se considera que el error en las aproximaciones anteriores es menor que la unidad,razonar si serıa una buena estrategia resolver un sistema de ecuaciones con el metodode Gauss-Seidel, si la matriz del proceso iterativo hubiera resultado ser A.
Solucion:
d) El metodo de la potencia inversa, partiendo del vector ω0 obtiene la sucesion
ω1 = A−1ω0 ω2 = (A−1)2ω0
ω3 = (A−1)3ω0 = (1, 53, 2)T ω4 = (A−1)4ω0 = (5
3, 2, 58
27)T
y una aproximacion del autovalor de menor modulo de la matriz A viene dado, medianteel cociente de Rayleigh, por
λ1 =ωT4 Aω4
ωT4 ω4
=(A−1)4ω0(A
−1)3ω0
(A−1)4ωT0 (A−1)4ω0
=
(5/3 2 58/27
) 15/3
2
(
5/3 2 58/27
) 5/3
258/27
≈ 0.81601444912703
Teniendo en cuenta que la raız de mayor modulo del polinomio es doble, el metodo de lapotencia simple no hubiese sido convergente, ya que no existe un autovalor dominante.
e) Se aprecia una convergencia del metodo ya que los elementos situados por debajo dela diagonal principal van tendiendo a cero.
El siguiente termino de la sucesion viene dado por
T4 = RQ =
3′9 −8′6 16
0 2′4 −4′1
0 0 0′96
0′99 −0′023 0′00029
0′023 0′99 −0′013
0 0′013 0′99
=⇒
T4 =
3′7 −8′4 16
0′055 2′3 −4′1
0 0.012 0′95
f) Si nos detenemos en T4 obtenemos que α ≈ 0′95 pero no tenemos aun una buena
aproximacion de la raız doble que debe oscilar entre 2′3 y 3′7
Si la matriz A fuese la matriz del metodo de Gauss-Seidel, dado que su radio espectrales mayor que 1, el proceso no resultarıa convergente.
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
25 de junio de 2007
Ejercicio 1
Dado el polinomio P (x) = x3 + 2x2 + x+ 6, se pide:
a) Probar, mediante una sucesion de Sturm, que solo tiene una raız real y que esta seencuentra en el intervalo [−2′6,−2′5].
b) ¿Como afecta a la convergencia del metodo de Newton la multiplicidad de una raız?
c) Comenzando por x0 = −2′5, calcular la raız real de P (x) con 1 cifra decimal exacta,por el metodo de Newton, indicando el orden de convergencia.
d) Si P (x) es el polinomio caracterıstico de una matriz A ∈ R3×3, ¿podrıa determinarsesu raız real aplicando el metodo de la potencia simple a dicha matriz? Justifıquese larespuesta.
Indicacion: El modulo del termino independiente de un polinomio es el producto delos modulos de sus raıces.
e) Trabajando con una cifra decimal, al aplicar el algoritmo QR a la matriz A el procesose detiene en α −5′2 1′7
0 0′8 β
0 2′2 −0′3
con β = ±1′2
Determinar el valor de α y el signo del elemento β.
Solucion:
a)
f0(x) = P (x) = x3 + 2x2 + x+ 6
f1(x) = P ′(x) = 3x2 + 4x+ 1
9f0(x) = (3x+ 2)f1(x) + 2(−x+ 26) =⇒ f2(x) = x− 26
f1(x) = (3x+ 82)f2(x) + 2133 =⇒ f3(x) = −1
−∞ −2′6 −2′5 +∞x3 + 2x2 + x+ 6 − − + +
3x2 + 4x+ 1 + + + +
x− 26 − − − −−1 − − − −
cambios de signo 2 2 1 1
por lo que solo existe una raız real que se encuentra en el intervalo [−2′6,−2′5].
b) Si la raız es simple el metodo de Newton es de segundo orden, mientras que si la raızes multiple la convergencia es lineal a menos que se utilice el metodo generalizado deNewton
xn+1 = xn − k ·f(xn)
f ′(xn)siendo k la multiplicidad de la raız
en cuyo caso la convergencia vuelve a ser de segundo orden.
c) La formula de Newton nos dice que xn+1 = xn −P (xn)
P ′(xn)y el metodo resultara de
segundo orden por tratarse de una raız simple.
Comenzando con x0 = −2′5 (se parte de una cifra decimal exacta) obtenemos, en laprimera aproximacion, que x1 = −2′5384 . . ., por lo que al ser una convergencia desegundo orden podemos asegurar que la raız real, con una cifra decimal exacta, esx = −2′5.
d) Dado que el termino independiente es 6 y una raız tiene de modulo 2’5, las raıcescomplejas tienen de modulo
√6/2’5 =
√2′4 < 2′5 por lo que −2′5 es un autovalor
dominante de A y, por tanto, el metodo de la potencia simple resulta convergente.
En otras palabras, podrıamos calcular la raız real del polinomio aplicando dicho metodoa la matriz A.
e) Dado que el algoritmo QR converge a una matriz triangular por cajas en la que losautovalores de cada caja son los autovalores de A de igual modulo, α = −2′5 (elautovalor dominante) y los autovalores de la caja de orden 2(
0′8 β
2′2 −0′3
)
son las raıces complejas de P (x).
Para β = 1′2 obtenemos la matriz (0′8 1′2
2′2 −0′3
)
cuya ecuacion caracterıstica es
λ2 − 0′5λ− 2′88 = 0 =⇒ λ =0′5±
√11′77
2
es decir, las raıces serıan reales y no complejas conjugadas, por lo que β = −1′2, esdecir, el proceso converge a la matriz −2′5 −5′2 1′7
0 0′8 −1′2
0 2′2 −0′3
Ejercicio 2
Se considera el sistema superdeterminado Ax = b con
A =
1 5
1 5
1 1
1 1
x =
(x
y
)b =
3
−11
5
3
a) Calcular su pseudosolucion, dando la norma del vector error, mediante transformacio-
nes de Householder.
b) Realizar la factorizacion QR de la matriz A y probar que A y R poseen la misma normaespectral (euclıdea).
c) c.1) ¿Puede resolverse mediante Cholesky el sistema formado por las ecuaciones nor-males de cualquier sistema superdeterminado Ax = b? Justificar la respuesta
c.2) Calcular la pseudosolucion del sistema dado aplicando Cholesky a sus ecuacionesnormales. Determinar la norma del vector error.
Solucion:
a) Dado que la matriz A tiene rango maximo, el sistema solo tiene una solucion en mınimoscuadrados que es su pseudosolucion.
x =
1
1
1
1
y =
‖x‖0
0
0
=
2
0
0
0
=⇒ v = x− y =
−1
1
1
1
H = I4 −2
vTvvvT = I4 −
1
2
1 −1 −1 −1
−1 1 1 1
−1 1 1 1
−1 1 1 1
=1
2
1 1 1 1
1 1 −1 −1
1 −1 1 −1
1 −1 −1 1
Quedandonos el sistema HAx = Hb con
HA =
2 6
0 4
0 0
0 0
Hb =
0
−8
8
6
por lo que la pseudosolucion buscada es la solucion del sistema(
2 6
0 4
)x =
(0
−8
)=⇒ x =
(6
−2
)
y la norma del error viene dada por
‖E‖ =
∥∥∥∥∥(
8
6
)∥∥∥∥∥ =√
82 + 62 = 10
b) Dado que HA =
2 6
0 4
0 0
0 0
= R =⇒ H2A = HR =⇒ A = HR (ya que H2 = I).
Por lo que A = QR con
Q = H =1
2
1 1 1 1
1 1 −1 −1
1 −1 1 −1
1 −1 −1 1
R =
2 6
0 4
0 0
0 0
ATA = (QR)T (QR) = RT (QTQ)R = RTR =⇒
‖A‖2 =maxi
√λi(ATA)
mıni
√λi(ATA)
=maxi
√λi(RTR)
mıni
√λi(RTR)
= ‖R‖2
c) c.1) Las ecuaciones normales vienen dadas por ATAx = AT b por lo que el sistemaresultante podra resolverse por Cholesky siempre que su matriz ATA sea simetricay definida positiva.
• Simetrica.-
(ATA)T = AT (AT )T = ATA =⇒ ATA es simetrica
• Definida positiva.-
xT (ATA)x = (xTAT )(Ax) = (Ax)T (Ax) = ‖Ax‖2 > 0 ∀x 6= 0
siempre que las columnas de la matriz A sean independientes, es decir, siempreque A tenga rango maximo.
Ası pues, la matrizATA es definida positiva y, por tanto, se puede aplicar Choleskysi, y solo si, A tiene rango maximo.
c.2) Las ecuaciones normales del sistema dado son
(1 1 1 1
5 5 1 1
)1 5
1 5
1 1
1 1
(x
y
)=
(1 1 1 1
5 5 1 1
)3
−11
5
3
(
4 12
12 52
)(x
y
)=
(0
−32
)(
4 12
12 52
)=
(a 0
b c
)(a b
0 c
)=⇒
a = 2
b = 6
c = 4
quedando el sistema(2 0
6 4
)(2 6
0 4
)(x
y
)=
(0
−32
)Llamando ahora (
2 6
0 4
)(x
y
)=
(α
β
)nos queda el sistema(
2 0
6 4
)(α
β
)=
(0
−32
)=⇒
(α
β
)=
(0
−8
)=⇒
(2 6
0 4
)(x
y
)=
(0
−8
)=⇒
(x
y
)=
(6
−2
)La pseudosolucion del sistema es
x = 6 y = −2
El vector error es E = A
(6
−2
)− b, por lo que
‖E‖ =
∥∥∥∥∥∥∥∥∥
1 5
1 5
1 1
1 1
(
6
−2
)−
3
−11
5
3
∥∥∥∥∥∥∥∥∥ =⇒
‖E‖ =
∥∥∥∥∥∥∥∥∥
−7
7
−1
1
∥∥∥∥∥∥∥∥∥ =
√(−7)2 + 72 + (−1)2 + 12 =
√100 = 10
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
5 de septiembre de 2007
Considerese la matriz A, con s ∈ R, definida por A =
4 −2 −4
−2 2 0
−4 0 s
Ejercicio 1
a) Analizar si existen valores de s para los que la matriz A es definida positiva. Recomen-dar razonadamente un metodo iterativo para resolver un sistema de ecuaciones linealesde la forma Ax = b, en el caso s = 10.
Supongase en adelante s = 10.
b) Utilizar el metodo de Cholesky para resolver el sistema de ecuaciones lineales Ax = b,con x = (x, y, z)T y b = (2,−2, 2)T . A partir del resultado obtenido, hallar el vectorq1 que se obtiene con un paso del metodo de la potencia inversa, partiendo de q0 = b.¿Que es lo que aproxima q1?
c) Encontrar la pseudosolucion del sistema q1 x = Aq1, utilizando transformaciones deHouseholder.¿Es el x obtenido el autovalor de mınimo modulo de A? Razonar la respuesta.
d) Al utilizar MATLAB para aplicar el algoritmo QR a la matriz A = A0, en el quintopaso se obtiene
A5 =
12.0818 0.0313 0.0000
0.0313 3.7412 0.0000
0.0000 0.0000 0.1770
.
¿Que aproxima el elemento a33 de la matriz A5? Describir como se obtiene la matrizA6 que resultarıa en el siguiente paso del algoritmo QR.
Solucion:
a) Al tratarse de una matriz simetrica, sera definida positiva si, y solo si, admite factori-zacion de Cholesky.
r11 0 0
r12 r22 0
r13 r23 r33
r11 r12 r13
0 r22 r23
0 0 r33
=
4 −2 −4
−2 2 0
−4 0 s
=⇒
r11 = 2
r12 = −1
r13 = −2
r22 = 1
r23 = −2
r233 = s− 8
por lo que admite dicha factorizacion si s ≥ 8. Es decir, A es definida positiva si, ysolo si, s ≥ 8.
b) Para el caso s = 10 se obtiene que r33 =√
2, por lo que el sistema Ax = b puedeescribirse de la forma
RTRx = b ⇐⇒
2 0 0
−1 1 0
−2 −2√
2
2 −1 −2
0 1 −2
0 0√
2
x
y
z
=
2
−2
2
y denotando por Rx = y se verifica que
RTy = b ⇐⇒
2 0 0
−1 1 0
−2 −2√
2
y1
y2
y3
=
2
−2
2
=⇒ y =
1
−1√2
Rx = y ⇐⇒
2 −1 −2
0 1 −2
0 0√
2
x
y
z
=
1
−1√2
=⇒ x =
2
1
1
El metodo de la potencia simple nos dice que
q1 = A−1q0 = A−1b =⇒ Aq1 = b =⇒ q1 = x =
2
1
1
donde q1 representa una primera aproximacion del autovector asociado al autovalor demenor modulo de la matriz A.
c)
q1x = Aq1 ⇐⇒ xx = Ax = b ⇐⇒
2
1
1
x =
2
−2
2
La transformacion de Householder que transforma el vector 2
1
1
en el
√
22 + 12 + 12
0
0
=
√
6
0
0
viene definida por el vector
v =
2
1
1
−√
6
0
0
=
2−√
6
1
1
Siendo H = I3 − 2
vvT
vTvy aplicada al sistema nos lo transforma en
√
6
0
0
x =
2√
6/3
2√
6/6− 2
2√
6/6 + 2
quedandonos que la pseudosolucion del sistema es la solucion de la ecuacion
√6x =
2√
6
3=⇒ x =
2
3
Evidentemente, el valor obtenido para x no es el autovalor de menor modulo de lamatriz A sino solo la primera arpoximacion obtenida mediante el metodo de la potenciainversa.
d) Al obtenerse una matriz triangular por cajas, a33 es uno de los autovalores de la matriz
A y los otros dos coinciden con los autovalores de la caja de orden 2
(12.0818 0.0313
0.0313 3.7412
)de determinante 45.1995 (producto de los modulos de los autovalores de igual modulo),por lo que el elemento a33 aproxima al autovalor de menor modulo de la matriz A.
Haciendo la factorizacion A5 = Q5R5 (mediante transformaciones de Householder), lamatriz A6 vendrıa dada por A6 = R5Q5.
Ejercicio 2
a) Determinar el polinomio caracterıstico p(x) de la matriz A, utilizando el metodo inter-polatorio.
b) Sabiendo que la sucesion S = (x3 − 16x2 + 48x− 8, 3x2 − 32x+ 48, 28x− 87, α)es una sucesion de Sturm para el polinomio p(x) en R, determinar un valor de αadecuado para completarla. Utilizar la sucesion S para obtener el numero de raıcespositivas de p(x).
c) Seleccionar razonadamente un punto inicial x0 que garantice la convergencia del metodode Newton a λ1, la menor de las raıces del polinomio p(x), conociendo la grafica en elintervalo que muestra la Figura 1. Hallar la aproximacion numerica que se obtiene deλ1 despues de dos iteraciones, partiendo de x0.
Figura 1: Grafica del polinomio p(x). Figura 2: Grafica de y = F ′(x).
d) Analizar la convergencia de la iteracion xn+1 = F (xn), siendo F (x) = (8 + 16x2 − x3)/48,partiendo de un punto x0 suficientemente proximo a λ1. ¿Puede ser el proceso iterativomas rapido que el de Newton?Indicacion: Un trozo de la grafica de F ′ se muestra en la Figura 2.
Solucion:
a) Sea p(x) = x3 + ax2 + bx+ c.
p(0) = c = det(0 · I − A) = det(−A) = −det(A) = −8
p(1) = 1 + a+ b+ c = det(1 · I − A) = det(I − A) = 25 =⇒ a+ b = 32
p(−1) = −1 + a− b+ c = det(−1 · I − A) = det(−I − A) = −73 =⇒ a− b = −64
de donde a = −16 y b = 48, resultando que
p(x) = x3 − 16x2 + 48x− 8
b) El resto de la division de 3x2 − 32x+ 48 entre 28x− 87 es el valor numerico que tomael polinomio 3x2 − 32x+ 48 para x = 87/28 que es, aproximadamente −22.465, por loque al ser α (salvo constantes positivas) el resto cambiado de signo de dicha division,un valor adecuado es α = 1.
Los signos que toma la sucesion S en 0 son (−,+,−,+) (3 cambios de signo) y cuandox se acerca a ∞ (+,+,+,+) (0 cambios de signo), por lo que p(x) tiene tres raıcespositivas.
c) A la vista de la grafica de p(x) en [0, 4] podemos asegurar la convergencia del metodode Newton si tomamos como valor inicial x0 = 0 ya que las sucesivas tangentes seaproximan a la solucion buscada.
x1 = x0 −p(x0)
p′(x0)= 0− −8
48= −1
6
x2 = x1 −p(x1)
p′(x1)= −1
6− p(−1/6)
p′(−1/6)≈ 0.1413
d) A la vista de la grafica observamos que en las proximidades de la raız buscada F ′(x)se mantiene menor que 1, por lo que el proceso resultara convergente, pero dado queen la raız F ′(x) 6= 0, el metodo de Newton producira una convergencia mas rapida quelas iteraciones xn+1 = F (xn).
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
26 de noviembre de 2007
Ejercicio 1
Se sabe que el polinomio caracterıstico de la matriz del tipo
An =
−an−1 −an−2 · · · −a1 −a0
1 0 · · · 0 0
0 1 · · · 0 0...
......
...
0 0 · · · 1 0
es P (λ) = λn + an−1λ
n−1 + · · ·+ a1λ+ a0. Se considera la matriz
A4 =
−4 95 198 100
1 0 0 0
0 1 0 0
0 0 1 0
a) Demostrar (sin calcularlo) que A4 tiene un autovalor doble.
b) Encontrar una matriz A3 que tenga los mismos autovalores que A4 pero simples.
c) Usando el metodo de Newton, encontrar el autovalor de A3 de mayor modulo con 12cifras decimales exactas.
d) Partiendo del vector x0 =
0.8
−1
1
y usando 4 cifras decimales, realizar 4 iteraciones
en el metodo de la potencia inversa para aproximar el autovalor de A3 de menor modulo.
Solucion:
a) El polinomio caracterıstico de la matriz es P4(x) = x4 + 4x3 − 95x2 − 198x− 100.
Si buscamos una sucesion de Sturm para dicho polinomio obtenemos:
f0(x) = P4(x) = x4 + 4x3 − 95x2 − 198x− 100
P ′4(x) = 4x3 + 12x2 − 190x− 198 =⇒ f1(x) = 2x3 + 6x2 − 95x− 99
2f0(x) = f1(x)(x+ 1) + (−101x2 − 202x− 101) =⇒ f2(x) = x2 + x+ 1
f1(x) = f2(x)(2x+ 2) + (−101x− 101) =⇒ f3(x) = x+ 1
f2(x) = f3(x)(x+ 1) =⇒ f4(x) = 0
por lo que el polinomio posee la raız doble x = −1 y, por tanto, la matriz A4 unautovalor doble.
b) EL polinomio que tiene las mismas raıces que P4(x) pero todas simples es
P3(x) =P4(x)
x+ 1= x3 + 3x2 − 98x− 100
por lo que la matriz pedida es
A3 =
−3 98 100
1 0 0
0 1 0
c) Una sucesion de Sturm para P3(x) viene dada por
g0(x) = P3(x) = x3 + 3x2 − 98x− 100
g1(x) = f1(x)/(x+ 1) = 2x2 + 4x− 99
g2(x) = f2(x)/(x+ 1) = x+ 1
g3(x) = f3(x)/(x+ 1) = 1
−12 −11 0 10
x3 + 3x2 − 98x− 100 − + − +
2x2 + 4x− 99 + + − +
x+ 1 − − + +
1 + + + +
Cambios de signo 3 2 1 0
La raız de mayor modulo es la que se encuentra en el intervalo [−12,−11].
Dado que P3(−12) < 0 y P3(−11) > 0, P ′3(x) = 3x2 + 6x − 98 y P ′′3 (x) = 6x + 6observamos que para cualquier x ∈ [−12,−11] es P ′′3 (x) < 0 lo que nos lleva a que
P ′(x) es decreciente pasando de 262 a 199 es decir, es siempre positiva, por lo que severifican las hipotesis de la regla de Fourier, debiendose comenzar a iterar en x0 = −12.
Ademas, sabemos que mınx∈[−12,−11]
P ′3(x) = 199.
La formula de Newton y el error a posteriori vienen dados respectivamente por
xn+1 = xn −P3(xn)
P ′3(xn)εn <
|P3(xn)|199
obteniendose:
x0 = −12
x1 = −11.16030534351145 ε1 < 0.114
x2 = −11.05165026330686 ε2 < 0.0019
x3 = −11.04987609098608 ε3 < 4.8 · 10−7
x4 = −11.04987562112092 ε4 < 3.4 · 10−14 < 10−12
por lo que el autovalor de mayor norma de la matriz A3 es −11.049875621121 con las12 cifras decimales exactas.
d) Dado A−13 =
1
100
0 100 0
0 0 100
1 3 −98
, obtenemos (sin escalar)
x1 = A−13 x0 =
−1
1
−1.0020
x2 = A−13 x1 =
1
−1.0020
1.0020
x3 = A−13 x2 =
−1.0020
1.0020
−1.0020
x4 = A−13 x3 =
1.0020
−1.0020
1.0020
Una aproximacion del autovalor de menor modulo es
xT4A3x4
xT4 x4
= −1
Ejercicio 2
Se pretende encontrar en R3 un plano de la forma z = αx+ βy que pase por los puntos 1
1
3
,
−1
1
0
,
0
1
−3
,
1
1
2
,
1
1
1
en donde α, β ∈ R.
a) Plantear el sistema de ecuaciones y comprobar que es incompatible.
b) Calcular la pseudosolucion del sistema usando el metodo de Choleski para resolver lasecuaciones normales, ası como la norma del error.
c) Calcular la pseudosolucion, ası como la norma del error, utilizando transformacionesunitarias en el sistema incompatible.
Solucion:
a) El sistema de ecuaciones es
α + β = 3
−α + β = 0
β = −3
α + β = 2
α + β = 1
⇐⇒
1 1
−1 1
0 1
1 1
1 1
(α
β
)=
3
0
−3
2
1
⇐⇒ Ax = b
el sistema es incompatible ya que si α + β = 3 no puede ser α + β = 2.
b) Las ecuaciones normales vienen dadas por
ATAx = AT b ⇐⇒
(4 2
2 5
)(α
β
)=
(6
3
)La factorizacion de Choleski de la matriz del sistema es(
4 2
2 5
)=
(2 0
1 2
)(2 1
0 2
)por lo que llamando
y =
(2 1
0 2
)(α
β
)obtenemos (
2 0
1 2
)y =
(6
3
)=⇒ y =
(3
0
)por lo que (
2 0
1 2
)(α
β
)=
(3
0
)=⇒
(α
β
)=
(3/2
0
)y el error viene dado por
E =
∥∥∥∥∥A(
3/2
0
)− b
∥∥∥∥∥ =
∥∥∥∥∥∥∥∥∥∥∥∥
−3/2
−3/2
3
−1/21/2
∥∥∥∥∥∥∥∥∥∥∥∥= 3.7417
c) Para transformar el vector x1 =
1
−1
0
1
1
en el y1 =
‖x1‖
0
0
0
0
=
2
0
0
0
0
hacemos
uso de la transformacion de Householder definida por el vector
v1 =x1 − y1
‖x1 − y1‖=
−0.5
−0.5
0
0.5
0.5
H1 = I5 − 2v1vT1 =
1
2
1 −1 0 1 1
−1 1 0 1 1
0 0 2 0 2
1 1 0 1 −1
1 1 0 −1 1
que transforma el sistema en
H1Ax = H1b ⇐⇒
2 1
0 1
0 1
0 1
0 1
x =
3
0
−3
2
1
Para transformar ahora el vector x2 =
1
1
1
1
1
en el
y2 =
1√
12 + 12 + 12 + 12
0
0
0
=
1
2
0
0
0
utilizamos la transformacion de Householder asociada al vector
v2 =x2 − y2
‖x2 − y2‖=
0
−0.5
0.5
0.5
0.5
que viene dada por
H2 = I5 − 2v2vT2 =
1
2
1 0 0 0 0
0 1 0 1 1
0 0 1 1 −1
0 1 −1 1 −1
0 1 −1 −1 1
que nos transforma el sistema en
H2H1Ax = H2H1b ⇐⇒
2 1
0 2
0 0
0 0
0 0
x =
3
0
−3
2
1
La pseudosolucion es la solucion del sistema(
2 1
0 2
)(α
β
)=
(3
0
)=⇒
(α
β
)=
(3/2
0
)
y el error viene dado por
E =
∥∥∥∥∥∥∥ −3
2
1
∥∥∥∥∥∥∥ =
√(−3)2 + 22 + 12 =
√14 = 3.7417
que son los mismos resultados que obtuvimos en el apartado anterior.
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
19 de junio de 2008
Ejercicio 1
Considerese la ecuacion f(x) = 0, siendo f(x) = x − 2 e−x la funcion cuya grafica en elintervalo [0, 2] aparece en la Figura 1.
Figura 1: y = x− 2 e−x en [0, 2]. Figura 2: y = 2 e−x en [0, 2].
a) Probar analıticamente que la ecuacion f(x) = 0 tiene solucion unica, x = α, en elintervalo I = [0, 2]. Estudiar si es posible aplicar la regla de Fourier en el intervalo Ial utilizar el metodo de Newton para calcular dicha raız.
b) Utilizar el metodo de dicotomıa para reducir el intervalo I a un nuevo intervalo deamplitud 0.5 que contenga a la solucion x = α.
c) Empezando en α0 = 2, acotar el error en la aproximacion de la solucion que se obtienecon tres pasos del metodo de Newton. Si se continua aplicando el metodo de Newton,¿se puede asegurar la convergencia de la sucesion (αn) que se origina?
d) Empezando en β0 = 2, construir sobre la grafica de la funcion G(x) = 2 e−x, que semuestra en la Figura 2, los primeros pasos de la red que describe el proceso iterativoβn+1 = G(βn). ¿Se aprecia convergencia o divergencia de la sucesion (βn)?
e) Probar que el proceso iterativo βn+1 = 2 e−βn converge a x = α, si se empieza sufi-cientemente cerca de la solucion. Analizar la velocidad de convergencia de la sucesion(βn), y compararla con la sucesion (αn) que origina el metodo de Newton partiendo deun mismo punto α0 = β0 ∈ [0, 1].
Solucion:
a) La continuidad de la funcion f(x) = x − 2 e−x y el cambio de signo en los extremosdel intervalo, f(0) = −2 y f(2) = 2 − 2/e2 > 0, garantizan solucion de la ecuacionf(x) = 0 en I (teorema de Bolzano).
Por otro lado, f ′(x) = 1 + 2 e−x > 0 implica que la funcion y = f(x) es creciente en R;en particular, y = f(x) solo puede cortar al eje de abscisas una sola vez en el intervalo[0, 2].
Ya que f ′′(x) = −2 e−x < 0, para todo x ∈ R, los signos de f ′ y f ′′ permanecenconstantes en el intervalo I, por lo que es aplicable la regla de Fourier: Partiendo deun punto x0 ∈ I en el que signo(f(x0)) = signo(f ′′) < 0, la sucesion (xn) que originael metodo de Newton es una sucesion creciente que converge a la solucion x = α.
b) Partiendo de I0 = [a0, b0] = [0, 2], con f(a0) < 0 y f(b0) > 0, se verifica
α1 =a0 + b0
2= 1, f(α1) = 1− 2
e> 0 =⇒ α ∈ [a0, α1] =⇒ I1 = [a1, b1] = [0, 1]
α2 =a1 + b1
2=
1
2, f(α2) =
1
2− 2√
e< 0 =⇒ α ∈ [α2, b1] =⇒ I2 = [a2, b2] = [0.5, 1]
Por lo tanto, el intervalo pedido es I2 = [0.5, 1], como puede apreciarse en la Figura 1.
c) El metodo de Newton para la ecuacion f(x) = 0, con f(x) = x − 2 e−x, es el procesoiterativo αn+1 = F (αn), siendo F (x) = x − f(x)/f ′(x) la funcion de iteracion. Porconsiguiente:
F (x) = x− x− 2 e−x
1 + 2 e−x=
2x+ 2
ex + 2=⇒ αn+1 = 2
αn + 1
eαn + 2.
Partiendo de α0 = 2, y redondeando los resultados a diezmilesimas, se tiene
α1 = 2α0 + 1
eα0 + 2= 2
2 + 1
e2 + 2≈ 0.6390
α2 = 2α1 + 1
eα1 + 2≈ 0.8417
α3 = 2α2 + 1
eα2 + 2≈ 0.8526.
Dado que, f ′(x) = 1 + 2 e−x es decreciente, y se tiene la acotacion 1 < f ′(x) < 3 (porejemplo), en el intervalo [0, 2], el problema de la evaluacion inversa para f esta biencondicionado y se puede acotar el error |α− α3| a posteriori, en la forma
|α− α3| ≤|f(α3)|
min |f ′(x)|< |f(α3)| ≈ 0.0002 .
La acotacion asegura que α ≈ 0.8526 es una aproximacion de la solucion con 3 cifrasdecimales exactas.
Tomando x0 = α1, se verifica que signo(f(x0)) = signo(f ′′), y la regla de Fourier,analizada en el apartado 1, garantiza la convergencia del metodo de Newton. Porconsiguiente, (αn)→ α .
d) En la Figura 2 se han dibujado los primeros 15 pasos de la red, que muestran unasucesion (βn) oscilante, pero que parece converger lentamente al punto fijo de la funciony = G(x).
e) El proceso iterativo responde al proceso iterativo de punto fijo que determina la funciony = G(x) del apartado anterior. Si converge, la continuidad de la funcion G implicaque
βn+1 = 2 e−βn(βn)→β=⇒ β = 2 e−β =⇒ β = sol(f(x) = 0) = α .
Por otro lado, |G′(x)| = G(x) toma valores < 1 en un entorno de x = α, como muestrala Figura 2; por lo tanto, se garantiza |G′(α)| < 1 y x = α es un punto fijo atractivode G. La convergencia esta garantizada entonces porque y = G(x) es una aplicacioncontractiva en un entorno del punto fijo.
Como f ′(α) 6= 0, la raız x = α de la ecuacion f(x) = 0 es simple y el metodo de Newtonconverge cuadraticamente. Por contra, como G′(α) 6= 0, el proceso iterativo βn+1 =G(βn) converge linealmente. De hecho, al ser |G′(α)| = G(α) = α, la aproximacionα ≈ 0.8526 del apartado 3 muestra una tasa asintotica de convergencia |G′(α)| > 1/2,por lo que (βn) converge incluso mas lentamente que la sucesion que proporciona elmetodo de dicotomıa. . .
Ejercicio 2
Considerense las matrices A y L, definidas por
L =
3 0 0
−2 1 0
1 0 −2
y A = LLT .
a) Calcular ‖L‖∞ y analizar el condicionamiento de la matriz L para la norma ‖ ‖∞.
b) Probar que la matriz A es definida positiva. Determinar su factorizacion de Cholesky.
Analizar la convergencia o divergencia del metodo iterativo de Gauss-Seidel para resol-ver el sistema de ecuaciones Ax = b, siendo b un vector arbitrario de R3.
c) Hallar un vector v que aproxime a un autovector dominante de la matriz A, partiendode v0 = (1, 2, 1)T y realizando un paso del metodo de la potencia.
Aproximar el autovalor dominante de la matriz A, utilizando las ecuaciones normalescon el sistema incompatible v λ = Av.
d) Utilizando transformaciones de Householder en el sistema v λ = Av del apartadoanterior, determinar el error en la pseudosolucion.
e) Describir como se emplea el algoritmo QR para el calculo de los autovalores y autovec-tores de la matriz A, y la relacion existente entre los autovalores de las matrices Ak−1
y Ak utilizadas en el paso k-esimo del algoritmo.
Solucion:
a) Como ‖L‖∞ = max{∑n
j=1 |lij| : i = 1, 2 . . . , n}
, se tiene ‖L‖∞ = max{3, 3, 3} = 3 .
Por otro lado, como κ∞(L) = ‖L‖∞‖L−1‖∞ , la matriz L esta bien condicionada, yaque
L−1 =1
6
2 0 0
4 6 0
1 0 −3
=⇒ ‖L−1‖∞ =1
6max{2, 10, 4} =
5
3=⇒
κ∞(L) = 35
3= 5 .
b) La existencia de la factorizacion de Cholesky A = RTR, con R triangular superior yelementos diagonales positivos, prueba que es definida positiva. Por otra parte, ya queA = LLT , con L triangular inferior, la unicidad de la factorizacion permite determinarR en la forma
A = L
1 0 0
0 1 0
0 0 −1
1 0 0
0 1 0
0 0 −1
LTA=RTR
=⇒
RT = L
1 0 0
0 1 0
0 0 −1
=
3 0 0
−2 1 0
1 0 2
.
NOTA: Por supuesto, cualquier otra forma de obtener la factorizacion de Choleskyconduce a la misma R. Por otro lado, se podrıa haber probado que A es definidapositiva utilizando cualquier caracterizacion de la propiedad. Por ejemplo, que losdeterminantes de las submatrices principales de A o los pivotes de su factorizacion LUsean positivos, etc. E incluso, de un modo mas teorico, ya que si A = LLT , siendo Lno singular, se verifica xTAx = ‖ LTx‖22 > 0.
La condicion definida positiva de la matriz A implica la convergencia del metodo deGauss-Seidel.
NOTA: No obstante, puede obtener la matriz B de la iteracion de Gauss-Seidel,xn+1 = B xn + c, y comprobar que el radio espectral es ρ(B) < 1:
B =
0 2/3 −1/3
0 4/5 0
0 −2/25 1/5
=⇒ autov(B) =
{0,
4
5,
1
5
}=⇒ ρ(B) =
4
5.
c) El metodo de la potencia obtiene la sucesion de vectores (vk), donde vk = Avk−1/σk,escalando Avk−1 con algun numero σk (en caso necesario). Teniendo en cuenta el valorde A, y partiendo del vector v0 = (1, 2, 1)T , en un paso se puede tomar v = v1, con elvalor σ1 que mejor convenga para operar en aritmetica exacta. . .
v0 =
1
2
1
=⇒ Av0 =
9 −6 3
−6 5 −2
3 −2 5
1
2
1
=
0
2
4
σ1=2
=⇒ v =1
2Av0 =
0
1
2
.
Para el sistema vλ = Av, las ecuaciones normales son vTv λ = vTA v. Entonces,
(0 1 2
)0
1
2
λ =(
0 1 2)
9 −6 3
−6 5 −2
3 −2 5
0
1
2
∼ 5λ = 17 =⇒
λ =17
5= 3.4 .
NOTA: En realidad, el sistema vλ = Av, es0
1
2
λ =
9 −6 3
−6 5 −2
3 −2 5
0
1
2
∼
0
1
2
λ =
0
1
8
y por lo tanto se podrıa suprimir la ecuacion “0λ = 0” y operar con un sistemaincompatible de solo dos ecuaciones para determinar la aproximacion de λ.
d) Para resolver el sistema v λ = Av basta una transformacion de Householer que lleveel vector v = (0, 1, 2)T al vector r = (±‖v‖2, 0, 0)T ; entonces, H = I − 2uuT , siendou un vector unitario en la direccion v− r. Por ejemplo, tomando r = (−
√5, 0, 0)T , se
tiene v − r = (√
5, 1, 2)T , y la matriz de Householder H queda determinada por
H = I − 2
‖v − r‖22(v − r) (v − r)T = I − 1
5
√
5
1
2
( √5 1 2).
Para calcular H b, se tiene H b =(I − 1
5(v − r)(v − r)T
)b = b− 1
5(v− r)(v− r)T b. En
el caso particular b = Av = (0, 1, 8)T , se tiene (v−r)T b = 17, y el vector transformadoresulta
Hb =
0
1
8
− 1
5
√
5
1
2
( √5 1 2)
0
1
8
=
0
1
8
− 17
5
√
5
1
2
=⇒
Hb =1
5
−17√
5
−12
6
.
Entonces, el sistema vλ = Av, se transforma en
vλ = Av×H−→
−√
5
0
0
λ =1
5
−17√
5
−12
6
∼
R
Θ
λ =
c1
c2
=⇒
(1) λ = sol(R λ = c1
)= sol
[−√
5λ = −17
5
√5
]=⇒ λ =
17
5.
(2) c2 =1
5
−12
6
=⇒ ‖vλ− Av‖2 = ‖c2‖2 =6
5
√5 ≈ 2.68 .
e) Partiendo de la matriz A0 = A, el paso k-esimo del algoritmo se realiza calculandola factorizacion QR de la matriz del paso anterior, Ak−1 = Qk Rk, y obteniendo lanueva matriz Ak como el producto Ak = RkQk, cambiando el orden de las matricesresultantes de la factorizacion de Ak−1.
Dado que Qk es una matriz ortogonal, se verifica QTkQk = I. Por consiguiente,
Ak = RkQk = QTk Qk RkQk
Ak−1=QkRk
=⇒ Ak = QTk Ak−1Qk .
Ası, Ak y Ak−1 son unitariamente semejantes y tienen teoricamente los mismos auto-valores; ademas, desde el punto de vista numerico, lo interesante es que, en la practica,los autovalores de ambas matrices no se van diferenciar mas alla del orden de la per-turbacion introducida en los calculos. En efecto, si numericamente λ y µ representanel mismo autovalor teorico para Ak−1 y Ak, al ser κ2(Qk) = 1, el condicionamientode la matriz de paso Qk no interviene en la acotacion |λ − µ| ≤ κ2(Qk) ‖δAk−1‖2 quepermite medir el efecto global de la perturbacion transmitida a los autovalores.
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
1 de septiembre de 2008
Ejercicio 1
Se desea aproximar el valor de α =
√1 +
√1 +√
1 + · · · y para ello se tiene que
α2 = 1 +
√1 +
√1 +√
1 + · · · = 1 + α =⇒ α2 = 1 + α =⇒ α =√
1 + α
es decir, se trata de buscar el punto fijo de la funcion
ϕ(x) =√
1 + x
a) Verificar las condiciones de convergencia de la sucesion (xn) definida por xn+1 = ϕ(xn)partiendo de cualquier punto x0 del intervalo [1, 2]. En caso de ser convergente, ¿deque orden resultara la convergencia?
b) Partiendo de x0 = 1.5, realizar diez iteraciones. ¿Como acotarıamos el error en ladecima iteracion?
c) ¿Se tiene ya el valor de α con cinco cifras decimales exactas?
d) Si aproximamos el valor de α a traves de la ecuacion x2 − x− 1 = 0 por el metodo deNewton, ¿de que orden resultarıa la convergencia? Justifica la respuesta.
e) Aproximar el valor de α por el metodo de Newton (con cinco cifras decimales exactas)estudiando previamente su convergencia mediante la regla de Fourier.
Solucion:
a) Dado que ϕ([1, 2]) ⊆ [1, 2]
ϕ′(x) =1
2√
1 + x< 1 ∀x ∈ [1, 2]
el metodo es convergente partiendo de cualquier numero real x ∈ [1, 2].
Teniendo en cuenta que ϕ′(x) no se anula en ningun punto del intervalo [1, 2], laconvergencia resultara de primer orden.
b)
x1 =√
1 + x0 = 1.58113883008419 x6 =√
1 + x5 = 1.61792949242847
x2 =√
1 + x1 = 1.60659230363032 x7 =√
1 + x6 = 1.61800169728850
x3 =√
1 + x2 = 1.61449444211813 x8 =√
1 + x7 = 1.61802401010878
x4 =√
1 + x3 = 1.61693983874420 x9 =√
1 + x8 = 1.61803090517727
x5 =√
1 + x4 = 1.61769584246984 x10 =√
1 + x9 = 1.61803303587327
La cota del error “a posteriori”, teniendo en cuenta que estamos resolviendo la ecuacionx− ϕ(x) = 0, viene dada por
ε10 ≤|x10 −
√1 + x10|
mınx∈[1,2]
|1− ϕ′(x)|
ε10 ≤1.61803303587327− 1.61803369429480
1− 12√
2
=6.58 · 10−7
0.64644660940673= 1.0179 · 10−6 < 10−5
c) Dado que α = 1.61803303587327 con un error ε < 1.0179 · 10−6, el valor α = 1.61803 tendraun error
ε < 0.00000303587327 + 0.0000010179 = 0.0000040538 < 10−5
por lo que α = 1.61803 con las cinco cifras decimales exactas.
d) Al tratarse de una raız simple de la ecuacion f(x) = x2 − x − 1 = 0, el metodo de Newtonresultara de segundo orden.
e) Dado que α es la raız positiva de la ecuacion f(x) = x2 − x− 1 = 0 con
f(1) = −1 < 0 f(2) = 1 > 0
f ′(x) = 2x− 1 > 0 ∀x ∈ [1, 2]
f ′′(x) = 2 > 0 ∀x ∈ [1, 2]
sabemos que el metodo de Newton resultara convergente partiendo de x0 = 2.
xn+1 = xn −f(xn)f ′(xn
= xn −x2n − xn − 12xn − 1
=x2n + 1
2xn − 1
x0 = 2x1 = 1.66666666666667x2 = 1.61904761904762x3 = 1.61803444782168
que ya tiene cinco cifras decimales exactas.
Ejercicio 2
Se considera la matriz A =
5 1 1
1 0 1
0 1 9
.
a) Haciendo uso de sus cırculos de Gerschgorin, y sabiendo que en cada cırculo hay, almenos un autovalor, ¿se puede probar la convergencia del metodo de la potencia simple?
b) Partiendo del vector x0 = (2, 1, 7)T , realizar tres iteraciones (sin escalado) del metodode la potencia simple, junto con el cociente de Rayleigh, para aproximar el autovalordominante de la matriz A.
c) Solo con los datos del primer apartado: ¿podrıamos garantizar la convergencia delmetodo de la potencia inversa aplicado a la matriz A− 5I?
d) Queremos resolver el sistema (A − 5I)x = b con b = (5, 1, 0)T mediante la facto-rizacion LU y observamos que la matriz del sistema no admite dicha factorizacion.¿Alterarıamos el condicionamiento del sistema si intercambiamos las dos primerasecuaciones?
e) Intercambia dichas ecuaciones y resuelvelo mediante la factorizacion LU .
f) Aplicar el cociente de Rayleigh a la matriz A y la solucion obtenida en el apartadoanterior. ¿De quien estamos obteniendo una primera aproximacion?
Solucion:
a) Los cırculos de Gerschgorin tienen centros en los puntos del eje real 5, 0 y 9 con radiosrespectivos 2, 2 y 1.
lo que nos asegura que la matriz tiene los tres autovalores reales y que se encuentranen los intervalos [−2, 2], [3, 7] y [8, 10].
Dado que el que se encuentra en el intervalo [8, 10] es mayor, en modulo, que los otrosdos (es dominante) el metodo de la potencia simple resultara convergente.
b) Partiendo del vector x0 = (2, 1, 7)T y sin escalar, obtenemos:
x1 = Ax0 =
18
9
64
x2 = Ax1 =
163
82
585
x3 = Ax2 =
1482
748
5347
y aplicando el cociente de Rayleigh obtenemos que la aproximacion del autovalor do-minante obtenida es
λ =xT3 Ax3
xT3 x3
=286435739
31346237= 9.1378
c) Los cırculos de Gerschgorin de la matriz A − 5 I =
0 1 1
1 −5 1
0 1 4
son los mismos
que los de la matriz A desplazados 5 unidades a la izquierda
por lo que la matriz A−5 I tiene un autovalor de menor valor absoluto que los otros dosy, por tanto, el metodo de la potencia inversa aplicado a dicha matriz es convergente.
d) La matriz del cambio de filas que permuta las dos primeras ecuaciones,
F1,2 =
0 1 0
1 0 0
0 0 1
es unitaria (F T
1,2 · F1,2 = F1,2 · F T1,2 = I), por lo que no altera el condicionamiento del
sistema.
e) Intercambiando las ecuaciones obtenemos el sistema Bx = c con
B =
1 −5 1
0 1 1
0 1 4
c =
1
5
0
Realizando la factorizacion LU de la matriz B obtenemos
B = LU =
1 0 0
0 1 0
0 1 1
1 −5 1
0 1 1
0 0 3
Bx = c ⇐⇒ LUx = c ⇐⇒ Ly = c con Ux = y
Ly = c ⇐⇒
1 0 0
0 1 0
0 1 1
y =
1
5
0
=⇒ y =
1
5
−5
Ux = y ⇐⇒
1 −5 1
0 1 1
0 0 3
x =
1
5
−5
=⇒ x =1
3
108
20
−5
f) Aplicando el cociente de Rayleigh a la matriz A y el vector x obtenemos
xT Ax
xT x=
62125/912089/9
=62125
12089= 5.1389
Observese que lo que hemos hecho es una iteracion del metodo de la potencia inversacon desplazamiento (desplazamiento 5) a la matriz A,
x0 = (5, 1, 0)T x1 = (A− 5 I)−1x0
por lo que el valor obtenido es una primera aproximacion del autovalor de la matriz Amas proximo a 5.
E.T.S. de
Ingenierıa Informatica
Algebra Numerica
Ingenierıa Informatica
24 de noviembre de 2008
Ejercicio 1
Considerense la matriz A =
2 1 2
1 2 0
2 0 2
de polinomio caracterıstico P (λ) = λ3−6λ2+7λ+2
y el vector z0 = (7 ,−3 ,−6)T . Se pide:
a) Calcular, razonadamente, el numero de raıces reales que posee, localizando cada unade ellas dentro de un intervalo [a, a+ 1] con a entero.
b) Para la mayor de ellas, comprobar que se verifican las condiciones de Fourier (en elintervalo obtenido en al apartado anterior), indicando el extremo en el que se debecomenzar a iterar para garantizar la convergencia del metodo de Newton, y efectuartres iteraciones de dicho metodo.
c) Comenzando por z0 y sin calcular A−1, efectuar una iteracion del metodo de la potenciainversa para aproximar un autovector asociado al autovalor de menor valor absoluto.Aproximar dicho autovalor utilizando el cociente de Rayleigh.
d) Encontrar un intervalo de longitud 0.1 que contenga a dicho autovalor y estimar elerror cometido en la aproximacion obtenida en el apartado anterior.
Solucion:
a)
P (−1) = −1 < 0
P ( 0 ) = 2 > 0
}=⇒ en [−1, 0] existe una raız
P (2) = 0 =⇒ 2 es una raız
P (4) = −2 < 0
P (5) = 12 > 0
}=⇒ en [4, 5] existe otra raız
Es decir, posee tres raıces reales, una de ellas es 2 y las otras se encuentran en losintervalos [−1, 0] y [4, 5].
b) Sabemos ya que P (4) < 0 y P (5) > 0 (cambia de signo en los extremos del intervalo).Ademas,
P ′(λ) = 3λ2 − 12λ+ 7
P ′′(λ) = 6λ− 12 > 0 ∀λ ∈ [4, 5]
Al ser P ′′(λ) > 0 ∀λ ∈ [4, 5] sabemos que P ′(λ) es creciente en dicho intervalo,pasando de P ′(4) = 7 a P ′(5) = 22, por lo que P ′(λ) > 0 ∀λ ∈ [4, 5] y, por tanto, severifican las condiciones de Fourier en dicho intervalo.
El extremo en el que debe iniciarse el metodo de Newton es 5, extremo en el quecoinciden los signos de P (λ) y P ′′(λ).
La formula de Newton viene dada por
λn+1 = λn −P (λn)
P ′(λn)= λn −
λ3n − 6λ2
n + 7λn + 2
3λ2n − 12λn + 7
=2λ3
n − 6λ2n − 2
3λ2n − 12λn + 7
y partiendo de λ0 = 5 obtenemos
λ1 = 4.45454545454545
λ2 = 4.26215377542811
λ3 = 4.23651235699098
c)z1 = A−1z0 ⇐⇒ Az1 = z0
por lo que se trata de resolver el sistema 2 1 2
1 2 0
2 0 2
z1 =
7
−3
−6
⇐⇒
0 1 0
1 2 0
2 0 2
z1 =
13
−3
−6
⇐⇒
0 1 0
1 0 0
2 0 2
z1 =
13
−29
−6
⇐⇒
0 1 0
1 0 0
0 0 2
z1 =
13
−29
52
⇐⇒
0 1 0
1 0 0
0 0 1
z1 =
13
−29
26
=⇒ z1 =
−29
13
26
Una aproximacion del autovalor de menor modulo de A viene dada por
zT1 Az1
zT1 z1
=−398
1686= −0.23606168446026
d) A la vista de la aproximacion obtenida ıntimos que el autovalor se encuentra en elintervalo [−0.3,−0.2], dato que confirmamos viendo que P (−0.3) = −0.667 < 0 yP (−0.2) = 0.352 > 0.
Dado que
P ′(λ) = 3λ2 − 12λ+ 7 > 0
P ′′(λ) = 6λ− 12 < 0
∀λ ∈ [−0.3,−0.2]
P ′(λ) es decreciente y positiva, por lo que el mınimo lo alcanza en −0.2, es decir,
mınλ∈[−0.3,−0,2]
|P ′(λ)| = P ′(−0, 2) = 0.352
El error vendra dado por
ε ≤ |P (−0.23606168446026)|0.352
<6.293013 · 10−5
0.352< 1.8 · 10−4
Ejercicio 2
Consideremos el sistema superdeterminado Ax = b donde
A =
1 −1 0
−1 1 1
1 2 1
−1 2 0
x =
x
y
z
y b =
5
1
−1
3
a) Se pretende resolver el sistema formado por sus ecuaciones normales mediante los
metodos iterativos de Jacobi o Gauss-Seidel. Usando el Teorema de los cırculos deGerschgorin, ¿de que metodo se tiene garantizada la convergencia?
b) Calcular la pseudosolucion y la norma del error del sistema superdeterminado resol-viendo sus ecuaciones normales por el metodo de descomposicion LU .
c) Usando transformaciones unitarias, calcular la pseudosolucion, ası como la norma delvector error, del sistema superdeterminado.
Solucion:
a) Las ecuaciones normales del sistema:
ATAx = AT b
vienen dadas por 4 −2 0
−2 10 3
0 3 2
x =
0
0
0
• La matriz de Jacobi viene dada por
J =
4 0 0
0 10 0
0 0 2
−1 0 2 0
2 0 −3
0 −3 0
=
0 0.5 0
0.2 0 −0.3
0 −1, 5 0
cuyos cırculos de Gerschgorin son concentricos en el origen y de radios 0.5, 0.5 y1.5, es decir, el dominio de Gerschgorin es un cırculo centrado en el origen y deradio 1.5 lo que NO nos garantiza que todos sus autovalores sean menores que1 y, por tanto, que ρ(J) < 1, que es la condicion necesaria y suficiente para laconvergencia.
• La matriz de Gauss-Seidel viene dada por
L1 =
4 0 0
−2 10 0
0 3 2
−1 0 2 0
0 0 −3
0 0 0
=
0 0.5 0
0 0.1 −0.3
0 −0.15 0.45
cuyos cırculos de Gerschgorin son:
C1 = {z : |z − 0| ≤ 0.5}C2 = {z : |z − 0.1| ≤ 0.3}C3 = {z : |z − 0.45| ≤ 0.15}
por lo que ahora, SI podemos asegurar que sus autovalores son menores que 1 yque por tanto ρ(L1) < 1, lo que nos garantiza la convergencia del metodo.
b) La factorizacion LU viene dada por 4 −2 0
−2 10 3
0 3 2
=
1 0 0
−1/2 1 0
0 1/3 1
4 −2 0
0 9 3
0 0 1
quedandonos el sistema 1 0 0
−1/2 1 0
0 1/3 1
4 −2 0
0 9 3
0 0 1
x =
0
0
0
Llamando 4 −2 0
0 9 3
0 0 1
x = y
resolvemos, en primer lugar el sistema 1 0 0
−1/2 1 0
0 1/3 1
y =
0
0
0
=⇒ y =
0
0
0
y posteriormente el sistema 4 −2 0
0 9 3
0 0 1
x = y =
0
0
0
=⇒ x =
0
0
0
Observese que el sistema de las ecuaciones normales es homogeneo y con
rg
4 −2 0
−2 10 3
0 3 2
= 3
por lo que solo admite la solucion trivial, que es la que se ha obtenido.
c) Resolvamos ahora el sistema mediante transformaciones de Householder. Buscamos latransformacion
x1 =
1
−1
1
−1
→ y1 =
‖x1‖
0
0
0
=
2
0
0
0
que viene definida por el vector
v1 = x1 − y1 =
−1
−1
1
−1
=⇒ H1 = I4 −2
vT1 v1
v1vT1 =
1
2
1 −1 1 −1
−1 1 1 −1
1 1 1 1
−1 −1 1 1
quedandonos que
H1A =
2 −1 0
0 1 1
0 2 1
0 2 2
y H1b =
0
−4
4
−2
Buscamos ahora una segunda transformacion
x2 =
−1
1
2
2
→ y2 =
−1√
12 + 22 + 22
0
0
=
−1
3
0
0
que viene definida por el vector
v2 = x2 − y2 =
0
−2
2
−2
=⇒ H2 = I4 −2
vT2 v2
v2vT2 =
1
3
3 0 0 0
0 1 2 2
0 2 1 −2
0 2 −2 1
quedandonos que
H2H1A =
2 −1 0
0 3 1
0 0 1
0 0 0
y H2H1b =
0
0
0
−6
La solucion del sistema superdeterminado viene dada por la del sistema 2 −1 0
0 3 1
0 0 1
x =
0
0
0
=⇒ x =
0
0
0
y la norma del vector error viene dada por
‖E‖ = ‖ − 6‖ = 6