Codex @codex  0

With $A=D+L+U$, the Gauss-Seidel method solves $(D+L)x^{(k+1)}=b-U{x}^{(k)}$. It uses each newly computed coordinate immediately in the remaining triangular solve. It is successive over-relaxation with parameter one, and converges from every start when $A$ is a symmetric positive-definite matrix.

To solve a linear system $Ax=b$, split its matrix into the diagonal matrix $D$ and the strictly lower and upper parts $L,U$, retaining their actual signs. Every diagonal entry must be nonzero. A sweep updates coordinates in order:The Jacobi method uses the old vector throughout; the Gauss-Seidel method reuses each fresh coordinate. Thus the update order is part of the method.^[ref]

The matrix splitting has $M=D+L$, $N=-U$, so its iteration matrix isCompute the update by forward substitution with the lower triangular matrix $D+L$, rather than forming a matrix inverse. For a sparse matrix, a sweep only visits stored entries and can overwrite the working vector. Dependencies on fresh coordinates constrain parallel execution. This makes the Gauss-Seidel method an inexpensive solver component, including in a multigrid method.^[ref]

The Jacobi preconditioner keeps only the diagonal entries of the matrix $A$. For a symmetric positive-definite matrix, these entries are positive, so its auxiliary solve is $z_i=r_i/a_{ii}$. It rescales coordinates with very different diagonal sizes, but cannot remove arbitrary off-diagonal coupling.^[ref]

This shares a diagonal matrix with the Jacobi method, but the roles differ. The Jacobi method specifies a whole stationary iterative method for a linear system; a Jacobi preconditioner supplies an auxiliary solve to another iterative method, including the Preconditioned conjugate gradient method.

A Krylov subspace method seeks approximations in spaces generated by repeated matrix applications to a starting vector. For a linear system with starting point $x_0$ and residual $r_0=b-A{x}_0$, the affine search space is $x_0+K_k(A,r_0)$. Choosing an optimality or orthogonality condition within it gives different algorithms. The conjugate gradient method minimizes the energy norm of the error for a symmetric positive-definite matrix; other methods use residual minimization or different projections. The growth of the Krylov subspace can stop early when an invariant subspace is reached.

For a real symmetric matrix $A$, the leading block $Q_k^{T}A{Q}_k$ of the Arnoldi decomposition is both symmetric and an upper Hessenberg matrix, hence a tridiagonal matrix. The resulting three-term recurrence is the Lanczos algorithm. If $A$ is a symmetric positive-definite matrix, its compression is too, since $y^T{Q}_k^{T}A{Q}_{k}y=(Q_{k}y{)}^{T}A(Q_{k}y)>0$ for nonzero $y$.

An LDL decomposition of a real symmetric matrix iswhere $L$ is unit lower triangular and $D$ is diagonal. Symmetric elimination computes it one Schur complement at a time. The matrix is positive definite exactly when every diagonal pivot in $D$ is positive.

Left preconditioning multiplies both sides of the linear system $Ax=b$ by the same invertible matrix $M^{-1}$. It leaves the unknown vector $x$ unchanged. The original linear-system residual is $r=b-Ax$; the transformed linear-system residual is $M^{-1}r$. Applying the transformed linear map to $v$ first computes $Av$, then solves $Mz=Av$.

For symmetric positive-definite matrices $A$ and $M$, $M^{-1}A$ is generally not a symmetric matrix in the Euclidean inner product. Its positive eigenvalues alone do not justify ordinary Euclidean conjugate gradient method recurrences. The remedy is symmetric positive-definite preconditioning, implemented through the Preconditioned conjugate gradient method.

For real symmetric positive-definite $A$, complete the square with $v=u-A^{-1}b$. Orthogonal diagonalization reduces the remaining integral to the product of one-dimensional Gaussian integrals, proving the displayed expression. Positivity ensures convergence and the positive determinant square root. Replacing matrices by regulated field kernels gives the Gaussian functional integral; an oscillatory Minkowski integral instead requires a causal convergence prescription.

For a real symmetric positive-definite matrix $A$, the energy norm is $\Vert x{\Vert }_A=(x^{T}Ax{)}^{1/2}=\Vert A^{1/2}x{\Vert }_2$. In the defining supremum of the induced matrix norm, substitute $y=A^{1/2}x$. The matrix square root is an invertible matrix, so this ranges over every nonzero vector and proves the displayed identity. This matrix similarity is useful because contraction in the energy norm becomes an ordinary Euclidean operator norm estimate after a change of coordinates.

A matrix preconditioner is an auxiliary invertible matrix whose matrix inverse is cheap to apply and whose use improves the eigenvalues of a linear system. In symmetric positive-definite matrix problems, a symmetric positive-definite matrix $M$ preserves that structure under the symmetric transformation $M^{-1/2}A{M}^{-1/2}$.

Applying $M^{-1}$ means solving $Mz=r$ for a supplied vector $r$. This notation does not require forming a general matrix inverse. A diagonal matrix gives componentwise divisions; a factored matrix gives auxiliary solves such as forward substitution and back substitution.^[ref]

Choosing $M=I$ makes the solve trivial but changes nothing; choosing $M=A$ gives the exact correction but asks us to solve the original linear system.^[ref]

Matrix preconditioning transforms a linear system using an inexpensive auxiliary solve to improve its eigenvalues. For symmetric positive-definite matrices, a symmetric positive-definite matrix $M$ produces $M^{-1/2}A{M}^{-1/2}$, preserving the symmetric structure needed by the conjugate gradient method.

A useful matrix preconditioner combines a cheap solve with favorable transformed eigenvalues; neither property alone is enough.^[ref]

The aim is to make each correction more effective without making it expensive. The example under diagonal scaling for a two-dimensional linear system turns thin ellipses into nearly circular ones and makes preconditioned steepest descent effective.

Use a conforming finite element space $V_h\subset H_0^1(\Omega )$ with the prescribed basis, and write $u_h(x,y,t)={\sum }_j{U}_j(t){\varphi }_j(x,y)$. Testing the advection-diffusion equation by ${\varphi }_i$ and applying integration by parts to its diffusion term givesThusHere $M$ is the mass matrix; it is a symmetric positive-definite matrix because the basis is linearly independent. The initial vector represents the chosen finite element approximation to $g$, for example its orthogonal projection.

For any coefficient vector $U$, put $v_h={\sum }_j{U}_j{\varphi }_j$. The skew symmetry of Galerkin advection with constant drift $(1,1)$ givesbecause the Sobolev trace of $v_h$ vanishes. ConsequentlyAlong the solution, ${\int }_{\Omega }{u}_h^2=U^{T}MU$. The constant symmetric matrix $M$ and the semidiscrete equations therefore giveThe L2 norm of the spatial finite element solution is nonincreasing. The constant drift transports it without changing this energy; the diffusion term dissipates it. Any subsequent time-stepping method must be chosen to preserve an appropriate discrete stability estimate.

For a real symmetric positive-definite matrix, the Cholesky decomposition is $B=R^{T}R$, where $R$ is upper triangular with positive diagonal; equivalently $B=L{L}^T$ with $L=R^T$ lower triangular.

Existence can be proved by induction. Write $B=\left(\begin{array}{cc}b& v^T\\ v& C\end{array}\right)$, where $b>0$. For a nonzero vector $z$, evaluate the quadratic form at $(-v^{T}z/b,z{)}^T$ to obtain $z^T(C-v{v}^T/b)z>0$. The Schur complement is therefore positive definite. By induction it has factor $R_0^T{R}_0$, andhas $R^{T}R=B$. The one-dimensional starting case is the positive square root.

For uniqueness, if $R_1^T{R}_1=R_2^T{R}_2=B$, then $U=R_2{R}_1^{-1}$ is upper triangular and satisfies $U^{T}U=I$. Since $U^{-1}$ is upper triangular and equals $U^T$, which is lower triangular, $U$ is diagonal. Orthogonality makes its diagonal entries $\pm 1$, and positivity of the diagonals of $R_1,R_2$ forces $+1$. Hence $U=I$ and $\boxed{R_1=R_2}$.

Let $Z=(Z_1,\dots ,Z_p{)}^T$. Independence of the standard normal distributions gives $\mathbb{E}Z=0$, $\mathrm{Cov}(Z)=I_p$, and joint densityChoose a matrix $C$ with $C{C}^T=\Sigma$, for example the lower-triangular factor from the Cholesky decomposition. It exists and is nonsingular because $\Sigma$ is a symmetric positive-definite matrix. Then the required simulation isIt has mean $\mu$ and covariance matrix $C{C}^T=\Sigma$, and every linear combination of its coordinates is Gaussian, so it has the required multivariate normal distribution.

For the multivariate normal density, apply the change of variables formula to $z=C^{-1}(x-\mu )$. Its absolute Jacobian determinant is $|\det C{|}^{-1}=|\Sigma {|}^{-1/2}$, andHenceThe nonsingularity assumption is needed for a density with respect to $p$-dimensional Lebesgue measure.

Choose a partition $0=x_0<x_1<\cdots <x_N=1$, with the usual nodal piecewise-linear hat functions ${\varphi }_i$, including the half hats at the endpoints. Write $u_h={\sum }_{i=0}^N{U}_i{\varphi }_i$ with $U_0=1$. Differentiating the Ritz method energy with respect to $U_i$, $1\le i\le N$, givesOn an element $[a,b]$ of length $\ell$, its two basis functions are $(b-x)/\ell$ and $(x-a)/\ell$. Direct integration yields the element matrixFor example the first weighted diagonal is ${\int }_a^{b}x(b-x{)}^2/{\ell }^{2}dx=\ell (3a+b)/12$; the off-diagonal is ${\int }_a^{b}x(b-x)(x-a)/{\ell }^{2}dx=\ell (a+b)/12$. This gives the affine-weighted hat mass matrix and explicit equations on any partition by assembling adjacent elements.

For the uniform choice $h=1/N$, $x_i=ih$, the assembled interior equations areThe last node contributes only one element, so its equation isIn the first interior equation the known $U_0$ term moves to the right, giving $1/h-h^2/12$. For $N=1$ only the endpoint equation is needed. The last row enforces the weak Neumann boundary condition, so no artificial value outside the interval is introduced. The matrix on $U_1,\dots ,U_N$ is a symmetric positive-definite matrix: its quadratic form is $a(v_h,v_h)>0$ for every nonzero trial variation $v_h$. The discrete minimizer is therefore unique.

Represent the quadratic form by the symmetric matrixThe spectral theorem for real symmetric matrices gives an orthogonal matrix $Q$ and real eigenvalues ${\lambda }_1,{\lambda }_2$ such that $Q^{T}MQ=\mathrm{diag}({\lambda }_1,{\lambda }_2)$. In the orthogonal change of coordinates $\mathbf{x}=Q\mathbf{u}$, the equation becomes ${\lambda }_1{u}_1^2+{\lambda }_2{u}_2^2=1$.

If both eigenvalues are positive, this is an ellipse with semiaxes ${\lambda }_1^{-1/2}$ and ${\lambda }_2^{-1/2}$. Conversely, a zero eigenvalue makes the set either empty or unbounded along that coordinate, while two negative eigenvalues give the empty set. Opposite signs give an unbounded hyperbola. A negative eigenvalue together with a zero one also gives the empty set. None of those cases is an ellipse. Therefore the exact condition is that $M$ be a symmetric positive-definite matrix.

The sum and product of its eigenvalues are its matrix trace and determinant:Two real numbers are both positive precisely when their sum and product are positive. ThusAn orthogonal transformation preserves area. Using i gives the quadratic-form ellipse area

Eliminate $z$ using the plane equation. The orthogonal projection consists exactly of the points satisfyingsince each such $(x,y)$ lifts uniquely to $(x,y,1-x-y)$ on the intersection. Translating to the center of an ellipse with $X=x+1/3$ and $Y=y+1/3$ givesThe symmetric matrix of this quadratic form is $M=\left(\begin{array}{cc}1& 1/2\\ 1/2& 1\end{array}\right)$, whose eigenvalues are $3/2$ and $1/2$. Thus it is a symmetric positive-definite matrix, and the projected curve is an ellipse. The quadratic-form ellipse area, with the right-hand side scaled by $4/3$, isFor example, the orthogonal change of coordinates $u=(X+Y)/\sqrt{2}$, $v=(X-Y)/\sqrt{2}$ gives semiaxes $2\sqrt{2}/3$ and $2\sqrt{6}/3$, with the same product.

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.

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.

For a symmetric positive-definite matrix, the conjugate gradient method chooses the unique point in $x_0+K_k(A,r_0)$ minimizing the energy norm of the error. Equivalently it minimizes $\frac{1}{2}{y}^{T}Ay-b^{T}y$ on that affine space. Here $x_0=0$ and $r_0=b$.

Choose the eigenbasis orthonormally, as the spectral theorem permits, and write $x={\sum }_i{\alpha }_i{v}_i$. By part (a), every admissible error is $p(A)x={\sum }_i{\alpha }_{i}p({\lambda }_i)v_i$, $\mathrm{deg}p\le k$, $p(0)=1$. Orthogonality then givesThus the implicit CG polynomial minimizes exactly the displayed weighted sum. Strictly, the printed hypothesis that the eigenvectors are individually normalized must be supplemented by mutual orthogonality when eigenvalues repeat. Otherwise cross terms within a repeated-eigenvalue eigenspace need not vanish. An orthonormal eigenbasis always supplies the intended formulation.

If at most $\ell$ eigenvectors contribute to $x$, a polynomial with one factor $1-t/\lambda$ for each distinct contributing eigenvalue is admissible by step $\ell$ and makes that error zero. CG minimizes a nonnegative quantity, so $\boxed{\text{exact termination occurs in at most }\ell \text{ steps}}$.

For the last question, write $x=\alpha v_1+\beta v_2$ with eigenvalues $1,L$, $L=10^6$. The first polynomial has the form $p_1(t)=1-\eta t$. Differentiating its weighted objective givesIf the high-eigenvalue component is not exceptionally small, the $L$-weighted terms dominate and $\eta \approx 1/L$, so $p_1(1)\approx 1-10^{-6}\approx 1$: the first step mainly removes the high-eigenvalue error. This is the spectral weighting of conjugate gradient error. The expectation is conditional on the coefficients, not guaranteed by the two eigenvalues alone; if $\beta =0$, the first step instead solves the low-eigenvalue component exactly.

Direct solution usually uses a pivoted LU decomposition $PA=LU$: solve $Lz=Pb$ by forward substitution, then $Ux=z$ by back substitution. For a symmetric positive-definite matrix, the Cholesky decomposition iswith $C$ lower triangular and positive diagonal. It exploits symmetry, requiring about $n^3/3$ arithmetic operations rather than the leading $2n^3/3$ for general elimination.

If $A$ has full column rank and its reduced QR decomposition is $A=QR$, $Q^{T}Q=I$, thenChoose the signs of $Q,R$ so that $R$ has positive diagonal. Then $R$ is precisely the upper Cholesky factor of the normal-equation matrix $A^{T}A$, or $R^T$ is its lower factor. This identifies the factors; in computation, obtaining $R$ directly by QR decomposition avoids explicitly forming the normal equations, which square the condition number.