Обратная связь ПОЗНАВАТЕЛЬНОЕ Сила воли ведет к действию, а позитивные действия формируют позитивное отношение Как определить диапазон голоса — ваш вокал Как цель узнает о ваших желаниях прежде, чем вы начнете действовать. Как компании прогнозируют привычки и манипулируют ими Целительная привычка Как самому избавиться от обидчивости Противоречивые взгляды на качества, присущие мужчинам Тренинг уверенности в себе Вкуснейший «Салат из свеклы с чесноком» Натюрморт и его изобразительные возможности Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д. Как научиться брать на себя ответственность Зачем нужны границы в отношениях с детьми? Световозвращающие элементы на детской одежде Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия Как слышать голос Бога Классификация ожирения по ИМТ (ВОЗ) Глава 3. Оси и плоскости тела человека — Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д. Отёска стен и прирубка косяков — Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу. Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) — В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар. |
Наиболее простой вид принимает матрица линейного оператора , имеющего линейно независимых собственных векторов с собственными значениями, соответственно равными . . (10) Пример 56.В некотором базиселинейный оператор задан матрицей . В действительном линейном пространстве найти базис, в котором матрица этого оператора имеет диагональный вид. Решение Матрица имеет диагональный вид в базисе из собственных векторов, поэтому найдем собственные векторы. Характеристическое уравнение: его корни Если то пусть тогда , собственный вектор . Если то Пусть тогда , собственный вектор . Таким образом, матрица в базисе имеет вид: .
Матрица приводится к диагональному виду, если можно подобрать невырожденную матрицу , что — диагональная матрица. Правило построения матрицы , приводящей матрицу порядка к диагональному виду: 1. Найти все собственные значения матрицы . 2. Для каждого собственного числа найти фундаментальную систему решений однородной системы линейных уравнений 3. Построить матрицу , столбцами которой являются координаты решений найденных фундаментальных систем. 4. Если полученная матрица является квадратной, то она приводит матрицу к диагональному виду. Пример 57.Найти матрицу , которая приводит матрицу к диагональному виду. Найти матрицу . Решение Вычислим определитель матрицы : . Собственные числа матрицы равны и . Построим фундаментальные системы решений систем уравнений ФСР первой системы состоит из одного решения , а второй – из одного решения . Следовательно, матрица имеет вид . Полученная матрица не является квадратной, поэтому матрица не приводится к диагональному виду. Пример 58. Решение Характеристическое уравнение матрицы имеет вид . Матрица имеет два собственных числа: ФСР системы уравнений состоит из двух векторов: , , а системы уравнений — из одного вектора . Матрица , приводящая матрицу к диагональному виду, имеет вид . После ортогонализации и нормирования столбцов этой матрицы получим ортогональную матрицу . Матрица, обратная к , совпадает с , т.е. . Нетрудно проверить, что . Квадратичные формы Переход от системы неизвестных к системе неизвестных по формуле где — квадратная матрица порядка , называется линейным преобразованием неизвестных. Определение. Квадратичной формой от неизвестных называется сумма, каждое слагаемое которой является или квадратом одного из неизвестных, или произведением двух разных неизвестных. Квадратичную форму можно записать в виде , (11) где — симметрическая матрица порядка , которая называется матрицей квадратичной формы . Пример 59.Написать матрицу квадратичной формы Решение Обозначим коэффициенты при произведении через причем . Член запишем в виде . Тогда квадратичную форму можно записать в виде . Теперь матрица А квадратичной формы имеет вид: .
Пример 60. Дана квадратичная форма . Записать ее в матричном виде. Решение Найдем матрицу квадратичной формы. Ее диагональные элементы равны коэффициентам при квадратах переменных, а другие элементы – половинам соответствующих коэффициентов квадратичной формы. Получили:
Две квадратичные формы называются эквивалентными, если одна из них переводится в другую посредством невырожденного линейного преобразования. Если в квадратичной форме неизвестные подвергнуть линейному преобразованию то получится квадратичная форма с матрицей . (12) Пример 61. Дана квадратичная форма Найти квадратичную форму , полученную из данной линейным преобразованием . Решение Матрица данной квадратичной формы , а матрица линейного преобразования . Следовательно, по (12) матрица искомой квадратичной формы = . Определение. Каноническим видом данной квадратичной формы называется эквивалентная ей форма, не содержащая произведений неизвестных.
Каждую квадратичную форму можно привести к каноническому виду с помощью линейного преобразования неизвестных с ортогональной матрицей . Пример 62. Привести к каноническому виду квадратичную форму . Решение Сгруппируем все члены, содержащие неизвестное , и дополним их до полного квадрата: В дальнейшем полный квадрат, содержащий неизвестное , не изменится. Теперь среди оставшихся членов сгруппируем все, содержащие , и дополним их до полного квадрата: Теперь перейдем от неизвестных к неизвестным по формулам: В результате этого перехода получили канонический вид данной квадратичной формы:
Если для всех , то квадратичная форма называется положительно (отрицательно) определенной. Квадратичная форма положительно (отрицательно) определена, если в каком-нибудь ее каноническом виде нет отрицательных (положительных) коэффициентов при квадратах неизвестных.
Следующие утверждения равносильны: 1) Квадратичная форма положительно определена. 2) Собственные значения матрицы А положительны. 3) Угловые миноры матрицы А положительны.
А также равносильны следующие утверждения: 1) Квадратичная форма отрицательно определена. 2) Собственные значения матрицы А отрицательны. 3) Все угловые миноры матрицы А нечетного порядка отрицательны, а все угловые миноры четного порядка положительны. Доверь свою работу ✍️ кандидату наук! Имя Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно — исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое Нажимая кнопку «Продолжить», я принимаю политику конфиденциальности |
Матрица порядка приводится к диагональному виду тогда и только тогда, когда в пространстве имеется базис, состоящий из собственных векторов матрицы . Столбцами матрицы являются координаты векторов этого базиса.
Если же матрица не будет квадратной, то матрица не может быть приведена к диагональному виду.
Привести к диагональному виду с помощью ортогональной матрицы симметрическую матрицу .
Если С — невырожденная матрица, то линейное преобразование неизвестных также называется невырожденным .
ru Все права принадлежат авторам размещенных материалов. Обратная связь…Приведение матрицы линейного оператора к диагональному виду — Студопедия
Поделись
Как следует из теоремы 13.1, матрица линейного оператора зависит от базиса пространства. Как подобрать этот базис, чтобы матрица линейного оператора в нем имела наиболее простой вид? На этот вопрос отвечает следующая теорема.
Теоремa 14.1. Для того чтобы матрица линейного оператора A: Rn®Rn в некотором базисе была диагональной, необходимо и достаточно, чтобы этот базис состоял из собственных векторов линейного оператора A.
Доказательство. Необходимость. Пусть матрица линейного оператора A в некотором базисе еl, е2,…, еn диагональная, т.
е.
.
Тогда, очевидно, справедливы равенства Aеj= Lеj = ljеj, j = 1, 2,…, n, из которых следует, что lj – собственные значения, а еj – соответствующие им собственные векторы оператора A.
Достаточность. Предположим, что базис пространства состоит из собственных векторов x1, x2,…, xn, а l1, l2,…, ln – соответствующие им собственные значения оператора A. Тогда Axj = ljxj, j = 1, 2,.
.., n. Отсюда следует, что L = = diag (l1, l2,…, ln) – матрица линейного оператора A в базисе x1, x2,…, xn.¨
Определение 14.1. Если существует базис пространства Rn, состоящий из собственных векторов x1, x2,…, xn линейного оператора A: Rn®Rn с матрицей А в некотором базисе пространства Rn, и Т – матрица перехода от этого базиса к базису x1, x2,…, xn, то справедливо равенство
L = Т–1АТ, (14.
1)
где L – диагональная матрица с собственными значениями, соответствующими собственным векторам оператора A, на главной диагонали. В этом случае матрица А линейного оператора A называется диагонализируемой.
Пример 1. Привести к диагональному виду матрицу
.
Решение. Для этой матрицы в примере 1 из §12.2 найдены собственные векторы x1 = (–1, 1, 1), x2 = (11, 1, –14)и x3 = (1, 1, 1), соответствующие собственным значениям l1 = 1, l2 = – 2 и l3 = 3. Поскольку все собственные значения попарно различны, векторы x1, x2, x3 образуют базис пространства R3 согласно теореме 12.
1. Значит, согласно определению 14.1 матрица А диагонализируема.
Составим матрицу перехода Т к базису x1, x2, x3, столбцами которой будут координаты данных базисных векторов.
откуда
Тогда
diag (1, – 2, 3).·
запрос ссылки — Преобразование двоичной матрицы в треугольную форму с использованием матриц перестановки
Задавать вопрос
спросил
Изменено 3 года, 10 месяцев назад
Просмотрено 2к раз
$\begingroup$
Меня интересует сложность следующей задачи:
Имея $m\times n$ бинарную матрицу $M$, можем ли мы переставить ее строки/столбцы, чтобы получить треугольную матрицу?
Меня также интересует случай, когда «треугольный» заменен на однотреугольный .
Здесь говорится, что Уилф (1997) изучал первую задачу в книге «О числах пересечения и некоторых нерешенных задачах». Однако у меня нет к нему доступа, и я не могу найти его на его сайте.
Кто-нибудь знает ссылку или была ли какая-либо последующая работа?
Большое спасибо.
Уточнение : Я спрашиваю, существуют ли две матрицы перестановок $P,Q$ такие, что $PMQ$ треугольная. Эквивалентно, можно свободно менять местами строки и столбцы $M$.
Предыстория : Поскольку алгоритм был подробно изложен, я кратко объясню свою мотивацию.
Каждая конечная (теоретико-порядковая) решетка $L$ имеет ассоциированное «полумножество неприводимых элементов», которое можно рассматривать как отношение $R \subseteq J(L) \times M(L)$ между соединением/встречными неприводимыми где $R(j,m) \iff j \nleq_L m$. В теореме 11 книги «Простые числа, неприводимые числа и экстремальные решетки» Марковский доказывает, что $R$ унитреугольизуема снизу или сверху тогда и только тогда, когда $L$ имеет длину $|M(L)|$ или $|J(L)|$ соответственно.
- запрос-справка
- кокомбинаторика
- матрицы
- вычислительная сложность
$\endgroup$
7
$\begingroup$
К счастью, проблема больше не в «NP-лимбо». В статье Фертина, Русу и Виалетт «Получение треугольной матрицы независимыми перестановками строк и столбцов» показано, что проблема является NP-полной для бинарных квадратных матриц.
РЕДАКТИРОВАТЬ : Кроме того, такая же проблема была задана пять лет назад на CS Theory StackExchange, и было доказано, что она является NP-полной. Вот опубликованная версия «Топологические упорядочения взвешенных ориентированных ациклических графов» Гербнера, Кесега, Палмера и Палволги
. $\endgroup$
1
$\begingroup$
Эта проблема была изучена аспирантом Кнута Рэмси В.
Хаддадом в его диссертации: Триангуляризация: проблема планирования для двух процессоров.
Согласно тезису, проблема находится в «NP-лимбе» (неизвестно, является ли она NP-полной или в P). Диссертация была опубликована в 1990 году, то есть до упомянутой вами ссылки. Тем не менее, он содержит много наблюдений над проблемой и анализ сложности некоторых расширений проблемы, которые могут вас заинтересовать.
Кроме того, вы можете отслеживать новые ссылки, начиная оттуда.
$\endgroup$
1
9{-1} L’ P’$ и $L’$ являются нижнетреугольными. Если вы представляете каждый элемент матрицы как связь от отца (столбец $j$) к ребенку (строка $i$), каждый раз, когда первый ребенок находится перед отцом (первый $i
Повторите тот же процесс для каждой полученной переставленной матрицы.
$\endgroup$
2
Зарегистрируйтесь или войдите в систему
Зарегистрируйтесь с помощью Google
Зарегистрироваться через Facebook
Зарегистрируйтесь, используя электронную почту и пароль
Опубликовать как гость
Электронная почта
Требуется, но никогда не отображается
Опубликовать как гость
Электронная почта
Требуется, но не отображается
Нажимая «Опубликовать свой ответ», вы соглашаетесь с нашими условиями обслуживания, политикой конфиденциальности и политикой использования файлов cookie
.
linear алгебра — Упростить матрицу до верхней треугольной матрицы
Не всегда рекомендуется выполнять LU-разложение без поворота для трехдиагональных матриц или иным образом. Тем не менее, всякий раз, когда она устойчива (например, диагонально доминирующие случаи), существует простая формула для факторов $\mathbf L$ и $\mathbf U$, основанная на обычном трехчленном рекуррентном методе для определителя трехдиагональной матрицы (см. например это).
В частности, рассмотрим трехдиагональную матрицу
MatrixForm[trid = With[{n = 5},
РазреженныйМассив[{Полоса[{2, 1}] -> Массив[l, n - 1],
Полоса [{1, 1}] -> Массив [d, n],
Band[{1, 2}] -> Array[u, n - 1]}, {n, n}]]]
$$\begin{pmatrix} д[1] и и[1] и 0 и 0 и 0 \\ л[1] и д[2] и и[2] и 0 и 0 \\ 0 & l[2] & d[3] & u[3] & 0 \\ 0 & 0 & l[3] & d[4] & u[4] \\ 0 & 0 & 0 & l[4] & d[5] \\ \end{pmatrix}$$
Мы можем использовать RecurrenceTable[] для оценки трехчленного повторения для трехдиагонального определителя:
With[{n = 5},
rr = RecurrenceTable[{y[n] == d[n] y[n - 1] - l[n - 1] u[n - 1] y[n - 2],
y[-1] == 0, y[0] == 1}, y[n], {n, 0, n}]];
Проверка:
Last[rr] == Det[trid] // Упростить Истинный
Здесь, однако, нас интересует использование rr для построения желаемой декомпозиции.
В частности, требуемыми факторами являются:
С[{n=5},
lf = SparseArray[{Band[{2, 1}] -> Array[l, n - 1]/Ratios[Most[rr]],
Band[{1, 1}] -> 1}, {n, n}];
uf = SparseArray[{Band[{1, 1}] -> Ratios[rr],
Band[{1, 2}] -> Array[u, n - 1]}, {n, n}];]
Проверить:
lf.uf == trid // Упростить Истинный
Применим это к примеру Даниэля:
la = {12, -9, -21, -16};
да = {-30, 72, -49, 88, -98};
иа = {-98, 29, 63, -16};
RecurrenceTable[] плохо работает, когда диагонали указаны в виде списков, поэтому я продемонстрирую метод вычисления трехчленного повторения, основанный на многократном умножении матриц $2\times 2$:
n = длина [да];
rr = FoldList[Dot, IdentityMatrix[2],
Транспонировать[{{ConstantArray[0, n], ConstantArray[1, n]},
{-Append[la ua, 0], da}}, {2, 3, 1}]][[Все, 2, 2]]
{1, -30, -984, 40386, 2252136, -231048144}
(ранее я использовал это в этом сообщении в блоге.