§ 44. Метод бисекций

Пусть А — вещественная симметричная матрица. Предположим, что для невырожденной матрицы матрица

является диагональной. Тогда, в соответствии с законом инерции квадратичных форм [1], можно утверждать, что число нулевых, положительных и отрицательных диагональных элементов не зависит от способа приведения матрицы А из (44.1) к диагональному виду, т. е. не зависит от матрицы

Возьмем в качестве ортогональную матрицу собственных векторов из (43.1). В этом случае матрица в (44.1) будет матрицей собственных значений.

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

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

Согласно сказанному выше число положительных и отрицательных элементов равно соответственно числу положительных и отрицательных собственных значений матрицы А. Но элементы матрицы легко определить. Действительно, используя формулу Бине—Коши [1], находим, что для всех

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

Знаки главных миноров матрицы при любом вещественном X определяют число собственных значений матрицы А соответственно больших X и меньших Беря различные значения Я, можно найти число собственных значений, лежащих на произвольном отрезке вещественной оси и, следовательно, в нужной мере локализовать любое собственное значение матрицы А. На этой идее основан рассматриваемый ниже численный метод нахождения собственных значений симметричной матрицы, называемый методом бисекций.

Будем считать, что симметричная матрица А имеет трехдиагональную форму с ненулевыми внедиагональными

элементами. Такие матрицы называются матрицами Якоби и имеют вид

В рассмотрении матриц Якоби нет особого ограничения. В самом деле, мы показали в § 32, что симметричную матрицу можно привести к трехдиагональной форме с помощью ортогонального подобного преобразования. Если окажется, что некоторые из внедиагональных элементов равны нулю, то трехдиагональная матрица распадется в прямую сумму диагональных матриц и трехдиагональных матриц с ненулевыми внедиагональными элементами. Для диагональных матриц решение проблемы собственных значений очевидно, поэтому остается решить эту проблему для матриц вида (44.2).

Обозначим через главные миноры трехдиагональной матрицы А. Аналогично формуле (26.6) находим

Из этих соотношений и вида матрицы А вытекает ряд полезных следствий. Например,

никакие два соседних главных минора матрицы (44.2) не могут одновременно равняться нулю;

если минор равен нулю, то соседние миноры отличны от нуля и имеют противоположные знаки;

все собственные значения матрицы (44.2) простые.

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

Вычислим каким-либо способом главные миноры матрицы и рассмотрим чередование знаков в последовательности

Если ни один из членов последовательности не равен нулю, то по числу перемен знаков мы сразу определим число положительных и отрицательных собственных значений матрицы (44.2). Наличие нулевых членов в (44.4) не вносит никаких трудностей.

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

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

Формулы (44.3) в прямом виде нельзя использовать для вычислений на ЭВМ по многим причинам. Даже для самых простых матриц вычислительный процесс (44.3) может привести либо к переполнению, либо к неправильным выводам из-за появления машинных нулей. Рассмотрим, например, матрицу Якоби с элементами для всех Ее нечетные миноры равны нулю, а четные миноры порядка равны Поэтому при быстро наступает переполнение. Если же то, начиная с некоторого номера, все главные миноры будут восприниматься как нулевые. Это эквивалентно замене

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

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

Машинный нуль заставляет преодолевать гораздо больше трудностей при реализации формул (443), чем может показаться на первый взгляд. Связано Это прежде всего с тем, что мы должны гарантировать правильность знаков вычисляемых величин. Такая задача не проста, если сами величины близки к машинному

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

Будем считать, что матрица Якоби нормирована и ее коэффициенты для всех I удовлетворяют неравенствам

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

возмущение соответствующее выполненной замене, очень мало. Именно,

Обозначим через максимальное положительное число, представимое на ЭВМ. Обычно лишь незначительно меньше числа Выберем какое-либо число близкое к например,

Это число потребуется для дальнейших вычислений.

Рассмотрим теперь типичный шаг вычислительного процесса. Он заключается в нахождении величин

Здесь удовлетворяют условиям (44.5), числа не равны нулю одновременно, параметр у выбирается по ходу вычислений.

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

Если же то процесс вычислений будем осуществлять в такой последовательности:

Ни одна из величин слева не превосходит по модулю Чтобы на промежуточных этапах не возникало

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

Исследуем более детально возникающие ошибки. Заметим, что влияют незначительно лишь на выбор и не влияют на остальные вычисления в (44.7). Поэтому будем рассматривать ошибки только для 3.

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

Но (44.8) не имеет места, когда Если же то будут справедливы такие соотношения:

И снова (44.8) не имеет места. Следовательно,

Ошибки заведомо не равны — 1 в силу того, что Не равна — 1 и ошибка Действительно, если то при при . В обоих случаях независимо от величины Если же то и при любых

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

Однако подчеркнем, что могут оказаться равными — 1.

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

и дадим оценки для эквивалентных возмущений

Объединяя последовательно результаты вычислений в (44.7), мы получим независимо от величины ошибок следующие выражения для

Это означает, что

Так как

При оценке эквивалентных возмущений нам придется рассмотреть несколько случаев. Предположим сначала, что все ошибки 1. Тогда из (44.9), (44.10) вытекает, что

Если то при всех а ошибка Допустим, что т. е. выполняется асимптотическое неравенство

Представив в следующем виде:

и воспользовавшись неравенством (44.12), находим, что

Поэтому для эквивалентных возмущений получаем такие оценки:

Пусть . В этом случае Если ошибка то должно выполняться асимптотическое неравенство

откуда следует, что

Записав в виде

и приняв во внимание соотношение (44.13), заключаем, что теперь

Окончательное сравнение полученных результатов показывает, что для эквивалентных возмущений всегда гарантируется выполнение оценок (44.11).

Таким образом, вычисляя по описанному алгорифму знаки главных миноров якобиевой матрицы нормированной согласно (44.5), мы в действительности получим следующее. Реально вычисленная последовательность знаков будет точно совпадать с последовательностью знаков главных миноров некоторой возмущенной матрицы Если имеет вид (44.2), то возмущение будет симметричной трехдиагональной матрицей, имеющей аналогичный вид:

При этом элементы удовлетворяют неравенствам

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

вначений матрицы Собственные значения матрицы А асимптотически отличаются от собственных значений матрицы не более, чем на так как в соответствии с (44.5), (44.14) имеем

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

Как уже отмечалось, основной операцией метода является вычисление знаков главных миноров матриц для различных Но все собственные значения матрицы А с элементами (44.16) не превосходят по модулю 3/4. Поэтому достаточно брать X из сегмента . В этом случае коэффициенты матриц будут удовлетворять неравенствам (44.5).

Вычисляя знаки главных миноров матрицы мы в действительности правильно определим лишь знаки главных миноров некоторой матрицы Возмущение складывается из возмущений (44.6), (44.15) и возмущения возникающего при вычислении матрицы Очевидно, что матрица является диагональной, причем

Следовательно, для суммарного возмущения получаем оценку

для всех значений

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

Покажем, как определить по номеру собственное значение независимо от остальных.

Обозначим через число собственных значений матрицы строго больших, чем К. Если известны такие числа что

то заведомо принадлежит полуинтервалу Заметим, что в качестве можно взять любое число, меньшее — 3/4, в качестве любое число, большее Положим теперь

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

Это позволяет локализовать собственное значение с любой нужной точностью.

Сделанный вывод справедлив лишь в случае точных вычислений. Ошибки округления, конечно, вносят свои коррективы. Рассмотрим реально построенный полуинтервал Строго говоря, можно утверждать лишь то, что собственное значение некоторой матрицы больше собственное значение другой матрицы меньше или равно причем для возмущений выполняются неравенства (44.17). Но в соответствии с (44.17) заключаем, что

Следовательно, должны выполняться соотношения

Если в качестве приближения к всегда брать точку являющуюся серединой полуинтервала то из (44.18) вытекает, что

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

Нет никакого смысла в выполнении очень большого числа шагов деления полуинтервалов пополам. Обычно достаточно взять где означает целую часть числа. Принимая во внимание, что получаем такую оценку:

Рассмотренный метод определения собственных значений матрицы Якоби обладает исключительной универсальностью. Его можно использовать не только для нахождения заданного по номеру собственного значения, но и для вычисления всех или части собственных значений, принадлежащих любой заданной области, для исследования общего распределения собственных значений и т. п. На его реализацию не оказывает никакого влияния наличие близких и кратных собственных значений и даже очень большое их скопление. При этом достижимая точность (44.19) не зависит от размеров матрицы.

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)