PDF de programación - Técnicas de Cálculo para Sistemas de Ecuaciones, Programación Lineal y Programación Entera

Técnicas de Cálculo

para Sistemas de Ecuaciones,

Programaci ón Lineal y Programaci ón

Entera

Códigos en FORTRAN y C con Aplicaciones de Sistemas de

Energía Eléctrica

José Luis de la Fuente O’Connor

Profesor Titular

Universidad Politécnica de Madrid

Escuela Técnica Superior de Ingenieros Industriales

A mi familia.

V

Índice General

Índice General
Índice de Figuras
Índice de Tablas
Prefacio
I Sistemas de ecuaciones

VII
XXIII
XXV
XXIX
1

Capítulo 1. M ÉTODOS DIRECTOS DE SOLUCI ÓN DE SISTEMAS DE ECUACIONES

LINEALES
1.1 Planteamiento del problema a resolver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Eliminación de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Pivotación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.2 Número de operaciones aritméticas del método . . . . . . . . . . . . . . . . . . . .
1.3 Método de Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Descomposición o factorización LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Métodos directos para la obtención de factorizaciones LU . . . . . . . . . . . .
1.4.1.1 Método de Crout. Versión LU1 . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1.2 Método de Crout. Versión L1U . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1.3 Método de Doolittle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Factorización de matrices simétricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1 Factorización LDLT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2 Factorización de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.3 Matrices simétricas semidefinidas positivas . . . . . . . . . . . . . . . . . . . . . . .
1.5.3.1 Pivotación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.4 Matrices simétricas indefinidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.4.1 El método de Parlett y Reid . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.4.2 El método de Aasen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.4.3 Factorización de pivotación diagonal . . . . . . . . . . . . . . . . . . . . .
El método de Bunch y Kaufman . . . . . . . . . . . . . . . . .
1.6 Condicionamiento de sistemas de ecuaciones lineales . . . . . . . . . . . . . . . . . . . . .
1.7 Mínimos cuadrados lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7.1 Fundamentos teóricos del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7.1.1 Descomposición en valores singulares . . . . . . . . . . . . . . . . . . . .
Sistemas incompatibles. Ecuaciones normales . . . . . . . . . . . . . .
1.7.1.2
1.7.1.3
Sistemas indeterminados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.5.4.3.1

3
4
7
14
20
23
24
29
29
34
36
39
40
41
46
48
48
50
53
59
60
66
73
74
74
79
81

VII

VIII

Índice General

1.7.2 Resolución numérica del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7.2.1 Método de Gram-Schmidt . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7.2.2 Factorización QR o triangularización ortogonal. Transfor-

maciones ortogonales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7.2.2.1 Transformaciones de Householder . . . . . . . . . . . . . . . .

1.7.2.2.1.1

1.7.2.2.1.2

1.7.2.2.1.3

Resolución numérica de Ax = b, Am×n,
m > n y rango completo . . . . . . . . . . . . . . . . . .
Resolución numérica de Ax = b, Am×n,
n > m y rango completo . . . . . . . . . . . . . . . . . .
Resolución numérica de Ax = b, Am×n,
m > n ó m < n y rango incompleto . . . . . . . . .

81
83

88
90

94

98

98
1.7.2.2.2 Transformaciones de Givens . . . . . . . . . . . . . . . . . . . . 105
1.7.2.2.3 Transformaciones rápidas de Givens . . . . . . . . . . . . . . 110
1.7.3 Descomposición numérica en valores singulares. Método de Golub-Reinsch 115
1.8 El problema generalizado de mínimos cuadrados . . . . . . . . . . . . . . . . . . . . . . . . . 128
1.9 Mínimos cuadrados lineales con restricciones lineales . . . . . . . . . . . . . . . . . . . . . 131
1.9.1 Resolución numérica del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
1.9.1.1 Método de eliminación directa . . . . . . . . . . . . . . . . . . . . . . . . . . 132
1.9.1.2 Método de la base del subespacio núcleo de la matriz de

restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
1.9.1.3 Método de la ponderación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

Capítulo 2. M ÉTODOS ITERATIVOS DE SOLUCI ÓN DE SISTEMAS DE ECUACIONES

LINEALES
143
2.1 Método de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
2.2 Método de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
2.3 Convergencia de los métodos de Jacobi y Gauss-Seidel . . . . . . . . . . . . . . . . . . . . 152
2.3.1 Matrices generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
2.3.2 Matriz de diagonal dominante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
2.3.3 Matriz simétrica definida positiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
2.4 Métodos de relajación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
2.4.1 Convergencia del método SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
2.4.2 Método SSOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
2.5 Métodos de minimización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
2.5.1 Direcciones de descenso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
2.5.1.1 Relajación en una variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
2.5.1.2 Relajación SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
2.5.1.3 Máxima pendiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
2.5.2 Direcciones de descenso conjugadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
2.5.2.1 Determinación de direcciones conjugadas . . . . . . . . . . . . . . . . . 179
2.5.2.2 Determinación de direcciones conjugadas. Método de los

gradientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
2.5.2.2.1 Convergencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
2.5.2.2.2

Interpretación geométrica del método de los gra-
dientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

Índice General

IX

2.5.2.2.3

Implementación práctica del método de los gra-
dientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

2.5.2.2.4 Método de los gradientes conjugados con precon-

dicionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
2.6 Comparación numérica de los algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
2.7 Mínimos cuadrados y métodos iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
2.7.1 Método de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
2.7.2 Método de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
2.7.3 Método de relajación SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
2.7.4 Método de los gradientes conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

Capítulo 3. SISTEMAS DE ECUACIONES LINEALES DE MATRIZ DE COEFICIENTES

3.2.3

DISPERSA
201
3.1 Almacenamiento en ordenador de matrices dispersas . . . . . . . . . . . . . . . . . . . . . 202
3.1.1 Almacenamiento por coordenadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
3.1.2 Almacenamiento por filas o columnas . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
3.1.3 Almacenamiento por perfil o envolvente . . . . . . . . . . . . . . . . . . . . . . . . . . 204
3.1.4 Almacenamiento por listas encadenadas . . . . . . . . . . . . . . . . . . . . . . . . . . 207
3.2 Operaciones algebraicas elementales con matrices dispersas . . . . . . . . . . . . . . . . 208
3.2.1 Producto interior de dos vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
3.2.2 Multiplicación de matrices por vectores . . . . . . . . . . . . . . . . . . . . . . . . . . 210
3.2.2.1 Multiplicación de una matriz por un vector . . . . . . . . . . . . . . . 210
3.2.2.2 Multiplicación de un vector por una matriz . . . . . . . . . . . . . . . 210
Suma de matrices dispersas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
Suma o resta simbólica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
3.2.3.1
3.2.3.2
Suma o resta numérica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
3.2.4 Mul