3
$\begingroup$

I'm studying basic iterative methods and about solving PDEs with basic iterative methods. I came across the following text in my lecture notes

"In this section we revisit the convergence of BIMs applied to the discrete Poisson equation and reveal what causes their slow convergence. To this end we consider solving the linear system $$A^hu^h = f^h$$ resulting from finite difference discretisation of a PDE. The eigenmodes can be subdivided into low and high frequency modes. The low frequency modes are slowly varying grid vectors that correspond to the small eigenvalues of $A^h\in\mathbb{R}^{n\times n}$. We more precisely have that in one and two dimensions (of the PDE) the low frequency modes are the eigenvectors $v^{h,[k]}$ for $1\leq k\leq n/2$ and $v^{h,[kl]}$ for $1\leq k,l\leq n/2,$ respectively. The remaining eigenmodes are called the high frequency modes and correspond to oscillatory grid vectors."

I have never heard about eigenmodes or slowly varying grid vectors before, and this text doesn't make a lot of sense to me.

Question: What are high and low frequency eigenmodes in this example? What does it mean for a vector to be slowly varying or oscillating, and why do the slowly varying grid vectors correspond to the small eigenvector? What do the superscripts above the eigenvectors in the one or two dimensional case mean?

Thanks!

Thanks in advance!

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ What book is this? It might be helpful to provide a reference $\endgroup$ – Yuriy S Jan 31 '18 at 13:37
  • 1
    $\begingroup$ High and low frequency eigenmodes can be thought of as analogous to high and low frequency parts of the fourier transform. Something is high frequency is changes quickly, e.g. $\sin(100x)$ changes much more quickly than $\sin(x)$. Low frequency changes slowly, like a constant function or $\sin(\frac{x}{10})$. Slowly varying/oscillating are literally self-explanatory. The slowly varying grid vectors correspond to the smallest eigenvalue, not eigenvector. $\endgroup$ – TSF Jan 31 '18 at 13:47
  • 3
    $\begingroup$ You're asking quite a lot of questions the past few days. Please remember, this site works both ways - once you get an answer to your question, you are expected to return input by either explaining why none of the answers is what you needed, or by accepting the best answer. Please, don't post hit and run questions. $\endgroup$ – 5xum Jan 31 '18 at 14:36
  • $\begingroup$ @YuriyS I've printed out my lecture notes, sorry it's not a book! $\endgroup$ – titusAdam Jan 31 '18 at 15:39
  • 1
    $\begingroup$ @5xum Your comment is completely misguided and I don't understand why it was upvoted twice. I always accept answers and I always reply to comments! Don't try to make a point for the sake of making a point. $\endgroup$ – titusAdam Jan 31 '18 at 15:41
3
$\begingroup$

There are a lot of questions in your question, but I think the following answer tackles them all.

Consider the Laplace problem: \begin{align*} -Δu&=f \text{ in } Ω=[0,1]², \\ u &= 0 \text{ on } ∂Ω. \end{align*}

Using an equidistant grid of Ω with lexicographic numbering:

(0,1)                (1,1)
    x---x---x---x---x 
    |   |   |   |   |    
    x---7---8---9---x
    |   |   |   |   |
    x---4---5---6---x
    |   |   |   |   |
    x---1---2---3---x
    |   |   |   |   |
    x---x---x---x---x 
(0,0)                (1,0)

and the 5-point-star: $$Δ_h^{(5)}u_h(x,y) := h^{-2}\left\{u(x\pm h,y) + u(x,y\pm h) -4u(x,y)\right\}$$

will lead to the matrix: $$A_h = h^{-2}\pmatrix{B_m & -I_m \\ -I_m & B_m & -I_m \\ & \ddots &\ddots & \ddots}, B_m = \pmatrix{4 & -1 \\ -1 & 4 & -1 \\ & \ddots & \ddots & \ddots }$$

Here $m$ is the amount of points in one direction - so $m=3$ in the picture above.

The eigenvectors/eigenvalues of that matrix are defined by: $$Aw^{kl}=λ_{kl}w^{kl}.$$ and are given by: \begin{align*} λ_{kl} &= h^{-2}\left\{4-2(\cos(khπ)+\cos(lhπ))\right\}, \ k,l = 1,…,m \\ w^{kl} &= \left[\sin(ihkπ)\sin(jlhπ)\right]_{i,j=1,…,m}∈ℝ^{n} \\ \end{align*} Note that $n=m^2$. And $h$ is just the size of one cell: $h=\frac{1}{(m+1)}$.

The eigenvalues get small for $k,l$ tending to 1 ($λ_{11}=λ_{min}$), and large for $k,l$ close to $m$. So we already have the division into "small" and "large" eigenvalues simply by saying an eigenvalue is small if: $$1\leq k,l\leq n/2,$$ without defining what "small" really is. Note that using this definition only one fourth of the eigenvalues are "small". That is just because you have a sinus term in both dimensions.

Small remark, while we are in this topic: The smallest eigenvalue is bounded by $λ_{min}\approx 2π²$, while the largest is given by $λ_{max}=8h^{-2}$. Hence the bad condition number of $A_h$.

The frequency of a sinus-wave with respect to the time is given by $w(t) = \sin(2πft)$. Therefore, the frequency with respect to the grid-size $h$ is given by: $$f_1 = \frac{ik}{2}, \qquad f_2 = \frac{jl}{2}$$ So if $k$ or $l$ is "large", in the way we defined it precisely above, the freqency is also large.


Why is that freqency stuff interesting?
The first application that comes to my mind is the multigrid method.

For the multigrid method you have several grids containing each other. Each of them is finer. In the simplest case imagine dividing all cells of the coarse grid into four smaller cells each. If the finer grid has gridsize $h$, then the coarse grid has gridsize $2h$.

In the simplest case (V-cycle) a Multigrid step consists of transforming the solution from the finest level to the coarsest level. Solving there, and then transforming back the the finest level. After each transformation (on each grid level) you do smoothing steps using the Richardson iteration or Gauß-Seidel method. (Multigrid on wikipedia.)

Let's have a closer look at that smoothing. Consider beeing on the grid with grid-size $h$. There the equation system is given by $$A_hx_h = b_h,$$

which is just the finite representation of $Δu=f$.

Let $\{w_h^{i}, i=1,…,N\}$ denote the orthonormal system of eigenvectors of $A_h$, ordered by the eigenvalues $λ_{min}=λ_1 ≤ … ≤ λ_N=λ_{max}$. (I want to get rid of the double index, and I don't care about how the exact order in double-index notation is.)

Then the Richardson iteration is given by:

$$x_h^{t+1} = (I_h-θA_h)x_h^{(t)} + θb_h$$ with the damping factior $0<θ<1$.

The error is given by: $$x_h^{(0)} - x_h = \sum_{i=1}^N ε_iw^{i}_h$$ using the orthonormal basis, $ε_i∈ℝ$ the coefficient to each basis vector.

Then, doing some calculation, one can derive at: $$|x_h^{(t)}-x_h^{(0)}|²=|(I_h-θA_h)^t(x_h^{(1)}-x_h^{(0)})|²=\sum_{i=1}^N ε_i²(1-θλ_i)^{2t}.$$

Note that $t$, the step of the iteration, is not in the exponent of $ε_i$.

So the damping of the error components depends on the magnitude of the eigenvalues. For convergence we need $0<θ≤λ_{max}^{-1}$.
And it is $|1-θλ_i|<<1$ for large $λ_i$. Hence, higher frequent components of the error get damped faster than lower frequent components. (The same also works for the residual.)

This means, that the high frequent error terms on the finer grid get smoothed after a few Richardson steps. So the approximations on the coarse grid should (hopefully) be good for these higher frequent terms. Using several layers in the multigrid level will lead to the smoothing of lower frequent componenst - as they get "higher frequent" with coarsening the mesh.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ Thanks this is amazing! $\endgroup$ – titusAdam Jan 31 '18 at 18:27
  • $\begingroup$ seconded @titusAdam 's comment. ooc why do you call it sinus wave? I had seen that recently and thought it were a false spell-correct but yours is a more serious treatise so i'm wondering if that were truly a thing? $\endgroup$ – javadba May 17 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.