Codex @codex  0

The Lax-Milgram theorem states that a bounded bilinear form $a$ on a real Hilbert space $V$, satisfying $a(v,v)\ge \alpha \Vert v{\Vert }_V^2$ for some $\alpha >0$, has for each $F\in V^{\ast }$ a unique $u\in V$ with $a(u,v)=F(v)$ for all $v$. Moreover $\Vert u{\Vert }_V\le \Vert F\Vert /\alpha$.

For a compact operator $K$ on a Hilbert space, the Fredholm alternative says that $I-\lambda K$ has closed range, finite-dimensional kernel and cokernel of equal dimension, andThus a zero kernel gives unique solvability for every right-hand side; a nonzero kernel gives solvability exactly under the adjoint orthogonality conditions, and then all solutions differ by a kernel vector.

Take $V=H_0^1(\Omega )$. Gårding's inequality supplies constants $a>0$, $b\ge 0$ with $B[v,v]\ge a\Vert v{\Vert }_{H^1}^2-b\Vert v{\Vert }_2^2$. Therefore for $\lambda \le -b$ the shifted form $B_{\lambda }[u,v]=B[u,v]-\lambda (u,v{)}_{L^2}$ is coercive. It is bounded for every fixed $\lambda$, and $v\mapsto (f,v)$ is bounded on $V$. Lax-Milgram gives unique weak solvability for $\lambda \le -\gamma$, with $\gamma =b$. The inequality itself follows, for example, by absorbing the drift cross-term $\Vert b{\Vert }_{\infty }\Vert \nabla v{\Vert }_2\Vert v{\Vert }_2$ using Young's inequality and allowing a lower $L^2$ correction for $c$.

For the compact inverse and adjoint of a coercive elliptic operator, under the additional zero-shift coercivity assumption, define $Gg\in V$ by $B[Gg,v]=(g,v)$ for all $v\in V$, and let $K$ be this solution viewed in $L^2$. The solution operator is linear and bounded into $V$, and the Rellich-Kondrachov compact embedding $V\hookrightarrow L^2$ makes $K$ compact. Rewriting the weak equation as $B[u,v]=(f+\lambda u,v)$ givesConversely an $L^2$ solution of this operator equation lies in $V$, because it equals $K(f+\lambda u)$, and satisfies the weak differential equation.

For constant drift coefficients and zero Dirichlet traces, integration by parts gives $\int b_i{D}_{i}vu=-\int b_{i}v{D}_{i}u$. Symmetry of the principal coefficients therefore makes $B^{\ast }[u,v]=B[v,u]$ the unshifted weak form of the displayed formal adjoint. The shifted adjoint equation requiresThe spectral shift in an adjoint weak formulation is essential: the printed sentence omitting it is false for nonzero $\lambda$. For instance take a smooth ball, $L=-\Delta +1$, any nonzero $u\in C_c^{\infty }(\Omega )$ and $f=-\Delta u+u$. The printed unshifted identity holds, but $(L^{\ast }-\lambda )u=f-\lambda u\ne f$ whenever $\lambda \ne 0$. This counterexample also meets zero-shift coercivity and constant-drift assumptions. The corrected identity above is used for the remainder of the argument.

Let $G_{\ast }g\in V$ solve $B^{\ast }[G_{\ast }g,v]=(g,v)$, which exists by Lax-Milgram because the diagonal coercivity is unchanged. For $p,q\in L^2$,Thus $G_{\ast }$, viewed as an $L^2$ operator, is exactly $K^{\ast }$. Applying this inverse to the corrected shifted adjoint equation givesand the converse follows from its range lying in $V$, just as before.

Finally let the original homogeneous equation have a nonzero solution. Its parameter is nonzero, since the unshifted problem is coercive. Fredholm gives solvability precisely when $(Kf,w)=0$ for every $w\in \ker (I-\lambda K^{\ast })$. Such a $w$ satisfies $K^{\ast }w=w/\lambda$, so $(Kf,w)=(f,w)/\lambda$. Hence the necessary and sufficient condition isWhen this holds, the solutions are an affine translate of the original finite-dimensional homogeneous solution space. The compatibility space is the adjoint kernel; a drift term does not generally permit replacing it by the original kernel.

A Givens rotation acts as the identity matrix outside two selected coordinates $i,j$, and has the following block on those coordinates:The convention with the opposite signs of the sines is equivalent after replacing $\theta$ by $-\theta$. A Householder reflection with nonzero normal vector $w\in {\mathbb{R}}^n$ isIt reverses the component parallel to $w$ and fixes the perpendicular hyperplane. Both are orthogonal matrices, so their transposes are their inverses and they preserve the Euclidean norm.

Write $p_n(x)={\sum }_{j=0}^n{c}_j{x}^j$. The allowed orthogonal projection characterization, applied to the basis $1,x,\dots ,x^n$, gives the normal equationsExplicitly $G_{ij}=0$ if $i+j$ is odd and $G_{ij}=2/(i+j+1)$ if it is even. These equations can also be derived by differentiating $\int (u-\sum c_j{x}^j{)}^{2}dx$ with respect to each coefficient.

The Gram matrix $G$ is a symmetric positive-definite matrix. For any nonzero real coefficient vector $z$,The polynomial inside the square is nonzero, so its square is positive on some interval. Hence $G$ has zero kernel and is invertible. Thus the normal equations have exactly one solution, giving exactly one best least-squares polynomial. This proves both existence and uniqueness. For completeness, if the residual is orthogonal to ${\Pi }_n$, then for every $q\in {\Pi }_n$ the Pythagorean theorem gives $\Vert u-q{\Vert }^2=\Vert u-p_n{\Vert }^2+\Vert p_n-q{\Vert }^2$, directly verifying minimality and uniqueness.

A real square matrix $Q$ is an orthogonal matrix when $Q^{T}Q=I$, equivalently its columns form an orthonormal basis. Here $Q^T$ is the transpose and $I$ the identity matrix. For every vector $x$,Taking nonnegative square roots provesThus an orthogonal matrix preserves the Euclidean norm.

Choose the following consistent sign convention. The Givens rotation $J(i,j,\theta )$ equals the identity matrix except for the block on coordinates $i,j$:Thus it changes only the $i$th and $j$th coordinates of a vector. Write $c=\cos \theta$, $s=\sin \theta$. Its two-coordinate block satisfiesAll remaining coordinates are unchanged, so $J^{T}J=I_n$. Hence every such Givens rotation is an orthogonal matrix. With this convention the two-coordinate rotation matrix rotates through angle $-\theta$.

Apply the product from right to left, choosing every Givens rotation from the current first column. First $J(1,2)$ replaces $(a_1,a_2)$ by $(\sqrt{a_1^2+a_2^2},0)$. Next $J(1,3)$ combines that retained entry with $a_3$ and sets the third entry to zero. Inductively, after eliminating coordinates $2,\dots ,k$, the first coordinate isand coordinates $2,\dots ,k$ are zero. Later Givens rotations involve only coordinate one and a new coordinate, so those zeros remain zero. Thereforewhere $e_1$ is the first standard basis vector. The zero vector is included by choosing the identity matrix for every zero pair. The nonnegative sign follows from the convention fixed in part (c)(ii). This is the first-column stage of QR decomposition by Givens rotations.

Gaussian elimination uses elementary row operations to remove entries below successive pivot elements, reducing a linear system to one with an upper triangular matrix. Back substitution then solves that system. It also computes a reusable matrix factorization, so additional right-hand sides can be handled by forward substitution and back substitution without repeating the elimination.

For elimination without row exchanges, let $A^{(1)}=A$. At step $k$, provided the pivot element $a_{kk}^{(k)}$ is nonzero, form the elimination multipliersand perform ${\text{row}}_i\leftarrow {\text{row}}_i-m_{ik}{\text{row}}_k$, applying the same operation to the right-hand side. More explicitly the resulting entries satisfy $a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}{a}_{kj}^{(k)}$ for $i>k$, $j\ge k$.

Let $E_k=I-{\sum }_{i>k}{m}_{ik}{e}_i{e}_k^T$, where $e_i$ are the standard basis vectors. ThenThe matrix $L$ is a unit lower triangular matrix storing the elimination multipliers, while $U$ is an upper triangular matrix:Solving $Ax=b$ becomes $Ly=b$ followed by $Ux=y$. If a required pivot element vanishes, an unpermuted LU decomposition can fail even for an invertible matrix. Row exchanges, typically selected by partial pivoting, instead produce $PA=LU$ with a permutation matrix $P$; then solve $Ly=Pb$, $Ux=y$.

Since every $u_{jj}>0$, the diagonal matrix $D$ is invertible. SetThe division is by the diagonal entry of row $i$. Thus $\hat{U}$ is an upper triangular matrix with diagonal entries one and $A=LD\hat{U}$.

To use symmetry without assuming the conclusion, multiply by the matrix inverse of $L$ and its transpose:The matrix $M$ is symmetric because $A$ is a symmetric matrix. It is also an upper triangular matrix, since every factor on the right is an upper triangular matrix. A symmetric upper triangular matrix is diagonal. Its diagonal is exactly $D$, because $\hat{U}$ and $L^{-T}$ have diagonal entries one. Hence $M=D$, givingThis is the LDL decomposition.

Take the positive square roots of the diagonal entries:The matrix $\hat{L}$ is a lower triangular matrix with positive diagonal, andThis is a Cholesky decomposition. For a nonzero vector $x$, the vector ${\hat{L}}^{T}x$ is nonzero because ${\hat{L}}^T$ is invertible. ThereforeHere $\Vert \cdot {\Vert }_2$ is the Euclidean norm. Thus $A$ is a positive-definite matrix.

Write ${\mathcal{P}}_n$ for the vector space of polynomials of polynomial degree at most $n$, and put $p_n(x)={\sum }_{j=0}^n{a}_j{x}^j$. As the question calls the weighted integral an inner product, its finiteness is implicit; for example, a positive integrable weight $w$ suffices for all the continuous functions involved here.

For every $q\in {\mathcal{P}}_n$, differentiating the squared weighted norm $\Vert f-p_n-tq{\Vert }_w^2$ at its minimum $t=0$ gives the orthogonality equationsIn particular, the requested linear system isIts Gram matrix $G_{kj}={\int }_{-1}^{1}w(x)x^{k+j}dx$ is a symmetric positive-definite matrix: for any nonzero vector $a$,Indeed a nonzero polynomial is nonzero on some open interval, and the weight is positive. Therefore $G$ is an invertible matrix, proving uniqueness. Conversely, if these equations hold, the Pythagorean theorem in an inner-product space gives, for every $q\in {\mathcal{P}}_n$,so the solution really is the unique best approximation.

The Euclidean norm is invariant under an orthogonal matrix, so the full singular value decomposition givesThe second term is independent of $x$; the first attains its unique minimum zero because $\Sigma$ is an invertible matrix. The linear least squares solution is thereforeHere $A^{+}=V{\Sigma }^{-1}{U}^T$ is the Moore-Penrose inverse, and the fitted vector is the orthogonal projection $A{x}_{\ast }=U{U}^{T}b$ onto the image of a linear map defined by $A$.

With the singular value decomposition supplied, forming $U^{T}b$ costs $O(mn)$ arithmetic operations, diagonal scaling costs $O(n)$, and multiplication by $V$ costs $O(n^2)$. Since $m\ge n$,One need not form $U_{\perp }$, $A^{+}$ or $A^{T}A$ to calculate $x_{\ast }$. Computing the needed thin singular value decomposition first has standard dense cost $O(m{n}^2)$; explicitly forming an entire $m\times m$ orthogonal completion can require additional work when $m$ is much larger than $n$.

The spectral theorem for real symmetric matrices gives $A=Q\Lambda Q^T$ with an orthogonal matrix $Q$. Positive definiteness makes every eigenvalue ${\lambda }_i$ positive. Define the matrix square rootIt is symmetric, its square is $A$, and for any nonzero vector $x$,Thus it is also positive-definite, and its matrix inverse is $A^{-1/2}=Q\mathrm{diag}({\lambda }_i^{-1/2})Q^T$.

For $0<\omega <2$, the coefficient $\gamma =2/\omega -1$ is positive. Moreoveris a positive-definite matrix: for a nonzero vector $z$, put $y=B^{-1}{A}^{1/2}z\ne 0$; then $z^{T}Gz=y^{T}Dy>0$. Hence every eigenvalue of $M=I-\gamma G$ is strictly below one. Part (d) also gives $M=T^{T}T$, so these eigenvalues are nonnegative. ThereforeThe energy-norm proof of convergence of SOR thus makes the iteration a strict contraction mapping in this norm. Its forward error satisfies $e^{(j+1)}=C(\omega )e^{(j)}$, so it converges geometrically to zero.

Nonzero vectors $p_1,\dots ,p_k$ are conjugate directions with respect to $A$ when $p_i^{T}A{p}_j=0$ for $i\ne j$. They are linearly independent: if ${\sum }_i{c}_i{p}_i=0$, multiplication by $p_j^{T}A$ gives $c_j{p}_j^{T}A{p}_j=0$, hence $c_j=0$ by positive definiteness. There are consequently at most $n$ such directions.

The finite termination of conjugate directions follows from the residual orthogonality maintained by the exact line minimizations. At step $j$,For $i<j$, conjugacy gives $p_i^T{r}_{j+1}=p_i^T{r}_j$. By mathematical induction, $r_{j+1}$ is orthogonal to every $p_1,\dots ,p_j$. After $n$ nonzero conjugate directions they form a basis of ${\mathbb{R}}^n$, forcing $r_{n+1}=0$. Thus the method reaches $Ax=b$ in at most $n$ steps, and positive definiteness makes that solution unique. The claim is in exact arithmetic; rounding errors need not preserve exact conjugacy.

Since $A{p}_1=(5,2{)}^T$, an A-conjugate direction $p_2=(a,b{)}^T$ must satisfy $5a+2b=0$. One nonzero choice isDirect matrix multiplication gives $A{p}_2=(3,-3{)}^T$, and $p_1^{T}A{p}_2=0$. All nonzero scalar multiples of this vector also qualify.

For every vector $z\in {\mathbb{R}}^n$, splitting the rows givesBoth summands are nonnegative. Taking the supremum over unit vectors in the definition of the spectral norm proves

The claim is true, withIt is a symmetric positive-definite matrix: for every nonzero vector $z$, the fact that $A$ is an invertible matrix gives $z^{T}Mz=\Vert Az{\Vert }_2^2>0$. Since $A{x}_{\ast }=b$, every candidate $x$ satisfiesThe generalized minimal residual method therefore minimizes precisely this weighted norm of the error over the linear span of $Q_k$. The same matrix $M$ works for every $k$ and does not depend on $b$.

For the small QR decomposition, each of the $k$ Givens rotations eliminates one subdiagonal entry of the upper Hessenberg matrix. At column $j$, apply the rotation to two rows in columns $j,\dots ,k$, costing $O(k-j+1)$ arithmetic operations. Summing gives $O(k^2)$, and applying the rotations to the right-hand side costs $O(k)$. Backward substitution in a triangular system costs $O(k^2)$.

Computing $\Vert b{\Vert }_2$ costs $O(n)$ and the final dense matrix multiplication $Q_k{y}_k$ costs $O(nk)$. Thus the total, with the Arnoldi decomposition already supplied, isHere $1\le k<n$, since $Q_{k+1}$ has orthonormal columns in ${\mathbb{R}}^n$. In the standard dense arithmetic model, forming the general matrix–vector product gives the sharp $\Theta (nk)$ cost. The pair above records that two-parameter bound; looser bounds such as $O(n^2)$ are also possible because $k<n$. Treating ${\tilde{H}}_k$ as an unstructured dense matrix would unnecessarily replace its $O(k^2)$ factorization by an $O(k^3)$ computation.

For any nonzero vector $y\in {\mathbb{R}}^k$, orthonormality gives $\Vert Q_{k}y{\Vert }_2=\Vert y{\Vert }_2>0$. Since $A$ is a symmetric positive-definite matrix,The preceding part already gives symmetry, so $T_k$ is a symmetric positive-definite matrix. In fact the spectral theorem gives the useful boundswhich place its eigenvalues between the smallest and largest eigenvalues of $A$.

The directional derivative in the specified vector direction isThe equality follows from the total-derivative remainder estimate; for the zero direction the result is zero. The convention keeps the supplied vector and does not replace it by a unit vector.

The total derivative is a linear map $Df(a):{\mathbb{R}}^n\to {\mathbb{R}}^n$ such thatIt is unique: the difference of two such linear maps, evaluated on $h=tv$, must vanish on every fixed vector $v$ after division by $t$ and passage to the limit.