Дипломная работа на тему "Алгоритм компактного хранения и решения СЛАУ высокого порядка"

ГлавнаяМатематика → Алгоритм компактного хранения и решения СЛАУ высокого порядка




Не нашли то, что вам нужно?
Посмотрите вашу тему в базе готовых дипломных и курсовых работ:

(Результаты откроются в новом окне)

Текст дипломной работы "Алгоритм компактного хранения и решения СЛАУ высокого порядка":


Введение

Цепь Маркова — последовательность случайных событий с конечным или счётным бесконечным числом исходов, характеризующаяся тем свойством, что при фиксированном настоящем будущее независимо от прошлого.

Цепи Маркова – одна из основных и актуальных тем в нынешнее время в современной математике. Цепи Маркова являются обобщением схемы Бернулли, которая была написана в XVII, а Марковские цепи получили сравнительно недавно свое признание. Очень много процессов в нынешнее время решаются с помощью схем Бернулли или цепей Маркова. Вся поисковая система Интернета основана на этих процессах.

Эта была одна из основных причин выбора мною этой темы для выпускной квалификационной работы (ВКР). Мне было очень интересно, по какому принципу происходит выборка по рассылке, или по поиску в Интернете. Рассылка спам-ботов основана тоже на этих же процессах.

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

Свою работу «Приложение схемы Бернулли. Обобщение. Цепи Маркова» я начинаю с введения понятий касающихся раздела схемы Бернулли. Из этого и состоят моя первая глава ВКР - Биография Якоба Бернулли и схема Бернулли. Я рассматриваю различные варианты схем Бернулли, как она по-разному применятся, различные формы записи, обобщения.

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

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

Глава 1. Схема Бернулли

1.1 Исторический курс. Биография Якоба Бернулли

Якоб Бернулли родился 27 декабря 1654 г. По желанию отца готовился к званию протестантского священника. Окончил Базельский университет, где изучал философию, богословие и языки. Владел немецким, французским, английским, итальянским, латинским и греческим языками. Испытывая непреодолимое влечение к математике, изучал ее тайком от отца. В 1671 г. получил степень магистра философии. С большим успехом читал проповеди на немецком и французском языках. В то же время продолжал пополнять свои знания по математике без учителя, почти без учебников.

В октябре 1686 г. оказывается вакантной должность профессора математики в Базельском университете. Успехи Якоба в математике хорошо известны, и Сенат университета единодушно выдвинул на вакантную должность Якоба Бернулли. Вступление в должность состоялось 15 февраля 1687 г. Вряд ли присутствовавшие при этом скромном акте представляли, что они являются свидетелями начала беспримерного в истории математики события: отныне кафедру будут занимать Бернулли на протяжении ста лет. Члены же этой семьи будут профессорами родного университета в течение четверти тысячелетия, вплоть до второй половины XX в.

В том же году Якоб Бернулли прочитал в «Асtа Eruditirum» за 1684 г. «Новый метод» Лейбница и, обнаружив трудные места, письменно обратился к Лейбницу за разъяснением. Лейбниц, находившийся в длительной служебной поездке, получил письмо только через три года, когда надобность в консультации отпала: Якоб совместно Иоганном овладели дифференциальным и интегральным исчислениями настолько, что вскоре смогли приступить систематическому развитию метода. Образовавшийся триумвират — Лейбниц, Якоб и Иоганн Бернулли — менее чем за двадцать лет чрезвычайно обогатил анализ бесконечно малых.

С 1677 г. Я. Бернулли стал вести записные книжки, куда вносил различного рода заметки научного содержания. Первые записи посвящены теологии, сделаны под влиянием распространенного в то время в Базеле сборника спорных теологических вопросов.

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

В январе 1684 г. Я. Бернулли провел в Базельском университете открытый диспут, на котором защищал 100 тезисов, из них 34 логических, 18 диалектических и 48 смешанных. Некоторые тезисы крайне любопытны. Вот примеры:

78. Иногда существует несколько кратчайших путей из точки в точку

Заказать написание дипломной - rosdiplomnaya.com

Уникальный банк готовых защищённых студентами дипломных работ предлагает вам скачать любые работы по необходимой вам теме. Высококлассное выполнение дипломных проектов на заказ в Иркутске и в других городах России.

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

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

89. Квадратура круга еще не найдена, но не потому, что между искривленным и прямолинейным нет никакой связи; в действительности кривую можно спрямить, а криволинейную фигуру квадрировать

В мае 1690 г. Я. Бернулли опубликовал в «Асtа Eruditirum» первую работу, связанную с исчислением бесконечно малых. В ней он дал решение поставленной Лейбницем в 1687 г. задачи о парацентрической изохроне. Необходимо было найти кривую, по которой материальная точка опускалась бы в равные промежутки времени на равные высоты. Я. Бернулли вывел дифференциальное уравнение кривой и проинтегрировал его. При этом он впервые употребил в печати термин «интеграл», указав, что из равенства двух выражений, связывающих дифференциалы, следует равенство интегралов.

В лекциях, читанных Лопиталю, И. Бернулли ход решения излагает так. Пусть искомой кривой будет АDС. Материальная точка за время ∆t перемещается из точки D в точку d и из точки С в точку с. По условию задачи проекции дуг Dd Сс на вертикаль одинаковы. Проведем через D и С касательные к кривой до пересечения с продолжением АF. Отрезки касательных будут DK и CL. Напишем тождество

Вв. Сс=Вв. Рс • Рс. Ссю

Дуги Dd и Сс малы, поэтому фигуры GDd и НСс можно считать треугольниками.

Из подобия треугольников GDd и DEK, НСс и СFL получим

Вв. ВП=ВЛ. ВУбСс. Нс=СД. САю

С помощью этих пропорций найдем

Вв. Сс=ВП1Нс • ВК. ВЕ • СА. СДю

По условиям задачи dG/Нс=1, поэтому

Вв1Сс=ВК. ВЕ • СА. СДю

Проведем через точку С прямую СМ, параллельную DК. Тогда

DК/DЕ=СМ/СF, Dd/Сс=СМ/СL.

Но отношение Dd/Сс равно отношению скоростей (интервал ∆t один и тот же), квадраты же скоростей, по найденному Галилеем закону, относятся как пройденные высоты; это дает

Dd2/Сс2=СМ2/СL2=DЕ/CF, СМ2/СL2 =DЕ/СF.

Последнее равенство означает, что если через две произвольные точки кривой провести касательные СL и DК и через точку С провести СМ параллельно DК, то должна выполняться указанная пропорция. Таким свойством обладает искомая кривая.

Задача оказалась сведенной к классу обратных задач на касательные: найти кривую, касательные к которой удовлетворяют некоторому требованию. Подобную задачу впервые предложил Декарту Дебон, и Декарт с ней не справился. Разработанный Лейбницем метод позволяет решать и обратные задачи на касательные.

Выберем начало координат в точке А. Обозначим АЕ=х, ЕD=у. Тогда GD=dх, Gd=dу. Обозначим также СF=а, СL=b. Треугольники FСМ и СdD подобны, отсюда

Gd/Dd=FС/СМ.

Но Dd = √dx2+dy2, поэтому

dy/√ dx2+dy2= а/СМ, откуда

CM2= (a2dx2+a2dy2)/dy2.

Подставим найденное выражение в пропорцию СL2/СM2=СF/СЕ и получим дифференциальное уравнение

и2вн2.(ф2вч2+ф2вн2)=ф. нб и2нвн2-ф3вн2=ф3вч2б (и2н-а3)ву2 = а3вч2б

√b2y-a3 dy=√a3 dx.

В уравнении переменные разделены, интегрирование его дает искомую кривую

2b2у — 2а3/3b2 √b2у - а3 == х√а3.

Парацентрическая изохрона оказалась полукубической параболой. Вид кривой раньше Я. Бернулли определили Лейбниц и Гюйгенс, но лишь Я. Бернулли дал решение средствами анализа бесконечно малых.

В приложении к другой работе о рядах (1694 г.) Я. Бернулли сформулировал несколько тезисов.

1. Существуют спирали, которые совершают бесконечное число витков вокруг полюса, но имеют конечную длину.

2. Существуют кривые, которые, подобно эллипсу, замкнуты и, подобно параболе, уходят в бесконечность, например ay2=х2(b+х).

3. Существуют кривые, состоящие из двух ветвей, например ау2=х(а2—х2),

4. Существуют неограниченные поверхности с конечной площадью.

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

Я. Бернулли увлекался также и изопериметрическими задачами. Древнейшая из них—задача легендарной основательницы Карфагена и его первой царицы Дидоны. Легенда такова. Дидона бежала от отца, тирского царя, и достигла Африки, где купила у туземцев участок земли на берегу моря «не больше, чем можно окружить воловьей шкурой». Она разрезала шкуру на узкие полоски и связала из них длинную ленту. Спрашивается, какой формы должна быть фигура, оцепленная лентой данной длины, чтобы площадь фигуры была наибольшей?

Ван-дер-Варден пишет, что Зенодор, живший вскоре после Архимеда, высказал 14 предложений относительно изопериметрических фигур. Он утверждал, что из всех фигур (кругов и многоугольников), имеющих одинаковый периметр, круг будет наибольшим, а также и то, что из всех пространственных тел с одинаковой поверхностью наибольшим будет шар.

Решение задачи содержится в записных книжках Я. Бернулли и помещено в майском номере «Acta Eruditorum» за 1701 г. Я. Бернулли и здесь применил высказанный ранее принцип: поскольку площадь должна быть экстремальной, этим же свойством должна обладать и любая ее элементарная часть. Он получил дифференциальное уравнение третьего порядка и впоследствии проинтегрировал его.

К. А. Рыбников пишет: «Таким образом, решение изопериметрической задачи означало очень важный, принципиально новый этап в истории вариационного исчисления; оно дало возможность решать более сложные вариационные задачи, им был сделан важный шаг на пути решения вариационных задач».

При изучении свойств сочетаний и фигурных чисел Я. Бернулли встретился с суммированием степеней натуральных чисел Sm = å km

Эти вопросы интересовали математиков и ранее. Я. Бернулли составил таблицу фигурных чисел, указал их свойства и на основании отмеченных свойств нашел формулы для сумм степеней натуральных чисел. Он привел формулы сумм от S(n) до S(n10):

S (n) = n2/2 +n/2

S (n2) = n3/3 + n2/2+ n/6

S (n3) = n4/4 + n3/2 + n2/4

S (n4) = n5/5 + n4/2 + n3/3 – n/30

S (n5) = n6/6 + n5/2 + 5n4/12 - n2/12

S (n6) = n7/7 + n6/2 + n5/2 - n3/6 + n/42

S (n7) = n8/8 + n7/2 + 7n6/12 - 7n4/24 + n2/12

S (n8) = n9/9 + n8/2 + 2n7/3 - 7n5/15 + 2n3/9 – n/30

S (n9) = n10/10 + n9/2 + 3n8/4 - 7n6/10 + n4/2 - n2/12

S (n10) = n11/11 + n10/2 + 5n9/9 – n7 + n5 - n3/2 + 5n/66

Затем Я. Бернулли указал общую формулу

S(nc) = nc+1/c+1 + 1/2*nc + 1/2*( )Anc-1 + 1/4*( )Bnc-3 + 1/6*( )Cnc-5 +

+1/8*( )Dnc-7+ …

Здесь ( ), ( ) … - числа сочетаний; показатели степени n убывают, последний член в правой части содержит n или n2.

Числа A, B, C, D … - коэффициенты при n в выражениях S(n2), S(n4), S(n6), …

Именно: А=1/6, В=-1/30, С=1/42, D=-1/30,

Бернулли формулирует общее правило для вычисления этих чисел: сумма коэффициентов в выражениях S(n), S(n2), S(n3), … равна единице. Например, 1/9+1/2+2/3-7/15+2/9+D=1. Отсюда D=-1/30.

Я. Бернулли подчеркивает удобство таблицы фигурных чисел и заявляет, что с ее помощью в течение «половины четверти часа» нашел сумму десятых степеней первой тысячи натуральных чисел. Она оказалась равной

91 409 924 241 424 243 424 241 924 242 500.

1.2 Схема Бернулли. Обобщение

Определение 1. Схемой Бернулли называется последовательность независимых в совокупности испытаний, в каждом из которых возможны лишь два исхода - "успех" и "неудача", при этом успех в одном испытании происходит с вероятностью Рисунок убран из работы и доступен только в оригинальном файле.а неудача - с вероятностью Рисунок убран из работы и доступен только в оригинальном файле..

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

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

Здесь буквами "у" и "н" обозначены успешный и неудачный результаты испытаний соответственно.

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

Теорема 1 (формула Бернулли). При любом Рисунок убран из работы и доступен только в оригинальном файле.имеет место равенство:

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

Доказательство. Событие Рисунок убран из работы и доступен только в оригинальном файле.означает, что в Рисунок убран из работы и доступен только в оригинальном файле.испытаниях схемы Бернулли произошло ровно Рисунок убран из работы и доступен только в оригинальном файле.успехов. Рассмотрим один из благоприятствующих событию Рисунок убран из работы и доступен только в оригинальном файле.элементарных исходов:

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

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

Определение 2. Набор чисел Рисунок убран из работы и доступен только в оригинальном файле.называется биномиальным распределением вероятностей.

1.2.1 Номер первого успешного испытания

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

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

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

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

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

Определение 3. Набор чисел Рисунок убран из работы и доступен только в оригинальном файле.называется геометрическим распределением вероятностей.

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

Теорема 3. Пусть Рисунок убран из работы и доступен только в оригинальном файле.для любого Рисунок убран из работы и доступен только в оригинальном файле.. Тогда для любых неотрицательных целых Рисунок убран из работы и доступен только в оригинальном файле.и Рисунок убран из работы и доступен только в оригинальном файле.имеет место равенство:

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

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

Доказательство. По определению условной вероятности,

--------------------------------------------------

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

| (1) |
--------------------------------------------------------- --------------------------------------------------

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

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

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

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

Теорема 3 доказана.


1.2.2 Независимые испытания с несколькими исходами

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

Пример 1. Игральная кость подбрасывается 15 раз. Найти вероятность того, что выпадет ровно десять троек и три единицы.

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

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

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

Теорема 4 (Обобщенная формула Бернулли). Для любого Рисунок убран из работы и доступен только в оригинальном файле.и любых неотрицательных целых чисел Рисунок убран из работы и доступен только в оригинальном файле.сумма которых равна Рисунок убран из работы и доступен только в оригинальном файле.верна формула

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

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

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

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

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

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

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

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

1.2.3 Теорема Пуассона для схемы Бернулли

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

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

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

Теорема 5 (теорема Пуассона). Пусть Рисунок убран из работы и доступен только в оригинальном файле.и Рисунок убран из работы и доступен только в оригинальном файле.так, что Рисунок убран из работы и доступен только в оригинальном файле. Тогда для любого Рисунок убран из работы и доступен только в оригинальном файле.вероятность получить Рисунок убран из работы и доступен только в оригинальном файле.успехов в Рисунок убран из работы и доступен только в оригинальном файле.испытаниях схемы Бернулли с вероятностью успеха Рисунок убран из работы и доступен только в оригинальном файле.стремится к величине Рисунок убран из работы и доступен только в оригинальном файле.

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

Доказательство. Положим Рисунок убран из работы и доступен только в оригинальном файле.. По условию Рисунок убран из работы и доступен только в оригинальном файле.. Подставим Рисунок убран из работы и доступен только в оригинальном файле.в формулу Бернулли:

--------------------------------------------------

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

| (2) |
--------------------------------------------------------- --------------------------------------------------

В соотношении (2) мы воспользовались тем, что Рисунок убран из работы и доступен только в оригинальном файле.и замечательным пределом Рисунок убран из работы и доступен только в оригинальном файле.. Докажем последнее свойство:

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

Определение 4. Набор чисел Рисунок убран из работы и доступен только в оригинальном файле.называется распределением Пуассона с параметром Рисунок убран из работы и доступен только в оригинальном файле..

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

Рисунок убран из работы и доступен только в оригинальном файле.(3)

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

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

Теорема 6 (уточненная теорема Пуассона). Пусть Рисунок убран из работы и доступен только в оригинальном файле.- произвольное множество целых неотрицательных чисел, Рисунок убран из работы и доступен только в оригинальном файле.- число успехов в Рисунок убран из работы и доступен только в оригинальном файле.испытаниях схемы Бернулли с вероятностью успеха Рисунок убран из работы и доступен только в оригинальном файле.Рисунок убран из работы и доступен только в оригинальном файле.. Cправедливо неравенство

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

Таким образом, теорема 6 предоставляет нам возможность самим решать, достаточно ли Рисунок убран из работы и доступен только в оригинальном файле.велико, а Рисунок убран из работы и доступен только в оригинальном файле.мало, руководствуясь полученной величиной погрешности. Какова же погрешность в формуле (3)? Взяв Рисунок убран из работы и доступен только в оригинальном файле.имеем

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

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

Пример 2. В урне 20 белых и 10 черных шаров. Вынули 4 шара, причем каждый вынутый шар возвращают в урну перед извлечением следующего и шары в урне перемешивают. Найти вероятность того, что из четырех вынутых шаров окажется 2 белых.

Решение. Событие А – достали белый шар. Тогда вероятностиРисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.. По формуле Бернулли требуемая вероятность равна

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

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

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

Найдем вероятности того, что в семье нет девочек, родилась одна, две или три девочки:

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле.,

Рисунок убран из работы и доступен только в оригинальном файле., Рисунок убран из работы и доступен только в оригинальном файле..

Следовательно, искомая вероятность

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

Пример 4. Среди деталей, обрабатываемых рабочим, бывает в среднем 4% нестандартных. Найти вероятность того, что среди взятых на испытание 30 деталей две будут нестандартными.

Решение. Здесь опыт заключается в проверке каждой из 30 деталей на качество. Событие А - «появление нестандартной детали», его вероятность Рисунок убран из работы и доступен только в оригинальном файле., тогда Рисунок убран из работы и доступен только в оригинальном файле.. Отсюда по формуле Бернулли находимРисунок убран из работы и доступен только в оригинальном файле..

Пример 5. При каждом отдельном выстреле из орудия вероятность поражения цели равна 0,9. Найти вероятность того, что из 20 выстрелов число удачных будет не менее 16 и не более 19.

Решение. Вычисляем по формуле Бернулли:

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

Пример 6. Независимые испытания продолжаются до тех пор, пока событие А не произойдет k раз. Найти вероятность того, что потребуется n испытаний (n < k), если в каждом из них Рисунок убран из работы и доступен только в оригинальном файле..

Решение. Событие В – ровно n испытаний до k-го появления события А – есть произведение двух следующий событий:

D – в n-ом испытании А произошло;

С – в первых (n–1)-ом испытаниях А появилось (к-1) раз.

Теорема умножения и формула Бернулли дают требуемую вероятность:

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

цепь марков бернулли информатика

Глава 2. Цепи Маркова

2.1 Биография Маркова

Марков Андрей Андреевич. 2 (14) июня 1856—20 июля 1922 — русский математик, специалист по теории чисел, теории вероятностей и математическому анализу.

С 1886 — адъюнкт, с 1890 — экстраординарный, а с 1896 — ординарный академик Императорской Санкт-Петербургской Академии Наук.

Андрей Марков родился в семье мелкого чиновника в Рязанской губернии. В 1878 окончил Петербургский университет со степенью кандидата и в том же году получил золотую медаль за работу "Об интегрировании дифференциальных уравнений при помощи непрерывных дробей". С 1880 — приват-доцент, с 1886 — профессор, а с 1905 — заслуженный профессор Петербургского университета.

Научные исследования Марков тесно примыкают по своей тематике к работам старших представителей Петербургской математической школы — П. Л. Чебышева, Е. И. Золотарева и А. Н. Коркина. Блестящих результатов в области теории чисел Марков достиг в магистерской диссертации "О бинарных квадратичных формах положительного определителя" (1880). Результаты, полученные им в этой работе, послужили основой дальнейших исследований в этой области в СССР и за рубежом. В 1905 вышел в отставку. В этом же году ему присвоено звание заслуженного профессора Петербургского университета. Написал около 70 работ по теории чисел, теории приближения функций, теории дифференциальных уравнений, теории вероятностей, в т. ч. и 2 классических произведения — "Исчисление конечных разностей" и "Исчисление вероятностей". Труды Маркова по теории чисел касаются главным образом теории неопределенных квадратичных форм. Почти все они посвящены нахождению экстремальных квадратичных форм данного определителя.

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

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

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

Он был материалистом и убежденным атеистом, бескомпромиссным борцом против религии. 12.02.1912 Марков подал в Синод прошение об отлучении его от церкви. Марков протестовал против решения царского правительства, отказывавшегося утвердить избрание А. М. Горького почетным членом Петербургской Академии Наук. АН СССР учредила премию им. А. А. Маркова за лучшие работы по математике. Именем Маркова назван кратер краевой зоны Луны.

Свой последний мемуар он представил Академии наук всего лишь за несколько месяцев до смерти. Тяжелый недуг свалил его в постель, и 20 июля 1922 г. он умер.

2.2 Цепи Маркова

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

Определение 6. Цепью Маркова называется последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий Ai из полной группы. При этом условная вероятность pij(s) того, что в s –ом испытании наступит событие Aj при условии, что в (s – 1) – ом испытании наступило событие Ai, не зависит от результатов предшествующих испытаний.

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

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

Определение 8. Однородной называется цепь Маркова, если условная вероятность pij перехода системы из состояния i в состояние j не зависит от номера испытания. Вероятность pij называется переходной вероятностью.

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

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

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

Пример 7. По заданной матрице перехода построить граф состояний

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

Т. к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния. S1 0,2 0,7 S2 0,4 S4 0,6 0,5 0,1 0,5 S3.

На графе не отмечаются вероятности перехода системы из одного состояния в то же самое. При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы. Пусть Pij(n) – вероятность того, что в результате n испытаний система перейдет из состояния i в состояние j, r – некоторое промежуточное состояние между состояниями i и j. Вероятности перехода из одного состояния в другое pij(1) = pij. Тогда вероятность Pij(n) может быть найдена по формуле, называемой равенством Маркова:

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

Здесь т – число шагов (испытаний), за которое система перешла из состояния i в состояние r. В принципе, равенство Маркова есть ни что иное как несколько видоизменная формула полной вероятности. Зная переходные вероятности (т. е. зная матрицу перехода Р1), можно найти вероятности перехода из состояния в состояние за два шага Pij(2), т. е. матрицу Р2, зная ее – найти матрицу Р3, и т. д. Непосредственное применений полученной выше формулы не очень удобно, поэтому, можно воспользоваться приемами матричного исчисления (ведь эта формула по сути – не что иное как формула перемножения двух матриц). Тогда в общем виде можно записать:

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

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

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

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

Рассмотрим задачу об осле, стоящем точно между двумя копнами: соломы ржи и соломы пшеницы (рис. 1).

Осел стоит между двумя копнами: "Рожь" и "Пшеница" (рис. 1). Каждую минуту он либо передвигается на десять метров в сторону первой копны (с вероятностью Рисунок убран из работы и доступен только в оригинальном файле.), либо в сторону второй копны (с вероятностью Рисунок убран из работы и доступен только в оригинальном файле.), либо остается там, где стоял (с вероятностью Рисунок убран из работы и доступен только в оригинальном файле.); такое поведение называется одномерным случайным блужданием. Будем предполагать, что обе копны являются "поглощающими" в том смысле, что если осел подойдет к одной из копен, то он там и останется. Зная расстояние между двумя копнами и начальное положение осла, можно поставить несколько вопросов, например: у какой копны он очутится с большей вероятностью и какое наиболее вероятное время ему понадобится, чтобы попасть туда?

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

Рис. 1

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

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

Рис. 2

Пусть Рисунок убран из работы и доступен только в оригинальном файле.— вероятность того, что он переместится из Рисунок убран из работы и доступен только в оригинальном файле.в Рисунок убран из работы и доступен только в оригинальном файле.за одну минуту. Например, Рисунок убран из работы и доступен только в оригинальном файле.и Рисунок убран из работы и доступен только в оригинальном файле.. Эти вероятности Рисунок убран из работы и доступен только в оригинальном файле.называются вероятностями перехода, а Рисунок убран из работы и доступен только в оригинальном файле.-матрицу Рисунок убран из работы и доступен только в оригинальном файле.называют матрицей перехода (рис. 2). Заметим, что каждый элемент матрицы Рисунок убран из работы и доступен только в оригинальном файле.неотрицателен и что сумма элементов любой из строк равна единице. Из всего этого следует, что Рисунок убран из работы и доступен только в оригинальном файле.— начальный вектор-строка, определенный выше, местоположение осла по прошествии одной минуты описывается вектором-строкой Рисунок убран из работы и доступен только в оригинальном файле., а после Рисунок убран из работы и доступен только в оригинальном файле.минут — вектором Рисунок убран из работы и доступен только в оригинальном файле.. Другими словами, Рисунок убран из работы и доступен только в оригинальном файле.-я компонента вектора Рисунок убран из работы и доступен только в оригинальном файле.определяет вероятность того, что по истечении Рисунок убран из работы и доступен только в оригинальном файле.минут осел оказался в Рисунок убран из работы и доступен только в оригинальном файле..

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

Нас будет интересовать следующее: можно ли попасть из одного данного состояния в другое, и если да, то за какое наименьшее время. Например, в задаче об осле из Рисунок убран из работы и доступен только в оригинальном файле.в Рисунок убран из работы и доступен только в оригинальном файле.можно попасть за три минуты и вообще нельзя попасть из Рисунок убран из работы и доступен только в оригинальном файле.в Рисунок убран из р
<p>Здесь опубликована для ознакомления часть дипломной работы Если у вас нет возможности самостоятельно написать дипломную - закажите её написание опытному автору»


Просмотров: 507

Другие дипломные работы по специальности "Математика":

Интеграл Лебега-Стилтьеса

Смотреть работу >>

Расширение кольца с помощью полутела

Смотреть работу >>

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

Смотреть работу >>

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

Смотреть работу >>

Кольцо целых чисел Гаусса

Смотреть работу >>