Найти лямбда в системе уравнений

Найдите общее решение линейной системы в зависимости от значения параметра . При каких значениях система допускает решение с помощью обратной матрицы?

тогда систему можно записать в виде .

Приравнивая к нулю, найдем, что при и .

Если и , то матрица имеет обратную

и решение имеет вид .

Если аккуратно перемножить и упростить, получим .

Случаи и рассматриваются отдельно. Нужно просто подставить и решить как обычную систему линейных уравнений с числовыми коэффициентами без параметров, например, методом гаусса.

Можно не использовать обратную матрицу, а применить метод редукции гаусса к расширенной матрице, учитывая, что и ,

При расширенная матрица

Следовательно решения имеют вид , или в матричном виде:

Теорема Кронекера-Капелли. Исследование систем линейных уравнений на совместность. Вторая часть.

В первой части мы рассматривали системы линейных алгебраических уравнений (СЛАУ), все коэффициенты которых были известны. В этой же части разберём СЛАУ, среди коэффициентов которых есть некий параметр. Для исследования СЛАУ на совместность станем использовать теорему Кронекера-Капелли. В процессе решения примеров на данной странице будем применять метод Гаусса или же метод Крамера. Сформулируем теорему и следствие из неё ещё раз:

Система линейных алгебраических уравнений совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы системы, т.е. $\rang A=\rang\widetilde$.

Следствие из теоремы Кронекера-Капелли

Параметр $n$, использованный выше, равен количеству переменных рассматриваемой СЛАУ.

Исследовать СЛАУ $ \left \ <\begin& kx_1+2x_2+x_3=8;\\ & -x_1+x_2+2x_3=7;\\ & x_2+kx_3=5.\end\right.$ на совместность и найти решение системы в зависимости от значений параметра $k$.

Чтобы исследовать заданную систему на совместность, нам нужно найти ранг матрицы системы $A$ и ранг расширенной матрицы системы $\widetilde$. Сделать это можно несколькими путями. Стоит учесть, что в данном примере нам требуется не только исследовать систему на совместность, но и указать её решения. Мне кажется наиболее удобным в таких задачах применять метод Гаусса, однако это вовсе не является обязательным. Для разнообразия данный пример решим методом Гаусса, а следующий – методом Крамера. Итак, запишем и начнём преобразовывать расширенную матрицу системы. При записи расширенной матрицы системы поменяем местами первую и вторую строки. Это нужно для того, чтобы первым элементом первой строки стало число -1.

$$ \left(\begin -1 & 1 &2 &7 \\ k & 2 & 1 & 8\\ 0 & 1 & k & 5 \end \right) \begin \phantom <0>\\ r_2+k\cdot\\ \phantom<0>\end\rightarrow \left(\begin -1 & 1 &2 &7 \\ 0 & 2+k & 1+2k & 8+7k\\ 0 & 1 & k & 5 \end \right)\rightarrow\left|\begin&\text<меняем местами>\\&\text<вторую и третью строки>\end\right|\rightarrow \\ \rightarrow \left(\begin -1 & 1 &2 &7 \\0 & 1 & k & 5 \\ 0 & 2+k & 1+2k & 8+7k \end \right) \begin \phantom<0>\\\phantom<0>\\r_3-(2+k)\cdot\end \rightarrow \left(\begin -1 & 1 &2 &7 \\0 & 1 & k & 5 \\ 0 & 0 & 1-k^2 & 2k-2 \end \right) $$

Мы привели расширенную матрицу системы к ступенчатому виду. Напомню, что до черты расположена преобразованная матрица матрица системы: $\left(\begin-1 & 1 &2\\0 & 1 & k\\ 0 & 0 & 1-k^2\end \right)$.

Каким бы ни было значение параметра $k$, полученная нами после преобразований матрица будет содержать не менее двух ненулевых строк (первая и вторая строки точно останутся ненулевыми). Вопрос о количестве решений зависит лишь от третьей строки.

В следствии из теоремы Кронекера-Капелли указаны три случая, и в данном примере легко рассмотреть каждый из них. Начнём с варианта $\rang A\neq\rang\widetilde$, при котором система не имеет решений, т.е. несовместна.

$\rang A\neq\rang\widetilde$

Ранги будут не равны друг другу лишь в одном случае: когда $1-k^2=0$, при этом $2k-2\neq<0>$. В этом случае преобразованная матрица системы будет содержать две ненулевых строки (т.е. $\rang A=2$), а преобразованная расширенная матрица системы будет содержать три ненулевых строки (т.е. $\rang \widetilde=3$). Иными словами, нам требуется решить систему уравнений:

Из первого уравнения имеем: $k=1$ или $k=-1$, однако $k\neq<1>$, поэтому остаётся лишь один случай: $k=-1$. Следовательно, при $k=-1$ система не имеет решений.

$\rang A=\rang\widetilde<3$

Рассмотрим второй пункт следствия из теоремы Кронекера-Капелли – ранги равны между собой, но меньше, чем количество переменных (т.е. меньше 3). Это возможно лишь в том случае, если последняя строка преобразованной расширенной матрицы системы полностью станет нулевой, т.е.

Из данной системы имеем: $k=1$. Именно при $k=1$ третья строка преобразованной расширенной матрицы системы станет нулевой, поэтому $\rang=\rang\widetilde=2$. При этом, повторюсь, у нас всего три переменных, т.е. имеем случай $\rang A=\rang\widetilde=2<3$.

Система имеет бесконечное количество решений. Найдём эти решения. Подставим $k=1$ в преобразованную матрицу и продолжим операции метода Гаусса. Третью строку (она станет нулевой) просто вычеркнем:

$$ \left(\begin -1 & 1 &2 &7 \\0 & 1 & k & 5 \\ 0 & 0 & 1-k^2 & 2k-2 \end \right)\rightarrow|k=1|\rightarrow \left(\begin -1 & 1 &2 &7 \\0 & 1 & 1 & 5 \end \right) \rightarrow\left|\begin&\text<переносим третий столбец>\\&\text<за черту>\end\right|\rightarrow \\ \rightarrow\left(\begin-1 & 1 &-2 &7\\0 & 1 & -1 & 5\end\right) \begin r_1-r_2\\\phantom<0>\end \rightarrow\left(\begin-1 & 0 &-1 &2\\0 & 1 & -1 & 5\end\right) \begin -1\cdot\\\phantom<0>\end \rightarrow\left(\begin1 & 0 &1 &-2\\0 & 1 & -1 & 5\end\right) $$

$\rang A=\rang\widetilde=3$

Рассмотрим третий пункт следствия из теоремы Кронекера-Капелли – ранги равны между собой и равны количеству переменных. Это возможно лишь в том случае, если $1-k^2\neq<0>$, т.е. $k\neq<-1>$ и $k\neq<1>$. Продолжаем решение методом Гаусса:

$$ \left(\begin -1 & 1 &2 &7 \\0 & 1 & k & 5 \\ 0 & 0 & 1-k^2 & 2k-2 \end\right)\rightarrow \left(\begin -1 & 1 &2 &7 \\0 & 1 & k & 5 \\ 0 & 0 & (1-k)(1+k) & -2(1-k) \end\right) \begin \phantom<0>\\\phantom<0>\\r_3:((1-k)(1+k))\end \rightarrow\\ \rightarrow\left(\begin -1 & 1 &2 &7 \\0 & 1 & k & 5 \\ 0 & 0 & 1 & -2/(1+k) \end\right) \begin r_1-2r_3\\r_2-k\cdot\\\phantom<0>\end \rightarrow \left(\begin -1 & 1 &0 &(7k+11)/(k+1) \\0 & 1 & 0 & (7k+5)/(k+1) \\ 0 & 0 & 1 & -2/(1+k) \end\right) \begin r_1-r_2\\\phantom<0>\\\phantom<0>\end\rightarrow\\ \rightarrow \left(\begin -1 & 0 &0 &6/(k+1)\\0 & 1 & 0 & (7k+5)/(k+1) \\ 0 & 0 & 1 & -2/(1+k) \end\right) \begin -1\cdot\\\phantom<0>\\\phantom<0>\end\rightarrow \left(\begin 1 & 0 &0 &-6/(k+1)\\0 & 1 & 0 & (7k+5)/(k+1) \\ 0 & 0 & 1 & -2/(1+k) \end\right) $$

Исследовать СЛАУ $\left\ <\begin& 2kx_1+x_2+x_3=0;\\ & x_1-x_2+kx_3=1;\\ & (k-6)x_1+2x_2-4x_3=-3.\end\right.$ на совместность и найти решение системы при тех значениях параметра, при которых она совместна.

Вновь, как и в предыдущем примере, для того, чтобы исследовать заданную систему на совместность, нам нужно найти ранг матрицы системы $A$ и ранг расширенной матрицы системы $\widetilde$. Чтобы исследовать систему на совместность и указать количество решений применим метод Крамера. Можно было бы решить и методом Гаусса, однако в предыдущем примере мы его уже использовали, поэтому для разнообразия решим задачу с помощью метода Крамера. Начнём с вычисления определителя матрицы системы. Этот определитель мы получим с помощью готовой формулы.

Значения переменных $x_1$, $x_2$, $x_3$ будут такими:

Нам остаётся исследовать совместность системы при условии $\Delta=0$. Это равенство возможно при $k=0$ или $k=1$.

Случай $k=0$

Нам остаётся рассмотреть последний случай: $k=1$.

Случай $k=1$

Для наглядности я запишу здесь матрицу системы $A$ и расширенную матрицу системы $\widetilde$, подставив $k=1$:

Если $k=1$, то $\Delta=0$. Это значит, что $\rang≤2$. Рассмотрим миноры второго порядка матрицы $A$. Например, возьмём минор, образованный на пересечении строк №1, №2 и столбцов №1, №2: $M=\left|\begin2 & 1\\ 1 & -1\end\right|=-3$. Так как $M\neq<0>$, то ранг матрицы $A$ равен 2.

Задача решена, осталось лишь записать ответ.

Разберём ещё один пример, в котором рассмотрим СЛАУ с четырьмя уравнениями.

Исследовать СЛАУ $ \left \ <\begin& kx_1+x_2+x_3+x_4=1;\\ & x_1+kx_2+x_3+x_4=1;\\ & x_1+x_2+kx_3+x_4=1;\\ & x_1+x_2+x_3+kx_4=1.\end\right.$ на совместность и найти решение системы в зависимости от значений параметра $k$.

Применим метод Гаусса. При записи расширенной матрицы системы поместим первую строку вниз, на место четвёртой строки. А дальше начнём стандартные операции метода Гаусса.

$$ \left(\begin 1 & k &1 &1&1 \\ 1 & 1 &k &1&1 \\ 1 & 1 &1 &k&1 \\ k & 1 &1 &1&1 \end \right) \begin \phantom<0>\\r_2-r_1\\r_3-r_1\\r_4-k\cdot\end\rightarrow \left(\begin 1 & k &1 &1&1\\ 0 & 1-k &k-1 &0&0\\ 0 & 1-k &0&k-1&0\\ 0 & 1-k^2 &1-k &1-k&1-k\end \right) $$

Здесь можно было бы остановиться и рассмотреть случаи $k=1$ и $k\neq<1>$ отдельно. Цель таких действий: разделить вторую, третью и четвёртую строки на $k-1$ при условии $k-1\neq<0>$. Однако пока что полученная нами матрица содержит не столь уж громоздкие элементы, поэтому сейчас отвлекаться на частности я не вижу смысла. Продолжим преобразования в общем виде:

$$ \left(\begin 1 & k &1 &1&1\\ 0 & 1-k &k-1 &0&0\\ 0 & 1-k &0&k-1&0\\ 0 & 1-k^2 &1-k &1-k&1-k\end \right) \begin \phantom<0>\\\phantom<0>\\r_3-r_2\\r_4-(k+1)r_2\end\rightarrow \\ \rightarrow \left(\begin 1 & k &1 &1&1\\ 0 & 1-k &k-1 &0&0\\ 0 & 0 &1-k&k-1&0\\ 0 & 0 &(1-k)(k+2) &1-k&1-k\end \right) \begin \phantom<0>\\\phantom<0>\\\phantom<0>\\r_4-(k+2)r_3\end\rightarrow \\ \rightarrow \left(\begin 1 & k &1 &1&1\\ 0 & 1-k &k-1 &0&0\\ 0 & 0 &1-k&k-1&0\\ 0 & 0 &0&(1-k)(k+3)&1-k\end \right) $$

Мы привели расширенную матрицу системы к ступенчатому виду. До черты расположена преобразованная матрица системы. Ранги матриц $A$ и $\widetilde$ зависят от значения параметра $k$. Рассмотрим три случая: $k=1$, $k=-3$ и случай $k\neq<1>$, $k\neq<-3>$.

Случай $k=-3$

Случай $k=1$

Если $k=1$, то преобразованная матрица станет такой: $\left(\begin 1 & 1 &1 &1&1\\ 0 & 0 &0 &0&0\\ 0 & 0 &0&0&0\\ 0 & 0 &0&0&0\end\right)$. Ранги матрицы системы и расширенной матрицы системы равны между собой (и равны 1), но меньше, чем количество переменных, т.е. $\rang=\rang<\widetilde>=1<4$. Вывод: система является неопределённой. Общее решение системы непосредственно получим из первой строки записанной матрицы:

$$x_1+x_2+x_3+x_4=1\; \Rightarrow \; x_1=-x_2-x_3-x_4+1.$$

Случай $k\neq<1>$ и $\neq<-3>$

Продолжим решение методом Гаусса. Так как $k\neq<1>$ и $\neq<-3>$, то $(1-k)(k+3)\neq<0>$. Следовательно, мы можем разделить вторую и третью строки на $1-k$, четвёртую строку – на выражение $(1-k)(k+3)$. С полученной после этого матрицей продолжим операции обратного хода метода Гаусса:

$$ \left(\begin 1 & k &1 &1&1\\ 0 & 1 &-1 &0&0\\ 0 & 0 &1&-1&0\\ 0 & 0 &0&1&\frac<1>\end \right) \begin r_1-r_4\\\phantom<0>\\\phantom<0>\\r_3+r_4\end\rightarrow \left(\begin 1 & k &1 &0&\frac\\ 0 & 1 &-1 &0&0\\ 0 & 0 &1&0&\frac<1>\\ 0 & 0 &0&1&\frac<1>\end\right) \begin r_1-r_3\\r_2+r_3\\\phantom<0>\\\phantom<0>\end\rightarrow\\ \rightarrow\left(\begin 1 & k &0 &0&\frac\\ 0 & 1 &0 &0&\frac<1>\\ 0 & 0 &1&0&\frac<1>\\ 0 & 0 &0&1&\frac<1>\end\right) \begin r_1-k\cdot\\\phantom<0>\\\phantom<0>\\\phantom<0>\end\rightarrow \left(\begin 1 & 0 &0 &0&\frac<1>\\ 0 & 1 &0 &0&\frac<1>\\ 0 & 0 &1&0&\frac<1>\\ 0 & 0 &0&1&\frac<1>\end\right) $$

Из последней матрицы имеем: $x_1=x_2=x_3=x_4=\frac<1>$.

• При $k=-3$ система несовместна.
• При $k=1$ система является неопределённой. Общее решение системы: $\left\<\begin& x_1=-x_2-x_3-x_4+1;\\&x_2\in,\;x_3\in,\;x_4\in. \end\right.$
• При $k\neq<-3>$ и $k\neq<1>$ система является определённой. Решение системы: $x_1=x_2=x_3=x_4=\frac<1>$.

λ-исчисление. Часть первая: история и теория

Идею, короткий план и ссылки на основные источники для этой статьи мне подал хабраюзер z6Dabrata, за что ему огромнейшее спасибо.

UPD: в текст внесены некоторые изменения с целью сделать его более понятным. Смысловая составляющая осталась прежней.

Вступление

Возможно, у этой системы найдутся приложения не только
в роли логического исчисления. (Алонзо Чёрч, 1932)

Вообще говоря, лямбда-исчисление не относится к предметам, которые «должен знать каждый уважающий себя программист». Это такая теоретическая штука, изучение которой необходимо, когда вы собираетесь заняться исследованием систем типов или хотите создать свой функциональный язык программирования. Тем не менее, если у вас есть желание разобраться в том, что лежит в основе Haskell, ML и им подобных, «сдвинуть точку сборки» на написание кода или просто расширить свой кругозор, то прошу под кат.

Начнём мы с традиционного (но краткого) экскурса в историю. В 30-х годах прошлого века перед математиками встала так называемая проблема разрешения (Entscheidungsproblem), сформулированная Давидом Гильбертом. Суть её в том, что вот есть у нас некий формальный язык, на котором можно написать какое-либо утверждение. Существует ли алгоритм, за конечное число шагов определяющий его истинность или ложность? Ответ был найден двумя великими учёными того времени Алонзо Чёрчем и Аланом Тьюрингом. Они показали (первый — с помощью изобретённого им λ-исчисления, а второй — теории машины Тьюринга), что для арифметики такого алгоритма не существует в принципе, т.е. Entscheidungsproblem в общем случае неразрешима.

Так лямбда-исчисление впервые громко заявило о себе, но ещё пару десятков лет продолжало быть достоянием математической логики. Пока в середине 60-х Питер Ландин не отметил, что сложный язык программирования проще изучать, сформулировав его ядро в виде небольшого базового исчисления, выражающего самые существенные механизмы языка и дополненного набором удобных производных форм, поведение которых можно выразить путем перевода на язык базового исчисления. В качестве такой основы Ландин использовал лямбда-исчисление Чёрча. И всё заверте…

λ-исчисление: основные понятия

Синтаксис

В основе лямбда-исчисления лежит понятие, известное ныне каждому программисту, — анонимная функция. В нём нет встроенных констант, элементарных операторов, чисел, арифметических операций, условных выражений, циклов и т. п. — только функции, только хардкор. Потому что лямбда-исчисление — это не язык программирования, а формальный аппарат, способный определить в своих терминах любую языковую конструкцию или алгоритм. В этом смысле оно созвучно машине Тьюринга, только соответствует функциональной парадигме, а не императивной.

Мы с вами рассмотрим его наиболее простую форму: чистое нетипизированное лямбда-исчисление, и вот что конкретно будет в нашем распоряжении.

Термы:

Соглашения о приоритете операций:

• Применение функции левоассоциативно. Т.е. s t u — это тоже самое, что (s t) u
  
• Аппликация (применение или вызов функции по отношению к заданному значению) забирает себе всё, до чего дотянется. Т.е. λx. λy. x y x означает то же самое, что λx. (λy. ((x y) x))
  
• Скобки явно указывают группировку действий.

Может показаться, будто нам нужны какие-то специальные механизмы для функций с несколькими аргументами, но на самом деле это не так. Действительно, в мире чистого лямбда-исчисления возвращаемое функцией значение тоже может быть функцией. Следовательно, мы можем применить первоначальную функцию только к одному её аргументу, «заморозив» прочие. В результате получим новую функцию от «хвоста» аргументов, к которой применим предыдущее рассуждение. Такая операция называется каррированием (в честь того самого Хаскелла Карри). Выглядеть это будет примерно так:

И напоследок несколько слов об области видимости. Переменная x называется связанной, если она находится в теле t λ-абстракции λx.t . Если же x не связана какой-либо вышележащей абстракцией, то её называют свободной. Например, вхождения x в x y и λy.x y свободны, а вхождения x в λx.x и λz.λx.λy.x(y z) связаны. В (λx.x)x первое вхождение x связано, а второе свободно. Если все переменные в терме связаны, то его называют замкнутым, или комбинатором. Мы с вами будем использовать следующий простейший комбинатор (функцию тождества): id = λx.x . Она не выполняет никаких действий, а просто возвращает без изменений свой аргумент.

Процесс вычисления

Рассмотрим следующий терм-применение:

Его левая часть — (λx.t) — это функция с одним аргументом x и телом t . Каждый шаг вычисления будет заключаться в замене всех вхождений переменной x внутри t на y . Терм-применение такого вида носит имя редекса (от reducible expression, redex — «сокращаемое выражение»), а операция переписывания редекса в соответствии с указанным правилом называется бета-редукцией.

Существует несколько стратегий выбора редекса для очередного шага вычисления. Рассматривать их мы будем на примере следующего терма:

который для простоты можно переписать как

(напомним, что id — это функция тождества вида λx.x )

В этом терме содержится три редекса:

1. Полная β-редукция. В этом случае каждый раз редекс внутри вычисляемого терма выбирается произвольным образом. Т.е. наш пример может быть вычислен от внутреннего редекса к внешнему:
   
2. Нормальный порядок вычислений. Первым всегда сокращается самый левый, самый внешний редекс.
   
3. Вызов по имени. Порядок вычислений в этой стратегии аналогичен предыдущей, но к нему добавляется запрет на проведение сокращений внутри абстракции. Т.е. в нашем примере мы останавливаемся на предпоследнем шаге:
   
   Оптимизированная версия такой стратегии (вызов по необходимости) используется Haskell. Это так называемые «ленивые» вычисления.
4. Вызов по значению. Здесь сокращение начинается с самого левого (внешнего) редекса, у которого в правой части стоит значение — замкнутый терм, который нельзя вычислить далее.
   
   Для чистого лямбда-исчисления таким термом будет λ-абстракция (функция), а в более богатых исчислениях это могут быть константы, строки, списки и т.п. Данная стратегия используется в большинстве языков программирования, когда сначала вычисляются все аргументы, а затем все вместе подставляются в функцию.

Если в терме больше нет редексов, то говорят, что он вычислен, или находится в нормальной форме. Не каждый терм имеет нормальную форму, например (λx.xx)(λx.xx) на каждом шаге вычисления будет порождать самоё себя (здесь первая скобка — анонимная функция, вторая — подставляемое в неё на место x значение).

Недостатком стратегии вызова по значению является то, что она может зациклиться и не найти существующее нормальное значение терма. Рассмотрим для примера выражение

(λx.λy. x) z ((λx.x x)(λx.x x))

Этот терм имеет нормальную форму z несмотря на то, что его второй аргумент такой формой не обладает. На её-то вычислении и зависнет стратегия вызова по значению, в то время как стратегия вызова по имени начнёт с самого внешнего терма и там определит, что второй аргумент не нужен в принципе. Вывод: если у редекса есть нормальная форма, то «ленивая» стратегия её обязательно найдёт.

Ещё одна тонкость связана с именованием переменных. Например, терм (λx.λy.x)y после подстановки вычислится в λy.y . Т.е. из-за совпадения имён переменных мы получим функцию тождества там, где её изначально не предполагалось. Действительно, назови мы локальную переменную не y , а z — первоначальный терм имел бы вид (λx.λz.x)y и после редукции выглядел бы как λz.y . Для исключения неоднозначностей такого рода надо чётко отслеживать, чтобы все свободные переменные из начального терма после подстановки оставались свободными. С этой целью используют α-конверсию — переименование переменной в абстракции с целью исключения конфликтов имён.

Так же бывает, что у нас есть абстракция λx.t x , причём x свободных вхождений в тело t не имеет. В этом случае данное выражение будет эквивалентно просто t . Такое преобразование называется η-конверсией.

На этом закончим вводную в лямбда-исчисление. В следующей статье мы займёмся тем, ради чего всё и затевалось: программированием на λ-исчислении.