§ 3. Метод Ланцоша

1. Отыскание собственных значений.

Решение систем (25) или (42) предыдущего параграфа для определения коэффициентов характеристического или минимального многочлена можно осуществлять методами ортогонализации, изложенными в § 4 главы 6. Процесс ортогонализации целесообразно проводить после каждого умножения на матрицу А. В настоящем параграфе мы и рассмотрим возникающие при этом алгорифмы.

Выбираем произвольный начальный вектор и находим Подберем теперь коэффициент так, чтобы вектор

был ортогонален к вектору Это всегда возможно и условие ортогональности дает

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

был ортогонален к векторам Это также всегда возможно. При этом

Если окажется, что то

даст линейную зависимость между векторами а многочлен

будет делителем минимального многочлена матрицы А. Если же то продолжаем процесс ортогонализации.

Пусть нами уже найдены векторы удовлетворяющие условиям:

Тогда подбираем коэффициенты так, чтобы вектор

был ортогонален к каждому из векторов Это возможно. Коэффициенты должны быть определены по формулам

Параллельно с построением системы взаимно ортогональных векторов строим последовательность многочленов

Так как в нашем пространстве имеется не более взаимно ортогональных векторов, то на каком-то шаге будем иметь При этом

даст линейную зависимость векторов следовательно, многочлен

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

Для симметрической матрицы А равенства (7) упрощаются. Действительно, в этом случае

и если —1, то Таким образом, если матрица А симметрическая, то вместо (7) будем иметь:

Аналогичное упрощение можно получить и для несимметрической матрицы, заменив процесс ортогонализации процессом биортогонализации, подобно тому как это сделано в § 4 главы 6.

Будем исходить из двух начальных векторов Найдем по ним векторы и образуем линейные комбинации

Коэффициенты подберем так, чтобы оказалось Это возможно, если начальные векторы не были ортогональны, так как

В дальнейшем будем предполагать, что Тогда по найденным строим векторы и и образуем линейные комбинации

так, чтобы оказалось

При этом будем иметь:

и наше построение возможно, если Будем предполагать, что эти условия выполнены, и продолжим построение дальше. Пусть у нас уже построены векторы

причем эти две системы биортогональны, т. е.

Тогда строим векторы

так, чтобы

Условия (25) дают

Таким образом соотношения (24) примут вид

Наши построения будут возможны до тех пор, пока Это условие может нарушаться в следующих трех случаях:

Все эти три случая могут встречаться фактически. Продемонстрируем это на примере матрицы (44) § 2. а) Возьмем сначала

Тогда

(31)

и

Следовательно,

Далее,

Отсюда

и

Продолжая процесс, найдем:

б) Возьмем теперь

При

в) Наконец, если взять

то

и

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

Предполагая, что мы получили или последовательно находим минимальный многочлен А или его делитель по формулам:

В частности, в рассмотренных нами примерах будем иметь: в случае

в случае (38)

Такой способ получения минимального многочлена или его делителя будем называть методом Ланцоша.

Пусть процесс, осуществляемый по методу Ланцоша, продолжается до Рассмотрим матрицы

где — соответственно компоненты векторов . В силу биортогональности будем иметь:

где Следовательно, Далее, так как

то

Поэтому

Таким образом, в рассматриваемом случае наш процесс эквивалентен приведению матрицы А к тридиагональной форме. Если производить процесс Ланцоша без указанных упрощений, то он будет эквивалентен приведению матрицы А к верхней треугольной форме. В симметрическом случае всегда получим тридиагональную форму.

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

где клетки имеют вид, указанный выше.

Вернемся еще раз к вопросу о применении метода Ланцоша в случае симметрической матрицы А. Этот случай особенно выгоден для этого метода.

Прежде всего отметим, что для симметрической матрицы

причем знак равенства будет достигаться лишь при Далее, из условия

следует, что никакие два многочлена не могут обращаться в нуль при одном и том же значении Действительно, если бы то из (52) и (53) следовало бы Повторяя эти рассуждения для многочленов мы пришли бы к выводу, что Продолжая дальше, мы пришли бы в конце концов к заключению, что Но это невозможно, так как

Изучим теперь взаимное расположение корней Многочлен имеет единственный корень При этом Следовательно, квадратный многочлен положительный для достаточно больших по абсолютной величине значений X, будет обращаться в нуль в точках Для будем иметь: Так как отрицателен при достаточно больших по абсолютной величине, но отрицательных X и положителен при достаточно больших положительных X, то имеются три корня таких, что Теперь нетрудно по индукции показать, что корни многочленов действительны, различны и удовлетворяют условиям:

Пусть это выполнено для Тогда в силу (53)

и, следовательно, в силу (52)

По предположению индукции не имеет кратных корней, поэтому меняет знак при переходе от Следовательно, в силу (56) это верно и для Так как степени имеют одинаковую четность, то эти многочлены должны иметь одинаковые знаки левее и правее множества всех их действительных корней. лежит левее всех нулей а — правее всех нулей Поэтому должен обратиться в нуль левее и правее Так как он должен обратиться в нуль между каждыми двумя соседними то утверждение доказано.

Из доказанного следует, что совокупность многочленов образует систему Штурма (см. главу 7, § 1). Поэтому мы можем использовать ее для отделения корней многочлена как это указано в предыдущей главе.

Подсчитаем число операций умножения и деления, необходимых Для получения характеристического многочлена симметрической матрицы А порядка по способу Ланцоша. Пусть процесс, начинающийся с вектора может быть продолжен вплоть до Конечно. Вычисление потребует умножений. Получение потребует умножений и делений. Поэтому переход от потребует всего операций умножения и деления. На следующем шаге, при переходе от придется затратить операций умножения для получения операций умножения и деления для получения

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

операций умножения и деления. Нам еще придется подсчитать для чего нужно операций умножения и деления. Наконец, получение многочлена требует

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

операций умножения и деления.