Исследование числовых матриц на линейную независимость строк. Элементарные операции. Гауссово исключение. Преобразование Хаусхольдера. Строчно поисковый алгоритм. Форма Гейзенберга, страница 2

Численная устойчивость исключения может быть улучшена благодаря использованию  преобразованияХаусхольдера (Householder transformation). Пусть I будет устойчивой матрицей. Преобразованием Хаусхольдера называется квадратная матрица вида

с хх^t=1, где х- столбцовый вектор и х^tего транспонирование. Очевидно, что

,следовательно, Hсимметричная матрица. Ввиду этого , а также используя  хх^t=1, получим

, т.е. H^-1=H^t, следовательно, H – ортогональная матрица. Поэтому все сингулярные значения Hравны 1 и ее число обусловленности (condition number), определенное как отношение наибольшего и наименьшего сингулярных значений , равно 1. Таким образом, использование преобразования Хаусхольдера не ухудшает численные свойства задачи.

Важное свойство преобразования Хаусхольдера состоит в том, что для заданных двух векторов a и b с равными нормами Эвклида  существует преобразование Хаусхольдера Н такое , что На=b. Действительно,  если выберем , то

Так как  по предположению и   ввиду независимости скалярного произведения от транспонирования,  имеем

Это доказывает утверждение. Сейчас, используя данное свойство, покажем, что К₁   и  К₂ в (1.2) и (1.3) могут быть выбраны как преобразования Хаусхольдера.

Рассмотрим n*m матрицу А заданную в(1.1). Прежде всего вычислим норму σ первого столбца а₁ матрицы А. Выберем b₁ равным

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

Численная устойчивость этого процесса  может быть далее улучшена перестановкой столбцов. Вначале мы вычисляем норму всех столбцов А. Далее переставляем столбец с наибольшей нормой с первым столбцом. Далее применяем хаусхольдерово преобразование, что соответствует исключению. Подобным образом диагональные элементы результирующей матрицы будут располагаться в порядке убывания по амплитуде. Назовем этот процесс преобразованием Хаусхольдера с упорядочением (Householder transformation with pivoting).

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

1.4.  Строчно поисковый алгоритм

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

Пусть (i,j)- й  элемент n*m матрицы  А обозначен а_ij . Пусть а_1к будет некоторой ненулевой элемент первой строки матрицы А. Этот элемент будет называть ведущим элементом (pivot element) или просто ведущим (pivot). Введем матрицы