Популярные лекции

ПО МАТЕМАТИКЕ

Ю. А. ШРЕЙДЕР

ЧТО ТАКОЕ РАССТОЯНИЕ?

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

ВЫПУСК 38

Ю. А. ШРЕЙДЕР

ЧТО ТАКОЕ РАССТОЯНИЕ?

ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

МОСКВА 1963

513 Ш 86

Юлий Анатольевич Шрейдер Что такое расстояние? М., Физматгиз, 1963 г., 76 стр. с илл. Редактор А. П. Баева. Техн. редактор Л. Ю. Плакше. Корректор О. А. Сигал.

Сдано в набор 23.11 1963 г. Подписано к печати 19/1V 1963 г. Бумага 84Х1081/3,. Физ. печ. л. 2,34. Условн. печ. л. 3,89. Уч.-изд. л. 3,72. Тираж 67 000 экз. Т-04942. Цена книги 11 коп. Заказ № 178.

Государственное издательство физико-математической литературы. Москва, В-71, Ленинский проспект, 15.

Первая Образцовая типография имени А. А. Жданова Московского городского совнархоза. Москва, Ж-54, Валовая, 28.

Отпечатано с матриц в гос. типографии «Вайздас». Вильнюс, ул. Страздялио 1. Заказ № 1796

СОДЕРЖАНИЕ

Предисловие ........................ 4

§ 1. Как определяются математические понятия...... 7

§ 2. Расстояние в элементарной геометрии и его свойства . . 10

§ 3. Определение метрического пространства и расстояния . . 16

§ 4. Некоторые примеры метрических пространств ..... 23

§ 5. Пространство сообщений................ 33

§ 6. Автоматическое исправление ошибок в сообщениях . . 44

§ 7. Расстояния и нормы в многомерном пространстве ... 52

§ 8. Сглаживание ошибок экспериментальных измерений . . 65

§ 9. Более общие определения расстояния......... 69

ПРЕДИСЛОВИЕ

Эта книга является развитием лекции, прочитанной автором в Московском университете для школьников 9—10 классов. В ней рассказывается, как из простого геометрического понятия с помощью математической абстракции возникло общее определение расстояния. Приведены различные примеры пространств с расстоянием, так называемых метрических пространств. При этом оказывается, что общее понятие расстояния связано с разнообразными математическими фактами.

На основе понятия расстояния можно изучать задачи о кратчайших путях на поверхностях, геометрические свойства многомерных пространств, методы помехоустойчивого кодирования сообщений, методы «сглаживания» результатов измерений и др.

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

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

Материал, отобранный для книги, в основном диктуется этим общим замыслом.

Первые четыре параграфа как раз и должны раскрыть читателю, как происходит переход от обычного геометрического определения к общему понятию «расстояния» и что это новое «понятие» означает в различных конкретных случаях.

В пятом параграфе описывается так называемое пространство сообщений, играющее важную роль в теории информации и общей теории связи.

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

Седьмой параграф несколько более сложен для понимания. В нем описывается важный класс пространств с расстоянием.

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

В последнем параграфе рассматриваются возможные обобщения понятия расстояния. Здесь автору хотелось показать, что далеко не всякое обобщение является содержательным, т. е. обладающим интересными свойствами.

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

расстоянием. Так, например, хотя электроны в оболочке атомов нельзя представлять себе в виде материальных точек, все же в квантовой механике можно особым образом определить «расстояние» между различными состояниями электронов в атоме. Это «расстояние» по идее близко к одному из определений расстояния из § 7 (так называемое пространство /,).

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

Автор пользуется случаем выразить признательность И. М. Яглому, давшему ряд ценных советов по улучшению рукописи.

§ 1. КАК ОПРЕДЕЛЯЮТСЯ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ

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

Вместе с тем дело обстоит гораздо сложнее.

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

На плоскости и в обычном трехмерном (так называемом евклидовом) пространстве расстояние между двумя точками M и N определяется как длина отрезка MN, соединяющего эти точки. Однако когда мы имеем дело с расстояниями между географическими объектами, на поверхности земли, то мы обычно имеем в виду длину дуги большого круга, соединяющего эти объекты. Разница между этими двумя видами расстояний особенно наглядна, если вычислить расстояния между северным N и южным S полюсами (см. рис. 1). Обычное (евклидово) расстояние между полюсами равно диаметру земли, т. е. около 12 800 км. Расстояние между полюсами по поверхности земли больше первого в раз, т. е. равно примерно 20 100 км.

Рис. 1.

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

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

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

Вместе с тем любой путник исчисляет расстояние между пунктами своего маршрута по времени перехода.

Однако, несмотря на различие всех этих примеров, видно, что слово «расстояние» всюду употреблено в сходном смысле. Это слово везде означает меру удаленности каких-то объектов.

Итак, можно предположить, что есть некое общее определение расстояния, которое в разных конкретных ситуациях может иметь разное содержание. Такое общее определение будет сформулировано в § 3.

А сейчас мы обсудим, какие требования надо предъявлять к определению математического понятия.

Современная математика — это язык естествознания. В основе наиболее важных математических образов лежат какие-то пространственно-временные формы мира, в котором мы живем. Однако отношение между этими формами и математическими образами является очень сложным.

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

В геометрии такими основными понятиями являются: точка, прямая, плоскость, пространство и т. п. В систематических курсах геометрии можно найти перечень основных

свойств этих объектов, выраженных в виде так называемых аксиом и постулатов, на основе которых строится все здание геометрии*).

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

При этом в каждом из перечисленных пяти случаев проверяется выполнимость основных законов (свойств действий над числами). Это — переместительный (коммутативный) закон для сложения (а + b = b + а), сочетательный (ассоциативный) закон для сложения ((a + b) + c=a +(Ь + с)), переместительный (коммутативный) закон для умножения (ab = ba), сочетательный (ассоциативный) закон для умножения ((ab) с = а (be)), распределительный (дистрибутивный) закон (а + Ь) с =ас + be и правила: а—а=0; a-J-=l, характеризующие связь между основными (сложение и умножение) и обратными (вычитание, деление) операциями. Все эти законы выполняются во всех перечисленных числовых системах. Однако в некоторых из них деление выполнимо всегда, а в некоторых нет. Если числовая система состоит только из положительных чисел, то в ней не всегда возможно и вычитание. Оказывается, что правила алгебраических преобразований различных выражений основаны только на перечисленных выше свойствах. Все правила решения уравнений первой степени и систем таких уравнений также основаны на этих законах и возможности выполнения деления.

Оказывается, что свойства различных числовых систем можно изучать, исходя из общего понятия системы величин, над которыми определены операции (называемые сложением и умножением), удовлетворяющие перечисленным выше свойствам. Такие системы называются в современной алгебре кольцами или полями (в зависимости от того, можно ли всегда в этой системе выполнять деление)**).

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

*) Впервые так построил курс геометрии древнегреческий математик Евклид (IV—III век до н. э.).

**) Определение кольца и поля см. в книге: А. Г. Курош, Высшая алгебра, Москва, 1961, Физматгиз.

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

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

Эта черта математики не менее важна, чем возможность описания физического мира. Замечательный русский ученый Н. И. Лобачевский, изменив один из постулатов Евклида, создал так называемую «воображаемую» геометрию. Эта геометрия, спустя очень долгое время, легла в основу новых физических представлений о мире, возникших в результате открытия А. Эйнштейном теории относительности.

В этой книге мы рассматриваем одно из важных математических понятий — понятие «расстояния». Сначала мы проанализируем, какие основные законы, связанные с расстоянием, имеют место в элементарной геометрии. Положив в основу эти законы, мы получим определение так называемого «метрического пространства» и изучим различные примеры таких пространств. Мы увидим, что такой специфичный для математики подход к изучению различных объектов с точки зрения какого-то общего понятия открывает много интересных фактов.

Этот подход — создание новых общих понятий и попытка описать разнообразные объекты с помощью этих понятий — наиболее характерен для современной математики и ее приложений*). С этой точки зрения «расстояние» является удобным примером для того, чтобы убедиться в плодотворности такого подхода.

§ 2. РАССТОЯНИЕ В ЭЛЕМЕНТАРНОЙ ГЕОМЕТРИИ И ЕГО СВОЙСТВА

К общему определению расстояния мы придем, обобщая свойства обычного расстояния в трехмерном пространстве. Поэтому мы сначала сформулируем основные свойства обычного расстояния.

*) Нельзя не указать на роль, которую играют в кибернетике такие общие математические понятия, как информация, автомат, алгоритм.

Расстояние между двумя точками M и N в трехмерном пространстве—- длину отрезка MN — принято обозначать Q (M, N).

Это обозначение подчеркивает, что расстояние есть вещественное число, определяемое точками M и N. Иначе говоря, расстояние есть числовая функция от пары точек. Если каждую из точек характеризовать тройкой координат М(х% у, z) и N(x, у. z), то расстояние в пространстве есть функция шести переменных

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

Следовательно,

Отсюда

(1)

Еще проще вычисляется расстояние между точками M (х, у) и N(xx> yj на плоскости (см. рис. 3). Для этого надо заметить, что длина отрезка ML равна | х — jtj, а длина отрезка LN равна 1^—ух\. По теореме Пифагора

откуда

(2)

Рис. 2. Рис. 3.

Несмотря на важность соотношений (1) и (2), нужные нам свойства расстояния могут быть получены без использования координатной системы.

Эти свойства можно записать следующим образом:

1. Q(M, N) = Q(Nt M) (симметричность).

2. q(M, N) ^ 0 (неотрицательность).

3. q(M, yV) = 0 в том и только в том случае, когда точки M и N совпадают (невырожденность).

4. q(M> N)^q(M, L) + q(L, /V) — для любой тройки точек /И, L, N (аксиома треугольника).

Свойства 1, 2 и 3 очевидны. Они означают просто, что длина отрезка MN не зависит от порядка, в котором берутся точки M и Л/, всегда неотрицательна и равна нулю, только если начало и конец отрезка MN совпадают.

Свойство 4 становится очевидным, если через точки Ж, N и L провести плоскость и рассмотреть в этой плоскости треугольник MLN (см. рис. 4). Тогда свойство 4 означает просто, что длина стороны MN не превосходит суммы длин остальных сторон треугольника MLN, откуда и происходит название свойства 4. Это свойство означает, что прямолинейный отрезок MN является кратчайшим путем, соединяющим точки M и N.

В самом деле, неравенство треугольника буквально означает, что длина отрезка MN меньше длины двухзвенной ломаной MLN, если точка L не лежит внутри этого отрезка. Отсюда можно вывести, что длина отрезка MN меньше длины

Рис. 4. Рис. 5.

ломаной с любым числом звеньев, соединяющей точки M и N. Для этого (см. рис. 5) будем последовательно уменьшать число звеньев ломаной на единицу, спрямляя по два звена. Каждый раз при этом длина ломаной будет уменьшаться, пока мы не дойдем до отрезка MN. Так, на рис. 5 мы переходим от ломаной MLxLtLtN к ломаной MLxLtN, затем к ломаной MLtN, а затем к отрезку MN. Каждый раз длина ломаной уменьшается, а, значит, длина исходной ломаной больше длины отрезка MN.

Отметим, что в этом рассуждении мы пользовались только неравенством треугольника. Действительно, составим такую таблицу:

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

Если воспользоваться дополнительно тем фактом, что длина кривой есть предел длин вписанных в эту кривую ломаных, то можно доказать следующее утверждение.

Среди всех линий, соединяющих тон/си M и N, отрезок MN имеет наименьшую длину.

Из неравенства треугольника следует, что

(3)

Неравенство треугольника показывает, что если точка M близка к точке Z,, а точка L близка к точке N, то точки M и N тоже близки. Подчеркнем, что в свойстве 4 неравенство превращается в равенство в том и только том случае, когда

точки Ж, L и N лежат на одной прямой, а точка L находится между M и N (принадлежит отрезку MN).

Рассмотрим теперь расстояние на поверхности сферы S радиуса /?.

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

Большой круг лежит в плоскости, проходящей через точки Му N и О (центр сферы). Отсюда следует, что для несовпадающих точек M и N большой круг определяется единственным образом, поскольку для него заданы центр и две точки на окружности. Определенное таким образом расстояние qs (M, N)t очевидно, удовлетворяет свойствам 1, 2 и 3. Нетрудно также видеть, что для любых точек на сфере

(4)

причем равенство достигается только для точек M и N, лежащих на концах общего диаметра сферы (например, северный и южный полюсы).

Для того чтобы проверить свойство 4, надо рассмотреть сферический треугольник MLN (см. рис. 6). На этом рисунке точка О есть центр сферы.

Ясно, что

Известно, что в трехгранном угле каждый плоский угол не превосходит суммы двух других плоских углов, т. е.

(5)

Умножая обе части этого неравенства на радиус /?, получим

Рис. 6.

Это и означает, что

(6)

что и требовалось доказать.

Таким образом, для сферического расстояния QS(M, N) выполнены все основные свойства обычного расстояния.

Нетрудно проверить, что неравенство (6) обращается в равенство, только когда точка L расположена на том же большом круге, что и точки M п N. При этом точка L должна находиться между точками M и N, т. е. на меньшей дуге большого круга, соединяющей точки M и N.

Это следует из того, что неравенство (6) обращается в равенство только тогда, когда в равенство обращается (5). Последнее же может произойти, только когда трехгранный угол вырождается в плоский, т. е. когда точки ж, L и N лежат в одной плоскости с центром сферы О и луч OL находится между лучами ОМ и ON. Но это и значит, что точка L принадлежит меньшей дуге большого круга, соединяющего точки M и N.

Отсюда видно, что меньшая дуга большого круга, соединяющая точки M и Л/, обладает свойствами, аналогичными свойствам отрезка в обычной (не сферической) геометрии. А именно: 1) через любые не совпадающие точки проходит ровно одна такая дуга (исключением является случай, когда точки M и N лежат на концах некоторого диаметра сферы—являются антиподами; в этом случае обе дуги любого большого круга, соединяющего M и Л/, равноправны, а таких кругов бесконечно много); 2) две такие дуги могут пересекаться только в одной точке; 3) для любой точки Z,, лежащей на такой дуге, соединяющей точки M и Ny имеет место равенство q5 (ж, L)+qs(Li N)=qs(M, N).

Заметим теперь следующее важное обстоятельство. Для обычного расстояния мы показали, что длина ломаной, соединяющей две точки M и /V, больше, чем расстояние между точками M и N, т. е. чем длина отрезка MN. При этом рассуждение основывалось только на неравенстве треугольника и том факте, что оно обращается в равенство, лишь когда точки ж, L и N лежат на одном отрезке. Так как неравенство треугольника верно и для расстояния на сфере, а обычным отрезкам здесь соответствуют меньшие дуги больших кругов, то ясно, что аналогичное утверждение верно и на сфере. Именно, если точки M и N соединены цепочкой из дуг больших кругов (см. рис. 7), последовательно

соединенных друг с другом, то суммарная длина такой «сферической ломаной» больше*), чем расстояние QS(M, N).

Можно предложить читателю для упражнения восстановить полное доказательство этого утверждения по аналогии с приведенным выше доказательством для обычной ломаной. Это утверждение можно легко обобщить в следующей форме. Длина меньшей дуги большого круга, соединяющей точки M и N, меньше, чем длина любой другой линии на сфере, соединяющей эти точки.

Итак, мы рассмотрели два вида «расстояний» и убедились, что их основные свойства совпадают. Дополнительные свойства типа (4) играют гораздо меньшую роль.

Поэтому следующий наш шаг будет состоять в том, что мы основные свойства расстояния (1, 2, 3, 4) возьмем в качестве исходных и будем изучать различные «пространства», в которых определено «расстояние», обладающее этими исходными свойствами. В этом параграфе мы рассмотрели два простейших примера таких пространств: обычное пространство и поверхность сферы.

§ 3. ОПРЕДЕЛЕНИЕ МЕТРИЧЕСКОГО ПРОСТРАНСТВА И РАССТОЯНИЯ

Мы начнем с разъяснения того, что такое множество. Так же как «точка» в геометрии, понятие «множества» является первоначальным и определению не подлежит. Под словом «множество» в математике понимается совокупность каких-то объектов, называемых элементами множества.

Понятие «множества» состоит в сущности в том, что каким-то объектам приписывается свойство общности. Иначе, эти объекты по каким-то признакам попадают в некий класс, т. е. образуют множество. Задать множество — это и значит задать классификацию, т. е. для любого мыслимого объекта иметь возможность определить, попадает он в этот класс

Рис. 7.

*) Разумеется, если эта цепочка не лежит целиком на меньшей дуге большого круга, соединяющей точки M и N.

или нет. Принято говорить, что множество содержит каждый из своих элементов, а каждый из элементов данного множества в нем содержится. Множество считается заданным, если для любого объекта можно как-то проверить, содержится ли он в данном множестве*).

Можно рассматривать, например, множество всех целых чисел. Солнце не содержится в этом множестве, так как оно не есть число, а объект совсем другой природы. Число я также не содержится в этом множестве, ибо оно не целое. С другой стороны, корни уравнения хг — Зл: + 2 = 0 входят в это множество. Можно рассматривать множество всех планет солнечной системы, понимая под планетами тела, движущиеся вокруг Солнца по замкнутым орбитам и имеющие массу не меньше чем 1 тонна. Солнце не содержится в этом множестве, так как является звездой, а не планетой. Земля содержится в этом множестве. Советская ракета, запущенная с Земли 2 января 1959 года, содержится в этом множестве, так как является искусственной планетой.

Пусть Е—некоторое множество, а N—его элемент. Этот факт символически записывается как N £ Е. Читается: «/V является элементом Еу>. Применяется также символическая запись типа E{L, M, /V,...}, где в скобках перечислены все элементы этого множества. Так, множество Ес, состоящее из всех столиц союзных республик, можно было бы записать символически так: Ес {Москва, Киев, Минск, Тбилиси, Ереван, Баку, Рига, Таллин, Вильнюс, Ташкент, Алма-Ата, Фрунзе, Ашхабад, Дюшамбе, Кишинев}.

Если любой элемент множества Е является в то же время элементом множества Е1% то множество Е называется подмножеством множества Ev Это записывается так: EczEî («Е содержится в

Так, множество целых чисел является подмножеством множества вещественных чисел.

Множество Е называется конечным, если его элементы можно перенумеровать с помощью некоторого отрезка натурального ряда — множества Еп{\, 2, 3, ... , п). Например,

*) Вопрос о том, какой способ проверки считать эффективным, представляет большой интерес для математической логики или философии, но здесь нас интересовать не будет. Имеющиеся здесь трудности аналогичны трудностям любой формальной классификационной системы. Примером тому могут служить описанные в книге Веркора сЛюди или животные» трудности в определении, какие человекообразные принадлежат виду Homo sapiens.

множество столиц союзных республик Ес конечно, так как его можно перенумеровать элементами множества £ls, что видно из следующей таблицы соответствий:

Теперь мы можем дать определение метрического пространства.

Метрическим пространством называется такое множество £, что для любой пары его элементов M и N определено вещественное число Q(M, N), обладающее следующими свойствами:

(симметричность).

(неотрицательность).

3. Q(My /V)=0 в том и только в том случае, когда M и N один и тот же элемент (невырожденность).

4. q(M, N)^q(M, Z.)+Q(£, N) для любой тройки M, L, N элементов множества Е (аксиома треугольника).

Элементы множества Е принято называть точками соответствующего пространства. Метрическое пространство определяется, таким образом, выбором множества Е и функции Q(AÎ, N) — расстояния в пространстве. Для простоты будем обозначать получаемое пространство той же буквой, что и соответствующее множество, хотя на самом деле пространство и множество его элементов суть разные объекты. Действительно, в одном и том же множестве Е можно ввести различные расстояния и получить разные метрические пространства. В § 4 мы построим различные определения расстояния на плоскости.

Вместо указанных четырех свойств расстояния можно было бы ввести только два (предполагая заранее, что q (m, N) — вещественное число):

1'. q (M, iV) = 0 тогда и только тогда, когда точки M и .v совпадают.

2\ Q(Mt N)*ZQ(M9 L)+Q(Nt L).

Действительно, эти свойства вытекают из свойств 1, 2, 3 и 4» так как свойство Г совпадает со свойством 3, а свойство 2' вытекает из неравенства треугольника 4 и условия 1.

С другой стороны, из свойств Г и 2' можно вывести все условия 1, 2, 3 и 4.

Покажем это. Положим сначала в свойстве 2' £, = М, тогда получим:

В силу 1' q (M, М) = 0. Отсюда следует q (m, N)^q(N, m). Меняя в 2' местами точки m и n и проводя аналогичное рассуждение, убеждаемся, что q(N, M)<q(M, N). Из последних двух неравенств следует свойство симметрии (1):

Подставляя в 2' M вместо N и L, получаем

что доказывает условие неотрицательности расстояния (2). Наконец, используя доказанное условие симметрии, можно в 2' поменять во втором слагаемом правой части N и L и получить неравенство треугольника 4. Таким образом, система свойств Г и 2' равносильна системе свойств 1, 2, 3 и 4. Удобнее пользоваться более полной системой, которая в явном виде содержит больше фактических свойств расстояния. Однако интересно знать, что все эти свойства могут быть выведены всего из двух.

С точки зрения введенного определения содержание предыдущего параграфа можно было бы охарактеризовать как доказательство, что множество точек трехмерного пространства с расстоянием, определенным как длина отрезка или по формуле (1), является метрическим пространством. Аналогичный факт доказан в конце того же параграфа про множество точек сферы 5 с расстоянием QS(M, N).

Еще один пример метрического пространства получится, если взять множество точек некоторой поверхности П в трехмерном пространстве, а в качестве расстояния Qn (Ж, N) взять минимум длин путей, проходящих по поверхности П и соединяющих точки M и Л/*). Первые три свойства расстояния очевидны.

Аксиома треугольника проверяется так. Соединим точки M и L наикратчайшим путем, и точки L и N также соединим

*) Для простоты мы предполагаем, что такой наикратчайший путь существует для любых точек M и N на поверхности П. При некоторых предположениях о свойствах поверхности П это можно доказать.

наикратчайшим путем. Тогда путь, состоящий из двух наикратчайших линий ML и LNy соединяет точки M и N. Ясно, что длина этого пути не может быть меньше длины наикратчайшего пути из M в N. Так как длина этого пути есть Qn (M, L)+Qn(Ly N), a длина наикратчайшего пути из M в N есть оп (Ж, N), то отсюда следует искомое соотношение:

(7)

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

Полезно ввести понятие отрезка в произвольном метрическом пространстве. Именно, мы назовем отрезком, соединяющим точки M и N в метрическом пространстве Еу такое множество точек Ем N этого пространства, что для любой точки L множества Ем N выполнено равенство

(8)

Нетрудно видеть, что для обычного расстояния на плоскости или в трехмерном пространстве множество Ем N совпадает с отрезком MN в обычном смысле слова. На 'сфере S при расстоянии Q5(/V, M), введенном в § 2, отрезком Ем N является наименьшая дуга большого круга, соединяющая точки M w N (если они не лежат на одном диаметре) и весь большой круг, если точки M и N—антиподы на сфере.

Предоставляем читателю убедиться, что для расстояния Qn(M, N), введенного выше, отрезок EMN есть кратчайший путь (или так называемая геодезическая линия), соединяющий точки M и N.

В любом метрическом пространстве Е можно также ввести понятие сферы SM г с центром в точке M и радиусом г, обозначая этим термином множество таких точек N, для которых расстояние q(M, N)~r.

На плоскости это понятие соответствует окружности; в трехмерном пространстве—-обычной сфере; для расстояния QS(M> N) — окружностям на сфере S.

В качестве еще одного (тривиального) примера метрического пространства возьмем произвольное множество Е и определим расстояние между двумя любыми не совпадающими точками M и N равным единице, а между совпадающими точками — нулю. Легко видеть, что все необходимые условия при таком определении выполнены.

Разнообразные примеры метрических пространств будут рассмотрены в § 4.

В метрическом пространстве можно всегда определить операцию предельного перехода.

Последовательность точек метрического пространства Е: Lv Lt, ... , Lk называется сходящейся к точке если для всякого положительного вещественного числа е можно подобрать такой номер п(г), что из условия k>n(e) следует

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

Нетрудно убедиться, что для метрического пространства, состоящего из вещественных чисел х% с расстоянием, определяемым по правилу

это определение предела совпадает с обычным.

Для метрического пространства £3, состоящего из точек трехмерного пространства с обычным расстоянием, данное понятие предела позволяет хорошо определить, что такое предел последовательности точек в трехмерном пространстве.

Заметим, что в этом случае совокупность точек М, для которых Q (L, М)<г, образует сферу с центром в точке L и радиусом е. Последовательность геометрических точек L,, L2, ... , Lkl ... оказывается сходящейся к точке L, если, начиная с некоторого номера л (е), все члены этой последовательности с k>n (е) лежат в сфере с центром в L и радиусом е, причем такой номер п (г) должен существовать для всякого положительного е.

Теорема. Если последовательность элементов метрического пространства Е: Lv Lt, ... , Lk, ... сходится к пределу L, то для всякого положительного числа г существует такой номер m (е), что при k>m(e) и k'>m(e) выполняется условие Q(Lk, Lk)<z.

Доказательство. На основании определения предела

можно выбрать такой номер

будут справедливы неравенства

Но по аксиоме треугольника и свойству симметричности

Иными словами, если положить

то при k>m (е)

и k'>m (е) будет иметь место неравенство

что и доказывает теорему.

Эта теорема позволяет охарактеризовать внутренние свойства сходящихся последовательностей.

Если в пространстве Е справедливо утверждение, обратное этой теореме, то пространство Е называется полным метрическим пространством.

Определение полного метрического пространства удобно дать в следующей развернутой форме. Последовательность точек метрического пространства Е: Lv L2, ... , Lk, ... называется фундаментальной, если для всякого числа е>0 найдется номер m (е), такой, что при k>m (е) и к' (е) выполнено условие

Метрическое пространство Е называется полным, если в нем всякая фундаментальная последовательность имеет предел.

Прямая, плоскость и трехмерное пространство с обычным расстоянием являются полными метрическими пространствами.

Вопрос о полноте метрических пространств очень существен при использовании этих пространств в математическом анализе, но здесь мы его больше касаться не будем*).

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

Рассмотрим пример. Пусть пространство Е есть плоскость с обычным расстоянием, а пространство Ек есть множество

*) Для математического анализа принципиальное значение имеет полнота ряда метрических пространств, точками которых являются функции. См., например, определение пространства С в конце § 7.

Обычный способ изображения комплексных чисел точками плоскости осуществляет взаимно однозначное соответствие между этими пространствами. Нетрудно проверить, что это соответствие является изометричным, так как величина \z — zx I ="|/(jc — л:,)* + (у—Уг)* равна геометрическому расстоянию между соответствующими точками.

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

§ 4. НЕКОТОРЫЕ ПРИМЕРЫ МЕТРИЧЕСКИХ ПРОСТРАНСТВ

В этом параграфе мы рассмотрим ряд примеров метрических пространств с необычно определяемым расстоянием.

Ряд интересных примеров получается, если пространство есть множество точек обычной плоскости, а расстояние вводится различными способами. Точки плоскости мы будем при этом изображать с помощью раз и навсегда выбранной координатной системы, так что каждая точка плоскости задается двумя координатами х и у. Поэтому точку плоскости удобно обозначать как M (х, у).

Метрическое пространство / возникает, если расстояние между точками М(ху у) и N(x,y) определить по формуле

комплексных чисел z с расстоянием, определяемым по формуле

(9)

Из рис. 3 (стр. 11) можно усмотреть, что дДМ, N) равно сумме длин катетов треугольника MLN, в котором MN—гипотенуза, а катеты ML и LN параллельны осям координат.

Так как длина гипотенузы не превосходит суммы длин катетов, то всегда

(10)

где q(M, M) есть обычное геометрическое расстояние. Неравенство (10) превращается в равенство в том и только в том случае, когда отрезок MN или вертикален, или горизонтален, т. е. параллелен одной из осей координат.

Если в неравенство (10) подставить алгебраические выражения для соответствующих расстояний (9) и (2), то мы получим неравенство

При .^=^=0 отсюда следует простое, но красивое неравенство

(11)

Свойства 1, 2 и 3 для расстояния qx(M, N) очевидны. Докажем, что выполнено и свойство 4. Для этого рассмотрим три точки М(х, у), N(xvyl)i L(xz,yz) и запишем элементарное тождество

Если использовать тот факт, что для любых вещественных чисел а и b, |fl + é|<|fl| + |*|, то из (12) получается неравенство

что уже после перестановки членов в правой части равносильно искомому соотношению

(13)

Тем самым доказано неравенство треугольника для пространства /.

Расстояние еДМ, N) можно трактовать как минимальный путь, проходимый частицей, движущейся из M в Л/, если эта частица может двигаться только по отрезкам, параллельным осям координат.

Из рис. 8 видно, что существует много (бесконечно много!) наикратчайших путей для этой частицы.

Нетрудно показать, что это равносильно тому, что в пространстве / существует, вообще говоря, бесконечное множество различных «отрезков»*), соединяющих точки M и N (исключением является случай, когда точки M н N находятся на одной вертикали или горизонтали).

«Отрезком» в пространстве /, соединяющим точки M и N, является любая ломаная, соединяющая эти точки, состоящая из вертикальных и горизонтальных линий и пересекаемая любой вертикальной или горизонтальной линией не более чем по одному звену. (Это утверждение предоставляем проверить читателю.)

Еще более естественная картина получится, если рассмотреть метрическое пространство /, состоящее из всех точек, находящихся в узлах некоторой прямоугольной решетки на плоскости (рис. 9) с расстоянием, определенным формулой (9). Точки этого пространства можно рассматривать как перекрестки улиц бесконечного идеально распланированного города (тоже своего рода математическая абстракция!). Расстояние Q, (Ж, N) есть в этом случае минимальная длина пути, который необходимо пройти по улицам города, чтобы попасть из перекрестка M в перекресток N (не пользуясь, разумеется, проходными дворами).

Следующий пример метрического пространства — пространство С состоит из точек плоскости с расстоянием,

Рис. 8. Рис. 9.

*) В смысле введенного в § 3 определения.

определяемым по формуле

(14)

если точка M имеет координаты х и у, а точка N—координаты х1 и ух*). Геометрически это означает (см. рис. 3), что расстояние Qc^(M, N) равно максимальному катету треугольника MLN. Так как даже максимальный катет меньше гипотенузы (или равен ей в вырожденном треугольнике), то

(15)

где q(M, N)— обычное геометрическое расстояние.

Отсюда при ^=^,=0 получается алгебраическое неравенство

(16)

Для расстояния дЛ(Ж, N) также очевидны свойства 1, 2, 3. Аксиома треугольника проверяется следующим образом. Вы берем любые три точки М(х, у), N(xiyyx) и L(xt, уг). Пред положим, что \ X — хх I ^ \ у —ух I**). Это значит, что

Следовательно,

(17)

Очевидно также, что

(18)

Подставляя правые части неравенств (18) в неравенство (17), получаем

(19)

что и требовалось доказать.

На примере города, изображенного на рис. 9, расстоянию QoolM, N) можно придать следующий смысл. Предположим,

*) Смысл индекса оо будет раскрыт на стр. 29.

**) В противном случае доказательство видоизменяется очевидным образом.

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

Тогда путешественник может попасть на перекресток Ж, отстоящий от N на расстоянии Ссю(Ж, N)<^k.

Мы уже указывали, что в любом метрическом пространстве можно ввести понятие обобщенной сферы. (Слово «обобщенный» мы в дальнейшем будем опускать.) Аналогично этому обобщенным шаром с центром в точке Ж и радиусом г мы будем называть множество точек N, для которых

д(Ж, Л/)<г. (20)

Если g (Ж, N) — геометрическое расстояние на плоскости, то обобщенный шар является кругом с центром в точке M и радиусом г.

Для трехмерного пространства с обычным расстоянием шар, определяемый неравенством (20), есть обычный шар с центром в точке M и радиусом г. (Отсюда и происходит название «обобщенный шар».)

В пространстве / обобщенным шаром является квадрат с центром в точке Ж, с диагоналями, равными 2г и параллельными осям координат.

В пространстве С шаром является также квадрат с центром в точке Ж, но со сторонами, равными 2г и параллельными осям координат. На рис. 10 изображены обобщенные шары радиуса г в пространствах / и С и в смысле обычного расстояния. Доказательство того, что шары в / и С имеют указанный вид, предоставляется читателю.

Интересный класс метрических пространств получается, если определить расстояние Qp(M, N) по формуле

(21)

и получить тем самым пространство 1р.

Рис. 10.

Свойства 1,2, 3 для этого расстояния очевидны. Аксиома треугольника следует из неравенства Минковского*)

(22)

справедливого при

Читатель легко получит из (22) доказательство аксиомы треугольника для расстояния (21) при если для точек М(х, у), N(xvyt) и L(xtyyt) обозначит и будет действовать по аналогии с доказательством аксиомы треугольника для пространства /. При р<\ аксиома треугольника неверна, так как знак неравенства (22) меняется на противоположный.

Нетрудно видеть, что при р = 1 расстояние Qp(M, N)=* = Qt(My N)y а при p=2 расстояние Qp(M, N) совпадает с обычным геометрическим расстоянием Q(M, N).

Таким образом, рассмотренное ранее пространство / совпадает с пространством lv а плоскость с обычным расстоянием есть пространство /8.

Покажем, что при р—► оо расстояние Qp (Ж, N) стремится к расстоянию Qoo (УИ, N).

В самом деле, рассмотрим сначала случай |х — ХХ\>\У —ух |-Тогда (My N) = \x — xx\. С другой стороны, преобразуя (21), имеем

(23)

Замечая, что при р>1

и что величина —»-0 при р—юо, получаем

*) Доказательство этого неравенства можно найти в книге: Г. Харди, Дж. Литлвуд и Полиа, Неравенства, перев. с англ., ИЛ, Москва, 1948.

Учитывая этот факт и используя (23), видим, что

(24)

Аналогично, при | jkt — |<d| >f — -V» I можно получить

(25)

Наконец, рассмотрим случай | л; — *J = 1^ — ух |. Тогда

Так как

то и в этом случае

(26)

Сопоставляя (24), (25) и (26), получаем, что во всех случаях

(27)

что и требовалось доказать.

Таким образом, пространство С можно было бы обозначить символом /с*,, так как расстояние в этом пространстве получается предельным переходом из расстояния в пространстве 1р при р—► оо.

На рис. 11 показаны шары в пространствах 1р с центром в точке M при различных значениях р.

Метрические пространства 1р носят общее название пространств Минковского. В § 7 мы рассмотрим многомерные пространства Минковского.

В качестве упражнения для читателя предлагается найти вид «отрезков» в пространствах 1р.

Следующий класс метрических пространств на плоскости получится, если расстоянием называть минимальное время,

Рис. 11.

требующееся для прохождения при некоторых заданных условиях пути из Ж в N.

При этом обычное расстояние получается, если путь от M к N проходится точкой, движущейся с постоянной скоростью, равной единице.

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

Новый пример получится, если рассмотреть (см. рис 12) схему московского метрополитена и считать, что путешественник проходит из точки M в N следующим образом.

Если существует одна и та же ближайшая от обеих точек станция метро, то путешественник идет пешком но наикратчайшему пути. Если такой станции нет, то путешественник идет пешком (кратчайшим путем) до станции, ближайшей к исходной точке Ж, едет скорейшим путем к станции, ближайшей к точке Л/, и оттуда идет пешком к N. Если для точек Ж или N есть несколько ближайших станций метро, то выбирается вариант маршрута с наименьшим временем пути. На рис. 12 есть точка Ж, из которой надо двигаться в точку N пешим способом, и точка Жр из которой надо

Рис. 12.

двигаться в точку Ых с помощью метро. Скажем, если человеку, живущему посредине между станциями «Рижская» и «Ботаническая», нужно добраться в район Земляного вала, то ему надо сесть на «Ботанической» и доехать до «Лермонтовской» или «Курской». Нетрудно видеть, что определенное таким образом расстояние Qt (M, N) существенно отличается от обычного геометрического расстояния. В самом деле, если точка Q расположена около вертолетной станции, т. е. между станциями «Динамо» и «Аэропорт», точка Р в районе Волоколамского шоссе, а точка R в районе Валовой улицы (возле станции метро Павелецкая) (см. рис. 12), то в смысле обычного расстояния точка Р гораздо ближе к Q, чем точка /?,

Однако из карты на рис. 12 очевидно, что

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

Для расстояния Qt (M, M) нетривиальной является аксиома симметричности (свойство 1).

Равенство

означает, что время, затрачиваемое в обе стороны кратчайшего пути AIN, одинаково. Это более или менее справедливо, если пользоваться метро и пешим способом сообщения. Но уже при пользовании такси это не так, ибо одно дело ждать такси недалеко от таксомоторного парка, а совсем другое — получить такси в каком-либо отдаленном районе, или у Курского вокзала в часы прихода поездов.

Свойства 2 и 3 для расстояния Qt(M, N) очевидны. Доказательство свойства 4 (аксиомы треугольника) читатель легко проведет самостоятельно, если вспомнит, как это свойство доказывалось в § 3 для расстояния Qn(Af, N).

Для исследования свойств метрических пространств полезно ввести следующее понятие.

Пусть Е—некоторое метрическое пространство, a Lx% ^i» •••• Lk — точки этого пространства.

Назовем областью Дирихле точки Ll множество Dh состоящее из точек Л/, для которых

(28)

для всех Таким образом, область Дирихле D{ состоит из точек пространства, расположенных ближе к точке L0 чем к остальным выбранным точкам. Ясно, что определение области Дирихле зависит от набора точек Lv L2> Lk и выбранной точки Lr Рассмотрим примеры областей Дирихле в различных метрических пространствах.

Для начала возьмем плоскость с обычным расстоянием Qi (M, N) и две точки Lx и L2. Соединим эти точки отрезком Lx, Lt (рис. 13) и проведем через середину этого отрезка перпендикуляр.

Этот перпендикуляр разбивает плоскость на две полуплоскости, которые и будут областями Дирихле для точек

Возьмем теперь три точки Lv L2 и La на плоскости с обычным расстоянием. На рис. 14 построены и отмечены штриховкой области Дирихле для этих трех точек. Способ построения ясен из рисунка.

Рассмотрим теперь две точки Lx и Lt на плоскости с расстоянием qx (Ж, N) (т. е. в пространстве /). Для наглядности мы опять рассматриваем город, разделенный на кварталы. Области Дирихле состоят из тех перекрестков, от которых путь по городу будет короче, чем до точки Lx (со-

Рис. 13. Рис. 14.

ответственно L2). Эти области отделены на рис. 15 жирной чертой. На рис. 16 приведено аналогичное разбиение для пространства С. Предоставляем читателю вывести общее правило построения областей Дирихле в пространствах / и С, для пар точек Lx и L2, а затем для троек Lx, L2, Lz.

Обращаясь снова к рис. 12, мы видим, что если построить разбиение пространства на области Дирихле для пары точек Р и /?, то точка Q попадает в области Дирихле точки R.

Предоставляем опять же читателю нарисовать это разбиение на области Дирихле. Важно, что это разбиение сильно отличается от разбиения на области Дирихле, показанного на рис. 13, 15 и 16.

§ 5. ПРОСТРАНСТВО СООБЩЕНИЙ

Под словом «сообщение» обычно понимается какая-то конкретная форма передачи информации. Сообщениями в широком смысле слова являются книги, письма, телеграммы, записи музыкальных произведений на пленку или с помощью нот, записи на перфокартах, с помощью которых информация о решаемой задаче вводится в математические машины, сигналы, управляющие взлетом и посадкой космических кораблей, молекулы дезоксирибонуклеиновой кислоты (ДНК), передающие наследственную информацию от родителей к потомству, и т. п.

Рис. 15. Рис. 16.

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

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

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

Например, при плохой слышимости по телефону мы вынуждены повторять отдельные слова. При передаче незнакомого и трудного для восприятия названия или фамилии используется побуквенная система. Так, сообщая по телефону собственное имя «Павсикакий», мы будем произносить следующее: «Петр, Андрей, Василий, Семен, Илья, Константин, Анна, Кирилл, Инна, Иван краткий».

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

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

*) Основные сведения из этой теории в достаточно элементарном изложении можно найти в книге: А. М. Яглом и И. М. Яглом, Вероятность и информация, Физматгиз, 1960.

месте написал слово «телеграф». В самом деле, в этом случае мы имели бы дело с восемью опечатками подряд, в то время как из слова «кастрюля» тот же результат получается вследствие одной опечатки*).

Правда, существуют курьезные примеры, когда из-за ошибки в одной букве могут возникнуть различные слова. Скажем, слово «корона» может произойти и из «корова», и из «ворона».

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

Легко видеть, что и в этом случае истинный смысл сообщения довольно легко установить по контексту.

Аналогично ошибка в нотной записи часто может быть обнаружена по фальшивому звучанию и исправлена по законам гармонии.

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

Проблема восстановления правильного сообщения имеет одинаковый вид и при передаче и при хранении информации.

Каждый вид сообщения записывается с помощью каких-то символов. Множество используемых символов образует алфавит 9Ï. Мы предположим, что этот алфавит задан заранее и состоит из конечного множества символов. Например, алфавит может состоять из всех русских букв, символа пропуска буквы и знаков препинания. В этом алфавите можно писать любые русские фразы. Другой пример алфавита — множество десятичных цифр, алгебраических знаков, знаков препинания и латинских и греческих букв. С помощью такого алфавита можно записывать разнообразнейшие математические формулы.

Еще один пример—это двоичный алфавит — множество из двух символов 31, {0, 1}. С помощью такого алфавита можно записывать числа в двоичной системе счисления.

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

Действительно, можно легко показать, что всякое целое число X записывается в виде

(29)

где величины е,- принимают значения 0 или 1.

Таким образом, для того чтобы передать информацию о значении числа х, достаточно передать последовательность знаков алфавита 312: гп гп_1 ... гх е0. На самом деле, чтобы разделять сообщения о разных числах, надо либо ввести специальный знак для конца числа, либо передавать только последовательности двоичных знаков стандартной длины*).

Последний способ фактически применяется в вычислительных машинах, где запоминаемые двоичные последовательности обычно имеют стандартную величину, соответствующую величине так называемых ячеек памяти. В разрабатываемых в последние годы машинах от этого принципа постепенно отказываются, переходя к ячейкам переменной длины. Формула (29) аналогична хорошо известной формуле:

(30)

где ап% а„_1, а1Э а0—цифры в десятичном представлении числа X. Легко распространить равенство (29) на не целые числа, подобно тому как вводятся десятичные дроби.

Установим связь между числом п и значением х в (29). Ясно, что если несколько первых слагаемых в правой части (29) равны нулю, то их можно отбросить. Поэтому мы будем предполагать, что ел = 1. Перенося все члены, кроме первого, из правой части в левую, мы получим

Отсюда ясно, что или

(31)

С другой стороны, верна следующая оценка:

*) Есть и другие более сложные приемы разделения смысловых единиц (слов) в произвольном алфавите. См. статью А. А. Сардинаса и Дж. Паттерсона в «Кибернетическом сборнике», № 3, ИЛ, Москва, 1961.

Из последнего соотношения и из (29) следует

или

что можно записать и так:

(32)

Сопоставляя (31) и (32), получаем двойное неравенство

(33)

Неравенство (33) означает в других терминах, что

т. е. п равно целой части*) \og2x (читается: *п равно антье от log2*»). Вышеизложенное можно записать еще так: количество двоичных знаков, необходимых для кодирования всех целых чисел в диапазоне 0<:*^:а, равно

(34)

Единица здесь добавляется потому, что двоичные знаки включают еще и нулевой: е0.

С помощью двоичного алфавита 2(, в памяти вычислительных машин записывается любая информация (числа, команды, логические соотношения и др.)**).

Сообщением в данном алфавите SÏ мы будем называть конечную упорядоченную последовательность символов этого алфавита. Иногда удобно делить сообщения на некоторые стандартные сообщения, которые называются словами.

Вообще говоря, возможны также бесконечные алфавиты и сообщения, но мы их здесь рассматривать не будем.

Сообщение, записанное в одном алфавите, можно различными способами записать в другом алфавите.

Так, мы уже видели, что целое число, заданное десятичными цифрами, можно записать и в двоичном алфавите. Один из важных способов такой перекодировки состоит в следующем. Пусть дан алфавит 2Ï. Возьмем все слова, составленные в этом алфавите, длиной не более k и будем

*) Целой частью числа а называется наибольшее из целых чисел, меньших а. Целая часть а обозначается [а]; например,

**) См. по этому вопросу: Б. А. Трахтенброт, Алгоритмы и машинное решение задач, изд. 2, Физматгиз, Москва, 1960).

считать это множество слов новым алфавитом 21'. Ясно, что всякое сообщение в алфавите 31 можно разбить на последовательность слов длины не более а значит, закодировать в новом алфавите 81'.

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

Вместо иероглифов можно было бы использовать шестизначные десятичные числа. Первых пяти знаков такого числа достаточно для кодирования слов*); шестой знак можно использовать для кодирования грамматических признаков.

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

Рассмотренный способ «пословного» кодирования практически используется при шифровке сообщений наряду с «побуквенной» шифровкой.

Возможна и обратная картина, когда символы исходного алфавита 31 кодируются в виде слов, записанных в более простом алфавите ЗГ. Например, пусть алфавит ЗГ состоит из трех символов {•, — ,*}; читается так: точка, тире, конец буквы. Тогда любая русская (или латинская) буква и знак препинания могут быть записаны в так называемой азбуке Морзе как слово из семи — не более — символов алфавита ЭТ.

*) Так как заведомо можно удовлетвориться словарем из 100 000 русских слов.

Азбука Морзе*)

*) Знак конца буквы # кодируется временным интервалом и поэтому не входит в приведенный в таблице код Морзе.

Таким образом, слова русского языка могут быть вместо русского алфавита записаны в алфавите Морзе.

Пример. Русская фраза «Что такое расстояние?» записывается в алфавите Морзе следующим образом:

Оказывается (и этим часто пользуются в вычислительной технике), сообщения в любом конечном алфавите могут быть перекодированы с помощью двоичного алфавита 2t, {О, 1}, состоящего только из двух символов «О» и «1».

Действительно, любое целое неотрицательное число может быть представлено в виде (29), т. е. в так называемой двоичной системе счисления. Так, каждое целое число х может быть закодировано в виде слова в двоичном алфавите.

Если целые числа меняются в диапазоне 0*^х<а, то последовательность двоичных знаков х^е^е^..^.,.. .в^,

необходимая для записи любого из чисел этого диапазона, может быть выбрана из не более чем п+\ = \+[logta] знаков, как это следует из (34).

Теперь, если имеется произвольный алфавит 31 из m символов, то каждому этому символу можно сопоставить порядковый номер от 0 до m—1. Значит, каждому символу алфавита 31 можно сопоставить двоичное слово, соответствующее, согласно (29), номеру этого символа. При этом, согласно (24), можно обойтись словами длины л, где

(35)

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

*) В настоящее время большее значение приобретает так навиваемый международный телеграфный код № 2, построенный по аналогичному принципу.

Последние пять комбинаций читаются во всех регистрах одинаково.

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

Пример. Запишем в рассмотренном телеграфном коде фразу: «Фамилия автора Гамлета по-английски пишется Shakespeare, а по-русски Шекспир»:

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

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

Фраза «Гипотенуза короче суммы катетов» запишется в этом коде так:

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

В самом деле, представим себе, что вышенаписанный текст записан слитно (воспроизведем для примера первую строку):

Тогда мы можем сначала выделить первые пять знаков 00011 и написать их отдельно. Затем выделим следующие пять знаков 01000 и выпишем их отдельно. Действуя таким образом, мы получим сообщение с выделенными пробелами между словами (о разделимости слов в сообщении см. сноску на стр. 36).

Теперь введем понятие пространства сообщений. Рассмотрим произвольный алфавит 31*) и множество сообщений, состоящих ровно из п символов алфавита 31.

Назовем расстоянием между двумя сообщениями бит], Q(£» Л) количество позиций, в которых у сообщений £ и т] стоят различные символы. Полученное метрическое пространство Е(п, 31) называется я-мерным пространством сообщений в алфавите 31.

Пример 1. 31 — русский алфавит, п = 6. Пусть £ = корова; т] = ворона. Не совпадают первая и пятая буквы, следовательно, Q(£, т]) = 2.

Пример 11. 31, — двоичный алфавит, л = 12 и £ = 000110101010; Т1 = 010101101011. Не совпадают 2-й, 5-й, 6-й и 12-й двоичные знаки, q(£, т)) = 4.

Заметим, что можно было бы сравнивать любые слова длиной не более л, если условиться слова более короткие, чем л, дополнять определенным знаком (в двоичном алфавите нулем) до п символов.

*) В данном случае даже не существенно, что алфавит 21 конечен.

Проверим, что определенное выше расстояние q(£, tj) удовлетворяет всем необходимым свойствам.

Симметричность q(£ t))=q(t), £) следует из определения, в котором оба слова £ и ц участвуют равноправно. Очевидно, что q(£, г])^0, причем q(£, т]) = 0, только если, все соответствующие символы в сообщениях £ и т] совпадают, т. е. совпадают слова Е и т).

Аксиома треугольника проверяется так.

Пусть даны три слова £, т] и £ по п символов каждое. Предположим, что в £-й позиции совпадают символы у слов £ и £ и у слов £ и г]. Ясно, что тогда в этой позиции совпадают символы и у слов J И Т|.

Действительно, пусть |Ä—k-Pi символ сообщения £ft— &-й символ сообщения £, а т]А—£-й символ сообщения т). Тогда, если lk = t)k, a £ä = t]ä> то> очевидно,lk = r\k. Значит, если 1кфг\кУ то либо £*=££*, либо £*=£л*-

Таким образом, у слов £ и т| могут быть не совпадающие символы только на тех местах, где либо у £ и £, либо у £ и т] не совпадают символы. Это значит, что общее количество не совпадающих символов у слов £ и т] не превосходит суммарного числа не совпадающих символов у £ и £ и у £ и т). Но общее число символов, не совпадающих у £ и £, плюс общее число символов, не совпадающих у £ и rj, есть q (£,£) + q(£, т]). Иными словами,

(36)

что и требовалось доказать.

Пример. В пространстве £(6, SI), где SI — русский алфавит, запишем слова: £ = картон; т] = кортеж; £= кордон. Ясно, что q(£, г)) = 3; Q(£, £) = 2, q(£, т|) = 3 и

С помощью так определенного понятия расстояния можно сформулировать общий принцип построения кодов, позволяющих автоматически исправлять группы из не более чем / ошибок. Этот принцип впервые предложил Р. Хэмминг*). Он будет рассмотрен в следующем параграфе.

*) См. статью Р. Хэмминга в сб. переводов «Коды с обнаружением и исправлением ошибок», ИЛ, Москва, 1956.

§ 6. АВТОМАТИЧЕСКОЕ ИСПРАВЛЕНИЕ ОШИБОК В СООБЩЕНИЯХ

В этом параграфе мы рассматриваем пространство сообщений Е(п, 31), т. е. пространство сообщений длины п в алфавите 91. Как мы видели ранее, фактически можно ограничиться двоичными сообщениями, т. е. сообщениями в алфа-

вите 312. Все содержательные примеры будут рассматриваться именно в этом алфавите.

Рассмотрим следующую общую схему передачи информации (рис. 17). Сообщения, передаваемые источником, перекодируются в помехоустойчивый код устройством кодирования. Затем эти сообщения передаются по линиям

связи, в которых возможны искажения сообщений. После этого сообщения на приемном конце исправляются в декодирующем устройстве и снова перекодируются в исходный код, если это необходимо.

Совершенно аналогично происходит автоматическое обнаружение и исправление ошибок при хранении сообщений в машинной памяти (рис. 18).

Рис. 17.

Рис. 18.

При записи информации в память сообщения кодируются в помехоустойчивом коде. При чтении сообщения проходят соответствующую дешифровку с обнаружением и исправлением ошибок, допущенных при хранении. На рис. 18 видна дополнительная возможность, состоящая в том, что информация периодически считывается, проходит дешифровку с исправлением, а затем снова шифруется и записывается в память. Эта возможность бывает полезна, ибо она обеспечивает проверку хранимой информации не реже, чем один раз за Тсек у где Т надо выбрать так, чтобы за это время не могло возникнуть слишком много искажений в хранимой информации. Иначе говоря, чтобы расстояние q(£, £') между записанным сообщением | и считанным сообщением £' не успело стать слишком большим.

Пусть в пространстве Е(п, Щ выделено подмножество Нкс:Е(Пу Щу обладающее тем свойством, что для любых не совпадающих слов £ и г\ множества Hk расстояние удовлетворяет условию

(37)

Множество Hk назовем множеством осмысленных слов. Предположим, что при передаче или хранении осмысленного слова l£Hk допущено / ошибок (/<& — 1), т. е. неверно передано / символов из слова £. Это ошибочно переданное слово обозначим По определению расстояния q(£, £')=/. Ясно, что слово £' не осмысленно, так как в противном случае q(£, £') было бы больше / (согласно (37)).

Таким образом, проверив переданное слово и убедившись, что оно не осмысленно (для этого можно его, к примеру, сравнить со всеми словами из Hk—на рис. 17 и 18 эта возможность обеспечивается наличием словаря), мы обнаруживаем ошибочность передачи. При хранении слов в машинной памяти такую проверку можно осуществлять периодически, выбирая период Т из того условия, что за время Т мало шансов для возникновения более чем k—1 ошибок в слове. Это рассуждение показывает, что у нас уже есть общий принцип для обнаружения ошибок.

Оказывается, можно сделать больше, а именно: исправить допущенные ошибки. Для этого предположим, что число ошибок / ^ —тр . Пусть т) — произвольное осмысленное слово, не совпадающее с £, а как и ранее, ошибочно переданное сообщение.

Запишем неравенство треугольника

и подставим сюда Q(g, £')=/ и оценку (37):

Отсюда видно, что

(38)

так как по условию

Из (38) видно, что ошибочное слово |' отстоит от любого осмысленного слова т) Ф \ не менее чем на—а от £ не более чем на —^- . Следовательно, найдя ближайшее к £' осмысленное слово £, мы тем самым восстановим правильное сообщение.

Иными словами, нужно для осмысленных сообщений построить их области Дирихле.

Для каждого проверяемого (после передачи или хранения) сообщения определяется, чьей области Дирихле оно принадлежит. «Владелец» этой области Дирихле — осмысленное сообщение £— и считается правильным сообщением.

В этом и состоит замечательная идея Хэмминга. Она приводит к тому, что для передачи сообщений в условиях возможных искажений надо пользоваться не всеми возможными сочетаниями символов алфавита, а некоторым множеством осмысленных слов. Так как в русском языке используются в качестве осмысленных слов только некоторые сочетания букв, то восстановление смысла искаженного сообщения часто может быть выполнено без специальных дополнительных приемов кодирования. Это положение уже иллюстрировалось.

Мы сейчас рассмотрим несколько конкретных примеров построения множества осмысленных сообщений Нк£Е(п% 21), т. е. выясним, как фактически, исходя из общего принципа Хэмминга, строить конкретные помехоустойчивые коды. Все эти примеры мы будем строить для случая двоичного алфавита Ш2. Как мы уже видели, такое условие на самом деле не является ограничением, так как в двоичном алфавите можно записывать любые сообщения.

Задачу о помехоустойчивом кодировании можно поставить следующим образом. Пусть имеется пространство s-значных

двоичных сообщений E(sy 2Ï,). Требуется каждому такому сообщению поставить в соответствие сообщение из некоторого HkczE(ny 3Ï,). Иными словами, нужно построить некоторое множество осмысленных сообщении Нк, устойчивое относительно /-кратных ошибок, с помощью которого можно кодировать исходные сообщения из Е(s, 3Ï,). Величина

называется избыточностью кода.

В действительности точная постановка этой задачи должна исходить из заданной статистики искажений в передающем канале. При этом нужно строить такой код (множество HkaE(n, 3Ï,)), что вероятность получить в слове из п двоичных символов более чем / ошибок будет достаточно мала. Такая постановка задачи изучается в теории информации, но мы ею здесь заниматься не будем.

Для построения этих кодов удобно использовать тот факт, что над величинами 0 и 1 можно выполнять особую операцию сложения по модулю 2 согласно правилам:

Знак операции сложения обведен кружком, чтобы показать, что эта операция несколько отличается от обычного сложения. Расстояние между двумя двоичными словами £ = хххг.. .хп и т)=ЛЛ-• -Уп (xi и Vi принимают значения О или 1) можно с помощью этой операции записать так:

Действительно, в скобках здесь будут появляться единицы, когда соответствующие символы у обоих слов не совпадают, и нули в противном случае. Общее количество единиц как раз равно количеству не совпадающих символов в словах £ и т].

Рассмотрим пространство сообщений E(s, 31,) и сопоставим каждому слову gCE(s, 3Ï,) слово V длины 5+1, образованное по следующему правилу.

Первые s символов слова £' совпадают со словом £.

Последний, ($+1)-й символ слова g' выбирается равным нулю или единице с тем, чтобы общее количество единиц в слове £' было четным. Если положить ^' = х1хг.. .xsxs+iy то это условие означает, что

(39)

Отсюда можно выразить xs+l:

(40)

Например, если £ = 001 011 101, то £'=001011 101 1.

Определенные таким образом слова £' образуют множество осмысленных сообщений Нг с Е (s + 1, 212).

В самом деле, расстояние между двумя не совпадающими осмысленными сообщениями £' и £" должно быть четным, так как, если бы £' отличалось от £" в нечетном числе позиций, то сумма единиц, хотя бы в одном из слов £' или была бы нечетной. А это невозможно по построению этих слов. Так как минимальное четное число, не равное нулю, есть 2, то минимальное расстояние между различными осмысленными сообщениями равно двум.

Следовательно, этот код позволяет обнаруживать единичные ошибки. Процесс обнаружения состоит просто в том, что после передачи слова £' подсчитывается четность единиц в нем (или, что равносильно, проверятся (39)). Если критерий четности не удовлетворяется ((39) не выполнено), то принятое слово считается ошибочным. Этот процесс проверки широко известен как «проверка на четность» и очень часто применяется ввиду его простоты. Избыточность в этом случае равна jqry-

Опишем теперь принадлежащий Хэммингу красивый пример кода, способного исправлять единичные ошибки.

Пусть £Ç£(s, Sïj) — двоичное слово длины s. Образуем слово £'С£(л, 2ït) по следующему правилу. Среди л-позиций, которые занимает слово £', мы выделим 1-ю, 2-ю, 4-ю,..., 2*-ю позицию для контрольных символов, которые определяются по слову £. Между этими позициями мы будем последовательно записывать символы, образующие слово:

В написанном слове показано взаимное расположение контрольных (выделенных жирным шрифтом) и смысловых позиций для случая 5=25, /1=31, &=4. Для того чтобы разместить нужным образом 5 смысловых позиций, необходимо и достаточно, чтобы выполнялось соотношение

(41)

Избыточность данного кода равна

Контрольная позиция с номером 2' заполняется по еле* дующему правилу. Каждая позиция слова £' определяется номером /, отсчитываемым от начала слова. Рассмотрим двоичное представление этого номера:

(число двоичных разрядов в представлении номера / определяется тем, что согласно (41) /<2а+1).

Возьмем теперь множество П; всех тех позиций, для номеров которых lt=\. В множество входит одна контрольная позиция, а именно позиция с номером / = 2'. Заполним ее так, чтобы сумма всех единиц в позициях из П/ была четной.

В следующей таблице приведен пример слова £' (его можно прочесть по вертикали во втором столбце таблицы), указаны двоичные номера позиций и отмечена знаком * принадлежность каждой позиции к множеству П|- Слова построенные по этому правилу, назовем осмысленными.

Продолжение

Покажем, что расстояние между любыми двумя осмысленными словами £' и п/ не менее чем 3, то есть осмысленные слова образуют множество HtŒE(s + k1 21,).

I случай. Пусть соответствующие слова £ и т) из E(s, 2lt) отличаются не менее чем в трех позициях. Ясно, что слова £' и т]' также отличаются не менее чем в трех позициях, а следовательно, Q(£', т]')^3.

II случай. Пусть слова £ и т) отличаются в двух позициях. Тем самым слова £' и г\' отличаются в двух смысловых позициях с номерами / и /'. Выберем множество позиций П,, содержащее позицию / и не содержащее позиции /'. Для этого нужно номер * выбрать так, чтобы /-й двоичный знак числа /, /,= 1, а /-й двоичный знак числа l\ li=zO (так как /=£/', то у них обязательно есть не совпадающие двоичные знаки).

Таким образом, у слов £' и т|' количество единиц в смысловых позициях множества П,- отличается на одну. Так как общее число единиц во множестве позиций П,- должно быть четным и у и у т|', то слова £' и т)' должны отличаться еще и в контрольной позиции множества (в позиции с номером 2'). Тем самым £' и т|' отличаются не менее чем в трех позициях, (>(£', т)')^3.

III случай. Пусть слова £ и г] отличаются в одной позиции. Тогда слова £' и т)' отличаются ровно в одной смысловой позиции с номером /. Этот номер не может быть точной степенью двойки, так как номера вида 21 закреплены за контрольными позициями. Таким образом, у номера / есть по крайней мере два ненулевых двоичных знака /,= 1 и /у = 1. Следовательно, позиция с номером / входит в два множества IL и П/. Так как количество единиц в этих множествах

позиций и для и для т)' должно быть четным, то кроме /-й позиции слова £' и г)' обязательно должны отличаться и в контрольных позициях с номерами 2' и 2^.

Всего, таким образом, слова £' и т)' отличаются не менее чем в трех позициях, Q(|'. т)')^3.

Итак, доказано, что множество осмысленных сообщений есть Н9 и, следовательно, позволяет принципиально восстанавливать единичные ошибки.

В данном случае этот процесс восстановления может быть сравнительно просто выполнен. В основе этого лежит такое соображение. Для исправления слова в двоичном алфавите достаточно узнать номер позиции, где допущена ошибка и переменить содержимое в этой позиции (если был «О», поставить «1» и наоборот).

В рассматриваемом коде номер неисправной позиции устанавливается путем следующих проверок.

После передачи сообщения в результате которой возможно искажение в одной позиции %' —► £*, проверяется четность единиц для каждого множества позиций П4-.

Иными словами, вычисляются контрольные величины

т. е. а; равна сумме по модулю 2 всех символов в позициях множества П,- принятого сообщения £*.

Если все 06/ = 0, то £* является осмысленным сообщением*). Если же некоторое at=l, то ошибка допущена в позиции, принадлежащей множеству П/э а значит, номер / этой позиции имеет /-й двоичный знак, равный 1, /,= 1.

Таким образом, контрольные величины а{ равны знакам двоичного разложения номера ошибочной позиции /, т. е.

(42)

Это значит, что после всех контрольных вычислений номер / определен и дает возможность восстановить правильное сообщение £''.

Для примера возьмем слово \\ записанное в предыдущей таблице, и исказим его в 19-й позиции. Получится слово

*) То есть если и была допущена ошибка, то не менее чем в трех позициях, и её нельзя исправить с помощью данного кода.

осуществляя все проверки, получаем

т. е. /=10 101, что соответствует десятичному числу 19. Переменив в 19 позиции слова £* 0 на 1, получаем передававшееся слово

Более простой код с исправлением одиночных ошибок будет, если слово £' получается трехкратным повторением слова £Ç£(s, §t2). Если £ и т) отличаются в г позициях, то соответствующие £' и т|' отличаются в Зг позициях. Таким образом, (>(£', ч\')^Ъ, если \'Фх\'. Проверка переданного слова осуществляется так.

Берутся тройки позиций с номерами /, l + s, / + 2s. Если символы в этих позициях совпадают, то соответствующий символ считается правильно переданным. Если совпадают два из этих символов, то их общее значение считается правильным и заносится в третью позицию.

Если все три символа не совпадают, то ошибку исправить нельзя.

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

Недостатком этого кода является его большая избыточность, равная s-=Избыточность предыдущего кода примерно равна log*s, что при больших s (длинных сообщениях) близко к нулю.

Коды, позволяющие исправлять ошибки при передаче и хранении сообщений, очень важны для различных устройств автоматического управления. За последние 10 лет появилось большое количество работ, где изучены коды, исправляющие единичные или групповые ошибки.

§ 7. РАССТОЯНИЯ И НОРМЫ В МНОГОМЕРНОМ ПРОСТРАНСТВЕ

В этом параграфе рассматривается так называемое /{-мерное векторное пространство Еп и различные определения расстояния в нем, превращающие Еп в различные метрические пространства. Векторное пространство Еп служит обобщением понятий прямой, плоскости и трехмерного пространства из элементарной геометрии. Прийти к разумному

определению л-мерного пространства можно следующим образом.

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

Каждой точке M однозначно соответствует вектор (см. рис. 19), соединяющий начало координат с этой точкой. Таким образом, существует взаимное однозначное соответствие между следующими объектами:

точка M <-> вектор ОМ пара координат (х, у).

Это значит, что можно с одинаковым успехом говорить о плоскости как о множестве точек, как о множестве векторов или как о множестве пар чисел (х, у)*). Аналогично, о трехмерном пространстве можно говорить как о множестве троек чисел (х, у, z). Теперь уже сами собой напрашиваются такие определения.

n-мерным вектором называется упорядоченная совокупность из п вещественных чисел

Числа xv х1У..., хп называются координатами вектора |. Множество всех л-мерных векторов называется n-мерным векторным пространством Еп.

Ясно, что векторное пространство Ег есть обычное трехмерное пространство, пространство Ег есть плоскость, а пространство Ех — прямая.

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

Суммой векторов l = (xv х„ хп) и r\ = (yv у„... ... ,уп) называется вектор

Рис. 19.

*) То есть говорить об одном и том же математическом объекте—плоскости — на языке точек, на языке векторов или на языке числовых пар. Любое утверждение может быть переведено с каждого языка на каждый.

у которого координаты равны суммам соответствующих координат слагаемых.

Аналогично, разностью тех же векторов \ и ij называется вектор

у которого координаты равны разностям соответствующих координат.

Произведением вектора | = (а:1, лг2,..., хп) на число а называется вектор

Иными словами, чтобы умножить вектор на число, нужно умножить на это число все его координаты. На плоскости и в трехмерном пространстве эти операции имеют простой геометрический смысл. Для наглядности рассмотрим два вектора | и rj на плоскости (см. рис. 20). Из рисунка видно, что сумма ç^l + t] есть вектор, образованный диагональю параллелограмма, построенного на векторах | и т]. Такое определение суммы векторов возникает в физике при сложении сил.

Разность векторов | и т| (см. рис. 21) есть вектор, направленный из конца вектора г\ в конец вектора §.

Произведение вектора | на положительное число а есть вектор, имеющий то же направление, а длину, в а раз большую, чем |. (Ясно, что при а< 1 длина вектора а\ меньше длины вектора |.) Чтобы умножить вектор | на отрица-

Рис. 20. Рис. 21.

тельное число я, надо умножить его на |а|, a затем изменить направление на противоположное. Все эти случаи показаны на рис. 22.

Легко показать, что операции над /z-мерными векторами удовлетворяют следующим свойствам, аналогичным свойствам соответствующих числовых операций.

Здесь использовано обозначение для нулевого вектора О = (0, 0, ..., 0). Ясно, что два вектора \ и rj совпадают в том и только том случае, когда \—т|=0.

Рассмотрим несколько примеров многомерных пространств, естественно возникающих в геометрии.

Пример I. Множество всех шаров в пространстве. Каждый шар определяется четырьмя параметрами (х, у} г, R)t где (х, у, z) — координаты центра, a R — радиус.

Рис 22.

Пример II. Множество всех треугольников. Каждый треугольник определяется девятью параметрами (xv yv zv *i> Л» *t> xt> Л1 где каждая тройка (xh yiy z{)

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

Теперь рассмотрим различные способы определения расстояния в Еп% превращающие Еп в различные метрические пространства.

Пространство 1лп) получается, если расстояние определить формулой

(43)

В трехмерном пространстве и на плоскости расстояние Qi (1> совпадает с обычным геометрическим расстоянием. Свойства 1, 2, 3 для этого расстояния очевидны.

Пространство l[n) определяется с помощью расстояния

(44)

В случае плоскости это расстояние совпадает с расстоянием Qj(Af, ЛО» определенным в § 4. Опять-таки, свойства 1, 2 и 3 для расстояния Qt(|, т)) очевидны.

Пространство С(П) возникает, если ввести расстояние по правилу

(45)

т. е. как максимальное отклонение координат соответствующих векторов. Свойства 1, 2 и 3 очевидны и для этого расстояния, которое на плоскости совпадает с введенным в § 4 расстоянием Q«, (M, N).

Докажем аксиому треугольника для пространства /(,п).

Пусть

Тогда, очевидно,

что и требовалось доказать.

Для пространства Ön) аксиома треугольника доказывается так. Пусть \xk—yk\ самая большая из соответствующих разностей координат, т. е.

(46)

Очевидно, что

(47)

Сравнивая (46) и (47), получаем искомое соотношение

Более общий вид метрических пространств получится, если ввести расстояние по формуле

где и получить таким образом пространство/^.

Свойства 1, 2 и 3 проверяются здесь столь же легко. Неравенство треугольника (свойство 4) получается из неравенства Минковского (см. ссылку на стр. 28):

Нетрудно видеть, что при /? = 1 и р = 2 получаются выше определенные пространства l\n) и l[n\ При р—►со расстояние Qp (£, г\) переходит в расстояние q«, (£, г)), т. е. = Этот факт читатель сумеет легко проверить, обобщив аналогичные рассуждения из § 4.

В качестве более трудного упражнения читателю предлагается показать, что обобщенный шар радиуса г в пространстве /(!8) имеет вид октаэдра (рис. 23), а в пространстве 09) имеет вид куба (рис. 24).

Пространства 1{рп\ так же как и соответствующие пространства 1р на плоскости, называются пространствами Минковского. Эти пространства допускают красивые обобщения на случай бесконечного количества координат у вектора.

Более общий вид расстояния можно ввести с помощью понятия выпуклого тела.

Введем несколько новых определений. Каждый вектор из векторного пространства Еп мы будем геометрически интерпретировать как точку, соответствующую концу этого вектора, считая сам вектор выходящим из начала координат. Поэтому каждому факту, относящемуся к векторам, соответствует некоторое свойство точек л-мерного пространства. Назовем подмножество V пространства Еп выпуклым, если вместе с каждыми двумя векторами | Ç V и r\£V оно содержит любой вектор вида а\ -+ ( 1 — а) ц, где а —любое число между нулем и единицей (0^а^1). Геометрически (в Et и в Ег) это означает, что множество V вместе с любой парой точек содержит и весь отрезок, соединяющий эти точки.

Назовем подмножество VаЕп ограниченным, если существует такое общее для всех векторов число А, что координаты всех векторов | Ç V удовлетворяют неравенствам

Рис. 23. Рис. 24.

На рис. 25 изображено выпуклое, но не ограниченное множество на плоскости. А на рис. 26 — выпуклое и ограниченное множество.

Вектор |, принадлежащий множеству I/, называется внутренним для множества V если для всякого вектора г\ можно подобрать такое положительное число а, что век гор £ + ац также входит в множество V. Это значит, что если из конца вектора | двигаться по любому направлению, то некоторое время мы будем еще находиться во множестве V.

Если V—плоская фигура, расположенная в пространстве то никакая его точка не является внутренней. Действительно (см. рис. 27), если |çV,a вектор х\ перпендикулярен плоскости, где лежит И, то при любом а вектор | + ат) лежит вне этой плоскости, а следовательно, и вне фигуры V.

Наличие во множестве V внутренних точек делает его «полно размерным».

Назовем, наконец, выпуклым телом выпуклое ограниченное множество V, имеющее хотя бы одну внутреннюю точку*).

Рис. 25.

Рис. 26. Рис. 27.

*) Читателю предоставляется доказать, что в этом случае множество V обязательно имеет бесконечно много внутренних точек.

Рассмотрим выпуклое тело Vy имеющее О своей внутренней точкой и симметричное относительно этой точки. Последнее означает, что вместе с каждым вектором \ в теле V содержится и противоположный вектор — \.

С помощью этого выпуклого тела можно ввести расстояние Qv(\y Для этого используем такую конструкцию. Образуем разность векторов £ = |— ц. Так как О является внутренней точкой тела V, то существует такое положительное число а, при котором а£ Ç V. С другой стороны, из ограниченности тела V следует, что при достаточно больших а вектор а£ лежит вне тела Vy если сам вектор £=^=0. Определим расстояние Qv(%, Л) как нижнюю грань величин — , а > 0, для которых вектор а£ еще принадлежит телу V%

(48)

При £ = 0, т. е. когда векторы | и х\ совпадают, допустимо любое а (так как всегда aÇ=0ÇV) и нижняя грань в (48) равна нулю. При несовпадающих \ и т) вектор J^O и допустимые значения а ограничены сверху. С другой стороны, при достаточно малых а > 0, a£ÇV; поэтому значения величины ~ также ограничены сверху. Следовательно, в этом

случае величина Qy (£, ц) конечна, положительна и не равна нулю*).

Из симметричности выпуклого тела V следует, что векторы а\ и а( — £) принадлежат телу V при одних и тех же значениях а. Так как —£ = 1) — 1, то отсюда следует симметричность расстояния

Итак, для определенного нами с помощью выпуклого тела V расстояния доказаны свойства 1, 2 и 3 (см. стр. 18). Осталось доказать неравенство треугольника.

Это можно сделать следующим образом.

Рассмотрим три вектора |, х\ и Ç. Выберем два положительных числа а и Этакие, что а (| — £) ç V и £(£ — tj) ç V.

*) Здесь мы пользуемся свойствами нижней грани, которые неискушенному читателю очевидны, а знакомому с понятием нижней грани известны.

Обозначим теперь через а число

Ясно, что 0 < а < 1 и

В силу выпуклости тела V вектор

(49)

также содержится в V. Преобразуем теперь выражение (49), подставляя вместо а и 1 —а их значения и пользуясь свойствами операций над векторами:

(50)

Так как вектор 0 = с — т^СУ, то число

может быть только больше расстояния Qv{\, т|):

(51)

Однако в силу определения чисел а и b величины

можно сделать сколь угодно близкими, соответственно к расстояниям QK(1, ?) и QK(£, îj). Так как при переходе к пределу знак неравенства сохраняется, то из (51) получается искомое неравенство

(52)

справедливое для любых троек векторов.

Определение расстояния с помощью симметричного выпуклого тела V можно изложить в несколько иных терминах.

Назовем нормой вектора | величину

(53)

Ясно, что определенное выше расстояние QK(1, ц) равно норме разности векторов \ и т|

(54)

Можно показать (оставляем доказательство читателю), что норма удовлетворяет следующим свойствам:

Можно было бы подойти к понятию нормы иным, более абстрактным способом. Назовем нормой в л-мерном векторном пространстве Еп число || |||, поставленное в соответствие каждому вектору |, так что при этом выполнены следующие свойства:

Векторное пространство Еп с определенной в нем нормой называется п-мерным пространством Минковского*). Оказывается, что норма всегда может быть определена с помощью некоторого симметричного выпуклого тела V. Проверим это утверждение. Рассмотрим множество V, состоящее из всех векторов |, для которых

Покажем, что это множество является выпуклым симметричным телом в Еп.

Выпуклость множества V проверяется так. Пусть | £ V и tjÇ V, и пусть О^а^ 1. Тогда по свойствам нормы 3 и 4

т. е. вектор а£ + (1—а)х\ также принадлежит множеству V, что и означает выпуклость последнего.

Проверим, что О является внутренней точкой множества V. Действительно, если | любой вектор, не равный нулю, то,

выбрав число a=jTTT|i мы убедимся, что

*) В честь известного математика Г. Минковского— одного из создателей теории относительности.

т. е. a% Ç V. Если же £ = 0, то для любого числа а% так как по свойству 2|| а\\\ = ||0|| =0< 1.

Симметричность множества V следует из свойства 3. Действительно, если |£1Л то |||||<1, но тогда ||—|||= ЩИ, т. е. -1£1Л

Ограниченность множества V доказывается несколько более громоздко, и мы это доказательство опустим.

Итак, множество V есть выпуклое тело и с помощью него можно определить норму |||||к. Покажем, что эта норма совпадает с нормой |||||. Пусть а—такое положительное число, при котором a|ÇV. Это значит, что ||а$(<1, a значит, аii 11^1 и ~^|||||. Нижняя грань величины-^- достигается, если положить û = |]-jtîj, таким образом:

(55)

Сравнивая равенства (55) и (53), убеждаемся, что

(56)

что и требовалось доказать.

В случае трехмерного пространства Е9 норме, определяемой с помощью произвольного выпуклого тела V, можно дать простое физическое истолкование.

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

Будем теперь из начала координат откладывать по каждому направлению вектор, равный величине скорости звука с вдоль этого направления. Предположим, что совокупность концов этих векторов ограничивает некоторое выпуклое тело V. Нетрудно видеть, что тело V ограничено, центрально-симметрично относительно начала координат и имеет последнее своей внутренней точкой. Тем самым в Ег определяется норма HIiiу и расстояние

Читателю предоставляется проверить, что это расстояние равно времени, за которое звуковой сигнал проходит из конца вектора \ в конец вектора tj по прямой, соединяющей эти концы.

Кроме конечномерных пространств Минковского, в мате матике рассматриваются и аналогичные бесконечномерные — так называемые банаховы пространства. Банаховым*) пространством называется множество элементов (векторов), над которыми можно выполнять операции сложения, вычитания и умножения на число и для которых определено понятие нормы.

При этом нужно, чтобы операции над векторами удовлетворяли всем условиям, перечисленным на стр. 55, а норма обладала свойствами, указанными на стр. 62.

Пример бесконечномерного банахова пространства можно построить следующим образом.

Назовем вектором любую непрерывную функцию /(/), определенную при 0^/^1. Суммой векторов назовем сумму функций/(/) +g(t). Произведением вектора/(г) на число а назовем функцию af(t)y получаемую умножением всех ее значений на число а. Нулевым вектором является функция /0(/)==0, тождественно равная нулю. Нормой функции назовем максимум ее модуля

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

Это пространство обычно обозначается как С[0,.] или просто С.

Банаховы пространства, в которых векторами являются функции, играют большую роль в современной математике.

То обстоятельство, что метрическое пространство, точками которого являются функции, является бесконечномерным, можно пояснить следующим рассуждением.

Рассмотрим отрезок [0, 1] и проведем через какие-то из точек этого отрезка вертикальные прямые (рис. 28).

Рис. 28.

*) Название дано в честь известного польского математика С. Банаха (1892—1945), одного из основателей так называемого функционального анализа — важной ветви современной математики.

Возьмем вектор |=(jclf jtt, .хп), принадлежащий /z-мерному пространству, и будем откладывать его координаты на этих вертикальных прямых.

Полученные точки на вертикалях образуют график некоторой функции, заданной в соответствующих точках отрезка [О, 1J. Отсюда видно, что при п—► со эти наборы точек могут приближаться к графикам непрерывных функций. (При этом надо выбирать только «гладкие» наборы точек, т. е. такие, что ординаты на близких вертикалях близки.) Если в Еп взять норму Сп\ т. е. || £ || = max ( | хх |, |xt|, ... • • •> |*п|)> то «в пределе» эта норма переходит в норму С:

§ 8. СГЛАЖИВАНИЕ ОШИБОК ЭКСПЕРИМЕНТАЛЬНЫХ ИЗМЕРЕНИЙ

При наблюдении той или иной физической величины результатом эксперимента обычно является серия измеренных значений этой величины (xv хг, ..., хп).

Сама эта величина может быть стационарной или переменной. В последнем случае значения хх, х1У хп теоретически должны получаться изменяющимися по какому-то закону, а в первом случае постоянными. Кроме того, в величинах xv хг, ..., хп содержатся еще ошибки измерений, искажающие картину.

Эту ситуацию можно было трактовать как получение некоего сообщения от природы, на которое из-за несовершенства эксперимента налагаются искажения.

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

Если измеряемые величины могут принимать любые вещественные значения, то в качестве пространства сообщений можно взять л-мерное векторное пространство Еп. Расстояние между точками этого пространства q (§, г\) определяется из конкретных свойств проводимого эксперимента. Наиболее часто используется расстояние вида

(57)

при котором пространство сообщений является пространством

Теоретически возможные сообщения образуют подмножество H пространства сообщений.

В качестве правильного сообщения выбирается вектор «ближайший» к принятому сообщению |, т. е. такой, что

(58)

Для расстояния вида (57) этот принцип широко известен под названием метода наименьших квадратов и впервые предложен великим немецким математиком К. Гауссом.

Рассмотрим теперь конкретный пример подмножества теоретически возможных сообщений. Предположим, что измеряемая величина изменяется во времени по линейному закону:

Это значит, что каждый вектор ч\£Н имеет вид Ч = 0\» Уш* •••» Уп), где

Вектор определяется двумя параметрами k и Ь.

Пусть вектор, полученный в результате измерений этой величины, равен 1 = (лгр л:,, ...,хп). Основное условие (58) записывается теперь так:

В выражении F(ky b) неизвестными являются параметры искомого теоретически возможного сообщения k и Ь\ величины iv tty ..., tn и xv х2, ..., хп известны из опыта.

*) Для простоты будем считать, что ошибками в определении моментов времени // можно пренебречь.

Для отыскания минимума величины F(k, b) используем критерий, известный из дифференциального исчисления:

(59)

который в данном случае положительной квадратичной функции F(k, b) является необходимым и достаточным для минимума.

Вычислим частные производные:

(60)

Обозначим для удобства

Выражения (60) можно записать тогда в виде

(61)

Приравнивая согласно (59) эти выражения нулю, сокращая на два и перенося свободные члены в правую часть, получаем основные уравнения метода наименьших квадратов в символической форме:

(62)

На рис. 29 изображены измерения значения xv xt, xv xv xs, xe, x7, xs и определенная по методу наименьших квадратов прямая y = kt+b. Из этого рисунка понятен смысл термина «сглаживание» ошибок.

Следующая таблица показывает рациональный порядок выполнения вычислений.

Система (62) имеет в этом случае вид

Решением являются k = 0,319, b=—0,032. Искомое теоретическое сообщение у = 0,319/ — 0,032.

Аналогично, если множество теоретически возможных сообщений H состоит из параболических зависимостей

Рис. 29.

вида у = at2 + bt + с, то основное условие (53) запишется в виде

Минимизация функции F(a, с) сводится к решению системы трех линейных уравнений с тремя неизвестными параметрами a, b и с.

Основные приемы метода наименьших квадратов легко переносятся на случай расстояния вида

(63)

где (Хр а,, ап — положительные числа (веса). Неравные веса приходится использовать, если отдельные измерения в эксперименте не равноточны и более грубым измерениям приходится приписывать наименьший вес.

Основной принцип сглаживания ошибок (58) применяется также для расстояний в пространствах С{п) и l[n). Однако при этом методы восстановления теоретически возможного сообщения оказались более сложными.

§ 9. БОЛЕЕ ОБЩИЕ ОПРЕДЕЛЕНИЯ РАССТОЯНИЯ

Как мы уже говорили, возможны различные обобщения понятия расстояния. Одно из наиболее радикальных обобщений используется в теории относительности. В этой теории рассматривается пространственно-временной мир, состоящий из точек вида (л;, уу z, t), где х, у и z — пространственные координаты, a t — момент времени. Расстояние (пространственно-временной интервал) между двумя такими точками определяется по формуле

(64)

где с—скорость света. Ясно, что расстояние (64) может принимать и мнимые значения.

Можно было бы обобщить понятие расстояния, считая, что функция q(M, N), удовлетворяя всем свойствам расстояния 1, 2, 3 и 4 (см. § 3, стр. 18), может принимать бесконечные значения*). Однако в этом случае множество

*) Точнее, значение + оо.

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

Рассмотрим такое «обобщенное» пространство Е. Выберем некоторую точку NX£E и рассмотрим множество Ev состоящее из всех точек m пространства Е, для которых расстояние q(Nv m) конечно.

Пусть m и м'—произвольные точки множества ev тогда по аксиоме треугольника

Следовательно, q(M, m') конечно, а, значит, множество Ех образует метрическое пространство с конечным расстоянием. Выкинем из Е множество Ех. Если Е совпадает с ev то само Е есть обычное метрическое пространство. Если же нет, то среди оставшихся элементов выберем наугад элемент Nt и образуем множество Ег из элементов м, для которых расстояние Q(Nt, m) конечно.

Продолжая этот процесс*), можно как раз и получить разбиение обобщенного пространства Е на обычные метрические пространства с конечным расстоянием. Этот пример показывает, что получить содержательное обобщение какого-либо математического понятия не так-то просто. Во всяком случае, такое обобщение должно идти от содержательного изучения объектов, а не от чисто формального изменения аксиом. В частности, существует ряд вполне содержательных обобщений метрического пространства. Одно из таких обобщений мы и рассматриваем далее. Именно, понятие расстояния можно обобщить, отказавшись от условия симметрии (условия 1). Получающийся при этом класс пространств оказывается связанным с некоторыми существенными для математики объектами и поэтому заслуживает рассмотрения.

Мы будем называть обобщенным метрическим пространством множество Е, для любых двух элементов которого I и т] определено вещественное число q(|, т)) со следующими свойствами:

*) В действительности проводить этот процесс придется с помощью так называемой трансфинитной индукции, поэтому мы говорим только об идее доказательства.

2. Двойное равенство q(|, г]) = о(г], £) = 0 выполняется тогда и только тогда, когда элементы £ и т] совпадают:

3. Для любой тройки элементов g, r], Ç

Ясно, что обычное расстояние удовлетворяет этим условиям. Однако этим свойствам 1,2,3 может удовлетворять и функция q(£, г)), несимметричная относительно своих аргументов. Пример с несимметричным расстоянием у нас встретился фактически в конце § 4 в связи с определением расстояния как минимального времени, затрачиваемого на переход из одной точки в другую. В связи с тем, что путь в противоположные концы может занимать разное время, это расстояние, вообще говоря, несимметрично, хотя аксиома треугольника проверяется легко.

Другой пример пространства с несимметричным расстоянием получается, если рассмотреть множество из 1U точек, являющихся вершинами ломаной, изображенной на рис. 30,

Расстояние между точками Mt и Му, Q(Miy Mf) определяется как минимальное число отрезков, проходимых против стрелки в пути, соединяющем Ж,- и Жу.

Например,

Рис. 30.

Ясно, что q (Ж,-, Mj) ^ 0. Условие q (Mi, Mj)—q Ж,.)=0 (равенство нулю обоих расстояний) означает, что и точку Mt с Mj и точку Mj с Mi можно соединить отрезками, направленными по стрелке, т. е. Mi и Mj принадлежат замкнутой ломаной с согласованными направлениями отрезков. Так как таких петель на рис. 30 нет, то равенство Q(Mh Ж/) =Q(My., Ж,) = 0 влечет за собой совпадение точек М( и Жу. Таким образом, мы проверили выполнение условий 1 и 2 для несимметричного расстояния.

Аксиома треугольника проверяется следующим рассуждением. Рассмотрим путь с наименьшим количеством отрезков, направленных против стрелки, идущий из М{ в Aîft, и аналогичный путь из Mk в Mj. Объединяя эти пути, мы получим путь из М( в Mj с количеством отрезков, направленных против стрелки, равным Q(Mh Mh)+Q(Mk, Mj). Так как в «кратчайшем» пути из М{ в Mf количество таких отрезков может быть только меньше, то

(65)

В этом примере можно было бы определить новое расстояние по правилу

(66)

Это расстояние равно просто минимальному количеству отрезков в пути, соединяющем точки М{ и Mу. Отсюда ясно, что Q* (Mh MJ) обладает свойствами обычного расстояния.

Аналогичный факт справедлив для любого обобщенного метрического пространства.

Теорема. Если в обобщенном метрическом пространстве с расстоянием q(£, г\) ввести новое расстояние

(67)

то оно обладает всеми свойствами обычного расстояния и пространство превращается в обычное метрическое пространство.

Доказательство. Симметричность расстояния Q* (£, у\) следует из того, что правая часть (67) не меняется при перестановке I и т). Так как q(£, тО^О и q(t), £)^0, то Q*(Ê> т|)^0. Равенство q* (|, т]) = 0 равносильно двойному равенству q (£, t]) = q(t], £) = 0, т. е. равносильно совпадению точек £ и tj. Наконец, складывая два неравенства

получаем

или

т. е. для нового расстояния выполнено неравенство треугольника.

Интересный пример обобщенного метрического пространства с несимметричным расстоянием получается с помощью важного понятия частично упорядоченного множества.

Множество называется частично упорядоченным, если для некоторых пар точек M и N этого множества имеет смысл отношение M{N (читается: M предшествует N) и при этом выполняются свойства:

1. Если M (Л/, то невозможно отношение N { М.

2. Если М{ N, а N { Z,, то M{L.

Примером частично упорядоченного множества является множество точек на рис 30. Для этого нужно положить Mj(Mt1 если из точки Мх можно достичь точку Мр двигаясь только по отрезкам вдоль стрелки. Например, Л18 { Ж10, Мх { /И„ Мг { Мь.

Второй пример получится, если взять множество точек на числовой прямой и положить х {у, если число х < у. В этом случае для каждой пары различных точек х и у справедливо либо отношение х { уу либо у {х (такие множества называются упорядоченными).

Во всяком частично упорядоченном множестве Е можно ввести понятие непосредственного предшествования.

Точка M непосредственно предшествует точке N (пишется: MQN), если M{N и не существует третьей, отличной от M и N точки I, лежащей между ними: M ( L(N.

Так, в примере на рис. 30 Мг О Мг, Мг О Л44» М\ О ^ и т. д.

Во множестве вещественных чисел непосредственно предшествующих точек нет вообще. Действительно, если х{у%

то всегда

Теперь рассмотрим конечное частично упорядоченное множество Е. Предположим, что множество Е обладает свойством связности. Это значит, что для любых точек M и N из Е существует последовательность точек L1=M, . .., Lk = N, так что для любой пары Lt, Li + l либо Li { Li+V либо Li+l(Li. Так, для точек Мг и Ж8 на рис. 30 эту последовательность можно составить так:

так как

Можно проверить, что это множество является связным.

Множество точек на рис. 31 не является связным, так как для точек /И8 и Мг такой последовательности нельзя найти. Однако оба подмножества 5Л {МХУ Mt} Mf, Л/4} и Ег{Мь, Мь, М7, М%\ являются связными. Можно легко проверить, что всякое конечное частично упорядоченное множество распадается на связные подмножества без общих точек. Введем теперь в конечное связное частично упорядоченное множество Е расстояние q (M, N), определенное по следующему правилу. Назовем путем из M в N цепочку из точек LX=M\ 18, Lv ..., Lk = N таких, что всегда или L(OLl+v или Li + lOLi. Длиной пути мы назовем количество точек L{ в нем, для которых Li+lQLl. Тогда расстоянием q(M} N) мы назовем минимальную длину пути из M в N. Проверим, что так определенное расстояние обладает всеми необходимыми свойствами.

Неотрицательность расстояния q(AÎ, N) следует из определения. Для доказательства второго свойства расстояния заметим, что при несовпадающих M и N из условия Q(M, N)=0 следует, что M {N. Действительно, условие 0(УИ, Л/) = 0 означает, что существует цепочка точек Lx = Af, ifl ... , Lk = N такая, что всегда Lf0^i + i» а следовательно, и L{{LUv Но тогда по второму свойству частичной упорядоченности получается, что М{ N. Аналогично, из q(N} Af)=0 вытекает, что N( Ai Значит, если M и N — разные точки и Q(M, N)=q(N, Af)=0, то одновременно M{N и N{ M. Так как последнее невозможно по первому свойству частично упорядоченных множеств, то M совпадает с N. Итак, второе свойство расстояния доказано.

Для доказательства третьего свойства (аксиомы треугольника) используем надежно послуживший нам ранее прием. Возьмем «кратчайший» путь из в Q: M = Z,t, L% ... , Lk = Q и «кратчайший» путь из Q в N: Q = LU Lt1 ... ... , Lp=N. Объединяя их, мы получим цепочку точек M = LX, Lt, ... , Lk = Q = Lu Lt1 ... , Lp = N, образующую путь из M в N. Общее число смежных точек этой цепочки, для которых LUlÇ)Lt (Lt + iQ^/)» Равно сумме

Рис 31.

расстояний q (Ж, Q)+Q(Q, n). Ясно, что число таких пар для «кратчай шего» пути из Ж в n может быть только меньше этого значения:

(68)

Итак, доказано, что всякое конечное связное частично упорядоченное множество е является обобщенным метрическим пространством, если определить расстояние по указанному рецепту.

В качестве упражнения предоставляем читателю убедиться, что для всякой пары точек Ж и n таких, что м{ /V, расстояние q (Ж, n) = 0.

Оказывается, что верно и в некотором смысле обратное утверждение. Именно в каждом обобщенном метрическом пространстве е можно ввести частичную упорядоченность, определив правило предшествования так: m{n, если е(Ж, n) = 0.

Покажем, что при этом выполнены оба свойства частичной упорядоченности. Пусть Ж и n—разные точки и Ж { n, т. е. q(M, n) = 0. Тогда, если бы было одновременно Л7( Ж, то было бы и q(A/, Ж) = 0. Отсюда по второму свойству расстояния вытекало бы, что Ж и /V совпадают. Так как последнее неверно по предположению, то, значит, из Ж { n следует невозможность отношения n { Ж. Первое свойство частичной упорядоченности доказано.

Пусть теперь m ( l и l { n. Это значит, что д(Ж, l) =0 и q (l, Л/) = 0. Тогда, по аксиоме треугольника,

Мы доказали, таким образом, что из m {l и l {n следует m{n.

Полученное частично упорядоченное множество, вообще говоря, не обязано быть связным.

Рассмотрим, например, частично упорядоченное множество е точек на рис. 31 (стр. 74). Между точками подмножества е1{м1% мг, Ж8, Ж4} можно определить расстояние с помощью «наикратчайших» путей. То же самое можно сделать и для точек подмножества £,{Ж6, Жв, Ж7, Ж8}. Определим теперь расстояние между любой точкой м1^ех и любой точкой ЖуСЯ,, просто положив

(69)

Нетрудно проверить, что мы получим обобщенное метрическое пространство, в котором равенство q(M, n)=0 равносильно отношению m ( n в частично упорядоченном множестве Е. Однако Е не является, как уже говорилось, связным частично упорядоченным множеством.

Можно ввести понятие связного обобщенного метрического пространства. Именно, пространство Е называется связным, если для любой пары несовпадающих точек M и n из Е существует цепочка точек Ll = M, Lt, ... ,Lk = n такая, что для любой смежной пары точек L{ и Li+l, либо Q(Lh Ll + 1)=0, либо g(Li+1, Lt)=0. Читатель легко проверит, что связным метрическим пространствам соответствуют связные частично упорядоченные множества.

Конечное частично упорядоченное множество (а значит, и соответствующее метрическое пространство) можно довольно просто изобразить геометрически. Для этого будем изображать элементы частично упорядоченного множества точками в трехмерном пространстве, обозначая их теми же буквами, что и соответствующие элементы. Каждую пару точек M и N, для которых соединим линией, направленной из .V в Ж, и укажем это направление стрелкой. Полученная геометрическая фигура, состоящая из точек (вершин этой фигуры) и соединяющих их направленных линий, называется графом. Примеры графов мы уже видели на рис. 30 и 31.

Нетрудно видеть, что если M { n, то из n в M можно попасть, двигаясь только но направлению стрелки.

Заметим в заключение, что пространства с несимметричным расстоянием связаны также с важным для математики понятием дискретных топологических пространств.

На этом мы заканчиваем изучение понятия расстояния. Мы установили, что это понятие имеет много различных аспектов и связано не только с чисто математическими задачами, но и с такими вполне прикладными проблемами, как построение помехоустойчивых кодов. Эта особенность—многозначность применений и сложные логические связи — характерна и для других существенных математических понятий. Основной смысл создания таких понятий как раз и состоит в возможности установления связей и аналогий между, казалось бы, очень далекими областями и в выяснении скрытых пружин, от которых зависят математические свойства различных объектов.

Цена 11 коп.

ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ

Вып. 1, А. И. Маркушевич. Возвратные последовательности.

Вып. 2. И. П. Натансон. Простейшие задачи на максимум и минимум.

Вып, 3, И. С. Соминский. Метод математической индукции.

Вып. 4. А, И. Маркушевич. Замечательные кривые.

Вып. 5. П. П. Коровкин. Неравенства.

Выо. 6. Н. Н. Воробьев. Числа Фибоначчи.

Вып. 7. А. Г. Курош. Алгебраические уравнения произвольных степеней.

Вып. 8. А. О. Гельфонд. Решение уравнений в целых числах.

Вып. 9. А. И. Маркушевич. Площади и логарифмы.

Вып. 10. А. С. Смогоржевский. Метод координат.

Вып. 11. Я. С. Дубнов. Ошибки в геометрических доказательствах.

Вып. 12. И. П. Натансон. Суммирование бесконечно малых величии.

Вып. 13. А. Н. Маркушевич. Комплексные числа и конформные отображения.

Вып. 14. А. И. Фетисов. О доказательствах в геометрии.

Вып. 15. И. Р. Шафаревич. О решении уравнений высших степеней.

Вып. 16. В. Г. Шерватов. Гиперболические функции.

Вып. 17, В, Г. Болтянский. Что такое дифференцирование?

Вып. 18. Г. М. Миракьян. Прямой круговой цилиндр.

Вып. 19. Л. А. Люстерник. Кратчайшие линии.

Вып. 20, А. М. Лопшиц. Вычисление площадей ориентированных фигур.

Вып. 21. Л. И. Головина и И. М. Яглом. Индукция в геометрий

Вып. 22. В. Г. Болтянский. Равновеликие и равносоставленные фигуры.

Вып. 23. А. С. Смогоржевский. О геометрии Лобачевского.

Вып. 24. Б. И. Аргунов и Л. А. Скорняков. Конфигурационные теоремы.

Вып. 25. А. С. Смогоржевский. Линейка в геометрических построениях.

Вып. 26. Б. А. Трахтенброт. Алгоритмы и машинное решение задач

Вып. 27, В. А. Успенский. Некоторые приложения механики к математике.

Вып. 28. Н. А. Архангельский и Б. И. Зайцев. Автоматические цифровые машины.

Вып. 29, А. Н. Костовский. Геометрические построения одним циркулем.

Вып. 30, Г. Е. Шилов. Как строить графики.

Вып. 31. А. Г. Дорфман. Оптика конических сечений.

Вып. 32. Е. С. Вентцель. Элементы теории игр.

Вып. 33. А. С. Барсов. Что такое линейное программирование?

Вып. 34. Б. Е. Маргулис. Системы линейных уравнений.

Вып. 35. Н. Я. Виленкин. Метод последовательных приближений.

Вып. 36. В. Г. Болтянский. Огибающая.

Вып. 37. Г. Е. Шилов. Простая гамме (устройство музыкальной шкалы),

Вып 38. Ю- А. Шрейдер. Что такое расстояние?