AMLA hw2

Задача 1

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

{[3*x+4*y,=,12],[x,=,0],[y,=,0])

Решение

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

Запишем систему в матричном виде(A)*x=b):

([3,4],[1,0],[0,1])*X=([12],[0],[0])

В таком виде решение по МНК выражается через псевдообратную матрицу к A : x=x=(A^+)*b

rank(A)=2 но при этом число строк в матрице A равно 3 ⇒ матрица имеет полностолбцовый ранг и (A^+)=((A^∗)*A)(-1)⋅(A^∗)

(A^∗)*A=([3,1,0],[4,0,1])*([3,4],[1,0],[0,1])=([10,12],[12,17])

|[10,12],[12,17]|=170-144=26

([10,12],[12,17])(-1)=1/26*([17,-12],[-12,10])

X=1/26*([17,-12],[-12,10])*([3,1,0],[4,0,1])*([12],[0],[0])=1/26*([17,-12],[-12,10])*([36],[48])

=1/26*([36],[48])≈([1.38],[1.85])

Задача 2

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

{[2*x+3*y+2*z,=,7],[3*x+4*y-z,=,6])

Решение

Решение системы по методу наименьших квадратов дает вектор решения который имеет наименьшую норму невязки с b . Таких векторов может быть много, как в этом случае(система имеет 2 уравнения но 3 переменных), поэтому что бы выбрать из всех решений вектор с минимальной евклидовой нормой, необходимо вычислить решение через псевдобратную матрицу: (x_min)=(A^+)*b

([2,3,2],[3,4,-1])≡([2,3,2],[1,1,-3])≡([1,1,-3],[0,1,8])≡([1,0,5],[0,1,8])

Получаем что rank(A)=2, а значит матрица A полного строчного ранга. Тогда псевдообратную матрицу можно вычислить по формуле: (A^+)=(A^∗)⋅(A*(A^∗))(-1)

A*(A^∗)=([2,3,2],[3,4,-1])*([2,3],[3,4],[2,-1])=([17,16],[16,26])

|[17,16],[16,26]|=442-256=186

(x_min)=1/186*([2,3],[3,4],[2,-1])*([26,-16],[-16,17])*([7],[6])=1/186*([2,3],[3,4],[2,-1])*([86],[-10])=

1/186*([142],[218],[162])≈([0.763],[1.172],[0.871])

Задача 3

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

{[x-3*y+t,=,-1],[2*y-3*z,=,-1],[x-2*y+z+t,=,0],[x-2*z+t,=,8])

Решение

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

A=([1,-3,0,1],[0,2,-3,0],[1,-2,1,1],[1,0,-2,1]),b=([-1],[-1],[0],[8])

(x_min)=(A^+)*b

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

(A^+)=(FG^+)=(G^+)*(F^+) , где матрица F имеет полностолбцовый ранг, а матрица G полнострочный

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

([1,-3,0,1],[0,2,-3,0],[1,-2,1,1],[1,0,-2,1])≡([0,-3,2,0],[0,2,-3,0],[0,-2,3,0],[1,0,-2,1])≡([1,0,-2,1],[0,2,-3,0],[0,3,-2,0])≡([1,0,-2,1],[0,2,-3,0],[0,1,1,0])≡

≡([1,0,-2,1],[0,1,1,0],[0,0,-5,0])≡([1,0,0,1],[0,1,0,0],[0,0,1,0])=G

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

F=([1,-3,0],[0,2,-3],[1,-2,1],[1,0,-2])

Теперь найдем (G^+)=(G^∗)⋅(G*(G^∗))(-1) и (F^+)=((F^∗)*F)(-1)⋅F

G*(G^∗)=([1,0,0,1],[0,1,0,0],[0,0,1,0])*([1,0,0],[0,1,0],[0,0,1],[1,0,0])=([2,0,0],[0,1,0],[0,0,1])

(G*(G^∗))(-1)=1/2*([1,0,0],[0,2,0],[0,0,2])

(F^∗)*F=([1,0,1,1],[-3,2,-2,0],[0,-3,1,-2])*([1,-3,0],[0,2,-3],[1,-2,1],[1,0,-2])=([3,-5,-1],[-5,17,-8],[-1,-8,14])

det((F^∗)*F)=|[3,-5,-1],[-5,17,-8],[-1,-8,14]|=75

((F^∗)*F)(-1)=1/75*([174,78,57],[78,41,29],[57,29,26])

(x_min)=1/150*([1,0,0],[0,1,0],[0,0,1],[1,0,0])*([1,0,0],[0,2,0],[0,0,2])*([174,78,57],[78,41,29],[57,29,26])*([1,0,1,1],[-3,2,-2,0],[0,-3,1,-2])*([-1],[-1],[0],[8])=

=1/150*([1,0,0],[0,1,0],[0,0,1],[1,0,0])*([174,78,57],[156,82,58],[114,58,52])*([7],[1],[-13])=1/150*([174,78,57],[156,82,58],[114,58,52],[174,78,57])*([7],[1],[-13])=

=1/150*([555],[420],[180],[555])=([3.7],[2.8],[1.2],[3.7])

Задача 4

Доказать, что система A*x=b разрешима, тогда и только тогда, когда A*(A^+)*b=b

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

(⇒) То, что система разрешима, означает что (im^-1_A)(b) , те в данном случае множество решений A*x=b является непустым множеством. Мы уже знаем, что наименьший по длине вектор-решение можно получить вычислив: x=(A^+)*b и что x∈(im^-1_A)(b) .

Но тогда: A*(A^+)*b=A*x=b

(⇐) Нам дано что A*(A^+)*b=b . Ранее мы доказали, что im(A*(A^+))=im(A) верно. Тогда из A*(A^+)*b=b следует что b∈im(A*(A^+))=im(A) , а значит найдется некоторый вектор x , такой что A*x=b , следовательно система разрешима ∎