{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "\n", "%precision 3\n", "np.set_printoptions(precision=3, suppress=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def is_upper_triangular(RQ):\n", " for i in range(1, len(A)):\n", " for j in range(i):\n", " if abs(RQ[i][j]) > 0.0001:\n", " return False\n", " \n", " return True" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def factorize(A):\n", " RQ = A\n", "\n", " for n in range(101):\n", " if is_upper_triangular(RQ):\n", " break\n", " \n", " Q,R = np.linalg.qr(RQ)\n", " RQ = R@Q\n", " \n", " print(f'After iteration {n+1}:')\n", " print(RQ)\n", " print()\n", " \n", " return n, RQ" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def find_eigenvalues(A):\n", " size = len(A)\n", " eigenvalues = np.zeros(size)\n", " n, RQ = factorize(A)\n", " \n", " for i in range(size):\n", " eigenvalues[i] = RQ[i][i]\n", " \n", " return n, RQ, eigenvalues" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[5, 1],\n", " [3, 3]])" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = np.array([[5, 1], \n", " [3, 3]])\n", "\n", "A" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "After iteration 1:\n", "[[ 6.235 0.941]\n", " [-1.059 1.765]]\n", "\n", "After iteration 2:\n", "[[ 6.129 -1.682]\n", " [ 0.318 1.871]]\n", "\n", "After iteration 3:\n", "[[ 6.047 1.899]\n", " [-0.101 1.953]]\n", "\n", "After iteration 4:\n", "[[ 6.016 -1.967]\n", " [ 0.033 1.984]]\n", "\n", "After iteration 5:\n", "[[ 6.005 1.989]\n", " [-0.011 1.995]]\n", "\n", "After iteration 6:\n", "[[ 6.002 -1.996]\n", " [ 0.004 1.998]]\n", "\n", "After iteration 7:\n", "[[ 6.001 1.999]\n", " [-0.001 1.999]]\n", "\n", "After iteration 8:\n", "[[ 6. -2.]\n", " [ 0. 2.]]\n", "\n", "After iteration 9:\n", "[[ 6. 2.]\n", " [-0. 2.]]\n", "\n", "After iteration 10:\n", "[[ 6. -2.]\n", " [ 0. 2.]]\n", "\n", "Upper-triangular matrix after 10 iterations:\n", "[[ 6. -2.]\n", " [ 0. 2.]]\n", "\n", "Eigenvalues:\n", "[6. 2.]\n" ] } ], "source": [ "n, RQ, values = find_eigenvalues(A)\n", "\n", "print(f'Upper-triangular matrix after {n} iterations:')\n", "print(RQ)\n", "print()\n", "\n", "print('Eigenvalues:')\n", "print(values)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[ 92, -32, -15],\n", " [-64, 34, 39],\n", " [176, -68, -99]])" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = np.array([[ 92, -32, -15],\n", " [-64, 34, 39],\n", " [176, -68, -99]])\n", "\n", "A" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "After iteration 1:\n", "[[ 31.012 2.04 244.332]\n", " [ 12.206 10.861 -12.481]\n", " [ 23.86 3.105 -14.873]]\n", "\n", "After iteration 2:\n", "[[ 133.383 -19.963 -115.265]\n", " [ -47.914 15.653 71.675]\n", " [ 87.77 -11.688 -122.037]]\n", "\n", "After iteration 3:\n", "[[ 47.804 -47.666 235.158]\n", " [ 5.965 12.401 -11.655]\n", " [ 21.743 11.404 -33.205]]\n", "\n", "After iteration 4:\n", "[[ 124.96 113.346 -121.625]\n", " [ -48.839 -82.568 91.704]\n", " [ 13.135 24.701 -15.392]]\n", "\n", "After iteration 5:\n", "[[ 60.817 215.496 93.042]\n", " [ 17.403 -44.741 -25.606]\n", " [ -1.123 3.484 10.924]]\n", "\n", "After iteration 6:\n", "[[112.936 163.766 -95.523]\n", " [-27.301 -94.871 57.987]\n", " [ 0.159 0.606 8.935]]\n", "\n", "After iteration 7:\n", "[[ 70.15 204.399 105.198]\n", " [ 12.673 -52.456 -33.491]\n", " [ -0.013 0.062 9.306]]\n", "\n", "After iteration 8:\n", "[[104.233 175.983 -97.778]\n", " [-15.627 -86.499 51.766]\n", " [ 0.002 0.01 9.267]]\n", "\n", "After iteration 9:\n", "[[ 76.525 200.437 104.35 ]\n", " [ 8.815 -58.798 -36.688]\n", " [ -0. 0.001 9.273]]\n", "\n", "After iteration 10:\n", "[[ 98.542 182.311 -99.469]\n", " [ -9.309 -80.814 48.391]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 11:\n", "[[ 80.756 197.575 103.579]\n", " [ 5.954 -63.029 -38.821]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 12:\n", "[[ 94.904 185.93 -100.444]\n", " [ -5.69 -77.177 46.332]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 13:\n", "[[ 83.52 195.565 103.037]\n", " [ 3.945 -65.792 -40.237]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 14:\n", "[[ 92.59 188.084 -101.024]\n", " [ -3.536 -74.862 45.054]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 15:\n", "[[ 85.308 194.201 102.67 ]\n", " [ 2.581 -67.581 -41.166]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 16:\n", "[[ 91.116 189.4 -101.378]\n", " [ -2.22 -73.389 44.252]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 17:\n", "[[ 86.46 193.295 102.426]\n", " [ 1.675 -68.733 -41.769]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 18:\n", "[[ 90.177 190.217 -101.598]\n", " [ -1.403 -72.45 43.745]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 19:\n", "[[ 87.2 192.701 102.266]\n", " [ 1.081 -69.473 -42.158]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 20:\n", "[[ 89.579 190.729 -101.736]\n", " [ -0.891 -71.851 43.423]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 21:\n", "[[ 87.675 192.316 102.162]\n", " [ 0.696 -69.947 -42.409]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 22:\n", "[[ 89.196 191.053 -101.823]\n", " [ -0.567 -71.468 43.218]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 23:\n", "[[ 87.979 192.067 102.095]\n", " [ 0.447 -70.251 -42.57 ]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 24:\n", "[[ 88.952 191.259 -101.878]\n", " [ -0.362 -71.224 43.088]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 25:\n", "[[ 88.173 191.907 102.052]\n", " [ 0.286 -70.446 -42.674]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 26:\n", "[[ 88.796 191.389 -101.913]\n", " [ -0.231 -71.068 43.005]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 27:\n", "[[ 88.298 191.804 102.025]\n", " [ 0.183 -70.57 -42.74 ]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 28:\n", "[[ 88.696 191.473 -101.936]\n", " [ -0.147 -70.968 42.952]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 29:\n", "[[ 88.378 191.738 102.007]\n", " [ 0.117 -70.65 -42.782]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 30:\n", "[[ 88.632 191.526 -101.95 ]\n", " [ -0.094 -70.905 42.918]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 31:\n", "[[ 88.429 191.695 101.995]\n", " [ 0.075 -70.701 -42.809]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 32:\n", "[[ 88.591 191.56 -101.959]\n", " [ -0.06 -70.864 42.896]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 33:\n", "[[ 88.461 191.668 101.988]\n", " [ 0.048 -70.733 -42.827]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 34:\n", "[[ 88.565 191.582 -101.965]\n", " [ -0.039 -70.838 42.882]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 35:\n", "[[ 88.482 191.651 101.984]\n", " [ 0.031 -70.754 -42.838]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 36:\n", "[[ 88.549 191.596 -101.969]\n", " [ -0.025 -70.821 42.873]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 37:\n", "[[ 88.495 191.64 101.981]\n", " [ 0.02 -70.768 -42.845]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 38:\n", "[[ 88.538 191.604 -101.971]\n", " [ -0.016 -70.81 42.867]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 39:\n", "[[ 88.504 191.633 101.979]\n", " [ 0.013 -70.776 -42.849]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 40:\n", "[[ 88.531 191.61 -101.973]\n", " [ -0.01 -70.803 42.864]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 41:\n", "[[ 88.509 191.628 101.977]\n", " [ 0.008 -70.782 -42.852]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 42:\n", "[[ 88.527 191.614 -101.974]\n", " [ -0.006 -70.799 42.861]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 43:\n", "[[ 88.513 191.625 101.977]\n", " [ 0.005 -70.785 -42.854]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 44:\n", "[[ 88.524 191.616 -101.974]\n", " [ -0.004 -70.796 42.86 ]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 45:\n", "[[ 88.515 191.623 101.976]\n", " [ 0.003 -70.787 -42.855]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 46:\n", "[[ 88.522 191.618 -101.975]\n", " [ -0.003 -70.794 42.859]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 47:\n", "[[ 88.516 191.622 101.976]\n", " [ 0.002 -70.789 -42.856]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 48:\n", "[[ 88.521 191.619 -101.975]\n", " [ -0.002 -70.793 42.858]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 49:\n", "[[ 88.517 191.622 101.976]\n", " [ 0.001 -70.79 -42.856]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 50:\n", "[[ 88.52 191.619 -101.975]\n", " [ -0.001 -70.793 42.858]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 51:\n", "[[ 88.518 191.621 101.975]\n", " [ 0.001 -70.79 -42.857]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 52:\n", "[[ 88.52 191.62 -101.975]\n", " [ -0.001 -70.792 42.858]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 53:\n", "[[ 88.518 191.621 101.975]\n", " [ 0.001 -70.791 -42.857]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 54:\n", "[[ 88.52 191.62 -101.975]\n", " [ -0. -70.792 42.858]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 55:\n", "[[ 88.519 191.621 101.975]\n", " [ 0. -70.791 -42.857]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 56:\n", "[[ 88.519 191.62 -101.975]\n", " [ -0. -70.792 42.857]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 57:\n", "[[ 88.519 191.62 101.975]\n", " [ 0. -70.791 -42.857]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 58:\n", "[[ 88.519 191.62 -101.975]\n", " [ -0. -70.792 42.857]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 59:\n", "[[ 88.519 191.62 101.975]\n", " [ 0. -70.791 -42.857]\n", " [ -0. 0. 9.272]]\n", "\n", "After iteration 60:\n", "[[ 88.519 191.62 -101.975]\n", " [ -0. -70.791 42.857]\n", " [ 0. 0. 9.272]]\n", "\n", "After iteration 61:\n", "[[ 88.519 191.62 101.975]\n", " [ 0. -70.791 -42.857]\n", " [ -0. 0. 9.272]]\n", "\n", "Upper-triangular matrix after 61 iterations:\n", "[[ 88.519 191.62 101.975]\n", " [ 0. -70.791 -42.857]\n", " [ -0. 0. 9.272]]\n", "\n", "Eigenvalues:\n", "[ 88.519 -70.791 9.272]\n" ] } ], "source": [ "n, RQ, values = find_eigenvalues(A)\n", "\n", "print(f'Upper-triangular matrix after {n} iterations:')\n", "print(RQ)\n", "print()\n", "\n", "print('Eigenvalues:')\n", "print(values)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.7" } }, "nbformat": 4, "nbformat_minor": 4 }