{ "cells": [ { "cell_type": "markdown", "id": "81b1d2f0", "metadata": {}, "source": [ "---\n", "title: \"Jacobi & Gauss-Seidel Methods\"\n", "subtitle: \"Lecture 8: Introduction to Chapter 2: Iterative Methods in Matrix Algebra\"\n", "date: 2026-02-18\n", "abstract-title: Overview\n", "abstract: | \n", " (1) Reminders on matrix analysis, \n", " (2) Jacobi & Gauss-Seidel\n", "format:\n", " html:\n", " other-links:\n", " - text: This notebook\n", " href: L8.ipynb\n", "---" ] }, { "cell_type": "markdown", "id": "63cf0867", "metadata": {}, "source": [ "::: {.callout-note}\n", "\n", "I encourage you to play around with the juptyer notebook for this lecture - you can copy the code with the ```this notebook``` button on the side of this page.\n", "\n", ":::\n", "\n", "::: {.callout-warning}\n", "\n", "These notes are mainly a record of what we discussed and are not a substitute for attending the lectures and reading books! If anything is unclear/wrong, let me know and I will update the notes.\n", "\n", ":::\n", "\n", "::: {.callout-tip}\n", "\n", "This lecture is mostly based on @Burden sections 7.1-7.3.\n", "\n", ":::" ] }, { "cell_type": "code", "execution_count": 2, "id": "db6fe346", "metadata": {}, "outputs": [], "source": [ "#| echo: false\n", "\n", "# IF YOU ARE READING THIS, THANK YOU\n", "# FOR DOWNLOADING THE LECTURE NOTES.\n", "# THE FIRST PERSON TO LET ME KNOW,\n", "# WINS SOME CHOCOLATES OF YOUR CHOICE\n", "\n", "using Plots, LaTeXStrings" ] }, { "cell_type": "markdown", "id": "5ea01014", "metadata": {}, "source": [ "## Recap: Matrix Analysis\n", "\n", "@Burden 7.1 - 7.2\n", "\n", "We will define $\\|\\cdot\\|_{p}$ to be the induced matrix norm from the vector norm $|\\cdot|_p$: that is,\n", "\n", "\\begin{align}\n", " |x|_p := \\begin{cases}\n", " \\big(\\sum_{i=1}^n|x_i|^p\\big)^{\\frac1p}, &\\text{if } 1\\leq p < \\infty\\\\\n", " %\n", " \\max_{1\\leq i\\leq n} |x_i|, &\\text{if } p= \\infty.\n", " \\end{cases}\n", "\\end{align}\n", "\n", "and\n", "\n", "\\begin{align}\n", " \\|A\\|_p := \\max_{|x|_p = 1} |Ax|_p\n", " %\n", " = \\max_{ x \\not= 0} \\frac{|Ax|_p}{|x|_p}.\n", "\\end{align}\n", "\n", "Notice that $|Ax|_p \\leq \\|A\\|_p |x|_p$.\n", "\n", "You can use ```LinearAlgebra``` to work with matrices in Julia:" ] }, { "cell_type": "code", "execution_count": 3, "id": "607e643d", "metadata": {}, "outputs": [], "source": [ "using LinearAlgebra" ] }, { "cell_type": "markdown", "id": "93e0c919", "metadata": {}, "source": [ "::: {#exr-1}\n", "\n", "Compute $\\| A \\|_2$ and $\\| A\\|_{\\infty}$ when \n", "\n", "\\begin{align}\n", "A = \\begin{pmatrix}\n", " 1 & 0 \\\\ -1 & 1 \n", "\\end{pmatrix}.\n", "\\end{align}" ] }, { "cell_type": "code", "execution_count": 4, "id": "3a9a5d8a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Matrix{Int64}:\n", " 1 0\n", " -1 1" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = [1 0; -1 1]" ] }, { "cell_type": "code", "execution_count": 5, "id": "c20bf1af", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(1.6180339887498951, 2.0)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "opnorm(A), opnorm(A,Inf)" ] }, { "cell_type": "markdown", "id": "d4ce2d4d", "metadata": {}, "source": [ ":::\n", "\n", "::: {.callout-tip}\n", "\n", "You can show \n", "\n", "\\begin{align}\n", " \\| A \\|_\\infty = \\max_{1\\leq i \\leq n} \\sum_{j=1}^n |A_{ij}|\n", "\\end{align}\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "76cc7786", "metadata": {}, "source": [ "::: {.callout-warning}\n", "\n", "In Julia, ```norm(A)``` is the *Frobenius norm*:\n", "\n", "\\begin{align}\n", " \\| A \\|_{\\mathrm{F}} := \\sqrt{\\sum_{ij} |A_{ij}|^2}\n", "\\end{align}\n", "\n", "which is not an induced matrix norm.\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "9d12fea3", "metadata": {}, "source": [ "::: {#exr-2}\n", "\n", "Find the eigenvalues and eigenvectors of \n", "\n", "\\begin{align}\n", "A = \\begin{pmatrix}\n", " 0 & 1 \\\\ -1 & 0 \n", "\\end{pmatrix}.\n", "\\end{align}\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "5f3994a5", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Matrix{Int64}:\n", " 0 1\n", " -1 0" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = [0 1 ; -1 0]" ] }, { "cell_type": "code", "execution_count": 7, "id": "7c0976b0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Eigen{ComplexF64, ComplexF64, Matrix{ComplexF64}, Vector{ComplexF64}}\n", "values:\n", "2-element Vector{ComplexF64}:\n", " 0.0 - 1.0im\n", " 0.0 + 1.0im\n", "vectors:\n", "2×2 Matrix{ComplexF64}:\n", " 0.707107-0.0im 0.707107+0.0im\n", " 0.0-0.707107im 0.0+0.707107im" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "λ, v = eigen(A)" ] }, { "cell_type": "code", "execution_count": 8, "id": "c44eebba", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0.0 + 0.0im, 0.0 + 0.0im)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "det(A - λ[1]I), det(A - λ[2]I)" ] }, { "cell_type": "code", "execution_count": 9, "id": "acfc6e32", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(ComplexF64[0.0 + 0.0im, 0.0 + 0.0im], ComplexF64[0.0 + 0.0im, 0.0 + 0.0im])" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(A - λ[1]I) * v[:,1], (A - λ[2]I) * v[:,2]" ] }, { "cell_type": "markdown", "id": "a9bdbe87", "metadata": {}, "source": [ ":::" ] }, { "cell_type": "markdown", "id": "1b41f72f", "metadata": {}, "source": [ "We will write $\\sigma(A) := \\{ \\lambda : \\exists x \\not= 0 \\text{ s.t. } A x = \\lambda x \\}$ for the set of eigenvalues of $A$. The *spectral radius* $\\rho(A)$ is defined as\n", "\n", "\\begin{align}\n", " \\rho(A) := \\max_{\\lambda \\in \\sigma(A)} |\\lambda|.\n", "\\end{align}\n", "\n", "::: {#lem-rho}\n", "\n", "$\\rho(A) \\leq \\|A\\|$ for every submultiplicative matrix norm.\n", "\n", ":::\n", "\n", "