AMLA hw2

Задача 1

Найти решение системы по методу наименьших квадратов

{3⁢x+4⁢y=12x=0y=0 3 cases Case 1: 3 x plus 4 y equals 12 Case 2: x equals 0 Case 3: y equals 0

Решение

Так как система не совместна(это следует из того что при x=y=0 x equals y equals 0 в первой строке возникает ложное утверждение 0 0 = equals 12 12), то можно лишь вычислить наилучшее по МНК псевдорешение.

Запишем систему в матричном виде(A⁢x→=b open paren A x right arrow equals b):

(341001)⁢X→=(1200) the 3 by 2 matrix Row 1: 3 4 Row 2: 1 0 Row 3: 0 1 times X right arrow equals the 3 by 1 column matrix 12 0 0

В таком виде решение по МНК выражается через псевдообратную матрицу к A A : x→=x^=A+⁢b x right arrow equals x hat equals A raised to the plus power b

rank⁡(A)=2 rank of A equals 2 но при этом число строк в матрице A A равно 3 3 ⇒ right double arrow матрица имеет полностолбцовый ранг и A+=(A∗⁢A)-1⋅A∗ A raised to the plus power equals open paren A raised to the asterisk power A close paren to the negative 1 power times A raised to the asterisk power

A∗⁢A=(310401)⁢(341001)=(10121217) A raised to the asterisk power A equals the 2 by 3 matrix Row 1: 3 1 0 Row 2: 4 0 1 times the 3 by 2 matrix Row 1: 3 4 Row 2: 1 0 Row 3: 0 1 equals the 2 by 2 matrix Row 1: 10 12 Row 2: 12 17

|10121217|=170-144=26 the determinant of the 2 by 2 matrix Row 1: 10 12 Row 2: 12 17 equals 170 minus 144 equals 26

(10121217)-1=126⁢(17-12-1210) the 2 by 2 matrix Row 1: 10 12 Row 2: 12 17 to the negative 1 power equals 1 over 26 times the 2 by 2 matrix Row 1: 17 negative 12 Row 2: negative 12 10

X→=126⁢(17-12-1210)⁢(310401)⁢(1200)=126⁢(17-12-1210)⁢(3648) X right arrow equals 1 over 26 times the 2 by 2 matrix Row 1: 17 negative 12 Row 2: negative 12 10 times the 2 by 3 matrix Row 1: 3 1 0 Row 2: 4 0 1 times the 3 by 1 column matrix 12 0 0 equals 1 over 26 times the 2 by 2 matrix Row 1: 17 negative 12 Row 2: negative 12 10 times the 2 by 1 column matrix 36 48

=126⁢(3648)≈(1.381.85) equals 1 over 26 times the 2 by 1 column matrix 36 48 almost equals the 2 by 1 column matrix 1.38 1.85


Задача 2

Среди всех решений системы найти вектор наименьшей возможной длины

{2⁢x+3⁢y+2⁢z=73⁢x+4⁢y-z=6 2 cases Case 1: 2 x plus 3 y plus 2 z equals 7 Case 2: 3 x plus 4 y minus z equals 6

Решение

Решение системы по методу наименьших квадратов дает вектор решения который имеет наименьшую норму невязки с b b . Таких векторов может быть много, как в этом случае(система имеет 2 2 уравнения но 3 3 переменных), поэтому что бы выбрать из всех решений вектор с минимальной евклидовой нормой, необходимо вычислить решение через псевдобратную матрицу: x→min=A+⁢b x right arrow sub min equals A raised to the plus power b

(23234-1)≡(23211-3)≡(11-3018)≡(105018) the 2 by 3 matrix Row 1: 2 3 2 Row 2: 3 4 negative 1 is identical to the 2 by 3 matrix Row 1: 2 3 2 Row 2: 1 1 negative 3 is identical to the 2 by 3 matrix Row 1: 1 1 negative 3 Row 2: 0 1 8 is identical to the 2 by 3 matrix Row 1: 1 0 5 Row 2: 0 1 8

Получаем что rank⁡(A)=2 rank of A equals 2, а значит матрица A A полного строчного ранга. Тогда псевдообратную матрицу можно вычислить по формуле: A+=A∗⋅(A⁢A∗)-1 A raised to the plus power equals A raised to the asterisk power times open paren A A raised to the asterisk power close paren to the negative 1 power

A⁢A∗=(23234-1)⁢(23342-1)=(17161626) A A raised to the asterisk power equals the 2 by 3 matrix Row 1: 2 3 2 Row 2: 3 4 negative 1 times the 3 by 2 matrix Row 1: 2 3 Row 2: 3 4 Row 3: 2 negative 1 equals the 2 by 2 matrix Row 1: 17 16 Row 2: 16 26

|17161626|=442-256=186 the determinant of the 2 by 2 matrix Row 1: 17 16 Row 2: 16 26 equals 442 minus 256 equals 186

x→min=1186⁢(23342-1)⁢(26-16-1617)⁢(76)=1186⁢(23342-1)⁢(86-10)= x right arrow sub min equals 1 over 186 times the 3 by 2 matrix Row 1: 2 3 Row 2: 3 4 Row 3: 2 negative 1 times the 2 by 2 matrix Row 1: 26 negative 16 Row 2: negative 16 17 times the 2 by 1 column matrix 7 6 equals 1 over 186 times the 3 by 2 matrix Row 1: 2 3 Row 2: 3 4 Row 3: 2 negative 1 times the 2 by 1 column matrix 86 negative 10 equals

1186⁢(142218162)≈(0.7631.1720.871) 1 over 186 times the 3 by 1 column matrix 142 218 162 almost equals the 3 by 1 column matrix 0.763 1.172 0.871


Задача 3

Для следующей системы найти псевдорешение наименьшей длины. Ответить на вопрос единственно ли оно?

{x-3⁢y+t=-12⁢y-3⁢z=-1x-2⁢y+z+t=0x-2⁢z+t=8 4 cases Case 1: x minus 3 y plus t equals negative 1 Case 2: 2 y minus 3 z equals negative 1 Case 3: x minus 2 y plus z plus t equals 0 Case 4: x minus 2 z plus t equals 8

Решение

Как и ранее что бы найти псевдорешение наименьшей длины, перепишем систему в матричном виде, а затем найдем псевдообратую к этой матрице:

A=(1-30102-301-21110-21),b=(-1-108) A equals the 4 by 4 matrix Row 1: Column 1, 1 Column 2, negative 3 Column 3, 0 Column 4, 1 Row 2: Column 1, 0 Column 2, 2 Column 3, negative 3 Column 4, 0 Row 3: Column 1, 1 Column 2, negative 2 Column 3, 1 Column 4, 1 Row 4: Column 1, 1 Column 2, 0 Column 3, negative 2 Column 4, 1 comma b equals the 4 by 1 column matrix Row 1: negative 1 Row 2: negative 1 Row 3: 0 Row 4: 8

x→min=A+⁢b x right arrow sub min equals A raised to the plus power b

rank⁡(A)≤3 rank of A is less than or equal to 3 , так (1) и (4) столбцы матрицы равны. Значит матрица A A не является полноранговой, в обоих смыслах, и для нее нужно применить общую формулу:

A+=FG+=G+⁢F+ A raised to the plus power equals FG raised to the plus power equals the plus power of G the plus power of F , где матрица F F имеет полностолбцовый ранг, а матрица G G полнострочный

Что бы их вычислить, найдем скелетное разложение матрицы A A :

(1-30102-301-21110-21)≡(0-32002-300-23010-21)≡(10-2102-3003-20)≡(10-2102-300110)≡ the 4 by 4 matrix Row 1: Column 1, 1 Column 2, negative 3 Column 3, 0 Column 4, 1 Row 2: Column 1, 0 Column 2, 2 Column 3, negative 3 Column 4, 0 Row 3: Column 1, 1 Column 2, negative 2 Column 3, 1 Column 4, 1 Row 4: Column 1, 1 Column 2, 0 Column 3, negative 2 Column 4, 1 is identical to the 4 by 4 matrix Row 1: Column 1, 0 Column 2, negative 3 Column 3, 2 Column 4, 0 Row 2: Column 1, 0 Column 2, 2 Column 3, negative 3 Column 4, 0 Row 3: Column 1, 0 Column 2, negative 2 Column 3, 3 Column 4, 0 Row 4: Column 1, 1 Column 2, 0 Column 3, negative 2 Column 4, 1 is identical to the 3 by 4 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, negative 2 Column 4, 1 Row 2: Column 1, 0 Column 2, 2 Column 3, negative 3 Column 4, 0 Row 3: Column 1, 0 Column 2, 3 Column 3, negative 2 Column 4, 0 is identical to the 3 by 4 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, negative 2 Column 4, 1 Row 2: Column 1, 0 Column 2, 2 Column 3, negative 3 Column 4, 0 Row 3: Column 1, 0 Column 2, 1 Column 3, 1 Column 4, 0 is identical to

≡(10-21011000-50)≡(100101000010)=G is identical to the 3 by 4 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, negative 2 Column 4, 1 Row 2: Column 1, 0 Column 2, 1 Column 3, 1 Column 4, 0 Row 3: Column 1, 0 Column 2, 0 Column 3, negative 5 Column 4, 0 is identical to the 3 by 4 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, 0 Column 4, 1 Row 2: Column 1, 0 Column 2, 1 Column 3, 0 Column 4, 0 Row 3: Column 1, 0 Column 2, 0 Column 3, 1 Column 4, 0 equals G

Для того что бы найти матрицу F F просто возьмем все столбцы из матрицы A A на которых стоят лидеры у матрицы G G :

F=(1-3002-31-2110-2) F equals the 4 by 3 matrix Row 1: Column 1, 1 Column 2, negative 3 Column 3, 0 Row 2: Column 1, 0 Column 2, 2 Column 3, negative 3 Row 3: Column 1, 1 Column 2, negative 2 Column 3, 1 Row 4: Column 1, 1 Column 2, 0 Column 3, negative 2

Теперь найдем G+=G∗⋅(G⁢G∗)-1 the plus power of G equals the asterisk power of G times open paren G the asterisk power of G close paren to the negative 1 power и F+=(F∗⁢F)-1⋅F the plus power of F equals open paren the asterisk power of F F close paren to the negative 1 power times F

G⁢G∗=(100101000010)⁢(100010001100)=(200010001) G the asterisk power of G equals the 3 by 4 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, 0 Column 4, 1 Row 2: Column 1, 0 Column 2, 1 Column 3, 0 Column 4, 0 Row 3: Column 1, 0 Column 2, 0 Column 3, 1 Column 4, 0 times the 4 by 3 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, 0 Row 2: Column 1, 0 Column 2, 1 Column 3, 0 Row 3: Column 1, 0 Column 2, 0 Column 3, 1 Row 4: Column 1, 1 Column 2, 0 Column 3, 0 equals the 3 by 3 matrix Row 1: 2 0 0 Row 2: 0 1 0 Row 3: 0 0 1

(G⁢G∗)-1=12⁢(100020002) open paren G the asterisk power of G close paren to the negative 1 power equals one half times the 3 by 3 matrix Row 1: 1 0 0 Row 2: 0 2 0 Row 3: 0 0 2

F∗⁢F the asterisk power of F F=(1011-32-200-31-2)⁢(1-3002-31-2110-2)=(3-5-1-517-8-1-814) the 3 by 4 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, 1 Column 4, 1 Row 2: Column 1, negative 3 Column 2, 2 Column 3, negative 2 Column 4, 0 Row 3: Column 1, 0 Column 2, negative 3 Column 3, 1 Column 4, negative 2 times the 4 by 3 matrix Row 1: Column 1, 1 Column 2, negative 3 Column 3, 0 Row 2: Column 1, 0 Column 2, 2 Column 3, negative 3 Row 3: Column 1, 1 Column 2, negative 2 Column 3, 1 Row 4: Column 1, 1 Column 2, 0 Column 3, negative 2 equals the 3 by 3 matrix Row 1: 3 negative 5 negative 1 Row 2: negative 5 17 negative 8 Row 3: negative 1 negative 8 14

det⁡(F∗⁢F)=|3-5-1-517-8-1-814|=75 the determinant of open paren the asterisk power of F F close paren equals the determinant of the 3 by 3 matrix Row 1: 3 negative 5 negative 1 Row 2: negative 5 17 negative 8 Row 3: negative 1 negative 8 14 equals 75

(F∗⁢F)-1=175⁢(1747857784129572926) open paren the asterisk power of F F close paren to the negative 1 power equals 1 over 75 times the 3 by 3 matrix Row 1: 174 78 57 Row 2: 78 41 29 Row 3: 57 29 26

x→min=1150⁢(100010001100)⁢(100020002)⁢(1747857784129572926)⁢(1011-32-200-31-2)⁢(-1-108)= x right arrow sub min equals 1 over 150 times the 4 by 3 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, 0 Row 2: Column 1, 0 Column 2, 1 Column 3, 0 Row 3: Column 1, 0 Column 2, 0 Column 3, 1 Row 4: Column 1, 1 Column 2, 0 Column 3, 0 times the 3 by 3 matrix Row 1: 1 0 0 Row 2: 0 2 0 Row 3: 0 0 2 times the 3 by 3 matrix Row 1: 174 78 57 Row 2: 78 41 29 Row 3: 57 29 26 times the 3 by 4 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, 1 Column 4, 1 Row 2: Column 1, negative 3 Column 2, 2 Column 3, negative 2 Column 4, 0 Row 3: Column 1, 0 Column 2, negative 3 Column 3, 1 Column 4, negative 2 times the 4 by 1 column matrix Row 1: negative 1 Row 2: negative 1 Row 3: 0 Row 4: 8 equals

=1150⁢(100010001100)⁢(174785715682581145852)⁢(71-13)=1150⁢(1747857156825811458521747857)⁢(71-13)= equals 1 over 150 times the 4 by 3 matrix Row 1: Column 1, 1 Column 2, 0 Column 3, 0 Row 2: Column 1, 0 Column 2, 1 Column 3, 0 Row 3: Column 1, 0 Column 2, 0 Column 3, 1 Row 4: Column 1, 1 Column 2, 0 Column 3, 0 times the 3 by 3 matrix Row 1: 174 78 57 Row 2: 156 82 58 Row 3: 114 58 52 times the 3 by 1 column matrix 7 1 negative 13 equals 1 over 150 times the 4 by 3 matrix Row 1: Column 1, 174 Column 2, 78 Column 3, 57 Row 2: Column 1, 156 Column 2, 82 Column 3, 58 Row 3: Column 1, 114 Column 2, 58 Column 3, 52 Row 4: Column 1, 174 Column 2, 78 Column 3, 57 times the 3 by 1 column matrix 7 1 negative 13 equals

=1150⁢(555420180555)=(3.72.81.23.7) equals 1 over 150 times the 4 by 1 column matrix Row 1: 555 Row 2: 420 Row 3: 180 Row 4: 555 equals the 4 by 1 column matrix Row 1: 3.7 Row 2: 2.8 Row 3: 1.2 Row 4: 3.7


Задача 4

Доказать, что система A⁢x=b A x equals b разрешима, тогда и только тогда, когда A⁢A+⁢b=b A A raised to the plus power b equals b

Доказательство

(⇒) open paren right double arrow close paren То, что система разрешима, означает что imA-1⁡(b) the inverse imaginary sub A of b , те в данном случае множество решений A⁢x=b A x equals b является непустым множеством. Мы уже знаем, что наименьший по длине вектор-решение можно получить вычислив: x^=A+⁢b x hat equals A raised to the plus power b и что x^∈imA-1⁡(b) x hat is a member of the inverse imaginary sub A of b .

Но тогда: A⁢A+⁢b=A⁢x^=b A A raised to the plus power b equals A x hat equals b

(⇐) open paren left double arrow close paren Нам дано что A⁢A+⁢b=b A A raised to the plus power b equals b . Ранее мы доказали, что im⁡(A⁢A+)=im⁡(A) the imaginary of open paren A A raised to the plus power close paren equals imaginary A верно. Тогда из A⁢A+⁢b=b A A raised to the plus power b equals b следует что b∈im⁡(A⁢A+)=im⁡(A) b is a member of the imaginary of open paren A A raised to the plus power close paren equals imaginary A , а значит найдется некоторый вектор x^ x hat , такой что A⁢x^=b A x hat equals b , следовательно система разрешима ∎ end of proof