Викиконспекты - Вклад участника [ru]

Алгоритм Левита

2013-10-20T19:48:56Z

Никита:

'''Алгоритм Левита''' (Levit algorithm) находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
<tex>M_1^{''}</tex>.push(v)
relax(uv)

<tex>M_0</tex>.add(u)

== Сложность ==

В худшем случае алгоритм Левита работает за <tex>\bf O(|V| \cdot 2^{|V|})</tex>. Это происходит вследствие того, что некоторые вершины приходится обрабатывать повторно. Однако эксперементы показывают, что для реальных графов(например, карт дорог) данный алгоритм оказывается достаточно быстрым и '''эксперементальная''' оценка данного алгоритма составляет <tex>\bf O(|E| \cdot log |V|)</tex>.

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T18:29:17Z

Никита: /* Псевдокод */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
<tex>M_1^{''}</tex>.push(v)
relax(uv)

<tex>M_0</tex>.add(u)

== Сложность ==

В худшем случае алгоритм Левита работает за <tex>\bf O(|V| \cdot 2^{|V|})</tex>. Это происходит вследствие того, что некоторые вершины приходится обрабатывать повторно. Однако эксперементы показывают, что для реальных графов(например, карт дорог) данный алгоритм оказывается достаточно быстрым и '''эксперементальная''' оценка данного алгоритма составляет <tex>\bf O(|E| \cdot log |V|)</tex>.

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T16:36:58Z

Никита: /* Сложность */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Сложность ==

В худшем случае алгоритм Левита работает за <tex>\bf O(|V| \cdot 2^{|V|})</tex>. Это происходит вследствие того, что некоторые вершины приходится обрабатывать повторно. Однако эксперементы показывают, что для реальных графов(например, карт дорог) данный алгоритм оказывается достаточно быстрым и '''эксперементальная''' оценка данного алгоритма составляет <tex>\bf O(|E| \cdot log |V|)</tex>.

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T16:08:23Z

Никита: /* Сложность */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Сложность ==

В худшем случае алгоритм Левита работает за <tex>\bf O(|V| \cdot 2^{|V|})</tex>. Это происходит вследствие того, что некоторые вершины приходится обрабатывать повторно. Однако эксперементы показывают, что для реальных графов(например, карт дорог) данный алгоритм оказывается достаточно быстрым. Эксперементальная оценка данного алгоритма составляет <tex>\bf O(|E| \cdot log |V|)</tex>.

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T15:03:39Z

Никита: /* Сложность */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Сложность ==

В худшем случае алгоритм Левита работает за <tex>\bf O(|V| * 2^{|V|})</tex>. Это происходит вследствие того, что некоторые вершины приходится обрабатывать повторно. Однако эксперементы показывают, что для реальных графов(например, карт дорог) данный алгоритм оказывается достаточно быстрым. Эксперементальная оценка данного алгоритма составляет <tex>\bf O(|E| \cdot log |V|)</tex>.

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T11:55:27Z

Никита:

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Сложность ==

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T11:53:54Z

Никита:

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Корректность ==

== Сложность ==

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T11:28:37Z

Никита: /* Источники */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Данный алгоритм является модификацией [[Алгоритм Дейкстры|алгоритмы Дейкстры]], которая позволяет работать с ребрами отрицательного веса.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Корректность ==

== Сложность ==

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0 Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, Дискретный анализ, ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T11:27:48Z

Никита: /* Источники */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Данный алгоритм является модификацией [[Алгоритм Дейкстры|алгоритмы Дейкстры]], которая позволяет работать с ребрами отрицательного веса.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Корректность ==

== Сложность ==

== См. также ==

* [[Алгоритм A*]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Джонсона]]
* [[Алгоритм Флойда]]
* [[Алгоритм Форда-Беллмана]]

== Источники ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B8%D1%82%D0%B0: Алгоритм Левита - Википедия, свободная энциклопедия]
* [http://e-maxx.ru/algo/levit_algorithm: Алгоритм Левита - MAXimal::algo]
* И. В. Романовский, '''Дискретный анализ''', ISBN 5-7940-0138-0; 2008 г., стр. 228-234.

Алгоритм Левита

2013-10-19T11:17:56Z

Никита: /* См. также */

Алгоритм Левита

2013-10-19T11:15:57Z

Никита:

Алгоритм Левита

2013-10-19T11:14:21Z

Никита: /* Псевдокод */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Данный алгоритм является модификацией [[Алгоритм Дейкстры|алгоритмы Дейкстры]], которая позволяет работать с ребрами отрицательного веса.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>
В конце шага помещаем вершину <tex>u</tex> в множество <tex>M_0</tex>.

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

'''for''' u <tex>\in</tex> V ''':'''
<tex>d_v \gets</tex> <tex>\infty</tex>
<tex>d_s \gets 0</tex>

<tex>M_1^{''}</tex>.add(s)
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
<tex>M_2</tex>.add(u)

'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
'''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
'''else :'''
u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()

'''for''' uv <tex>\in</tex> E ''':'''
'''if''' v <tex>\in M_2</tex> ''':'''
<tex>M_1^{'}</tex>.push(v)
relax(uv)
'''if''' v <tex>\in M_1</tex> ''':'''
relax(uv)
'''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
relax(uv)
<tex>M_1^{''}</tex>.push(v)

<tex>M_0</tex>.add(u)

== Сложность ==

== См. также ==

== Источники ==

Алгоритм Левита

2013-10-19T11:02:16Z

Никита: /* Алгоритм */

Алгоритм Левита

2013-10-19T10:47:09Z

Никита:

Алгоритм Левита

2013-10-19T10:44:36Z

Никита: /* Алгоритм */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Работает с ребрами отрицательного веса.

== Алгоритм ==

Пусть <tex>d_i</tex> {{---}} текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i \gets \infty</tex>; <tex>d_s \gets 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> {{---}} вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> {{---}} вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на два упорядоченных подмножества:
# <tex>M_1^{'}</tex> {{---}} основная очередь
# <tex>M_1^{''}</tex> {{---}} срочная очередь
* <tex>M_2</tex> {{---}} вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

'''Шаг алгоритма:''' выбирается вершина <tex>u</tex> из <tex>M_1</tex>. Если подмножество <tex>M_1^{''}</tex> не пусто, то вершина берется из него, иначе из <tex>M_1^{'}</tex>. Далее, для каждого ребра <tex>uv \in E</tex>:
* если <tex>v \in M_2</tex>, то <tex>v</tex> переводится в конец очереди <tex>M_1^{'}</tex>. При этом <tex>d_v \gets d_u + w_{uv}</tex>
* если <tex>v \in M_1</tex>, то происходит релаксация ребра <tex>uv</tex>
* если <tex>v \in M_0</tex> и <tex>d_v > d_u + w_{uv}</tex>, то происходит релаксация ребра <tex>uv</tex> и <tex>v</tex> помещается в <tex>M_1^{''}</tex>

Алгоритм заканчивает работу, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

== Сложность ==

== См. также ==

== Источники ==

Алгоритм Левита

2013-10-19T10:44:12Z

Никита: /* Алгоритм */

Алгоритм Левита

2013-10-19T10:08:06Z

Никита: /* Алгоритм */

Алгоритм Левита

2013-10-19T08:57:08Z

Никита: /* Алгоритм */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Работает с ребрами отрицательного веса.

== Алгоритм ==

Пусть <tex>d_i</tex> - текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i = \infty</tex>; <tex>d_s = 0</tex>.

Разделим вершины на три множества:
* <tex>M_0</tex> - вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> - вершины, расстояние до которых вычисляется
* <tex>M_2</tex> - вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

На каждом шаге выбирается вершина <tex>u</tex> из множества <tex>M_1</tex>. Переводим эту вершину во множество <tex>M_0</tex>. Для каждого ребра <tex>uv</tex>:
* если <tex>v \in M_2</tex>, то переносим <tex>v</tex> в <tex>M_1</tex> и релаксируем ребро <tex>uv</tex>
* если <tex>v \in M_1</tex>, то релаксируем ребро <tex>uv</tex>
* если <tex>c \in M_0</tex>, то переносим <tex>v</tex> в <tex>M_1</tex> и релаксируем ребро <tex>uv</tex>

Алгоритм завершается, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

== Сложность ==

== См. также ==

== Источники ==

Алгоритм Левита

2013-10-19T08:56:43Z

Никита: /* Алгоритм */

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Работает с ребрами отрицательного веса.

== Алгоритм ==

Пусть <tex>d_i</tex> - текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i = \infty</tex>; <tex>d_s = 0</tex>.

Разделим вершины на три '''множества''':
* <tex>M_0</tex> - вершины, расстояние до которых уже вычислено(возможно, не окончательно)
* <tex>M_1</tex> - вершины, расстояние до которых вычисляется
* <tex>M_2</tex> - вершины, расстояние до которых не вычисленно

Изначально все вершины, кроме <tex>s</tex> помещаются в множество <tex>M_2</tex>. Вершина <tex>s</tex> помещается в множество <tex>M_1</tex>.

На каждом шаге выбирается вершина <tex>u</tex> из множества <tex>M_1</tex>. Переводим эту вершину во множество <tex>M_0</tex>. Для каждого ребра <tex>uv</tex>:
* если <tex>v \in M_2</tex>, то переносим <tex>v</tex> в <tex>M_1</tex> и релаксируем ребро <tex>uv</tex>
* если <tex>v \in M_1</tex>, то релаксируем ребро <tex>uv</tex>
* если <tex>c \in M_0</tex>, то переносим <tex>v</tex> в <tex>M_1</tex> и релаксируем ребро <tex>uv</tex>

Алгоритм завершается, когда множество <tex>M_1</tex> становится пустым.

== Псевдокод ==

== Сложность ==

== См. также ==

== Источники ==

Алгоритм Левита

2013-10-19T07:44:04Z

Никита: Создание статьи

'''Алгоритм Левита''' находит расстояние от заданной вершины <tex>s</tex> до всех остальных. Работает с ребрами отрицательного веса.

== Алгоритм ==

== Псевдокод ==

== Сложность ==

== См. также ==

== Источники ==

Независимость определителя оператора от базиса. Теорема умножения определителей

2013-06-15T04:41:14Z

Никита:

{{Лемма
|about = <tex>*</tex>
|statement=
<tex> \mathcal{A}^{\wedge_p} {e_{i_1}} \land {e_{i_2}} \land ... \land {e_{i_p}} \stackrel{\mathrm{def}}{=} \mathcal{A}{e_{i_1}} \land \mathcal{A}{e_{i_2}} \land... \land \mathcal{A}{e_{i_p}} </tex>
}}

{{Лемма
|about = <tex>**</tex>
|statement=
Если <tex> {x_1} \land {x_2} \land... \land {x_p} \in {\wedge_p} </tex>, то <tex> \mathcal{A}^{\wedge_p} {x_1} \land {x_2} \land ... \land {x_p} = \mathcal{A}{x_1} \land \mathcal{A}{x_2} \land... \land \mathcal{A}{x_p} </tex>
}}

{{Лемма
|about = <tex>***</tex>
|statement=
<tex> \mathcal{A}^{\wedge_n} z = \det \mathcal{A} \cdot z </tex>
}}

{{Теорема
|statement=
Пусть <tex>\mathcal{A}</tex>, <tex>\mathcal{B} \colon X \to X</tex> (автоморфизм). Тогда <tex>\det (\mathcal{A} \cdot \mathcal{B}) = \det \mathcal{A} \cdot \det \mathcal{B}</tex>
|proof =
<tex>\det (\mathcal{A} \cdot \mathcal{B}) {e_1} \land {e_2} \land... \land{e_n} = </tex> <tex>
(\mathcal{A} \cdot \mathcal{B})^{\wedge_n}{e_1} \land {e_2} \land... \land{e_n} \stackrel{\mathrm{(*)}}{=}</tex> <tex>
(\mathcal{A} \cdot \mathcal{B}) {e_1} \land (\mathcal{A} \cdot \mathcal{B}) {e_2} \land ... \land (\mathcal{A} \cdot \mathcal{B}) {e_n} \stackrel{\mathrm{(def\mathcal{A} \cdot \mathcal{B})}}{=}</tex> <tex>
\mathcal{A} (\mathcal{B} {e_1}) \land \mathcal{A} (\mathcal{B} {e_2}) \land ... \land \mathcal{A} (\mathcal{B} {e_n}) \stackrel{\mathrm{(**)}}{=}</tex> <tex>
\mathcal{A}^{\wedge_n}(\mathcal{B} {e_1} \land \mathcal{B} {e_2} \land ... \land \mathcal{B} {e_n})\stackrel{\mathrm{(***)}}{=}</tex> <tex>
\det \mathcal{A} \cdot (\mathcal{B} {e_1} \land \mathcal{B} {e_2} \land ... \land \mathcal{B} {e_n}) \stackrel{\mathrm{(***)}}{=}</tex> <tex>
\det \mathcal{A} \cdot \mathcal{B}^{\wedge_n}({e_1} \land {e_2} \land ... \land {e_n}) = </tex> <tex>
\det \mathcal{A} \cdot \det \mathcal{B} \cdot {e_1} \land {e_2} \land ... \land {e_n} </tex> 
т.е. <tex> \det (\mathcal{A} \cdot \mathcal{B}) {e_1} \land {e_2} \land... \land{e_n} = </tex> <tex>
\det \mathcal{A} \cdot \det \mathcal{B} \cdot {e_1} \land {e_2} \land ... \land {e_n}
</tex>

}}
{{Утверждение
|statement=
'''Следствие 1: ''' 
Пусть <tex>\mathcal{A} \colon X \to X</tex> обратим, т.е. <tex>(\exists \mathcal{A}^{-1}) </tex> <tex>
\det \mathcal{A} \ne 0 </tex> 
Тогда: <tex>\mathcal{A}^{-1} = (\det \mathcal{A})^{-1} </tex>
|proof=
<tex>\mathcal{A}^{-1} \cdot \mathcal{A} = \mathcal{I} \det (\mathcal{A}^{-1} \cdot \mathcal{A}) = </tex> <tex>
\det \mathcal{A}^{-1} \cdot \det \mathcal{A} = \det \mathcal{I} = 1 (\det {E} = 1) </tex> 
Итого: <tex> \det \mathcal{A}^{-1} = (\det \mathcal{A})^{-1} </tex>
}}
{{Утверждение
|statement=
'''Следствие 2: ''' 
Пусть <tex>\tilde{A} = T^{-1}AT</tex> 
Тогда <tex> \det \tilde{A} = \det A </tex> 
<tex> \det \tilde{A} = \det T \det A \det T^{-1} = \det A </tex>
}}

Замена базиса

2013-06-14T19:11:06Z

Никита: /* Преобразование сопряженного базиса */

== Матрица перехода к новому базису ==

<tex>\{e_i\}_{i=0}^n \xrightarrow{\ T\ } \{\tilde{e}_k\}_{k=0}^n,</tex> где <tex>\tilde{e}_k = \sum\limits_{j=1}^n \tau^i_k e_i</tex>

<tex>T = ||\tau^i_k||</tex>

{{Определение
|definition= Заданная матрица <tex>T</tex> называется матрицей перехода от базиса <tex>e_i</tex> к базису <tex>\tilde{e}_k</tex>
}}

{{Теорема
|statement = <tex>T</tex> {{---}} невырожденная матрица <tex>(det T \ne 0)</tex>
|proof= Столбцы матрицы линейно независимы <tex>\Rightarrow Rg T = n \Rightarrow det T \ne 0</tex>
}}

Тогда <tex>\exists S = T^{-1} (</tex> далее <tex>S = ||\sigma^i_k||)</tex>

'''Итого:''' <tex>\{e_i\}_{i=0}^n \overset{T}{\underset{T^{-1}}{\longleftrightarrow}} \{\tilde{e}_k\}_{k=0}^n</tex>

== Преобразование сопряженного базиса ==

<tex> \{e_i\}_{i=0}^{n} </tex> {{---}} базис <tex>X ; \quad \{f^j\}_{j=0}^{n} </tex> {{---}} базис <tex>X^*</tex>

<tex> (f^j; e_i) = \delta^j_i</tex>

{{Теорема
|statement = <tex> \{f^j\}_{j=0}^n \overset{T^{-1}}{\underset{T}{\longleftrightarrow}} \{\tilde{f}^k\}_{k=0}^n</tex>
|proof=
<tex> \tilde{f}^k \overset{!}{=} \sum\limits_{j = 1}^{n} \beta^k_j f^i</tex>

Пусть <tex>B</tex> {{---}} матрица перехода от <tex>f^j</tex> к <tex>\tilde{f}^k</tex>

Рассмотрим <tex>\delta^k_i = (\tilde{f}^k; \tilde{e}_i) = (\sum\limits_{j=1}^n \beta^k_j f^j; \sum\limits_{s=1}^n \tau^s_i e_s) =
\sum\limits_{j, s} \beta^k_j \tau^s_i (f^j; e_s) = \sum\limits_{j=1}^n \beta^k_j \tau^j_i \delta^k_i</tex>

Получается, что <tex>B \cdot T = E \Rightarrow B = T^{-1} = S</tex>
}}

== Преобразование координат векторов <tex>X</tex> и <tex>X^*</tex> ==

[[Категория: Алгебра и геометрия 1 курс]]

Замена базиса

2013-06-14T18:23:17Z

Никита: /* Преобразование сопряженного базиса */

Пространство линейных операторов

2013-06-14T18:13:14Z

Никита:

Рассмотрим <tex>X \times Y = \{</tex> все Л.О. <tex>\mathcal{A} \colon X \to Y\}</tex> 

{{Определение
|definition= Пусть <tex>\mathcal{A}, \mathcal{B} \colon X \to Y;\quad \mathcal{A}, \mathcal{B} \in X \times Y</tex> 

Отображение <tex>\mathcal{C}</tex> называется суммой <tex>\mathcal{A}</tex> и <tex>\mathcal{B}\ (\mathcal{C} = \mathcal{A} + \mathcal{B})</tex>, если <tex>\forall x \in X \colon \mathcal{C}x = \mathcal{A}x + \mathcal{B}x</tex>
}}

{{Определение
|definition= Пусть <tex>\mathcal{A} \colon X \to Y;\quad \mathcal{A} \in X \times Y</tex> 
Отображение <tex>\mathcal{D}</tex> называется произведением <tex>\mathcal{A}</tex> на число <tex>\lambda\ (\mathcal{D} = \mathcal{A} \cdot \lambda)</tex>, если <tex>\forall x \in X \colon \mathcal{D}x = \lambda \mathcal{A}x</tex>
}}

{{Лемма
|statement=<tex>\mathcal{C}</tex> и <tex>\mathcal{D}</tex> {{---}} суть(являются) линейные операторы
|proof = Покажем, что:
# <tex>\mathcal{C}(x_1 + x_2) = \mathcal{C}x_1 + \mathcal{C}x_2</tex>
# <tex>\mathcal{C}(\lambda x) = \lambda \mathcal{C}x</tex>

Аналогично, покажем то же самое для <tex>\mathcal{D}</tex>
}}

{{Теорема
|statement = <tex>X \times Y</tex> {{---}} линейное пространство над полем <tex>F</tex>
|proof= Проверим все 8 аксиом лп. Все они будут выполняться:
# <math>\mathbf{x} + \mathbf{y} = \mathbf{y} + \mathbf{x}</math>, для любых <math>\mathbf{x}, \mathbf{y}\in X \times Y</math> (''коммутативность сложения'');
# <math>\mathbf{x} + (\mathbf{y} + \mathbf{z}) = (\mathbf{x} + \mathbf{y}) + \mathbf{z}</math>, для любых <math>\mathbf{x}, \mathbf{y}, \mathbf{z} \in X \times Y</math> (''ассоциативность сложения'');
# существует такой элемент <math>\theta \in X \times Y</math>, что <math>\mathbf{x} + \theta = \mathbf{x}</math> для любого <math>\mathbf{x} \in X \times Y</math> (''существование нейтрального элемента относительно сложения''), в частности <math>X \times Y</math> не пусто;
# для любого <math>\mathbf{x} \in X \times Y</math> существует такой элемент <math>-\mathbf{x} \in X \times Y</math>, что <math>\mathbf{x} + (-\mathbf{x}) = \theta</math> (''существование противоположного элемента относительно сложения'').
# <math>\alpha(\beta\mathbf{x}) = (\alpha\beta)\mathbf{x}</math> (''ассоциативность умножения на скаляр'');
# <math>1\cdot\mathbf{x} = \mathbf{x}</math> (''унитарность: умножение на нейтральный (по умножению) элемент поля F сохраняет вектор'').
# <math>(\alpha + \beta)\mathbf{x} = \alpha \mathbf{x} + \beta \mathbf{x}</math> (''дистрибутивность умножения на вектор относительно сложения скаляров'');
# <math>\alpha(\mathbf{x} + \mathbf{y}) = \alpha \mathbf{x} + \alpha \mathbf{y}</math>(''дистрибутивность умножения на скаляр относительно сложения векторов'').

}}

{{Определение
|definition= <tex>X \times Y</tex> называется прямым произведением пространств <tex>X</tex> и <tex>Y</tex>
}}

{{Лемма
|statement= Пусть <tex>\mathcal{A} \leftrightarrow A</tex>, <tex>\mathcal{B} \leftrightarrow B</tex>, <tex>\mathcal{C} \leftrightarrow C</tex>, <tex>\mathcal{D} \leftrightarrow D</tex>
<tex> \mathcal{C} = \mathcal{A} + \mathcal{C}</tex>,
<tex> \mathcal{D} = \lambda \mathcal{A}</tex>

Тогда: <tex>C = A + B;\quad D = \lambda A</tex>
}}

{{Теорема
|statement = Пусть <tex>F_n^m = \{</tex> все матрицы <tex>A_{[m \times n]} = \begin{Vmatrix} \alpha^i_k \end{Vmatrix},\ \alpha^i_k \in F \}</tex> 
<tex>X \times Y</tex> изоморфно <tex>F_n^m</tex>
|proof=
<tex> \mathcal{A} \overset{\underset{\mathrm{!}}{}}{\longleftrightarrow} A</tex> (единственным образом)

<tex> \{e_i\}_{i=0}^{n}</tex> {{---}} базис <tex>X ;\quad \{h_k\}_{k=0}^{m}</tex> {{---}} базис <tex>Y</tex>

Рассмотрим <tex>\mathcal{E}_k^i \colon X \to Y </tex> по формуле <tex>\mathcal{E}_k^i x \overset{\underset{\mathrm{def}}{}}{=} \xi^{i} h_k; \quad x \overset{\underset{\mathrm{!}}{}}{=} \sum\limits_{i=0}^{n} \xi^i e_i</tex>

Матрица <tex>\mathcal{E}^i_k e_j = \delta^i_j h_k</tex>

<tex>e_j = \begin{pmatrix}
0 \\
\vdots \\
1 \\
\vdots \\
0
\end{pmatrix} \leftarrow j</tex>

<tex>\mathcal{E}^i_k \longleftrightarrow E^i_k = \begin{pmatrix}
0 & \cdots & 0 & \cdots & 0 \\
\vdots & \ & \vdots & \ & \vdots \\
0 & \cdots & 1 & \cdots & 0 \\
\vdots & \ & \vdots & \ & \vdots \\
0 & \cdots & 0 & \cdots & 0 \\
\end{pmatrix} \leftarrow h_k \\
</tex>

Базис <tex>F_n^m</tex> состоит из таких же матриц
}}

{{Теорема
|statement = <tex>\{\mathcal{E}^i_k\}^{i = \overline{1, n}}_{k = \overline{1, m}}\ </tex> {{---}} базис <tex>X \times Y</tex>
}}

== Ссылки ==
* [[Линейный оператор]]

== Источники ==
* Анин конспект

[[Категория: Алгебра и геометрия 1 курс]]
[[Категория: Линейные операторы]]

Замена базиса

2013-06-14T18:06:14Z

Никита: /* Матрица перехода к новому базису */

Замена базиса

2013-06-14T17:32:08Z

Никита:

== Матрица перехода к новому базису ==

== Преобразование сопряженного базиса ==

== Преобразование координат векторов <tex>X</tex> и <tex>X^*</tex> ==

[[Категория: Алгебра и геометрия 1 курс]]

Пространство линейных операторов

2013-06-14T17:13:22Z

Никита:

Пространство линейных операторов

2013-06-14T16:34:21Z

Никита:

Пространство линейных операторов

2013-06-14T16:30:17Z

Никита:

Пространство линейных операторов

2013-06-14T15:15:50Z

Никита:

Собственные векторы и собственные значения

2013-06-14T00:16:54Z

Никита: /* Определения */

== Основные теоремы и определения ==

===Определения===
{{Определение
|id=def1.
|neat =
|definition=
Пусть <tex>\mathcal{A}\colon X \to X</tex> - линейный оператор (ЛО) 
<tex>x\ne 0_x</tex> называется '''собственным вектором''' <tex>\mathcal{A}</tex>, если <tex>x \in L</tex>, где <tex>L</tex> {{---}} [[Инвариантные подпространства | инвариантное подпространство]] <tex>\mathcal{A}</tex> и <tex>\dim L = 1</tex>
}}

{{Определение
|id=def2.
|neat =
|definition=
Пусть <tex>\mathcal{A}\colon X \to X</tex> <tex>x\ne 0_X</tex> называется '''собственным вектором''' <tex>\mathcal{A}</tex>, если существует <tex>\lambda \in F \colon \mathcal{A}x = \lambda x</tex>
}}

{{Лемма
|id=lemma1
|author=
|about=
|statement=
Предыдущие 2 определения эквивалентны.
|proof=
<math> (1) \Rightarrow (2) \colon x \in L, \dim L=1 \Rightarrow \mathcal{A}x \in L \ (</math>т. к. <math>x \ne 0_X \Rightarrow</math> базис <math>L = \{x\}) \Rightarrow \mathcal{A}x=\lambda x</math> (единственным образом) 
<tex> (1) \Leftarrow (2) \colon \exists \lambda: \mathcal{A}x = \lambda x \Rightarrow x \in</tex> одномерному подпространству <tex>L</tex>, где <tex>L =</tex> линейная оболочка <tex>\{x\}, \mathcal{A}x = \lambda x \in L</tex>
}}

{{Определение
|id=def3.
|neat =
|definition=
<tex>\lambda</tex> в равенстве <tex>\mathcal{A}x = \lambda x</tex> называется '''собственным числом (собственным значением)''' ЛО <tex>\mathcal{A}</tex>
}}

{{Определение
|id=def4.
|neat =
|definition=
'''Спектром''' <tex>\sigma</tex> ЛО называется множество всех его '''собственных значений''' 
<tex>\sigma (\mathcal{A}) = \sigma _\mathcal{A} = \{ \lambda _i \}</tex>
}}

// здесь мог быть пример, но думаю всем и так понятно

===Свойства===
{{Теорема
|id=th1.
|author=
|about=
|statement=
'''Собственные векторы''', отвечающие различным '''собственным значениям''' образуют ЛНЗ набор
|proof=
1) База: рассмотрим <tex>\lambda \leftrightarrow x_1 \ne 0_x\ \{x_1\}</tex> - ЛНЗ набор. 
2) <tex>\{x_1,x_2, ... , x_{m-1}\} \leftrightarrow \{\lambda _1, ... \lambda _ m-1 \}</tex> - ЛНЗ.
Рассмотрим <tex>\{x_1, ..., x_m \} </tex>- докажем, что тоже ЛНЗ.

<tex>\sum\limits_{i=1}^m \alpha^i x_i = 0 </tex>

<tex>\mathcal{A}( \sum\limits_{i=1}^m \alpha_i x_i) = \sum\limits_{i=1}^m \alpha_i Ax_i = \sum\limits_{i=1}^m \alpha_i \lambda_i x_i = 0_x</tex> (1)

<tex>\lambda_m( \sum\limits_{i=1}^m \alpha_i x_i) = \sum\limits_{i=1}^m \alpha_i \lambda_m x_i = 0_x</tex> (2)

(1) - (2) : <tex>\alpha_1(\lambda_1 - \lambda_m)x_1 + ... + \alpha_{m-1}(\lambda_{m-1} - \lambda_m)x_{m-1} + 0_x = 0_x</tex>

По предположению индукции <tex>\{x_1,x_2, ... , x_{m-1}\}</tex> - ЛНЗ <tex>\Rightarrow \alpha_1 (\lambda_1-\lambda_m)=0 ... \alpha_{m-1} (\lambda_{m-1} - \lambda_{m}) =0 </tex>, при этом все <tex>(\lambda_{i-1}-\lambda_m) \ne 0</tex>

<tex>\Rightarrow </tex> все <tex>\alpha_i = 0</tex> <tex>\Rightarrow \sum\limits_{i=1}^m \alpha_i x_i = 0_x</tex>

<tex>\Rightarrow \alpha_m x_m = 0_x </tex>, где <tex>x_m \ne 0_x</tex> <tex>\Rightarrow \alpha_m=0</tex>, т.е. набор ЛНЗ.
}}

{{Лемма
|id=lemma2.
|author=
|about=
|statement=
Множество всех собственных векторов, отвечающих одному и тому же собственному значению оператора <tex>\mathcal{A}</tex>, образует подпространство пространства <tex>X</tex>.
|proof=
1) Если <tex>x</tex> {{---}} св, то и <tex> \alpha x</tex> {{---}} тоже св.

2) Если <tex>x,y</tex> {{---}} св, то и <tex>x+y</tex> {{---}} тоже св.

Из 1 и 2 <tex>\Rightarrow</tex> что лемма доказана (по определению подпространства)

}}

{{Определение
|id=def45
|neat =
|definition=
<tex>L = </tex> линейная оболочка <tex>\{</tex> все СВ <tex> x_i \leftrightarrow \lambda_i \}</tex> называют собственным подпространством <tex>X \leftrightarrow</tex> СЗ <tex>\lambda_i</tex>
}}

{{Лемма
|id=lemma3.
|author=
|about=
|statement=
Пусть L - линейная оболочка<tex>\{ </tex> всех <tex>x_i \leftrightarrow \lambda_i\}</tex>
Пусть <tex>X_{\lambda i}</tex> - собственное подпространство X <tex>\leftrightarrow \lambda_i</tex>
Тогда <tex>L = X_{\lambda i}</tex>
|proof=
Сначала <tex>\subseteq</tex> потом <tex>\supseteq</tex> <tex>\Rightarrow</tex> доказательство (так в конспекте);
Вообще не понятно, зачем эта лемма, ибо она по определению.
}}

{{Лемма
|id=lemma4.
|author=
|about= (следствие из теоремы)
|statement=
У ЛО не может быть больше <tex>n</tex> СЗ, где <tex>n = dimX</tex>
|proof=
(идет как упражнение)
По теореме выше, набор собственных векторов - ЛНЗ набор. <tex>\Rightarrow</tex> их не больше чем размерность пространства, а <tex>dim X = n </tex>.
}}

== Поиск СЗ и СВ ==

<tex>x \ne 0_x</tex> и
<tex>\mathcal{A}x = \lambda x \Leftrightarrow \mathcal{A}x - \lambda \mathcal{I} x = 0 \Leftrightarrow (\mathcal{A} - \lambda \mathcal{I})X = 0 </tex>

<math dpi = "145">{C}= \begin{pmatrix}
({\alpha}_{1}^{1}- \lambda) \xi^1 & {\alpha}_{2}^{1} \xi^2 & \cdots & {\alpha}_{n}^{1} \xi^n \\
{\alpha}_{1}^{2} \xi^1 & ({\alpha}_{2}^{2}- \lambda) \xi^2 & \cdots & {\alpha}_{n}^{2} \xi^n \\
\vdots & \vdots & \ddots & \vdots \\
{\alpha}_{1}^{n} \xi^1 & {\alpha}_{2}^{n} \xi^2 & \cdots & ({\alpha}_{n}^{n}- \lambda) \xi^n \\
\end{pmatrix}</math>

Если <tex>det(A- \lambda E) \ne 0 \Rightarrow \exists </tex> тривиальное решение <tex>(0,0 ... ,0)^T</tex>

Если <tex>det(A- \lambda E) = 0 \Rightarrow \exists </tex> нетривиальное решение <tex>\Rightarrow \exists</tex> СВ <tex>x</tex>

<tex>\mathcal{X}_A (\lambda) = 0 </tex> - характеристический полином

<tex>det(A- \lambda E) = 0</tex> - уравнение на СЗ, а
<tex>det(A- \lambda E)X = 0</tex> - уравнение на СВ

Из уравнения на СЗ находим <tex>\{\lambda_i \}</tex> - корни характеристического полинома, они же - характеристические числа.

Затем подставляем каждую <tex>\lambda_i</tex> в уравнение на СВ по очереди на находим СВ <tex>x_i \leftrightarrow \lambda_i</tex>.

Так найдутся все СВ.

{{Теорема
|id=th2.
|author=
|about=
|statement=
Пусть <tex> \mathcal{A} : X \to X, X</tex> над С, тогда у <tex>\mathcal{A}</tex> есть хотя бы одно СЗ и один СВ.
|proof=
[http://ru.wikipedia.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D1%8B Основная теорема алгебры] гласит, что у <tex>\forall</tex> полинома комплексной переменной всегда есть корень.
}}

[[Категория: Алгебра и геометрия 1 курс]]

Собственные векторы и собственные значения

2013-06-14T00:16:19Z

Никита: /* Определения */

== Основные теоремы и определения ==

===Определения===
{{Определение
|id=def1.
|neat =
|definition=
Пусть <tex>\mathcal{A}\colon X \to X</tex> - линейный оператор (ЛО) 
<tex>x\ne 0_X</tex> называется '''собственным вектором''' <tex>\mathcal{A}</tex>, если <tex>x \in L</tex>, где <tex>L</tex> {{---}} [[Инвариантные подпространства | инвариантное подпространство]] <tex>\mathcal{A}</tex> и <tex>\dim L = 1</tex>
}}

{{Определение
|id=def2.
|neat =
|definition=
Пусть <tex>\mathcal{A}\colon X \to X</tex> <tex>x\ne 0_X</tex> называется '''собственным вектором''' <tex>\mathcal{A}</tex>, если существует <tex>\lambda \in F \colon \mathcal{A}x = \lambda x</tex>
}}

{{Лемма
|id=lemma1
|author=
|about=
|statement=
Предыдущие 2 определения эквивалентны.
|proof=
<math> (1) \Rightarrow (2) \colon x \in L, \dim L=1 \Rightarrow \mathcal{A}x \in L \ (</math>т. к. <math>x \ne 0_X \Rightarrow</math> базис <math>L = \{x\}) \Rightarrow \mathcal{A}x=\lambda x</math> (единственным образом) 
<tex> (1) \Leftarrow (2) \colon \exists \lambda: \mathcal{A}x = \lambda x \Rightarrow x \in</tex> одномерному подпространству <tex>L</tex>, где <tex>L =</tex> линейная оболочка <tex>\{x\}, \mathcal{A}x = \lambda x \in L</tex>
}}

{{Определение
|id=def3.
|neat =
|definition=
<tex>\lambda</tex> в равенстве <tex>\mathcal{A}x = \lambda x</tex> называется '''собственным числом (собственным значением)''' ЛО <tex>\mathcal{A}</tex>
}}

{{Определение
|id=def4.
|neat =
|definition=
'''Спектром''' <tex>\sigma</tex> ЛО называется множество всех его '''собственных значений''' 
<tex>\sigma (\mathcal{A}) = \sigma _\mathcal{A} = \{ \lambda _i \}</tex>
}}

// здесь мог быть пример, но думаю всем и так понятно

===Свойства===
{{Теорема
|id=th1.
|author=
|about=
|statement=
'''Собственные векторы''', отвечающие различным '''собственным значениям''' образуют ЛНЗ набор
|proof=
1) База: рассмотрим <tex>\lambda \leftrightarrow x_1 \ne 0_x\ \{x_1\}</tex> - ЛНЗ набор. 
2) <tex>\{x_1,x_2, ... , x_{m-1}\} \leftrightarrow \{\lambda _1, ... \lambda _ m-1 \}</tex> - ЛНЗ.
Рассмотрим <tex>\{x_1, ..., x_m \} </tex>- докажем, что тоже ЛНЗ.

<tex>\sum\limits_{i=1}^m \alpha^i x_i = 0 </tex>

<tex>\mathcal{A}( \sum\limits_{i=1}^m \alpha_i x_i) = \sum\limits_{i=1}^m \alpha_i Ax_i = \sum\limits_{i=1}^m \alpha_i \lambda_i x_i = 0_x</tex> (1)

<tex>\lambda_m( \sum\limits_{i=1}^m \alpha_i x_i) = \sum\limits_{i=1}^m \alpha_i \lambda_m x_i = 0_x</tex> (2)

(1) - (2) : <tex>\alpha_1(\lambda_1 - \lambda_m)x_1 + ... + \alpha_{m-1}(\lambda_{m-1} - \lambda_m)x_{m-1} + 0_x = 0_x</tex>

По предположению индукции <tex>\{x_1,x_2, ... , x_{m-1}\}</tex> - ЛНЗ <tex>\Rightarrow \alpha_1 (\lambda_1-\lambda_m)=0 ... \alpha_{m-1} (\lambda_{m-1} - \lambda_{m}) =0 </tex>, при этом все <tex>(\lambda_{i-1}-\lambda_m) \ne 0</tex>

<tex>\Rightarrow </tex> все <tex>\alpha_i = 0</tex> <tex>\Rightarrow \sum\limits_{i=1}^m \alpha_i x_i = 0_x</tex>

<tex>\Rightarrow \alpha_m x_m = 0_x </tex>, где <tex>x_m \ne 0_x</tex> <tex>\Rightarrow \alpha_m=0</tex>, т.е. набор ЛНЗ.
}}

{{Лемма
|id=lemma2.
|author=
|about=
|statement=
Множество всех собственных векторов, отвечающих одному и тому же собственному значению оператора <tex>\mathcal{A}</tex>, образует подпространство пространства <tex>X</tex>.
|proof=
1) Если <tex>x</tex> {{---}} св, то и <tex> \alpha x</tex> {{---}} тоже св.

2) Если <tex>x,y</tex> {{---}} св, то и <tex>x+y</tex> {{---}} тоже св.

Из 1 и 2 <tex>\Rightarrow</tex> что лемма доказана (по определению подпространства)

}}

{{Определение
|id=def45
|neat =
|definition=
<tex>L = </tex> линейная оболочка <tex>\{</tex> все СВ <tex> x_i \leftrightarrow \lambda_i \}</tex> называют собственным подпространством <tex>X \leftrightarrow</tex> СЗ <tex>\lambda_i</tex>
}}

{{Лемма
|id=lemma3.
|author=
|about=
|statement=
Пусть L - линейная оболочка<tex>\{ </tex> всех <tex>x_i \leftrightarrow \lambda_i\}</tex>
Пусть <tex>X_{\lambda i}</tex> - собственное подпространство X <tex>\leftrightarrow \lambda_i</tex>
Тогда <tex>L = X_{\lambda i}</tex>
|proof=
Сначала <tex>\subseteq</tex> потом <tex>\supseteq</tex> <tex>\Rightarrow</tex> доказательство (так в конспекте);
Вообще не понятно, зачем эта лемма, ибо она по определению.
}}

{{Лемма
|id=lemma4.
|author=
|about= (следствие из теоремы)
|statement=
У ЛО не может быть больше <tex>n</tex> СЗ, где <tex>n = dimX</tex>
|proof=
(идет как упражнение)
По теореме выше, набор собственных векторов - ЛНЗ набор. <tex>\Rightarrow</tex> их не больше чем размерность пространства, а <tex>dim X = n </tex>.
}}

== Поиск СЗ и СВ ==

<tex>x \ne 0_x</tex> и
<tex>\mathcal{A}x = \lambda x \Leftrightarrow \mathcal{A}x - \lambda \mathcal{I} x = 0 \Leftrightarrow (\mathcal{A} - \lambda \mathcal{I})X = 0 </tex>

<math dpi = "145">{C}= \begin{pmatrix}
({\alpha}_{1}^{1}- \lambda) \xi^1 & {\alpha}_{2}^{1} \xi^2 & \cdots & {\alpha}_{n}^{1} \xi^n \\
{\alpha}_{1}^{2} \xi^1 & ({\alpha}_{2}^{2}- \lambda) \xi^2 & \cdots & {\alpha}_{n}^{2} \xi^n \\
\vdots & \vdots & \ddots & \vdots \\
{\alpha}_{1}^{n} \xi^1 & {\alpha}_{2}^{n} \xi^2 & \cdots & ({\alpha}_{n}^{n}- \lambda) \xi^n \\
\end{pmatrix}</math>

Если <tex>det(A- \lambda E) \ne 0 \Rightarrow \exists </tex> тривиальное решение <tex>(0,0 ... ,0)^T</tex>

Если <tex>det(A- \lambda E) = 0 \Rightarrow \exists </tex> нетривиальное решение <tex>\Rightarrow \exists</tex> СВ <tex>x</tex>

<tex>\mathcal{X}_A (\lambda) = 0 </tex> - характеристический полином

<tex>det(A- \lambda E) = 0</tex> - уравнение на СЗ, а
<tex>det(A- \lambda E)X = 0</tex> - уравнение на СВ

Из уравнения на СЗ находим <tex>\{\lambda_i \}</tex> - корни характеристического полинома, они же - характеристические числа.

Затем подставляем каждую <tex>\lambda_i</tex> в уравнение на СВ по очереди на находим СВ <tex>x_i \leftrightarrow \lambda_i</tex>.

Так найдутся все СВ.

{{Теорема
|id=th2.
|author=
|about=
|statement=
Пусть <tex> \mathcal{A} : X \to X, X</tex> над С, тогда у <tex>\mathcal{A}</tex> есть хотя бы одно СЗ и один СВ.
|proof=
[http://ru.wikipedia.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D1%8B Основная теорема алгебры] гласит, что у <tex>\forall</tex> полинома комплексной переменной всегда есть корень.
}}

[[Категория: Алгебра и геометрия 1 курс]]

Пространство линейных операторов

2013-06-14T00:10:38Z

Никита:

Пространство линейных операторов

2013-06-13T02:26:00Z

Никита:

Линейный оператор

2013-06-13T01:27:10Z

Никита:

==Линейный оператор==
{{Определение
|definition=Пусть <tex>X</tex> и <tex>Y</tex> {{---}} линейные пространства над полем <tex>F</tex>. Отображение <tex>\mathcal{A} \colon X \to Y</tex> называется линейным оператором, если <tex>\forall x_1,x_2 \in X</tex>, <tex>\forall \lambda \in F</tex>:
* <tex>\mathcal{A}(x_1+x_2)=\mathcal{A}(x_1)+\mathcal{A}(x_2)</tex>
* <tex>\mathcal{A}(\lambda \cdot x_1) = \lambda \cdot \mathcal{A}(x_1)</tex>
}}

{{Определение
|definition=Линейный оператор <tex>\mathcal{A} \colon X \to X</tex> называется автоморфизмом (или гомоморфизмом).
}}
{{Nota Bene|notabene=<tex>\mathcal{A}(x) = \mathcal{A}x</tex>}}
{{Определение
|definition=Пусть <tex>\mathcal{A},\mathcal{B}\colon X \to Y</tex> 
<tex>\mathcal{A}=\mathcal{B}</tex>, если <tex>\forall x \in X:\mathcal{A}x = \mathcal{B}x</tex>
}}
{{Определение
|definition=<tex>\mathcal{O}</tex> называется нулевым оператором, если <tex>\forall x, y \in X : \mathcal{O}x=0_y</tex>
}}
== Примеры ==
=== Тождественный оператор ===
<tex>I \colon X \to X</tex> по формуле <tex>Ix=x</tex>

=== Линейный оператор проектирования ===
<tex>X=L_1 + L_2</tex>

<tex>\mathcal{P}_{L_1}^{||L_2} \colon X \to L_1</tex>

<tex>\mathcal{P}_{L_2}^{||L1} \colon X \to L_2</tex>

NB: <tex>\mathcal{P}_{L_{1,2}}^{||L_{2,1}}\colon X \to X</tex> (<tex>L_1</tex> и <tex>L_2</tex> {{---}} п.п. <tex>X</tex>)

=== Оператор дифференцирования ===
Пусть <tex>X=P_n</tex>

<tex>\mathcal{D} \colon P_n \to P_{n-1}</tex> по формуле <tex>(\mathcal{D}p)(t)={dp(t) \over dt} = p^{'}(t)</tex>

=== Интегральный оператор ===
Пусть <tex>X = C(a,b); K(s,t); s \in (a,b); t \in (a,b)</tex>

<tex>(\mathcal{B}f)(s) = \int_a^b K(s,t) \cdot f(t) \cdot dt</tex>

<tex>\mathcal{B} \colon C(a,b) \to C(a,b)</tex>

== Матрица линейного оператора ==
Пусть <tex>\mathcal{A} \colon X \to Y</tex>

Пусть п.п. <tex>X \leftrightarrow \{e_k\}_{k=1}^n, \dim X=n</tex>

Пусть п.п. <tex>Y \leftrightarrow \{h_i\}_{i=1}^m, \dim Y = m</tex>

<tex>\underset{1\leq k\leq n}{\mathcal{A}e_k}=\displaystyle \sum_{i=1}^m \alpha_k^i \cdot h_i \Rightarrow A=||\alpha_k^i||</tex>, где <tex>1\leq i\leq m, 1 \leq k \leq n</tex>

<tex>
A=
\begin{pmatrix}
\alpha_1^1 & \cdots & \alpha_n^1 \\
\alpha_1^2 & \cdots & \alpha_n^2 \\
\cdots & \cdots & \cdots \\
\alpha_1^m & \cdots & \alpha_n^m \\
\end{pmatrix}
</tex>

{{Nota Bene|notabene=Обратите внимание, что <tex>\mathcal{A}</tex> означает оператор, а <tex>A</tex> {{---}} матрицу этого оператора.}}

== Примеры ==
=== Нулевой оператор ===
<tex>
\mathcal{O}_{[m \times n]}=
\begin{pmatrix}
0 & \cdots & 0 \\
\cdots & \cdots & \cdots \\
0 & \cdots & 0 \\
\end{pmatrix}
</tex>

=== Оператор дифференцирования ===
<tex>\mathcal{D} \colon P_n \to P_{n-1}</tex>

<tex>\{1,t,t^2,...,t^n\}</tex> - базис <tex>P_n</tex>

<tex>
D=
\begin{pmatrix}
0 & 1 & 0 & 0 & \cdots & 0 \\
0 & 0 & 2 & 0 & \cdots & 0 \\
0 & 0 & 0 & 3 &\cdots & 0 \\
\cdots & \cdots & \cdots & \cdots &\cdots & \cdots \\
0 & 0 & 0 & 0 &\cdots & n \\
\end{pmatrix}
</tex>

==Теорема об эквивалентности задания линейного оператора==
{{Теорема
|statement=
Задание Л.О. <tex>\mathcal{A}: X \rightarrow Y \Leftrightarrow </tex> заданию его матрицы в паре базисов <tex>\{x_i\}_{i=1}^{n}</tex> и <tex>\{h_k\}_{k=1}^{m}</tex>
|proof=
<tex> \Rightarrow \mathcal{A} = \sum\limits_{k=1}^{m} \alpha_{k}^{i}h_k </tex> (единственным образом) <tex> \Rightarrow A=||\alpha_k^i||</tex>, где <tex>1\leq i\leq n, 1 \leq k \leq m</tex>

<tex> \Leftarrow x= \sum\limits_{i=1}^{n} \xi^i e_i </tex> (единственным образом)

Рассмотрим <tex>\mathcal{A}x= \mathcal{A}(\sum\limits_{i=1}^{n} \xi^ie_i)= \sum\limits_{i=1}^{n} \xi^i \mathcal{A}e_i= \sum\limits_{i=1}^{n} \xi^i \sum\limits_{k=1}^{m} \alpha_{i}^{k}h_k=\sum\limits_{k=1}^{m}(\sum\limits_{i=1}^{n} \alpha_{i}^{k} \xi^i)h_k </tex> (1)

<tex>\mathcal{A}x=y=\sum\limits_{k=1}^{m} \eta^kh_k </tex> (2)

из (1) и (2) получим, что <tex>\eta^k=\sum\limits_{i=1}^{n} \alpha_{i}^{k} \xi^i \Leftrightarrow A \cdot X= Y</tex> (умножение матриц), тогда <tex>\mathcal{A}x=y</tex>
}}

[[Категория: Алгебра и геометрия 1 курс]]

Ортогональные системы векторов

2013-06-12T22:13:57Z

Никита:

==Коэффициенты Фурье==
{{Определение
|definition=
Пусть <tex>{\{e_i\}}^k_{i=1}</tex> {{---}} ОРТН-система векторов.

Тогда числа <tex>\varphi_i = \left\langle x, e_i\right\rangle</tex> называются коэффициентами Фурье вектора <tex>x</tex> относительно системы <tex>{\{e_i\}}^k_{i=1}</tex>
}}
NB: <tex>\mathcal{P}^{\bot}_L x = \sum\limits_{i=1}^{k}\varphi_{i}e_{i}\;\;(k \le n = \dim E)</tex>

==Неравенство Бесселя==
{{Лемма
|statement=
<tex>{\Vert\mathcal{P}^{\bot}_L x\Vert}^2 = \sum\limits_{i=1}^k{|\varphi_{i}|}^2</tex>
|proof=
<tex>{\Vert\mathcal{P}^{\bot}_L x\Vert}^2 = \left\langle \mathcal{P}^{\bot}_L x; \mathcal{P}^{\bot}_L x\right\rangle =
\left\langle\sum\limits_{i=1}^{k}\varphi_{i}e_{i}; \sum\limits_{j=1}^{k}\varphi_{j}e_{j}\right\rangle =
\sum\limits_{i,j=1}^{k} \varphi_i\cdot\overline{\varphi_j}\left\langle e_i, e_j\right\rangle</tex>;

Т.к. у нас ОРТН-базис, то <tex>\left\langle e_i, e_j\right\rangle = \delta_{ij}</tex>, поэтому одно суммирование можно убрать:

<tex>\sum\limits_{i,j=1}^{k} \varphi_i\cdot\overline{\varphi_j}\left\langle e_i, e_j\right\rangle = \sum\limits_{i=1}^{k} \varphi_i\cdot\overline{\varphi_j} = \sum\limits_{i=1}^{k} {|\varphi_i|}^2</tex>
}}

{{Теорема
|about = неравенство Бесселя
|statement = <tex>\Vert x\Vert^2 \ge \sum\limits_{i=1}^{k} {|\varphi_i|}^2</tex>
|proof= Утверждается, что равенство напрямую следует из леммы
}}
==Равенство Парсеваля==
{{Теорема
|about= равенство Парсеваля
|statement= <tex>\Vert x\Vert^2 =\sum\limits_{i=1}^{k} {|\varphi_i|}^2 \Longleftrightarrow x\in L</tex>
|proof= Утверждается, что равенство напрямую следует из леммы
}}
{{Теорема
|statement=
Для того, чтобы ОРТН-система векторов <tex>{\{e_i\}}^k_{i=1}</tex> могла бы быть полной в евклидовом пространстве <tex>E</tex>, необходимо и достаточно, чтобы выполнялось равенство Парсеваля: <tex>\Vert x\Vert^2 =\sum\limits_{i=1}^{k} {|\varphi_i|}^2</tex>, где <tex>n=\dim E</tex>
|proof=
Достаточность: пусть <tex>n\ne\dim E</tex>, тогда т.к. <tex>{\{e_i\}}^k_{i=1}</tex> {{---}} ОРТН-система, то набор <tex>{\{e_i\}}^k_{i=1}</tex> {{---}} ЛНЗ(по определению ортонормированности), а значит он может быть полным, только если <tex>n=\dim L</tex>
Необходимость: полностью следует из равенства Парсеваля.
}}
[[Категория: Алгебра и геометрия 1 курс]]

Пространство линейных операторов

2013-06-12T21:59:25Z

Никита:

Пространство линейных операторов

2013-06-12T21:53:51Z

Никита:

Пространство линейных операторов

2013-06-12T21:18:23Z

Никита: Новая страница: «Рассмотрим <tex>X \times Y = \{</tex> все Л.О. <tex>\mathcal{A} \colon X \to Y\}</tex> {{Определение |definition= Пусть <tex>...»

Обратная матрица

2013-06-12T17:56:00Z

Никита:

{{Определение
|definition='''Обратная матрица''' - такая матрица <tex>A^{-1}</tex>, при умножении на которую, исходная матрица <tex>A</tex> даёт в результате единичную матрицу <tex>E</tex>
: <math>\! AA^{-1} = A^{-1}A = E</math>
}}

==Критерий обратимости матрицы==
{{Теорема
|statement=
Квадратная матрица обратима тогда и только тогда, когда она невырожденная, то есть ее определитель НЕ равен нулю.
|proof =
*Если матрица <tex>A</tex> обратима, то <tex>AB = E</tex> для некоторой матрицы <tex>B</tex>. Тогда в силу теоремы(если квадратные матрицы одного и того же порядка, то <tex>det(AB) = detA * detB</tex>):
<tex>1 = det E = det(AB) = detA * detB</tex>, следовательно, <tex>detA \ne 0</tex>.
*Теперь докажем обратное утверждение. Пусть <tex>det A \ne 0</tex>. Положим <tex>B = \frac{1}{detA}A^{*}</tex>
Тогда <tex>AB = A(\frac{1}{detA}A^{*}) = \frac{1}{detA}(AA^{*})</tex> то есть, <tex>A</tex> обратима справа.
*Поскольку для квадратной матрицы одно и двусторонняя обратимость эквивалентны (Квадратная матрица <tex>A</tex> обратима справа тогда и только тогда, когда она обратима слева.), получаем, что <tex>A</tex> обратима и <tex>A^{-1} = B = \frac{1}{detA}A^{*}</tex>
''<tex>A^{*}</tex> - присоединенная матрица''
}}

==Свойства обратной матрицы==
* <math dpi = "145">\det A^{-1} = \frac{1}{\det A}</math>
* <math dpi = "145">\ (AB)^{-1} = B^{-1}A^{-1}</math>
* <math dpi = "145">\ (A^T)^{-1} = (A^{-1})^T</math>
* <math dpi = "145">\ (kA)^{-1} = k^{-1}A^{-1}</math>

== Методы нахождения обратной матрицы ==
=== Метод Гаусса для нахождения обратной матрицы ===
Возьмём две матрицы: саму <tex>A</tex> и <tex>E</tex>. Приведём матрицу <tex>A</tex> к единичной матрице методом Гаусса. После применения каждой операции к первой матрице применим ту же операцию ко второй. Когда приведение первой матрицы к единичному виду будет завершено, вторая матрица окажется равной <tex>A^-1</tex>.

====Пример====
Найдем обратную матрицу для матрицы
:<math dpi = "145"> A =
\begin{bmatrix}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{bmatrix}.
</math>
*'''1)''' Для начала убедимся, что ее определитель не равен нулю(она невырожденная).

*'''2)''' Справа от исходной матрицы припишем единичную.
:<math dpi = "145"> [ A | I ] =
\left[ \begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\\
-1 & 2 & -1 & 0 & 1 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right].
</math>

*'''3)''' Методом Гаусса приведем левую матрицу к единичной, применяя все операции одновременно и к левой, и к правой матрицам.
:<math dpi = "145"> [ I | B ] =
\left[ \begin{array}{rrr|rrr}
1 & 0 & 0 & \frac{3}{4} & \frac{1}{2} & \frac{1}{4}\\[3pt]
0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2}\\[3pt]
0 & 0 & 1 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4}
\end{array} \right].
</math>

*'''4)''' <tex dpi = "145">A^{-1} = B</tex>

=== Метод присоединенной матрицы ===

<math dpi = "145">A^{-1} = \frac{1}{\det A}\cdot \mbox{adj}\,A,</math>
где <math dpi = "145">\mbox{adj}\,A</math> — присоединенная матрица;
{{Определение
|definition= '''Присоединенная(союзная, взаимная) матрица''' — матрица, составленная из алгебраических дополнений для соответствующих элементов исходной матрицы.
}}

<math dpi = "145">{C}^{*}= \begin{pmatrix}
{A}_{11} & {A}_{12} & \cdots & {A}_{1n} \\
{A}_{21} & {A}_{22} & \cdots & {A}_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
{A}_{n1} & {A}_{n2} & \cdots & {A}_{nn} \\
\end{pmatrix}</math>

Исходная матрица:

<math dpi = "145">{A}= \begin{pmatrix}
{a}_{11} & {a}_{12} & \cdots & {a}_{1n} \\
{a}_{21} & {a}_{22} & \cdots & {a}_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
{a}_{n1} & {a}_{n2} & \cdots & {a}_{nn} \\
\end{pmatrix}</math>

Где:

* <math dpi = "145">{C}^{*}</math> — присоединённая(союзная, взаимная) матрица;
* <math dpi = "145">{A}_{ij}</math> — алгебраические дополнения исходной матрицы;
* <math dpi = "145">{a}_{ij}</math> — элементы исходной матрицы.

'''Алгебраическим дополнением''' элемента <math dpi = "145">\ a_{ij}</math> матрицы <math dpi = "145">\ A</math> называется число

<math dpi = "145">\ A_{ij}=(-1)^{i+j}M_{ij}</math>,

где <math dpi = "145">\ M_{ij}</math> — дополнительный минор, определитель матрицы, получающейся из исходной матрицы <math dpi = "145">\ A</math> путем вычёркивания ''i'' -й строки и ''j'' -го столбца.

<math dpi="145">M_{ij} = det\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1(j-1)} & a_{1(j+1)} & \cdots & a_{1n} \\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
a_{(i-1)1} & a_{(i-1)2} & \cdots & a_{(i-1)(j-1)} & a_{(i-1)(j+1)} & \cdots & a_{(i-1)n} \\
a_{(i+1)1} & a_{(i+1)2} & \cdots & a_{(i+1)(j-1)} & a_{(i+1)(j+1)} & \cdots & a_{(i+1)n} \\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{n(j-1)} & a_{n(j+1)} & \cdots & a_{nn} \\
\end{pmatrix}</math>
====Алгоритм получения обратной матрицы====
:*заменить каждый элемент исходной матрицы на его алгебраическое дополнение,
:*транспонировать полученную матрицу - в результате будет получена союзная матрица,
:*разделить каждый элемент союзной матрицы на определитель исходной матрицы.

<tex dpi="145">A^{-1} = (C^*)^T \times \frac{1}{det A}</tex>

==Ссылки==
* [http://ru.wikipedia.org/wiki/Обратная_матрица Википедия {{---}} Обратная матрица]

* [http://ru.wikipedia.org/wiki/Союзная_матрица Википедия {{---}} Союзная матрица]

* [http://ru.wikipedia.org/wiki/Алгебраическое_дополнение Википедия {{---}} Алгебраическое дополнение]

* [http://en.wikipedia.org/wiki/Invertible_matrix Wikipedia {{---}} Invertible matrix]

[[Категория: Алгебра и геометрия 1 курс]]
[[Категория: Линейные операторы]]

Обсуждение:Линейный оператор

2013-06-12T17:54:27Z

Никита:

Мне кажется нужна теорема об эквивалентности задания ло А его матрицей в паре базисов. В остальном ок! (Одинцова)

Было бы неплохо в примерах привести сами матрицы (Коваль)

Обсуждение:Линейный оператор

2013-06-12T17:54:13Z

Никита:

Мне кажется нужна теорема об эквивалентности задания ло А его матрицей в паре базисов. В остальном ок! (Одинцова)
Было бы неплохо в примерах привести сами матрицы (Коваль)

Линейный оператор

2013-06-12T17:51:41Z

Никита: /* Теорема об эквивалентности задания линейного оператора */

==Линейный оператор==
{{Определение
|definition=Пусть <tex>X</tex> и <tex>Y</tex> - линейные пространства над полем <tex>F</tex>. Отображение <tex>\mathcal{A}:X \mapsto Y</tex> называется линейным оператором, если <tex>\forall x_1,x_2 \in X</tex>, <tex>\forall \lambda \in F</tex>:
* <tex>\mathcal{A}(x_1+x_2)=\mathcal{A}(x_1)+\mathcal{A}(x_2)</tex>
* <tex>\mathcal{A}(\lambda \cdot x_1) = \lambda \cdot \mathcal{A}(x_1)</tex>
}}

{{Определение
|definition=Линейный оператор <tex>\mathcal{A}:X \mapsto X</tex> называется автоморфизмом (или гомоморфизмом).
}}
{{Nota Bene|notabene=<tex>\mathcal{A}(x) = \mathcal{A}x</tex>}}
{{Определение
|definition=<tex>\mathcal{A},\mathcal{B}:X \mapsto Y</tex>, <tex>\mathcal{A}=\mathcal{B}</tex>, если <tex>\forall x \in X:\mathcal{A}x = \mathcal{B}x</tex>
}}
{{Определение
|definition=<tex>O</tex> называется нулевым оператором, если <tex>\forall x, y \in X:Ox=Oy</tex>
}}
== Примеры ==
=== Тождественный оператор ===
<tex>I:X \mapsto X</tex> по формуле <tex>Ix=x</tex>
=== Линейный оператор проектирования ===
<tex>X=L_1 + L_2</tex>

<tex>P_{L_1}^{||L_2}:X \mapsto L_1</tex>

<tex>P_{L_2}^{||L1}:X \mapsto L_2</tex>

NB: <tex>P_{L_{1,2}}^{||L_{2,1}}:X \mapsto X</tex> (<tex>L_1</tex> и <tex>L_2</tex> - п.п. <tex>X</tex>)

=== Оператор дифференцирования ===
Пусть <tex>X=P_n; D:P_n \rightarrow P_{n-1}</tex>
по формуле <tex>(Dp)(t)={dp(t) \over dt} = p^{'}(t)</tex>
=== Интегральный оператор ===
Пусть <tex>X = C(a,b); K(s,t); s \in (a,b); t \in (a,b)</tex>

<tex>(Bf)(s) = \int_a^b K(s,t) \cdot f(t) \cdot dt</tex>

<tex>B : C(a,b) \rightarrow C(a,b)</tex>

== Матрица линейного оператора ==
Пусть <tex>\mathcal{A}:X \mapsto Y</tex>

Пусть п.п. <tex>X \leftrightarrow \{e_k\}_{k=1}^n, \dim X=n</tex>

Пусть п.п. <tex>Y \leftrightarrow \{h_i\}_{i=1}^m, \dim Y = m</tex>

<tex>\underset{1\leq k\leq n}{\mathcal{A}e_k}=\displaystyle \sum_{i=1}^m \alpha_k^i \cdot h_i \Rightarrow A=||\alpha_k^i||</tex>, где <tex>1\leq i\leq m, 1 \leq k \leq n</tex>

<tex>
A=
\begin{pmatrix}
\alpha_1^1 & \cdots & \alpha_n^1 \\
\alpha_1^2 & \cdots & \alpha_n^2 \\
\cdots & \cdots & \cdots \\
\alpha_1^m & \cdots & \alpha_n^m \\
\end{pmatrix}
</tex>

{{Nota Bene|notabene=Обратите внимание, что <tex>\mathcal{A}</tex> означает оператор, а <tex>A</tex> {{---}} матрицу этого оператора.}}

== Примеры ==
=== Нулевой оператор ===
<tex>
O_{[m \times n]}=
\begin{pmatrix}
0 & \cdots & 0 \\
\cdots & \cdots & \cdots \\
0 & \cdots & 0 \\
\end{pmatrix}
</tex>

=== Оператор дифференцирования ===
<tex>D:P_n \rightarrow P_{n-1}</tex>

<tex>\{1,t,t^2,...,t^n\}</tex> - базис <tex>P_n</tex>

<tex>
D=
\begin{pmatrix}
0 & 1 & 0 & 0 & \cdots & 0 \\
0 & 0 & 2 & 0 & \cdots & 0 \\
0 & 0 & 0 & 3 &\cdots & 0 \\
\cdots & \cdots & \cdots & \cdots &\cdots & \cdots \\
0 & 0 & 0 & 0 &\cdots & n \\
\end{pmatrix}
</tex>

==Теорема об эквивалентности задания линейного оператора==
{{Теорема
|statement=
Задание Л.О. <tex>\mathcal{A}: X \rightarrow Y \Leftrightarrow </tex> заданию его матрицы в паре базисов <tex>\{x_i\}_{i=1}^{n}</tex> и <tex>\{h_k\}_{k=1}^{m}</tex>
|proof=
<tex> \Rightarrow \mathcal{A} = \sum\limits_{k=1}^{m} \alpha_{k}^{i}h_k </tex> (единственным образом) <tex> \Rightarrow A=||\alpha_k^i||</tex>, где <tex>1\leq i\leq n, 1 \leq k \leq m</tex>

<tex> \Leftarrow x= \sum\limits_{i=1}^{n} \xi^i e_i </tex> (единственным образом)

Рассмотрим <tex>\mathcal{A}x= \mathcal{A}(\sum\limits_{i=1}^{n} \xi^ie_i)= \sum\limits_{i=1}^{n} \xi^i \mathcal{A}e_i= \sum\limits_{i=1}^{n} \xi^i \sum\limits_{k=1}^{m} \alpha_{i}^{k}h_k=\sum\limits_{k=1}^{m}(\sum\limits_{i=1}^{n} \alpha_{i}^{k} \xi^i)h_k </tex> (1)

<tex>\mathcal{A}x=y=\sum\limits_{k=1}^{m} \eta^kh_k </tex> (2)

из (1) и (2) получим, что <tex>\eta^k=\sum\limits_{i=1}^{n} \alpha_{i}^{k} \xi^i \Leftrightarrow A \cdot X= Y</tex> (умножение матриц), тогда <tex>\mathcal{A}x=y</tex>
}}

[[Категория: Алгебра и геометрия 1 курс]]

Замена базиса

2013-06-12T16:59:23Z

Никита: Новая страница: «Категория: Алгебра и геометрия 1 курс»

[[Категория: Алгебра и геометрия 1 курс]]

Ядро и образ линейного оператора

2013-06-12T16:46:31Z

Никита: /* Функции от линейного оператора */

{{Определение
|definition='''Ядром''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Ker\mathcal{A}} = \{x\in X \mid \mathcal{A}x = 0 \}</tex>
}}

{{Определение
|definition='''Образом''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Im\mathcal{A}} = \{y\in Y \mid y = \mathcal{A}x \}</tex> ''(множество значений)''
}}

{{Лемма
|statement=Ядро и образ линейного оператора являются подпространствами линейных пространств <tex>X</tex> и <tex>Y</tex> соответственно.
}}

{{Теорема
|about=Теорема о ядре и базисе
|statement = <tex>\dim Ker\mathcal{A} + \dim Im\mathcal{A} = n = \dim X</tex>
|proof=
<tex>Ker\mathcal{A}</tex> {{---}} подпространство <tex>X</tex>

Пусть <tex>\dim Ker\mathcal{A} = k;\ 0 \leqslant k \leqslant n</tex>

<tex>\{e\}_{i = 1}^{k}</tex> {{---}} базис <tex>Ker\mathcal{A}</tex>

<tex>\mathcal{8} e_i : \mathcal{A}e_i = 0\ (i = 1..k)</tex>

Дополним <tex>\{e\}_{i = 1}^{k}</tex> до базиса <tex>X</tex>. получим базис <tex>\{e\}_{i = 1}^{n}</tex>, где <tex>n = \dim X</tex>

Докажем, что <tex>Im\mathcal{A}</tex> {{---}} линейная оболочка <tex>\{ \mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n \}</tex>

Рассмотрим <tex>X = \xi^1 e_1 + \xi^2 e_2 +\ ...\ + \xi^n e_n</tex>

<tex>\mathcal{A}x = 0 +\ ...\ + 0 + \mathcal{A}e_{k+1} +\ ...\ + \mathcal{A}e_n = y \in Im\mathcal{A}</tex>

Осталось доказать следующее: <tex>\dim</tex> Л.О.<tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\} = n - k = \dim Im\mathcal{A}</tex>

Пусть <tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\}</tex> {{---}} линейно зависимы, <tex>\Rightarrow</tex> существует нетривиальная линейная комбинация, что <tex>\alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0 \ (*)</tex>

Пусть <tex>z = \alpha_{k+1}e_{k+1} +\ ...\ + \alpha_{n}e_n</tex>

Рассмотрим <tex>\mathcal{A}z = \alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0</tex> в соответствии с <tex>(*)</tex>

Получаем, что <tex>z \in Ker\mathcal{A}</tex>, что противоречит выбору <tex>z</tex>

Значит, <tex>\dim Im\mathcal{A} = n - k</tex>
}}

== Функции от линейного оператора ==

Пусть <tex>\mathcal{A} \colon X \to X</tex>

<tex>\mathcal{A}^n = \mathcal{A} \cdot\ ...\ \cdot \mathcal{A}</tex> (n раз)

<tex> p_m(\lambda) = \sum_{j = 0}^m \alpha_j \lambda^j \longrightarrow p_m(\mathcal{A}) = \sum_{j = 0}^m \alpha_j \mathcal{A}^j; \mathcal{A}^0 = J</tex>

Если <tex>\mathcal{9} \mathcal{A}^{-1}</tex>, то переходим к квазиполиномам:
<tex>p_{m, k} = \sum_{j = -k}^m \alpha_j \mathcal{A}^j</tex>

== Источники ==

* Анин конспект

[[Категория: Алгебра и геометрия 1 курс]]

Ядро и образ линейного оператора

2013-06-12T16:45:08Z

Никита: /* Функции от линейного оператора */

{{Определение
|definition='''Ядром''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Ker\mathcal{A}} = \{x\in X \mid \mathcal{A}x = 0 \}</tex>
}}

{{Определение
|definition='''Образом''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Im\mathcal{A}} = \{y\in Y \mid y = \mathcal{A}x \}</tex> ''(множество значений)''
}}

{{Лемма
|statement=Ядро и образ линейного оператора являются подпространствами линейных пространств <tex>X</tex> и <tex>Y</tex> соответственно.
}}

{{Теорема
|about=Теорема о ядре и базисе
|statement = <tex>\dim Ker\mathcal{A} + \dim Im\mathcal{A} = n = \dim X</tex>
|proof=
<tex>Ker\mathcal{A}</tex> {{---}} подпространство <tex>X</tex>

Пусть <tex>\dim Ker\mathcal{A} = k;\ 0 \leqslant k \leqslant n</tex>

<tex>\{e\}_{i = 1}^{k}</tex> {{---}} базис <tex>Ker\mathcal{A}</tex>

<tex>\mathcal{8} e_i : \mathcal{A}e_i = 0\ (i = 1..k)</tex>

Дополним <tex>\{e\}_{i = 1}^{k}</tex> до базиса <tex>X</tex>. получим базис <tex>\{e\}_{i = 1}^{n}</tex>, где <tex>n = \dim X</tex>

Докажем, что <tex>Im\mathcal{A}</tex> {{---}} линейная оболочка <tex>\{ \mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n \}</tex>

Рассмотрим <tex>X = \xi^1 e_1 + \xi^2 e_2 +\ ...\ + \xi^n e_n</tex>

<tex>\mathcal{A}x = 0 +\ ...\ + 0 + \mathcal{A}e_{k+1} +\ ...\ + \mathcal{A}e_n = y \in Im\mathcal{A}</tex>

Осталось доказать следующее: <tex>\dim</tex> Л.О.<tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\} = n - k = \dim Im\mathcal{A}</tex>

Пусть <tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\}</tex> {{---}} линейно зависимы, <tex>\Rightarrow</tex> существует нетривиальная линейная комбинация, что <tex>\alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0 \ (*)</tex>

Пусть <tex>z = \alpha_{k+1}e_{k+1} +\ ...\ + \alpha_{n}e_n</tex>

Рассмотрим <tex>\mathcal{A}z = \alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0</tex> в соответствии с <tex>(*)</tex>

Получаем, что <tex>z \in Ker\mathcal{A}</tex>, что противоречит выбору <tex>z</tex>

Значит, <tex>\dim Im\mathcal{A} = n - k</tex>
}}

== Функции от линейного оператора ==

Пусть <tex>\mathcal{A} \colon X \to X</tex>

<tex>\mathcal{A}^n = \mathcal{A} \cdot\ ...\ \cdot \mathcal{A}</tex> (n раз)

<tex> p_m(\lambda) = \sum_{j = 0}^m \alpha_j \lambda^j \longrightarrow p_m(\mathcal{A}) = \sum_{j = 0}^m \alpha_j \mathcal{A}^j; \mathcal{A}^0 = J</tex>

Если <tex>\mathcal{9} \mathcal{A}^{-1}</tex>, то переходим к квазиполиномам:
<tex>p_{m, k} = \sum_{j = -k}^m \alpha_j \mathcal{A}^j

== Источники ==

* Анин конспект

[[Категория: Алгебра и геометрия 1 курс]]

Ядро и образ линейного оператора

2013-06-12T16:35:16Z

Никита:

{{Определение
|definition='''Ядром''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Ker\mathcal{A}} = \{x\in X \mid \mathcal{A}x = 0 \}</tex>
}}

{{Определение
|definition='''Образом''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Im\mathcal{A}} = \{y\in Y \mid y = \mathcal{A}x \}</tex> ''(множество значений)''
}}

{{Лемма
|statement=Ядро и образ линейного оператора являются подпространствами линейных пространств <tex>X</tex> и <tex>Y</tex> соответственно.
}}

{{Теорема
|about=Теорема о ядре и базисе
|statement = <tex>\dim Ker\mathcal{A} + \dim Im\mathcal{A} = n = \dim X</tex>
|proof=
<tex>Ker\mathcal{A}</tex> {{---}} подпространство <tex>X</tex>

Пусть <tex>\dim Ker\mathcal{A} = k;\ 0 \leqslant k \leqslant n</tex>

<tex>\{e\}_{i = 1}^{k}</tex> {{---}} базис <tex>Ker\mathcal{A}</tex>

<tex>\mathcal{8} e_i : \mathcal{A}e_i = 0\ (i = 1..k)</tex>

Дополним <tex>\{e\}_{i = 1}^{k}</tex> до базиса <tex>X</tex>. получим базис <tex>\{e\}_{i = 1}^{n}</tex>, где <tex>n = \dim X</tex>

Докажем, что <tex>Im\mathcal{A}</tex> {{---}} линейная оболочка <tex>\{ \mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n \}</tex>

Рассмотрим <tex>X = \xi^1 e_1 + \xi^2 e_2 +\ ...\ + \xi^n e_n</tex>

<tex>\mathcal{A}x = 0 +\ ...\ + 0 + \mathcal{A}e_{k+1} +\ ...\ + \mathcal{A}e_n = y \in Im\mathcal{A}</tex>

Осталось доказать следующее: <tex>\dim</tex> Л.О.<tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\} = n - k = \dim Im\mathcal{A}</tex>

Пусть <tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\}</tex> {{---}} линейно зависимы, <tex>\Rightarrow</tex> существует нетривиальная линейная комбинация, что <tex>\alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0 \ (*)</tex>

Пусть <tex>z = \alpha_{k+1}e_{k+1} +\ ...\ + \alpha_{n}e_n</tex>

Рассмотрим <tex>\mathcal{A}z = \alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0</tex> в соответствии с <tex>(*)</tex>

Получаем, что <tex>z \in Ker\mathcal{A}</tex>, что противоречит выбору <tex>z</tex>

Значит, <tex>\dim Im\mathcal{A} = n - k</tex>
}}

== Функции от линейного оператора ==

== Источники ==

* Анин конспект

[[Категория: Алгебра и геометрия 1 курс]]

Ядро и образ линейного оператора

2013-06-12T16:34:41Z

Никита:

{{Определение
|definition='''Ядром''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Ker\mathcal{A}} = \{x\in X \mid \mathcal{A}x = 0 \}</tex>
}}

{{Определение
|definition='''Образом''' линейного оператора <tex>\mathcal{A}</tex> называется множество <tex>~{Im\mathcal{A}} = \{y\in Y \mid y = \mathcal{A}x \}</tex> ''(множество значений)''
}}

{{Лемма
|statement=Ядро и образ линейного оператора являются подпространствами линейных пространств <tex>X</tex> и <tex>Y</tex> соответственно.
}}

{{Теорема
|about=Теорема о ядре и базисе
|statement = <tex>\dim Ker\mathcal{A} + \dim Im\mathcal{A} = n = \dim X</tex>
|proof=
<tex>Ker\mathcal{A}</tex> {{---}} подпространство <tex>X</tex>

Пусть <tex>\dim Ker\mathcal{A} = k;\ 0 \leqslant k \leqslant n</tex>

<tex>\{e\}_{i = 1}^{k}</tex> {{---}} базис <tex>Ker\mathcal{A}</tex>

<tex>\mathcal{8} e_i : \mathcal{A}e_i = 0\ (i = 1..k)</tex>

Дополним <tex>\{e\}_{i = 1}^{k}</tex> до базиса <tex>X</tex>. получим базис <tex>\{e\}_{i = 1}^{n}</tex>, где <tex>n = \dim X</tex>

Докажем, что <tex>Im\mathcal{A}</tex> {{---}} линейная оболочка <tex>\{ \mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n \}</tex>

Рассмотрим <tex>X = \xi^1 e_1 + \xi^2 e_2 +\ ...\ + \xi^n e_n</tex>

<tex>\mathcal{A}x = 0 +\ ...\ + 0 + \mathcal{A}e_{k+1} +\ ...\ + \mathcal{A}e_n = y \in Im\mathcal{A}</tex>

Осталось доказать следующее: <tex>\dim</tex> Л.О.<tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\} = n - k = \dim Im\mathcal{A}</tex>

Пусть <tex>\{\mathcal{A}e_{k+1}\ ...\ \mathcal{A}e_n\}</tex> {{---}} линейно зависимы, <tex>\Rightarrow</tex> существует нетривиальная линейная комбинация, что <tex>\alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0 \ (*)</tex>

Пусть <tex>z = \alpha_{k+1}e_{k+1} +\ ...\ + \alpha_{n}e_n</tex>

Рассмотрим <tex>\mathcal{A}z = \alpha_{k+1}\mathcal{A}e_{k+1} +\ ...\ + \alpha_n\mathcal{A}e_n = 0</tex> в соответствии с <tex>(*)</tex>

Получаем, что <tex>z \in Ker\mathcal{A}</tex>, что противоречит выбору <tex>z</tex>

Значит, <tex>\dim Im\mathcal{A} = n - k</

== Функции от линейного оператора ==

== Источники ==

* Анин конспект

[[Категория: Алгебра и геометрия 1 курс]]

Обратный оператор

2013-06-12T16:33:44Z

Никита: /* Ссылки */

{{Определение
|definition=Пусть <tex>\mathcal{A}:X \rightarrow X</tex> — автоморфизм. Тогда <tex>\mathcal{A}^{-1}: X \rightarrow X</tex> называется '''обратным оператором''' к <tex>\mathcal{A}</tex>, если <tex>\mathcal{A} \cdot \mathcal{A}^{-1} = \mathcal{A}^{-1} \cdot \mathcal{A} = J</tex>.
}}

{{Теорема
|about= Критерий существования <tex>\mathcal{A}^{-1}</tex>
|statement = Для <tex>\mathcal {9} \mathcal{A}^{-1}</tex> нужно и достаточно, чтобы в некотором базисе <tex>\left\{ e \right\}_{i = 1}^{n}\ det A \ne 0</tex>
|proof=
}}

{{Теорема
|about= Критерий существования <tex>\mathcal{A}^{-1}</tex>
|statement = Для <tex>\mathcal{9} \mathcal{A}^{-1}</tex> нужно и достаточно одного из двух условий:
# <tex>Ker\mathcal{A} = \{0_{x}\}</tex>
# <tex>Im\mathcal{A} = X</tex>
|proof=
Первое и второе утверждение равносильны в силу равенства <tex>\dim Ker\mathcal{A} + \dim Im\mathcal{A} = \dim X</tex>

<tex>Ker\mathcal{A} = \{0_{x}\} \Rightarrow \sum^n_{k=1} \alpha_k^i \xi^k = 0</tex> имеет только тривиальное решение <tex>\Rightarrow det A \ne 0 \Leftrightarrow \mathcal{9} A^{-1} \Leftrightarrow \mathcal{9} \mathcal{A}^{-1}</tex>
}}

== Ссылки ==
* [[Обратная матрица]]

* [[Ядро и образ линейного оператора]]

== Источники ==

* Анин конспект

[[Категория: Алгебра и геометрия 1 курс]]

Обратный оператор

2013-06-12T16:31:02Z

Никита:

{{Определение
|definition=Пусть <tex>\mathcal{A}:X \rightarrow X</tex> — автоморфизм. Тогда <tex>\mathcal{A}^{-1}: X \rightarrow X</tex> называется '''обратным оператором''' к <tex>\mathcal{A}</tex>, если <tex>\mathcal{A} \cdot \mathcal{A}^{-1} = \mathcal{A}^{-1} \cdot \mathcal{A} = J</tex>.
}}

{{Теорема
|about= Критерий существования <tex>\mathcal{A}^{-1}</tex>
|statement = Для <tex>\mathcal {9} \mathcal{A}^{-1}</tex> нужно и достаточно, чтобы в некотором базисе <tex>\left\{ e \right\}_{i = 1}^{n}\ det A \ne 0</tex>
|proof=
}}

{{Теорема
|about= Критерий существования <tex>\mathcal{A}^{-1}</tex>
|statement = Для <tex>\mathcal{9} \mathcal{A}^{-1}</tex> нужно и достаточно одного из двух условий:
# <tex>Ker\mathcal{A} = \{0_{x}\}</tex>
# <tex>Im\mathcal{A} = X</tex>
|proof=
Первое и второе утверждение равносильны в силу равенства <tex>\dim Ker\mathcal{A} + \dim Im\mathcal{A} = \dim X</tex>

<tex>Ker\mathcal{A} = \{0_{x}\} \Rightarrow \sum^n_{k=1} \alpha_k^i \xi^k = 0</tex> имеет только тривиальное решение <tex>\Rightarrow det A \ne 0 \Leftrightarrow \mathcal{9} A^{-1} \Leftrightarrow \mathcal{9} \mathcal{A}^{-1}</tex>
}}

== Ссылки ==
[[Обратная матрица]]

== Источники ==

* Анин конспект

[[Категория: Алгебра и геометрия 1 курс]]