Вращение Гивенса и отражения Хаусхолдера

[Zloi_templar]

Была задача с помощью вращения Гивенса и отражений Хаусхолдера привести матрицу к верхне-треугольному виду. Реализовал на maple. И вот не могу справиться с одним из дополнительных вопросов: в каком случае можно привести задачу к треугольному виду?

[iifat]

Вот так на первый взгляд — любую.

[Zloi_templar]

iifat
мне кажется тут все не так просто

[iifat]

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

[ewert]

Zloi_templar в сообщении #1053556 писал(а):

в каком случае можно привести задачу к треугольному виду?

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

-- Вт сен 15, 2015 20:29:54 --

(Оффтоп)

iifat в сообщении #1053598 писал(а):

Всё, по-моему, достаточно просто и всегда выполнимо.

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

[iifat]

(Оффтоп)

ewert в сообщении #1053633 писал(а):

пракхтицски же обязательно учитывать ошибки округления

Дык! Истинно как дважды два — четыре с относительной ошибкой, равной сумме относительных ошибок сомножителей!

[Zloi_templar]

А к диагональному?

[ewert]

Zloi_templar в сообщении #1054101 писал(а):

А к диагональному?

А зачем?...

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

[Zloi_templar]

ewert
Почему нельзя?
Вот грубо говоря мы привели к верхнетреугольному виду. Почему нельзя продолжать обнулять элементы сверху??

[ewert]

Zloi_templar в сообщении #1054110 писал(а):

Почему нельзя?

А Вы попробуйте вопрос перевернуть. Любая ли матрица является произведением ортогональной и диагональной?... ну, скажем, треугольная -- является ли?...

[Zloi_templar]

Не любая конечно
Треугольная не является