Programaci´on:

Sistemas tridiagonales de ecuaciones lineales

Objetivos. Escribir una funci´on que resuelva sistemas de ecuaciones lineales de la si-
guiente forma (para un orden n arbitrario):

a1 b 1 0 0 0 x1 r1
x2 r2
c1 a 2 b 2 0 0
x3 = r3
0 c2 a 3 b 3 0 . (1)
3 4 4 x4 r4
0 0 c a b
4
0 0 0 c a 5 x5 r5

Sistemas tridiagonales surgen en muchas aplicaciones, por ejemplo, en la interpolaci´on seg-

mentaria c´ubica y en el m´etodo de diferencias finitas para resolver ecuaciones diferenciales
con condiciones de la frontera.

Requisitos. Idea de la eliminaci´on de Gauss, sustituci´on hacia atr´as, programaci´on con

vectores y matrices.

1. Ejemplo. Mostremos la idea de soluci´on con un ejemplo. Primero aplicamos opera-

ciones elementales y reducimos la matriz del sistema a una matriz triangular superior.
Usamos 2las entradas diagonales 2 como pivotes: 1
R += 2R 1 R +=−5R2
−−−−−− −−−−−−−
3 0 1 µ=− −4 =2 2 3 0 1 µ=− 5 =−5 2 3 0 1

−4 −5 4 −11 2 → 0 1 4 −9 3 → 0 1 4 −9 .

0 5 2 9 0 25 2
2x1 + 3x 9 0 0 −18 54
2
La ´ultima matriz aumentada corresponde al siguiente3 sistema:
3 2 1 = 1;

x + 4x 3 = −9;
3 2 1

− 18x = 54.

Calculamos x , x , x (usamos la tercera ecuaci´on, luego la segunda, y luego la primera):

54 −9 − 4x 3 1 − 3x 2
x = = −3; x = = 3; x = = −4.
−18 1 2

Comprobaci´on:

2 3 0 −4 −8 + 9 1

−4 −5 4 3 = 16 − 15 − 12 = −11 .
 0 5 2 −3 0 + 15 − 6 9

Programaci´on: Sistemas tridiagonales de ecuaciones lineales, p´agina 1 de 4

F´ormulas para resolver un sistema tridiagonal
(se recomienda deducirlas antes de la clase pr´ actica)
En la primera etapa hacemos operaciones elementales del tipo R p+1 + = µR para
p eliminar
los coeficientes c k. Los coeficientes nuevos de la diagonal principal denotemos por d y klas
constantes nuevas (en el lado derecho del sistema) denotemos por s . k

2. Ejemplo: n = 5, etapa preparatoria. Las entradas a y1 r no 1 necesitan ninguna

modificaci´on, solamente las copiamos en las variables d y1 s para
1 hacer los siguientes
pasos del algoritmo m´as regulares. Est´an marcadas las variables que obtienen valores
nuevos:

a1 b 1 0 0 0 r1 d1 b1 0 0 0 s1
1 2 2 d 1 :=a 1 2 2
c a b 0 0 r2 s1 :=r 11
−−−−− c d b 0 0 r2
1 3 3 2 3 3
00 c0 ac ba b0 r3 → 0 c0 dc bd b0 r3
3 4 3 4 4
4 r4 0 r4
4 4
0 0 0 c a 5 r5 0 0 0 c a5 r5

Para deducir las f´ormulas que se aplican en el p-´esimo paso del algoritmo consideremos
un caso particular:

3. Ejemplo: n = 5, paso p = 3. 4Supongamos 3 que n = 53 y que ya hemos hecho los 4

primeros
4 dos pasos del algoritmo. Consideremos el tercer paso. Vamos a realizar una
operaci´on elemental de la forma R + = µR . La entrada d es el pivote, y las entradas d
y s son las que1 obtienen
1 valores nuevos:
1 1 1 1
2 2 2 0 d 2 b 2 2
R += µR 3
d b d03 b0 3 00 s3 −−−−−− d0 b0 d03 b0 0 s3
0 0 c3 a 4 b r 0 0 0 d 4 4
0 d b 0 0 s 0 0 s
4 4
0 0 s 4 → 3 0 s
4 4 4 4b s 3
3
0 0 0 c a 5 r5 0 0 0 c a 5 r5
3 3

El coeficiente µ elegimos de tal manera que la operaci´on elemental R + = µR elimine la

entrada
Adem´ c : 4 3 4 4
c + µd = 0;
4 4 =⇒ µ= .

4 4 | {z }
?

as la operaci´on R + = µR afecta a las entradas que ten´ıan valores a y r . Deno-

tamos sus valores nuevos por d y s y los calculamos mediante las siguientes f´ormulas:

d = , s =
| {z } + µ | {z } | {z } + | {z } | {z } .
? ? ? ? ?
Programaci´on: Sistemas tridiagonales de ecuaciones lineales, p´agina 2 de 4
4. Primera etapa: f´ormulas generales.
El contador del ciclo p toma valores desde | {z } hasta | {z } .

? ?

Vamos a planear la p-´esimap iteraci´on del ciclo: p+1 p

Queremos eliminar c aplicando una operaci´on elemental R + = µR .

p
El coeficiente µ de esta operaci´on elemental se calcula de tal manera que se elimine
la entrada c : p

c + µ
| {z } = 0 =⇒ µ := | {z } .
p+1 p
? ?
p+1

Para realizar la operaci´on elemental R + = µR , los valores nuevos de a p+1 y

r p+1 denotados
p+1 por d p+1 y s respectivamente, se calculan mediante las siguientes

f´ormulas:

d := , s p+1 :=
as. Consideremos
| {z } | la segunda
{z etapa
} . cuando
? ?
1 1 x s1
2 2 x2 s2
3 3 x3 = s3
5. Segunda etapa: sustituci´on hacia4 atr´ 4 x4 s4
la matriz del sistema es triangular superior: 5

n n−1
d1 b 0 0 0 1

0 d b 0 0 5
5 0 0 d b 0 .
0 0 0 d b
0 0 0 0 d5 x5 s
5 5

Calculemos x , x ,...,x .
Escribimos de manera expl´ıcita la ´ultima ecuaci´on (que contiene x ) y despejamos
la inc´ognita x : es de x k+1

= s =⇒ x =
| {z } | {z } .
? ?

Escribimos de manera expl´ıcita la k-´esima ecuaci´on y despejamos la inc´ognita x k

expres´andola a trav´ :
| {z
 } =
=⇒x =
| {z } | {z } .

? ? ?

Programaci´on: Sistemas tridiagonales de ecuaciones lineales, p´agina 3 de 4

Programaci´on del algoritmo
6. Problema SolveTridiag. Escriba una funci´on que resuelva el sistema (1) y regrese
el vector x. Puede usar el siguiente esbozo (cambie . . . por las f´ormulas correctas):
Entrada: las listas a, b, c, r;
Variables locales: n, d, s, p, x, mu;
d := copia de a;
s := copia de r;
n := longitud de a;
Para p := de 1 hasta ...:
mu := ...;
d[p + 1] += mu * ...;
s[p + 1] += ...;
x := lista nula de longitud n;
x[n] := ...;
Para k desde ... hasta ...:
x[k] := ...;
Regresar x.

7. Prueba. El sistema de ecuaciones lineales

3 1 0 0 x1 5
x2
2 −1 3 0 −9
x3 =
0 2 1 −2 −7
>
0 0 3 2 x4 −1

tiene una soluci´on ´unica [1, 2,−3, 4] . Por lo tanto, si pongamos

a = el arreglo de n´umeros 3,−1, 1, 2,
b = el arreglo de n´umeros 1, 3,−2,
c = el arreglo de n´umeros 2, 2, 3,
r = el arreglo de n´umeros 5,−9,−7,−1,
y llamamos la funci´on SolveTridiag con argumentos a, b, c, r, entonces la funci´on debe
regresar el arreglo 1, 2,−3, 4.

8. N´umero de operaciones aritm´eticas. Calcule el n´umero de las operaciones de

multiplicaci´on y divisi´on en el algoritmo programado.
Primer m´etodo: calcule el n´umero de las operaciones de multiplicaci´on y divisi´on
dentro de cada ciclo y fuera de ciclos, luego transforme ciclos en sumas.
Segundo m´etodo: analice en cu´antas operaciones de multiplicaci´on y divisi´on parti-
cipa cada entrada de los arreglos a, b, c, r, d, s.

Programaci´on: Sistemas tridiagonales de ecuaciones lineales, p´agina 4 de 4