Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (1185350), страница 22

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

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

Поэтому правосторонним ортогональнымпреобразованием Q можно привести матрицу A к виду AQ = R, где применена ортогональная матрица Q одного из типов, а R — треугольная матрица, имеющая форму одного из возможных вариантов заполнения (см. подразд. 7.8). При этом преобразованию Q подвергаются не столбцы, а строкиматрицы A, и преобразование Q запоминается по принципу, показанномуранее на рис. 7.5 и рис. 7.8, на месте элементов, обращаемых в нуль.После такого преобразования матрицы A решение системы Ax = z сводится к решению эквивалентной системы с треугольной матрицей Ry = z.Затем искомый вектор определяется через сохраненное преобразование Qкак x = Qy.

Обратная матрица A−1, соответственно, находится как решение системы RY = I с последующим преобразованием Q матрицы Y , т. е.1277 Ортогональные преобразованияX = A−1 = QY . Матрица Q не формируется, из чего видна необходимостьзапоминания преобразований, обеспечивших AQ = R.7.10Двусторонние ортогональные преобразованияОртогональные преобразования, будучи применены одновременно слева исправа к данной матрице A, позволяют приводить ее к формам с нулями какниже, так и выше диагонали. Это, в свою очередь, облегчает решение другихсложных задач (матричная проблема собственных значений [143]).

С помощью ортогональных преобразований для квадратной матрицы широко распространены: приведение симметрической матрицы к трехдиагональномувиду и приведение квадратной матрицы к двухдиагональному виду. Приэтом в качестве ортогональных преобразований одинаково успешно могутбыть использованы преобразования Хаусхолдера или преобразования Гивенса.Приведение симметрической матрицы к трехдиагональному виду.Применим к симметрической матрице слева и справа преобразование Хаусхолдера (или Гивенса), выбирая его из задачи желаемого преобразованияведущего столбца и ведущей строки, а именно: сохранение первого диагонального элемента, получение ненулевых элементов в двух смежных с нимпозициях и получение нулевых элементов в остальных позициях.Лемма 7.3.

Пусть дана матрица A = A(n, n) = AT . Тогда существуетортогональное преобразование Q2 (Хаусхолдера T2 или Гивенса P2 ) такое,что11n−2z}|{ z}|{ z }| {s0a1{11 (7.43)I1 0I1 01{ s1.=AT0 Q20 Q2Ãn−20Замечание 7.6. В (7.43) транспонирование QT2 не требуется, если вкачестве Q2 взято преобразование Хаусхолдера (в силу его симметричности).При этом индекс «2 » указывает на позицию того элемента в ведущем столбце(для левостороннего преобразования) или в ведущей строке (для правостороннего преобразования), который остается ненулевым в этом столбце (в результате применения Q2) или в этой строке (в результате применения QT2 ).1287.10 Двусторонние ортогональные преобразованияВ данном случае, т.

е. в (7.43), эти элементы суть s1 и s1 . Элемент a1 неизменяется, так как I1 — единичная матрица размера 1 × 1.Теорема 7.3 (Тридиагонализация симметрической матрицы). Пустьдана симметрическая матрица A = A(n, n) = AT , A1 := A(n, n) и для каждого j = 1, . . . , k, где k ≤ N = n − 2, выбрано элементарное преобразованиеQj+1 (Хаусхолдера Tj+1 или Гивенса Pj+1 ) так, что1I1 00 Qj+1AjI1 00 QTj+11n−j−1z}|{ z}|{ z }| { sja1{0j1{ sj .=Aj+1n−j−10 (7.44)Тогда после k повторных применений леммы 7.3 имеем отвечающуюэтому моменту процесса итоговую матрицу преобразованийIk0(k)Q =Q(k−1), 1 ≤ k ≤ N = n − 2, Q(0) = In(7.45)0Qk+1и промежуточный результат тридиагонализации данной матрицы A в видеa1 s1Q(k) A Q(k)T=s1 a2 s20s2 .

. . . . .. . . ak sksk0.Ak+1Приведение квадратной матрицы к двухдиагональному виду.Применим к произвольной квадратной матрице слева преобразование Q1и справа преобразование S2 (беря любое из них как преобразование Хаусхолдера или как преобразование Гивенса), при этом Q1 выберем из задачижелаемого преобразования ведущего столбца и S2 — из задачи желаемогопреобразования ведущей строки, а именно: при действии Q1 — получениененулевого диагонального элемента и нулевых элементов ниже него в первом (ведущем) столбце; при действии S2 — сохранение диагонального элемента, получение в смежной с ним позиции ненулевого элемента и нулевыхэлементов правее него в первой (ведущей) строке.1297 Ортогональные преобразованияЛемма 7.4.

Пусть дана матрица A = A(n, n). Тогда существуютортогональное преобразование Q1 (Хаусхолдера или Гивенса) и ортогональное преобразование S2 (Хаусхолдера или Гивенса) такие, что1Q(1) AS (1)1n−2z}|{ z}|{ z }| {1{ s1a01,=n−20Ã(1) Q = Q1 ,0I1(1)S = 0 S .2(7.46)Теорема 7.4 (Бидиагонализация квадратной матрицы). Пусть данаквадратная матрица A = A(n, n), A1 := A и для каждого j = 1, .

. . , k, гдеk ≤ n − 2, выбраны элементарное преобразование Qj (Хаусхолдера типаTj или Гивенса типа Pj ) и элементарное преобразование Sj+1 (Хаусхолдератипа Tj+1 или Гивенса типа Pj+1 ) таким образом, что в результате получаем11n−j−1z}|{ z}|{ z }| {a01{sjjI1 0Qj Aj=.0 Sj+1n−j0Aj+1(7.47)Тогда после k повторных применений леммы 7.4 имеем отвечающие этомумоменту процесса итоговые матрицы преобразованийIk−10Q(k) =Q(k−1), k ≤ n − 2, Q(0) = In , Q(1) = Q1 ,0Qk(7.48)Ik0I10(k)(k−1)(1)S =S, k ≤ n − 2, S =0Sk+10S2и промежуточный результат бидиагонализации данной матрицы A в видеs1 a1Q(k) AS (k) =s2 a20... ...sk ak0130Ak+1.7.11 Ортогонализация Грама–ШмидтаВыполнив после k = n − 2 еще одно левостороннее преобразование Qn−1(что отвечает применению верхней формулы (7.48) для k = n − 1), получаемокончательноs1 a1s2 a20... ....sn−1an−1Q(n−1)AS (n−2) =0snОсновное применение указанных двусторонних ортогональных преобразований заключается в вычислении сингулярных значений [13] произвольной матрицы A = A(n, n), а также в решении проблемы собственных значений [143].

Однако эти преобразовавания можно использовать и для решения системы линейных алгебраических уравнений Ax = f . После приведения матрицы к двух– или трехдиагональному виду система уравнений легкорешается. Например, в случае с трехдиагональной матрицей система оченьэффективно решается методом прогонки [12].7.11Ортогонализация Грама–ШмидтаПусть A = A(m, n) — матрица, имеющая m строк и n столбцов, причем m ≥ n. Обозначая i-й столбец через ai , запишем A = [a1, a2 , . . .

, an],ai ∈ Rm . Рассмотрим случай матрицы полного ранга, т. е. rank A = n. Тогданабор векторов {ai } порождает некоторое подпространство L ∈ Rm , т. е.может считаться его базисом. Назовем этот набор исходным базисом и преобразуем его в ортонормированный базис. Такое преобразование называетсяпроцедурой ортогонализации системы векторов {a1 , a2, . . . , an }.Согласно определению, ортонормированным базисом в L ∈ Rm называется система векторов {q1, q2, . . .

, qn} такая, что1) ∀i : qi ∈ Rm , m ≥ n, qiT qi = kqik2 = 1;2) ∀i, j, i 6= j : qiT qj = 0и любой вектор ai имеет единственное представлениеai =nXqj bji, i = 1, 2, . . . , n,j=11317 Ортогональные преобразованиягде bTi = (b1i, b2i, . . . , bni) — вектор-строка некоторых коэффициентов. Следовательно, матрицу A можно представить в виде произведения двух матрицA = QB, где Q = [q1, q2, . .

. , qn] — матрица размера (m×n), составленная изстолбцов qi ∈ Rm , а B = [b1, b2, . . . , bn ] — матрица размера (n × n), составленная из столбцов bi ∈ Rn . Матрица Q = Q(m, n) в этом представлениисостоит из ортонормированных векторов-столбцов, в частном случае m = nв качестве Q имеем ортогональную матрицу, т.

е. QT Q = I.Таким образом, ортогонализация столбцов матрицы A есть представление A = QB, где Q — матрица тех же размеров, что и A, но в отличие от A,имеющая ортонормированные столбцы, при этом B — квадратная матрица,обеспечивающая равенство A = QB. Очевидно, существует бесконечноемножество таких представлений матрицы A, поскольку число ортонормированных базисов не ограничено. Для обеспечения единственности средимножества версий A = QB выберем представление, при котором B —треугольная матрица, которую далее традиционно будем обозначать R,поскольку в ней оказывается заполнен правый (right) верхний угол, т.

е.R = Rne . Хотя традиционно ортогонализацией Грама–Шмидта называютотыскание по матрице A такой матрицы Q, что A = QR, где R = Rne , дляR будем допускать все четыре возможных варианта заполнения (см. подразд. 7.8):✧✧✧✧вариантвариантвариантвариант1:2:3:4:R = Rne , гдеR = Rsw , гдеR = Rse , гдеR = Rnw , гдеRne —Rsw —Rse —Rnw —верхняя правая треугольная матрица;нижняя левая треугольная матрица;нижняя правая треугольная матрица;верхняя левая треугольная матрица.Для ортогонализации системы векторов вычисление матрицы R в явномвиде может и не требоваться, хотя такое вычисление всегда присутствует.Hиже, рассматривая ортогонализацию Грама–Шмидта обобщенно, т. е. вовсевозможных вариантах треугольного заполнения матрицы R, мы будемтребовать явного нахождения факторов (сомножителей) Q и R в разложении A = QR.

Для любого из вариантов возможны три формы алгоритма,отличающиеся порядком действий.•Грама–Шмидта Ортогонализация (ГШО)Этот вариант алгоритма предполагает вычисление ненулевых элементов матрицы R по столбцам, начиная с самого короткого (одноэлементного) столбца.1327.12 Алгоритмы ортогонализации Грама–Шмидта•Модифицированная ГШО (МГШО)В этом варианте ненулевые элементы матрицы R вычисляются по строкам, начиная с самой длинной (состоящей из n элементов) строки.•МГШО с выбором ведущего вектораЭтот вариант МГШО-алгоритма использует стратегию выбора ведущего вектора.

В качестве очередного, подлежащего ортогонализациивектора, выбирается тот из оставшихся столбцов матрицы A, которыйимеет наибольшую длину (евклидову норму). Хотя эта стратегия требует дополнительных вычислительных затрат, в некоторых плохо обусловленных задачах она так же полезна, как и выбор главного элементав методе Гаусса.Таким oбpaзом, данной темой — ортогонализация Грама–Шмидта — впредлагаемом проекте (см. подразд. 7.16) охвачено (4 × 3) = 12 различныхвариантов задачи разложения A = QR.Замечание 7.7.

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

Список файлов книги