Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 44
Текст из файла (страница 44)
д. Отсутствующим буквам будут соответствовать почти нулевые «омпоненты Рассмотрим теперь камноненты столбцов (( и «', отвечающих второму сингулярному числу. Если сингулярные числа упорядочены, то зто будут и„з и о„з. Свяжем с каждой бунвой х точку двумерной плоскости, декартовыми коордйнатамн нагорай ивляются компоненты х этих векторов, т. е. точку (и„з, о, з) Поскольку компоненты находятся и интервале ! — 1, 1), мы получим 2б точек, расположенных в квадрате со стороной 2 и центром в начале координат.
Большинству букв будут соответствовать точки второго и четвертого квадрантов плоскости. Другими словами, будет лишь несколько букв, для которых соответствующие компоненты второго правого и второго левого сингулярных векторов имеют одинаковый знак.
Кроме того, ббльшая часть согласных должна быть в одном квадранте, а гласных — в другом. Эта связано с тем обстоятельством, что пары гласнаи-согласиая или согласная-гласная встречаются более часто. чем пары гласная-гласная или согласная-согласная. Будут и некоторые иснлючения. Например, букве Н обычно предшествует согласная, а именна Т, а сопровождает ее гласная. Букпа М чгсто сопровождается другой согласной В действительности подобные исключения могут намочь в распознавании таких букв в криптограмме. Интересно была бы использонать тексты и не на английском языке. Например, для немецкого языка так хорошо не получилось бы, потому что он содержит сравнительна много пар гласная-гласная или сагласная-согласная.
9.б Поеодообратнол На пишите пад про гра мчу 50ВЕО()Т1)(Е Р5ЕОРО (НМ, М, Н, А, ТОЕ, АРЕ()5, '««ОЕК), которая бы, исполь. уя 5НО, вычисляла эффективную псевдообратиую дли тыл-матрицы А. Сингулярные числа, меньшие, чем ТОЕ, должны рассматриваться как пренебрежимо малые, Проверьте подпрограмму на примере, уиазаннол< в этой главе, а также на других матрицах по своечу гыбору. Найдите пример, в котором изменение ТОЕ приводило бы к нескольким различным ре. зультатам.
Та часть вашей подпрограчмы, которая фактически формирует А т, может выглядеть так: 00 20 1=.1, Н 0020 2=1, М Т=-О. О 00 1О К=1, Н 1Г (510МА (К) . ОТ. Т01.) ч Т =Т+Ъ' (1, К) «О (.1, К)(510Л!А (К) 10 СОКТ! НОЕ АРШ5 (1, д) =Т 20 СОР)Т!)91)Е. Попытайтесь организовать вашу программу так, чтобы, помимо А и ЛРЕ05 требовалось как можно меньше дополнительной памяти. 9.7, ()сеодообратиая Доиажите, чта эффективная псеадообратная матрица удовлетворяет четы. рем условиям: ХАХ.=Х; АХ снмметрнчна; ХА симметрична; ); А ХА — А )! ~ т.
10. ВЫРАБОТКА СЛУЧАЙНЫХ ЧИСЕЛ И МЕТОДЫ МОНТЕ-КАРЛО Существует много задач, в которых естественным образом присутствует случайный элемент. К примеру, если вы хотите исследовать влияние числа мясников на качество обслуживания в мясном магазине, то вам придется каким-то способом моделировать непредсказуемость моментов входа посетителей в магазин. Другим примером являются случайные помехи.
Многие типы сбоев в коммуникационной системе моделируются лучше всего как случайные эффекты. Есть другие задачи, которые сами по себе не содержат элемента случайности, но где по тем или иным причинам полезно брать случайные выборки. Например, в проводимой раз в десять лет переписи населения Соединенных Штатов было бы слишком дорого, да и просто излишне предоставлять каждому лицу наиболее полный набор вопросов. Обычно такой полный набор оставляют лишь для выборки ! человек из 1О или 40, при этом выборка берется случайная, чтобы избежать какой-либо систематической ошибки. (Каждый десятый дом может оказаться на углу, и тем самым буду~ отобраны более зажиточные люди). Еще одна задача, где случайный выбор оказывается удивительно полезным,— это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов.
Обозначим область через 1с; обычно она определяется рядом неравенств. Предположим, что 1т' — подмножество и-мерного единичного куба К. Идея Монте-Карло состоит в том, чтобы случайным образом выбрать в К болыпое число Л' точек, которые с одинаковой вероятностью могут оказаться в любой части К. Затем подсчитывают число М точек, попавших в К, т. е. удовлетворяющих неравенствам, определяющим 1с. Тогда М/Дг есть оценка объема й'. Студенты, знакомые с бииомиальным распределением, знают, что дисперсия оценки довольно большая, так что ее точность невелика.
Все же выборка из 1О 000 точек обеспечит точность около 1 %, если только объем не 10.! РАВНОМЕРНО РАСПРЕДЕЛЕННЫЕ ЧИСЛА 261 слишком близок к 0 илн 1. Такой точности часто бывает достаточно, н добиться лучшего другими методами может оказаться очень трудно. Для любого из подобных приложений, связанных с машиной, необходимо вырабатывать большие последовательности чисел, ведущих себя как случайные выборки из заданного распределения. Имеются три класса методов для выработки таких случайных чисел. 1. Можно использовать случайный физический процесс, например момент эмитирования электрона горячим катодом, интерпретируемый как фаза в некотором временном цикле Такие эффекты легко получать, однако очень трудно добиться, чтобы связанные с ними результаты замеров времени не содержали систематической ошибки, чему приходится противодействовать другими методами.
В любом случае физический процесс, будучи случайным, невоспроизводим, и потому машинную программу, основанную на нем, отлаживать нелегко. 2. Можно вычислять случайные числа автономно от их последующего потребления программой; хранить их можно в виде файла на диске или ленте. Подход, основанный на этой идее, был широко распространен в не знавшую ЭВМ эпоху, когда было опубликовано несколько книг с таблнцамн случайных чисел. Остается открытым вопрос о том, как выработать файл из случайных чисел.
Если вы как програмэшст не заготовите своего собственного файла, то вполне вероятно, что имеющийся файл будет слишком эксплуатироваться. Одно из возможных решений состоит в том, чтобы начать использовать файл случайным образом, но это возвращает нас к проблеме, как вырабатывать случайную позицию в файле. В прошлом статистики изобрели изощренные методы пользования таблнпами случайных чисел. 3. Третий и наиболее распространенный метод заключается в применении алгоритма, вырабатывающего «случайные» числа, немедленно потребляемые машинной программой.
Числа выдаются лишь в случае надобности в нпх, и они вполне воспроизводимы, что важно при проверке программы. Поскольку такие числа генерируются алгоритмом, онн вовсе не случайные, и следовало бы называть их псевдослучабньтш. Тем не менее, данный подход, по-видимому, наиболее полезен, и в этих заметках будет обсуждаться только он, 10.1. Выработка равномерно распределенных чисел Методы, вырабатывающие случайные числа с тем иля иным распределением, обычно основаны на первоначальном получении случайного действительного числа„равномерно распределенно- Ш БЫРАБОТКА СЛУЧАЙНЫХ ЧИСЕЛ гз2 го на интервале 10,!1.
Такое число позднее преобразуется к другому распределению. Поскольку целочисленная арифметика изучена лучше, то начинают с получения целого числа, равномерно распределенного в некоторой области неотрицательных целых чисел; например, для Системы 360 эта область простирается от 0 до 2" — 1.Такое целое число можно преобразовать в число с плавающей точкой из 10,1). (Однако отказ от обращения и умножения привел бы к значительной экономии времени, идля многих целей случайные целые числа столь же полезны, как и случайные действительные.) Почти повсеместно используемый метод выработки псевдослучайных целых чисел состоит в выборе некоторой функции ), отображающей множество целых чисел в себя. Берем какое- нибудь х„н порождаем каждое следующее целое число посредством функции ХАе, — )(ХА). Поначалу функции !' выбирались как можно более сложные и трудно понимаемые: например, )(х) определялась как целое число, двоичное представление которого составляет средний 31 разряд 62-разрядного квадрата чпсла х.
Но отсутствие теории относительно ) приводило к катастрофическим последствиям. В методе середины квадрата, например, )(х) могла иногда, причем совершенно непредсказуемо, обратиться в нуль, и тогда все последующие хА были равны О. Поэтому уже довольно давно перешли к использованию функций, свойства которых известны вполне. Всякая последовательность целых чисел нз интервала (0,2'"' — 1) должна содержать повторения самое большое после 2" АЙ!0' элементов. Используя теорию чисел, можно выбрать такую функцию ~, для которой наперед будет известно, что ее период максимально возможный или близкий к максимальному. Зтим избегается преждевременное окончание или зацикливание последовательности. Дальнейшее использование теория чисел может более или менее предсказать характер последовательности, давая пользователю некоторую степень уверенности в том, что она будет достаточно хорошо моделировать случайную последовательность чисел.
Чаще всего сейчас применяют функцию ) вида ! (х) — ах -1- с (гп ог( т), где для 1-разрядных двоичных целых чисел пг обычно равно 2'. Здесь х„, а и с — сами целые числа из той же области. Некоторые выборы для а н с хороши, другие — нет. (Пример; очевидно, что выбор а=с —.-1 ужасен.) В книге Кнут (1969), с. 101 и 193, следующим образом подытожены теоретико-числовые ограничения на выбор а и с,: 1, х, может быть произвольно. Для проверки программы всзможно х,=-1; в дальнейшем в качестве х, можно брать цифровую 10.1.
РХВНОМЕРНО РХСПРЕДЕЛ!<ННЫЕ ЧНСЛЛ версию времени прогона программы, чтобы обеспечить различ- ные последовательности для различных прогонов. 2. Выбор а должен удовлетворять трем требованиям (для двоичных машин): а) а(пюг) 8)=5, б) т/100(а~т — )гт, в) двоичные знаки а не должны иметь очевидного шаблона. 3. В качестве с следует выбирать нечетное число, такое, что — —, — —, )х 3 0.21132. <л З 6 Нужно помнить, что наименее значимые двоичные цифры х„ будут «не очень случайными».
Г1оэтсму, если, например, вы хотите использовать число хь для случайного выбора одной нз 15 возможных ветвей, берите наиболее значимые разряды х,, а не наименее значимые. Наконец, для большей надежности полезно предварительно испытать случайные числа на какой-либо задаче с известным ответолг, схожей с реальным прилогкением. Мы запрограммировали простой датчик равномерно распределенных случайных чисел, следуя предложениям Кнута. Соответствующая подпрограмма, написанная на ФОРТРАНе, стандарт АМВ1, приведена в следующем параграфе. Поскольку подпрограмма составлялась так, чтобы быть относительно независимой от конкретной машины, то мы назвали ее 1)КАМЭ, что означает как 1)шуегза) КА!хРогп пшпЬег яепега1ог, так и Рп<Ь !оггп КА)х)Рош пшпЬег яепега1ог '), Г)КАК)Р вырабатывает последовательность целых чисел, да.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
