The energy norm associated with this symmetric positive-definite matrix isIt is the norm induced by the inner product $⟨u,v{⟩}_A=u^{T}Av$. The conjugate gradient method minimizes this error norm over its successive affine Krylov subspaces.

For a unit eigenvector of $A$, $(A-I)x=(\lambda -1)x$. The matrix 2-norm bound from part (a) gives $|\lambda -1|\le 2/3$. Hence every eigenvalue lies inIn particular the condition number in the Euclidean operator norm satisfies ${\kappa }_2(A)={\lambda }_{\max }/{\lambda }_{\min }\le 5$.

An eigenvalue of $A$ is a scalar $\lambda$ for which $Az=\lambda z$ has a nonzero eigenvector. Allowing initially $z\in {\mathbb{C}}^m$, symmetry of the real matrix gives $A^{\ast }=A$, so $z^{\ast }Az$ is real. Since $z^{\ast }z>0$,This proves reality without presuming it when choosing the eigenvector. Once $\lambda$ is real, the real or imaginary part of $z$ supplies a nonzero real eigenvector.

A real symmetric matrix is positive-definite when $x^{T}Ax>0$ for every nonzero real vector $x$. The preceding matrix 2-norm bound givesThus $A$ is a symmetric positive-definite matrix, independently of the detailed positions of the nonzero entries of $t$.

The off-diagonal Toeplitz matrix $T=A-I$ is symmetric and has row and column absolute sums bounded byFor an elementary Euclidean bound, apply the weighted Cauchy-Schwarz inequality in each row:Sum over $i$ and use both absolute-sum bounds to get $\Vert Tx{\Vert }_2^2\le r^2\Vert x{\Vert }_2^2$. ThereforeThe entry $t_1$ is unused because the diagonal of $A$ is fixed to one; including it only weakens the bound. This is the row-column bound for the matrix 2-norm.

Solving the $m$ unrelated shifted systems by separate Gaussian elimination costs $\boxed{\frac{2}{3}{m}^4+O(m^3)}$ floating-point operations.

Instead compute $H=Q^{T}AQ$ once in $O(m^3)$ work. For each shift, solveThe shift changes only the diagonal, so $H-{\lambda }_{j}I$ remains an upper Hessenberg matrix. In each elimination column only the entry immediately below the pivot needs removal. With partial pivoting the only possible nonzero candidate rows are the current row and the next, and each update touches $O(m)$ entries. Factorization therefore costs $O(m^2)$ per shift; the triangular solve and both orthogonal-vector transformations also cost $O(m^2)$ each.

Thus $m$ shifted solves plus the initial Hessenberg reduction cost $\boxed{O(m^3)}$ in total. Pivoting is still needed in general: nonsingularity excludes a singular system but does not by itself guarantee that every unpivoted elimination pivot is nonzero.

An orthogonal similarity transformation is $H=Q^{T}AQ$ with $Q^{T}Q=I$. An upper Hessenberg matrix has $H_{ij}=0$ whenever $i>j+1$; its first subdiagonal may be nonzero.

At step $k=1,\dots ,m-2$, choose a Householder reflector $Q_k=\mathrm{diag}(I_k,{\hat{Q}}_k)$ whose trailing block sends the current column segment in rows $k+1,\dots ,m$ to a multiple of its first coordinate. The left multiplication zeros positions $(k+2,k),\dots ,(m,k)$. Apply the matching right multiplication to retain similarity: $A\leftarrow Q_k^{T}A{Q}_k$. Since $Q_k$ acts only on rows and columns $k+1,\dots ,m$, earlier Hessenberg zeros are preserved. Finally $Q=Q_1\cdots Q_{m-2}$ gives $H=Q^{T}AQ$.

Each reflector is applied through a rank-one update, costing $O(m^2)$ rather than a full matrix multiplication. Across $m-2$ steps, the Hessenberg reduction costs $O(m^3)$.

At elimination column $k$, let $r=m-k$ be the size of the remaining trailing block. Computing its multipliers costs $r$ divisions; updating all $r^2$ entries costs $2r^2$ floating-point operations, one multiplication and one subtraction per entry. Thus the dominant count isUpdating the right side and back substitution add only $O(m^2)$ floating-point operations. Pivot searches involve comparisons and row exchanges, without changing the leading arithmetic count. Hence Gaussian elimination with pivoting has the requested asymptotic cost.

Let $r$ be the matrix rank, and partition the right singular vectors as $V=(V_r{V}_0)$, with $V_0\in {\mathbb{R}}^{n\times (n-r)}$ consisting of the columns associated with zero singular values. From $Ax=0⟺\Sigma V^{T}x=0$, these columns form an orthonormal basis of the nullspace. Therefore its orthogonal projector isIt acts on the input space ${\mathbb{R}}^n$. Symmetry and idempotence follow from $V_0^T{V}_0=I_{n-r}$. At full column rank it is zero, and at rank zero it is the identity.

The nullspace is the vector subspace $\boxed{\ker A=\{x\in {\mathbb{R}}^n:Ax=0\}}$. A full real singular value decomposition iswhere $U,V$ are orthogonal matrices and ${\Sigma }_{ij}=0$ for $i\ne j$, with ${\Sigma }_{jj}={\sigma }_j\ge 0$ for $1\le j\le n$. We may order ${\sigma }_1\ge \cdots \ge {\sigma }_n\ge 0$. The columns of $V$ form an orthonormal basis of the input space ${\mathbb{R}}^n$, and the columns of $U$ form one of the output space ${\mathbb{R}}^m$. The positive singular values number exactly the matrix rank.

The perpendicular decomposition in part (a) gives, by the Pythagorean theorem,Thus an orthogonal projection cannot lengthen a vector and $\boxed{\Vert P{\Vert }_2\le 1}$. Algebraically the cross term vanishes because $P^T(I-P)=P-P^2=0$, giving the same identity directly from the hypotheses. If $P\ne 0$, take a nonzero $x$ in its range; then $Px=x$ and $\Vert P{\Vert }_2=1$. For $P=0$ the norm is zero.

The vector Euclidean norm is $\boxed{\Vert x{\Vert }_2=(x^{T}x{)}^{1/2}=(\sum _i{x}_i^2{)}^{1/2}}$, the ordinary length from the origin. The induced matrix norm isGeometrically this is the largest stretch of a unit vector. A linear map sends the unit sphere to an ellipsoid, possibly degenerate; its largest semiaxis has length $\Vert A{\Vert }_2$. Equivalently the matrix 2-norm is the largest singular value.

An orthogonal projector sends $x$ to the foot $Px$ of its perpendicular onto the image of a linear map $\mathrm{range}P$. The residual $r=x-Px$ is orthogonal to the entire range, not just to the single vector $Px$. Indeed, for any range vector $Pv$,In particular $\boxed{(Px{)}^T(x-Px)=0}$. The orthogonal projection diagram illustrates the resulting right triangle.

On the strictly feasible set ${\Omega }_c^{\circ }=\{x:c_j(x)>0\text{ for all }j\}$, use the logarithmic barrierChoose a strictly feasible starting point and parameters ${\mu }_n\downarrow 0$. For each parameter minimize the barrier functional by an unconstrained method confined to ${\Omega }_c^{\circ }$, warm-starting from the preceding point. In the exact version take a stationary point $x_n$ of the barrier subproblem. The stationarity equation isThese are the natural Lagrange multiplier estimates; the basic method need not perform a separate primal-dual correction.

The barrier method KKT convergence theorem is a global stationarity result: if the exact barrier stationary points form a bounded sequence, then every cluster point satisfying the linear independence constraint qualification is a KKT point. To prove it, take any subsequence $x_n\to x_{\ast }$. Continuity gives feasibility of $x_{\ast }$. For an inactive index, $c_j(x_{\ast })>0$ and therefore ${\lambda }_{n,j}={\mu }_n/c_j(x_n)\to 0$.

The active gradients at $x_{\ast }$ are independent. The supplied dual-basis result gives bounded vectors ${\phi }_{n,i}$, converging as $n\to \infty$, with $\nabla c_j(x_n{)}^T{\phi }_{n,i}={\delta }_{ji}$ for active $i,j$. Pair stationarity with these vectors:Thus all active multipliers are bounded as well. Extract a convergent multiplier subsequence. Its limit is nonnegative, satisfies stationarity by continuity, and satisfies complementarity because ${\lambda }_{n,j}{c}_j(x_n)={\mu }_n\to 0$. This proves the claimed KKT conclusion. The same proof permits approximate barrier stationary points whose stationarity residual tends to zero. Bounded iterates and the constraint qualification are substantive hypotheses, not automatic consequences of writing a barrier functional.

For a global-minimum conclusion one needs global minimization of the barrier subproblems and appropriate access to every feasible point. Specifically, suppose $x_n$ globally minimizes ${\Phi }_{{\mu }_n}$, has a cluster point $x_{\ast }$, and $\overline{{\Omega }_c^{\circ }}=\Omega$. For any fixed strictly feasible $z$,Along the convergent subsequence the $c_j(x_n)$ are bounded above, so taking the upper limit gives $f(x_{\ast })\le f(z)$. Density of strictly feasible points and continuity of $f$ extend the inequality to every feasible $z$. Hence $x_{\ast }$ is a global minimizer under these stronger hypotheses.

The active constraint set is $\boxed{\mathcal{A}(x)=\{j:c_j(x)=0\}}$, and the linearized tangent cone isDifferentiating each active feasibility inequality along a tangent sequence gives $T_{\Omega }(x)\subseteq F(x)$. A sufficient condition for equality is the linear independence constraint qualification: the active constraint gradients are linearly independent. The weaker Mangasarian–Fromovitz constraint qualification also suffices in this inequality-only setting.

Under the stated independence condition, the necessary first-order conditions become the Karush-Kuhn-Tucker conditions: there are multipliers ${\lambda }_j$ withUse the allowed span assertion to write $\nabla f(x_{\ast })={\sum }_{j\in \mathcal{A}}{\lambda }_j\nabla c_j(x_{\ast })$. Independence gives vectors ${\phi }_i$ with $\nabla c_j(x_{\ast }{)}^T{\phi }_i={\delta }_{ji}$ for the active indices. Each ${\phi }_i$ lies in $F=T_{\Omega }$, so part (a) gives ${\lambda }_i=\nabla f(x_{\ast }{)}^T{\phi }_i\ge 0$. Assign zero multipliers to inactive constraints. This proves all displayed conditions, including complementarity. Conversely, their stationarity and sign conditions imply $\nabla f(x_{\ast }{)}^{T}d={\sum }_{j\in \mathcal{A}}{\lambda }_j\nabla c_j(x_{\ast }{)}^{T}d\ge 0$ for every $d\in F$. Thus they reformulate the first-order inequality; they do not alone prove a minimum for a nonconvex problem.

The contingent tangent cone consists of feasible first-order velocities:If $x_{\ast }$ is a local minimizer, then $\boxed{\nabla f(x_{\ast }{)}^{T}d\ge 0\text{ for every }d\in T_{\Omega }(x_{\ast })}$. Indeed, $x_n\to x_{\ast }$ along the defining sequence, so eventually $f(x_n)-f(x_{\ast })\ge 0$. Differentiability givesThis proves the inequality. Using feasible limiting velocities avoids assuming that every tangent direction is realized by a straight segment staying in the feasible set.

Put $J(x)=DR(x)$, with one residual gradient per row. The chain rule givesDifferentiating each product givesThe approximation $B_n=J(x_n{)}^{T}J(x_n)$ defines the Gauss-Newton method. It is symmetric, and full column rank gives $v^T{B}_{n}v=\Vert J(x_n)v{\Vert }_2^2>0$ for $v\ne 0$, so the step is well-defined.

If $x_n\to x_{\ast }$, $R(x_{\ast })=0$ and $J(x_{\ast })$ has full column rank, then $\nabla f(x_{\ast })=0$ and $H_{\ast }={\nabla }^{2}f(x_{\ast })=J(x_{\ast }{)}^{T}J(x_{\ast })$ is positive definite. Continuity of $J$ gives $B_n\to H_{\ast }$. ThereforeThe Dennis-Moré condition applies, proving $\boxed{x_n\to x_{\ast }\text{ q-superlinearly}}$, or finite termination. The zero-residual hypothesis is what makes the discarded second-derivative term vanish at the limit.

A quasi-Newton method replaces the Hessian in the Newton system by an efficiently updated approximation $B_n$:The matrices must be nonsingular for the step to exist. Symmetry reflects the true Hessian, and positive definiteness makes every nonzero step a descent direction, since $\nabla f(x_n{)}^T{s}_n=-s_n^T{B}_n{s}_n<0$. Secant updates often enforce the Quasi-Newton secant equation $B_{n+1}{s}_n=\nabla f(x_{n+1})-\nabla f(x_n)$.

Q-superlinear convergence means $\Vert x_{n+1}-x_{\ast }\Vert /\Vert x_n-x_{\ast }\Vert \to 0$, unless the sequence terminates exactly. A sufficient Dennis-Moré condition isassuming $x_n\to x_{\ast }$, $\nabla f(x_{\ast })=0$, continuous Hessian near $x_{\ast }$ and nonsingular $H_{\ast }$. Only accuracy on the actual step direction is required; full matrix convergence $B_n\to H_{\ast }$ is sufficient but stronger.

To prove the assertion, continuity of the Hessian along the short segment from $x_n$ to $x_{n+1}$ givesNonsingularity of $H_{\ast }$ and $\nabla f(x_{\ast }+e)=H_{\ast }e+o(\Vert e\Vert )$ give a constant $C$ with $\Vert e\Vert \le C\Vert \nabla f(x_{\ast }+e)\Vert$ near zero. Writing $e_n=x_n-x_{\ast }$, we obtainThus $\Vert e_{n+1}\Vert /\Vert e_n\Vert \le {\epsilon }_n/(1-{\epsilon }_n)\to 0$. This proves sufficiency. It is a local rate result for an already convergent sequence, not a claim that arbitrary unmodified quasi-Newton iterations converge from every starting point.

A local minimizer of a differentiable function on ${\mathbb{R}}^N$ necessarily satisfies $\boxed{\nabla f(x_{\ast })=0}$. A sufficient condition for a strict local minimum is $\boxed{\nabla f(x_{\ast })=0,{\nabla }^{2}f(x_{\ast })\text{ positive definite}}$. Indeed, the second-order Taylor expansion has a strictly positive quadratic term that dominates its $o(\Vert x-x_{\ast }{\Vert }^2)$ remainder near $x_{\ast }$.

For Newton's method, solve $H_n{s}_n=-g_n$ with $H_n={\nabla }^{2}f(x_n)$, $g_n=\nabla f(x_n)$, and set $x_{n+1}=x_n+s_n$. A positive-definite Hessian makes this a descent direction; general Hessians may need modification or a separate line search for a globally useful method.

The sequence is q-quadratically convergent if there is $C<\infty$ such that $\Vert x_{n+1}-x_{\ast }\Vert \le C\Vert x_n-x_{\ast }{\Vert }^2$ eventually. Sufficient local hypotheses are $\nabla f(x_{\ast })=0$, a nonsingular $H_{\ast }={\nabla }^{2}f(x_{\ast })$, a Lipschitz continuous Hessian near $x_{\ast }$, and $x_0$ sufficiently close. For convergence to a local minimum take $H_{\ast }$ positive definite. Near $x_{\ast }$, inverse Hessians are uniformly bounded, and integration along the error segment givesA Hessian Lipschitz constant $L_H$ yields $\Vert x_{n+1}-x_{\ast }\Vert \le \frac{1}{2}{L}_H\Vert H_n^{-1}\Vert \Vert x_n-x_{\ast }{\Vert }^2$. Choosing a sufficiently small invariant neighborhood proves quadratic convergence. Continuous second derivatives alone do not guarantee this quadratic rate; the Lipschitz hypothesis supplies the needed remainder bound.

For any vectors $a,b$,Thus, among directions with $\Vert d{\Vert }_{\infty }\le 1$, $g^{T}d\ge -\Vert g{\Vert }_1$. Equality is achieved byFor $g\ne 0$ these minimizing directions have infinity norm one. The strongest decrease per unit infinity-norm step is $-\Vert g{\Vert }_1$, illustrating the dual norm pairing between the infinity norm and the one-norm.

To match the unnormalized convention in part (a), minimize $g^{T}s+\frac{1}{2}\Vert s{\Vert }_{\infty }^2$. At fixed $t=\Vert s{\Vert }_{\infty }$, its minimum is $-t\Vert g{\Vert }_1+\frac{1}{2}{t}^2$, attained at $t=\Vert g{\Vert }_1$. One conventional choice is therefore $\boxed{s=-\Vert g{\Vert }_1\mathrm{sgn}(g)}$, with zero entries where $g_j=0$. Its ray agrees with the unit direction just computed.