Информатика_Ч1

Количество m пар точек (xi, yi), которые удовлетворяют условию

yi ≤ f(xi),

(6.20)

представляет собой отношение интеграла F к площади прямоугольника S.

Отсюда оценка интеграла методом Монте-Карло определяется выражением

Fn ≈F = ∫b	f (x)dx,	(6.21)
a

где Fn = H · (b – a) · m / n; m – количество точек, удовлетворяющих условию (5.20); n – общее количество сгенерированных пар точек (xi, yi), удовлетворяющих условию (6.19).

Другая разновидность метода Монте-Карло основывается на теореме, гласящей, что оценка определенного интеграла определяется следующей формулой:

F = ∫b	f (x)dx ≈ < f > ·(b-a),	(6.22)
a

где < f > – среднее значение функции f(x) на интервале (a, b).

Для вычисления < f > будем генерировать случайные числа xi, удовлетворяющие условию a ≤ xi ≤ b, и вычислять значения функции f(xi) в этих точках. Тогда оценка одномерного интеграла будет иметь вид

F = ∫b	f (x)dx ≈ Fn=< f > (b-a)= (b-a )·1 / n · ∑n	f (xi ), (6.23)
a	i =1

где xi – случайные числа; n – число испытаний.

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

Монте-Карло. Понятно, что чем больше случайных точек мы сгенерируем, тем точнее будет оценка интеграла, причем можно показать, что точное значение интеграла F лежит в некотором интервале с центром в точке Fn:

F (Fn – σn, Fn+ σn).
Здесь σn = σ / n,
где σ – дисперсия; n – число испытаний.
Дисперсия σ определяется по формулам:
σ2 = < f 2> – < f >2;	(6.24)

101

< f > = 1 / n∑n		f (xi ) ;	(6.24а)
i =1
< f > 2 = 1 / n∑n	( f (xi ))2 .		(6.24б)
i =1

Вычисление многомерных интегралов

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

Простейший метод оценки многомерных интегралов заключается в сведении этих интегралов к произведению одномерных интегралов.

Рассмотрим двумерный интеграл вида

x * y *
2	2
F = ∫	∫ f (x, y)dydx,	(6.25)
x * y *
1	1

где пределы y1* и y2*, вообще говоря, являются функциями от x:

y1*= y1*(x), y2*= y2*(x).

Определим функцию g(x) как внутренний интеграл по y:

y *
2
g(x) = ∫ f (x, y)dy.	(6.26)
y *
1
Запишем исходный интеграл в виде
x *
2
F = ∫ g(x)dx.	(6.27)

x1*

102

Тогда алгоритм вычисления двухмерного интеграла выглядит сле-

дующим образом:
1) разбиваем интервал (x	*, x *) на n малых отрезков x, а интервал
1	2
(y1*, y2*) на m отрезков y;

2)для текущего xi = xi-1 + x вычисляем y1*(xi) и y2*(xi);

3)вычисляем g(xi):

y2*	m −1
g(xi ) = ∫ f (x, y)dy ≈ ∑f (xi , y) y;		(6.28)
y *	j =0
1
4) вычисляем Fn:
	n−1
Fn	=∑g(xi ) x.	(6.29)

i =1

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

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

Задание

Вычислите интеграл из предыдущего задания методом МонтеКарло.

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

ЭВМ в первую очередь предназначены для решения вычислительных задач. Вычислительные задачи можно решать, используя:

–специальные математические пакеты;

–программы, написанные на каком-либо алгоритмическом языке в конкретной системе программирования.

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

103

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

Примеры математических пакетов:

EUREKA, STATGRAPH, MATHEMATICA, MATHLAB, MATHCAD.

Системы программирования включают три основные программы:

–текстовый редактор для набора текста программы;

–транслятор, переводящий исходный текст в машинный код;

–редактор связей.

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

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

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

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

104

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

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

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

6.6. Точность компьютерного эксперимента

Погрешности компьютерного эксперимента

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

1. Переход от объекта к математической модели.

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

2. Переход от математической модели к численному методу. При переходе от математической модели к численному методу

возникают погрешности, называемые погрешностями метода. Они

105

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

Обычно построение численного метода для заданной математической модели разбивается на два этапа:

1)формулировка дискретной задачи;

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

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

3. Переход от вычислительного алгоритма к решению задачи на ЭВМ.

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

ктому, что, во-первых, существуют минимальное и максимальное

числа Ммин и Ммакс; во-вторых, числа в диапазоне (Ммин, Ммакс) представлены в ЭВМ не все, а лишь некоторые. В результате этого при

вводе некоторого числа а это число заменяется на его округленное значение а*, ближайшее к а, которое представлено в ЭВМ. Величину | а – а* | / | а | будем называть погрешностью округления, или вычислительной погрешностью.

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

Вычислительный алгоритм называют устойчивым, если в процессе его работы погрешности возрастают незначительно, и неустойчи-

106

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

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

–погрешности модели;

–погрешности метода;

–вычислительные погрешности.

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

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

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

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

Одной и той же математической задаче можно поставить в соответствие множество различных дискретных моделей. Однако далеко не все они пригодны для практической реализации на ЭВМ.

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

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

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

107

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

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

6.7. Пример моделирования физической системы

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

dT

=−r (T −T ),

(6.30)

dt	S

где T – температура тела; TS – температура окружающей среды; r – коэффициент пропорциональности, зависящий от механизма теплопередачи, площади тела и тепловых свойств самого тела. Знак минус в правой части уравнения означает, что температура нагретого тела может только убывать, если T >TS .

Данное уравнение представляет собой дифференциальное уравнение первого порядка. Типичным методом решения таких уравнений является метод Эйлера. Запишем уравнения дискретной модели:

108

ti = ti-1 + t,
Ti = Ti-1 – r(Ti-1 – TS)Δt, i = 1, 2...m.	(6.31)

Составим алгоритм решения задачи. Зафиксируем алгоритм на языке блок-схем (рис. 34).

Начало

Ввод t 0, tk, dt1, dt2,

Temp_0, Temp_S, r

N:=(tk-t0)/dt1

M:=dt1/dt2

t:=t0

Temp:=Temp_0

I =1,N

Конец

Печать

T,Temp

K =1, M

t:=t + dt2

Temp:=Temp – r*(Temp -Temp_S)*dt2

Рис. 34. Блок-схема алгоритма

Пояснения к блок-схеме

На блок-схеме буквой t обозначается переменная, относящаяся к времени; 0, tk – начальный и конечный моменты времени расчетов; dt1, dt2

– период расчетов (т.е. интервал времени, через который выдается текущее значение переменных) и параметр дискретизации соответствен-

109

но; N – количество точек расчетов; M – количество итераций метода Эйлера; переменные Temp, Temp_0, Temp_S – текущая температура, начальная температура и температура окружающей среды соответственно.

Задание 1

1.Разработайте по данному алгоритму программу на каком-либо алгоритмическом языке.

2.Проведите экспериментальное измерение температуры нагретого тела (например, жидкости, помещенной в сосуд) в разные моменты времени.

3.Задавая различные значения коэффициента r в программе, подберите такое его значение, при котором ошибка расчета не превышает 10%.

4.Сделайте расчет в промежуточных точках (т.е. в точках, в которых не измерялась температура) и сравните с экспериментальными значениями.

5.Варьируя параметр дискретизации (шаг сетки) Δt, исследуйте, как влияет его значение на точность расчетов.

Задание 2

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

Задание 3

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

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

Задание 4

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

6.8.Заключение

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

110