Обзор правил сжатия изображений

Так,

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

Прежде всего, приведем определение.

Пусть - случайный процесс, принимающий значения из набора . Будем говорить, что является цепью Маркова, если вероятность , зависит только от значения этого процесса на предыдущем шаге, , и не зависит от предшествующих значений . Мы определим N<? как число элементов S.

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

Аналогично, в вычислении вероятностей, соответствующих второму шагу, , мы использовали значения вероятностей, вычисленных на первом шаге.

Это свойство зависимости лишь от информации о является определяющим свойством цепи Маркова.

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

Матрица P является матрицей переходных вероятностей для цепи Маркова тогда и только тогда, когда для всех и для всех .

Для нашего веб-путешественника элементы матрицы переходных вероятностей представляют собой вероятности оказаться на веб-странице при переходе со страницы . Однако, наши правила предоставляют путешественнику возможность выбора перехода с равной вероятностью среди доступных ссылок. Так если веб-страница предлагает m ссылок, то столбец j матрицы содержит величину в строках, соответствующих m связанным веб-страницам и 0 в оставшихся строках. Матрица перехода простого примера нашей сети выглядит так:

Столбцы P указывают возможные переходы: с веб-страницы E веб-путешественник может перейти на веб-страницы B, C и D. Аналогично, ненулевые величины в строках указывают возможные начальные позиции: единственная ненулевая величина в четвертой строке указывает, что мы можем прибыть на веб-страницу D только со страницы E.

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

,

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

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

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



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

Тот же метод может быть применен, чтобы вычислить вероятностный вектор после некоторого числа шагов: , или

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

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

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

.

Такие векторы называются собственными векторами, а соответствующие им числа ? - характеристическими или собственными числами матрицы .

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

,

которую можно записать так

.



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

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

Из сказанного следует, что матрица размера имеет не более чем n различных характеристических чисел.

Свойство 1. Если собственные векторы матрицы , соответствующие одному и тому же характеристическому числу ?, а ?, ?, ? … - произвольные числа, то вектор либо равен нулю, либо также является собственным вектором матрицы при том же числе ?.

Действительно, из



следует:

.

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

Свойство 2. Собственный вектор определяется с точностью до множителя: если x - собственный вектор, то ?x - также собственный вектор.

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

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

Умножим обе части равенства на ?₁ и вычтем из равенства . Тогда получим



Число слагаемых изменилось, так как (?₁- ?₁)=0. Можно сказать, что мы применили к равенству матрицу (A- ?₁I). Применяя к равенству матрицы (A- ?₂I), (A- ?₃I), …,(A- ?_m-1I ) , приходим к равенству

.

Например, для случая (A- ?₂I), получим

,

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

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

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

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



Если

, то .

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

18. Уравнение колебаний струны

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

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

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

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

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

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

B) Струна предполагается упругой и подчиняющейся закону Гука; изменение величины силы натяжения при этом пропорционально изменению длины струны.

C) Примем, что струна однородна; линейную плотность струны обозначим ( - масса единицы длины струны).

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

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

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

Поскольку разложение функции в ряд Маклорена имеет вид

,

можно считать, что . Используя ряд Маклорена для функции , можно показать, что и, следовательно,

.



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

.

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

Так как , то .

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

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

.



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

.

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

.

В силу сделанных предположений

.

Следовательно,



Здесь частное приращение производной при переходе от аргументов к аргументам заменено ее частным дифференциалом, т.е. .

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

Направление равнодействующей определится знаком функции .

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

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



Здесь - постоянная положительная величина, . Если , уравнение называется однородным, в противном случае - неоднородным.

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

Рассмотрим некоторые примеры граничных условий:

а) если конец струны движется по закону , то ;

б) если на правый конец струны действует заданная сила , то .

Действительно, в этом случае . Следовательно, .

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

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

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

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

1. Заданные условия (режимы) в граничных точках. В этой задаче концы струны совершают заданные движения.

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



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

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

19. Конечные разности

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

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

,



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

.

Для первой производной по времени конечная разность имеет вид

,

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

.

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

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

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

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

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

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

Пример 1. Равномерная сетка на отрезке. Разобьем единичный отрезок [0,1] на равных частей. Расстояние между соседними узлами назовем шагом сетки. Точки деления - узлы сетки.

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

Разобьем отрезки [0,1] оси и [0,T] оси соответственно на и частей, пусть . Через точки деления проведем прямые, параллельные соответствующим осям. В результате пересечения этих прямых получим узлы , которые и образуют сетку. Эта сетка имеет шаги h и ? соответственно по направлениям x и t.

Численное решение уравнения колебаний струны

Рассмотрим численный метод решения уравнения колебаний струны

,

с условиями на концах струны



и начальными условиями

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

и

Пусть ,

Центральные конечно-разностные аппроксимации принимают вид

, .

Термин центральные конечно-разностные аппроксимации используется здесь в том смысле, что указанные аппроксимации не применяются в граничных точках ().

Подставим выражения в исходное уравнение:



Сокращаем обе части на и умножаем на

После преобразований получаем разностное уравнение в виде

для

Граничные условия переписываются в виде

Начальное условие для смещения напишем в виде

.

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

,

то есть .



После этого, используя разностную формулу для смещения, получаем

.

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

,

величину можно аппроксимировать по формуле

.

Поэтому

, ,

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

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

.

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

Используемая разностная схема устойчива при , то есть при .

Размещено на Allbest.ru