Метод максимального правдоподобия и его модификации

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

Рубрика Математика
Вид дипломная работа
Язык русский
Дата добавления 31.05.2016
Размер файла 400,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Оглавление

Аннотация

Abstract

Введение

Глава 1. Теоретические аспекты

1.1 Коротко о методе главных компонент

1.2 Факторный анализ

1.2.1 Модель факторного анализа

1.2.2 Сравнение факторного анализа с методом главных компонент

1.2.3 Интерпретация матрицы нагрузок

1.2.4 Неоднозначность решения задачи факторного анализа. Выбор вращения факторов

1.2.5 Метод максимального правдоподобия

1.2.6 Выбор числа общих факторов

Глава 2. Техническая часть

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

Глава 3. Экспериментальная часть

3.1 Адаптация метода максимального правдоподобия к нелинейным зависимостям

3.2 Генерация тестовых данных

3.3 Измерение эффективности метода

3.4 Определение числа факторов

3.5 Результаты применения методов к искусственно смоделированным данным

3.6 Демонстрация эффективности метода определения числа факторов, основанного на величине приращения объясняемого среднеквадратического отклонения

Глава 4. Исследовательская часть

4.1 Выбор реальных данных

4.2 Результаты применения методов к реальным данным

Заключение

Список литературы

Приложение

Аннотация

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

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

Ключевые слова

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

Abstract

With a rapid technological change, solving practical tasks requires to process increasing amounts of data. That is why dimensionality reduction methods are assuming greater importance nowadays. However, these methods lose theoretical validity or even efficiency when applied to certain data structures, because they set significant limits on the investigated system. Namely, in these methods it is assumed that the initial features of the system are linearly interdependent.

The aim of this graduation project is to adapt one of the traditional methods of factor analysis - maximum-likelihood method - to the cases of nonlinearly dependent features.

This paper provides an overview of the theoretical basis of factor analysis and its maximum-likelihood method. The adaptations of this method to nonlinear relationships between features are proposed. The traditional and the modified methods are compared in terms of efficiency on both modeled and real data.

Введение

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

Целью этого может являться следующее:

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

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

· Сокращение объема хранимых данных.

Список можно продолжать.

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

Если избыточность обусловлена тем, что многие признаки находятся в сильной зависимости друг от друга, то обычно целесообразнее применить то, что называется "feature extraction", а именно - подвергнуть старые признаки таким преобразованиям, чтобы получить на выходе меньшее число новых признаков, потеряв при этом минимум информации.

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

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

Для достижения этой цели перед автором этой работы стоят следующие основные задачи:

1) Изучение и программная реализация метода максимального правдоподобия.

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

3) Проверка корректности работы разработанных алгоритмов на искусственно смоделированных данных.

4) Сравнение эффективности адаптированных и традиционного методов на моделированных данных, связанных разными типами зависимости.

5) Применение методов к реальным данным с целью проверки и сравнения их эффективности для решения практических и научно-исследовательских задач.

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

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

Глава 1. Теоретические аспекты

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

1.1 Коротко о методе главных компонент

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

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

Определение: Назовем линейную комбинацию случайных величин линейной комбинацией единичной нормы, если .

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

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

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

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

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

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

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

Таким образом, мы получили систему

Или, в матричном виде, , где -ый столбец матрицы имеет вид .

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

.

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

.

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

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

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

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

1.2 Факторный анализ

1.2.1 Модель факторного анализа

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

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

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

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

Кроме того, принимаются следующие допущения:

· Общие факторы - некоррелированные случайные величины

·

· Частные факторы независимы как между собой, так и с .

·

Дисперсии частных факторов называются остаточными дисперсиями.

В матричном виде наша система записывается как . Матрица называется матрицей нагрузок. Ее элемент называется нагрузкой -го фактора на -й признак.

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

1.2.2 Сравнение факторного анализа с методом главных компонент

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

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

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

1.2.3 Интерпретация матрицы нагрузок

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

Из предположений модели следует, что

.

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

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

Более того, из предположений модели следует, что

.

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

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

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

1.2.4 Неоднозначность решения задачи факторного анализа. Выбор вращения факторов

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

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

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

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

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

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

1.2.5 Метод максимального правдоподобия

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

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

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

Если - дискретный случайный вектор, то функция правдоподобия определятся как .

Если имеет непрерывное распределение, то определение следующее:

,

где - функция плотности случайной величины .

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

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

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

Начнем с того, что в нем предполагается, что общие факторы имеют стандартное нормальное распределение , частные факторы имеют нормальное распределение: .

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

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

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

В общем случае, выборочная ковариационная матрица вычисляется по формуле:

,

где .

Но мы предполагаем, что - центрированный случайный вектор, поэтому формула имеет вид:

.

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

Воспользуемся следующим утверждением.

Если случайный вектор имеет нормальное распределение , то совместная функция плотности элементов его выборочной ковариационной матрицы имеет вид:

(1)

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

Выражение примет вид

.

Для удобства прологарифмируем полученное выражение:

.

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

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

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

1.2.6 Выбор числа общих факторов

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

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

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

Для проверки против воспользуемся методом отношения правдоподобия.

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

Пусть проверяется гипотеза против альтернативы .

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

,

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

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

При выполнении некоторых условий, (которые выполняются в том числе тогда, когда наблюдения независимы и имеют нормальное распределение, т.е. в нашем случае), если объем выборки стремится к бесконечности, то, при верности гипотезы , статистика сходится по распределению к случайной величине, распределенной согласно закону хи-квадрат , где . Точные формулировки этих условий приведены в: (Roger R. Davidson, William E. Lever, 1967).

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

Подставляя эти значения в нашу функцию правдоподобия (формула (1) пункт 1.2.5), получаем:

Здесь под имеется ввиду след матрицы .

Логарифмируя это выражение и умножая на , получаем

.

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

Таким образом,

.

Тогда

.

Заметим, что условие , наложенное в начале этого пункта, обеспечивает положительность числа .

В качестве границы критической области выступает квантиль .

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

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

Выводы по главе

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

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

Глава 2. Техническая часть

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

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

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

На первом шаге первой итерации мы вычисляем:

· вектор-строку

· вектор-строку

· число

и принимаем в качестве второго приближения для .

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

· вектор-строку

· число

· вектор-строку

· число

и объявляем вторым приближением для .

Если имеется третий фактор, то делаем третий шаг первой итерации, т.е. вычисляем

· вектор-строку

· два числа and

· вектор-строку

· число

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

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

Условия сходимости описанного алгоритма неизвестны, однако на практике сходимость есть, причем довольно быстрая.(Ивченко Г. И., Медведев Ю. И., 2010)

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

Выводы по главе

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

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

Глава 3. Экспериментальная часть

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

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

3.1 Адаптация метода максимального правдоподобия к нелинейным зависимостям

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

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

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

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

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

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

Тогда коэффициент ранговой корреляции двух признаков и вычисляется по формуле:

Матрицу, состоящую из коэффициентов ранговой корреляции, мы обозначаем как .

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

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

Таблица 3.1. Таблица сопряженности

Интервал

Интервал

Интервал

Интервал

Интервал

Интервал

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

Следующим шагом к получению коэффициента Крамера для признаков и является вычисление статистики хи-квадрат для этих признаков.

Она вычисляется на основании таблицы сопряженности по следующей формуле:

Тогда формула для вычисления коэффициента Крамера следующая:

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

Матрицу, состоящую из коэффициентов Крамера, мы обозначаем как .

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

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

Так что же теперь мы подразумеваем под ?

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

3.2 Генерация тестовых данных

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

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

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

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

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

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

Рисунок 3.1. Зависимости, связывающие признаки в группах демонстрационных данных

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

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

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

Заметим, что дисперсия случайной величины равна:

Сначала найдем ковариацию случайных величин и .

Тогда их корреляция равна:

Выражаем из этой формулы .

Предположим, что неотрицательно.

Тогда:

Аналогично, при отрицательном получаем:

Итого:

Теперь перейдем к алгоритмической реализации этого метода.

Для генерации данных, имеющих заданный коэффициент корреляции, была создана функция "generateCorr". Реализующий эту функцию фрагмент написанного в Матлабе программного кода приведен в Приложении. Функция "generateCorr" работает следующим образом. Она принимает на вход три целых числа: r, n и corr, где corr . r означает количество признаков в нашей генерируемой группе, n - число наблюдений, corr - заданный коэффициент корреляции. Затем создается матрица размера r?n. Первая строка этой матрицы заполняется стандартными нормальными случайными величинами. Вводится переменная . В начале ей присваивается значение дисперсии каждого элемента первой строки, т.е. единица. Затем в цикле для каждой строки матрицы, со второй по последнюю, выполняется следующая последовательность шагов:

· вычисляется текущее значение переменной ? по формуле . По сути, это и есть формула (3), только теперь под случайной величиной мы понимаем стандартную нормальную случайную величину. Значит, в числителе равно единице. А текущее значение переменной на данной итерации цикла равно дисперсии элементов предыдущей строки.

· происходит заполнение текущей строки следующим образом: i-ый элемент текущей строки получается умножением i-го элемента предыдущей строки на текущее значение параметра ? и прибавлением к полученному произведению стандартной нормальной случайной величины, (под которой и подразумевается из математической трактовки).

· переменной присваивается новое значение, равное , т.е. теперь в переменной хранится значение дисперсии элементов текущей строки (см. формулу для (2)).

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

Принцип генерации оставшихся трех групп следующий. Пусть имеют усеченное стандартное нормальное распределение. А - нормальное распределение .

Тогда значения признаков - вычисляются по следующим формулам:

Технически эта задача была решена следующим образом. Была создана функция "generateData" (см. Приложение).

Она принимает на вход массив функций (теперь уже имеются ввиду математические функции) и два целых числа - m и n. m означает количество признаков в каждой группе (группы одинакового размера), n - количество наблюдений. Тогда количество всех признаков (далее оно обозначается r) равно произведению размера массива функций и m. Затем создается матрица из нулей размера r?n. Заполнение этой матрицы происходит следующим образом. Первая строка матрицы заполняется случайными величинами (правильнее сказать, их реализациями), имеющими усеченное стандартное нормальное распределение. Вторая строка матрицы получается применением первой функции из массива к первой строке, третья - применением первой функции ко второй строке и так далее до m-ой строки. На данный момент мы задали значения всех признаков первой группы. (m+1)-я строка матрицы заполняется опять усеченными стандартными нормальными случайными величинами и все действия повторяются для следующих m строк. Теперь мы задали значения признаков второй группы. И так далее, пока не заполним все строки матрицы. После этого добавляем к каждому элементу матрицы нормально распределенную случайную величину с нулевым математическим ожиданием и дисперсией, равной 0.01, т.е. добавляем к нашим данным шум.

Отметим, что с помощью одного вызова функции "generateData" можно смоделировать сразу несколько групп взаимно зависимых признаков, в то время как одним вызовом функции "generateCorr" моделируется только одна такая группа.

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

Для генерации случайных величин, имеющих усеченное стандартное нормальное распределение, автором была создана функция "randn_cut" (см. Приложение). Эта функция работает следующим образом. На вход принимаются два целых числа a и b. Затем создается матрица размера a?b, заполненная стандартными нормальными случайными величинами. (Это делается с помощью встроенной в Матлаб функции "randn(a,b)"). Затем те элементы матрицы, значения которых оказались больше единицы или меньше минус единицы (т.е. попали в выбросы нормального распределения), заменяются на новые стандартные нормальные случайные величины. Затем такое же замещение происходит с новой матрицей.

И так до тех пор, пока все элементы не будут лежать в интервале от минус единицы до единицы. (С вероятностью 1 это условие в какой-то момент окажется выполненным).

...

Подобные документы

  • Основные понятия математической статистики, интервальные оценки. Метод моментов и метод максимального правдоподобия. Проверка статистических гипотез о виде закона распределения при помощи критерия Пирсона. Свойства оценок, непрерывные распределения.

    курсовая работа [549,1 K], добавлен 07.08.2013

  • Цель и задачи статистического анализа. Методы получения оценок: максимального правдоподобия, моментов. Доверительный интервал. Точечная оценка параметров распределения. Генеральная и выборочная дисперсии. Интервальное оценивание математического ожидания.

    презентация [395,9 K], добавлен 19.07.2015

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

    контрольная работа [62,6 K], добавлен 20.02.2011

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

    курсовая работа [330,2 K], добавлен 25.11.2011

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

    реферат [99,0 K], добавлен 07.04.2015

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

    презентация [710,3 K], добавлен 01.11.2013

  • Приближенные решения кубических уравнений. Работы Диофанта, Ферма и Ньютона. Интерационный метод нахождения корня уравнения. Геометрическое и алгебраическое описания метода хорд. Погрешность приближенного решения. Линейная скорость сходимости метода.

    презентация [255,1 K], добавлен 17.01.2011

  • Теория вероятности – математическая наука, изучающая закономерности в случайных явлениях. Метод наибольшего правдоподобия. Доверительные оценки. Точечные оценки и критерий согласия. Теорема Чебышева. Распределение Пуассона. Доверительный интервал.

    курсовая работа [349,0 K], добавлен 16.01.2009

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

    реферат [140,2 K], добавлен 27.03.2012

  • Математические модели явлений или процессов. Сходимость метода простой итерации. Апостериорная оценка погрешности. Метод вращений линейных систем. Контроль точности и приближенного решения в рамках прямого метода. Метод релаксации и метод Гаусса.

    курсовая работа [96,7 K], добавлен 13.04.2011

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

    методичка [122,0 K], добавлен 01.07.2009

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

    презентация [113,3 K], добавлен 01.11.2013

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

    дипломная работа [964,9 K], добавлен 09.06.2019

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

    курсовая работа [228,5 K], добавлен 30.01.2012

  • Определение линейного оператора. Норма линейного оператора. Обратные операторы. Абстрактные функции. Аналитические абстрактные функции и ряды Тейлора. Метод малого параметра в простейшем случае. Метод малого параметра в общем случае.

    дипломная работа [206,5 K], добавлен 08.08.2007

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

    курсовая работа [1,2 M], добавлен 30.09.2012

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

    курс лекций [81,2 K], добавлен 06.03.2009

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

    курсовая работа [209,1 K], добавлен 27.04.2011

  • Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик.

    реферат [224,1 K], добавлен 09.10.2012

  • Основные понятия аксиоматической теории. Аксиоматический метод – фундаментальнейший метод организации и умножения научного знания в самых разных его областях. Этапы развития аксиоматического метода в науке. Евклидова система обоснования геометрии.

    курсовая работа [28,9 K], добавлен 12.05.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.