diff options
Diffstat (limited to 'Numerical_Methods_Principles_by_Analysis/11-Eigenvalues_and_Eigenvectors.ipynb')
-rw-r--r-- | Numerical_Methods_Principles_by_Analysis/11-Eigenvalues_and_Eigenvectors.ipynb | 786 |
1 files changed, 786 insertions, 0 deletions
diff --git a/Numerical_Methods_Principles_by_Analysis/11-Eigenvalues_and_Eigenvectors.ipynb b/Numerical_Methods_Principles_by_Analysis/11-Eigenvalues_and_Eigenvectors.ipynb new file mode 100644 index 0000000..d2208de --- /dev/null +++ b/Numerical_Methods_Principles_by_Analysis/11-Eigenvalues_and_Eigenvectors.ipynb @@ -0,0 +1,786 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 11: Eigenvalues and Eigenvectors" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.10: LU_Method.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.10\n", +"//LU Method\n", +"//Page no. 363\n", +"clc;close;clear;\n", +"\n", +"A=[120,80,40,-16;80,120,16,-40;40,16,120,-80;-16,-40,-80,120];\n", +"disp(A,'A =')\n", +"L=eye(4,4);\n", +"for l=1:20\n", +"for j=1:4\n", +" for i=1:j\n", +" k=0\n", +" for p=1:i-1\n", +" k=k-A(i,p)*A(p,j)\n", +" end\n", +" A(i,j)=A(i,j)+k\n", +" end\n", +" for i=j+1:4\n", +" k=0;\n", +" for p=1:j-1\n", +" k=k-A(i,p)*A(p,j)\n", +" end\n", +" A(i,j)=(A(i,j)+k)/A(j,j) \n", +" end\n", +"end\n", +"disp(A,'Modified A = ')\n", +" for i=1:4\n", +" for j=1:4\n", +" if i>j then\n", +" L(i,j)=A(i,j)\n", +" else\n", +" U(i,j)=A(i,j)\n", +" end\n", +" end\n", +"end\n", +"disp(U,'U =',L,'L =')\n", +"A=U*L;\n", +"printf('\n\nAfter %i iterations, matrix A =\n\n',l)\n", +"for i=1:4\n", +" for j=1:4\n", +" printf(' %.2f\t',A(i,j))\n", +" end\n", +" printf('\n')\n", +"end\n", +"end\n", +"printf('\n\nTherefore the eigenvalues are the diagonal elements f the transformed triangular matrix are:\n\n')\n", +"for i=1:4\n", +" printf(' %.2f,',A(i,i))\n", +"end" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.11: Generalized_Eigenvalue_Problem.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.11\n", +"//Generalized Eigenvalue Problem\n", +"//Page no. 365\n", +"clc;close;clear;\n", +"\n", +"A=[1,1,0.5;1,1,0.25;0.5,0.25,2]\n", +"B=[2,2,2;2,5,5;2,5,11]\n", +"disp(B,'B =',A,'A =')\n", +"for i=1:3\n", +" G(i,i)=sqrt(B(i,i))\n", +"end\n", +"G=[B;eye(3,3)];\n", +"\n", +"//transformation to frobenius matrix\n", +"for k=3:-1:2\n", +" g(k)=0;\n", +" for j=1:k-1\n", +" if(g(k)<G(k,j))\n", +" g(k)=G(k,j)\n", +" p=j;\n", +" end\n", +" end\n", +" if(g(k)~=0)\n", +" for j=1:3\n", +" r(1,j)=G(k,j)\n", +" end\n", +" for i=1:6\n", +" G(i,k-1)=G(i,k-1)/g(k)\n", +" end\n", +" for j=1:3\n", +" if(j~=k-1)\n", +" l=G(k,j)\n", +" for i=1:6\n", +" G(i,j)=G(i,j)-l*G(i,k-1)\n", +" end\n", +" end\n", +" end\n", +" end\n", +" for j=1:3\n", +" for i=1:3\n", +" c(i,1)=G(i,j)\n", +" end\n", +" G(k-1,j)=0\n", +" for i=1:3\n", +" G(k-1,j)=G(k-1,j)+r(1,i)*c(i,1)\n", +" end\n", +" end\n", +"end\n", +"\n", +"//partition g\n", +"for i=4:6\n", +" for j=1:3\n", +" T(i-3,j)=G(i,j)\n", +" end\n", +"end\n", +"\n", +"//eigenvalues computation\n", +"p=poly(B,'x')\n", +"a=roots(p)\n", +"printf('\n\nDiagonalized Matrix B = \n\n')\n", +"for i=1:3\n", +" for j=1:3\n", +" if i~=j then\n", +" B(i,j)=0\n", +" else\n", +" B(i,j)=a(i)\n", +" end\n", +" end\n", +"end\n", +"disp(B)\n", +"//eigenvectors computation\n", +"for k=1:3\n", +" m=2\n", +" for l=1:3\n", +" y(l,k)=a(k)^(m)\n", +" m=m-1;\n", +" end\n", +"end\n", +"printf('\n\n')\n", +"\n", +"\n", +"for k=1:3\n", +" for l=1:3\n", +" y1(l,1)=y(l,1)\n", +" y2(l,1)=y(l,2)\n", +" y3(l,1)=y(l,3)\n", +" end\n", +" x1=T*y3;\n", +" x2=T*y2;\n", +" x3=T*y1;\n", +"end\n", +"printf('\n\nEigenvectors of B are :\n\n')\n", +"for i=1:3\n", +" printf('|%.5f|\t\t|%.5f|\t\t|%.5f|',x3(i,1),x2(i,1),x1(i,1))\n", +" printf('\n')\n", +"end\n", +"x=[x3,x2,x1]\n", +"\n", +"\n", +"\n", +"\n", +"\n", +"B=[2,2,2;2,5,5;2,5,11]\n", +"G=0\n", +"for i=1:3\n", +" for j=1:3\n", +" if i==j then\n", +" G(i,j)=sqrt(B(i,j))\n", +" else\n", +" G(i,j)=0;\n", +" end\n", +" end\n", +"end\n", +"\n", +"B=inv(G)*x'*A*x*inv(G)\n", +"disp(B,'Eigenvectors of A =')\n", +"\n", +"printf('\n\n\nNote : Computation Error in book in caculation of eigenvector of B thus for A')\n", +"" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.1: Eigenvalues_and_Eigenvectors.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.1\n", +"//Eigenvalues and Eigenvectors\n", +"//Page no. 333\n", +"clc;clear;close;\n", +"\n", +"A1=[0.6;0.2];A2=[-0.2;0.6];A3=[-0.6;-0.2];A4=[0.2;-0.6];\n", +"T=[1.1,-0.3;-0.3,1.9];\n", +"B1=T*A1;B2=T*A2;B3=T*A3;B4=T*A4;\n", +"disp(B4,B3,B2,B1,'The transformed vectors are :')\n", +"disp('These points lie on the ellipse:')\n", +"printf(' 2 2\n(x-3y)+(3x+y)\n------ ------\n 16 4\n\n')\n", +"A5=[0;2/sqrt(10)];\n", +"disp('The vector (0,2/10^(1/2)) lies on the circle:')\n", +"printf(' 2 2\nx + y = 4\n -\n 10\n\n')\n", +"B5=T*A5;\n", +"disp('Also lies on the same ellipse',B5)\n", +"printf('\n\nWe can see that there is a linear relationship between the first 4 vectors and their respective transformend vectors through the scalars known as eigenvectors and eigenvalues respectively')" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.2: Leverriers_Method.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.2\n", +"//Leverrier's Method\n", +"//Page no. 337\n", +"clc;close;clear;\n", +"\n", +"A=[2,2,2;2,5,5;2,5,1];\n", +"A1=A;\n", +"C(1)=0;\n", +" for j=1:3\n", +" for k=1:3\n", +" if(j==k)\n", +" C(1)=C(1)+A1(j,k)\n", +" end\n", +" end\n", +" end\n", +" disp(A,'A=')\n", +" disp(A1,'A1=')\n", +" printf('\nC1=')\n", +" disp(C(1));\n", +"for i=2:3\n", +" A2=A*(A1-C(i-1)*eye(3,3));\n", +" printf('\n\n\nA%i=',i)\n", +" disp(A2);\n", +" C(i)=0;\n", +" for j=1:3\n", +" for k=1:3\n", +" if(j==k)\n", +" C(i)=C(i)+A2(j,k)/i\n", +" end\n", +" end\n", +" end\n", +" printf('\nC%i=',i)\n", +" disp(C(i))\n", +" A1=A2;\n", +"end\n", +"printf('\n\n\nTherefore the characteristic polynomial is:\n 3 2\nx - %ix - %ix %i = 0',C(1),C(2),C(3))\n", +"\n", +"//verification\n", +"printf('\n\nVerification:')\n", +"s=poly(0,'s');\n", +"p=poly(A,'x');\n", +"A=A-eye(3,3)*%s;\n", +"disp(p,'=',A)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.3: Danilevsky_Method.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.3\n", +"//Danilevsky Method\n", +"//Page no. 341\n", +"clc;close;clear;\n", +"\n", +"A=[-1,0,0;1,-2,3;0,2,-3];\n", +"G=[A;eye(3,3)];\n", +"disp(G);\n", +"//transformation to frobenius matrix\n", +"for k=3:-1:2\n", +" g(k)=0;\n", +" for j=1:k-1\n", +" if(g(k)<G(k,j))\n", +" g(k)=G(k,j)\n", +" p=j;\n", +" end\n", +" end\n", +" if(g(k)~=0)\n", +" for j=1:3\n", +" r(1,j)=G(k,j)\n", +" end\n", +" for i=1:6\n", +" G(i,k-1)=G(i,k-1)/g(k)\n", +" end\n", +" disp(G)\n", +" for j=1:3\n", +" if(j~=k-1)\n", +" l=G(k,j)\n", +" for i=1:6\n", +" G(i,j)=G(i,j)-l*G(i,k-1)\n", +" end\n", +" end\n", +" end\n", +" disp(G)\n", +" end\n", +" for j=1:3\n", +" for i=1:3\n", +" c(i,1)=G(i,j)\n", +" end\n", +" G(k-1,j)=0\n", +" for i=1:3\n", +" G(k-1,j)=G(k-1,j)+r(1,i)*c(i,1)\n", +" end\n", +" end\n", +" disp(G)\n", +"end\n", +"\n", +"//partition g\n", +"for i=4:6\n", +" for j=1:3\n", +" T(i-3,j)=G(i,j)\n", +" end\n", +"end\n", +"disp(T,'T=')\n", +"\n", +"//eigenvalues computation\n", +"printf('\n\n\nCharateristic polynomial:')\n", +"p=poly(A,'x')\n", +"disp(p)\n", +"printf('\n\n\nEigenvalues:')\n", +"a=roots(p)\n", +"disp(a')\n", +"//eigenvectors computation\n", +"for k=1:3\n", +" m=2\n", +" for l=1:3\n", +" y(l,k)=a(k,1)^(m)\n", +" m=m-1;\n", +" end\n", +"end\n", +"printf('\n\n')\n", +"disp(y,'y=')\n", +"\n", +"//eigenvector computation\n", +"\n", +"for k=1:3\n", +" for l=1:3\n", +" y1(l,1)=y(l,1)\n", +" y2(l,1)=y(l,2)\n", +" y3(l,1)=y(l,3)\n", +" end\n", +" x1=T*y3;\n", +" x2=T*y2;\n", +" x3=T*y1;\n", +"end\n", +"printf('\n\nEigenvectors :\n')\n", +"for i=1:3\n", +" printf('|%.1f|\t\t|%.1f|\t\t|%.1f|',x1(i,1),x2(i,1),x3(i,1))\n", +" printf('\n')\n", +"end" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.4: Power_Method.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.4\n", +"//Power Method\n", +"//Page no. 345\n", +"clc;close;clear;\n", +"\n", +"A=[1,2;3,4];\n", +"e=0.001;\n", +"q0=[1;1];\n", +"for i=1:5\n", +" q1=A*q0;\n", +" a=max(q1)\n", +" for j=1:2\n", +" q2(j)=q1(j)/a;\n", +" end\n", +" printf('\nq(%i) = %.4f a = %.4f Scaled q(%i) = %.4f\n %.4f %i\n\n',i,q1(1),a,i,q2(1),q1(2),q2(2))\n", +" q1=q2;\n", +" q0=q1;\n", +"end\n", +"printf('Hence the largest eigenvalue is %.4f with the corresponding eigenvector as %.4f\n %i',a,q0(1),q0(2))" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.5: Inverse_Power_Method.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.5\n", +"//Inverse Power Method\n", +"//Page no. 347\n", +"clc;close;clear;\n", +"\n", +"A=[7,6,-3;-12,-20,24;-6,-12,16];\n", +"e=10^-6;\n", +"X=[1;1;1];\n", +"B=0;\n", +"Y=[0;0;0]\n", +"a=0;l=0;\n", +"for i=1:2\n", +" printf('When a=%i\n',a);\n", +" C=A-a*eye();\n", +" disp(C,'C=')\n", +" C_1=inv(C);\n", +" disp(C_1,'Inverse of C=');\n", +" printf('\n\nItr lambda X')\n", +" printf('\n------------------------------------------------------------------\n')\n", +" for j=1:10\n", +" printf('\n%i %f %f %f %f',j-1,l,X(1),X(2),X(3));\n", +" Y=C_1*X;\n", +" B=max(Y);\n", +" e1=abs(l-B);\n", +" X=Y/B;\n", +" m=0;\n", +" for k=1:3\n", +" m=m+(Y(k)-X(k))^2;\n", +" end\n", +" e2=sqrt(m);\n", +" er=max(e1,e2);\n", +" if(er<e)\n", +" break\n", +" end\n", +" l=B;\n", +" \n", +" end\n", +" a=-3;\n", +" printf('\n\n\n\n')\n", +"end\n", +"printf('\n\n\nNote : Computation of Y is wrong given in the book')" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.6: Rayleigh_Quotient.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.6\n", +"//Rayleigh Quotient\n", +"//Page no. 348\n", +"clc;close;clear;\n", +"\n", +"A=[10,7,8,7;7,5,6,5;8,6,10,9;7,5,9,10];\n", +"q0=[1;1;1;1];\n", +"for i=0:4\n", +" X=(A^i)*q0;\n", +" l=(X'*A*X)/(X'*X)\n", +" printf('\nLambda(%i) = %f\n',i+1,l)\n", +"end\n", +"printf('\n\nDominant Eigenvalue = %f\n\n\n',l)\n", +"\n", +"e=0.001;\n", +"for i=1:5\n", +" q1=A*q0;\n", +" a=max(q1)\n", +" for j=1:4\n", +" q2(j)=q1(j)/a;\n", +" end\n", +"\n", +" q1=q2;\n", +" q0=q1;\n", +"end\n", +"disp(q2,'Corresponding Eigenvector = ')" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.7: Jacobi_Method.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.7\n", +"//Jacobi's Method\n", +"//Page no. 355\n", +"clc;close;clear;\n", +"\n", +"A=[1,1,1/2;1,1,1/4;1/2,1/4,2];\n", +"C=A;\n", +"V=[sqrt(2),0,1/2;sqrt(2),0,1/4;3/(4*sqrt(2)),-1/(4*sqrt(2)),2]\n", +"S=eye(3,3)\n", +"disp(A,'A =')\n", +"VI=0;\n", +"for i=1:3\n", +" for j=1:3\n", +" if(i~=j)\n", +" VI=VI+A(i,j)^2 //initial off diag norm\n", +" end\n", +" end\n", +"end\n", +"VI=sqrt(VI);\n", +"VF=VI*10^-7; //final threshold\n", +"V1=VI/3;\n", +"o=poly(0,'o');\n", +"for i=1:3\n", +"for q=2:3\n", +" for p=q-1:-1:1\n", +" if(A(p,q)>V1)\n", +" a=-A(p,q);\n", +" b=(A(p,p)-A(q,q))/2\n", +" if(b~=0)\n", +" w=b*abs(1/b)*(a/sqrt(a^2+b^2));\n", +" else\n", +" w=(a/sqrt(a^2+b^2));\n", +" end\n", +" sin0=w/sqrt(2*(1+sqrt(1-w^2)));\n", +" cos0=sqrt(1-sin0^2)\n", +" end\n", +" B(p,p)=A(p,p)*cos0^2+A(q,q)*sin0^2-2*A(p,q)*sin0*cos0\n", +" B(q,q)=A(p,p)*sin0^2+A(q,q)*cos0^2+2*A(p,q)*sin0*cos0\n", +" B(p,q)=(A(p,p)-A(q,q))*sin0*cos0+A(p,q)*(cos0^2-sin0^2)\n", +" S(i,i)=S(i,i)\n", +" S(i,p)=S(i,p)*cos0-S(i,q)*sin0\n", +" S(i,q)=S(i,p)*sin0+S(i,q)*cos0\n", +" \n", +" end\n", +"end\n", +"end\n", +"disp(B,'B =')\n", +"disp(S,'S =')\n", +"printf('\n\n\nComputation error in the solution provided by book')" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.8: Recursive_Formula.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.8\n", +"//Recursive Formula\n", +"//Page no. 357\n", +"clc;close;clear;\n", +"\n", +"A=[2,-1,0,0;-1,2,-1,0;0,-1,2,-1;0,0,-1,2];\n", +"l=poly(0,'l');\n", +"p0=1;\n", +"p1=A(1,1)-l;\n", +"for i=2:4\n", +" p2=(A(i,i)-l)*p1-A(i,i-1)^2*p0;\n", +" p0=p1;\n", +" p1=p2;\n", +" printf('\n\np%i(l) = ',i);\n", +" disp(p2)\n", +"end" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 11.9: QR_Method.sce" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Example 11.9\n", +"//QR Method\n", +"//Page no. 360\n", +"clc;close;clear;\n", +"\n", +"A=[2,-1,0;-1,2,-1;0,-1,2];\n", +"deff('y=c(i,j)','y=A(j,j)/sqrt((A(i,j)^2+A(j,j)^2))')\n", +"deff('y=s2(i,j)','y=A(i,j)/sqrt((A(i,j)^2+A(j,j)^2))')\n", +"disp(A,'A=')\n", +"l0=0;f=1;m=0;s=0;w=0;\n", +"for n=1:5\n", +" for j=1:2\n", +" for k=1:2\n", +" V(j,k)=A(j,k)\n", +" end\n", +" end\n", +" disp(V,'V=')\n", +" p=poly(V,'x');\n", +" disp('=0',p);\n", +" a=roots(p);\n", +" for j=1:2\n", +" printf('\na(%i) = %f',j,a(j))\n", +" end\n", +" if(abs(a(1)-V(1,1))<=abs(a(2)-V(1,1)))\n", +" a=a(1)\n", +" else\n", +" a=a(2)\n", +" end\n", +" printf('\na = %f\n',a)\n", +" s=s+a;\n", +" A=A-a*eye()\n", +" R=A;Q=eye(3,3);\n", +" \n", +" for j=1:2\n", +" for i=j+1:3\n", +" for k=1:3 //C matrix evaluation\n", +" for l=1:3\n", +" if(k==l)\n", +" if(k==i | k==j)\n", +" C(k,l)=c(i,j)\n", +" else\n", +" C(k,l)=1\n", +" end\n", +" end\n", +" if(k>l)\n", +" if(k==i & l==j)\n", +" C(k,l)=-1*s2(i,j)\n", +" else\n", +" C(k,l)=0\n", +" end\n", +" end\n", +" if(k<l)\n", +" if(k==j & l==i)\n", +" C(k,l)=s2(i,j)\n", +" else\n", +" C(k,l)=0\n", +" end\n", +" end\n", +" end\n", +" end\n", +" \n", +" R=C*R;\n", +" Q=Q*C';\n", +" \n", +" end\n", +" end\n", +"disp(Q,'Q=',R,'R=')\n", +"disp(Q*R,'Q*R=')\n", +"A=R*Q;\n", +"disp(A,'A=')\n", +"end\n", +"l1=l0+s;\n", +"for i=2:3\n", +" for j=2:3\n", +" V(i-1,j-1)=A(i,j)\n", +" end\n", +"end\n", +"disp(V,'V=')\n", +" p=poly(V,'x');\n", +" disp('=0',p);\n", +" a=roots(p);\n", +" for j=1:2\n", +" printf('\na(%i) = %f',j,a(j))\n", +" end\n", +" l2=l1+a(1)\n", +" l3=l1+a(2)\n", +" disp(l3,'l3=',l2,'l2=',l1,'l1=')\n", +"printf('\n\n\nNote : Values of V varies in each step resulting in different results due to error in book calculation')" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} |