{
"cells": [
{
"cell_type": "markdown",
"id": "significant-services",
"metadata": {},
"source": [
"Basic Iterative Methods\n",
"=\n",
"\n",
"In this chapter we learn\n",
"\n",
"* The Richardson iteration\n",
"* The gradient method\n",
"* The Chebyshev method\n",
"* The conjugate gradients method\n",
"* Using preconditioners"
]
},
{
"cell_type": "markdown",
"id": "indoor-toronto",
"metadata": {},
"source": [
"We are given a linear system of equations\n",
"\n",
"$$\n",
"A x = b.\n",
"$$\n",
"\n",
"The matrix $A \\in {\\mathbb R}^{n\\times n}$ is so large such that direct elimination is not a good option. \n",
"Although this section applies to linear systems in general, we think \n",
"of equations arising from finite element discretization. Other numerical methods for partial differential equations lead to similar systems. Matrices from graph networks are another example."
]
},
{
"cell_type": "markdown",
"id": "small-rouge",
"metadata": {},
"source": [
"The situation is advantageous if the matrix is\n",
"* symmetric:\n",
"\n",
" $$A = A^T$$\n",
"* positive definite:\n",
"\n",
" $$x^T A x > 0 \\qquad \\forall \\, 0 \\neq x \\in {\\mathbb R}^n$$\n",
"\n",
"We call symmetric and positive definite matrices SPD.\n",
"\n",
"SPD matrices lead to the energy norm and the energy inner product defined as\n",
"\n",
"\\begin{align*}\n",
"\\| x \\|_A &= \\sqrt{ x^T A x } \\\\\n",
"\\left< x, y \\right>_A &= x^T A y\n",
"\\end{align*}"
]
},
{
"cell_type": "markdown",
"id": "numerical-turkish",
"metadata": {},
"source": [
"We do not assume that the matrix is stored as a dense matrix, i.e. all $n^2$ entries are stored in a two dimensional array.\n",
"\n",
"We only assume that the matrix-vector product\n",
"\n",
"$$\n",
"y := A * x\n",
"$$\n",
"\n",
"is computationally available. \n",
"\n",
"Typically, the algorithmic complexity of the matrix-vector product is $O(n)$. \n",
"\n",
"Often one stores the matrix in a sparse matrix format, such as the CSR (Compressed Sparse Row) format. https://de.wikipedia.org/wiki/Compressed_Row_Storage https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html\n",
"\n",
"\n",
"More general, the matrix-vector product can be any linear operator. We can think of the sum or product of linear operators, multiplying with the inverse of the diagonal, or solving a triangular (sparse) system by forward/backward substitution"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "personalized-europe",
"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.12.2"
}
},
"nbformat": 4,
"nbformat_minor": 5
}