Материал: Имитационное и статистическое моделирование — копия

при этом никак не зависит от числа N элементов в системе, в то время как при аналитическом расчёте она растёт как 2N.

Формула (1.57) раскрывает, однако, специфическую проблему непосредственного статистического моделирования, состоящую в больших затратах компьютерного времени, необходимых для расчёта высоконадёжных структур. При малой вероятности отказа Q, которая на практике может достигать значений Q ≈ 10–5–10–15, число опытов n, как видно из (1.57), становится чрезмерно большим.

5.2.5. Аналитико-статистические методы моделирования

Многократное, достигающее нескольких порядков, сокращение затрат времени на моделирование высоконадёжных структурно сложных систем достигается путём эффективного использования в статистическом эксперименте известных общих законов теории вероятностей и математической статистики. Задача моделирования преобразуется в аналитико-статистических методах таким образом, что среднее значение оценки не изменяется, но резко снижается её дисперсия. Поэтому аналитико-статистические методы моделирования часто называют также методами понижения дисперсии [6].

При моделировании надёжности систем в терминах классической задачи надёжности наиболее часто используют метод взвешивания (метод существенной выборки), метод расслоения (метод стратифицированной выборки) или их комбинированные варианты. Эти методы достаточно подробно излагаются в [16].

5.2.6. Другие модели надёжности

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

Для изучения аналитических методов расчёта надёжности рекомендуются книги [27–29]. Методы имитационного моделирования и аналитико-статисти- ческие методы разрабатываются в [30]. Здесь исследуются модели достаточно общего вида, в которых комплексно представлены как аспекты отказов и восстановлений элементов, так и аспекты производительности восстанавливающих систем (ремонтных групп). Соответствующие математические модели органично сочетают подходы теории надёжности и теории массового обслуживания. В книге [31] для моделирования надёжности систем используется мощный язык переключательных процессов (ПП) на непрерывном времени и уравнений динамики ПП, включающих, наряду с логическими операторами, различного рода операторы запаздывания.

5.3. Предел Бремермана – Эшби

Принцип неопределенности Гейзенберга указывает на естественные пределы микроминиатюризации устройств, предназначенных для обработки тех-

36

нической информации. Ошибка в измерении количества движения физической частицы, то есть импульса, и погрешность измерения ее координаты связаны постоянной Планка так, что любые попытки повысить точность измерения импульса приводят к росту погрешности определения координаты, и наоборот. Учитывая конечную скорость передачи информации в пространстве – скорость света, и точные пределы пропускной способности каналов с помехами, установленные Шенноном, можно вычислить предел скорости, достижимой техническими средствами обработки информации. Этот предел называется пределом Бремермана или пределом Бремермана – Эшби и составляет приблизительно 1047 бит/г в секунду. Самый совершенный компьютер не может выполнять в одном грамме своего вещества более чем 1047 битовых операций в секунду.

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

Предел Бремермана – Эшби можно переформулировать и в виде ограничения объёма технической информации, который может быть обработан в принципе. Если предположить, что всё вещество земного шара мы сумеем превратить в совершенный компьютер с параллельной обработкой информации, то за время, равное сегодняшнему возрасту Земли, такой компьютер смог бы выполнить не более 1097 битовых операций. Учитывая то, при каких предположениях получено это число, можно обоснованно утверждать, что всякая задача, требующая выполнения большего числа битовых операций (например, просто записи или чтения такого количества бит), технически нереализуема.

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

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

гии с приведенной выше табл. 1.2, составит 2N, где N = 20×20 = 400. Таким образом, общее число исходов составляет здесь 2N = 2400 ≈ 10 0,3×400 = 10120, и оно

значительно превышает предел Бремермана – Эшби. Следовательно, рассмот-

37

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

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

Преимущества статистического моделирования сложных технических структур рассмотрим на примере исследования явления перколяции (протекания).

5.4. Модели теории протекания

5.4.1. Статистическое моделирование матрицы Эшби

Прежде чем рассматривать модели перколяции, выполним несколько экспериментов с матрицей Эшби.

Пример 1 4 . В ячейку A1 на чистом листе Ms Excel введите число 0,675. Это число будем использовать как вероятность p проводящего состояния (включения) элементов матрицы Эшби. Введите в ячейки любого свободного диапазона, имеющего размер 20 строк на 20 столбцов, формулу =ЕСЛИ(СЛЧИС()<$A$1;1;0). Сделайте ширину ячеек этого диапазона равной их высоте и примените к ним меню Формат/Условное форматирование, чтобы результат 0 выводился белым цветом на белом фоне, а 1 – чёрным на чёрном. Тогда включённые клетки матрицы будут изображаться в виде чёрных квадратиков. С помощью меню Сервис/Параметры на вкладке Вид отключите опцию сетка. Обрамите границы диапазона рамкой. Нажимая ключ F9, сгенерируйте и рассмотрите несколько реализаций построенной матрицы Эшби. На рис. 1.10 показаны полученные таким образом следующие одна за другой подряд четыре реализации. Во всех четырёх имеется путь из чёрных клеточек, соединяющий боковые границы матрицы. Напомним, что смежные клетки по диагонали не соединяются.

Рис. 1.10. Реализации матрицы Эшби при p = 0,675

Если заменить значение вероятности включения элемента в ячейке A1 на 0,525, то получаются реализации матрицы, в которых связь между её боковыми границами, как правило, отсутствует (рис. 1.11).

38

Рис. 1.11. Реализации матрицы Эшби при p = 0,525

Вблизи значения p = 0,6 результаты экспериментов начинают колебаться: связь то присутствует, то нет. При удалении от этого значения результат эксперимента становится предсказуемым всё более однозначно. Поэтому возникает предположение, что значение pкрит ≈ 0,6 представляет собой некое критическое, пороговое значение вероятности включения элемента, которое достаточно жёстко определяет свойства проводимости матрицы в целом.

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

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

5.4.2. Статистическое моделирование решёток Бернулли

При решении задач физики решёток рассматривается так называемая «перколяция сквозь Бернуллиевы решётки» и используется понятие контактного кластера. Приведём пояснение этих терминов, используя следующую цитату из [25, с. 184]. «Простейшей задачей о перколяции … является перколяция по связям на квадратной решётке. Для упрощения картины представим себе большую квадратную решётку, составленную из двух видов стержней: одни сделаны из изолирующего винила, другие – из электропроводной меди. Такая решётка может считаться решёткой Бернулли, если каждый стержень выбран совершенно случайно, независимо от других стержней, причём вероятность выбора проводящего стержня равна p. Наибольшие скопления связанных между собой медных или виниловых стержней называются соответственно медными или виниловыми кластерами. Если решётка содержит хотя бы одну непрерывную цепочку медных стержней, электрический ток сможет пройти всю решётку насквозь, от одного края до другого. В таких случаях говорят, что решётка перколирует. (От латинского per «сквозь» и colare «течь».) Все стержни, нахо-

39

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

… Наиболее замечательная находка Хаммерсли имеет отношение к особой роли некоторой пороговой вероятности или, как он её назвал, критической вероятности pкрит. Эта величина появляется на сцене, когда размер решётки Бернулли (измеряемый числом стержней) стремится к бесконечности. Оказывается, когда p > pкрит, вероятность существования перколяционного кластера возрастает с размером решётки и стремится к единице. Когда же p < pкрит, вероятность перколяции устремляется к нулю.

Поскольку в случае перколяции по связям на квадратных решётках дело обстоит таким образом, что либо медь, либо винил должны перколировать,

то pкрит = 1/2».

Пример 1 5 . Роль критической вероятности pкрит = 1/2 в перколяции сквозь Бернуллиевы решётки можно увидеть в экспериментах уже с достаточно небольшими решётками. Заметим, что предельные теоремы не указывают на размеры решёток, при которых эти теоремы могут использоваться на практике. Статистическое моделирование позволяет восполнять подобные недостатки теории.

Откройте чистый лист Ms Excel, выделите его и сделайте ширину столбцов равной высоте. Выделите диапазон из 10×10 клеток и скопируйте во все его ячейки одну формулу =СЛЧИС(). Сначала для всего диапазона с помощью меню Формат/Ячейки… на вкладке Шрифт задайте белый цвет шрифта, чтобы

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

Условие 1 значение между 0,36 и 0,6 (далее кнопка Формат… /вкладка Шрифт), цвет белый (далее вкладка Граница), значок граница снизу.

Условие 2 значение между 0,6 и 0,84 (далее кнопка Формат… /вкладка Шрифт), цвет белый (далее вкладка Граница), значок граница справа.

Условие 3 значение между 0,84 и 1 (далее кнопка Формат… /вкладка

Шрифт), цвет белый (далее вкладка Граница), значок граница снизу и справа.

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

Поскольку случайные числа в ячейке распределены равномерно на интервале (0, 1), то с вероятностью 0,6 – 0,36 = 0,24 (по условию 1) в ячейке появится только линия внизу. Аналогично с вероятностью 0,84 – 0,6 = 0,24 (условие 2) появится только линия справа, с вероятностью 1 – 0,84 = 0,16 (условие 3) появятся обе линии, и с вероятностью 0,36 – 0 = 0,36 (пропущенный

вусловиях случай, определяемый заданным ранее безусловным форматом) не будет выведено ни одной линии. Эти вероятности точно соответствуют вероятностям соответствующих событий в решётке при p = 0,4. Действительно, вероятность непоявления ни одной линии из двух есть (1 – p)(1 – p),

40