线性代数代写|schmidt gram orthogonal代写|QR decomposition代写|least square regression代写

证明 . This simply involves multiplying the block matrices out: $$ A^{T} A=\left[\begin{array}{ll} R^{T} & 0 \end{array}\right] Q^{T} Q\left[\begin{array}{l} R \\ \end{array}\right]=\left[\begin{array}{ll} R^{T} & 0 \end{array}\right]\left[\begin{array}{l} R \\ \end{array}\right]=R^{T} R $$

证明 . (a) To find out what \(\alpha_{k}\) is, apply the recurrence relation to the definition of \(f\left(x_{k+1}\right)\) : \(\begin{aligned} f\left(x_{k+1}\right) &=\frac{1}{2}\left(x_{k}+\alpha_{k} r_{k}\right)^{T} A\left(x_{k}+\alpha_{k} r_{k}\right)-\left(x_{k}+\alpha_{k} r_{k}\right)^{T} b \\ &=\frac{1}{2}\left(x_{k}^{T} A x_{k}+\alpha_{k} r_{k}^{T} A x_{k}+\alpha_{k} x_{k}^{T} A r_{k}+\alpha_{k}^{2} r_{k}^{T} A r_{k}\right)-x_{k}^{T} b-\alpha_{k} r_{k}^{T} b \\ &=\frac{1}{2}\left(x_{k}^{T} A x_{k}+\alpha_{k} r_{k}^{T} A x_{k}+\alpha_{k} r_{k}^{T} A^{T} x_{k}+\alpha_{k}^{2} r_{k}^{T} A r_{k}\right)-x_{k}^{T} b-\alpha_{k} r_{k}^{T} b \\ &=\frac{1}{2}\left(x_{k}^{T} A x_{k}+\alpha_{k} r_{k}^{T} A x_{k}+\alpha_{k} r_{k}^{T} A x_{k}+\alpha_{k}^{2} r_{k}^{T} A r_{k}\right)-x_{k}^{T} b-\alpha_{k} r_{k}^{T} b \\ &=\frac{1}{2}\left(x_{k}^{T} A x_{k}+2 \alpha_{k} r_{k}^{T} A x_{k}+\alpha_{k}^{2} r_{k}^{T} A r_{k}\right)-x_{k}^{T} b-\alpha_{k} r_{k}^{T} b \end{aligned}\) Now differentiate with respect to \(\alpha_{k}\) and set to zero: $$ \begin{aligned} \frac{d}{d \alpha_{k}} f\left(x_{k+1}\left(\alpha_{k}\right)\right) &=r_{k}^{T} A x_{k}+\alpha r_{k}^{T} A r_{k}-r_{k}^{T} b=0 \\ \alpha_{k} r_{k}^{T} A r_{k} &=r_{k}^{T} b-r_{k}^{T} A x_{k}=r_{k}^{T} r_{k} \end{aligned} $$ Isolating \(\alpha_{k}\) yields the desired result. Note that \(\alpha>0,\) since \(A\) is positive definite. (b) It helps to first establish a recurrence relation involving the residuals only: note that $$ r k+1=b-A x_{k+1}=b-A\left(x_{k}+\alpha_{k} r_{k}\right)=r_{k}-\alpha_{k} A r_{k} $$ Then $$ \begin{aligned} r_{k+1}^{T} r_{k} &=\left(r_{k}-\alpha_{k} A r_{k}\right)^{T} r_{k} \\ &=r_{k}^{T} r_{k}-\left(\frac{r_{k}^{T} r_{k}}{r_{k}^{T} A r_{k}}\right) r_{k}^{T} A^{T} r_{k} \\ &=0 \end{aligned} $$ since \(A=A^{T}\). (c) First, note that $$ r_{k}=b-A x_{k}=A x-A x_{k}=A\left(x-x_{k}\right)=A e_{k} $$ so that \(r_{k}^{T} A^{-1} r_{k}=e_{k}^{T} A^{T} A^{-1} A e_{k}=e_{k}^{T} A e_{k},\) and similarly for \(r_{k+1}\). Thus, the two inequalities are completely equivalent. Now we attack the inequality involving \(r\) : $$ \begin{aligned} r_{k+1}^{T} A^{-1} r_{k+1} &=r_{k+1}^{T} A^{-1}\left(r_{k}-\alpha_{k} A r_{k}\right) \\ &=r_{k+1}^{T} A^{-1} r_{k}-\underbrace{\alpha_{k} r_{k+1}^{T} r_{k}}_{0 \text { by (b) }} \\ &=\left(r_{k}-\alpha_{k} A r_{k}\right)^{T} A^{-1} r_{k} \\ &=r_{k} A^{-1} r_{k}-\underbrace{\alpha_{k} r_{k}^{T} r_{k}}_{>0} \\ &<r_{k} A^{-1} r_{k} . \end{aligned} $$

证明 . Solution. (a) We need two facts: i. \(P, Q\) orthogonal \(\Longrightarrow P Q\) orthogonal ii. \(P\) upper triangular \(\Longrightarrow P^{-1}\) upper triangular (i) is easy: \((P Q)^{T}(P Q)=Q^{T} P^{T} P Q=Q^{T} I Q=Q^{T} Q=I\). (ii) can be argued by considering the \(k\) th column \(p_{k}\) of \(P^{-1}\). Then \(P^{-1} e_{k}=p_{k},\) so \(P p_{k}=e_{k}\). Since \(P\) is upper triangular, we can use backward substitution to solve for \(p_{k} .\) Recall the formula for backward substitution for a general upper triangular system \(T x=b\) : $$ x_{k}=\frac{1}{t_{k k}}\left(b_{k}-\sum_{j=k+1}^{n} t_{k j} b_{j}\right) $$ In our case, we see that since \(\left(e_{k}\right)_{j}=0\) for \(j>k,\) this implies \(\left(p_{k}\right)_{j}=0\) for \(j>k .\) In other words, the \(k\) th column of \(P^{-1}\) must be all zero below the \(k\) th row. This is to say \(P^{-1}\) is upper triangular. Now we show that \(B\) both orthogonal and triangular implies \(B\) diagonal. Without loss of generality (i.e. replacing \(B\) by \(B^{T}\) if necessary), we can assume \(B\) is upper triangular. Then \(B^{-1}\) is also upper triangular by (ii). But \(B^{-1}=B^{T}\) by orthogonality, and we know \(B^{T}\) is lower triangular. So \(B^{T}\) (and hence \(B\) ) is both upper and lower triangular, implying that \(B\) is in fact diagonal. (b) We know \(B\) is diagonal, so that \(B=B^{T} .\) Let \(B=\operatorname{diag}\left(b_{11}, \ldots, b_{n n}\right) .\) Then \(I=B B^{T}=\) \(\operatorname{diag}\left(b_{11}^{2}, \ldots, b_{n n}^{2}\right),\) so \(b_{i i}^{2}=1\) for all \(i .\) Thus, the diagonal entries of \(B\) are \(\pm 1 .\) (c) There is an existence part and a uniqueness part to this problem. In class we showed existence of a decomposition \(A=Q R\) where \(Q\) is orthogonal, and \(R\) is upper triangular, but not necessarily with positive entries on the diagonal, so we have to fix it up. We know that \(r_{i i} \neq 0\) (otherwise \(R\) would be singular, contradicting the non-singularity of \(A\) ), so we can define $$ D=\operatorname{diag}\left(\operatorname{sgn}\left(r_{11}\right), \ldots, \operatorname{sgn}\left(r_{n n}\right)\right) $$ where $$ \operatorname{sgn}(x)=\left\{\begin{array}{ll} 1, & x>0 \\ 0, & x=0 \\ -1, & x<0 \end{array}\right. $$ Note that \(D\) is orthogonal, and \(\tilde{R}=D R\) has positive diagonal. So if we define \(\tilde{Q}=Q D\) (orthogonal), then \(A=\tilde{Q} \tilde{R}\) gives the required decomposition, so we have proved existence. For uniqueness, suppose \(A=Q_{1} R_{1}=Q_{2} R_{2}\) are two such decompositions. Then \(Q_{2}^{T} Q_{1}=\) \(R_{2} R_{1}^{-1},\) so that the left-hand side is orthogonal and the right-hand side is upper triangular. By parts (a) and (b), this implies both sides are equal to a diagonal matrix with ±1 as the only possible entries. But both \(R_{1}\) and \(R_{2}\) has positive diagonal, so \(R_{2} R_{1}^{-1}\) must have positive diagonal (you should verify that for upper triangular matrices, the diagonal of the inverse is the inverse of the diagonal, and the diagonal of the product is the product of the diagonals). Thus, both sides are equal to a diagonal matrices with +1 on the diagonal, i.e. the identity. So \(Q_{2}^{T} Q_{1}=I \Longrightarrow Q_{1}=Q_{2},\) and \(R_{2} R_{1}^{-1}=I \Longrightarrow R_{1}=R_{2} .\) This shows uniqueness.

证明 . (a) The least squares problem is $$ \min \|y-A \beta\| $$ where $$ A=\left[\begin{array}{cccc} t_{1}^{3} & t_{1}^{2} & t_{1} & 1 \\ \vdots & & & \vdots \\ t_{n}^{3} & t_{n}^{2} & t_{n} & 1 \end{array}\right] $$ \(n=11, t_{i}=1900+10(i-1) .\) We form the normal equations \(A^{T} A \beta=A^{T} y\) and solve for \(\beta\) to obtain beta \(=\) \(1.010415596011712 e-005\) \(-4.961885780449666 \mathrm{e}-002\) \(8.025770365215973 e+001\) $$ -4.259196447217581 e+004 $$ The plot is shown in Figure 4 . Here we have \(\|y-A \beta\|_{2}=10.1\). （b） Now we use the QR factorization to obtain beta2. \(\gg[Q, R]=\mathrm{qr}(\mathrm{A}) ;\) \(\gg \mathrm{b}=\) Q’*y; \(\gg\) beta \(2=R(1: 4,1: 4) \backslash b(1: 4)\) beta2 \(=\) $$ \begin{array}{r}1.010353535409117 \mathrm{e}-005 \\ -4.961522727598729 \mathrm{e}-002 \\ 8.025062525889830 \mathrm{e}+001 \\ -4.258736497384948 \mathrm{e}+004\end{array} $$ So \(\|\) beta \(2-\) beta \(\|_{2}=4.60 .\) The norm of the residual is essentially the same as in part (a), with a difference of \(1.08 \times 10^{-10}\). This shows the least-squares problem is very ill-conditioned, since a small change in the residual yields a relatively large change in the solution vector. However, Figure 5 shows that the two fits are hardly distinguishable on a graph (mostly because the residuals are both small). (c) We now perform a change of the independent variable $$ s=(t-1950) / 50 $$ so that \(s \in[-1,1] .\) We again set up the least square system and solve: \(\gg[Q, R]=q r(A)\) \(\gg b=Q^{\prime} * b ;\) \(\gg b=Q^{\prime} * y ;\) \(\gg\) beta \(3=R(1: 4,1: 4) \backslash b(1: 4) ;\) \(\gg\) betas beta3 \(=\) $$ \begin{array}{r}1.262941919191900 \mathrm{e}+000 \\ 2.372613636363639 \mathrm{e}+001 \\ 1.003659217171717 \mathrm{e}+002 \\ 1.559042727272727 \mathrm{e}+002\end{array} $$ Note that the coefficients are different because we are using a different basis. The residual is again essentially the same as parts (a) and (b) (the difference is \(1.54 \times 10^{-11}\) ). So even though the coefficients are quite different, the quality of the fit is essentially the same (even though (c) is more accurate by just a tiny bit).