本文为《Linear algebra and its applications》的读书笔记

目录

Least-Squares problemsSolution of the General Least-Squares ProblemAlternative Calculations of Least-Squares Solutions 最小二乘解的另一个计算

Least-Squares problems

Inconsistent systems arise often in applications. When a solution is demanded and none exists, the best one can do is to find an $\mathbf{x}$ that makes $A\mathbf{x}$ as close as possible to $\mathbf{b}$.Think of $A\mathbf{x}$ as an $approximation$ to $\mathbf{b}$. The smaller the distance between $\mathbf{b}$ and $A\mathbf{x}$, given by $\Vert \mathbf{b}-A\mathbf{x}\Vert$, the better the approximation.The general least-squares problem is to find an $\mathbf{x}$ that makes $\Vert \mathbf{b}-A\mathbf{x}\Vert$ as small as possible. $\Vert \mathbf{b}-A\mathbf{x}\Vert$ is called the least-squares error of this approximation.

The adjective “least-squares” arises from the fact that $\Vert \mathbf{b}-A\mathbf{x}\Vert$ is the square root of a sum of squares.

---

Notice that $A\mathbf{x}$ will necessarily be in $ColA$. So we seek an $\mathbf{x}$ that makes $A\mathbf{x}$ the closest point in $ColA$ to $\mathbf{b}$. See Figure 1.

Solution of the General Least-Squares Problem

Apply the Best Approximation Theorem in Section 6.3 to the subspace $ColA$. Let $$\hat{\mathbf{b}}=pro{j}_{ColA}\mathbf{b}$$

Because $\hat{\mathbf{b}}$ is in $ColA$, the equation $A\mathbf{x}=\hat{\mathbf{b}}$ is consistent, and there is an $\hat{\mathbf{x}}$ in ${\mathbb{R}}^n$ such that $$A\hat{\mathbf{x}}=\hat{\mathbf{b}}(1)$$

Since $\hat{\mathbf{b}}$ is the closest point in $ColA$ to $\mathbf{b}$, a vector $\hat{\mathbf{x}}$ is a least-squares solution of $A\mathbf{x}=\mathbf{b}$ if and only if $\hat{\mathbf{x}}$ satisfies (1). See Figure 2. [There are many solutions of (1) if the equation has free variables.]

Suppose $\hat{\mathbf{x}}$ satisfies $A\hat{\mathbf{x}}=\hat{\mathbf{b}}$. By the Orthogonal Decomposition Theorem in Section 6.3, $\mathbf{b}-\hat{\mathbf{b}}$ is orthogonal to $ColA$, so $\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to each column of $A$. If ${\mathbf{a}}_j$ is any column of $A$, then ${\mathbf{a}}_j\cdot (\mathbf{b}-A\hat{\mathbf{x}})=0$, and ${\mathbf{a}}_j^T(\mathbf{b}-A\hat{\mathbf{x}})=0$. Since each ${\mathbf{a}}_j^T$ is a row of $A^T$ , $$A^T(\mathbf{b}-A\hat{\mathbf{x}})=0(2)$$(This equation also follows from Theorem 3 in Section 6.1.) Thus $$\begin{array}{rl}{A}^T\mathbf{b}-A^{T}A\hat{\mathbf{x}}& =0\\ A^{T}A\hat{\mathbf{x}}& =A^T\mathbf{b}\end{array}$$

These calculations show that each least-squares solution of $A\mathbf{x}=\mathbf{b}$ satisfies the equation

The equation represents a system of equations called the normal equations (法方程) for $A\mathbf{x}=\mathbf{b}$. A solution of (3) is often denoted by $\hat{\mathbf{x}}$.

The next theorem gives useful criteria for determining when there is only one leastsquares solution of $A\mathbf{x}=\mathbf{b}$. (Of course, the orthogonal projection $\hat{\mathbf{b}}$ is always unique.)

Formula (4) for $\hat{\mathbf{x}}$ is useful mainly for theoretical purposes and for hand calculations when $A^{T}A$ is a $2\times 2$ invertible matrix.

PROOF If $A\mathbf{x}=0$, then $A^{T}A\mathbf{x}=0$ $\therefore NulA\subseteq Nul{A}^{T}A$. If $A^{T}A\mathbf{x}=0$, then ${\mathbf{x}}^T{A}^{T}A\mathbf{x}=(A\mathbf{x}{)}^{T}A\mathbf{x}=0$ $\therefore A\mathbf{x}=0$ $\therefore Nul{A}^{T}A\subseteq NulA$. $$\begin{gathered} \therefore NulA=Nul{A}^{T}A \\ \therefore rank{A}^{T}A=n-dimNul{A}^{T}A=n-dimNulA=rankA \end{gathered}$$

So when $A$ has $n$ linearly independent columns, $rank{A}^{T}A=rankA=n$, which means $A^{T}A$ is an invertible matrix.

Alternative Calculations of Least-Squares Solutions 最小二乘解的另一个计算

The next example shows how to find a least-squares solution of $A\mathbf{x}=\mathbf{b}$ when the columns of $A$ are orthogonal. Such matrices often appear in linear regression problems.

EXAMPLE 4 Find a least-squares solution of $A\mathbf{x}=\mathbf{b}$ for

SOLUTION Because the columns ${\mathbf{a}}_1$ and ${\mathbf{a}}_2$ of $A$ are orthogonal, the orthogonal projection of $\mathbf{b}$ onto $ColA$ is given by

Now that $\hat{\mathbf{b}}$ is known, we can solve $A\hat{\mathbf{x}}=\hat{\mathbf{b}}$. But this is trivial(简单), since we already know what weights to place on the columns of $A$ to produce $\hat{\mathbf{b}}$. It is clear from (5) that

In some cases, the normal equations for a least-squares problem can be $ill-conditioned(病态的)$; that is, small errors in the calculations of the entries of $A^{T}A$ can sometimes cause relatively large errors in the solution $\hat{\mathbf{x}}$. If the columns of $A$ are linearly independent, the least-squares solution can often be computed more reliably through a $QR$ factorization of $A$ (described in Section 6.4).