Eigenvalue Code

[azizcoktu]

Write your question here.
Hello. I have a code here which takes a matrix in a txt file as input and by using power iteration method, householder transform and deflation method to calculate the largest eigenvalue, its eigenvector and the second dominant eigenvalue. My code works well normally. But with some matrices it does not work. As I can see, matrices with eigenvalues of same magnitude with negative sign are not computed. Can you please help me find what is wrong ?

https://repl.it/repls/FixedGrayBooleanvalue

code is here but since it is a bit long I couldnot be able to post it hereç


Thanks.

[malibor]

Just a hint, some people don't click on links with not so well known domains.
You may want to re-link a zip file to ex. tinyupload.com, one drive, google drive or something like that.

[azizcoktu]

thank you. I will do that :)

[Ganado]

Sorry but repl.it is pretty well known.

Aziz, can you show example input that produces a wrong result?

[azizcoktu]

1 5
3 -1

I figured out that here

double dominant_eigenvalue (int row_number, double arr[], double vec_x[], double tolerance)
{
	double norm, eigen_value = -1 ; // two doubles namely norm and eigen_value are defined and eigen_value is initialized to "-1" since all the eigenvalues we get are
	// the absolute values of the real eigenvalues.
	double prev_vec[row_number] ;
	for (int i = 0; i < row_number ; i ++) // a for loop created to assign the values of arbitrary vector vec_x.
	{ // for loop starts.
		if (i %2 == 1) // if index is odd, the value "1" is assigned.
			vec_x[i] = 1 ;
		else // if index is even, the value "0.3" is assigned.
			vec_x[i] = 0.3 ;
	} // end of for loop
	while (true) //  a while loop is created to multiply the matrix and the vector until the absolute value of the difference of norm and eigen_value is smaller than
	// the tolerance value.
	{ // while loop starts
		for(int i = 0; i < row_number; i++)
		{
			prev_vec[i] = vec_x[i] ;
		}
		arr_vec_product (row_number, arr, vec_x) ; // matrix and the arbitrary vector are multiplied as A.x
		norm = inf_norm (row_number,vec_x) ; // infinity norm of the resultant vector vec_x is assigned to the variable norm.
		div_by_scalar(row_number, norm, vec_x) ; // vector is divided by its infinity norm.
		if (abs(norm-eigen_value) < tolerance) // if the absolute value of the difference of the norm and eigen_value is smaller than the tolerance following code block works.
		{ // if statement starts
		cout << "SUCCESS DOM_EIG\n" ;
			if(is_negative(row_number,vec_x,prev_vec))
				eigen_value = -1*norm ;
			else
				eigen_value = norm ;
			break ; // loop is broken.
		} // end of if statement.
		else // if the difference is greater than the tolerance, then following code block works and loop continues to work.
			eigen_value = norm ; // norm is assigned to eigen_value.
	} // end of while loop.
	return eigen_value ; // eigen_value is returned.
} // end of the dominant_eigenvalue function.

it is having an infinite loop. Thank you Ganado.

[azizcoktu]

But i dont know how to figure it out.

[lastchance]

The power method alone won't work if two eigenvalues have the same magnitude. Here, the eigenvalues are 4 and -4, so they have equal magnitude and neither will dominate when you repeatedly multiply by the matrix.

Suppose that your eigenvectors were v and w and that your initial guess is written in terms of them as basis vectors:
x = av + bw
Then, once you've multiplied by A some n times you will have
Aⁿx = 4ⁿav + (-4)ⁿbw
This is never going to isolate one eigenvalue over the other.

What you can do is called shifting. If A has eigenvalues λ_i, then A-tI has eigenvalues λ_i-t. So, if you used t=-1 in this instance, A+I would have eigenvalues 5 and -3; the power method would then pick out the 5; then correct by adding back -1 to get 4.



You also can't guarantee real eigenvalues, but that's another problem.

[azizcoktu]

So there is nothing wrong with the code. Thank you very much lastchance :).
I am very grateful and happy now :)