Finding the matrix eigenvalues using QR algorithm
Here’s an example Java program that uses the QR algorithm to find the eigenvalues of a matrix:
import java.util.Arrays;
public class MatrixEigenvalues {
// Helper function to calculate the dot product of two vectors
private static double dotProduct(double[] v1, double[] v2) {
double result = 0.0;
for (int i = 0; i < v1.length; i++) {
result += v1[i] * v2[i];
}
return result;
}
// Helper function to multiply a matrix with a vector
private static double[] matrixVectorMultiply(double[][] matrix, double[] vector) {
int m = matrix.length;
int n = matrix[0].length;
double[] result = new double[m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i] += matrix[i][j] * vector[j];
}
}
return result;
}
// Helper function to calculate the Euclidean norm of a vector
private static double euclideanNorm(double[] vector) {
double sum = 0.0;
for (double value : vector) {
sum += value * value;
}
return Math.sqrt(sum);
}
// Helper function to calculate the transpose of a matrix
private static double[][] transpose(double[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
double[][] result = new double[n][m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[j][i] = matrix[i][j];
}
}
return result;
}
// Helper function to calculate the QR decomposition of a matrix
private static void qrDecomposition(double[][] matrix, double[][] q, double[][] r) {
int m = matrix.length;
int n = matrix[0].length;
double[][] a = new double[m][n];
double[][] qTemp = new double[m][n];
double[][] rTemp = new double[n][n];
// Copy the input matrix into a temporary matrix
for (int i = 0; i < m; i++) {
System.arraycopy(matrix[i], 0, a[i], 0, n);
}
// Perform QR decomposition using Gram-Schmidt process
for (int j = 0; j < n; j++) {
double[] v = new double[m];
for (int i = 0; i < m; i++) {
v[i] = a[i][j];
}
for (int k = 0; k < j; k++) {
double[] qk = qTemp[k];
double dot = dotProduct(qk, v);
for (int i = 0; i < m; i++) {
v[i] -= dot * qk[i];
}
}
double norm = euclideanNorm(v);
for (int i = 0; i < m; i++) {
qTemp[j][i] = v[i] / norm;
}
}
// Calculate the R matrix
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
rTemp[i][j] = dotProduct(qTemp[j], a[i]);
}
}
// Copy the Q and R matrices into the output arrays
for (int i = 0; i < m; i++) {
System.arraycopy(qTemp[i], 0, q[i], 0, n);
}
for (int i = 0; i < n; i++) {
System.arraycopy(rTemp[i], i, r[i], i, n - i);
}
}
// Helper function to check if a matrix is upper triangular
private static boolean isUpperTriangular(double[][] matrix) {
int n = matrix.length;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (Math.abs(matrix[i][j]) > 1e-8) {
return false;
}
}
}
return true;
}
// Main function to calculate eigenvalues using QR algorithm
public static double[] findEigenvalues(double[][] matrix, int maxIterations) {
int n = matrix.length;
double[][] q = new double[n][n];
double[][] r = new double[n][n];
// Initialize the Q matrix as the identity matrix
for (int i = 0; i < n; i++) {
q[i][i] = 1.0;
}
// Apply the QR algorithm
for (int i = 0; i < maxIterations; i++) {
qrDecomposition(matrix, q, r);
matrix = transpose(r);
if (isUpperTriangular(matrix)) {
break;
}
}
// Extract the eigenvalues from the diagonal of the upper triangular matrix
double[] eigenvalues = new double[n];
for (int i = 0; i < n; i++) {
eigenvalues[i] = matrix[i][i];
}
return eigenvalues;
}
// Test the program
public static void main(String[] args) {
double[][] matrix = {
{ 6, -2, 1 },
{ -2, 3, -1 },
{ 1, -1, 1 }
};
int maxIterations = 100;
double[] eigenvalues = findEigenvalues(matrix, maxIterations);
System.out.println("Eigenvalues: " + Arrays.toString(eigenvalues));
}
}
In this program, we define several helper functions for matrix and vector operations. The `qrDecomposition` function performs the QR decomposition of a matrix using the Gram-Schmidt process. The `isUpperTriangular` function checks if a matrix is upper triangular. The `findEigenvalues` function applies the QR algorithm to find the eigenvalues of a matrix.
In the `main` method, we define a test matrix and call the `findEigenvalues` function to calculate its eigenvalues. The result is then printed to the console.
Please note that the QR algorithm is an iterative method, and the number of iterations required to converge to the eigenvalues depends on the matrix and its size. The `maxIterations` parameter in the `findEigenvalues` function controls the maximum number of iterations allowed. You may need to adjust this parameter based on your specific use case.