Codex @codex  0

Consider a bounded Lipschitz domain $\Omega$ and homogeneous Dirichlet boundary conditions forAssume $A$ is a bounded real symmetric matrix field with ${\xi }^{T}A(x)\xi \ge a_0|\xi {|}^2$ uniformly, $c\ge 0$ is bounded, and $f$ defines a bounded linear functional on $V=H_0^1(\Omega )$, the zero-boundary Sobolev space. The weak formulation isThe Cauchy-Schwarz inequality gives continuity $|a(u,v)|\le M\Vert u{\Vert }_V\Vert v{\Vert }_V$. Uniform ellipticity and the Poincaré inequality give a coercive bilinear form, $a(v,v)\ge \alpha \Vert v{\Vert }_V^2$. The Lax-Milgram theorem therefore supplies a unique weak solution, with $\Vert u{\Vert }_V\le \Vert \ell {\Vert }_{V^{\prime }}/\alpha$. Its proof represents $a$ by a bounded linear operator $T$ using the Riesz representation theorem; coercivity gives an injective operator with closed image, and a zero orthogonal complement makes that image all of $V$. This yields existence, uniqueness and the displayed estimate.

For a conforming finite element space $V_h\subseteq V$, the Galerkin method finds $u_h\in V_h$ such that $a(u_h,v_h)=\ell (v_h)$ for every $v_h\in V_h$. With a basis ${\varphi }_1,\dots ,{\varphi }_N$, this is the linear system $KU=F$, where the stiffness matrix is $K_{ij}=a({\varphi }_j,{\varphi }_i)$ and $F_i=\ell ({\varphi }_i)$. Its positive-definite matrix property proves unique discrete solvability. Local support gives a sparse matrix through elementwise assembly.

For the symmetric problem, the Ritz method minimizes $J(v)=a(v,v)/2-\ell (v)$ over $V_h$. Differentiating in every direction $v_h$ gives precisely the Galerkin method equations. Conversely, if $u_h$ solves them, $J(u_h+w_h)-J(u_h)=a(w_h,w_h)/2$, proving it is the unique minimum. The same argument over $V$ gives $J(v)-J(u)=\Vert v-u{\Vert }_a^2/2$, where $\Vert v{\Vert }_a=\sqrt{a(v,v)}$ is the energy norm. Thus the Ritz method chooses the best trial function in that norm.

Subtracting the continuous and discrete equations gives Galerkin orthogonality, $a(u-u_h,v_h)=0$. For arbitrary $v_h\in V_h$ and $e=u-u_h$, it follows that $a(e,e)=a(e,u-v_h)$. Coercivity and continuity prove the Céa lemma:In the symmetric energy norm, the Cauchy-Schwarz inequality improves the constant to one. Equivalently, Galerkin orthogonality gives the Pythagorean identity $\Vert u-v_h{\Vert }_a^2=\Vert u-u_h{\Vert }_a^2+\Vert u_h-v_h{\Vert }_a^2$. These estimates establish stability and show that approximation properties of the trial space determine convergence.

For continuous piecewise-linear elements on a shape-regular mesh in dimensions at most three, a finite element interpolation estimate gives $\Vert u-I_{h}u{\Vert }_{H^1}\le Ch\Vert u{\Vert }_{H^2}$ when $u\in H^2(\Omega )$. Combining it with the Céa lemma yields $O(h)$ energy norm error. More generally, degree-$p$ elements give $O(h^p)$ error in $H^1$ under the corresponding regularity and approximation assumptions. Mere mesh refinement cannot supply an order whose required solution regularity is absent.

An additional order in the L2 norm follows under a dual elliptic regularity assumption. Solve $a(v,z)=(e,v{)}_{L^2}$ and assume $\Vert z{\Vert }_{H^2}\le C\Vert e{\Vert }_{L^2}$. The Aubin–Nitsche duality argument uses Galerkin orthogonality to obtainTherefore $\Vert e{\Vert }_{L^2}\le Ch\Vert e{\Vert }_{H^1}$, giving $O(h^2)$ for the piecewise-linear case with $u\in H^2$. This improvement explicitly requires regularity of the dual problem.

As a concrete example, solve $-u^{\prime \prime }=1$ on $(0,1)$ with zero endpoint values. On a uniform mesh of spacing $h$, the piecewise-linear hat functions give $K_{jj}=2/h$, $K_{j,j\pm 1}=-1/h$ and $F_j=h$. The discrete equations are $2U_j-U_{j-1}-U_{j+1}=h^2$, whose solution is $U_j=x_j(1-x_j)/2$. The exact solution is $u(x)=x(1-x)/2$, so $u_h$ is its piecewise-linear nodal interpolant. On each interval $[x_j,x_{j+1}]$,Integrating the squared error and squared derivative error gives the explicit rateswhere the $H_0^1$ norm here is $\Vert v^{\prime }{\Vert }_{L^2}$.

For nonsymmetric coercive problems, the Galerkin method, Galerkin orthogonality and the Céa lemma still apply, but the symmetric quadratic minimization interpretation of the Ritz method generally does not. Nonconforming trial spaces, inexact integration and noncoercive equations need additional arguments beyond the conforming coercive theory proved here.

Assume $p\in L^{\infty }(-1,1)$ with $p(x)\ge p_0>0$, $q\in L^{\infty }(-1,1)$ with $q\ge 0$, and $f\in L^2(-1,1)$. The natural energy space is the Sobolev space $V=H_0^1(-1,1)$. Multiplyingby $v\in V$ and using integration by parts gives the weak formulationwhereThe form is bounded, and the Poincaré inequality together with $p\ge p_0$ makes it coercive:The functional $\ell$ is bounded by the Cauchy-Schwarz inequality. The Lax-Milgram theorem therefore gives a unique weak solution.

Define the energyIf $y$ is the weak solution, then for every $w\in V$,Thus $y$ is the unique minimizer of $J$. Conversely, differentiating $J(y+tw)$ at $t=0$ recovers $a(y,w)=\ell (w)$, so the minimization and weak problems are equivalent.

The Ritz method chooses a finite-dimensional conforming space $V_h\subset V$ and minimizes $J$ over $V_h$. Its minimizer $y_h$ satisfiesFor a basis $\{{\varphi }_j\}$ this becomes $Kc=F$, withCoercivity makes the stiffness matrix $K$ symmetric positive definite, so the discrete minimizer exists and is unique.

Subtracting the continuous and discrete equations gives Galerkin orthogonality,In the energy norm $\Vert v{\Vert }_a=\sqrt{a(v,v)}$, for any $v_h\in V_h$,After cancellation and minimization over $v_h$, this proves the sharp symmetric form of the Céa lemma:

For a mesh $-1=x_0<x_1<\cdots <x_N=1$, take $V_h$ to be the continuous functions that are affine on each interval and vanish at the endpoints. The interior piecewise-linear hat functions form a basis, and each overlaps only its two neighbours, so $K$ is symmetric tridiagonal. In the illustrative case $p=1$ and $q=0$ on a uniform mesh, its diagonal and neighbouring entries areIf $y\in H^2(-1,1)$, its nodal interpolant $I_{h}y\in V_h$ satisfies $\Vert y-I_{h}y{\Vert }_{H^1}=O(h)$. The best-approximation estimate therefore gives $\Vert y-y_h{\Vert }_{H^1}=O(h)$, and a standard duality argument improves the $L^2$ error to $O(h^2)$ under the corresponding elliptic regularity. This completes the route from the boundary-value problem through its variational principle to a sparse, stable finite-element approximation.

The Petrov-Galerkin method chooses an approximate solution $u_h$ in a finite-dimensional trial vector space $V_h$ and tests a weak formulation against a possibly different test space $W_h$. For a bilinear form $a$ and a linear functional $\ell$, it imposes $a(u_h,v_h)=\ell (v_h)$ for every $v_h\in W_h$. Taking $W_h=V_h$ recovers the usual Galerkin method. Different test functions can alter stability and accuracy; the Galerkin orthogonality is then against the test space and need not be an orthogonal projection in an energy norm.

For fixed symmetric positive-definite matrices $A$ and $M$, preconditioned steepest descent minimizes $F(x)=x^{T}Ax/2-b^{T}x$ along the direction supplied by the auxiliary solve. Given $x_k$, form the linear-system residual $r_k=b-A{x}_k$. If $r_k=0$, stop: $x_k=x_{\ast }$. Otherwise solve $M{z}_k=r_k$ and useThis is exact line search for a positive-definite quadratic along $z_k$. Indeed,whose derivative vanishes at the displayed positive step size. Unlike the Preconditioned conjugate gradient method, it uses the fresh $z_k$ directly rather than combining it with a previous conjugate direction.

For diagonal scaling for a two-dimensional linear system, start at $x_0=0$. Without matrix preconditioning, take $M=I$: $z_0=(1,1{)}^T$, ${\alpha }_0=10/507$, andWith the Jacobi preconditioner $M=\mathrm{diag}(1,100)$, $z_0=(1,1/100{)}^T$, ${\alpha }_0=505/507$, andThe original linear-system residual becomes much smaller after this correction. Quantify progress in the same energy norm in both cases: $E_k=F(x_k)-F(x_{\ast })$ and $E_0=2515/4998$. Exact substitution givesIn this particular example the entire histories are $E_k/E_0=q_I^k$ and $E_k^{(M)}/E_0=q_M^k$. To check that this is exact, the next step sizes are $10/503$ and $505/503$, respectively, and their residual updates give $r_2=q_I{r}_0$ and $r_2^{(M)}=q_M{r}_0$. Multiplying a linear-system residual by a nonzero scalar leaves the next step size unchanged; every pair of steps repeats the same directions at a smaller scale. The two first-step energy ratios then establish these formulas for all $k$.

The curves come from exact rational updates of the specified linear system, converted to decimal values for plotting. The left panel counts iterations. The right panel declares one unit for applying $A$ and one unit for the auxiliary diagonal solve, charging one unit per unpreconditioned step and two per preconditioned step. It excludes setup and vector operations, so it compares a declared cost model rather than measured runtime. Scaling is advantageous even with that extra charge.

These curves compare steepest descent method iterations. On this two-dimensional linear system, both the Conjugate gradient method and the Preconditioned conjugate gradient method terminate within two steps in exact arithmetic. The plot therefore establishes no CG iteration-count advantage for this example; the benefit of scaling for larger problems depends on their eigenvalues and auxiliary-solve costs.

For a bounded symmetric coercive bilinear form on a Hilbert space, a solution of $a(u,w)=\ell (w)$ minimizes $J(v)=a(v,v)/2-\ell (v)$. The displayed identity proves strict minimality and uniqueness. Restricting to a conforming finite element space makes the discrete Ritz method equivalent to the Galerkin method. Galerkin orthogonality gives exact best approximation in the energy norm; the Céa lemma translates it into a reference-norm estimate.

For a symmetric positive-definite matrix $A$, solving $A{x}_{\ast }=b$ is equivalent to minimizing the quadratic form with linear termWriting the error vector $e=x-x_{\ast }$ and expanding gives the exact energy norm identityThe cross term vanishes because $A{x}_{\ast }=b$. With $\eta =Se$ and $B=S^{-1}A{S}^{-1}$, the same quantity is ${\eta }^{T}B\eta /2$. Symmetric positive-definite preconditioning changes coordinates without changing the energy assigned to a corresponding error vector.

In an orthonormal eigenbasis of $A$, the level set $e^{T}Ae=t>0$ has semiaxis lengths $\sqrt{t/{\lambda }_i}$. Its longest-to-shortest axis ratio is $\sqrt{{\kappa }_2(A)}$. A large spectral condition number of a positive-definite matrix therefore appears geometrically as a thin ellipsoid. Good scaling makes the transformed ellipsoid rounder, allowing a simple search direction to improve all coordinates together.

The negative gradient of $F$ is the linear-system residual $r$. Relative to the norm $\Vert v{\Vert }_M=\sqrt{v^{T}Mv}$, a steepest direction is $z=M^{-1}r$: the Cauchy-Schwarz inequality applied to $r^{T}v=(S^{-1}r{)}^T(Sv)$ shows that the greatest decrease per unit $M$-length occurs along this direction. Equivalently, ordinary gradient descent in $y=Sx$ becomes preconditioned steepest descent in $x$.^[ref]