1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 37
Текст из файла (страница 37)
Поэтому в численных расчетах находить собственные векторы непосредственно из системы (1) нельзя. Для нахождения собственных векторов удобен метод обрапдной и!пера!(ии, заключающийся в следующем. Выберем наудачу вектор Ь и рассмотрим линейную неоднородную систему (А — ЦЕ) х=Ь. (17) Определитель этой системы отличен от нуля, так что она имеет единственное решение. Покажем, что найденный из нее вектор х окажется почти равным собственному вектору хд, соответствующему данному собственному значению Аь Для простоты ограничимся случаем, когда матрица л-го порядка имеет л линейно-независимых собственных векторов ху— например, матрица нормальная (для случая произвольных матриц ниже приведен численный пример).
Тогда собственные векторы образуют базис, по которому можно разложить векторы х и Ь: и е х= У Е;х,, Ь= У(),х,. (18) !=1 д= ! Подставляя это разложение в систему (17), перенося все члены влево и учитывая, что Ах;=Ах„попучиы У (8, ().! — ).!) — ().1хт = О. 1.= ! Поскольку собственные векторы линейно-независимы, то их линейная комбинация обращается в нуль только в' том случае, когда 167 ПРОБЛЕМА И ПРОСТЕЙШИЕ МЕТОДЫ $ и все ее коэффициенты равны нулю.
Поэтому из (19) следует ! (20) "/ ! Видно, что если )! — Л!, то коэффициент $7 будет очень большим; в противном случае он невелик. Рассмотрим следствия из этого в трех основных случаях. Первый случай — собственное значение )'! простое, Тогда из всех коэффициентов $7, 1=/= и, только один коэффициент $! оказывается очень боЛьшим. Это означает, что найденный вектор х почти совпадает с собственным вектором х; (с точностью до нормировочного множителя), что и требовалось доказать.
Заметим, что поскольку найденный вектор х оказывается очень большим, то его обычно нормируют. Из (20) видно, что при обратной итерации (т. е. при переходе от Ь к х) компонента р! усиливается по сравнению с другими компонентами р; примерно во столько раз, во сколько погрешность данного собственного значения меньше разности соседних собственных значений. Поэтому чем точнее найдено Ц (очевидно, хорошая точность особенно важна при наличии близких собствеинь!х значений), тем ближе х будет к хь Если собственные значения найдены слишком грубо, или случайно вектор Ь выбран неудачно, так что р! очень мало, то разница между х и х, может оказаться заметной.
Тогда подставляют найденный вектор х в правую часть уравнения (17) вместо Ь и организуют итерационный процесс (А )).,Е) х!м х! -и х!м Ь (21) Обычно он сходится настолько быстро, что двух итераций вполне достаточно. Напомним, что на каждой итерации обязательно надо нормировать найденные х!', чтобы не получать в расчетах слишком больших чисел, вызывающих переполнение на ЭВМ. Замечание 1. Очень эффективен один простой способ выбора Ь.
В качестве его компонент в декартовых координатах возьмем последовательные многоразрядные псевдослучайные числа у, (см. 9 4 главы 1Ъ'). Тогда вероятность того, что б! окажется очень малым, будет ничтожна. В т о р о й с л у ч а й — собственное значение А! кратно; например, ),,=Лэ=...=)!р, 1(р=п. Напомним, что в этом случае собственные векторы х„х„..., хр определены неоднозначно; любая их линейная комбинация удовлетворяет уравнению л А ', ~ а!Х!, '=- ~ и!АХ,=Л! ~~",сс!Х! !=! !=! и является собственным вектором. Т.
е, они порождают р-мерное !68 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЯ !ГЛ, У! подпространство, любой базис которого можно взять в качестве системы искомых собственных векторов. Теперь из (20) следует, что большими оказываются коэффициенты $„$«, ..., $р, причем степень их усиления одинакова; остальные коэффициенты остаются малыми. Значит, найденный из (!7) вектор х будет приближенно линейной комбинацией х, х„..., хр, а тем самым — искомым собственным вектором. Если точность !!олученного приближения недостаточна, то обратную итерацию повторяют снова по формуле (21). Чтобы найти все собственные векторы для кратного собственного значения, возьмем столько линейно-независимых векторов Ьм!, какова кратность корня. Обратными итерациями получим столько же векторов х!»!, которые н будут искомыми; они будут линейно- независимыми, поскольку преобразование (17) невырожденное.
Остается только ортогонализовать найденные векторы, если это требуется по условиям задачи. Напомним, что в качестве декартовых координат векторов Ь!»! целесообразно брать псевдослучайные числа; здесь это имеет то дополнительное преимущество, что векторы автоматически получаются линейно-независимыми, Третий случай — когда матрица имеет кратные корни, но число ее собственных векторов меньше и — выходит за рамки нашего доказательства. Однако метод обратных итераций здесь также применим в той форме, которая описана для кратных корней.
Разница лишь в том, что если р-кратному собственному значению соответствуют всего д собственных вектоББОБ (д(р), то из полученных обратной итерацией векторов х' ' только !) будут линейно-независимыми. Это выясняется при их ортогонализацин: первые д векторов ортогонализуются «без приключений», а при ортогоналнзации следующих векторов их компоненты обращаются почти в нуль (в пределах погрешности расчета). Каков объем расчетов в методе обратной итерации? Нахождение собственного вектора требует (при одной итерации) не более »/»п» действий, так что для нахождения всех их надо около п' арифметических действий.
Таким образом, при больших порядках матрицы метод неэкономичен, но при п=!0 вполне удовлетворителен. Особенно употребителен этот метод из-за своей простоты, универсальности и хорошей устойчивости алгоритма. В некоторых частных случаях расчеты существенно упрощаются и ускоряются. Наиболее важен случай трехднагональной матрицы. При этом линейная система уравнений (17) для определения компонент собственных векторов также будет трехдиагональной, и ее решают экономичным методом прогонки по несложным формулам (5.10) — (5.12).
Для вычисления одного собственного вектора в этом случае требуется 10п, а для всех — 10п' арифметических действий. !Ей ПРОБЛЕМА И ПРОСТЕЙШНЕ МЕТОДЫ ап Для почти треугольной матрицы в методе обратных итераций требуется решать линейную систему с почти треугольной матркцей, что делается специальным вариантом метода исключения. Если учесть, что случайный вектор в правой части ()7) можно задавать уже после приведения матрицы в методе исключения Гаусса к треугольной форме, то нахождение каждого собственнаго вектора требует 272пз действий (тот же прием для трсхдиагональной матрицы позволяет сократить число действий до 7п). А для нахождения всех соб:тненных векторов требуется соответственна 272пз арифметических действий.
Отметим одну существенную деталь. Поскольку г)е1 (Л вЂ” )чЕ) =О, то при нахождении собственных векторов в формулах прямого хода метода исключений (прогонки) на главной диагонали появится хотя бы один очень малый эЛемент. Чтобы формально можно было вести расчет, диагональные элементы не должны обращаться в нуль; для этого надо, чтобы погрешность собственного значения была не слишком мала, т. е.
составляла бы 10 — 15 последних двоичных разрядов числа на ЭВМ. Если корни характеристического миогочлена находят методом парабол (или секущих), то такая погрешность получается естественно, ибо из-за ошибок округления эти методы перестают сходиться в очень малой окрестности корня. Но если корни определялись методом Ньютона, то при этом могли быть найдены верно все знаки собственного значения; тогда, чтобы избежать деления на нуль, приходится специально вносить в )и небольшие погрешности.
Пример, Возьмем жорданову подматрицу 01 четвертого порядка (3) и приближенное собственное значение Х =-а — в. В качестве Ь выберем вектор с единнчныии декартовыми координатами, Тогда уравнение (!7) примет вид (22а) Последовательно находим компоненты вектора х х =в-' 1— х, = — в-'+ в-' х,=аз †аз' з-4+ в-3 а-2+ в-1 Затем нормнруем вектор, умножив все компоненты на — в-1; х, = ! + 0 (е), к, = 0 (е), х, = 0 (в'), ка — — 0 (в'). (22в) Полученный вектор х —.— е>+0(г) приближенно равен собственному вектору жордановой матрацы (см. й. !), что нам и требовалось.
Папутво заметим, что в промежугочных выкладках (22б) возникали высокие обратные степени пот> решности и, чего не бывасг у матриц с п собственными векторами. Это показывает, что случай матриц, содержащих жорданоны подматрицы высокого порядка, труден для численных расчетов на ЭВМ, нбо в них легко возникают переполнения, 170 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЯ 1ГЛ, Уг $2. Эрмитовы матрицы 1. Метод отражения. Существуют экономичные и устойчивые методы нахождения всех собственных значений матриц высокого порядка*).
Они основаны на приведении матрицы преобразованием подобия к трехдиагональной или другим простым формам, для которых проблема собственных значений решается легко. Сейчас мы рассмотрим метод отражений, который позволяет подобно преобразовать произвольную матрицу к почти треугольной форме за (1013)па арифметических действий, а эрмитову матрицу к трехдиагональной форме — всего за ')апа действий. Поскольку для трехдиагональной матрицы все собственные значения находятся очень экономично, то для эрмитовых матриц метод отражения является самым быстрым из известных методов решения полной проблемы собственных значений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
