Н.Н. Калиткин - Численные методы (1133437), страница 35
Текст из файла (страница 35)
Метод интерполяции прост и применим для матриц произвольной структуры, а также для более сложных проблем, Например, общую задачу с!е1 [рга (й)! = О, где каждый элемент матрицы есть некоторый многочлен от А, решают практически только этим методом; разумеется, число узлов по )ь выбирают в соответствии со степенью результирующего многочлена. Лишь в частном случае этой задачи — так называемой обобщенной проблемы собственных значений с!Е1(А — )гВ) =О, разработаны более экономичные методы.
Однако, чем выше порядок матрицы, тем менее выгоден метод интерполяции. Во-первых, число выполняемых арифметических действий возрастает с ростом порядка очень быстро — как па. Вовторых, прн составлении интерполяционного многочлена Ньютона вычисляются разделенные разности, что при высоких порядках приводит к большой потере точности. Поэтому при п)!О (а в случае кратных или близких собственных значеяий и при меньших и) метод интерполяции дает плохие результаты. Для матриц высокого порядка применяют более сложные, но зато более устойчивые и экономичные методы, изложенные в следующих параграфах. Существуют прямые методы Леверье, А.
Н. Крылова, А, М. Данилевского, Сачуэльсона н Ланцоша, позволяющие вычислить все коэффнцненгы характернстнчсского многочлена пронзвольной ма~рнцы примерно за гя арнфметнческнх действий. Онн энономнчней метода интерполяции. Однако в Е 2 главы ч' отмечалось, что корнн многочлена высокой степени могут быть очень чувствительны к погрешностям казффнцвентов. Кроме того, в козффнцненты в сами корнн характеристического многочлена нередко слабо устойчивы по матричным элементам, как было показано в и. 2.
Поэтому указанные выше экономичные методы оказались достаточно устойчивыми только для матриц невысокого порядка л ( 1О, а прн валвчнн кратных влн близких собственных значений — для еще меньшего порядка. Но прв таких порядках матрицы экономия по сравнению с методом интерполяции невелика н не оправдывает прнменення этих довольно сложных н капризных методов. 1б4 АлгеБРАН'гескАЯ ПРОБлемА сОБственных знАчений !гл. о! 4.
Трехдиагольные матрицы. В интерполяционном методе мы находили явное выражение для характеристического многочлеиа только затем, чтобы иметь способ экономного вычисления этого многочлена при заданных Л. Однако для трехдиагональиых матриц (даже очень высокого порядка) есть способ быстрого вычисления с(е1(А — ЛЕ) без нахождения явного выражения характеристического многочлена. Это существенно, ибо матрицы общего вида можно привести к трехдиагольной р ! форме преобразованием подобия.
Рассмотрим этот способ. Обозначим Ютг(Л) ) "! р главиьгй минор п о порядка матриц! )Ъгег) А — ЛЕ через 0,„(Л). Разложим такой --ч.--+--+-- минор по элементам последней строки; в (а ! Б)н„ч;ланг ией всего два ненулевых элемента (рис. + ' ~. ' 30), так что получим = (ам — Л) 0ж, (Л) — ам, зВ,„! (Л), (11). Рис. 30. где через В„,(Л) обозначен минор, до- полняющий элемент а„ж, Этот минор Содержит в последнем столбце только один ненулевой элемент а ь„, поэтому его целесообразно разложить по элементам последнего столбца: В„ ., (Л) = а ., ж0 , (Л). (12) Подставляя (12) в (11), найдем рекуррентное соотношение, выражающее минор высшего порядка через низшие: 0 (Л)=(ам — Л)0т-т(Л) — а и-за -! 0 -э(Л).
(13) Для начала расчета по рекуррентной формуле надо задать два первых минора. Удобно формально положить 0-! (Л) = 0 0е(Л) = 1. (14) Подставляя эти значения в (13) и вычисляя О, (Л) и 0,(Л), легко убедиться, что результат получается правильным. Следовательно, такой способ начала счета приемлем. Однократный расчет величины определителя по формулам (11) — (14) требует всего оп арифметических действий, причем среди них иет делений, и вычисления очень быстрые и устойчивые.
Таким образом, имеется быстрый способ нахождения характеристического многочлена при заданном значении Л. Имеется способ нахождения характеристического мнсгочлена, более эка. номичный при многократных вычислениях. Преобразуя рекуррентное соотнопгение (13), можно получить коз$фициенты характеристического многочлеиа в форме Горнера.
Однократное же вычисление многочлена по схеме Горнера требует всего йл действий. Однако устойчивость этого процесса для высоких порядков матрицы, по-видимому, хуже, а формулы расчета более сложны. 1Е5 ПРОБЛЕМА И ПРОСТЕЙШИЕ МЕТОДЫ Еще один несложный способ вычисления характеристического многочлеиа заключается в следующем. Вычтем заданное значение Л из диагональных элементов агг, а затем найдем определитель получившейся трехдиагональной матрицы по формулам прямого хода прогонки (5.12) †(5.13).
Однако этот способ менее экономичен и устойчив, чем расчет по формуле (13). Корни многочлена Г)„(Л) удобнее всего находить методом парабол (см. 3 2 главы Ч). Этот метод для многочленов не слишком высокой степени (гг(50) достаточно устойчив и позволяет найти все корни с 5 — 7 верными знаками, даже если среди корней есть кратные. В библиотеках многих ЭВМ имеются стандартные программы вычислений всех корней многочлена методом парабол. Иногда для нахождения всех корней характеристического многочлена употребляют метод Ньютона, но детали такого алгоритма хуже отработаны. В основном метод Ньютона применяют к частичной проблеме собственных значений.
Заметим, что при любом способе вычислений для нахождения всех корней требуется удалять уже полученные корни, т. е. переходить к вспомогательной функции 6 (Л) = О, (Л)/Ц (Л вЂ” гч). г =- 1 Поскольку явного выражения характеристического многочлена мы не выписываем, то для вычисления 6 (Л) надо находить отдельно числитель и знаменатель при требуемых значениях Л. Это немного увеличивает объем расчетов. Описанным способом все собственные значения трехдиагональной матрицы находятся довольно легко, причем для этого требуется всего около 50п' арифметических действий '), т. е.
способ экономичен. Поэтому для трехдиагональных матриц этот способ является основным. 5. Почти треугольные матрицы. Для такой матрицы также можно написать формулы, позводяющие легко вычислить определитель при заданаом значе. нии Л. Эго удобно делать методам исилючения Гаусса, учитывая большое количество нулей в матрице определителя. Используем формулы метода исключения (5.3) — (5.5). Для определенности будем считать нашу матрицу верхней почти треугольной.
Тогда видно, что г,„ь=о при т) 5+1, а каждый цикл исключения сводится всего лишь к вычитаниго двух строк. Достаточно при этом помечать изменяющиеся величины штрихом, опуская верхний индекс цикла. После этого формулы Ьго цикла примут внд причем а' и г ь — — О. Г!оследоватсльно полагая А=- 1, 2, ..., л — 1, аннулируем все поддиагональные эяементы. После этого определитель легко вычисляется *) Метод парабол обычно сходится менее чем за 1О итераций, а одна итерация требует 5л действий.
Эти цифры мы будем использовать при описании других методов, 166 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЯ [ГЛ, У! по формуле Чно (5,8): и де1 А= Ц ааы а',=а д, (! 6) а=! Поскольку иас интересует бе1 (А — АЕ), то для его вычисления надо в формулзх (15) — (16) вместо нештрихованных величин аьа всюду подставить ааа-л. Этот способ позволяет вычисли~ь определитель зз л' арифметических действий. Кан и для трехдиагональной матрицы, корни характеристического много. члена можно находить методом парабол. Тогда нахождеаие всех корней лотре.
бует около Юп' действий. Видно, что метод оказывается не быстрым, но довольно простым и устойчивым. Дальше мы увидим, что есть заметно более быстрые способы нахождения собствеипых значений почти треугольной матицы, основанные на преобразовании матрицы и трехдиагональной форме. о они более сложны и менее устойчивы. 6. Обратные итерации. Если собственное значение известно, то собственный вектор удовлетворяет системе (1). Но любой численный метод дает вместо точного собственного значения А! приближенное значение )и, так что г(е((А — АгЕ) ФО, хотЯ отличаетсЯ от нуля очень мало. В таком случае задача (А — ) гЕ) дс=О при использовании приближенного собственного значения имеет только тривиальное решение х=О.
Поэтому в численных расчетах находить собственные векторы непосредственно из системы (1) нельзя. Для нахождения собственных векторов удобен метод обрапдной и!пера!(ии, заключающийся в следующем. Выберем наудачу вектор Ь и рассмотрим линейную неоднородную систему (А — ЦЕ) х=Ь. (17) Определитель этой системы отличен от нуля, так что она имеет единственное решение. Покажем, что найденный из нее вектор х окажется почти равным собственному вектору хд, соответствующему данному собственному значению Аь Для простоты ограничимся случаем, когда матрица л-го порядка имеет л линейно-независимых собственных векторов ху— например, матрица нормальная (для случая произвольных матриц ниже приведен численный пример).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
