Численні методи і LU (АСД)
.pdfМатематические алгоритмы
Для определения (построения) LU-разложения используется
метод исключения Гаусса:
1.Первая переменная удаляется из всех уравнений путем вычитания этих уравнений из первого и умножения на соответствующий коэффициент.
2.Эти действия повторяются для всех уравнений путем последовательного исключения переменных.
В результате получим верхне-треугольную матрицу (U) и единичную нижне-треугольную матрицу (L) из коэффициентов, учавствовавших в процессе исключения.
1
Математические алгоритмы
Например,
2
Математические алгоритмы
Используя алгоритм Штрассена для перемножения матриц, представив результирующую матрицу в виде:
Элементы, на которые в процессе разложения выполняется деление, называются ведущими.
Матрица перестановки используется для того, чтобы избежать деления на ноль. Этот процесс называется
выбором ведущего элемента.
3
Математические алгоритмы
4
Математические алгоритмы
public static void LU(int A[][], int L[][], int U[][]) { int n = A.length;
for(int i=0; i<n; i++) { U[i][i] = A[i][i];
for(int j=i+1; j<n; j++) { L[j][i] = A[j][i]/U[i][i]; U[i][j] = A[i][j];
}
for(int j=i+1; j<n; j++) for(int k=i+1; k<n; k++)
A[j][k] = A[j][k] - L[j][i]*U[i][k];
}
}
5
Математические алгоритмы
6
Математические алгоритмы
public static int[] LUP(double A[][]) { int n = A.length, m;
int P[] = new int [A.length]; for(int i=0; i<n; i++)
P[i] = i;
for(int k=0; k<n; k++) { double pp = 0.0;
m = k;
for(int i=k; i<n; i++)
if (Math.abs(A[i][k]) > pp) { pp = Math.abs(A[i][k]); m = i;
}
7
|
Математические алгоритмы |
|
int a = P[k]; |
P[k] = P[m]; |
P[m] = a; |
for(int i=0; i<n; i++) { double b = A[k][i]; A[k][i] = A[m][i]; A[m][i] = b;
}
for(int i=k+1; i<n; i++) { A[i][k] = A[i][k]/A[k][k]; for(int j=k+1; j<n; j++)
A[i][j] = A[i][j] - A[i][k]*A[k][j];
} }
return P;
}
8
Математические алгоритмы
public static double[] solve(double A[][], int P[], double B[]) { double y[] = new double [A.length],
x[] = new double [A.length]; for(int i=0; i<y.length; i++) {
for(int j=0; j<=(i-1); j++) y[i] += A[i][j]*y[j];
y[i] = B[P[i]] - y[i];
}
for(int i=y.length-1; i>=0; i--) { double s = 0.0;
for(int j=i+1; j<x.length; j++) s += A[i][j]*x[j];
x[i] = (y[i] - s)/A[i][i];
}
return x;
} |
9 |
|
|
Математические алгоритмы |
|||
System: |
|
|
|
|
|
2.0x1 |
0.0x2 |
2.0x3 |
0.6x4 |
= |
3.0 |
3.0x1 |
3.0x2 |
4.0x3 |
-2.0x4 = |
7.0 |
|
5.0x1 |
5.0x2 |
4.0x3 |
2.0x4 |
= |
8.0 |
-1.0x1 |
-2.0x2 3.4x3 |
-1.0x4 = |
5.0 |
||
X: |
|
|
|
|
|
-0.243 |
0.423 |
1.695 |
0.16 |
|
|
10