Глава 6. Численные методы алгебры

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

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

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

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

Методы решения алгебраических задач разделяются на точные, итерационные и вероятностные. Классы задач, для решения которых обычно применяют методы этих групп, можно условно назвать соответственно классами задач с малым, средним и большим числом неизвестных. Изменение объема и структуры памяти ЭВМ, увеличение их быстродействия и развитие численных методов приводят к смещению границ применения методов в сторону систем более высоких порядков. В настоящее время точные методы обычно применяются для решения систем до порядка , итерационные — до порядка .

При изучении итерационных процессов нам понадобятся понятия норм вектора и матрицы. Напомним определения основных норм в пространствах векторов и матриц.

Если в пространстве векторов введена норма , то согласованной с ней нормой в пространстве матриц А называют норму

Наиболее употребительны в пространстве векторов следующие нормы:

а согласованными с ними нормами в пространстве матриц являются соответственно нормы

здесь и далее — собственные значения матрицы .

Приведем вывод этих соотношений для вещественного случая. Поскольку, согласно (2),

то

Пусть достигается при ; для вектора

имеем ,

Из этих соотношений следует (5).

Точно так же для нормы вектора, определяемой по формуле (3) имеем

Пусть достигается при . Для вектора , у которого

лишь одна компонента отлична от нуля, имеем

отсюда следует (6).

Согласно определению и (4), имеем

Матрица симметричная, поскольку .

Пусть матрица В симметричная, ортонормированная система ее собственных векторов, — соответствующие собственные значения. Представим произвольный вектор в виде . Имеем

поэтому

и

В то же время . Из этих соотношений следует, что

Поскольку , то все . Полагая в (10) , получаем

Из полученных соотношений следует (7).

Отметим важный частный случай.

Если А — симметричная матрица, то , поэтому для нее

Если , то . Следовательно, модуль любого собственного значения матрицы А не больше любой ее нормы.