Численні методи і LU (АСД)

Математические алгоритмы

Для определения (построения) 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

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

10