1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 13

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

Текст из файла (страница 13)

. · cond(En−1 ).могут отличаться не очень сильно.Число обусловленности и матричные преобразованияЕсли Ej отлична от единичной матрицы, тоcond(Ej ) > 1,причём несмотря на специальный вид матриц Ej правая и леваячасти неравенстваcond(U ) ≤ cond(A) · cond(E1 ) · cond(E2 ) · . . . · cond(En−1 ).могут отличаться не очень сильно.Как следствие, обусловленность матриц, в которые матрица Aисходной СЛАУ преобразуется в прямом ходе метода Гаусса, атакже обусловленность итоговой верхней треугольной матрицы Uмогут быть существенно хуже, чем у матрицы A.Число обусловленности и матричные преобразованияПример.Для 2 × 2-матрицыA=1 23 4!число обусловленности равно cond2 (A) = 14.93.Число обусловленности и матричные преобразованияПример.Для 2 × 2-матрицыA=1 23 4!число обусловленности равно cond2 (A) = 14.93.Выполнение для неё преобразований прямого хода метода Гауссаприводит к матрице!1 2Ã =,0 −2число обусловленности которой cond2 (Ã) = 4.27, т.

е. уменьшается.С другой стороны, для матрицыB=1 2−3 4число обусловленности cond2 (B) = 2.62.!,С другой стороны, для матрицыB=1 2−3 4!,число обусловленности cond2 (B) = 2.62.Преобразования метода Гаусса превращают её в матрицу!1 2B̃ =,0 10для которой число обусловленности уже равно cond2 (B̃) = 10.4,т. е. существенно возрастает.Число обусловленности и матричные преобразованияВывод.Ухудшение обусловленности и, как следствие, всё бо́льшаячувствительность решения к погрешностям в данных — этодополнительная плата за приведение матрицы (и всей СЛАУ)к удобному для решения виду.Число обусловленности и матричные преобразованияВывод.Ухудшение обусловленности и, как следствие, всё бо́льшаячувствительность решения к погрешностям в данных — этодополнительная плата за приведение матрицы (и всей СЛАУ)к удобному для решения виду.Можно ли уменьшить эту плату?И если да, то как?Число обусловленности и матричные преобразованияИдея.Нужно использовать для матричных преобразованийортогональные матрицы, которые имеют наименьшую возможнуюобусловленность в спектральной норме (и небольшие числаобусловленности в других нормах).Умножение на такие матрицы не будет ухудшать обусловленностьполучающихся систем линейных уравнений и устойчивость ихрешений к ошибкам вычислений.QR-разложение матрицОпределениеДля матрицы A представлениеA = QRв виде произведения ортогональной матрицы Q и правойтреугольной матрицы R называется QR-разложением.QR-разложение матрицОпределениеДля матрицы A представлениеA = QRв виде произведения ортогональной матрицы Q и правойтреугольной матрицы R называется QR-разложением.Правая треугольная матрица — это то же самое, что верхняятреугольная матрица, которую мы условились обозначать U .Другая терминология обусловлена здесь историческими причинами.QR-разложение матрицQR-разложение матриц часто определяют также для общихпрямоугольных матриц, не обязательно квадратных.Если A — это m × n-матрица, то представление A = QR можнопониматькак произведение ортогональной m × m-матрицы Q натрапецеидальную m × n-матрицу Rили как произведение m × n-матрицы Q с ортогональнымистроками (столбцами) на правую треугольную n × n-матрицу R.На практике встречаются оба вида разложений.QR-разложение матрицТеоремаQR-разложение существует для любой квадратной матрицы.QR-разложение матрицТеоремаQR-разложение существует для любой квадратной матрицы.Доказательство будет дано позднее, и даже не одно.На практике основным инструментом получения QR-разложенияявляется техника, использующая так называемые матрицыотражения и матрицы вращения, описанию которых посвященыследующие разделы лекций.Если известно QR-разложение матрицы A, то решение линейнойсистемы Ax = b, равносильной(QR)x = bсводится к решению треугольной системы линейныхалгебраических уравненийRx = Q⊤ b.Если известно QR-разложение матрицы A, то решение линейнойсистемы Ax = b, равносильной(QR)x = bсводится к решению треугольной системы линейныхалгебраических уравненийRx = Q⊤ b.Существуют и другие важные применения QR-разложения —при численном решениилинейной задачи наименьших квадратов,при численном нахождении собственных значенийи собственных векторов матриц.Ортогональные матрицы отраженияОпределениеДля вектора u ∈ Rn с единичной евклидовой нормой, kuk2 = 1,матрицаH = H(u) = I − 2uu⊤называется матрицей отражения или матрицей Хаусхолдера.Вектор u называется порождающим или вектором Хаусхолдерадля матрицы отражения H(u).Ортогональные матрицы отраженияПредложениеМатрицы отражения Хаусхолдера являются симметричнымиортогональными матрицами.Кроме того, для матрицы H(u)порождающий вектор u является собственным вектором,отвечающим собственному значению (−1), т.

е. H(u) · u = −u;любой вектор v, ортогональный порождающему вектору u,является собственным вектором, отвечающим собственномузначению 1, т. е. H(u) · v = v.Доказательство проводится непосредственной проверкой.Доказательство проводится непосредственной проверкой.Симметричность матрицы H(u):H⊤ =I − 2uu⊤= I − 2 u⊤⊤⊤= I ⊤ − 2uu⊤⊤u⊤ = I − 2uu⊤ = H.Доказательство проводится непосредственной проверкой.Симметричность матрицы H(u):H⊤ =I − 2uu⊤= I − 2 u⊤⊤⊤= I ⊤ − 2uu⊤⊤u⊤ = I − 2uu⊤ = H.Ортогональность:H ⊤H =I − 2uu⊤ I − 2uu⊤= I − 2uu⊤ − 2uu⊤ + 4uu⊤ uu⊤= I − 4uu⊤ + 4u(u⊤ u)u⊤ = I,так как u⊤ u = kuk22 = 1.Собственные векторы и собственные значения:H(u) · u = I − 2uu⊤ u = u − 2u(u⊤ u) = u − 2u = −u ;H(u) · v = I − 2uu⊤ v = v − 2u(u⊤ v) = v,поскольку u⊤ v = 0.Собственные векторы и собственные значения:H(u) · u = I − 2uu⊤ u = u − 2u(u⊤ u) = u − 2u = −u ;H(u) · v = I − 2uu⊤ v = v − 2u(u⊤ v) = v,поскольку u⊤ v = 0.Из последних двух свойств матриц отражения следуетгеометрическая интерпретация, которая мотивирует их название.Эти матрицы действительно выполняют преобразование отраженияотносительно гиперплоскости, ортогональной порождающемувектору u.Представим произвольный вектор x в видеx = αu + v,где α ∈ R, u — порождающий матрицу отражения вектор,а v — ему ортогональный.

ТогдаH(u) · x = H(u) · (αu + v) = −αu + v,т. е. в преобразованном векторе компонента, ортогональнаярассматривамой гиперплоскости, сменила направление напротивоположное. Это и есть отражение относительно неё.xuvHxОртогональные матрицы отраженияОпределениеДва вектора u, v ∈ Rn называются коллинеарными, если существуеттакое число γ ∈ R, γ 6= 0, что u = γv.Коллинеарные векторы могут быть сонаправленнымиили противоположно направленными.Ортогональные матрицы отраженияОпределениеДва вектора u, v ∈ Rn называются коллинеарными, если существуеттакое число γ ∈ R, γ 6= 0, что u = γv.Коллинеарные векторы могут быть сонаправленнымиили противоположно направленными.ПредложениеПусть задан вектор e ∈ Rn единичной длины, kek2 = 1.Для любого ненулевого вектора x ∈ Rn существует матрицаотражения, переводящая его в вектор, коллинеарный вектору e.Доказательство.Если H — искомая матрица отражения, и u — порождающий еёвектор Хаусхолдера, то утверждение предложения требуетравенстваHx = x − 2 uu⊤ x = γeс некоторым коэффициентом γ 6= 0.Доказательство.Если H — искомая матрица отражения, и u — порождающий еёвектор Хаусхолдера, то утверждение предложения требуетравенстваHx = x − 2 uu⊤ x = γeс некоторым коэффициентом γ 6= 0.Отдельно рассмотрим два случая:когда векторы x и e неколлинеарны,когда они коллинеарны друг другу.В первом случае можно переписать равенство как2u u⊤ x = x − γe,и правая часть здесь заведомо не равна нулю.В первом случае можно переписать равенство как2u u⊤ x = x − γe,и правая часть здесь заведомо не равна нулю.Тогда и числовой множитель u⊤ x в левой части обязан бытьненулевым, и можно заключить, чтоu=1(x − γe).2u⊤ xЭто означает, что вектор u, порождающий искомую матрицуотражения, должен быть коллинеарен вектору (x − γe).Ортогональная матрица H не изменяет длин векторов,так что kHxk2 = kxk2 .С другой стороны, взяв евклидову норму от обеих частей равенстваHx = γe, получим kHxk2 = |γ| kek2 .

Сопоставляя оба равенства,можем заключитьkxk2 = |γ| kek2 ,т. е. γ = ±kxk2 .Ортогональная матрица H не изменяет длин векторов,так что kHxk2 = kxk2 .С другой стороны, взяв евклидову норму от обеих частей равенстваHx = γe, получим kHxk2 = |γ| kek2 . Сопоставляя оба равенства,можем заключитьkxk2 = |γ| kek2 ,т. е. γ = ±kxk2 .Следовательно, вектор Хаусхолдера u коллинеарен векторамũ = x ± kxk2 e,и для определения u остаётся лишь применить нормировку:u=ũ.kũk2Тогда H = I − 2uu⊤ — искомая матрица отражения.Обсудим теперь случай, когда x коллинеарен e. При этомпредшествующая конструкция частично теряет смысл, так каквектор ũ = x − γe может занулиться при подходящем выборемножителя γ.Обсудим теперь случай, когда x коллинеарен e.

При этомпредшествующая конструкция частично теряет смысл, так каквектор ũ = x − γe может занулиться при подходящем выборемножителя γ.Но даже еслиx − γe = 0для какого-то одного из значений γ = −kxk2 и γ = kxk2 , то дляпротивоположного по знаку значения γ наверняка x − γe 6= 0.Обсудим теперь случай, когда x коллинеарен e. При этомпредшествующая конструкция частично теряет смысл, так каквектор ũ = x − γe может занулиться при подходящем выборемножителя γ.Но даже еслиx − γe = 0для какого-то одного из значений γ = −kxk2 и γ = kxk2 , то дляпротивоположного по знаку значения γ наверняка x − γe 6= 0.Можно также сказать, что конкретный знак у множителяγ = ±kxk2 следует выбирать из условия максимизации нормывектора (x − γe).Далее все рассуждения остаются в силеи приводят к определению вектора Хаусхолдера.Наконец, в случае коллинеарных векторов x и e мы можем простоуказать явную формулу для вектора Хаусхолдера:u=x.kxk2При этомx⊤ x= kxk2 6= 0,kxk2и для соответствующей матрицы отражения имеет местоu⊤ x =Hx = x − 2 uu⊤ x = x − 2u u⊤ x == x−2xkxk2 = −x.kxk2Итак, x снова переводится матрицей H в вектор, коллинеарныйвектору e, т.

е. условие предложения удовлетворено и в этом случае.Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П. ШарыйКафедра математического моделирования НГУЛекция 8 декабря 2017 г.Ортогональные матрицы отраженияОпределениеДва вектора u, v ∈ Rn называются коллинеарными, если существуеттакое число γ ∈ R, γ 6= 0, что u = γv.Коллинеарные векторы могут быть сонаправленнымиили противоположно направленными.Ортогональные матрицы отраженияОпределениеДва вектора u, v ∈ Rn называются коллинеарными, если существуеттакое число γ ∈ R, γ 6= 0, что u = γv.Коллинеарные векторы могут быть сонаправленнымиили противоположно направленными.ПредложениеПусть задан вектор e ∈ Rn единичной длины, kek2 = 1.Для любого ненулевого вектора x ∈ Rn существует матрицаотражения, переводящая его в вектор, коллинеарный вектору e.В доказательстве предложения присутствует неоднозначностьв выборе знака в выраженииũ = x ± kxk2 e,если x и e неколлинеарны.В доказательстве предложения присутствует неоднозначностьв выборе знака в выраженииũ = x ± kxk2 e,если x и e неколлинеарны.В действительности, годится любой знак.Его конкретный выбор может определяться только требованиемустойчивости вычислительного алгоритма.Метод отражений ХаусхолдераМетод Хаусхолдера для решения систем линейных алгебраическихуравнений (который называют также методом отражений)основан на той же идее, что и в методе Гаусса:привести эквивалентными преобразованиями исходнуюсистему к правому (верхнему) треугольному виду,затем воспользоваться обратной подстановкой.Но теперь это приведение выполняется путём последовательногоумножения на специальным образом подобранные матрицыотражения.ПредложениеДля любой квадратной матрицы A существует конечнаяпоследовательность H1 , H2 , .

Характеристики

Список файлов лекций