В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 6
Текст из файла (страница 6)
Но тогда для работы вычислительного алгоритма понадобится значительная память,где будет храниться такая таблица, причём и всей таблицы может оказаться недостаточно,если случайных величин для решения задачи нужно очень много.Можно также попробовать смоделировать случайные величины с помощью каких-то алгоритмов. Правда, тогда это будут уже не настоящие случайные числа, а так называемыепсевдослучайные, поскольку в подобных алгоритмах последующее число генерируется наоснове предыдущего (или предыдущих).
Наиболее распространенными в настоящее времяявляются линейный конгруэнтный метод и метод регистра сдвига с линейной обратной связью. В последнее время появились и часто используются метод Фибоначчи сзапаздываниями и так называемый «вихрь Мерсенна» (Mersenne Twister).6.5.Линейный конгруэнтный методОдин из простых способов получения псевдослучайных значений, в нём используются только целочисленные операции. Необходимо выбрать три натуральных числа-константы: (модуль), < (множитель), < (приращение) и первоначальное значение псевдослучайного числа 0 , тогда последующие значения псевдослучайных чисел получаются спомощью рекуррентной формулы:+1 = ( + ) Эта последовательность, конечно, периодична, поскольку может содержать не более чем различных значений, поэтому выбираются большие значения . Но если сомножитель и модуль подобраны «хорошо», то результирующая последовательность чисел будет статистически очень похожа на случайную последовательность элементов множества{0, 1, 2, ..., − 1}.«Правильный» выбор констант важен и для периода последовательности, поскольку даже взаимная простота значений не всегда может приводить к максимально возможномупериоду.
Тривиальные примеры: = 5, = 3, = 11; = 2, = 4, = 7 (проверьтесамостоятельно!):555555· 1· 8· 10· 9· 4+++++333333=====843534823 +111→8→10→9→4→1Видно, что при «плохом» выборе констант период последовательности может быть заметнокороче максимального. Кроме того, такой метод малопригоден для получения случайныхвекторов, разве что совсем малой размерности (не выше пяти).В 1960-х годах был распространён линейный конгруэнтный генератор псевдослучайных чиселпод названием RANDU. Он имел параметры = 65 539 (65 539 = 216 +3), = 0 и = 231 ; значение 0 выбиралось нечётным (скажем, равным 1).
Основания для выбора таких параметровбыли: умножение – много проще произвольного, остаток – тоже получается тривиально. Однако, оказалось, что использование его для получения случайных векторов размерности более2 проблематично: в трёхмерном пространстве все его значения располагаются всего лишь в15 параллельных плоскостях!276.6.Метод регистра сдвига (с линейной обратной связью)Основа алгоритма – логическая операция «Исключающее ИЛИ», производимая над некоторыми разрядами двоичного числа, представляющего текущее псевдослучайное значение. Результат её становится частью нового значения, а старое сдвигается на один разряд.Можно использовать для реализации метода программу или логическую схему, называемую регистром сдвига, дополненную схемой-вычислителем значения указанной логическойоперации над разрядами.
Максимальным значением периода при регистре из двоичных разрядов будет 2 − 1. Это обусловлено тем, что среди всех формируемых значенийотсутствует значение, представленное нулями во всех разрядах. Однако для получениямаксимально возможного периода надо знать, какие именно разряды регистра и в какомколичестве необходимо выбирать для формирования обратной связи. Два простых примерас трёхразрядным регистром:0 0 1 1 0⊕6.7.0 0 1 1 1 0 1 00 0 1 1 00 1 1 0 01 1 0 0 1⊕0 0 1 1 1 0 1 00 1 1 0 0 1 0 01 1 1 0 1 0 0 1Метод Фибоначчи с запаздываниямиЕсли скорость выполнения арифметических операций с вещественными числами сравнимасо скоростью целочисленных операций, то для получения псевдослучайных вещественныхзначений можно воспользоваться так называемым методом Фибоначчи с запаздываниями.Пусть далее обозначает вещественное число из диапазона [0, 1), генерируемое на -омшаге, а и – целые положительные числа (параметры метода).
Одна из возможныхреализаций предписывает такую процедуру получения очередного значения по значениям,сгенерированным ранее:{︃ =− − − ,− ≥ −− − − + 1, − < −Предполагается, что предыдущие {, } значений сохраняются, т.е., для работы необходим некоторый объём памяти, определяемый параметрами метода. Первоначальные значения для работы можно получить с помощью, например, линейного конгруэнтного генератора. Существуют некоторые (хорошо зарекомендовавшие себя) значения параметров и , которые можно использовать: (, ) = (17, 5), (55, 24), (97, 33). Чем больше значениеконстанты , тем выше размерность пространства, в котором сохраняется равномерность«расположения» случайных векторов, получаемых из генерируемых чисел.6.8.«Вихрь Мерсенна» (Mersenne Twister)Из современных генераторов псевдослучайных чисел широкое распространение также получил так называемый «вихрь Мерсенна» (Mersenne Twister, сокращённо – ), предложенный в 1997 году Мацумото и Нисимурой (Matsumoto, Nishimura).
Его достоинствамиявляются колоссальный период (219937 − 1), равномерное распределение в 623 измерениях (у линейного конгруэнтного метода – максимум в 5 измерениях), быстрая генерация128случайных чисел (в 2-3 раза быстрее, чем стандартные генераторы, использующие линейный конгруэнтный метод). Однако, существуют тесты, распознающие последовательность,порождаемую , как неслучайную. формирует последовательность из 624 32-битных слов (битовых векторов) , образующих всего 624 · 32 − 31 = 19937 бит состояния (в первом из слов используется лишь одинстарший бит) в соответствии с выражением:+624 = +397 ⊕ (( &0x80000000)|(+1 &0x7FFFFFFF)), = 0, 1, 2, . . .где – константная битовая матрица размером 32 × 32:⎛⎜⎜⎜⎜⎜⎜⎜⎝⎞1131 30...1· · · · · · 0⎟⎟⎟⎟⎟⎟⎟⎠и a = (31 , 30 , . .
. , 0 ) = 0x9908B0DF.На каждом шаге матрица умножается слева на вектор, образованный старшим битомслова и всеми битами – кроме старшего – слова +1 . Результат умножения вектораx на эту матрицу может быть записан ещё и так: x = x>>1, если младший бит x– нулевой, или x = (x>>1) ⊕ a – если младший бит x – единичный. Получающийсявектор с помощью поразрядной операции «Исключающее ИЛИ» комбинируется с вектором+397 , в результате чего образуется новый вектор последовательности +624 , участвующийв состоянии вместо вектора +1 – за исключением самого старшего его бита (см. далееиллюстрацию изменения состояния ).Для инициализации надо указать его начальное состояние: 0 , 1 , . .
. , 623 (для 0 достаточно одного старшего бита), для чего используется такое правило: 0 ← 19650218, ←((−1 ⊕ (−1 >>30)) + ) × 1812433253 (1 ≤ ≤ 623); переполнения за пределы 32 двоичныхразрядов в арифметических операциях игнорируются. Выходная последовательность начинается с +624 , т.е., начальное состояние полностью пропускается.wi+1wi+2wi+397wi+624⊕AРис. 6: Mersenne Twister: изменение состояния297.Решение дифференциальных уравненийПоскольку многие процессы в физике описываются дифференциальными уравнениями,необходимы численные методы решения таких уравнений.
Мы рассматриваем здесь методырешения так называемой задачи Коши для обыкновенного дифференциального уравненияпервого порядка (дифференциальное уравнение + начальное условие).7.1.Обыкновенные дифференциальные уравнения (ОДУ)Обыкновенное дифференциальное уравнениеаргумента – это соотношение вида(ОДУ) -го порядка для функции () (, , ′ , ′′ , . . . , () ) = 0,где – заданная функция своих аргументов. Слово «дифференциальное» подчёркиваеттот факт, что в соотношение входят и производные функции , а не только сами и ,слово «обыкновенное» говорит о том, что искомая функция зависит только от одногоаргумента.Решить ОДУ – значит найти все функции (), превращающие уравнение в тождество.Семейство таких функций называется общим решением ОДУ, оно образуется с помощью некоторого числа произвольных констант (их число совпадает с порядком уравнения).Иногда его называют также общим интегралом дифференциального уравнения.Конкретная прикладная задача может приводить к дифференциальному уравнению любогопорядка.
Но обыкновенное дифференциальное уравнение, скажем, -го порядка (здесь и далеепредполагается, что оно разрешимо относительно старшей производной, и такое разрешениепроизведено):() () = (, , ′ , ′′ , . . . , (−1) )можно свести к эквивалентной системе уравнений первого порядка с помощью замен () () ≡ (). Аналогично, произвольную систему дифференциальных уравнений любого порядкаможно заменить эквивалентной системой уравнений первого порядка, но с бо льшим количеством уравнений.Различают три основных типа задач для обыкновенных дифференциальных уравнений:задачи Коши, краевые задачи, задачи на собственные значения. Далее мы рассматриваемтолько задачу Коши, т.е., задачу с начальными условиями (в случае уравнения первогопорядка – с начальным условием).Общее ОДУ первого порядка имеет вид (, , ′ ) =0; если его удаётся разрешить относительно производной, то оно может быть записано так: ′ = (, ).Геометрически общее решение ОДУ первого порядкапредставляет собой семейство кривых, не имеющихобщих точек и отличающихся друг от друга некоторой константой .
Эти кривые называются интегральными кривыми для данного уравнения.Их очевидное свойство: в каждой точке тангенс угла наклона касательной к кривой в этой точке равензначению правой части уравнения в этой точке (т.е.,решаемое уравнение задаётся в плоскости полем30направлений касательных к интегральным кривым). Одна интегральная кривая определяет частное решение.7.2.Задача Коши (задача с начальными условиями)Для ОДУ первого порядка формулируется так:{︃ ′ = (, ), ∈ [0 , ](0 ) = 0Известно, что если (, ) непрерывна вместе со своей частной производной по в некоторой области, то задача Коши имеет в этой области единственное решение.С вычислительной точки зрения можно сказать, что имеется неизвестная функция =(), про которую известно, чему равна её первая производная ′ = (, ) (вообще говоря,она зависит как от самой функции, так и от её аргумента), и в начальной точке 0 значениефункции тоже известно: (0 ) = 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
