Хамухин А.А. Введение в информатику для инженеров нефтегазового дела:

Подождите немного. Документ загружается.

iiiiiiii

YYYYYYYY +−+−=Δ−Δ=Δ

+++++ 1234

464 . (4.35)

И так далее.

Формула численного дифференцирования в общем виде

⎟

⎠

⎞

⎜

⎝

⎛

−Δ+Δ−Δ

⎥

⎦

⎤

⎢

⎣

⎡

Δ+

= ...

)(

)1ln(

. (4.36)

Таким образом, первая и вторая производная будут иметь вид:

⎟

⎠

⎞

⎜

⎝

⎛

−Δ+Δ−Δ

== ...

)(

32''

iiiii

YYY

XYY ; (4.37)

()

⎟

⎠

⎞

⎜

⎝

⎛

−Δ−Δ+Δ−Δ

== ...

111

)(

5432

''''

iiiiii

YYYY

XYY . (4.38)

На практике часто используются явные трехточечные формулы численного

дифференцирования:

()

RYYY

Y +−+−

+−− 101

;

()

RYY

Y ++−

+− 11

; (4.39)

()

RYYY

Y ++−

+−+ 101

где

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

численного дифференцирования, ее можно оценить по формуле для крайних точек:

()

'''

(4.40)

и для центральной точки

()

'''

. (4.41)

Результат численного дифференцирования сильно зависит от правильного

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

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

измерения всегда связаны с дополнительными затратами, поэтому шаг измерения

необходимо уменьшать только в том случае, если результат численного

131

дифференцирования значительно изменяется. Пример правильного и неправильного

выбора точек для численного дифференцирования приведен на рисунках 4.7, а,б.

1−

Рис. 4.7. Пример выборки точек на графике для численного дифференцирования: а –

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

132

4.7.2. Метод последовательных приближений

Метод последовательных приближений (итераций) базируется на известном в

математике (теория множеств) принципе сжатых отображений. Этот принцип

определяет так называемый оператор сжатия, для которого выполняется условие:

1212

)()( xxaxFxF −≤−

, . (4.42)

)1,0(⊂a

Из этого определения следует теорема, согласно которой в замкнутом

множестве для такого оператора сжатия существует неподвижная точка и она

единственная.

Эта неподвижная точка, в приложении к численным методам расчета, и есть

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

дает только приближенное решение с некоторой погрешностью, которая

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

Но решение приближается не всегда, поэтому существуют понятия

сходимость,

скорость сходимости, условия сходимости.

Сходимость – это свойство алгоритма обеспечивать приближение к точному

решению.

Условия сходимости – это математические соотношения величин,

участвующих в итерационном процессе, которые обеспечивают алгоритму свойство

сходимости.

Скорость сходимости – это степень приближения к точному решению на

каждой итерации, обычно она бывает линейной или квадратичной.

В зависимости от того или иного способа реализации метод последовательных

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

названия в специальной литературе. В качестве примеров рассмотрим некоторые из

них.

4.7.3. Метод дихотомии (деления пополам)

Существует теорема, которая гласит, что если непрерывная функция

f(x) на

концах отрезка [

a;b] имеет разные знаки, то она имеет корень (нулевое значение) на

этом отрезке. Поэтому первым этапом метода дихотомии является табуляция

исследуемой функции или разделение ее на такие отрезки, на концах которых ее

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

подвергается делению пополам. После разделения из двух вновь полученных

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

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

процедура повторяется до тех пор, пока значение функции на середине отрезка не

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

погрешностью метода дихотомии.

Формулы дихотомии представлены в математических выражениях (4.43), а сам

процесс демонстрируется на рис. 4.8.

133

{}

.0)(*)

(

;0)

(*)(

;0)(*)(:,

iiii

еслиправый

fXf

еслилевый

XfXfXX

Выбираем

(4.43)

i+1

f(X

)

f(X

i+1

)

Y=f(X)

⎟

⎠

⎞

⎜

⎝

⎛

1ii

Рис. 4.8. Пример последовательного приближения к точке пересечения функцией y=f(x) оси X

методом дихотомии

Модификация метода дихотомии – метод золотого сечения, который применяют

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

вычисляя только одно значение функции на каждой итерации. В результате двух

рассмотренных значений функции определяется интервал, который должен

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

точек и следующую точку, помещаемую симметрично ей. Точка делит интервал на

две части так, что

отношение целого к большей части равно отношению

большей части к меньшей, т. е. равно так называемому «золотому сечению».

4.7.4. Метод хорд-касательных (Ньютона)

Метод Ньютона (или метод касательных) имеет различные модификации,

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

нами в разделе 4.7.1. В общем виде задача формулируется следующим образом.

Действительный корень x уравнения f(x) = 0 вычисляется методом Ньютона по

итерационному уравнению:

134

k+1

= x

– f(x

)/f '(x

). (4.44)

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

выбрано так, что

|f(x

)f ''(x

)| < |f '(x

. (4.45)

Оценка погрешности k-го приближения производится по приближенной

формуле

|f(x

)f'(x

)| < e. (4.46)

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

каждой итерации, поэтому на практике чаще используют модификации этого

метода, которые заменяют производную ее разностными приближениями,

рассмотренными в разделе 4.7.1. Различные модификации этого метода наглядно

продемонстрированы на рис. 4.9 (а, б, в), а наиболее часто употребляемые формулы

хорд представлены в выражениях 4.47, 4.48.

Начальная

точка

Касательные

f(x)

Искомая точка

Контур месторождения

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

х: а – методом касательных

135

Начальные

точки

Хорды

f(x)

Искомая точка

Контур месторождения

Начальные

точки

Секущие

Искомая точка

Контур месторождения

f(x)

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

х: б – методом хорд, в – методом секущих

136

4.7.5. Метод Монте-Карло (случайного поиска)

Датой рождения метода Монте-Карло принято считать 1949 год, когда

американские ученые Н. Метрополис и С. Услам впервые опубликовали статью с

аналогичным названием «Метод Монте-Карло», в которой были изложены

принципы этого метода. Свое название метод получил в честь города Монте-Карло,

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

является рулетка – одно из простейших средств получения случайных чисел с

хорошим равномерным распределением, на использовании которых и основан этот

метод.

Метод Монте-Карло – это статистический метод, его используют при

вычислении сложных интегралов, решении систем алгебраических уравнений

высокого порядка, моделировании поведения элементарных частиц, в теориях

передачи информации и массового обслуживания, при исследовании сложных

систем (экономических, биологических и т. д.).

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

величину ξ, изменяющуюся по какому-то закону p(ξ). Как правило, случайную

величину выбирают таким образом, чтобы искомая в задаче величина A стремилась

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

AM ≈)(

. (4.49)

Таким образом, мы определяем искомую величину A лишь теоретически. А вот

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

случайной величины ξ объемом N элементов. В результате получают N вариант

случайной величины ξ

, для которых вычисляют их среднее арифметическое

(выборочное среднее), которое и принимают в качестве приближенного значения

(оценки) искомой величины A.

Для получения результата приемлемой точности по методу Монте-Карло

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

иногда так и называют:

метод статистических испытаний.

При поиске экстремумов, часто возникает проблема «ловушки локального

экстремума», которую многие алгоритмы не могут преодолеть. Метод Монте-Карло

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

множество модификаций этого метода, в частности, – метод «моделируемого

отжига», который применяют для поиска

глобальных экстремумов. Метод

«моделируемого отжига» строится на аналогии постепенного охлаждения нагретого

до температуры плавления металла, при которой атомы, первоначально

находящиеся в беспорядочном движении, последовательно занимают все более

низкоэнергетическое состояние, пока не будет достигнуто наименьшее из

возможных энергетических состояний – глобальный минимум.

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

количества вычислений целевой функции и, если она слишком сложна, то время

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

137

Глава 5. Дополнительные разделы информатики для

инженеров нефтегазового дела

5.1. Основы инженерной компьютерной графики

Для инженеров нефтегазового дела, как и для всех инженеров технических

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

помощью современных аппаратных и программных средств. Это и всевозможные

графики, диаграммы, гистограммы, и чертежи элементов конструкций, и

изображение трехмерных тел на плоскости, а для инженеров геологов и нефтяников

– добавляется работа с картографическим материалом.

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

изображения, которые оказывает значительное влияние на возможности его

редактирования, печати, на объем занимаемой памяти, а также возможности

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

возможности имеющегося программного обеспечения для ее обработки. Для более

подробного изучения практических основ работы с компьютерной графикой

рекомендуется курс «Основы работы в Photoshop»(ИНТУИТ).

5.1.1. Графические форматы

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

хранения изображения и подразделяются на: растровые, векторные и

комплексные.

Растровый формат характеризуется тем, что все изображение по вертикали и

горизонтали разбивается на достаточно мелкие прямоугольники – так называемые

элементы изображения, или пиксели (от английского pixel – picture element),

которые на мониторе отображаются в виде светящейся точки (с тем или иным

оттенком цвета). Минимально возможный размер пикселя называется зерном

экрана и измеряется в мм (или в дюймах), а максимально возможное количество

пикселей по горизонтали на количество пикселей по вертикали экрана называется

разрешающей способностью монитора.

В таком представлении графический файл содержит номера цветов (оттенков)

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

такой файл должен полностью располагаться в видеопамяти компьютера

(видеокарте). В черно-белых мониторах достаточно было одного бита для хранения

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

отражать на мониторе 256 цветов (если сам монитор это позволяет), уже требуется

выделять по 8 бит (2

=256)

для хранения каждого пикселя.

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

настоящее время современная аппаратура и операционные системы широко

используют до 32 бит на пиксель (Windows XP). Глубина цвета связана с

разрешающей способностью (и частотой обновления экрана) через объем

имеющейся видеопамяти в Вашем компьютере.

Средствами операционной системы можно увеличить один параметр за счет

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

138

выше виде, имеют формат BMP (Bit MaP). Все остальные графические форматы

используют те или иные методы сжатия данных, так как BMP-файлы требуют

слишком много памяти для хранения. Рассмотрим некоторые, наиболее часто

употребляемые.

PCX. Исторический графический формат эпохи «до Windows», использует метод

«сжатие без потерь»(ROB), не поддерживает глубину цвета выше 24 бит, не

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

графическими программами.

TIFF. Был разработан для одной из издательских систем, которая в настоящее

время уже не используется, а формат остался из-за множества полезных файлов,

хранящихся в нем. Благодаря своей совместимости с большинством

профессионального ПО для обработки изображений, формат TIFF очень удобен при

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

Маc и обратно).

GIF. Самый популярный графический формат эпохи появления Интернет.

Поддерживает только до 256 цветов, использует метод «сжатие без потерь»(LZW),

режим постепенного появления изображения (сначала каждая 8-я строка, затем

каждая 4-я и т.д.) благодаря чему файлы получались небольшие и быстро

открывались на web-страницах. Немаловажную роль сыграла возможность

анимации с помощью GIF-файлов. Однако фирма-разработчик CompuServe после

достигнутого успеха сделала этот формат коммерческим и его применение в

настоящее время без лицензии является нарушением законодательства.

PNG. Является плодом труда сообщества независимых программистов, как

ответная реакция на переход формата GIF в разряд коммерческих продуктов. Этот

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

алгоритм Deflate, в отличие от GIF или TIFF сжимает растровые изображения не

только по горизонтали, но и по вертикали, что обеспечивает более высокую степень

сжатия и поддерживает цветные фотографические изображения вплоть до 48-

битных.

Формат PNG позволяет создавать изображения с 256 уровнями прозрачности и

двумерную чересстрочную развертку (т.е. изображение проявляется постепенно не

только по строкам, но и по столбцам). Так как формат создавался для Интернета, в

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

разрешения, поэтому для хранения изображений, подлежащих печати, PNG плохо

подходит, для этих целей лучше подойдет PSD или TIFF. Зато он хорош для

публикации высококачественной растровой графики в Интернете.

JPEG (или JPG). Самый популярный формат для хранения фотографических

изображений использует метод «сжатия с потерей» данных, но эти «потери»

малозаметны для человеческого глаза. Степень сжатия JPEG и соответственно, –

потери информации, можно регулировать: он может быть настроен на

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

максимальное сжатие и наименьший размер файла.

Не рекомендуется использовать формат JPEG для хранения изображений,

подлежащих последующей обработке, так как при каждом сохранении документа в

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

характер. Наиболее целесообразно будет корректировать изображение в каком-

нибудь другом подходящем формате, например TIFF, и лишь по завершению всех

работ окончательная версия может быть сохранена в JPEG. Таким образом, можно

139

сохранить вполне приемлемое качество изображения при минимальном размере

итогового файла.

PSD. Является стандартным форматом пакета Adobe Photoshop и отличается от

большинства обычных растровых форматов возможностью хранения слоев (layers).

Он содержит много дополнительных переменных (не уступает TIFF по их

количеству) и сжимает изображения, используя алгоритм сжатия без потерь RLE

Packbits, иногда даже сильнее, чем PNG (в тех случаях, когда размеры файла

измеряются не в килобайтах, а в десятках или даже сотнях мегабайт). Формат

поддерживает глубины цвета, вплоть до 16 бит на канал (48-битные цветные и 16-

битные черно-белые), а также альфа-каналы, слои, контуры, прозрачность,

векторные надписи и т. п. Прекрасно подойдет для переноса или хранения

изображений, содержащих специфические, свойственные только Adobe Photoshop,

элементы.

В векторном формате изображение представляется в виде комбинации базовых

геометрических фигур – точек, отрезков прямых и кривых, окружностей,

прямоугольников и т. п. При этом для полного описания рисунка необходимо знать

вид и координаты каждой фигуры. Этот способ кодирования идеально подходит для

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

например, для технических чертежей. Векторные форматы менее стандартизованы,

чем растровые и в каждой профессиональной графической системе существует свой

векторный формат. Примеры обозначений векторных форматов: AI (Adobe

Illustrator), CDR (Corel Draw), DXF (AutoCAD), SVG (международный стандарт web-

консорциума), WMF (Windows).

Комплексные форматы – это тексто-графические форматы. Наиболее широко

известные из них – PDF и DjVu. Они предназначены для хранения текстовой

информации больших объемов (книг) в графическом виде с целью минимизации

объема требуемой для хранения памяти и борьбы с пиратским копированием и

плагиатом.

Следует отметить, что многие широко распространенные системы, связанные с

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

собственные графические форматы. Например: AUTOCAD (*.DXF), MapInfo

(MID/MIF), ArcInfo (*.SHP).

5.1.2. Аппаратно-программная поддержка компьютерной графики

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

комплексом характеристик, включающим в себя производительность процессора,

объем оперативной памяти, объем видеопамяти, тактовую частоту системной шины

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

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

Особо следует отметить появление в последнее время специальных аппаратных

средств для выполнения типовых математических операций над массивами

графических данных – графических ускорителей и графических процессоров. С их

помощью математические операции выполняются в несколько раз быстрее по

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

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

140