566 ОБЗОР МЕТОДОВ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ [ГЛ. 11

Активный прогресс в области спектральной оптимизации ите-
рационных методов стимулирует постановку ряда проблем. Сле-
дует иметь в виду, что спектральные методы оптимизации особен-
но эффективны в случае решения серии задач с одним и тем же
оператором, но разными входными данными.

Второе направление связано с применением вариационных
принципов. Методы этого класса осуществляют последовательную
минимизацию некоторого функционала (как правило, квадратич-
ного), который достигает минимального значения на искомом ре-
шении системы. Основы вариационного подхода к построению
итерационных методов заложены Л. В. Канторовичем [II], Лан-
цошем [З], Хестенсом, Штифелем [II], М. А. Красносельским,
С. Г. Крейном [11] и др. Из последних исследований нужно отме-
тить работы Петришина [9, Ю], Форсайта [II], Даниеля [II],
Г. И. Марчука,   Ю. А. Кузнецова  [3, И], С. К. Годунова,
Г. П. Прокопова [II], В. И. Лебедева [9], Н. И. Горбенко,
В. П. Ильина [11] и др.

Достоинство вариационных методов типа наискорейшего спус-
ка и итерационного процесса с минимальными невязками состоит
в том, что параметры релаксации выбираются за счет использова-
ния апостериорной информации, получаемой на каждом шаге.
Скорость сходимости таких многошаговых методов не ниже, чем
для методов, использующих полиномы Чебышева. Существенным
является также то, что такие методы сходятся как для симметрич-
ных, так и несимметричных матриц при условии их положитель-
ной определенности. В последнее время удалось построить ряд эф-
фективных методов типа минимальных невязок для положитель-
но полуопределенных матриц.

Важным обстоятельством, сдерживающим до настоящего вре-
мени развитие нестационарных вариационных методов, является
необходимость хранить большее, по сравнению с чебышевскими
методами оптимизации, количество промежуточной информации.

В последнее время развиваются итерационные методы, в кото-
рых сочетается подход спектральных и вариационных оптимиза-
ций. В. И. Лебедев сформулировал условия на операторы задач,
для которых итерационный процесс имеет неулучшаемую оценку
числа арифметических операций. Развивается еще один метод вы-
бора оптимальных параметров итерации, основанный на вероят-
ностном подходе. Ряд интересных результатов в этой области по-
лучен Ю. В. Воробьевым [9]. До сих пор не утратил своего боль-
шого значения ставший уже классическим метод верхней релак-
сации Янга — Франкела [Ю]. Исследования этого метода обобще-
ны в монографиях Вазова, Форсайта [З], Варги [З], Изаксона, Кел-
лера [З], Янга [10] и др. Обзор и систематизация итерационных
методов даны в книге Г. И. Марчука и В. И. Лебедева [17].

Большой круг исследований был выполнен по итерационным
методам решения линейных систем с особенными матрицами. Для

11.4]       ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ЛИНЕЙНОЙ АЛГЕБРЕ

567

случая совместных систем автором и Ю. А. Кузнецовым [8, 11]
был предложен общий подход к исследованию сходимости стацио-
нарных и нестационарных итерационных методов. Этот подход
позволил не только расширить область применимости известных
итерационных методов, но и дал возможность разработать новый
класс методов, получивших название матричных аналогов метода
фиктивных областей (см. Ю. А. Кузнецов, А. М. Мацокин [4]).
Итерационные методы решения несовместных систем были предло-
жены в работах Ю. А. Кузнецова [8] и др.

Остановимся на итерационных методах решения полной про-
блемы собственных значений для общих матриц. Рассмотрим толь-
ко степенные методы, поскольку именно здесь в последнее время
получены существенные результаты, чем мы обязаны исследова-
ниям Уилкинсона [8], Бауэра [8], Коллатца [З], В. В. Воеводина
I8], Френсиса [8], В. Н. Кублановской [8], Эберлейна [8] и мно-
гих других.

Степенные методы основаны на последовательном приведении
исходной матрицы с помощью унитарных преобразований подо-
бия (метод Якоби, (?7?-алгоритм) или преобразований подобия
с треугольными матрицами (L.fl-алгоритм) к матрице, собственные
значения которой легко вычисляются. Такими матрицами являют-
ся диагональная, треугольная или блочно-треугольная, порядки
диагональных блоков которой не выше двух.

До последнего времени существовали эффективные алгорит-
мы решения проблемы собственных значений лишь для симмет-
ричных матриц, такие как метод Якоби (Д. К. Фаддеев,
В. Н. Фаддеева [8], Рутисхаузер [8]). Разработка (?-й-алгоритма
(В. Н. Кублановская [8], Френсис [8], Уилкинсон [8]) и обобщен-
ного метода вращении (В. В. Воеводин [8]) позволяет говорить
о решении проблемы для произвольных матриц. Наиболее интен-
сивно в настоящее время разрабатываются различные модифика-
ции Д-алгоритма.

Прогресс в развитии проблемы собственных чисел имеется
также в связи с работами в области расчета ядерных реакторов,
стимулировавшими изучение итерационных методов решения част-
ной проблемы собственных чисел для неотрицательных матриц.
Основы теории заложены в трудах Перрона, Фробениуса и значи-
тельно развиты в исследованиях Варги [З], Трауба [8], Марека
[8] и др.

Анализ ошибок округления. Если до последнего времени вычис-
лительные методы сравнивались между собой по количеству ариф-
метических действий и объему памяти, которые требовались для
их реализации, то теперь к этим характеристикам добавилась точ-
ность. Это означает, что анализ ошибок округления при реали-
зации метода на ЭВМ стал одной из составных частей алгоритма.

Начало исследованиям в этой области положено работами
Неймана. Систематическое изучение ошибок впервые было прове-