Review-11-Partial-Differential-Equations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Review-11-Partial-Differential-Equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Answers to review questions from Chapter 11: Partial Differential Equations <cite data-cite=\"heath2018scientific\">(Heath, 2018)</cite>.\n",
    "\n",
    "---\n",
    "Questions marked with $\\bigtriangledown$ are considered more difficult."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.1. True or false: For solving a time-dependent partial differential equation, a finite difference method that is both consistent and stable con- verges to the true solution as the step sizes in time and in space go to zero.\n",
    "\n",
    "True. From **Lax Equivalence Theorem**: consistency and stability necessary and sufficient for convergence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.2. True or false: The Gauss-Seidel iterative method for solving a system of linear equations Ax = b always converges.\n",
    "\n",
    "False. The Gauss-Seidel method does not always converge, but it is guaranteed to converge under conditions that are often satisfied in practice and are somewhat weaker than those for the Jacobi method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.3. True or false: The Gauss-Seidel method is a special case of SOR (successive over-relaxation) for solving a system of linear equations.\n",
    "\n",
    "False. Gauss-Seidel is a special case of the class of methods referred to as **stationary methods**.  These methods use the technique of splitting to rewrite the matrix $A$ in the system $Ax = b$. However setting the relaxation parameter value to one in SOR results is equivalent to the Gauss-Seidel method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.4. How does a semidiscrete method differ from a fully discrete method for solving a time- dependent partial differential equation?\n",
    "\n",
    "A semidiscrete method obtains a solution by discretizing in space, but leaving time independent.  The Method of Lines is an example of a semidiscrete method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.5. (a) Explain briefly the method of lines for solving an initial value problem for a time- dependent partial differential equation in one space dimension.\n",
    "(b) How might the method of lines be used to solve a pure boundary value problem for a time- independent PDE in two space dimensions?\n",
    "\n",
    "(a) The **Method of Lines** approximates the solution to the PDE at $u(t_k, x_i)$ by solving the initial value problem (IVP) at each of the $n$ spatial mesh points $x_i$ using finite differences.\n",
    "\n",
    "(b) Assume the space dimensions are x and y. Pick one of the space dimensions to discretize, say x, and use the boundary values as initial values when computing the solution to the IVP at each mesh point $x_i$.  The solution at each mesh point $u(x_i, y)$ will be a continous function of the unselected space dimension y."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.6. Other than the usual concerns of stability and accuracy, what additional important consider- ation enters into the choice of a numerical method for solving a system of ODEs arising from semidis- cretization of a PDE using the method of lines?\n",
    "\n",
    "The system of ODEs obtained from the method of lines become **stiff** as the mesh size $\\Delta x$ becomes small."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bigtriangledown$\n",
    "\n",
    "> 11.7. In using a fully discrete finite difference method for solving a time-dependent partial dif- ferential equation with one space dimension, can the sizes of the time step and space step be chosen independently of each other? Why?\n",
    "\n",
    "The mesh spacing used for the spatial mesh points $\\Delta x$ are independent from the mesh spacing used for temporal mesh points  $\\Delta t$. However, they must be chosen so as to respect each other's domain of dependence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.8. Fully discrete finite difference and finite el- ement methods for solving boundary value prob-lems convert the original differential equation into a system of algebraic equations. Why does the re- sulting n × n linear system usually require far less work to solve than the usual O(n3) that might be expected?\n",
    "\n",
    "The linear system obtained from a fully discrete finite difference and finite elements is tridiagonal.  A tridiagonal system of bandwidth $\\beta=3$ requires only $O(3n)$ storage and $O(9n)$ work to factorize using LU factorization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.9. Which of the following types of partial dif- ferential equations are time-dependent?\n",
    "(a) Elliptic\n",
    "(b) Parabolic\n",
    "(c) Hyperbolic\n",
    "\n",
    "(a) Elliptic PDE are time-independent.  Canonical example is Laplace equation $u_{xx} + u_{yy} = 0$. \n",
    "\n",
    "(b) Parabolic PDE are time-dependent. Canonical example is heat equation $u_t = cu_{xx}$.\n",
    "\n",
    "(c) Hyperbolic PDE are time-dependent. Canonical example is wave equation $u_{tt} = cu_{xx}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.10. Classify each of the following partial dif- ferential equations as hyperbolic, parabolic, or el- liptic. Also, state whether each equation is time- dependent or time-independent.\n",
    "(a) Laplace equation\n",
    "(b) Wave equation\n",
    "(c) Heat equation\n",
    "(d ) Poisson equation\n",
    "\n",
    "(a) Laplace equation is time-independent elliptic PDE.\n",
    "\n",
    "(b) Wave equation is time-dependent hyperbolic PDE.\n",
    "\n",
    "(c) Heat equation is time-dependent parabolic PDE.\n",
    "\n",
    "(d) Poisson equation is time-independent elliptic PDE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.11. What is meant by the stencil of a finite difference method for solving a PDE numerically?\n",
    "\n",
    "The stencil describes the neighborhood of points in the mesh used to compute the finite difference.  For example, the stencil of a fully discrete explicit finite difference method will only use mesh points from previous time-steps to compute the current time-step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.12. The heat equation ut = cuxx with ap- propriate initial and boundary conditions can be solved numerically by using a second-order, cen- tered finite difference approximation for uxx and then solving the resulting system of ordinary dif- ferential equations in time by some numerical method.\n",
    "(a) On what ODE method in time is the Crank- Nicolson method based?\n",
    "(b) What advantage does the Crank-Nicolson\n",
    "method have over the use of the backward Euler method? (c) What fundamental advantage do both of these methods have over the use of Euler’s method?\n",
    "\n",
    "Heat equation is a time-dependent parabolic PDE $u_t = cu_{xx}$.\n",
    "\n",
    "(a) Crank-Nicolson is based on the trapezoid method.\n",
    "\n",
    "(b) Crank-Nicolson is second-order accurate in space and time whereas the backward Euler method is first-order accurate.\n",
    "\n",
    "(c) Crank-Nicolson and backward Euler methods are implicit methods which means that they are unconditionally stable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.13. In solving the Laplace equation on the unit square using the standard second-order cen- tered finite difference scheme in both space di- mensions, what is the maximum number of un- known solution variables that are involved in any one equation of the resulting linear algebraic sys- tem?\n",
    "\n",
    "There are 5 unknowns: 4 neighbors arranged in `+`-shaped stencil around 1 central mesh point."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bigtriangledown$\n",
    "\n",
    "> 11.14. Consider the numerical solution of the heat equation, ut = c uxx , by a fully discrete finite difference method. For the spatial discretization, suppose that we approximate the second deriva- tive by the standard second-order centered differ- ence formula.\n",
    "(a) Why is Euler’s method impractical for the time integration?\n",
    "(b) Name a method for numerically solving the heat equation that is unconditionally stable and second-order accurate in both space and time.\n",
    "(c) On what ODE method is the time integration in this method based?\n",
    "\n",
    "Heat equation is a time-dependent parabolic PDE $u_t = cu_{xx}$.\n",
    "\n",
    "(a) Euler's method provides a solution for a continuous indepdendent variable whereas in a fully discrete finite difference method there is more than one dimension and all dimensions are discretized.\n",
    "\n",
    "(b) Crank-Nicolson implicit method is unconditionally stable and second-order accurate.\n",
    "\n",
    "(c) The time integration of the Crank-Nicolson method is based on the trapezoid method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.15. Implicit finite difference methods for solv- ing time-dependent PDEs require the solution of a system of equations at each time step. In using the backward Euler or trapezoid method to solve the heat equation in one space dimension, what is the nonzero pattern of the matrix of the linear system to be solved at each time step?\n",
    "\n",
    "The linear system to solve for the implicit method is tridiagonal with coefficients $[\\alpha, -2 \\alpha - 1, \\alpha]$ where $\\alpha$ is a constant multiple on the centered difference. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.16. (a) For a finite difference method for solv- ing a PDE numerically, what is meant by the terms consistency, stability, and convergence?\n",
    "(b) How does the Lax Equivalence Theorem relate these terms to each other?\n",
    "\n",
    "(a)\n",
    "\n",
    "1. Consistency\n",
    "  * Local truncation error goes to zero.\n",
    "  * Avoids accumulation of local error into global error.\n",
    "2. Stability\n",
    "  * Approximate solution at any time $t$ as $\\Delta t \\rightarrow 0$ is bounded.\n",
    "3. Convergence\n",
    "  * Convergence occurs when the solution of a PDE approaches the true solution.\n",
    "\n",
    "(b) **Lax Equivalence Theorem**: consistency and stability together are necessary and sufficient for convergence.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bigtriangledown$\n",
    "\n",
    "> 11.17. Suppose you are solving the heat equation ut = uxx by applying an ODE method to solve the semidiscrete system of ODEs resulting from spa- tial discretization using the standard second-order centered difference approximation to the second derivative. Each of the following ODE methods then gives a time-stepping procedure that may or may not be consistent, stable, or convergent. State which of these three properties, if any, ap- ply for each method listed (note that none, one, or more than one of the properties may apply in a given case).\n",
    "(a) Euler’s method with ∆t = ∆x (b) Backward Euler method with ∆t = ∆x\n",
    "(c) The “zero method,” which produces the an- swer 0 at every time step\n",
    "\n",
    "Heat equation is a time-dependent parabolic PDE $u_t = cu_{xx}$.\n",
    "\n",
    "(a) Euler's method is an explicit method with first-order accuracy, but without the stability guarantees of an implicit method.  Instead the convergence will depend upon the stability of the ODE itself.\n",
    "\n",
    "(b) Backward Euler method is unconditionally stable and first-order accurate so consistency isn't guaranteed and thus neither is convergence.\n",
    "\n",
    "(c) The zero method is unconditionally stable, but not accurate so consistency isn't guaranteed and thus neither is convergence.  In general, the convergence of this solution will be worse than backward Euler. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 1.18. List two advantages and two disadvan- tages of iterative methods compared with direct methods for solving large sparse systems of linear algebraic equations.\n",
    "\n",
    "Advantages of Iterative Methods\n",
    "1. Some methods do not require matrix to be stored.\n",
    "2. May be more efficient than direct methods when high accuracy not required.\n",
    "\n",
    "Disadvantages of Iterative Methods\n",
    "1. Poor rates of convergence for methods such as Jacobi and Gauss-Seidel.\n",
    "2. Place requirements on the input data eg conjugate gradient requires a positive definite matrix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.19. What principal feature limits the useful- ness of direct methods based on matrix factoriza- tion for solving very large sparse systems of linear equations?\n",
    "\n",
    "As the size of the matrix grows, the work and storage required to factorize the matrix grows.  Methods for representing sparse matrices help reduce the cost of storage, but factorization introduces new nonzero entries into the matrix, termed **fill**, which must be handled specially and make factorizating sparse matrices more complicated."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.20. What is the computational complexity of a fast Poisson solver for a problem with n mesh points?\n",
    "\n",
    "FFT can be used to compute solution to certain kinds of elliptic BVP such as the Poisson problem in $O(n \\log n)$ work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.21. What is meant by fill in the factorization of a sparse matrix?\n",
    "\n",
    "Fill is the introduction of nonzero entries into a sparse matrix as a result of factorization."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.22. Explain briefly the minimum degree algo- rithm for reordering a symmetric positive definite sparse matrix to limit fill in its Cholesky factor.\n",
    "\n",
    "Minimum degree limits fill by **first** eliminating nodes with **fewest** neighbors (eg smallest degree)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.23. Explain briefly the nested dissection algo- rithm for reordering a symmetric positive definite sparse matrix to limit fill in its Cholesky factor.\n",
    "\n",
    "Nested disection recursively selects and numbers nodes which split the graph into 2 pieces of roughly equal size. No node in either piece is connected to a node in the other, hence no fill due to elimination of any node in the other."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.24. What is the general form of a station- ary iterative method for solving a system of linear equations Ax = b?\n",
    "\n",
    "Choose $G$ and $c$ such that $Gx + c$ is a solution to $Ax = b$.\n",
    "$$\n",
    "x_{k+1} = G x_k + c\n",
    "$$\n",
    "\n",
    "Method called **stationary** since $G$ and $c$ are fixed over all iterations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.25. (a) What is meant by a splitting of a ma- trix A?\n",
    "(b) What form of iterative method for solving a linear system Ax = b results from such a split- ting?\n",
    "(c) What condition on the splitting guarantees that the resulting iterative scheme is locally con- vergent?\n",
    "(d) For the matrix $A = [[4, 1], [1, 4]]$ what is the splitting for the Jacobi method?\n",
    "(e) For the same matrix as in part d, what is the splitting for the Gauss-Seidel method?\n",
    "\n",
    "(a) Rewrite $A$ as $A = M - N$. The iteration scheme becomes: \n",
    "$$\n",
    "x_{k+1} = M^{-1} N x_k + M^{-1} b\n",
    "$$\n",
    "\n",
    "(b) Use fixed-point iteration to solve.\n",
    "\n",
    "(c) The iteration scheme is convergent if the spectral radius of the Jacobian matrix $J = G = M^{-1} N$ is less than 1 eg $\\rho(G) < 1$.  The smaller the value of $\\rho(G)$ the faster the convergence.\n",
    "\n",
    "(d) For the Jacobi method, the splitting of $A$ is given by:\n",
    "* $M = D$ where $D$ is formed from the diagonals of $A$.\n",
    "* $N = -(L + U)$ where $L$ and $U$ contain the lower and upper triangular portions of $A$.\n",
    "\n",
    "$$\n",
    "A = \n",
    "\\begin{bmatrix}\n",
    "4 & 1 \\\\\n",
    "1 & 4 \\\\\n",
    "\\end{bmatrix}, \\qquad\n",
    "M = \n",
    "\\begin{bmatrix}\n",
    "4 & 0 \\\\\n",
    "0 & 4 \\\\\n",
    "\\end{bmatrix}, \\qquad\n",
    "N = \n",
    "\\begin{bmatrix}\n",
    "0 & -1 \\\\\n",
    "-1 & 0 \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "(e) For the Gauss-Seidel method, the splitting of $A$ is given by:\n",
    "* $M = D + L$\n",
    "* $N = -U$\n",
    "\n",
    "$$\n",
    "A = \n",
    "\\begin{bmatrix}\n",
    "4 & 1 \\\\\n",
    "1 & 4 \\\\\n",
    "\\end{bmatrix}, \\qquad\n",
    "M = \n",
    "\\begin{bmatrix}\n",
    "4 & 0 \\\\\n",
    "1 & 4 \\\\\n",
    "\\end{bmatrix}, \\qquad\n",
    "N = \n",
    "\\begin{bmatrix}\n",
    "0 & -1 \\\\\n",
    "0 & 0 \\\\\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.26. In solving a nonsingular system of linear equations Ax = b, what property of the ma- trix A would necessarily cause the Jacobi iterative method to fail outright?\n",
    "\n",
    "The iteration scheme of the Jacobi method is:\n",
    "$$\n",
    "x_{k+1} = D^{-1}(b - (L + U)x_k)\n",
    "$$\n",
    "\n",
    "The method will fail outright if $D$ is singular eg $D^{-1}$ does not exist or if there is a zero on the diagonal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.27. Which of the following methods for solv- ing a linear system are stationary iterative meth- ods?\n",
    "(a) Jacobi method\n",
    "(b) Steepest descent method (c) Iterative refinement\n",
    "(d) Gauss-Seidel method\n",
    "(e) Conjugate gradient method (f ) SOR method\n",
    "\n",
    "(a) Jacobi method is stationary\n",
    "\n",
    "(b) Steepest descent method is **not** stationary (see Section 6.5)\n",
    "\n",
    "(c) Iterative refinement is stationary (see Section 2.11)\n",
    "\n",
    "(d) Gauss-Seidel is stationary\n",
    "\n",
    "(e) Conjugate gradient method is **not** stationary\n",
    "\n",
    "(f) SOR method is stationary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.28. (a) In words (or formulas if you prefer), describe the difference between the Jacobi and Gauss-Seidel iterative methods for solving a sys- tem of linear algebraic equations.\n",
    "(b) Which method is more rapidly convergent? (c) Which method requires less storage for the suc- cessive approximate solutions?\n",
    "\n",
    "(a) Jacobi and Gauss-Seidel are both stationary iterative methods, but they differ in how the matrix $A$ is split in the fixed-point iteration.\n",
    "\n",
    "(b) Gauss-Seidel converges more rapidly than Jacobi.\n",
    "\n",
    "(c) The Jacobi method requires double storage for the vector x because all of the old component values are needed throughout the sweep, and therefore the new component values cannot overwrite them until the sweep has been completed.  In contrast, a benefit of the Gauss-Seidel method is that duplicate storage is not needed for the vector x, since the newly computed component values can overwrite the old ones immediately."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.29. Listed below are several properties that may pertain to various methods for solving sys- tems of linear equations. For each of the proper- ties listed, state whether this quality more accu- rately describes direct or iterative methods.\n",
    "(a) The entries of the matrix are not altered dur- ing the computation.\n",
    "(b) A prior estimate for the solution is helpful. (c) The matrix entries are stored explicitly, using a standard storage scheme such as an array.\n",
    "(d) The work required depends on the condition- ing of the problem.\n",
    "(e) Once a given system has been solved, another system with the same matrix but a different right- hand side is easily solved.\n",
    "(f ) Acceleration parameters or preconditioners are usually employed.\n",
    "(g) The maximum possible accuracy is relatively easy to attain.\n",
    "(h) “Black box” software is relatively easy to im- plement.\n",
    "(i) The matrix can be defined implicitly by its ac- tion on an arbitrary vector.\n",
    "(j) A factorization of the matrix is usually per- formed.\n",
    "(k) The amount of work required can often be de- termined in advance.\n",
    "\n",
    "(a) Iterative methods do not require explicit storage of matrix entries.\n",
    "\n",
    "(b) Iterative methods generally require an initial guess.\n",
    "\n",
    "(c) Direct methods use explicit storage.\n",
    "\n",
    "(d) The speed of convergence of iterative methods depends on conditioning.  In general, the more ill-conditioned the problem, then the more work required to converge.\n",
    "\n",
    "(e) Direct methods such as LU factorization can be used to solve multiple right hand sides.\n",
    "\n",
    "(f) Preconditioners may be required for use with the conjugate gradient (CG) iterative method.\n",
    "\n",
    "(g) Iterative methods are more efficient if high accuracy is **not** needed.  As a result, use direct methods for high accuracy.\n",
    "\n",
    "(h) Direct methods are more suitable as black boxes whereas iterative methods tend to be more easily hard-coded to the problem.\n",
    "\n",
    "(i) Iterative methods do not require explicit representation of the matrix.\n",
    "\n",
    "(j) Direct methods typically use LU or Cholesky factorization to solve.\n",
    "\n",
    "(k) The work required to solve is easier to determine in advance for direct methods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.30. Let A be a nonsingular matrix. Denote the strict lower triangular portion of A by L, the diagonal of A by D, and the strict upper triangle of A by U.\n",
    "(a) Express the Jacobi iteration scheme for solv- ing the linear system Ax = b in terms of L, D, and U. (b) Express the Gauss-Seidel iteration scheme for solving the linear system Ax = b in terms of L, D, and U.\n",
    "\n",
    "(a) Jacobi iteration scheme: $x_{k+1} = D^{-1}(b - (L + U)x_k)$\n",
    "\n",
    "(b) Gauss-Seidel iteration scheme: $x_{k+1} = (D + L)^{-1}(b - Ux_k)$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.31. What are the usual bounds on the relax- ation parameter ω in the SOR method?\n",
    "\n",
    "We always have $0 < \\omega < 2$ (otherwise the method diverges), but choosing a specific value of $\\omega$ to attain the best possible convergence rate is a difficult problem in general and is the subject of an elaborate theory for special classes of matrices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.32. Rank the following iterative methods for solving systems of linear equations in order of their usual speed of convergence, from fastest to slow- est:\n",
    "(a) Gauss-Seidel\n",
    "(b ) Jacobi\n",
    "(c) SOR with optimal relaxation parameter ω\n",
    "\n",
    "1. Fastest: SOR\n",
    "2. Middle: Gauss-Seidel\n",
    "3. Slowest: Jacobi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.33. The conjugate gradient method for solv- ing a symmetric positive definite system of linear equations is in principle a direct method. Why is it used in practice as an iterative method instead?\n",
    "\n",
    "When CG is used as a direct method, the rounding error causes a loss of orthogonality that spoils the finite termination property.  As a result, CG is usually used in an iterative manner and halted when the residual, or some other measure of error, is sufficiently small."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.34. What two key features largely account for the effectiveness of the conjugate gradient method for solving large sparse symmetric positive definite linear systems?\n",
    "\n",
    "1. Short recurrence means that we only need to keep prior two gradients as history.\n",
    "2. Minimal error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.35. When using the conjugate gradient method to solve a system of linear algebraic equa- tions Ax = b, how can you accelerate its conver- gence rate?\n",
    "\n",
    "Preconditioners can accelerate convergence of CG method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.36. (a) What is meant by preconditioning in the conjugate gradient method?\n(b) List at least two types of preconditioners used with the conjudate gradient method.",
    "\n",
    "(a) Preconditioning means implicitly multiplying A by some matrix to improve its conditioning\n.",
    "(b) Commonly used preconditioners include diagonal, block diagonal, SSOR, incomplete factorization, polynomial and approximate inverse.\n."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.37. Why are some stationary iterative meth- ods for solving linear systems sometimes called smoothers ?\n",
    "\n",
    "Stationary iterative methods exhibit asymptotic convergence.\n",
    "* Make rapid initial progress to remove high-frequency error.\n",
    "* Make slow progress to remove low-frequency error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 11.38. Explain briefly the basic idea of multigrid methods.\n",
    "\n",
    "Multigrid methods vary the spacing of the mesh to adjust the convergence rate of the method.\n",
    "* Restriction or Injection: Transition from finer to coarser grid.\n",
    "* Interpolation or Prolongation: Transition from coarser to finer grid."
   ]
  },
  {
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}