Unit3/Computing-Eigenvalues/computing-eigenvalues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "44f6ab49",
   "metadata": {},
   "source": [
    "# Numerical Methods for Computing Eigenvalues\n",
    "\n",
    "### Matrix Similarity\n",
    "\n",
    "The first concept we will need to understand (if you don't already) is the concept of matrix similarity.\n",
    "When we say two matrices $A$ and $B$ are similar matrices it means that they have a very particular relationship.\n",
    "\n",
    "If an invertibe matrix $X$ exits such that the following relationship exists between $A_{n \\times n}$ and $B_{n \\times n}$ then $A$ and $B$ are *similar* matrices.\n",
    "\n",
    "$A = X^{-1} B X$\n",
    "\n",
    "If two matrices are similar they will share many of the same properties:\n",
    "\n",
    "- Rank\n",
    "- Determinant\n",
    "- Trace\n",
    "- ***Eigenvalues (MOST IMPORTANTLY)***\n",
    "- etc... (There are many more, see sources)\n",
    "\n",
    "Because similar matrices will share the same eigenvalues we can exploit the concept of matrix similarity to compute the eigenvalues of a matrix.\n",
    "\n",
    "So how do we go about finding some matrix $X$ or check if $A_{n \\times n}$ and $B_{n \\times n}$ are similar?\n",
    "\n",
    "### Schur Decomposition\n",
    "\n",
    "In order for us to leverage the knowledge of matrix similarity to compute eigenvalues we'll need to use the Schur matrix decomposition, using the $QR$ decomposition.\n",
    "\n",
    "Let's begin with the $QR$ decomposition...\n",
    "\n",
    "$A = QR$\n",
    "\n",
    "With $Q$ being an orthonormal matrix  recall that $Q^T Q = Q Q^T = I$, so $Q^T=Q^{-1}$.\n",
    "\n",
    "Let's then say $B = RQ$. From this we can play quite an clever trick with our $QR$ decomposition of $A$ and the porperties of orthonormal matrices.\n",
    "\n",
    "$B = RQ$\n",
    "\n",
    "$IB = IRQ$ \n",
    "\n",
    "$B = Q^{T}QRQ$\n",
    "\n",
    "$B = Q^{-1}QRQ$ (Remember $A = QR$)\n",
    "\n",
    "$B = Q^{-1}AQ$ (This is the Schur Decomposition)\n",
    "\n",
    "So with this we can say $B$ and $A$ are similar matrices. Further, by examining how we get the Schur decomposition we can see a way of producing an similar matrix for $A$ provided that we can perform a $QR$ decomposition for $A$.\n",
    "That is that we can just compute $RQ$ and we will have a similar matrix.\n",
    "\n",
    "To show or check that two similar matrices have the same eigenvalues, below we'll use `np.linalg.eig()` and `np.linalg.qr()` to confirm that $A$ and $B$ have the same eigenvalues."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "fe2d1e36",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A:\n",
      " [[44. 12. 61.]\n",
      " [94. 80. 26.]\n",
      " [76. 62.  9.]]\n",
      "Eigenvalues for A: \n",
      " [149.49147857 -26.75672795  10.26524939]\n",
      "RQ = B: \n",
      " [[143.17524776 -82.02127042  34.66647877]\n",
      " [-10.9111755    0.63783827  51.77375492]\n",
      " [  8.04904861   1.97549379 -10.81308604]]\n",
      "Eigenvalues for B: \n",
      " [149.49147857 -26.75672795  10.26524939]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "A = np.array(np.random.randint (0, 100, (3, 3)), dtype=np.float64)\n",
    "print(f\"A:\\n {A}\")\n",
    "A_eigvals, A_eigvecs = np.linalg.eig(A)\n",
    "print(f\"Eigenvalues for A: \\n {A_eigvals}\")\n",
    "\n",
    "Q, R = np.linalg.qr(A)\n",
    "B = np.dot(R, Q)\n",
    "print(f\"RQ = B: \\n {B}\")\n",
    "B_eigvals, B_eigvecs = np.linalg.eig(B)\n",
    "print(f\"Eigenvalues for B: \\n {B_eigvals}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9548d52d",
   "metadata": {},
   "source": [
    "As you can clearly see the eigenvalues are the same for both $A$ and $B$.\n",
    "\n",
    "### The Rayleigh Quotient\n",
    "\n",
    "The following is defined as the Rayleigh Quotient.\n",
    "\n",
    "$r(\\vec{x}, A) \\equiv\n",
    "  \\begin{cases}\n",
    "    \\frac{\\langle x \\mid Ax \\rangle} {\\langle x \\mid x \\rangle} & \\quad \\text{}\\\\\n",
    "    \\frac{\\vec{x}^* A \\vec{x}} {\\vec{x}^* \\vec{x}} & \\quad \\text{Complex}\\\\\n",
    "    \\frac{\\vec{x}^T A \\vec{x}} {\\vec{x}^T \\vec{x}} & \\quad \\text{Real}\n",
    "  \\end{cases}\n",
    "$\n",
    "\n",
    "In the case of where $\\vec{x}$ is an eigenvector $(\\vec{v})$ of $A$, then the Rayeligh quotient will procude compute the corresponding eigenvalue for the eigenpair. Of course this will be useful in computing $\\lambda$s.\n",
    "\n",
    "$r(\\vec{v}) = \\lambda$\n",
    "\n",
    "The mathematical analysis to show this is beyond the scope of the focus of computing eigenvalues. If interested though for the sake of simplicity it's best to consider that $A$ is a strictly real and symmetric matrix, or if you want to consider the complex case assume $A$ is Hermitian to show this. However, this general idea behind the Rayleigh Quotiet can be applied to the complex non-Hermitian case, or in our case the real non-symmetric case. This can be seen in the code below using the same randomly generated $A$ from above and the computed eigenvalues and eigenvectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "d245b9c8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A: \n",
      "[[44. 12. 61.]\n",
      " [94. 80. 26.]\n",
      " [76. 62.  9.]]\n",
      "Eigenvalues for A:\n",
      " [149.49147857 -26.75672795  10.26524939]\n",
      "Eigenvectors for A:\n",
      " [[-0.39755815 -0.63646445  0.61843026]\n",
      " [-0.74050254  0.39976377 -0.76199621]\n",
      " [-0.54185192  0.65962257 -0.19210879]]\n",
      "Eigenvalue 1: 149.49147856748235\n",
      "Eigenvalue 2: -26.75672795313828\n",
      "Eigenvalue 3: 10.265249385655858\n"
     ]
    }
   ],
   "source": [
    "print(f\"A: \\n{A}\")\n",
    "print(f\"Eigenvalues for A:\\n {A_eigvals}\")\n",
    "print(f\"Eigenvectors for A:\\n {A_eigvecs}\")\n",
    "# Eigenvectors from np.linalg.eig() comes in a form of a matrix which needs\n",
    "# to be transposed get at the eigenvectors in a loop\n",
    "\n",
    "def rquotient(vec, A):\n",
    "    top = np.dot(vec.T, np.dot(A, vec))\n",
    "    bottom = np.dot(vec.T, vec)\n",
    "    return top / bottom\n",
    "\n",
    "for num, i in enumerate(A_eigvecs.T):\n",
    "    eigval = rquotient(i, A)\n",
    "    print(f\"Eigenvalue {num + 1}: {eigval}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6360d568",
   "metadata": {},
   "source": [
    "As you can see from the output above passing each eigenvector into the Rayleigh Quotient function `rquotient` returns the expected eigenvalues for $A$ as computed before with `np.linalg.eig()`. This is what we can consider a baby method for computing $\\lambda$s. In reality the rayleigh quotient will be used, but as a part of more elaborate methods.\n",
    "\n",
    "### Computing $\\lambda$'s with $QR$\n",
    "\n",
    "The first method of computing $\\lambda$'s comes uses our knowledge of $QR$, matrix similarity, and how to get a similar matrix through the Schur Decomposition.\n",
    "\n",
    "We will start by computing a $QR$ decomposition for some matrix $A_0$ that can be decomposed with $QR$.\n",
    "\n",
    "$A_0 = Q_0 R_0$\n",
    "\n",
    "Then we will compute a similar matrix to $A_0$ using our $Q_0$ and $R_0$ matrices and call this new similar matrix $A_1$.\n",
    "\n",
    "$A_1 = R_0 Q_0$\n",
    "\n",
    "From this point the process will be repeated for $A_1$ (decompose into $Q_1 R_1$) to compute another new similar matrix $A_2$. We will continue through this process iteratively until we compute $A_n$ similar matrices.\n",
    "\n",
    "$A_1 = Q_1 R_1$\n",
    "\n",
    "$A_2 = R_1 Q_1$\n",
    "\n",
    "$\\vdots$\n",
    "\n",
    "$A_n = Q_n R_n$\n",
    "\n",
    "$A_{n+1} = R_n Q_n$\n",
    "\n",
    "What will happen throughout this process each similar matrix computed will get closer and closer, and ultimately converge to an upper triangular matrix (or at least in the numerical world, one with incredibly small values denoted as $\\epsilon$'s we can round to zero below the diagonal). Conveniently the $\\lambda$s will be on the diagonal.\n",
    "\n",
    "$A_n = \n",
    " \\begin{pmatrix}\n",
    "  \\lambda_1 & a_{1,2} & \\cdots & a_{1,m} \\\\\n",
    "  \\epsilon & \\lambda_2 & \\cdots & a_{2,m} \\\\\n",
    "  \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "  0 & 0 & \\cdots & \\lambda_m\n",
    " \\end{pmatrix}$\n",
    " \n",
    " We put this into action with the following code for the same randomly generate $A$ matrix previously."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "61f1d24a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A_42 = \n",
      "[[ 1.49491479e+02 -7.70154185e+01 -6.66314401e+00]\n",
      " [-7.62838420e-31 -2.67567280e+01  4.76364128e+01]\n",
      " [ 2.51713936e-48  9.92303419e-17  1.02652494e+01]]\n",
      "A:\n",
      " [[44. 12. 61.]\n",
      " [94. 80. 26.]\n",
      " [76. 62.  9.]]\n",
      "Eignevalues: [149.49147856748243, -26.756727953138228, 10.265249385655883]\n",
      "# of iterations: 42\n"
     ]
    }
   ],
   "source": [
    "def makesimilar(A):\n",
    "    Q, R = np.linalg.qr(A)\n",
    "    B = np.dot(R, Q)\n",
    "    return B\n",
    "\n",
    "def eig_qr(A):\n",
    "    B = makesimilar(A)\n",
    "    iters = 0\n",
    "    leig = B[-1, -1]\n",
    "    diff = 1\n",
    "    while diff > 1e-32:\n",
    "        B = makesimilar(B)\n",
    "        iters += 1\n",
    "        diff = abs(leig - B[-1, -1])\n",
    "        leig = B[-1, -1]\n",
    "    print(f\"A_{iters} = \\n{B}\")\n",
    "    eigs = [B[i, i] for i in range(len(B))]\n",
    "    return eigs, iters\n",
    "\n",
    "eigs, iters = eig_qr(A)\n",
    "print(f\"A:\\n {A}\")\n",
    "print(f\"Eignevalues: {eigs}\")\n",
    "print(f\"# of iterations: {iters}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8132a0e",
   "metadata": {},
   "source": [
    "As you can hopefully see we get the same $\\lambda$s as before when using `numpy.linalg.eig()`. In `eig_qr()` we are computing similar matrices in the process of the QR algorithm until we reach a difference in values along the diagonal of the $n$th and $n - 1$ $A_n$'s on order of $10^{-32}$ (see the while loop).\n",
    "\n",
    "### Computing $\\lambda$'s with $QR$ + Shifts\n",
    "\n",
    "While computing $\\lambda'$s with $QR$ worked well, it took 89 iterations of computing similar matrices to converge to the point where the computer rounded the last value of the first column to zero. While we could lower our standards and compute less iterations, there is a faster way to converge to an upper triangular matrix and precision in out $\\lambda'$s with less iterations. That method is introducing shifts into the $QR$ method.\n",
    "\n",
    "\n",
    "There are 2 possible ways to start this method:\n",
    "\n",
    "1. Compute a QR decomposition with no shifts initially\n",
    "\n",
    "$A_0 = Q_0 R_0$\n",
    "\n",
    "$A_1 = R_0 Q_0$ (Like before)\n",
    "\n",
    "OR\n",
    "\n",
    "2. Shift A and then compute a QR decomposition for the shifted matrix for some value $s$\n",
    "\n",
    "$A_0 - sI = Q_0 R_0$\n",
    "\n",
    "Then reintroduce the shift when computing the similar matrix.\n",
    "\n",
    "$A_1 = R_0 Q_0 + sI$\n",
    "\n",
    "\n",
    "Either way for each subsequent similar matrix computation $(n >= 1)$ we'll use the 2nd method.\n",
    "\n",
    "$A_n - sI = Q_n R_n$\n",
    "\n",
    "$A_{n+1} = R_n Q_n + sI$\n",
    "\n",
    "But how do we choose a value for $s$? Should we even choose one at all or just use a random value?\n",
    "\n",
    "While you could use a random value it is unlikely to give too much of an efficiency improvement.\n",
    "\n",
    "To use this shifting method and see improved efficiency, we'll want to choose a value close to a $\\lambda$ or better yet use the **Rayleigh Quotient**. The motivation for this comes from a different, in my opinion, worse method to compute $\\lambda$s discussed later on, but the general idea is that we want to pick a value for $s$ close to a $\\lambda$.\n",
    "\n",
    "If we think about computing $\\lambda$s without shifts, each iteration of computing a similar $A_n$ matrix converges to an upper triangular matrix (roughly) with better approximations of the $\\lambda$s along the diagonal with each iteration. This means that the last value of each similar matrix $A_{m,m}$ is getting closer to an actual $\\lambda$ with each iteration. So with that in mind, we should choose a value along the diagonal of our similar matrix when starting each new iteration to be our shift $s$. We do that in the below code for the last value along the diagonal.\n",
    "\n",
    "$A_n = \n",
    " \\begin{pmatrix}\n",
    "  \\lambda_1 & a_{1,2} & \\cdots & a_{1,m} \\\\\n",
    "  \\epsilon & \\lambda_2 & \\cdots & a_{2,m} \\\\\n",
    "  \\vdots  & \\vdots  & \\ddots & \\vdots  \\\\\n",
    "  0 & 0 & \\cdots & s\n",
    " \\end{pmatrix}_{m \\times m}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "96cea3c5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A:\n",
      " [[44. 12. 61.]\n",
      " [94. 80. 26.]\n",
      " [76. 62.  9.]]\n",
      "Position: 1\n",
      "\n",
      "A_22 = \n",
      "[[ 1.49491479e+02  6.48987676e+01  4.19990730e+01]\n",
      " [-5.77915850e-15  1.02652494e+01 -4.76364128e+01]\n",
      " [ 0.00000000e+00  0.00000000e+00 -2.67567280e+01]]\n",
      "Eignevalues: [149.4914785674824, 10.265249385655856, -26.75672795313824]\n",
      "# of iterations: 22\n",
      "Position: 2\n",
      "\n",
      "A_23 = \n",
      "[[ 1.49491479e+02 -6.48987676e+01 -4.19990730e+01]\n",
      " [ 1.21394639e-15  1.02652494e+01 -4.76364128e+01]\n",
      " [ 0.00000000e+00  0.00000000e+00 -2.67567280e+01]]\n",
      "Eignevalues: [149.4914785674824, 10.265249385655856, -26.75672795313824]\n",
      "# of iterations: 23\n",
      "Position: 3\n",
      "\n",
      "A_8 = \n",
      "[[ 1.49491487e+02 -6.48987499e+01  4.19990669e+01]\n",
      " [ 1.77490861e-05  1.02652411e+01  4.76364181e+01]\n",
      " [-2.12711673e-67 -8.32848222e-62 -2.67567280e+01]]\n",
      "Eignevalues: [149.49148684101993, 10.265241112118325, -26.75672795313824]\n",
      "# of iterations: 8\n"
     ]
    }
   ],
   "source": [
    "def eig_qrshifts(A, refeig=-1, sindex=-1, verbose=True):\n",
    "    B = makesimilar(A)\n",
    "    n = 0\n",
    "    leig = B[refeig, refeig]\n",
    "    diff = 1\n",
    "    while diff > 1e-32 and n < 100:\n",
    "        shift = np.identity(len(B)) * B[sindex, sindex]\n",
    "        C = B - shift\n",
    "        B = makesimilar(C) + shift\n",
    "        n += 1\n",
    "        diff = abs(leig - B[refeig, refeig])\n",
    "        leig = B[refeig, refeig]\n",
    "    if verbose is True:\n",
    "        print(f\"A_{n} = \\n{B}\")\n",
    "    eigs = [B[i, i] for i in range(len(B))]\n",
    "    return eigs, n\n",
    "\n",
    "print(f\"A:\\n {A}\")\n",
    "m, n = A.shape\n",
    "\n",
    "for i in range(0, n):\n",
    "    print(f\"Position: {i + 1}\\n\")\n",
    "    eigs, iters = eig_qrshifts(A, refeig=i)\n",
    "    print(f\"Eignevalues: {eigs}\")\n",
    "    print(f\"# of iterations: {iters}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "066e0fdd",
   "metadata": {},
   "source": [
    "What we see in the above output for computing $\\lambda$s with the QR algorithm with shifts is that we are computing less similar matrices (doing less iterations) compared to just the QR algorithm. Also above, by using the `refeig` kwarg of `eig_qrshifts()` we can change the value along the diagonal we are using as our reference for comparing values with each iteration until we reach a difference between iterations of $<10^{-32}$. From using this we can see in the output that when we choose the shift to be the last value along the diagonal, setting the reference to the same last position along the diagonal converges to a precision on order of $<10^{-32}$ the fastest in only 8 iterations.\n",
    "\n",
    "If the idea about choosing the shift to be the last value along the diagonal works well because with each iteration the values along the diagonal converge to be the $\\lambda$s, then couldn't we choose any value along the diagonal to be the shift $(s)$? The below code shows that choosing just any value along the diagonal as the shift doesn't work by iterating through the `refeig` and `sindex` (the shift index) kwargs of `eig_qrshifts()` keeping track of the number of iterations, stopping at 100 max iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "d6320878",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZkAAAGNCAYAAADD4gxDAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8fJSN1AAAACXBIWXMAAA9hAAAPYQGoP6dpAAAclElEQVR4nO3df2xT9/3v8ZcD5McgNg1dEiLCiCaugNFBBzRNQYiuERmrELTsBxLbKEJl2hK2kG0UpPJjjDaD3bW5KRTWaoNVKiurdIGWaUwoqEHchlCCmMpWKNXYJRtyoOqwIfvGCbHvH72415dkxTnn7dg5z4d01Ob4HJ+P68mvvd+fj499sVgsJgAADGQN9gAAAEMXIQMAMEPIAADMEDIAADOEDADADCEDADBDyAAAzBAyAAAzhAwAwAwhAwAwQ8gAwBB0/PhxLVy4UCUlJfL5fDp48GDC47FYTBs3btTYsWOVl5enyspKXbx4MeGYjz76SMuWLZPf79fo0aO1cuVK3bx5M6lxEDIAMAR1dnZq2rRp2rlzZ5+Pb9++XY2Njdq9e7daW1s1cuRIVVVVqaurK37MsmXL9Je//EVHjx7V4cOHdfz4ca1atSqpcfi4QSYADG0+n08HDhzQ4sWLJX1cxZSUlOhHP/qRfvzjH0uSQqGQioqKtHfvXi1dulTvvfeepkyZonfeeUczZ86UJB05ckRf/epX9Y9//EMlJSV3de3hJq8IACBJ6urqUnd3t+PnicVi8vl8CftycnKUk5OT9HNdunRJwWBQlZWV8X2BQEDl5eVqaWnR0qVL1dLSotGjR8cDRpIqKyuVlZWl1tZWPfbYY3d1LUIGAIx0dXWprKxMwWDQ8XONGjXqjvmQTZs2afPmzUk/1+3xFBUVJewvKiqKPxYMBlVYWJjw+PDhw1VQUJDU6yFkAMBId3e3gsGg2tsvye/3D/h5wuGwSkvL1N7envA8A6liUo2QAQBjfr/fUci4/TzFxcWSpI6ODo0dOza+v6OjQ9OnT48fc/Xq1YTzbt26pY8++ih+/t1gdRkAmLvlwuaesrIyFRcXq6mpKb4vHA6rtbVVFRUVkqSKigpdv35dbW1t8WOOHTumaDSq8vLyu74WlQwAmHMaFMmfe/PmTX3wwQfxvy9duqSzZ8+qoKBA48ePV21trbZu3aqJEyeqrKxMGzZsUElJSXwF2uTJk/WVr3xFTz75pHbv3q2enh7V1NRo6dKld72yTCJkAGBIOn36tB5++OH433V1dZKk5cuXa+/evVq7dq06Ozu1atUqXb9+XXPmzNGRI0eUm5sbP+fVV19VTU2NHnnkEWVlZWnJkiVqbGxMahx8TwYAjITDYQUCAYVC/9vxxH8g8DmFQiFX5mRSiUoGAMz1ylm7rNetgaQcE/8AADNUMgBgLvUT/+mCkAEAc94NGdplAAAzVDIAYM67lQwhAwDmeuVshRirywAAuAMhMwA7d+7UhAkTlJubq/Lycp06dWqwh+RJn/bzskiN+vp6zZo1S/n5+SosLNTixYt14cKFwR5Wmrn9PZmBblQynrF//37V1dVp06ZNOnPmjKZNm6aqqqo77lYKe5/287JIjebmZlVXV+vkyZM6evSoenp6NH/+fHV2dg720NJIet0gM5W4rUySysvLNWvWLO3YsUOSFI1GVVpaqtWrV2vdunWDPDrv+v9/XhaD59q1ayosLFRzc7Pmzp072MMZVJ/cVuaE/P5RDp7npgKBORl5WxkqmSR0d3erra0t4SdLs7KyVFlZqZaWlkEcGZA+QqGQJKmgoGCQR4J0wOqyJHz44Yfq7e3t8ydLz58/P0ijAtJHNBpVbW2tZs+eralTpw72cNIIS5gBwLHq6mqdO3dOJ06cGOyhpBnv3iCTkEnCvffeq2HDhqmjoyNhf0dHR1I/RwoMRTU1NTp8+LCOHz+ucePGDfZwkCaYk0lCdna2ZsyYkfCTpdFoVE1NTfGfLAW8JhaLqaamRgcOHNCxY8dUVlY22ENKQ95dXUYlk6S6ujotX75cM2fO1AMPPKCGhgZ1dnZqxYoVgz00z/m0n5dFalRXV2vfvn06dOiQ8vPzFQwGJUmBQEB5eXmDPLp04d05GZYwD8COHTv0i1/8QsFgUNOnT1djY6PKy8sHe1ie89ZbbyX8vOxtt39eFqnh8/n63L9nzx498cQTqR1MmvlkCfMf5PePdPA8nQoEHs3IJcyEDAAY+SRkDrkQMosyMmRolwGAOe+2y5j4BwCYoZIBAHN8TwYAYIZ2GQAArqOSAQBzVDJIQiQS0ebNmxWJRAZ7KJ7He5FeeD/6491v/PM9mQH4ZO175q1ZH2p4L9IL70eiT/57vCS//zMOnuffCgRWZeR/VyoZAIAZ5mQAwBxLmFMmGo3qypUrys/P7/eeR+kuHA4n/BODh/civQyF9yMWi+nGjRsqKSlRVpZbzZ5eOQsKQuauXblyRaWlpam+rImh8jqGAt6L9DIU3o/29nZ+F8cFKQ+Z/Px8SR+/gZk2gTUUrQwEBnsI+H+MGewBQN2S9uiTzyp3eHcJc8pD5naLzO/3EzJpYMRgDwAJcgZ7AIhzt53v3ZBhdRkAwAyrywDAHKvLAABmaJcBAOA6KhkAMOfdSoaQAQBzhAwAwIx3Q4Y5GQCAGSoZADDHEmYAgJlbkoY5PD8z0S4DAJihkgEAc96tZAgZADDn3ZChXQYAMEMlAwDmWF0GADBzS84aR7TLAAC4A5UMAJjzbiVDyACAOe+GDO0yAIAZKhkAMNcrZyvEWF0GAOgXS5gBAGZuSfI5PD8zMScDADBDJQMA5rxbyRAyAGDOuyFDuwwAYIZKBgDMebeSIWQAwFyvnIVM5i5hpl0GADBDJQMA5py2u2iXAQD65d2QoV0GADBDJQMA5rxbyRAyAGDO6eowVpcBAHAHKhkAMHdLUszB+VQyAIB+3XJhu3u9vb3asGGDysrKlJeXp89//vP62c9+pljsk6CLxWLauHGjxo4dq7y8PFVWVurixYtOX+gdCBkAMJfakNm2bZt27dqlHTt26L333tO2bdu0fft2vfDCC/Fjtm/frsbGRu3evVutra0aOXKkqqqq1NXV5fTFJqBdBgBDzNtvv61Fixbp0UcflSRNmDBBv/vd73Tq1ClJH1cxDQ0Nevrpp7Vo0SJJ0iuvvKKioiIdPHhQS5cudW0sVDIAYM6dSiYcDidskUikz6s99NBDampq0vvvvy9J+vOf/6wTJ05owYIFkqRLly4pGAyqsrIyfk4gEFB5eblaWlpcfeVUMgBgrlfOJv6jkqTS0tKEvZs2bdLmzZvvOHrdunUKh8OaNGmShg0bpt7eXj3zzDNatmyZJCkYDEqSioqKEs4rKiqKP+YWQgYAMkR7e7v8fn/875ycnD6P+/3vf69XX31V+/bt0xe+8AWdPXtWtbW1Kikp0fLly1M1XEkDbJft3LlTEyZMUG5ursrLy+N9PgBAX3pd2CS/35+w9RcyP/nJT7Ru3TotXbpU9913n7797W9rzZo1qq+vlyQVFxdLkjo6OhLO6+joiD/mlqRDZv/+/aqrq9OmTZt05swZTZs2TVVVVbp69aqrAwOAoSO1q8v+/e9/Kysr8eN92LBhikY/bruVlZWpuLhYTU1N8cfD4bBaW1tVUVGR/Mv7D5IOmeeee05PPvmkVqxYoSlTpmj37t36zGc+o9/85jeuDgwAMDALFy7UM888oz/84Q/6+9//rgMHDui5557TY489Jkny+Xyqra3V1q1b9cYbb+jdd9/Vd77zHZWUlGjx4sWujiWpOZnu7m61tbVp/fr18X1ZWVmqrKzsd0VCJBJJWAERDocHOFQAyFS35GwxbzSpo1944QVt2LBB3//+93X16lWVlJTou9/9rjZu3Bg/Zu3aters7NSqVat0/fp1zZkzR0eOHFFubq6Dcd4pqZD58MMP1dvb2+eKhPPnz/d5Tn19vX76058OfIQAkPFSGzL5+flqaGhQQ0NDv8f4fD5t2bJFW7ZscTCuT2f+PZn169crFArFt/b2dutLAgDSRFKVzL333qthw4YltSIhJyen3xUQAOANvUq2Gknk5Ds2gyupSiY7O1szZsxIWJEQjUbV1NTk+ooEABg6Uru6LJ0k/WXMuro6LV++XDNnztQDDzyghoYGdXZ2asWKFRbjAwBksKRD5pvf/KauXbumjRs3KhgMavr06Tpy5MgdiwEAALfdkuRzcH7mtssGdFuZmpoa1dTUuD0WABiiCBkAgJVY1FlOZG7GcKt/AIAdKhkAsBaVsxXMTs4dZIQMAFj75EbKAz8/Q9EuAwCYoZIBAGsermQIGQCw5uE5GdplAAAzVDIAYI12GQDADO0yAADcRyUDANaictbyyuBKhpABAGsenpOhXQYAMEMlAwDWPDzxT8gAgDUPt8sIGQCw5uGQYU4GAGCGSgYArDEnAwAwQ7sMAAD3UckAgLWYnLW8Ym4NJPUIGQCwRrsMAAD3UckAgDUPVzKEDABY8/ASZtplAAAzVDIAYI12GQDAjIdDhnYZAMAMlQwAWPPwxD8hAwDWonLW8iJkAAD98nAlw5wMAMAMlQwAWPPw6jJCBgCseThkaJcBAMxQyQCANQ9P/BMyAGCNdhkAAO6jkgEAax6uZAgZALAWk7N5lZhbA0k9Qsbj9sUy+H+9Q9BTPt9gD8HzeAfcRcgAgDXaZQAAMyxhBgCY8XAlwxJmAIAZKhkAsObhSoaQAQBrHp6ToV0GADBDJQMA1miXAQDMROUsKGiXAQBwJyoZALDm4Yl/QgYArHl4ToZ2GQDADJUMAFijXQYAMEO7DAAA91HJAIA1D1cyhAwAWGNOBgBghm/8AwDgPioZALDm4XYZlQwAWOt1YUvSP//5T33rW9/SmDFjlJeXp/vuu0+nT5+OPx6LxbRx40aNHTtWeXl5qqys1MWLFx28yL4RMgAwxPzrX//S7NmzNWLECP3xj3/UX//6V/3yl7/UPffcEz9m+/btamxs1O7du9Xa2qqRI0eqqqpKXV1dro6FdhkAWEvxEuZt27aptLRUe/bsie8rKyuL/3ssFlNDQ4OefvppLVq0SJL0yiuvqKioSAcPHtTSpUsdDDYRlQwAWIu6sEkKh8MJWyQS6fNyb7zxhmbOnKmvf/3rKiws1P3336+XX345/vilS5cUDAZVWVkZ3xcIBFReXq6WlhZXXzohAwAZorS0VIFAIL7V19f3edzf/vY37dq1SxMnTtSf/vQnfe9739MPfvAD/fa3v5UkBYNBSVJRUVHCeUVFRfHH3EK7DACsudQua29vl9/vj+/Oycnp8/BoNKqZM2fq2WeflSTdf//9OnfunHbv3q3ly5c7GEjyqGQAwJpLq8v8fn/C1l/IjB07VlOmTEnYN3nyZF2+fFmSVFxcLEnq6OhIOKajoyP+mFsIGQAYYmbPnq0LFy4k7Hv//ff1uc99TtLHiwCKi4vV1NQUfzwcDqu1tVUVFRWujoV2GQBYi8nZFypjyR2+Zs0aPfTQQ3r22Wf1jW98Q6dOndJLL72kl156SZLk8/lUW1urrVu3auLEiSorK9OGDRtUUlKixYsXOxjonQgZALCW4iXMs2bN0oEDB7R+/Xpt2bJFZWVlamho0LJly+LHrF27Vp2dnVq1apWuX7+uOXPm6MiRI8rNzXUw0Dv5YrFYkhnpTDgcViAQUCgUSpjAAiA95fMN9hA8LyLpf0iufEbFP+9+LPn7nj65u+eJSIH/7s6YUo1KBgCsefjeZYQMAFjjR8sAAGY8HDIsYQYAmKGSAQBrzMkAAMzQLgMAwH1UMgBgLSpn1QjtMgBAvzw8J0O7DABghkoGAKx5eOKfkAEAa7TLAABwX9Ihc/z4cS1cuFAlJSXy+Xw6ePCgwbAAYAhx6ZcxM1HSIdPZ2alp06Zp586dFuMBgKHHwyGT9JzMggULtGDBAouxAACGGPOJ/0gkokgkEv87HA5bXxIA0gsT/3bq6+sVCATiW2lpqfUlASC93P7G/0A3QqZ/69evVygUim/t7e3WlwSA9MKcjJ2cnBzl5Dj4cWsAQMbiy5gAYM3DczJJh8zNmzf1wQcfxP++dOmSzp49q4KCAo0fP97VwQHAkNArZ5MTXmqXnT59Wg8//HD877q6OknS8uXLtXfvXtcGBgDIfEmHzLx58xSLxSzGAgBDE+0yAIAZD7fLuEEmAMAMlQwAWPNwJUPIAIC1mJzNq2TwNDjtMgCAGSoZALDWK8nn8PwMRcgAgDUPhwztMgCAGSoZALDGlzEBAGY83C4jZADAmocrGeZkAABmqGQAwBrtMgCAmaicBQXtMgAA7kQlAwDWonLWLsvgSoaQAQBrTudUMnhOhnYZAMAMlQwAWPNwJUPIAIA1D8/J0C4DAJihkgEAa7TLAABmaJcBAOA+KhkAsOa0EsngSoaQAQBrvZJiDs4nZAAA/fJwJcOcDADADJUMAFijXQYAMOPhkKFdBgAwQyUDANY8PPFPyACAtaictcucnDvIaJcBAMxQyQCANaf3LsvgSoaQAQBrvfJsyNAuAwCYoZIBAGsermQIGQCwxpwMAMCMhysZ5mQAAGaoZADAmocrGUIGSCM7BnsAsPk8j1k9cfqjXQYAMEMlAwDGev/v5uT8TEXIAIAxL4cM7TIAGOJ+/vOfy+fzqba2Nr6vq6tL1dXVGjNmjEaNGqUlS5aoo6PD9WsTMgBgLOrCNlDvvPOOfvWrX+mLX/xiwv41a9bozTff1Ouvv67m5mZduXJFjz/+uIMr9Y2QAQBjvS5sA3Hz5k0tW7ZML7/8su655574/lAopF//+td67rnn9OUvf1kzZszQnj179Pbbb+vkyZMDvFrfCBkAyBDhcDhhi0Qi//H46upqPfroo6qsrEzY39bWpp6enoT9kyZN0vjx49XS0uLqmAkZADDmVrustLRUgUAgvtXX1/d7zddee01nzpzp85hgMKjs7GyNHj06YX9RUZGCwaCDV3onVpcBgDG3Vpe1t7fL7/fH9+fk5PR5fHt7u374wx/q6NGjys3NdXBl56hkACBD+P3+hK2/kGlra9PVq1f1pS99ScOHD9fw4cPV3NysxsZGDR8+XEVFReru7tb169cTzuvo6FBxcbGrY6aSAQBjUTmrZJJdXfbII4/o3XffTdi3YsUKTZo0SU899ZRKS0s1YsQINTU1acmSJZKkCxcu6PLly6qoqHAw0jsRMgBgzOky5GTPzc/P19SpUxP2jRw5UmPGjInvX7lyperq6lRQUCC/36/Vq1eroqJCDz74oIOR3omQAQBj6fiN/+eff15ZWVlasmSJIpGIqqqq9OKLL7p+HV8sFkvpvUHD4bACgYBCoVDCBBYAaaTPyf3g4YaYpP+SXPmMuv15976kfAfPc0PSf3NpTKlGJQMAxtKxkkkVQgYAjKV6TiadsIQZAGCGSgYAjNEuAwCYoV0GAIABKhkAMJbqb/ynE0IGAIx5eU6GdhkAwAyVDAAY8/LEPyEDAMZolwEAYIBKBgCMebmSIWQAwBhzMgAAM16uZJiTAQCYoZIBAGMxOWt5pfSXJV1GyACAMdplAAAYoJIBAGNermQIGQAw5uUlzLTLAABmqGQAwBjtMgCAGS+HDO0yAIAZKhkAMObliX9CBgCMReWs5ZXJIUO7DABghkoGAIzRLgMAmPHy6jJCBgCMeTlkkpqTqa+v16xZs5Sfn6/CwkItXrxYFy5csBobACDDJRUyzc3Nqq6u1smTJ3X06FH19PRo/vz56uzstBofAGS8qAtbpkqqXXbkyJGEv/fu3avCwkK1tbVp7ty5rg4MAIYKL7fLHM3JhEIhSVJBQUG/x0QiEUUikfjf4XDYySUBABlkwN+TiUajqq2t1ezZszV16tR+j6uvr1cgEIhvpaWlA70kAGSkXhe2TDXgkKmurta5c+f02muv/cfj1q9fr1AoFN/a29sHekkAyEgxOZuPiaV+yK4ZULuspqZGhw8f1vHjxzVu3Lj/eGxOTo5ycnIGNDgAQGZLKmRisZhWr16tAwcO6K233lJZWZnVuABgyGDi/y5VV1dr3759OnTokPLz8xUMBiVJgUBAeXl5JgMEgEzn5dvKJDUns2vXLoVCIc2bN09jx46Nb/v377caHwAggyXdLgMAJId2GQDAjJdDht+TAQCYoZIBAGNenvgnZADAmJfbZYQMABiLyllQZHIlw5wMAMAMlQwAGGNOBgBgxstzMrTLAABmqGQAwBjtMgCAGdplAAAYoJIBAGNermQIGQAw5uU5GdplAAAzVDIAYMzLt5UhZADAmJfnZGiXAQDMUMkAgDEvT/wTMgBgzMvtMkIGAIx5uZJhTgYAYIZKBgCM0S4DAJjxcsjQLgMAmKGSAQBjMTmbvI+5NZBBQMgAgDHaZQCAIaO+vl6zZs1Sfn6+CgsLtXjxYl24cCHhmK6uLlVXV2vMmDEaNWqUlixZoo6ODtfHQsgAgLFeF7ZkNDc3q7q6WidPntTRo0fV09Oj+fPnq7OzM37MmjVr9Oabb+r1119Xc3Ozrly5oscff9zZC+2DLxaLpbTdFw6HFQgEFAqF5Pf7U3lpIO2N9PkGewieF5P0X5Irn1G3P+++IynbwfN0S3rFwZiuXbumwsJCNTc3a+7cuQqFQvrsZz+rffv26Wtf+5ok6fz585o8ebJaWlr04IMPOhhtIioZAMgQ4XA4YYtEInd1XigUkiQVFBRIktra2tTT06PKysr4MZMmTdL48ePV0tLi6pgJGQAw5la7rLS0VIFAIL7V19d/6rWj0ahqa2s1e/ZsTZ06VZIUDAaVnZ2t0aNHJxxbVFSkYDDo8NUmYnUZABhz695l7e3tCe2ynJycTz23urpa586d04kTJxyMYOAIGQDIEH6/P6k5mZqaGh0+fFjHjx/XuHHj4vuLi4vV3d2t69evJ1QzHR0dKi4udnPItMsAwFqqV5fFYjHV1NTowIEDOnbsmMrKyhIenzFjhkaMGKGmpqb4vgsXLujy5cuqqKgYwCvsH5UMABiLytkXKpNttVVXV2vfvn06dOiQ8vPz4/MsgUBAeXl5CgQCWrlyperq6lRQUCC/36/Vq1eroqLC1ZVlEiEDAOZS/Xsyu3btkiTNmzcvYf+ePXv0xBNPSJKef/55ZWVlacmSJYpEIqqqqtKLL77oYJR943syQBrhezKDz+J7Mo9LGuHgeXok/U+XxpRqVDIAYKxXzibAM/neZYQMABjzcsiwugwAYIZKBgCMpXriP52kPGRurzMIh8OpvjSQ9jL5x6mGitvvgZtrorzcLkt5yNy4cUPSx/fgAYB0dePGDQUCgcEeRsZLeciUlJSovb1d+fn58mXocs1wOKzS0tI77iOE1OO9SC9D4f2IxWK6ceOGSkpKXHtO2mUplJWVlXAPnUyW7H2EYIf3Ir1k+vvhdgWT6m/8pxNWlwEAzLC6DACM9UpyMjnAxL/H5OTkaNOmTXf1Ww6wxXuRXng/+ublOZmU37sMALzi9r3LZsvZ/6O/Jel/KTPvXcacDADADO0yADDGnAwAwIyX52RolwEAzFDJAIAx2mUAADMxOWt5ZfISYNplAAAzVDIAYMxpu4t2GQCgX14OGdplAAAzVDIAYCwqZ6vLMvl7MoQMABijXQYAgAEqGQAw5uVKhpABAGPMyQAAzDgNiUwOGeZkAABmqGQAwJiXKxlCBgCM9crZTS4zOWRolwEAzFDJAIAxL1cyhAwAGPPynAztMgCAGSoZADBGuwwAYCYqZyHDzy8DANAHKhkAMOb03mWZXMkQMgBgrFfeDRnaZQAAM1QyAGDMy5UMIQMARrKzs1VcXKxgMOj4uYqLi5Wdne3CqFLLF4vFMjkkASCtdXV1qbu72/HzZGdnKzc314URpRYhAwAww8Q/AMAMIQMAMEPIAADMEDIAADOEDADADCEDADBDyAAAzPwfV87f0xuDEBoAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 480x480 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "m, n = A.shape\n",
    "miters = np.zeros((n, n))\n",
    "\n",
    "for i in range(0, n):\n",
    "    for j in range(0, n):\n",
    "        eigs, iters = eig_qrshifts(A, refeig=i, sindex=j, verbose=False)\n",
    "        miters[i, j] += iters\n",
    "\n",
    "plt.matshow(miters, cmap='hot', interpolation='nearest')\n",
    "plt.colorbar()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c00ea4c",
   "metadata": {},
   "source": [
    "As we can see, using the last value along the diagonal as the shift $(s)$ converges the fastest for getting all $\\lambda$s to a precision on order $10^{-32}$. This is not an accident, rather it is because the last value along the diagonal is actually the **Rayleigh Quotient**, while the last column of each similar matrix is a better approximation of an eigenvector. To better understand why this is the case let's explore some other (in my opinion less effective) methods for computing $\\lambda$s.\n",
    "\n",
    "### Computing Max $\\lambda$ with Power Method (Von Mises Iteration Algorithm)\n",
    "\n",
    "The power method or Von Mises Iteration is a simple and old school way of computing the largest $\\lambda$ for a matrix $A$ using the Rayleigh Quotient. To use this method we'll choose a random vector $\\vec{x}_0$ and compute the following.\n",
    "\n",
    "$\\vec{x}_1 = \\frac{A \\vec{x}_0} {\\| A \\vec{x}_0 \\|}$\n",
    "\n",
    "The process will the repeat...\n",
    "\n",
    "$\\vec{x}_{n + 1} = \\frac{A \\vec{x}_n} {\\| A \\vec{x}_n \\|}$\n",
    "\n",
    "The idea here is that eventually $\\vec{x}$ will converge to an eigenvector $(\\vec{v})$.\n",
    "\n",
    "Then we can just use the Rayleigh Quotient to obtain the corresponding eigenvalue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "482a0caf",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eigenvalues for A:\n",
      " [149.49147857 -26.75672795  10.26524939]\n",
      "Eigenvectors for A:\n",
      " [[-0.39755815 -0.63646445  0.61843026]\n",
      " [-0.74050254  0.39976377 -0.76199621]\n",
      " [-0.54185192  0.65962257 -0.19210879]] \n",
      "\n",
      "Max eigenvalue approximtion: 149.49147856822398\n",
      "Corresponding eigenvector: [0.39755815 0.74050254 0.54185192]\n",
      "Iterations: 15\n"
     ]
    }
   ],
   "source": [
    "def powermethod(A):\n",
    "    x0 = np.random.rand(A.shape[1])\n",
    "    maxeig = 0\n",
    "    diff = 1\n",
    "    iters = 0\n",
    "    while diff >= 1e-8:\n",
    "        xn = np.dot(A, x0)\n",
    "        norm = np.linalg.norm(xn)\n",
    "        x0 = xn / norm\n",
    "        neweig = rquotient(x0, A)\n",
    "        diff = np.abs(maxeig - neweig)\n",
    "        maxeig = neweig\n",
    "        iters += 1\n",
    "    return maxeig, x0, iters\n",
    "\n",
    "meig = powermethod(A)[0]\n",
    "eigvec = powermethod(A)[1]\n",
    "iters = powermethod(A)[2]\n",
    "print(f\"Eigenvalues for A:\\n {A_eigvals}\")\n",
    "print(f\"Eigenvectors for A:\\n {A_eigvecs} \\n\")\n",
    "print(f\"Max eigenvalue approximtion: {meig}\")\n",
    "print(f\"Corresponding eigenvector: {eigvec}\")\n",
    "print(f\"Iterations: {iters}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97f80b84",
   "metadata": {},
   "source": [
    "This works perfectly fine, and with more iterations the approximation of the eigenvector and eigenvalue will get better. The problem here though is that it only get us the largest $\\lambda$. Further it took 15 iterations to compute just 1 $\\lambda$ where as the QR method with shifts gave all the $\\lambda$.\n",
    "\n",
    "How do we get the rest of the $\\lambda$s? Short answer is introduce shifts\n",
    "\n",
    "### Computing $\\lambda$s with the Inverse Iteration and Rayleigh Iteration Methods\n",
    "\n",
    "The ***inverse iteration*** method for computing $\\lambda$s is effectively just power method with some added steps. The following formula is the method used for computing an approximate eigenvector as was the case with power method, but instead using a shift $s$ and inverting matrices (which is a problem in of itself).\n",
    "\n",
    "$\\vec{x}_{n + 1} = \\frac{(A - sI)^{-1}\\vec{x}_n} {\\| (A - sI)^{-1}\\vec{x}_n \\|}$\n",
    "\n",
    "The shift $s$ for inverse iteration is just a guess or estimate of for a $\\lambda$. By choosing a good guess for the shift this method will produce the eigenvector and eigenvalue after using the Rayleigh Quotient to give us the eigenpair. The big problem here is that we need a good guess, for the shift, that is close to one of the $\\lambda$s. Also we need to repeat this process for as many $\\lambda$s there will be for a matrix, so it isn't the most efficient. Turns out though that if you choose the shift (s) to be the Rayleigh Quotient of the approximate eigenvector produced with each iteration this process is made much more efficient. That is what is known as ***Rayleigh Iteration***, and can be seen in the following code. This is (where I surmise) the idea of shifting and using the Rayleigh Quotient for speeding up the QR algorithm came from."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "b38fefb9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eigenvalues for A:\n",
      " [149.49147857 -26.75672795  10.26524939]\n",
      "Eigenvectors for A:\n",
      " [[-0.39755815 -0.63646445  0.61843026]\n",
      " [-0.74050254  0.39976377 -0.76199621]\n",
      " [-0.54185192  0.65962257 -0.19210879]] \n",
      "\n",
      "Guess 1:\n",
      "\n",
      "Eigenvalue approximtion: 149.49147856748237\n",
      "Corresponding eigenvector: [-0.39755815 -0.74050254 -0.54185192]\n",
      "Iterations: 6\n",
      "Guess 2:\n",
      "\n",
      "Cannot invert\n",
      "Guess 3:\n",
      "\n",
      "Eigenvalue approximtion: 10.265249385655864\n",
      "Corresponding eigenvector: [-0.61843026  0.76199621  0.19210879]\n",
      "Iterations: 7\n"
     ]
    }
   ],
   "source": [
    "def eig_rayleigh(A, s):\n",
    "    x0 = np.random.rand(A.shape[1])\n",
    "    diff = 1\n",
    "    eig = 0\n",
    "    iters = 0\n",
    "    while diff >= 1e-16:\n",
    "        shift = np.identity(len(A)) * s\n",
    "        invert = np.linalg.inv(A - shift)\n",
    "        top = np.dot(invert, x0)\n",
    "        norm = np.linalg.norm(top)\n",
    "        x0 = np.divide(top, norm)\n",
    "        neweig = rquotient(x0, A)\n",
    "        diff = np.abs(eig - neweig)\n",
    "        eig = neweig\n",
    "        s = neweig\n",
    "        iters += 1\n",
    "    return eig, x0, iters\n",
    "\n",
    "\n",
    "print(f\"Eigenvalues for A:\\n {A_eigvals}\")\n",
    "print(f\"Eigenvectors for A:\\n {A_eigvecs} \\n\")\n",
    "for num, i in enumerate(A_eigvals):\n",
    "    print(f\"Guess {num + 1}:\\n\")\n",
    "    try:\n",
    "        guess = i - 0.99\n",
    "        result = eig_rayleigh(A, guess)\n",
    "        print(f\"Eigenvalue approximtion: {result[0]}\")\n",
    "        print(f\"Corresponding eigenvector: {result[1]}\")\n",
    "        print(f\"Iterations: {result[2]}\")\n",
    "    except np.linalg.LinAlgError:\n",
    "        print(\"Cannot invert\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19f7dadd",
   "metadata": {},
   "source": [
    "Computing matrix inverses is tricky computationally/numerically and merits its own seperate discussion. So this (in my opinion) is not as effective as the QR algorithm or QR with shifts since we need to compute one $\\lambda$ at a time, need to pick a good guess, and hope that everything will invert (it doesn't always, run this code with other random matrices and python will throw an error your way eventually). But, my motivation behind sharing this method and power method is that:\n",
    "\n",
    "1. They are both methods that will yield $\\lambda$s\n",
    "2. It may provide some understanding of were the use of shifting came from (idk it just connects for me in my mind)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "929a6fd0",
   "metadata": {},
   "source": [
    "### References\n",
    "\n",
    "https://youtu.be/d32WV1rKoVk?si=J68lHihm_OBeYrrI\n",
    "\n",
    "https://pythonnumericalmethods.studentorg.berkeley.edu/notebooks/Index.html\n",
    "\n",
    "https://sci.utah.edu/~akil/docs/courses/2020fall/math6610/lec21.pdf\n",
    "\n",
    "https://sci.utah.edu/~akil/docs/courses/2020fall/math6610/lec20.pdf\n",
    "\n",
    "https://en.wikipedia.org/wiki/Eigenvalue_algorithm\n",
    "\n",
    "https://web.math.ucsb.edu/~padraic/ucsb_2013_14/math108b_w2014/math108b_w2014_lecture5.pdf\n",
    "\n",
    "https://youtu.be/Bt8o4Yn-71o?si=VDFbrGFBk7HdBirg\n",
    "\n",
    "https://johnfoster.pge.utexas.edu/numerical-methods-book/NumericalMethods.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0ab9ab54",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}