Category Archives: Дискретная математика

1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ

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

rotE = 0,

?
divD = ?,

?    ?
D = ?E.
безвихревой характер поля позволяет ввести вспомогательную
функцию – скалярный электрический потенциал    u, которая удовлетворяет либо уравнению пуассона в области с зарядами
u    ?,

D = – ?
либо уравнению лапласа в области, свободной от зарядов

?u = 0.

?

(1.1)

напряженность электрического поля E  находится из выражения
E?= -gradu.    (1.2)
полученное решение будет единственным, если оно удовлетворяет граничным и краевым условиям.
граничные условия определяют поведение составляющих векторов поля на границе раздела сред, где значения параметров меняются скачком.

3

в  электростатическом поле на границе раздела сред при отсутствии поверхностных зарядов непрерывны касательные составляющие вектора    E  и нормальные составляющие вектора D?, т. е.

Et1  =  Et2,Dn1  = Dn2.

(1.3)

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

Et1  =  Et2,Dn1 – Dn2  = s.

(1.4)

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

?
divB =?0,

?
B = ?H.

?

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

?
H = -graduм.
граничные условия на поверхности раздела сред с различными
магнитными проницаемостями состоят в том, что
Ht1  =  Ht2,Bn1  =  Bn2,
где Bn1,Bn2 – нормальные составляющие вектора магнитной индукции.
если на такой поверхности протекают токи с поверхностной
плотностью    K?,  то граничные условия изменяются и принимают
следующий вид:
Ht1 – Ht2  =  Kn, Bn1  =  Bn2.
4

1.3. Операции векторного анализа
в ортогональных криволинейных координатах
произвольная точка P в пространстве задана тремя независимы-?
ми координатами x1; x2 ; x3. расстояние    dl  между любыми двумя

точками – это приращение радиуса вектора    dr?, при этом в ортогональной системе координат приращению каждой координаты    dxk
соответствует перемещение вдоль этой координатной линии на элемент длины dlk:
dlk  =  hk dxk, k = 1, 2, 3,
где hk –

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

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

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

СОДЕРЖАНИЕ

Предисловие ………………………………………………………….. 4
1. Аналитические основы численных методов ………………….. 5
1.1. Погрешности численного решения ………………………. 5
1.2. Метрическое пространство ………………………………… 6
1.3. Линейное нормированное пространство ………………… 7
1.4. Вычислительные погрешности …………………………… 9
1.5. Пространство со скалярным произведением ……………. 11
1.6. Полнота метрических пространств ………………………. 13
2. Численные методы линейной алгебры …………………………. 17
2.1. Норма и число обусловленности матрицы ………………. 18
2.2. Прямые методы решения систем алгебраических уравне
ний ………………………………………………………………….. 24
2.3. Итерационные методы решения систем линейных алге
браических уравнений …………………………………………… 34
2.4. Решение систем уравнений с матрицами специального вида
(трехдиагональные матрицы) ………………………………….. 37
2.5. Методы решения проблемы собственных значений и соб
ственных векторов матриц ……………………………………… 39
3. Численные методы решения алгебраических уравнений выс
ших порядков и трансцендентных уравнений …………………… 47
3.1. Устойчивые решения, число обусловленности функции
одной переменной ………………………………………………… 48
3.2. Отделение корней …………………………………………… 51
3.3. Методы уточнения корней уравнения …………………… 52
4. Численные методы приближения функций …………………… 56
4.1. Интерполяция функций …………………………………… 58
4.2. Аппроксимация функций в среднеквадратичной метрике 71
Библиографический список ………………………………………… 86

ПРЕДИСЛОВИЕ

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

1. Дифференциальные уравнения первого порядка.
При решении задач из различных областей науки и техники,
а также экономики часто приходится рассматривать уравнения,
которые кроме независимых переменных и неизвестных (искомых) функций от этих переменных содержат производные искомых функций или их дифференциалы. если искомые (неизвестные) функции, входящие в дифференциальное уравнение,
зависят только от одной независимой переменной, то дифференциальное уравнение называется обыкновенным дифференциальным уравнением. если же искомые (неизвестные) функции зависят от нескольких независимых переменных, то уравнение называется дифференциальным уравнением в частных производных
[1, 2].
Определение 1. Пусть x – независимая переменная, а y = y(x) –
искомая (неизвестная) функция, зависящая от этой переменной.
общим видом обыкновенного дифференциального уравнения nго порядка называется соотношение вида
F (x, y, y, y, …, y (n) ) = 0,
где F – некоторая функция от переменной x, искомой функции
y = y(x) и ее производных до n-го порядка включительно. равенство вида
y (n) = f (x, y, y, y, …, y (n1) ),
где f – некоторая функция независимой переменной x, искомой
(неизвестной) функции y = y(x) и ее производных до (n1)-го порядка включительно, называется дифференциальным уравнением n-го порядка, разрешенным относительно старшей производной [1–5].
Определение 2. решением (или частным решением) дифференциального уравнения называется всякая функция y = j(x),
подстановка которой в дифференциальное уравнение вместо искомой функции обращает его в тождество по независимой переменной x. неявная форма (x, y) = 0 решения дифференциального уравнения называется его интегралом [1, 3, 5].

Определение 3. график решения дифференциального уравнения называется интегральной кривой. в случае интеграла
дифференциального уравнения интегральной кривой называется множество точек числовой плоскости, координаты которых
удовлетворяют равенству (x, y) = 0 [1–6].
1.1. Дифференциальные уравнения первого порядка,
разрешенные относительно производной
Определение 4. общим видом дифференциального уравнения
первого порядка называется равенство
F (x, y, y) = 0,
выражающее взаимосвязь независимой переменной x, искомой
функции y = y(x) и ее производной y. равенства

y = f (x, y) или dy = f (x, y)dx

(1.1)

называются дифференциальным уравнением первого порядка,
разрешенным относительно производной [1, 4, 5].
Пример 1. в случае уравнения

xy x2 y = 0 или yyx
x

(1.2)

решением является функция y = x2 + Cx, поскольку при подстановке в уравнение (1.2) этой функции и ее производной y=
= 2x + C мы получаем тождество по независимой переменной x
при любом значении постоянной C: x(2x + C) x2 (x2 + Cx) =
= 2×2 + Cx x2 x2 Cx = 0. Как видно, дифференциальное уравнение (1.2) имеет бесконечное множество решений (при каждом
из действительных значений

1. ЗАКОН БОЛЬШИХ ЧИСЕЛ. ПРЕДЕЛЬНЫЕ
ТЕОРЕМЫ
Массовые случайные явления в своём совокупном действии
создают строгие закономерности, которые проявляются (и, следовательно, могут изучаться) лишь на достаточно большом числе испытаний (опытов). Эти закономерности могут быть количественно выражены только в форме средних чисел; средние числа выражают их тем точнее, чем большее число испытаний ими
охватывается.
В любом массовом явлении наряду с факторами, общими для
всей массы испытаний, действуют факторы случайные, то есть
такие, которые в отдельных испытаниях (опытах) могут быть
различны, и их действие может быть направлено в разные стороны (поскольку между отдельными испытаниями имеется известная степень взаимной независимости). В результате взаимопогашения действия случайных факторов проявляется действие
факторов общих для данного явления, то есть проявляется закономерность всего массового явления в целом.
Таким образом, при достаточно большом числе испытаний,
характеристики случайных событий и случайных величин, наблюдаемых при испытании (в опыте), становятся почти неслучайными. Теория вероятностей изучает эти закономерности.
Группа теорем, устанавливающих соответствие между теоретическими и экспериментальными характеристиками случайных
величин и случайных событий при большом числе испытаний над
ними, а также касающихся предельных законов распределения,
объединяются под общим названием предельных теорем теории
вероятностей.

Рассмотрение предельных теорем начнём с утверждений и
теорем, объединённые общим названием – закон больших чисел.
Наиболее изящные и простые доказательства этих теорем получаются с помощью неравенства Чебышева, которое мы и рассмотрим в первую очередь.
1.1. Неравенство Чебышева

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

D[ ]

P (j M [ ]j < ) > 1

2;

(1)

где – случайная величина, M [ ] и D[ ] – соответственно математическое ожидание и дисперсия, > 0 .
Доказательство. Проведем доказательство для непрерывной случайной величины с плотностью вероятности f (x) . В этом
случае
Z +1

D[ ] =

1

(x M [ ])2f (x)dx :

Разобъём область интегрирования на две области:
jx M [ ]j < k[ ] и jx M[ ]j k[ ] , где [ ] – среднее
квдратичное отклонение ( D[ ] =2[ ] ) и k > 0 :

Z

D[ ] =
Z
+

(x M [ ])2f (x)dx +
jx M[ ]jk[ ]

(x M[ ])2f (x)dx :

jx M[ ]jОба интеграла, входящих в формулу для дисперсии, неотрицательны (в силу неотрицательности подинтегральной функции),
отбросив второй из них и заменив в подинтегральной функции в
первом интеграле jx M [ ] на минимально возможное значение
k[ ] , получим следующее неравенство:
Z

D[ ]

(x M [ ])2f (x)dx >
jx M[ ]jk[ ]
Z
> k22[] f (x)dx :
jx M [ ]jk[ ]

Так как,

P (

) =Rf (x)dx , то

или

D[ ] > k2D[ ]P (j M[ ]j k[ ])

1
> P (j M [ ]j k[ ])