matlablinear-algebraeigenvectoreigenvalue
Finding the Largest Eigenvalue Using the Power method
For this problem, I have to take a large 100 by 100 matrix of randomly generated values and an initial x vector and try to obtain the largest absolute value of the eigenvalues and the associated convectors as well as the number of iterations.
The power method as described:
I have to find the absolute val of the largest eigenvalue, the corresponding eigenvector, and the number of iterations.
My code:
%% problem 2b: Power method
% code snippet from class generates A and x
nx = 10;
ex = ones(nx,1);
Dxx = spdiags([ex -2*ex ex], [-1 0 1], nx, nx);
A = kron(Dxx, speye(nx)) + kron(speye(nx), Dxx);
rng(2);
x = rand(nx*nx,1); % initial vector
yk = [] % stores yk values
count = 0; % keeps track of iterations
value = 1; % 1 to ensure while loop is entered
tolerance = 10^(-6); % tol
while (value >= tolerance)
yk = A*x; % yk = A*xk
xnext = yk/norm(yk); % Xk+1=yk/2norm(yk)
rk = dot(xnext,(A*xnext)); % rk = Xk+1 * (A*Xk+1)
count = count+1; % iterate count
value = norm(yk - rk*x); % update tolerance check
x = xnext;
end
value
x % final eigenvector
rk % the largest eignvalue in abs value
count % the number of iterations
According to the answers, my largest eigenvalue—rk—is correct, but the corresponding eigenvector and the number of iterations is incorrect. Can someone clarify this for me? The eigenvalue and the eigenvector agrees when I use:
[C, D] = eigs(A)
Solution
Are you sure? It looks correct to me.
When I produce C and D with eigs, I get:
>> [C, D] = eigs(A)
C =
0.0520 0.0170 0.0531 0.0158 -0.0358 -0.0144
-0.0788 -0.0433 -0.0894 -0.0327 0.0626 0.0277
0.0717 0.0801 0.0973 0.0510 -0.0741 -0.0387
-0.0437 -0.1180 -0.0743 -0.0694 0.0684 0.0466
0.0200 0.1424 0.0277 0.0855 -0.0486 -0.0507
-0.0200 -0.1424 0.0277 -0.0959 0.0217 0.0507
0.0437 0.1180 -0.0743 0.0974 0.0038 -0.0466
-0.0717 -0.0801 0.0973 -0.0876 -0.0204 0.0387
0.0788 0.0433 -0.0894 0.0664 0.0243 -0.0277
-0.0520 -0.0170 0.0531 -0.0358 -0.0158 0.0144
-0.0892 -0.0116 -0.0894 -0.0243 0.0664 0.0277
0.1308 0.0427 0.1504 0.0511 -0.1157 -0.0531
-0.1090 -0.0972 -0.1637 -0.0814 0.1359 0.0743
0.0494 0.1585 0.1250 0.1135 -0.1236 -0.0894
-0.0009 -0.1993 -0.0466 -0.1427 0.0849 0.0973
0.0009 0.1993 -0.0466 0.1627 -0.0333 -0.0973
-0.0494 -0.1585 0.1250 -0.1671 -0.0149 0.0894
0.1090 0.0972 -0.1637 0.1517 0.0456 -0.0743
-0.1308 -0.0427 0.1504 -0.1157 -0.0511 0.0531
0.0892 0.0116 -0.0894 0.0626 0.0327 -0.0277
0.1051 -0.0223 0.0973 0.0204 -0.0876 -0.0387
-0.1453 0.0142 -0.1637 -0.0456 0.1517 0.0743
0.0999 0.0326 0.1781 0.0777 -0.1760 -0.1038
-0.0060 -0.0973 -0.1360 -0.1151 0.1560 0.1250
-0.0674 0.1433 0.0507 0.1521 -0.1004 -0.1360
0.0674 -0.1433 0.0507 -0.1801 0.0282 0.1360
0.0060 0.0973 -0.1360 0.1902 0.0377 -0.1250
-0.0999 -0.0326 0.1781 -0.1760 -0.0777 0.1038
0.1453 -0.0142 -0.1637 0.1359 0.0814 -0.0743
-0.1051 0.0223 0.0973 -0.0741 -0.0510 0.0387
-0.1049 0.0695 -0.0743 -0.0038 0.0974 0.0466
0.1334 -0.0988 0.1250 0.0149 -0.1671 -0.0894
-0.0622 0.0750 -0.1360 -0.0377 0.1902 0.1250
-0.0626 -0.0205 0.1038 0.0714 -0.1617 -0.1504
0.1571 -0.0229 -0.0387 -0.1100 0.0926 0.1637
-0.1571 0.0229 -0.0387 0.1437 -0.0057 -0.1637
0.0626 0.0205 0.1038 -0.1617 -0.0714 0.1504
0.0622 -0.0750 -0.1360 0.1560 0.1151 -0.1250
-0.1334 0.0988 0.1250 -0.1236 -0.1135 0.0894
0.1049 -0.0695 -0.0743 0.0684 0.0694 -0.0466
0.1002 -0.1031 0.0277 -0.0217 -0.0959 -0.0507
-0.1184 0.1604 -0.0466 0.0333 0.1627 0.0973
0.0302 -0.1555 0.0507 -0.0282 -0.1801 -0.1360
0.1133 0.1112 -0.0387 0.0057 0.1437 0.1637
-0.2201 -0.0719 0.0144 0.0290 -0.0656 -0.1781
0.2201 0.0719 0.0144 -0.0656 -0.0290 0.1781
-0.1133 -0.1112 -0.0387 0.0926 0.1100 -0.1637
-0.0302 0.1555 0.0507 -0.1004 -0.1521 0.1360
0.1184 -0.1604 -0.0466 0.0849 0.1427 -0.0973
-0.1002 0.1031 0.0277 -0.0486 -0.0855 0.0507
-0.1002 0.1031 0.0277 0.0486 0.0855 0.0507
0.1184 -0.1604 -0.0466 -0.0849 -0.1427 -0.0973
-0.0302 0.1555 0.0507 0.1004 0.1521 0.1360
-0.1133 -0.1112 -0.0387 -0.0926 -0.1100 -0.1637
0.2201 0.0719 0.0144 0.0656 0.0290 0.1781
-0.2201 -0.0719 0.0144 -0.0290 0.0656 -0.1781
0.1133 0.1112 -0.0387 -0.0057 -0.1437 0.1637
0.0302 -0.1555 0.0507 0.0282 0.1801 -0.1360
-0.1184 0.1604 -0.0466 -0.0333 -0.1627 0.0973
0.1002 -0.1031 0.0277 0.0217 0.0959 -0.0507
0.1049 -0.0695 -0.0743 -0.0684 -0.0694 -0.0466
-0.1334 0.0988 0.1250 0.1236 0.1135 0.0894
0.0622 -0.0750 -0.1360 -0.1560 -0.1151 -0.1250
0.0626 0.0205 0.1038 0.1617 0.0714 0.1504
-0.1571 0.0229 -0.0387 -0.1437 0.0057 -0.1637
0.1571 -0.0229 -0.0387 0.1100 -0.0926 0.1637
-0.0626 -0.0205 0.1038 -0.0714 0.1617 -0.1504
-0.0622 0.0750 -0.1360 0.0377 -0.1902 0.1250
0.1334 -0.0988 0.1250 -0.0149 0.1671 -0.0894
-0.1049 0.0695 -0.0743 0.0038 -0.0974 0.0466
-0.1051 0.0223 0.0973 0.0741 0.0510 0.0387
0.1453 -0.0142 -0.1637 -0.1359 -0.0814 -0.0743
-0.0999 -0.0326 0.1781 0.1760 0.0777 0.1038
0.0060 0.0973 -0.1360 -0.1902 -0.0377 -0.1250
0.0674 -0.1433 0.0507 0.1801 -0.0282 0.1360
-0.0674 0.1433 0.0507 -0.1521 0.1004 -0.1360
-0.0060 -0.0973 -0.1360 0.1151 -0.1560 0.1250
0.0999 0.0326 0.1781 -0.0777 0.1760 -0.1038
-0.1453 0.0142 -0.1637 0.0456 -0.1517 0.0743
0.1051 -0.0223 0.0973 -0.0204 0.0876 -0.0387
0.0892 0.0116 -0.0894 -0.0626 -0.0327 -0.0277
-0.1308 -0.0427 0.1504 0.1157 0.0511 0.0531
0.1090 0.0972 -0.1637 -0.1517 -0.0456 -0.0743
-0.0494 -0.1585 0.1250 0.1671 0.0149 0.0894
0.0009 0.1993 -0.0466 -0.1627 0.0333 -0.0973
-0.0009 -0.1993 -0.0466 0.1427 -0.0849 0.0973
0.0494 0.1585 0.1250 -0.1135 0.1236 -0.0894
-0.1090 -0.0972 -0.1637 0.0814 -0.1359 0.0743
0.1308 0.0427 0.1504 -0.0511 0.1157 -0.0531
-0.0892 -0.0116 -0.0894 0.0243 -0.0664 0.0277
-0.0520 -0.0170 0.0531 0.0358 0.0158 0.0144
0.0788 0.0433 -0.0894 -0.0664 -0.0243 -0.0277
-0.0717 -0.0801 0.0973 0.0876 0.0204 0.0387
0.0437 0.1180 -0.0743 -0.0974 -0.0038 -0.0466
-0.0200 -0.1424 0.0277 0.0959 -0.0217 0.0507
0.0200 0.1424 0.0277 -0.0855 0.0486 -0.0507
-0.0437 -0.1180 -0.0743 0.0694 -0.0684 0.0466
0.0717 0.0801 0.0973 -0.0510 0.0741 -0.0387
-0.0788 -0.0433 -0.0894 0.0327 -0.0626 0.0277
0.0520 0.0170 0.0531 -0.0158 0.0358 -0.0144
D =
-7.2287 0 0 0 0 0
0 -7.2287 0 0 0 0
0 0 -7.3650 0 0 0
0 0 0 -7.6015 0 0
0 0 0 0 -7.6015 0
0 0 0 0 0 -7.8380
Also, rk from your Power Method gives:
>> rk
rk =
-7.8380
rk is the last eigenvalue produced by eigs, and that corresponds to the last eigenvector / last column in C. If we compare x and the last column of C, we get:
>> format long g;
>> [x C(:,6)]
ans =
-0.0144315780109194 -0.0144314970153476
0.0276939697943544 0.027693839969929
-0.0387127177669401 -0.0387125927117545
0.0465951447011548 0.0465950814247274
-0.0507026743311123 -0.050702713752288
0.0507025614842252 0.0507027137522879
-0.0465948419885827 -0.0465950814247267
0.0387123212977858 0.0387125927117535
-0.027693605444773 -0.027693839969928
0.0144313614593288 0.014431497015347
0.0276940018504475 0.0276938399699289
-0.0531443512380279 -0.053144089727102
0.0742891786790794 0.0742889213946561
-0.0894154487195339 -0.0894153064640425
0.0972977421934561 0.0972977951770151
-0.0972975256418808 -0.097297795177015
0.0894148678184032 0.0894153064640416
-0.0742884178603978 -0.074288921394655
0.0531436520563511 0.0531440897271008
-0.0276935862910177 -0.0276938399699281
-0.0387128332167354 -0.0387125927117545
0.074289314234918 0.074288921394656
-0.103847201265651 -0.10384680347939
0.124991879901604 0.124991635146944
-0.13601036376947 -0.136010387888769
0.136010061056953 0.136010387888769
-0.124991067873139 -0.124991635146943
0.103846137734539 0.103846803479389
-0.0742883368647708 -0.0742889213946555
0.0387122523156699 0.038712592711754
0.0465953928808543 0.0465950814247275
-0.0894158214731441 -0.0894153064640426
0.124992172891791 0.124991635146944
-0.150442250463584 -0.150441884904116
0.163704276053648 0.163704227858698
-0.163703911704186 -0.163704227858698
0.150441273093578 0.150441884904117
-0.124990892809312 -0.124991635146944
0.0894146450953342 0.0894153064640427
-0.0465946936993567 -0.0465950814247274
-0.0507030799451604 -0.0507027137522887
0.0972984079372535 0.0972977951770161
-0.136011046217971 -0.13601038788877
0.163704713723789 0.163704227858698
-0.17813587316184 -0.178135724874045
0.178135476692881 0.178135724874045
-0.163703650193004 -0.163704227858699
0.136009653288871 0.13601038788877
-0.0972971278549844 -0.0972977951770159
0.0507023191267988 0.0507027137522887
0.0507031083768884 0.0507027137522886
-0.0972984624973554 -0.097297795177016
0.136011122486338 0.13601038788877
-0.16370480552164 -0.163704227858699
0.17813597305228 0.178135724874046
-0.178135576583388 -0.178135724874046
0.163703741991037 0.163704227858699
-0.136009729557476 -0.13601038788877
0.0972971824153056 0.0972977951770162
-0.0507023475586572 -0.0507027137522885
-0.0465954691491656 -0.0465950814247277
0.089415967831003 0.0894153064640427
-0.124992377482224 -0.124991635146945
0.150442496711966 0.150441884904117
-0.163704544010458 -0.163704227858698
0.163704179661178 0.163704227858698
-0.150441519342448 -0.150441884904117
0.124991097400385 0.124991635146944
-0.0894147914537812 -0.0894153064640427
0.0465947699680175 0.0465950814247277
0.03871293310698 0.0387125927117539
-0.0742895059229478 -0.0742889213946556
0.103847469222133 0.10384680347939
-0.124992202418397 -0.124991635146944
0.136010714718256 0.13601038788877
-0.136010412005978 -0.136010387888769
0.124991390390572 0.124991635146944
-0.103846405691859 -0.103846803479389
0.0742885285535708 0.0742889213946558
-0.0387123522063723 -0.0387125927117542
-0.0276940936481785 -0.0276938399699281
0.0531445273966335 0.0531440897271008
-0.0742894249273207 -0.0742889213946552
0.089415745107934 0.0894153064640417
-0.097298064710459 -0.0972977951770146
0.097297848159103 0.0972977951770148
-0.0894151642073914 -0.0894153064640414
0.0742886641094094 0.0742889213946553
-0.0531438282156646 -0.053144089727101
0.0276936780891695 0.0276938399699285
0.0144316325710059 0.0144314970153468
-0.0276940744944232 -0.0276938399699279
0.0387128641248642 0.0387125927117535
-0.0465953208599396 -0.0465950814247267
0.0507028660194621 0.0507027137522877
-0.0507027531727052 -0.0507027137522875
0.046595018147717 0.0465950814247267
-0.0387124676561676 -0.0387125927117538
0.0276937101452626 0.0276938399699282
-0.0144314160196653 -0.0144314970153473
Also looks fine. Shall we do another test? Let's find the maximum deviation between x and the last eigenvector of C:
>> max(abs(x - C(:,6)))
ans =
7.42337632364531e-07
That also agrees with your tolerance you specified at the beginning, where it's < 1e-6.
As such, I don't see anything wrong with your code. You should probably double-check your theory on the Power Method because it produces what you expect.
- Distinguish between two maximum values in a column with Power Query
- Power Query Conditional JOIN - JOIN with WHERE clause
- Calculate combinations for a range of text values in excel
- How to update a column's values in Power BI M Language
- What's the difference between DAX and Power Query (or M)?
- Sorting issue when consolidating monthly data into a year to date file. Using query, sorting by day, time, and letter
- Power Query `List.Generate` runs too slow
- Custom Colum based on specific dates in powerquery
- How do I properly use table.group in a PowerQuery query to dynamically summarize different rows and columns?
- Excel Power Query syntax issue transform multiple columns of records
- How to capitalize only first letter of a sentence
- Power Query Import For Power BI with group by on SelectRows
- Get data from config table cell when loading data source with power query
- Translate Excel Formula into Power Query
- Counting matching pairs of letters in lists of bigrams in Power Query M
- Bigrams of a string in Power Query M
- Power Query code to refer to another query (and how buffering works)
- M code for the equivalent of of Left (string, len(string)-11)
- How to add a missing column to the Transform Sample File
- How to add or insert ' (single quotes) for every string in a list in which strings are separated by commas in Power Query
- Power BI M code Split column from Lowercase to Uppercase won't include diacritics (accents)
- M Code(Power Query) to Remove Empty columns that runs fast
- How to find the value with date closest to another date
- Error when build AOSP 14 - internal error: undefined variable CTS_TEST_SUITES_DEFAULT
- Call a table using a dynamic identifier
- Problem getting the value from a cell using M in excel
- How to rename columns based on the data within them in Power Query M?
- Power Query return a field name based on parameter
- Power Query: after combining 2 tables got something strange
- Token Literal Expected Error in Power Query M Code using try and List.MatchesAny