-1
$\begingroup$

Can anybody explain me the relation between the condition of a Matrix and the convergency of a problem. For example how is the relation between the condition of the stiffness Matrix occuring in FEM to the convergency of the FEM method?

Thank you!


Note: For example I want to solve problem In weak formulation: find $u\in H^1_{\Gamma_D}(\Omega)$ for $f\in L^2(\Omega)$, $g_D\in H^{\frac{1}{2}}(\Gamma_D)$ and $g_N \in L^2(\Gamma_N)$ such that for all $v\in H^{1}_0$

\begin{equation*} a(u,v) := \int\limits_{\Omega} \nabla u A \nabla v \, d\Omega = \int\limits_{\Omega} v^T f \, d\Omega + \int\limits_{\Gamma_N} v^T g_N \,d\Gamma:= \ell(v) \end{equation*}

with $A$ a bounded self-adjoint and elliptic linear operator and $\partial\Omega = \Gamma_D \cup \Gamma_N$ and $\Gamma_D \cap \Gamma_N = \emptyset$.

Using the Galerkin approach and defining \begin{align*} A:=(a(\varphi_i,\varphi_j))_{i,j = 1}^n, \quad \quad f := (\ell(\varphi_1),\ldots,\ell(\varphi_n))^T, \quad \quad u :&= (u_1,\ldots,u_n)^T \end{align*} the problem can be written as \begin{align}\label{eq:LGS} A u = f. \end{align}

Now my question is what does $cond(A)$ tells me about the convergency of FEM for this problem?

$\endgroup$
  • 1
    $\begingroup$ What kind of matrix? Jacobian, gradient, Hessian or something else? Optimize or solve system of equation? Are there any constraints? $\endgroup$ – R zu Oct 28 '18 at 17:33
  • $\begingroup$ The Stiffness matrix which occurs for example using FEM for an elliptic linear PDE. Maybe i should make a clearer post with more details. Let me change it in the o.g. post. $\endgroup$ – Kerem Oct 28 '18 at 17:39
  • $\begingroup$ Hi welcome to scicomp, if I understand your question, I suppose it is about the convergence of linear solver for the system $Au=f$ (different from the convergence of FEM). If is so maybe you are using things like coniugate gradient (CG) o precond coniugate gradient (PCG). If I am correct place tell us (and modify the question. $\endgroup$ – Mauro Vanzetto Oct 28 '18 at 17:59
  • $\begingroup$ Cross post: math.stackexchange.com/questions/2973505/… $\endgroup$ – Mauro Vanzetto Oct 28 '18 at 18:00
  • 1
    $\begingroup$ Sorry but $A$ is inside the integral? And after is the stiff matrix? $\endgroup$ – Mauro Vanzetto Oct 29 '18 at 11:19
1
$\begingroup$

I suppose there is an misunderstanding about the convergence, in my opinion it is about the convergence of the linear solver used to solve the linear system $Au=f$ and no the convergence of the method FEM itself. I try to explain.

Galeriking - FEM convergence

Your objective if to find the unique $u$ s.t. $$ \tag{1} u \in W \quad A(u,v) = l(v) \quad \forall v \in V $$ where:

  • $A$ is a bi-linear for associated to the differential operator
  • $l$ a linear functional in the dual
  • $W,V$ opportune functional spaces I only rewrite your problem in a general form, but we are talking about the same things.

Now find the exact solution for the problem $(1)$ is difficult, also because $V$ is an space infinite dimensional. So you approx it with a subspace finite dimensional.

You go on with keep $W=V$ and approximate $V$ with the family $V_h$ s.t.: $$ \forall v \in V \; \inf_{v_h \in V_h} ||v - v_h|| \longrightarrow 0 \; \text{for} \; h \longrightarrow 0 $$

Note that the idea is approximate the solution space and no the operator essentially this is the Galerking method.

Now the problem is find: $$ \tag{2} u_h \in V_h \quad:\quad A(u_h,v_h) =l(v_h) \; \forall v_h \in V_h $$

h is the discretization index i.e. the grid step. More $h$ is small more $V_h$ is big so you have got a best approximation.

The motivation about the Galerking method works is essentially based on the Céa's lemma, it give us this estimate: $$ ||u -u_h||_V \leq c \inf_{v \in V_h}||u - v||_V $$

In the wiki page there is an example of estimate with the approx by piecewise-linear function.

The choice of the base for the space is important, in the early time before computers often were used global or trigonometric polynomial.

When you choose piecewise polynomial, i.e simple polinomial with compact support, you obtain FEM method. For example it has got the advantage that the stiff matrix is sparse.

As you can see form the Céa's lemma and this estimates: $$ ||u - u_h||_{0,\infty} \leq C h^{l+1} |u|_{l+1, \infty} \; \forall u \in W^{l+1, \infty} $$ , here $W^{l+1, \infty}$ is a Sobolev's space, the convergence of the FEM method is related to the step $h$. For this I think that your question is about the second part.

Linear solver convergence

If you have got:

  1. data with infinite precision
  2. solve the linear system with infinite precision. For example by hand gauss elimination with infinite precision, or conjugate gradient (CG) that with infinite precision is an exact solver and converge after $n = dim(A)$ iteration you are immune about $cond(A)$.

But as the Spartans said, if... For point one you can not meet this requirement. For point 2, it is impractical, to much time by hand and also if you want use CG and wait the final step the dimension of $A$ give you problem.

For this is important to consider $cond(A)$ because influence your convergence.

For example, only to show a case, if you consider CG that is often used yo have got this estimate:

$$ \frac{e_n}{e_0} = \frac{||x - x_n||_A}{||x -x_0||_A} < 2 \left ( \frac{\sqrt{K_A} - 1}{\sqrt{K_A} + 1} \right )^n \;, \quad K_A = \frac{\lambda_{max}}{\lambda_{min}} $$

as you can see $cond(A) = K_A$ influence the convergence. Note this is a generic estimate for CG for a generic matrix.

$\endgroup$

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.