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

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

Пример

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

Осталось сделать еще один шаг – заменить физическое моделирование исследованиями математической модели.

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

Особенности математических моделей

1.Математическая модель – это уравнения, которые описывают интересующие нас объект, явление или процесс.

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

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

91

Пример

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

Естественно было бы переложить подобные расчеты на вычислительные устройства – ЭВМ.

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

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

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

Объект	Математи-	Метод	Программа	Расчет
	ческая	решения		на ЭВМ
	модель
				Анализ
				результатов

Корректировка результатов

Рис. 27. Схема компьютерного эксперимента

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

92

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

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

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

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

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

Таблица 2

Сравнение лабораторного и компьютерного экспериментов

Лабораторный эксперимент	Компьютерный эксперимент
Образец (объект)	Модель
Физический прибор	Программа для ЭВМ + ЭВМ
Калибровка измерительного прибора	Тестирование программы
Измерение	Расчет
Анализ результатов	Анализ результатов

93

6.4.Вычислительный алгоритм. Введение в численные методы

Для реализации конкретной математической модели необходимо составить алгоритм ее решения на ЭВМ.

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

Напомним основные свойства алгоритма:

1)дискретность – алгоритм должен состоять из отдельных, конечных во времени шагов;

2)однозначность – каждый шаг алгоритма должен быть однозначно понимаем;

3)конечность – алгоритм должен приводить к решению задачи за конечный промежуток времени;

4)массовость – алгоритм должен формулироваться в общем виде,

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

В компьютерном моделировании под методом (алгоритмом) будем понимать:

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

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

Что означает термин «дискретная задача»? Это значит, что исходная математическая модель должна быть сформулирована в виде, пригодном для решения на ЭВМ. Например: если исходная задача сформулирована в виде дифференциального уравнения или системы дифференциальных уравнений, то для численного решения на ЭВМ ее необходимо заменить системой линейных или разностных алгебраических уравнений. В этом случае говорят, что проведена дискретизация исходной математической задачи.

Формулировкой дискретных задач и составлением вычислительных задач занимается раздел прикладной математики, называемый «Численные методы».

Базовые понятия численных методов

В численных методах функции непрерывного аргумента заменяются функциями целочисленного аргумента – сеточными функци-

94

ями. Сеточную функцию можно рассматривать как функцию целочисленного аргумента (рис. 28).

y = y(x)	y = y(xi) = y(i) = yi i = 1,2…n
y	y

х	хn
х1

Рис. 28. Графики непрерывной и сеточной функции

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

yi = yi+1 – yi (правая разность);		(6.4)
yi = yi – yi-1 (левая разность).		(6.5)
Предположим, что надо вычислить сумму значений
yn = x1 + x2 +…+ xn = ∑n	xi .	(6.6)
i =1
Тогда вычисления организуются следующим образом.

Задается начальное значение y0 = 0, а затем последовательно, начиная с i = 1, находятся числа yi, связанные реккурентным соотно-

шением
yi = yi-1 + xi, i = 1, 2, …n.	(6.7)
Для вычисления произведения вида

n

yn = x1 · x2 · … · xn = ∏xi (6.8)

i =1

достаточно задать начальное значение у0=1 и воспользоваться реккурентным соотношением

yi = yi-1 · xi, i =1, 2, …n.

(6.9)

95

Уравнения (6.7) и (6.9) являются частным случаем линейного разностного уравнения первого порядка:

уi = qi · yi-1 + fi , i = 1, 2, …n,

(6.10)

где qi, fi – заданные числа, а уi – искомые значения.

Для данного уравнения рассматривается задача нахождения всех уi при заданном значении у0 . Ясно, что решение этой задачи существует и оно единственно.

Численное решение линейных дифференциальных уравнений

Рассмотрим уравнение вида

dy(x) / dx = g(x),

(6.11)

где y(x) – неизвестная функция; g(x) – заданная функция. Уравнение вида (6.11) называют дифференциальным уравнени-

ем первого порядка, поскольку в него входит только первая производная неизвестной функции y = y(x).

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

Типичный метод численного решения дифференциальных уравнений включает в себя преобразование дифференциального уравнения в алгебраическое разностное. Пусть нам необходимо найти решение уравнения (6.11) в точке x = xk. Положим, что при x = x0 функция y(x) принимает значение y0. Разобьем интервал (x0, xk) на n интервалов шириной Δx. Поскольку уравнение (6.11) описывает скорость изменения функции y(x) в точке x0, то можно найти приближенное значение функции y в близлежащей точке x1 = x0 + x, если x мало. Будем считать в первом приближении, что функция g(x) постоянна на отрезке (x0, x1). В этом случае приближенное значение y(x1) определяется выражением

y(x1) = y1 ≈ y(x0) + y = y(x0) + g(x0) · x.

Определив y1, мы можем повторить эту процедуру и найти значение y в точке x2 = x1 + x:

y(x2) = y2 ≈ y(x1) + y = y(x1) + g(x1) ·Δx.

96

Очевидным образом это правило можно обобщить и вычислить значение функции в любой точке xi = xi-1+ x, в том числе в интересующей нас точке xn = xk,, по итерационной формуле

y(xi) = yi ≈ y(xi–1) + y = y(xi–1) + g(xi–1) · x, i = 1, 2 …n. (6.12)

Итак, выполнив n шагов вычислений по формуле (6.12), мы получаем решение уравнения (6.11).

Задание

Используя метод Эйлера, решите численно дифференциальное уравнение dy/dx=2x в точке x=2 c начальными условиями x0=1, y0=1. Выберите шаг x = 0,1. Вычислив приближенное решение y(x), сравните его с точным решением уравнения и вычислите относительную ошибку.

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

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

F = ∫b	f (x)dx .	(6.13)
a

Для большинства подынтегральных функций f(x) вычислить аналитически данный интеграл не удается, и поэтому интеграл (6.13) нужно вычислять численно.

Классический метод численного интегрирования основан на геометрической интерпретации интеграла (6.13) как площади под графиком функции f(x) в пределах от x = a до x = b (рис. 29).

Y

y = f(x)

a

b

X

Рис. 29. Геометрический смысл определенного интеграла.

97

Делим отрезок (a, b) на n равных отрезков Δx:
x = (b – a) / n.	(6.14)
Тогда x0 = a, xi = xi + iΔx, xк = xn.	(6.15)

Простейшей оценкой площади под кривой f(x) служит сумма площадей прямоугольников (рис. 30).

Y

y = f(x)

x0 x0 + dx

X

Рис. 30. Оценка площади под кривой методом прямоугольников

Вметоде прямоугольников значение функции f(x) вычисляется

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

n−1
Fn =∑f (xi ) x .	(6.16)

i =0

Модификацией метода прямоугольников является вычисление f(x) в средней точке каждого отрезка:

n−1
Fn =∑f (xi + x / 2) x .	(6.17)

i =0

Другим приближением является формула трапеций, в которой интеграл оценивается вычислением площади трапеции со сторонами, равными значениям f(x) в начале и конце отрезка (рис. 31).

S трапеции = (f(x0)+ f(x0+dx))/2.

98

Y

y = f(x)

x0 x0 + dx X

Рис. 31. Оценка интеграла методом трапеции

Оценка интеграла дается выражением

Fn =[	n−1	] x .
	f (x0 ) / 2 +∑f (xi ) + f (xn )		(6.18)

i =0

Очевидно, что точность вычисления интегралов вышеописанными методами определяется шагом сетки Δx: чем меньше его величина, тем с большей точностью мы вычисляем интеграл.

Задание

Вычислите любым из описанных выше методов интеграл F = ∫2 xdx

1

и сравните приближенный ответ с точным значением интеграла.

Метод Монте Карло

Метод Монте-Карло является весьма популярным методом в математическом моделировании физических задач и основывается на проведении серии статистических испытаний. Метод Монте-Карло является самостоятельным методом и не относится к числу методов раздела математики, называемого «Численные методы».

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

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

99

в озеро. Если n – количество брошенных камней, а m – количество камней, попавших в озеро, то площадь озера будет определяться формулой Sозера = S·m /n (рис. 32).

S

озеро

Рис. 32. Вычисление площади озера

Рассмотрим данный метод применительно к вычислению опре-

деленного интеграла (рис. 33).
S = H(b – a)		y	S
F = ∫b		H
	f (x)dx
a
			y = f(x)
		a	b x

Рис. 33.Оценка интеграла методом Монте-Карло

Площадь прямоугольника, ограниченного линиями y = H, y = 0, x = a, x = b, равна S. Площадь под кривой y = f(x) на интервале [a, b] равна F.

Будем генерировать n пар случайных чисел xi, yi (i = 1, 2, …n), таких, что:

A ≤ xi ≤ b, 0 ≤ yi ≤ H.

(6.19)

100