Cтраница 3
В главе 14 рассмотрены тщательно разработанные и эффективные методы, основанные на блочной обратной итерации. Они совершенствовались физиками, инженерами и специалистами по численным методам начиная с 1960 - х годов в тот период, когда алгоритм Ланцоша находился в тени. Сомневаюсь, что в будущем они сохранят свое превосходство. [31]
Успешное применение метода сопряженных градиентов можно гарантировать лишь тогда, когда матрица А положительно ( или отрицательно) определена. Почему это ограничение существенно и как избавиться от него, помогает понять обнаруженная Пэйджем и Саундерсом ( 1973) аналогия между методом сопряженных градиентов и алгоритмом Ланцоша ( 1950) тридиагонализащга матрицы. [32]
Точный алгоритм может быть представлен несколькими способами. В действительности это уже было сделано при его появлении в § 7.2, где конструктивное доказательство того факта, что qj полностью определяет приведение А к трехдиагональной форме T ( Q AQ) является просто изложением алгоритма Ланцоша. [33]
В этом случае оператор L представляет собой комплексную самосопряженную матрицу. Оператор Г диагоналеп, поэтому матрица оператора - ( L-ИГ) не является ни эрмитовой, ни симметричной. Для эффективной работы алгоритма Ланцоша необходимо преобразовать оператор - ( L - - it) к симметричному виду, что достигается приведением оператора L к форме действительной симметричной матрицы. [34]
Привлекательной и удачной альтернативой является продолжение процесса вплоть до тех пор, пока первые пары Ритца не сойдутся и не будет потеряна ортогональность. Тогда нужно начать с нового R0, столбцы которого ортогональны ко всем известным собственным векторам, и продолжать итерировать таким образом, пока не будут найдены все требуемые собственные векторы. Значительная часть эффективности алгоритма Ланцоша теряется при этих возобновлениях, и выбор нового подходящего R0 с использованием информации о предыдущих прогонах процесса требует дополнительных усилий. [35]
Кроме того, расчет спектра ЭПР из три-диагональной матрицы Фи необходимо делать несколько раз. Мы предлагаем другой способ выбора размерности базиса Лан-цоша, причем этот способ не требует дополнительных затрат времени и оперативной памяти. На каждом шаге алгоритма Ланцоша строится базисный вектор т), ортогональный к двум предыдущим. В связи с этим в работе [6] рассмотрены возможности реортогонализации базиса с целью получения большего числа собственных значений и собственных векторов с нужной точностью. Отметим, что 1 1) 1; Ч 2) 0; ( 11 3 ci 10 - le, что соответствует точности машинного представления действительных чисел в арифметике 8-байтных чисел. Более того, нет необходимости проверять ортогональность нового базисного вектора ко всем остальным, поскольку такой способ требовал бы хранения всего базисного набора и заведомо нерационален. Мы проверяем ортогональность каждого нового базисного вектора лишь по отношению к стартовому вектору. [36]
Заметим, что г, ортогонализуется также и к qy и q / i. Таким образом, нужно хранить все векторы q и арифметическая стоимость каждого шага резко возрастает ( см. упр. Этот вариант процесса называется алгоритмом Ланцоша с переортогонализацией. [37]
Кроме того, матричные элементы верхних треугольных подматриц 1 - 4 хранятся не все. Элементы этих подматриц содержат общий множитель, одинаковый для групп матриц I-III и IV-VII, поэтому в целях экономии ресурсов оперативной памяти в ней хранится всего одна треугольная матрица типа I, содержащая общий множитель для группы I-III и одна треугольная матрица для группы IV-VII. Полностью матричные элементы оператора L вычисляются непосредственно на каждом шаге алгоритма Ланцоша. [38]
В результате проделанного анализа и экспериментального опыта Пэж пришел к заключению, то простой процесс Ланцоша может продолжаться настолько долго, насколько позволяет память. В конце процесса вычисляются все нужные пары Ритца, а дублирующие копии просто отбрасываются. Эта схема с успехом используется, но в остальных параграфах главы мы рассмотрим видоизмененный алгоритм Ланцоша в стиле Пэжа, который более эффективен и, что важнее, им можно пользоваться автоматически без какой-либо дополнительной экспертизы. [39]
Алгоритм Ланцоша, сформулированный для эрмитовых операторов, был модифицирован Моро и Фридом [3 ] для работы с комплексным симметричным оператором - ( L - f - zT) переопределением нормы вектора в комплекс-ном пространстве так, что норма стала комплексной. В пространстве с переопределенной таким способом метрикой неприменимы критерии сходимости, используемые в обычном метрическом пространстве, поэтому этот этап решения спектральной задачи требует особого рассмотрения. В работе [3] предлагается следующий способ выбора размерности базиса Ланцоша: начиная с некоторого ( обычно выбранного заранее) шага алгоритма Ланцоша, нужно следить за сходимостью спектральной функции. [40]
В следующей главе вводится специальная последовательность подпространств, называемых ( без достаточных оснований) подпространствами Крылова. К ним применяется процедура Релея - Ритца. Эта теория устанавливает большой потенциал алгоритма Ланцоша для вычисления собственных значений. [41]
Интересно сравнить время решения примера 2 по программе, приведенной в работе [2], и с использованием алгоритма Ланцоша. На ЭВМ PDP-11 / 34, по данным Фрида [3], необходимо соответственно 6 ч и 15 мин. На машине М-4030 это время составляет соответственно, 4 ч 40 мин и 6 4 мин. Значительно большая эффективность нашей программы, вероятно, обусловлена удачным выбором структуры данных и / или использованием другой версии алгоритма Ланцоша. [42]
В главе 13 анализируются широко распространенные опасения, что округления могут помешать в сборе того богатого урожая, какой обещала гл. В своей неопубликованной диссертации ( 1971 год) Пэж показал, что эти опасения неосновательны. Приводя доказательство основной теоремы, я пытался очистить его от мелких деталей, которые обременяют глубокий пионерский анализ, проведенный Пэжем для простого алгоритма Ланцоша. Далее изложена выборочная ортогонализация, которая представляет собой направляемую теорией Пэжа модификацию, ослабляющую весьма экономичным образом потерю ортогональности векторами Ланцоша-этой потери обычно очень боятся. Метод опубликован в 1978 году и продолжает совершенствоваться. Глава заканчивается обсуждением блочных схем алгоритма Ланцоша, необходимых, по всей видимости для обработки очень больших матриц. [43]