The Krylov subspace is $\boxed{K_k(A,b)=\mathrm{span}\{b,Ab,\dots ,A^{k-1}b\}}$. If $y\in K_k$, write $y=q(A)b$ with $\mathrm{deg}q\le k-1$. Since $b=Ax$,which has degree at most $k$ and $p(0)=1$. Conversely, if $x-y=p(A)x$ with these properties, then $q(t)=(1-p(t))/t$ is a polynomial of degree at most $k-1$ andThis is the polynomial description of the admissible errors in a Krylov subspace method.

For $[a,b]=[1,2]$, $z(0)=-3$ and $\cosh \theta =3$ gives $e^{\theta }=3+2\sqrt{2}$. The normalization factors cancel, soIf the eigenvalues are known to be exactly $1,3/2,2$, use the more targeted annihilating polynomialIt equals one at zero and vanishes on the entire spectrum, so the spectral theorem gives $p_3(A)=0$. Thus $y^{(3)}=x$ in exact arithmetic. Degree three is the least degree that can vanish at all three distinct eigenvalues; a particular initial error supported on fewer eigenspaces can terminate earlier.

Map $[a,b]$ to $[-1,1]$ by $z(r)=(2r-a-b)/(b-a)$. Since $a>0$, the normalization point $z(0)=-(a+b)/(b-a)$ lies outside that interval. The proposed Chebyshev polynomial ratio has degree $k$ and equals one at zero. On the spectral interval its maximum absolute value isThe Chebyshev minimax polynomial with exterior normalization minimizes this maximum among degree-at-most-$k$ polynomials with $p(0)=1$. One may quote the minimax property. Its reason is the alternating $k+1$ extremal values: a strictly better competitor would force their difference to have at least $k$ roots in $[a,b]$ and the additional root at zero outside it, impossible for degree at most $k$.

The paper uses a monic normalization of $T_k$ for $k\ge 1$, rather than the usual $T_k(1)=1$ convention. The common factor cancels in the ratio. With $\kappa =b/a>1$ and $q=(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, the hyperbolic-cosine formula gives the error factor $\boxed{2q^k/(1+q^{2k})\le 2q^k}$. This tends rapidly to zero when the spectral interval is well-conditioned. If $a=b$, use $p(r)=1-r/a$ for exact one-step termination instead of the displayed interval map.

Let $e_j=x-x^{(j)}$. The underlying Richardson iteration gives $e_j=(I-A{)}^j{e}_0$. The polynomials $1,(1-t),\dots ,(1-t{)}^k$ form a basis for polynomials of degree at most $k$. Thus writeDefine $y^{(k)}={\sum }_{j=0}^k{c}_j{x}^{(j)}$. Since the coefficients sum to one,The spectral theorem for real symmetric matrices supplies an orthonormal basis of eigenvectors. In that basis $p_k(A)$ has diagonal entries $p_k({\lambda }_i)$, soThe algebraic recombination is valid in exact arithmetic even if the original unaccelerated iterates themselves fail to converge.

Order points along each $j$-line before moving to the next $k$-line. The splitting hasand $N$ couples the two neighboring $k$-lines. Factor $T_n$ once with the Thomas algorithm; each iteration then needs $n$ tridiagonal solves and the neighboring-line right sides, costing $\boxed{O(n^2)}$ for $n^2$ unknowns. Known boundary values are moved to the right side; the error eigenmodes have homogeneous boundary values.

The generalized eigenvalue problem iswith $U=0$ at the boundary indices. Put ${\theta }_r=r\pi /(n+1)$, ${\theta }_s=s\pi /(n+1)$. The sine addition formula gives $U_{j+1,k}+U_{j-1,k}=2\cos {\theta }_r{U}_{j,k}$ and the corresponding identity in $k$. ThusThese tensor-product sine vectors form a basis, so they give the whole spectrum. With $c=\cos (\pi /(n+1))\in [0,1)$,The iteration therefore converges.

It is not a uniformly effective multigrid smoother. Take $r=1$ and $s=n$: the error is slowly varying along a line but highly oscillatory between lines, and its multiplier is $-c/(2-c)\to -1$ as the grid is refined. It changes sign at each step while retaining almost its full amplitude. This line-Jacobi Fourier spectrum distinguishes convergence on each fixed grid from the high-frequency damping needed by the multigrid method.

Write $G=M^{-1}N$. Subtracting the exact equation $Mx=Nx+b$ from the iteration gives $e_{\ell +1}=G{e}_{\ell }$, where $e_{\ell }=x-x^{(\ell )}$. Hence $e_{\ell }=G^{\ell }{e}_0$. Alsoso the stated scalars are precisely the eigenvalues of the iteration matrix $G$.

The spectral radius criterion for matrix powers states that $G^{\ell }\to 0$ if and only if all its eigenvalues have modulus strictly less than one. Applying that theorem gives $e_{\ell }\to 0$ for every initial vector. Therefore $\boxed{x^{(\ell )}\to A^{-1}b}$.

For a tridiagonal matrix with subdiagonal $a_i$, diagonal $b_i$ and superdiagonal $c_i$, banded Gaussian elimination introduces no fill beyond the original band. The Thomas algorithm usesUpdate the right side by $d_1=f_1$, $d_i=f_i-{\ell }_i{d}_{i-1}$. Then back substitution givesEach row requires only a fixed number of arithmetic operations, so both work and storage are $\boxed{O(n)}$. The assumed absence of a need for pivoting includes nonzero elimination pivots $p_i$.

A generic lower triangular matrix has a dense first column. The first left Householder transformation in its QR decomposition mixes those rows, usually creating entries throughout the rows to the right. Subsequent eliminations impose upper triangularity but no further systematic zeros; thus $R$ is generically a full upper triangular matrix.

For Householder bidiagonalization use two-sided operations instead. At stage $j$, a right Householder transformation acting on columns $j,\dots ,n$ clears the current row $j$ beyond its diagonal. Then a left Householder transformation acting on rows $j+1,\dots ,n$ clears column $j$ below its first subdiagonal. The left operation leaves row $j$ unchanged; both operations preserve the already completed lower-bidiagonal rows and columns. Continue for $j=1,\dots ,n-1$, omitting a final unnecessary left operation. The result isIt follows that $B^{T}B=Q^T{A}^{T}AQ$. Hence the two symmetric matrices are orthogonally similar and have the same eigenvalues. By part (c), compute the eigenvalues of the symmetric tridiagonal matrix $B^{T}B$ and take their nonnegative square roots to obtain all singular values of $A$.

The singular value decomposition $A=U\Sigma V^T$ givesTherefore $\boxed{{\sigma }_i(A)=\sqrt{{\lambda }_i(A^{T}A)}}$, counting multiplicities. These are the nonnegative square roots: zero singular values must be included if $A$ is singular. Strict positivity requires full rank, which the question does not assume.

Write the lower bidiagonal matrix entries as $B_{ii}=d_i$ and $B_{i+1,i}=e_i$. Its columns $i$ and $j$ have disjoint supports if $|i-j|>1$, so $T=B^{T}B$ has no entries outside the three central diagonals. More explicitly,This proves both symmetry and the tridiagonal matrix structure.

If $x\ne 0$, choose $\alpha =-\mathrm{sgn}(x_1)\Vert x{\Vert }_2$, with $\mathrm{sgn}(0)=1$ for this choice, and put $v=x-\alpha e_1$. This nonzero vector satisfiesThus the Householder matrix $H=I-2v{v}^T/(v^{T}v)$ gives $Hx=x-v=\alpha e_1$. Symmetry gives $\boxed{x^{T}H=\alpha e_1^T}$. If $x=0$, any Householder matrix works with $\alpha =0$.

For an LQ decomposition, process rows $j=1,\dots ,\min (m,n)$. At step $j$, postmultiply by an orthogonal block matrix $H_j=\mathrm{diag}(I_{j-1},{\hat{H}}_j)$ that zeros entries to the right of the diagonal in the current row. If its row tail is already suitable, use the identity. Earlier processed rows have zero entries throughout this trailing block, so their zeros are preserved. Consequently $L=A{H}_1\cdots H_r$ has $l_{ij}=0$ for $i<j$. Setting $\boxed{Q=H_r^T\cdots H_1^T}$ gives $\boxed{A=LQ}$. The argument handles both rectangular shapes; $L$ is lower trapezoidal when it is not square.

A linear spline is a continuous function whose restriction to every interval $[x_{i-1},x_i]$ is a polynomial of polynomial degree at most one. With $h_i=x_i-x_{i-1}$ and ${\ell }_i=\ell (x_i)$, linear interpolation givesIntegrating the two linear polynomials and adding the contributions givesThis is the composite trapezoidal rule applied to the nodal values, and it is exact for the linear spline itself, including nonuniform spline knots.

A cubic spline on this partition of an interval is a function $S\in C^2[x_0,x_n]$ that restricts to a polynomial of polynomial degree at most three on every interval $[x_{i-1},x_i]$. Thus its second derivative is continuous and piecewise of polynomial degree at most one: $S^{\prime \prime }$ is a linear spline on the same spline knots. Its third derivative is constant on each open interval and can jump across the spline knots; its fourth derivative vanishes inside each open interval.

For a real square matrix, a QR factorization writes $B=QR$ with $Q$ an orthogonal matrix, $Q^{T}Q=I$, and $R$ an upper triangular matrix. If $B$ is invertible, so is $R$, andCompute $Q^{T}b$ and use back substitution; no matrix inverse needs to be formed.

Apply the Gram-Schmidt process to the columns $b_1,b_2,b_3$. The first column has Euclidean norm two, giving $q_1=(1,0,0{)}^T$ and $r_{11}=2$. For the second column,For the third column,This residual already has Euclidean norm one. Set $q_3=(0,-3/5,4/5{)}^T$ and $r_{33}=1$. ThusThe columns of $Q$ are orthonormal, and matrix multiplication verifies $QR=B$.

Using precisely this QR factorization, transform the right-hand side:Back substitution in $Rx=Q^{T}b$ givesTherefore

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.

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$.