Беклемишев - Дополнительные главы линейной алгебры (947281), страница 41
Текст из файла (страница 41)
В этом случае матрицы Рии, и Ри+, могут быть получены ЯР-разложением матрицы А. Объединяя формулы (7), мы можем, как и в предыдущих случаях, записать сразу результат Й-й итерации: АиРи = РийгиРи,... Р,. Если начинать процесс с единичной матрицы и ввести обозначение Уи = ВЯ», ... Р„то мы получим Аи Р (7„ Так как матрица Уи — верхняя треугольная, последняя формула может рассматриваться как (~77-разложение А". Этот процесс позволяет найти все характеристические числа и, по крайней мере для симметричной матрицы, собственные векторы, но обычно проводится в другой, гораздо более удобной форме. К ее описанию мы и переходим. 5. (Я-алгоритм.
Основой этого алгоритма является следующий процесс. Найдем ЯЯ-разложение исходной матрицы. Пусть А = йи)7и. Положим А, = )7Ди и найдем для матрицы Аи ее ЯЯ-разложение Аи —— Яи)г,. Матрицу А, получим, переставив 1В1 » К ВЫЧИСЛЕНИЕ СОБСТВЕННЫХ ВЕКТОРОВ сомножители Я, и Р„и вообще А»»= Я»Р», А» — — РД». (8) При этом 1»» = м»'А, „и потому А» = ~КА» ~». Отсюда А» = Ж ° ° ° В'АЯ» ° ° ° Я» = Р»'ЛРЫ (9) где Р»=Й" Я». Это показывает, что характеристические числа всех матриц А» совпадают с характеристическими числами матрицы Л. Если обозначить произведение Р».,Я» через (»», то я-я степень матрицы А может быть выражена так: А» = Р»(У».
(10) Действительно, Р»(У» = Я»... Я»Р»... Р» = Я,... 0»»А» Я»»... Р» = Р»,А, »()»». Но из формулы (9), написанной для А», следует Р»»А»,= АР, „ и потому РЯ»=АР»,(У»» Формула (1О) получается последовательным применением этого результата и устанавливает связь с процессом, описанным в конце предыдущего пункта, Хотелось бы утверждать, что последовательность матриц А» сходится к блочно треугольной матрице, но, к сожалению, это не так. Можно доказать лишь, что те элементы Л», которые лежат ниже диагональных клеток, стремятся к нулю, а элементы этих клеток и вышележащие элементы равномерно ограничены. Последовательность матриц с таким свойством называется сходящейся по ' 4юрлы к блочно треугольной матрице. По-видимому, пока не существует доказательства этого утверждения, настолько простого, чтобы его можно было здесь воспроизвести.
Для того чтобы подробнее описать «предельную» матрицу А получаемую Яй-алгоритмом, предположим, что характеристические числа А пронумерованы в порядке невозрастания модулей: ~),)=...=~),,()~)„+1~=...=(),,„,,~)...)()„, 1=...=)),„!. Матрицу А» можно разбить на клетки, соответствующие группам равных по модулю характеристических чисел. Удается доказать, что элементы (1, 1)-й поддиагональной клетки при 1) 1 стремятся к нулю не медленнее, чем о(ж~ ~~~~), где и — максимальная из кратностей корней в мииимальиом много- члене матрицы А (см. Воеводин Я).
гл. Ие ВВедение В численные методы В «предельной» матрице диагональные клетки соответствуют группам равных по модулю характеристических чисел. При этом характеристические числа клетки совпадают с характеристическими числами матрицы А, принадлежащими соответствующей группе. Например, простой комплексно сопряженной паре 1,, г. соответст'- вует диагональная клетка второго порядка, с характеристическими числами Х н ь.
Допустим, что матрица А имеет полную систему из собственных векторов и Х вЂ” матрица, столбцы котсрой — собственные векторы матрицы А, Обозначим через Я ортогональную матрицу, входящую в 1,нт-разложение матрицы Х. Тогда может быть доказано, что найдутся такие ортогональные диагональные матрицы Т», чго ТД~,— Я . Это соотношение особенно существенно в случае симметричной матрицы г1, так как оно позволяет найти ее ортсеормированный базис из собственных векторов. Обычно размеры диагональных клеток предельной матрицы А бывают невелики и соответствующие характеристические числа находятся без труда. После того как это сделано, соответствующие собственные векторы находятся обратным степенным методом со сдвнгом. 6.
Приведение матрицы к почти треугольной форме. Кагкдый шаг В~-алгоритма состоит из нахождения ДР-разложения матрицы и умножения матриц и требует осуществления значительного числа арифметических операций. Эта работа может быть существенно сокращена, если предварительно подготовить матрицу А, приведя ее к почти треугольной форме. По определению матрица А с элементами а;„является правой почти треугольной, если ац = О при 1~ 1+ 1, Таким образом, ниже главной диагонали могут отличаться от нуля только элементы ряда, идущего параллельно диагонали непосредственно рядом с ней.
Аналогично определяются левые почти треугольные матрицы. П р е д л о ж е н и е 1. Для любой матрицы Л может быть построена ортогональная матрица 5 такая, что л~атрица Я-'Л5— правая почти треугольная. Матрица преобразуется в правую почти треугольную последцвательными шагами, на каждом из которых приводится к нужному виду один столбец. Пусть за г — 1 шаг она переведена в мат. рицу А~', у которой первые г — 1 столбцов соответствуют правой почти треугольной форме. Тогда матрица АР+И получается по формуле Ам+И Р АочР где Р, — матрица отражения (п.
6 Э 3). Матрица отражения симметрична и ортогональна: Р, «Рт = Р,'. Поэтому А1'+м ме = Р,'АспР . $6. ВЫЧИСЛЕНИЕ СОБСТВЕННЫХ ВЕКТОРОВ !Ез Опишем выбор матрицы Р,. Если в г-м столбце матрицы А( 1 последние и — г элементов — нули, то в преобразовании этого столбца необходимости нет, и мы переходим к (г+ 1)-му шагу, преобразующему (г + 1)-й столбец.
В противном случае строится отражение, которое переводит вектор и=(10, ..., О, а<'>,,, ..., соп'(г в вектор, пропорциональный (г + 1)-му столбцу единичной матрицы. Обратим внимание на то, что этот выбор отличается от сделанного при построении ЯЯ-разложения методом отражений. Там в г-м столбце заменялнсь на нули не г, а г — 1 первых элементов, и полученный столбец переводился в пропорциональный г-му столбцу единичной матрицы. В результате сейчас будет построена матрица отражения Р„ у которой первые г столбцов и строк совпадают с соответствующими строками и столбцами единичной матрицы.
Прн умноженцн А " слева на Р, первые г строк Л<' останутся неизменными, не изменятся нулевые элементы столбцов с номерамн ( г, последние и — (г + 1) элементов г-го столбца обратятся в нуль. При умножении матрицы на Р, справа не изменятся ее первые г столбцов, и потому вид, достигнутый после умножения слева, будет сохранен, Последним столбцом, нуждающимся в преобразовании, будет (и — 2)-й. Следовательно, после и — 2 шагов матрица А будет переведена в верхнюю почти треутольную матрицу.
П р е д л о ж е и н е 2. Верхняя почти треугольная форма матрицы не утрачпвается при преобразованиях матрицы по ЯР-алгоритлид Д о к а з г т е л ь с т в о. Пусть А — верхняя почти треугольная матрица. Она может быть преобразована в верхнюю треугольную )с умножением слева на матрицы вращений в плоскостях, натянутых на пары базисных векторов с номерами (1, 2), (2, 3), (3, 4), ...
..., (и — 1, п). Следовательно, ЯР-разложение Л имеет вид г т Л=РЫ...Р„ь „гс, а матрица А, равна А~ = РЯ= КР~~з... Р„' Умножение справа на указанные матрицы вращений может изменить в матрице Р только наддиагональные и диагональные клетки второго порядка. При этом треугольная матрица может превратиться только в почти треугольную. П р е д л о ж е н и е 3. Симметричность матрицы А не нарушается при применении к ней Я!с-алгоршпма, Действительно, если А симметрична и А = (К, то А = Аг = ЯЩТ, откуда Яг = фс9. Теперь, если Ат = 1ТЯ, то А,' = ч ЦТРТ ЯТЯЯЯ = А„, что и требовалось. 184 гл. нь вввданиа в чнслвнныа методы Если матрица симметрична и приведена ортогональной матрнцей 8 к почти треугольной форме, то полученная матрица 5"'АЯ также будет симметричной.
Симметричные почти треугольные матрицы называются трехдиагональными. В такой матрице могут быть ненулевыми только элементы главной диагонали и двух параллельных ей рядов непосредственно выше и ниже нее. ЯД-алгоритм практически всегда применяется к почти треугольным матрицам, а в симметричном случае — к трехднагональным. Отметим, что 1;1Д-разложение почти треугольной матрицы выгоднее всего получать методом вращений — как мы видели при доказательстве предложения 2, для этого требуется только и — 1 вращение. 7.
Ускорение сходимости ЯК-алгоритма. Приведенная выше оценка (11) показывает, что скорость сходимости 1Я-алгоритма в том виде, как он описан, может оказаться очень низкой. Разработаны улучшения этого алгоритма, позволяющие существенно увеличить скорость сходимости. а) П о н н ж е н и е п о р я д к а. Если в процессе преобразований почти треугольной матрицы по ~,'1Р-алгоритму один из поддиагональных элементов становится пренебрежимо малым, то после замены его на нуль матрица становится клеточно треугольной с почти треугольными диагональными клетками.
Все характеристические числа исходной матрицы будут получены, если мы найдем характеристические числа диагональных клеток. Поэтому с появлением нулевых поддиагональных элементов размеры решаемой задачи снижаются. б) С д в и г и. Пусть задана числовая последовательность ( р»), называемая лоследовательносавю сдвигов. Я»г-алгоритм со сдвигом определяется формулами Л, 1 — р»Е=а,й», Л» —— РД»+р»Е Нетрудно доказать, что и в этом случае Л» = Р»АР», где Р, = т = Я,...Я». Таким образом, характеристические числа всех матриц Л, совпадают с характеристическими числами матрицы А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
