1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 34

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

Текст из файла (страница 34)

Но практическая реализация этих теоретических рецептовнаталкивается на почти непреодолимые трудности.3.1. Задачи вычислительной линейной алгебры207К примеру, явная формула для определителя n × n-матрицы выражает его как сумму n! слагаемых, каждое из которых есть произведение n элементов из разных строк и столбцов матрицы. Раскрытиеопределителя по этой формуле требует n! (n − 1) умножений и (n! − 1)сложений, т. е.

всего примерно n! n арифметических операций, и потомуиз-за взрывного роста факториала2 решение СЛАУ по правилу Крамера при n ≈ 20–30 делается невозможным даже на самых современныхЭВМ.Производительность современных ЭВМ принято выражать в такназываемых флопах (сокращение от английской фразы floating pointoperation), и 1 флоп — это одна усреднённая арифметическая операция в арифметике с плавающей точкой в секунду (см. §1.2). Для наиболее мощных на сегодняшний день ЭВМ скорость работы измеряетсятак называемым петафлопами, 1015 операций с плавающей точкой всекунду.

Для круглого счёта можно даже взять производительностьнашего гипотетического компьютера равной 1 экзафлоп = 1018 операций с плавающей точкой в секунду. Решение на такой вычислительноймашине системы линейных алгебраических уравнений размера 30×30по правилу Крамера, с раскрытием определителей по явной комбинаторной формуле, потребует времени30 компонент решения ·30 · 30! операцийчассек· 24 сутки· 365 сутки1018 флоп · 3600 часгодлет, т. е. примерно 7.57 · 109 лет.

Для сравнения, возраст Земли в настоящее время оценивается в 4.5 · 109 лет.Обращаясь к задаче вычисления собственных значений матрицы,напомним известную из алгебры теорему Абеля-Руффини3 : для общихалгебраических уравнений степени выше четвёртой не существует конечной формулы, выражающей решения уравнения через коэффициенты с помощью арифметических операций и взятия корней произвольной степени. Таким образом, для матриц размера 5 × 5 и более мы понеобходимости должны развивать для нахождения собственных значений какие-то численные методы.

К этому добавляются трудности враскрытии определителя, который входит в характеристическое уравнение матрицы.2 Напомним в этой связи известную в математическом анализе асимптотическую√формулу Стирлинга — n! ≈ 2πn (n/e)n , где e = 2.7182818 . . .3 Иногда её называют просто «теоремой Абеля» (см., к примеру, [61]).2083. Численные методы линейной алгебрыПомимо неприемлемой трудоёмкости ещё одной причиной непригодности для реальных вычислений некоторых широко известных алгоритмов из «чистой математики» является сильное влияние на их результаты неизбежных погрешностей счёта и ввода данных. Например,очень неустойчиво к ошибкам решение СЛАУ по правилу Крамера.3.2Теоретическое введение3.2аОбзор основных понятийТермин «вектор» имеет несколько значений.

Прежде всего, это направленный отрезок на прямой, плоскости или в пространстве. Далее,термин «вектор» может обозначать упорядоченный кортеж из чиселлибо объектов какой-то другой природы, расположенный вертикально(вектор-столбец) или горизонтально (вектор-строка). Таким образом,если a1 , a2 , .

. . , an — некоторые числа, тоa1 a2  a =  .  — это вектор-столбец, .. (3.1)anаa = a1 , a2 , · · · , an — это вектор-строка.Этот смысл термина «вектор» широко используется в информатике ипрограммировании. Наконец, «вектор» можно понимать как элементабстрактного «векторного пространства», и в современной математикеогромное применение находят, к примеру, линейные векторные пространства, об элементах которых мы привычно говорим, как о некоторых «векторах».Все три перечисленных выше смысла тесно связаны между собой ивзаимно проникают друг в друга.

Мы в равной степени будем пользоваться всеми ими, предполагая, что контекст изложения не даст поводак недоразумениям. По умолчанию, если не оговорено противное, условимся считать, что «векторами» во втором смысле являются векторстолбцы, а сами числа a1 , a2 , . . . , an назовём «компонентами» вектораa. Множество векторов вида (3.1), компоненты которых принадлежат2093.2.

Теоретическое введениевещественной оси R или комплексной плоскости C, мы будем обозначать через Rn или Cn . При этом нулевые векторы, т. е. векторы, всекомпоненты которых суть нули, мы традиционно обозначаем через «0».Векторы можно складывать, вычитать, умножать на скаляр. Множество векторов с определёнными на нём операциями обычно рассматривают как специальную алгебраическую структуру — линейное векторное пространство.Ненулевые векторы a и b называются коллинеарными, если a = αbдля некоторого скаляра α. Иногда различают сонаправленные коллинеарные векторы, отвечающие случаю α > 0, и противоположно направленные, для которых α < 0.

Нулевой вектор по определению коллинеарен любому вектору.Вообще, в линейной алгебре, при работе с линейными векторнымипространствами, большую роль играют линейные выражения видаα1 v1 + α2 v2 + . . . + αr vr ,где α1 , α2 , . . . , αr — некоторые скаляры, а v1 , v2 , . . . , vr — векторыиз рассматриваемого пространства. Такие выражения называются линейными комбинациями векторов v1 , v2 , .

. . , vr . Говорят также, чтолинейная комбинация нетривиальная, если хотя бы один из коэффициентов α1 , α2 , . . . , αr не равен нулю.Векторы v1 , v2 , . . . , vr называются линейно зависимыми, если равнанулю некоторая их нетривиальная линейная комбинация. Иначе, еслилюбая нетривиальная линейная комбинация векторов не равна нулю,то эти векторы называются линейно независимыми.Линейной оболочкой векторов v1 , v2 , . . . , vr называют множествовсевозможных линейных комбинаций этих векторов, т.

е. наименьшеелинейное подпространство, содержащее эти векторы v1 , v2 , . . . , vr . Мыбудем обозначать линейную оболочку посредством lin {v1 , v2 , . . . , vr },так что( r)Xαi vi αi ∈ R или C .lin {v1 , v2 , . . . , vr } =i=1На линейных пространствах Rn и Cn можно задать скалярные произведения векторов, которые мы будем обозначать угловыми скобкамиh·, ·i. Напомним, что в вещественном случае это положительно определённая симметричная и билинейная форма, а в комплексном — положительно определённая эрмитова форма. Обычно они задаются в2103. Численные методы линейной алгебрыследующем стандартном видеha, bi =nXha, bi =nXилиai b i = a⊤ bдля a, b ∈ Rn(3.2)ai b i = a∗ bдля a, b ∈ Cn ,(3.3)i=1i=1где через bi обозначено комплексно-сопряжённое к bi число. Наличиескалярного произведения позволяет говорить о величине угла между векторами и ввести очень важное понятие ортогональности векторов.

По определению векторы a и b называются ортогональными,если ha, bi = 0. В целом введение скалярного произведение превращает пространство Rn в так называемое евклидово пространство, а Cn —в унитарное пространство. Для евклидовых и унитарных пространствсправедливы многие красивые и важные свойства, существенно упрощающие математические рассуждения.Матрицей в математике называют прямоугольную таблицу, составленную из чисел или каких-либо других объектов. Если она имеет mстрок и n столбцов, то обычно её записывают в видеa11 a12 . .

. a1n a21 a22 . . . a2n (3.4)A :=  ...  ,.... .... .am1 am2 . . . amnназывая aij элементами матрицы A = ( aij ). Двойной индекс означает номер строки и номер столбца, в которых располагается рассматриваемый элемент. При этом мы можем отождествлять n-векторы сматрицами размера n × 1 (вектор-столбцы) либо 1 × n (вектор-строки).Матрицы используются в современной математике для самых разнообразных целей. В частности, если дана система, составленная изконечного числа объектов (подсистем), то взаимодействие в ней i-гообъекта с j-ым можно описывать матрицей, элементы которой сутьaij .

В простейшем случае эти элементы принимают значения 1 или0, соответствующие ситуациям «связь есть» и «никак не связано». Длянашего курса особенно важны применения матриц, связанные с различными конструкциями линейной алгебры. Во-первых, матрица можетпредставлять какой-либо набор векторов арифметических пространств2113.2. Теоретическое введениеRn или Cn , когда упорядоченные кортежи чисел располагаются рядомдруг с другом, как единое целое. Во-вторых, с помощью матриц даётся удобное представление для линейных отображений конечномерныхлинейных векторных пространств. Кроме того, матрицы чрезвычайно полезны для компактной записи множества коэффициентов системлинейных алгебраический уравенний.Подматрицей матрицы A называют матрицу, образованную элементами, находящимися на пересечении фиксированного множествастрок и столбцов A с сохранением их исходного порядка.

Определитель квадратной подматрицы порядка k матрицы A носит названиеминора k-гo порядка матрицы A. Соответственно, ведущей подматрицей некоторой матрицы называется квадратная матрица, составленнаяиз строк и столбцов с первыми номерами. Ведущий минор матрицы —это определитель ведущей подматрицы.Транспонированной к m × n-матрице A = ( aij ) называется n × mматрица A⊤ , в которой ij-ым элементом является aji . Иными словами,если A задаётся в виде (3.4), тоa11 a21 . . .

an1 a12 a22 . . . an2 A⊤ :=  .....  ... ..... a1m a2m . . . anmЧисловые матрицы можно складывать, вычитать и умножать другна друга. Напомним, что сумма (разность) двух матриц одинаковогоразмера есть матрица того же размера, образованная поэлементнымисуммами (разностями) операндов. Если A = ( aij ) — m × l-матрица иB = ( bij ) — l × n-матрица, то произведение матриц A и B есть такаяm × n-матрица C = ( cij ), чтоcij :=lXaik bkj .k=1Квадратная диагональная матрица I вида1 1,...1002123.

Характеристики

Список файлов книги