Problem set# 1

Given the following Ax = b unsolvable system;
* Compute \({ A }^{ T }A\quad and\quad { A }^{ T }b\)
* Solve for \(\hat { x }\) in R using above two computed matrices
* What is the square error for this solution? * Instead of b = [0,8, 8, 20], start with p = 1, 5, 13, 17] and find the exact solution
* Show that error e = b - p = [1, 3, -5, 3] * Show that error e is orthogonal to p and to each of the column of A

\(Ax\quad =\quad b\quad \Leftrightarrow \quad \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 3 \\ 1 & 4 \end{bmatrix}\begin{bmatrix} { x }_{ 1 } \\ { x }_{ 2 } \end{bmatrix}\quad =\quad \begin{bmatrix} 0 \\ 8 \\ 8 \\ 20 \end{bmatrix}\)

# Define Matrix A and vector b
A <- matrix(c(1, 1, 1, 1, 0, 1, 3, 4), nrow = 4, ncol = 2, byrow = FALSE)
b <- c(0, 8, 8, 20)

A
##      [,1] [,2]
## [1,]    1    0
## [2,]    1    1
## [3,]    1    3
## [4,]    1    4
b
## [1]  0  8  8 20
# Define A transpose and A-transpose.A and A-transpose.b

t(A)
##      [,1] [,2] [,3] [,4]
## [1,]    1    1    1    1
## [2,]    0    1    3    4
t(A)%*%A
##      [,1] [,2]
## [1,]    4    8
## [2,]    8   26
t(A)%*%b
##      [,1]
## [1,]   36
## [2,]  112

Hence, we are looking for the solution to equation: \({ A }^{ T }A\hat { x } \quad =\quad { A }^{ T }b\)

x_p <- solve(t(A)%*%A, t(A)%*%b)
x_p
##      [,1]
## [1,]    1
## [2,]    4

To find the squarred error, let us consider \({ \left\| Ax\quad -\quad b \right\| }^{ 2 }\quad =\quad { \left\| Ax\quad -\quad p \right\| }^{ 2 }\quad +\quad { \left\| e \right\| }^{ 2 }\), when \(x\quad =\quad \hat { x }\), we have \({ \left\| Ax\quad -\quad b \right\| }^{ 2 }\quad =\quad { \left\| e \right\| }^{ 2 }\)

tp <- A%*%x_p - b
sqr_e <- crossprod(tp,tp)
sqr_e
##      [,1]
## [1,]   44

Let us now consider the vector p = [1, 5, 13, 17]. The original equation can be written as;
\(\begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 3 \\ 1 & 4 \end{bmatrix}\left[ \begin{matrix} x \\ y \end{matrix} \right] \quad =\quad \left[ \begin{matrix} 1 \\ 5 \\ 13 \\ 17 \end{matrix} \right]\)
We can easily write the correponding equations and clearly see that the system is solvable and that there are no extra constraints.

1x + 0y = 1
1x + y = 5
1x - 3y = 15
1x + 4y = 17

From this we can solve for x and y as follows:
x = y
y = 5 - 1*1 = 4
The other equations are duplicate.

p <- c(1, 5, 13, 17)
e <- b - p

e
## [1] -1  3 -5  3

In order to show that the vector e is orthogonal to p, let us compute the dot product for these vectors. If e.p = 0, they are orthognal.

#dot product between p and e
crossprod(p,e)
##      [,1]
## [1,]    0
#dot product between e and colums of A  

crossprod(A[,1], e)
##      [,1]
## [1,]    0
crossprod(A[,2], e)
##      [,1]
## [1,]    0

Since dot products are 0, this would indicate the vectors e and p and e and the column vectors of A are orthogonal.

Problem Set# 2