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 4b## [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 4t(A)%*%A## [,1] [,2]
## [1,] 4 8
## [2,] 8 26t(A)%*%b## [,1]
## [1,] 36
## [2,] 112Hence, 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,] 4To 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,] 44Let 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 3In 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,] 0crossprod(A[,2], e)## [,1]
## [1,] 0Since dot products are 0, this would indicate the vectors e and p and e and the column vectors of A are orthogonal.
We are assuming that “auto-mpg.data” is in working directory.
d <- read.table("auto-mpg.data")
# read first 4 column into matrix and column 5 into vector
A <- as.matrix(d[, 1:4])
b <- as.vector(d[, 5])
# Compute A-transpose.A and A-transpose.b and stored in appropriate variables
a1 <- t(A)%*%A
a2 <- t(A)%*%b
# Find least square solution x_p
x_p <- solve(a1, a2)
# Using this solution we can calculate cal_mpg as A.x_p of each row of matrix A with x_p
mpg_cal <- A%*%x_p
me <- cbind(b, mpg_cal)
me_diff <- me[, 1] - me[, 2]
# Construct the difference of actual mpg with calculated mpg and store as 3 column
me <-cbind(me, me_diff)
me## b me_diff
## [1,] 18.0 13.383782 4.616218240
## [2,] 15.0 15.417359 -0.417359036
## [3,] 18.0 14.621173 3.378826784
## [4,] 16.0 17.057679 -1.057678955
## [5,] 17.0 12.451130 4.548869576
## [6,] 15.0 11.204010 3.795990039
## [7,] 14.0 11.831453 2.168546863
## [8,] 14.0 10.728896 3.271103548
## [9,] 14.0 14.142845 -0.142844892
## [10,] 15.0 11.175563 3.824436855
## [11,] 15.0 13.024029 1.975971155
## [12,] 14.0 8.463839 5.536161185
## [13,] 15.0 7.141269 7.858731092
## [14,] 14.0 22.468590 -8.468590101
## [15,] 24.0 26.742699 -2.742699116
## [16,] 22.0 22.321691 -0.321690829
## [17,] 18.0 22.972739 -4.972739352
## [18,] 21.0 23.218718 -2.218717778
## [19,] 27.0 26.629564 0.370436481
## [20,] 26.0 33.848906 -7.848905950
## [21,] 25.0 28.703825 -3.703824969
## [22,] 24.0 24.778051 -0.778050635
## [23,] 25.0 31.987689 -6.987689299
## [24,] 26.0 25.195243 0.804756613
## [25,] 21.0 21.657722 -0.657722327
## [26,] 10.0 22.233178 -12.233178241
## [27,] 10.0 24.951849 -14.951848663
## [28,] 11.0 23.159299 -12.159299460
## [29,] 9.0 28.719210 -19.719209715
## [30,] 27.0 26.629564 0.370436481
## [31,] 28.0 26.816288 1.183711807
## [32,] 25.0 25.640753 -0.640753298
## [33,] 19.0 18.330036 0.669964336
## [34,] 16.0 19.313786 -3.313786305
## [35,] 17.0 18.461227 -1.461226546
## [36,] 19.0 16.743721 2.256278832
## [37,] 18.0 19.256843 -1.256842633
## [38,] 14.0 13.207592 0.792408065
## [39,] 14.0 10.692631 3.307368745
## [40,] 14.0 14.630131 -0.630130773
## [41,] 14.0 14.512012 -0.512012410
## [42,] 12.0 8.935874 3.064125878
## [43,] 13.0 9.152270 3.847729670
## [44,] 13.0 7.488003 5.511997111
## [45,] 18.0 18.079401 -0.079401003
## [46,] 22.0 30.083454 -8.083454073
## [47,] 19.0 17.754807 1.245193435
## [48,] 18.0 15.759915 2.240084874
## [49,] 23.0 24.006114 -1.006113756
## [50,] 28.0 25.417939 2.582061235
## [51,] 30.0 34.676970 -4.676970301
## [52,] 30.0 25.418679 4.581320866
## [53,] 31.0 35.004618 -4.004617659
## [54,] 35.0 34.600583 0.399417231
## [55,] 27.0 33.058762 -6.058761986
## [56,] 26.0 37.053764 -11.053764064
## [57,] 24.0 28.325841 -4.325840586
## [58,] 25.0 30.375793 -5.375792992
## [59,] 23.0 38.492501 -15.492501357
## [60,] 20.0 33.910197 -13.910196876
## [61,] 21.0 28.962109 -7.962108847
## [62,] 13.0 12.803430 0.196570453
## [63,] 14.0 12.182504 1.817495518
## [64,] 15.0 15.268175 -0.268175454
## [65,] 14.0 13.786917 0.213082632
## [66,] 17.0 14.572944 2.427055537
## [67,] 11.0 12.956866 -1.956865955
## [68,] 13.0 12.810577 0.189423170
## [69,] 12.0 13.882178 -1.882177867
## [70,] 13.0 15.307839 -2.307838563
## [71,] 19.0 25.613731 -6.613731476
## [72,] 15.0 15.202331 -0.202331179
## [73,] 13.0 13.685001 -0.685001225
## [74,] 13.0 18.182285 -5.182284625
## [75,] 14.0 16.627473 -2.627473141
## [76,] 18.0 24.686469 -6.686469463
## [77,] 22.0 28.644875 -6.644874743
## [78,] 21.0 30.489197 -9.489197447
## [79,] 26.0 30.298172 -4.298171700
## [80,] 22.0 26.912626 -4.912626158
## [81,] 28.0 31.268903 -3.268903147
## [82,] 23.0 25.014808 -2.014808131
## [83,] 28.0 26.129853 1.870147438
## [84,] 27.0 30.810742 -3.810741917
## [85,] 13.0 17.453819 -4.453818975
## [86,] 14.0 14.572944 -0.572944463
## [87,] 13.0 13.436751 -0.436751318
## [88,] 14.0 16.281863 -2.281862629
## [89,] 15.0 15.496857 -0.496856579
## [90,] 12.0 10.400865 1.599135061
## [91,] 13.0 7.763400 5.236600385
## [92,] 13.0 13.117511 -0.117511192
## [93,] 14.0 16.631272 -2.631272353
## [94,] 13.0 13.092034 -0.092034372
## [95,] 12.0 12.869559 -0.869559439
## [96,] 13.0 14.893587 -1.893587012
## [97,] 18.0 23.288394 -5.288394024
## [98,] 16.0 23.771641 -7.771640963
## [99,] 18.0 22.388237 -4.388236947
## [100,] 18.0 20.488267 -2.488267220
## [101,] 23.0 22.878882 0.121118380
## [102,] 26.0 34.132510 -8.132509893
## [103,] 11.0 8.443910 2.556090063
## [104,] 12.0 8.684722 3.315277511
## [105,] 13.0 12.923154 0.076845960
## [106,] 12.0 14.759802 -2.759801641
## [107,] 18.0 21.360906 -3.360905725
## [108,] 20.0 34.691043 -14.691043265
## [109,] 21.0 31.125640 -10.125639731
## [110,] 22.0 29.688229 -7.688229375
## [111,] 18.0 25.794806 -7.794805561
## [112,] 19.0 32.277333 -13.277332909
## [113,] 21.0 24.747385 -3.747384683
## [114,] 26.0 28.071664 -2.071663713
## [115,] 15.0 12.852270 2.147729675
## [116,] 16.0 16.495878 -0.495878224
## [117,] 29.0 32.995060 -3.995060003
## [118,] 24.0 25.839559 -1.839559026
## [119,] 20.0 22.781122 -2.781122073
## [120,] 19.0 27.087953 -8.087952807
## [121,] 15.0 14.851235 0.148765116
## [122,] 24.0 25.071060 -1.071059649
## [123,] 20.0 23.992431 -3.992430765
## [124,] 11.0 16.955752 -5.955752434
## [125,] 20.0 22.646401 -2.646401283
## [126,] 19.0 22.661824 -3.661823795
## [127,] 15.0 21.413683 -6.413682799
## [128,] 31.0 33.977980 -2.977980249
## [129,] 26.0 26.620391 -0.620391085
## [130,] 32.0 38.607533 -6.607532947
## [131,] 25.0 25.726963 -0.726962907
## [132,] 16.0 18.646725 -2.646724907
## [133,] 16.0 22.901364 -6.901363757
## [134,] 18.0 20.229196 -2.229195635
## [135,] 16.0 15.138979 0.861021202
## [136,] 13.0 12.797396 0.202603570
## [137,] 14.0 13.266017 0.733982841
## [138,] 14.0 16.043333 -2.043332905
## [139,] 14.0 18.924767 -4.924766785
## [140,] 29.0 29.255197 -0.255197489
## [141,] 26.0 26.906524 -0.906524427
## [142,] 26.0 24.001367 1.998633422
## [143,] 31.0 28.589639 2.410360842
## [144,] 32.0 32.585587 -0.585586594
## [145,] 28.0 24.828415 3.171585401
## [146,] 24.0 26.931440 -2.931439564
## [147,] 26.0 22.296404 3.703596103
## [148,] 24.0 26.119173 -2.119172618
## [149,] 26.0 27.459178 -1.459178140
## [150,] 31.0 27.675123 3.324876763
## [151,] 19.0 19.829419 -0.829419444
## [152,] 18.0 19.437141 -1.437140670
## [153,] 15.0 24.406811 -9.406810690
## [154,] 15.0 23.114529 -8.114529173
## [155,] 16.0 8.638605 7.361395281
## [156,] 15.0 12.623589 2.376410799
## [157,] 16.0 15.008405 0.991595085
## [158,] 14.0 10.716957 3.283042751
## [159,] 17.0 27.994433 -10.994433155
## [160,] 16.0 21.707010 -5.707010346
## [161,] 15.0 24.289332 -9.289332187
## [162,] 18.0 22.581865 -4.581865317
## [163,] 21.0 21.407630 -0.407629784
## [164,] 20.0 16.348818 3.651182422
## [165,] 13.0 15.459847 -2.459846539
## [166,] 29.0 27.328108 1.671892149
## [167,] 23.0 26.380754 -3.380753743
## [168,] 20.0 22.580991 -2.580991317
## [169,] 23.0 28.883397 -5.883397249
## [170,] 24.0 21.221135 2.778864693
## [171,] 25.0 27.585241 -2.585241246
## [172,] 24.0 29.795651 -5.795651024
## [173,] 18.0 20.510725 -2.510725255
## [174,] 29.0 24.213138 4.786862316
## [175,] 19.0 21.160444 -2.160444202
## [176,] 23.0 24.680465 -1.680464944
## [177,] 23.0 25.789804 -2.789804167
## [178,] 22.0 22.412235 -0.412235282
## [179,] 25.0 24.789581 0.210419117
## [180,] 33.0 29.385696 3.614304178
## [181,] 28.0 25.935501 2.064499167
## [182,] 25.0 29.192994 -4.192993732
## [183,] 25.0 24.017019 0.982980946
## [184,] 26.0 30.799676 -4.799676112
## [185,] 27.0 26.874003 0.125997463
## [186,] 17.5 12.591421 4.908579307
## [187,] 16.0 13.927531 2.072468583
## [188,] 15.5 12.849858 2.650141828
## [189,] 14.5 12.695600 1.804400437
## [190,] 22.0 19.609360 2.390640336
## [191,] 22.0 17.100255 4.899745175
## [192,] 24.0 23.143368 0.856631667
## [193,] 22.5 23.142290 -0.642290022
## [194,] 29.0 37.303924 -8.303924359
## [195,] 24.5 37.168518 -12.668517651
## [196,] 29.0 24.612602 4.387398125
## [197,] 33.0 29.185964 3.814036274
## [198,] 20.0 21.604123 -1.604122808
## [199,] 18.0 24.466565 -6.466565426
## [200,] 18.5 19.465657 -0.965657065
## [201,] 17.5 22.874815 -5.374814890
## [202,] 29.5 21.261213 8.238787033
## [203,] 32.0 30.025742 1.974257553
## [204,] 28.0 28.226522 -0.226522360
## [205,] 26.5 18.321713 8.178286702
## [206,] 20.0 23.892476 -3.892475728
## [207,] 13.0 15.881466 -2.881466334
## [208,] 19.0 33.630479 -14.630479499
## [209,] 19.0 25.022653 -6.022653492
## [210,] 16.5 23.410456 -6.910455812
## [211,] 16.5 14.700801 1.799198675
## [212,] 13.0 11.022832 1.977167792
## [213,] 13.0 17.250189 -4.250189174
## [214,] 13.0 18.629631 -5.629631436
## [215,] 31.5 31.975016 -0.475015755
## [216,] 30.0 25.395856 4.604143880
## [217,] 36.0 32.542246 3.457753933
## [218,] 25.5 28.075821 -2.575821404
## [219,] 33.5 29.906083 3.593917013
## [220,] 17.5 14.461329 3.038670588
## [221,] 17.0 22.177355 -5.177354953
## [222,] 15.5 14.850972 0.649028193
## [223,] 15.0 14.407857 0.592143156
## [224,] 17.5 20.642357 -3.142356619
## [225,] 20.5 22.016858 -1.516858374
## [226,] 19.0 21.734698 -2.734698349
## [227,] 18.5 23.918913 -5.418913472
## [228,] 16.0 12.196445 3.803555275
## [229,] 15.5 13.068365 2.431635367
## [230,] 15.5 15.311777 0.188223081
## [231,] 16.0 14.873552 1.126447816
## [232,] 29.0 26.239804 2.760195577
## [233,] 24.5 24.210588 0.289412282
## [234,] 26.0 31.137733 -5.137732960
## [235,] 25.5 24.205388 1.294611712
## [236,] 30.5 28.156149 2.343851400
## [237,] 33.5 28.952180 4.547819946
## [238,] 30.0 28.026637 1.973363024
## [239,] 30.5 23.886405 6.613594685
## [240,] 22.0 22.312496 -0.312495921
## [241,] 21.5 23.047347 -1.547347477
## [242,] 21.5 24.930882 -3.430881662
## [243,] 43.1 35.438041 7.661958594
## [244,] 36.1 24.995150 11.104850220
## [245,] 32.8 32.232585 0.567414603
## [246,] 39.4 32.724025 6.675974657
## [247,] 36.1 28.257363 7.842636851
## [248,] 19.9 19.508160 0.391839773
## [249,] 19.4 15.584975 3.815024518
## [250,] 20.2 16.135489 4.064510894
## [251,] 19.2 25.926729 -6.726729452
## [252,] 20.5 25.652223 -5.152223237
## [253,] 20.2 20.468894 -0.268893849
## [254,] 25.1 23.466970 1.633029877
## [255,] 20.5 21.979614 -1.479614452
## [256,] 19.4 21.566126 -2.166126276
## [257,] 20.6 20.099610 0.500389946
## [258,] 20.8 21.613605 -0.813605003
## [259,] 18.6 25.365355 -6.765354980
## [260,] 18.1 20.060660 -1.960659838
## [261,] 19.2 18.688591 0.511409197
## [262,] 17.7 24.328818 -6.628818455
## [263,] 18.1 15.209303 2.890697163
## [264,] 17.5 14.438466 3.061533642
## [265,] 30.0 27.296407 2.703593276
## [266,] 27.5 23.345084 4.154916337
## [267,] 27.2 26.725194 0.474805862
## [268,] 30.9 23.724968 7.175032179
## [269,] 21.1 24.823281 -3.723280967
## [270,] 23.2 28.098400 -4.898399922
## [271,] 23.8 26.219898 -2.419897659
## [272,] 23.9 26.471781 -2.571780625
## [273,] 20.3 26.408740 -6.108740196
## [274,] 17.0 22.382689 -5.382689340
## [275,] 21.6 28.412670 -6.812669505
## [276,] 16.2 26.354893 -10.154892535
## [277,] 31.5 25.868332 5.631667627
## [278,] 29.5 27.620496 1.879503522
## [279,] 21.5 21.711253 -0.211252711
## [280,] 19.8 25.107017 -5.307017069
## [281,] 22.3 26.204840 -3.904839844
## [282,] 20.2 23.221464 -3.021463672
## [283,] 20.6 22.787631 -2.187630529
## [284,] 17.0 18.145540 -1.145540228
## [285,] 17.6 14.798953 2.801047019
## [286,] 16.5 12.911558 3.588442086
## [287,] 18.2 18.203340 -0.003340094
## [288,] 16.9 16.489766 0.410234460
## [289,] 15.5 15.121503 0.378496704
## [290,] 19.2 19.163678 0.036322444
## [291,] 18.5 14.220409 4.279591260
## [292,] 31.9 24.474906 7.425094098
## [293,] 34.1 25.708217 8.391783391
## [294,] 35.7 26.479713 9.220287168
## [295,] 27.4 22.292731 5.107268766
## [296,] 25.4 24.797990 0.602010413
## [297,] 23.0 19.629824 3.370176477
## [298,] 27.2 36.618378 -9.418377560
## [299,] 23.9 29.405913 -5.505913374
## [300,] 34.2 20.529409 13.670591357
## [301,] 34.5 24.235748 10.264251588
## [302,] 31.8 33.447734 -1.647733638
## [303,] 37.3 24.224057 13.075942671
## [304,] 28.4 24.960071 3.439929109
## [305,] 28.8 19.306061 9.493938904
## [306,] 26.8 21.848897 4.951103080
## [307,] 33.5 20.076411 13.423589133
## [308,] 41.5 25.026551 16.473448806
## [309,] 38.1 32.066405 6.033595009
## [310,] 32.1 25.830943 6.269056960
## [311,] 37.2 27.831415 9.368585092
## [312,] 28.0 25.908988 2.091011695
## [313,] 26.4 27.927054 -1.527054267
## [314,] 24.3 31.078532 -6.778531801
## [315,] 19.1 23.709115 -4.609115300
## [316,] 34.3 27.294287 7.005713295
## [317,] 29.8 24.217122 5.582877837
## [318,] 31.3 27.326382 3.973617851
## [319,] 37.0 25.705616 11.294384308
## [320,] 32.2 24.815353 7.384647226
## [321,] 46.6 30.261569 16.338431003
## [322,] 27.9 23.162578 4.737421835
## [323,] 40.8 32.888124 7.911875823
## [324,] 44.3 35.215717 9.084282693
## [325,] 43.4 37.655888 5.744111509
## [326,] 36.4 28.296093 8.103907199
## [327,] 30.0 29.474689 0.525310710
## [328,] 44.6 23.853244 20.746755687
## [329,] 33.8 30.227489 3.572510760
## [330,] 29.8 26.154813 3.645187387
## [331,] 32.7 20.368316 12.331683592
## [332,] 23.7 23.528148 0.171851887
## [333,] 35.0 24.776391 10.223609037
## [334,] 32.4 27.813774 4.586225695
## [335,] 27.2 25.018006 2.181993570
## [336,] 26.6 25.033931 1.566068934
## [337,] 25.8 22.239293 3.560706814
## [338,] 23.5 20.308675 3.191324863
## [339,] 30.0 20.078385 9.921614540
## [340,] 39.1 29.582052 9.517947754
## [341,] 39.0 28.569674 10.430325639
## [342,] 35.1 28.207262 6.892738439
## [343,] 32.3 30.325456 1.974544319
## [344,] 37.0 34.127003 2.872997440
## [345,] 37.7 28.874789 8.825211471
## [346,] 34.1 27.565052 6.534948092
## [347,] 34.7 22.731776 11.968223770
## [348,] 34.4 26.909831 7.490169497
## [349,] 29.9 33.814784 -3.914784029
## [350,] 33.0 23.217371 9.782628834
## [351,] 33.7 23.589518 10.110482492
## [352,] 32.4 27.482546 4.917453744
## [353,] 32.9 25.437640 7.462359827
## [354,] 31.6 28.188860 3.411139882
## [355,] 28.1 28.995491 -0.895491203
## [356,] 30.7 27.084272 3.615728250
## [357,] 25.4 20.313429 5.086570572
## [358,] 24.2 23.812975 0.387024534
## [359,] 22.4 20.667563 1.732437424
## [360,] 26.6 20.771353 5.828647134
## [361,] 20.2 22.946059 -2.746059269
## [362,] 17.6 18.206861 -0.606860706
## [363,] 28.0 33.411837 -5.411836939
## [364,] 27.0 31.196890 -4.196890082
## [365,] 34.0 31.521879 2.478121180
## [366,] 31.0 26.336135 4.663864877
## [367,] 29.0 25.399577 3.600423185
## [368,] 27.0 28.550550 -1.550550413
## [369,] 24.0 25.191161 -1.191160796
## [370,] 36.0 26.720180 9.279820373
## [371,] 37.0 31.710443 5.289557307
## [372,] 31.0 30.854034 0.145966320
## [373,] 38.0 22.891922 15.108078499
## [374,] 36.0 29.395031 6.604968655
## [375,] 36.0 25.752154 10.247845547
## [376,] 36.0 23.820339 12.179660982
## [377,] 34.0 27.549578 6.450422367
## [378,] 38.0 25.534973 12.465027074
## [379,] 32.0 26.933098 5.066902406
## [380,] 38.0 27.745222 10.254778415
## [381,] 25.0 26.290257 -1.290257023
## [382,] 38.0 20.692433 17.307567317
## [383,] 26.0 22.656651 3.343348817
## [384,] 22.0 22.361075 -0.361075041
## [385,] 32.0 21.949746 10.050254025
## [386,] 36.0 20.371386 15.628614201
## [387,] 27.0 25.815581 1.184419080
## [388,] 27.0 23.116951 3.883048859
## [389,] 44.0 41.146341 2.853659482
## [390,] 32.0 18.041478 13.958522321
## [391,] 28.0 29.635814 -1.635813657
## [392,] 31.0 31.144357 -0.144356538