Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 26
Текст из файла (страница 26)
Далее будем всюду считать, что в пространстве т-мерных векторов ка введена и фиксирована некоторая норма !!х!! (например, одна из норм !!х!!„, 1 ~ ~ р ~ м. В этом случае в качестве меры степени близости векторов х и х* естественно использовать величину !!х — х*!!, являющуюся аналогом расстояния между точками х и х*. Введем абсолютную и относительную погрешности вектора х' с помощью формул (5.8) Выбор той или иной конкретной нормы в практических задачах диктуется тем, какие требования предъявляются к точности решения.
Выбор нормы !!х!!1 фактически отвечает случаю, когда малой должна быть суммарная абсолютная ошибка в компонентах решения; выбор '1х!!г соответствует критерию малости среднеквадратичной ошибки, а принятие в качестве нормы !!х!! означает, что малой должна быть максимальная из абсолютных ошибок в компонентах решения. 4.
Сходимость по норме. Пусть 1х< "'1„=1 — последовательность ВЕКтОрОВ Х< "1 = (Х<1 "1, Х'"1, ..., Х< "1)т. ГОВОрят, ЧтО ПОСЛЕдОВатЕЛЬ- ность векторов х«<> сходится х векпгору х при и -~ м (х'"' ~ х при а - оо), если ь(х< "1) = !!х'"' — х!! - 0 при а - х. 3 а м е ч а н и е. Сам факт наличия или отсутствия сходимости х<"' к х при и ~ м в конечномерных пространствах не зависит от выбора нормы. Известно, что из сходимости последовательности по 125 одной из норм следует сходимость этой последовательности в Я~ по любой другой норме.
Например, для норм ЦхЦп ЦЦд ЦюЦ„это выте- кает из неравенств (5.6). Более того, х' "> ~ х при и ~ ~ тогда и только тогда, когда для всех 1 = 1, 2, ..., т имеем х',."~ - х; при и ~ ю, т. е. сходимость по норме в В~ эквивалентна покомпонентной (покоординатной) сходимости. 5. Норма матрицы Величина ЦАЦ = тпах Ц -Ц хФО (5.9) 1с) ЦАЦ э О, причем ЦАЦ = 0 тогда и только тогда, когда А = О, 2э) Ц аАЦ = ! а~ ° ЦАЦ для любой матрицы А и любого числа а. Зс) ЦА + ВЦ ~ ЦАЦ + ЦВЦ для любых матриц А и В.
Дополнительно к этому верны следующие свойства: 4") ЦА. ВЦ ~( ЦАЦ ° Ц ВЦ для любых матриц А и В; 5с) для любой матрицы А и любого вектора х справедливо неравен- ство ЦАхЦ < ЦАЦ ЦхЦ. (5.10) Докажем, например, свойство 5с. Если ЦхЦ Ф О, то неравенство (5.10) эквивалентно неравенству ЦАРИЦ/ЦхЦ ~ ЦАЦ, справедливость которого следует из определения (5.9). Если же ЦхЦ = О, то неравенство (5.10) превращается в верное числовое неравенство 0 ( О. Как следует из определения (5.9), каждой из векторных норм ЦхЦ соответствует своя подчиненная норма матрицы А. Известно, в частности, что нормам ЦЩ, ЦхЦ~ и ЦхЦ„подчинены нормы ЦАЦи ЦАЦ~ и ЦАЦ„, вычисляемые по формулам ЦАЦ~ — — тах Е ( а~~, 1~( ~'~т ' (5.11) 126 называется норлой матрицы А, подчиненной норме векторов, введенной в Ю".
Заметим, что множество всех квадратных матриц размера т х т является векторным пространством. Можно показать, что введенная в этом пространстве формулой (5.9) норма обладает следующими свойствами, аналогичными свойствам нормы вектора: ))А))г = гггж г)тггА А) 1«7«т (5.12) где Л (АтА) — собственные числа1 матрицы АтА; ~А~ = тпах Е ~а, ~.
1«« (5.13) Нормы ~А~) и ~А~„вычисляются просто (см. ниже пример 5.2). Для получения значения первой из них нужно найти сумму модулей элементов каждого из столбцов матрицы А, а затем выбрать максимальную из этих сумм. Для получения значения ~А~„нужно анало- гичным образом поступить со строками матрицы А. Как правило, вычислить значение нормы ~А~т бывает трудно, так как для этого следует искать собственные числа Л7.
Для оценки величины ~~ А ~~ г можно, например, использовать неравенство (5.14) ))А12 4 1)А)1Е. )А Здесь ~А11б = Х ~ а, 12 — величина, называемая евклидовой норАиой 1,7=1 .иатрицы А. Норма (5.9) имеет простую геометрическую интерпретацию. Для того чтобы ее привести, заметим, что операцию умножения матрицы А на вектор х можно рассматривать как преобразование, которое переводит вектор х в новый вектор у = Ах. Если значение ~~х~ интерпретируется как длина вектора х, то величина )1Ах~/~~х~~ есть коэффициент растяжения вектора х под действием матрицы А. Таким образом, величина ~)))з;(: ~) А )) — тпах )! Ах11 (5.15) ХА=О представляет собой максимальный коэффициенТ растяжения векторов под действием матрицы А.
Полезно отметить, что для невырожденной матрицы А минимальный коэффициент растяжения 1св;„отвечает норме обратной матрицы и вычисляется по формуле ]с 1„— — (~А 1~ ' = п11п ~)Ах)~ (5.16) хФО 1 7.7 1 Напомним, что число Л называется собственным числом матрицы А, если <МеС (А — Лс) = О. Каждая матрица порядка т имеет ровно т собственных чисел (вообще говоря, комплексных) с учетом их кратности. Заметим, что в случае !!А!! < 1 происходит сжатие векторов под действием матрицы А. Пример 5.2.
Для матрицы 0.1 -0.4 0 0.2 0 -0.3 0 0.1 0.3 найдем !!А/!т, !!А/! и оценим !!А$з. В соответствии с формулами 15.11), 15.13) и неравенством 15.14) имеем !!А!!т = тпах (0.1 + 0.2 + О, 0.4 + 0 + 0.1, 0 + 0.3 + 0.3) = 0.6, !!А!! = твах (0.1 + 0.4 + О, 0.2 + 0 + 0.3, О + 0.1 + 0.3) = 0.5, з !/А!!з ( l!А!!е = ! Е аз1 ~ = г/04 н 0.63. 1г,,т=т 'т1 3 5.3. Типы используемых матриц Эффективность вычислений в линейной алгебре существенно зависит от умения использовать специальную структуру и свойства используемых в расчетах матриц.
Напомним некоторые важные типы матриц. Квадратная матрица А называется диагональной, если ее элементы удовлетворяют условию аΠ— — 0 для г' ~ т' (все отличные от нуля элементы расположены на главной диагонали): ап 0 0 ... 0 о о ... о О 0 азз ". 0 0 0 0 ... агзтз Диагональную матрицу, у которой все элемвнты аи главной диагонали равны единице, называют единичной и обозначают буквой Е: 1 0 0 ...
0 0 1 0 ... 0 0 0 1 ... 0 0 0 0 ... 1 Пример 5 3 Вычислим норму единичной матрицы Ю. По определению, !!Х!! = тпах = тттах — =1. Следовательно, !!К!! =1. !!М !! !! .~0!!, О!! !! 128 Важную роль в численном анализе играют треугольные иатрицъс Квадратная матрица А называется нижней треугольной, если все ее элементы, расположенные выше главной диагонали, равны нулю (а; — О для ~ < Я. Если же равны нулю все элементы матрицы, расположенные ниже главной диагонали (а," = О для ~ > Я, то она называется верхней тиреуьольной. Нижняя и верхняя треугольная матрицы имеют соответственно следующий вид: а~~ О О ...
О аы агг О ... О аз~ азг азз " О ап а~г алз ... а1а О агг агз "- аг и О О азз .. азт О О О ... а,„~ а н айаг абаз " а Треугольные матрицы обладают рядом замечательных свойств. Например, для таких матриц определитель легко вычисляется по формуле (5.17) с1е1 А = ап агг азз .. ает. Квадратная матрица А называется сил.иетринной, если она совпадает со своей транспонированной матрицей Ат(или, что то же, а, = а; для всех ~, Я. Будем называть симметричную матрицу А положительно определенной и писать А > О, если для всех векторов ю Ф О квадратичная форма (Аз ю) = Е айх,х ~,~=1 принимает положительные значения.
Обозначим через Л;„ и Л „ минимальное и максимальное собственные значения матрицы А. Известно, что для симметричной матрицы Лщ1с ~ й!/ ( (А~с з) ( Лбах $ й$ 5-28 и матрица А положительно определена тогда и только тогда, когда все ее собственные значения положительны. Одна из трудностей практического решения систем большой размерности связана с ограниченностью оперативной памяти ЭВМ, Хотя объем оперативной памяти вновь создаваемых вычислительных машин растет очень быстро, тем не менее еще быстрее возрастают потребности практики в решении задач все большей размерности (напомним, что 129 для хранения в оперативной памяти ЭВМ матрицы порядка т требуется т~ машинных слов). В значительной степени ограничения на размерность решаемых систем можно снять, если использовать для хранения матрицы внешние запоминающие устройства. Однако в этом случае многократно возрастают как затраты машинного времени, так и сложность соответствующих алгоритмов. Поэтому при создании вычислительных алгоритмов линейной алгебры большое внимание уделяют способам компактного размещения элементов матриц в памяти ЭВМ.
Заметим, что для хранения диагональной матрицы достаточно отвести массив длины т и расположить в нем элементы ап, а~2, ..., а „. Для хранения треугольной матрицы достаточно тл (т + 1)/2 ячеек памяти, что примерно вдвое меньше места, отводимого для хранения матрицы общего вида. Столько же ячеек используется для хранения симметричной матрицы, поскольку такая матрица полностью определяется, например, заданием своей ' нижней треугольной части. К счастью, приложения очень часто приводят к матрицам, в которых число ненулевых элементов много меньше общего числа элементов матрицы.
Такие матрицы принято называть разрежениыли. Напротив, матрицы общего вида называют плотнели (или заполненными). Разреженность матрицы является очень ценным свойством, поскольку объем информации, который следует обрабатывать и хранить в памяти ЭВМ, для таких матриц даже очень большого размера может оказаться не слишком большим. Для хранения всех ненулевых элементов и информации об их расположении оказывается достаточным использовать только оперативную память ЭВМ. Иногда элементы матрицы известны либо вычисляются по простым формулам и необходимость в их хранении отпадает. Одним из основных источников разреженных матриц являются математические модели технических устройств, состоящих из большого числа элементов, связи между которыми локальны.
Простейшие примеры таких устройств — сложные строительные конструкции и большие электрические цепи. Другой важный источник разреженности — метод конечных разностей и метод конечных элементов, используемые для решения уравнений математической физики. Известны примеры решенных в последние годы задач, где число неизвестных достигало сотен тысяч. Естественно, это было бы невозможно, если бы соответствующие матрицы не являлись разреженными (число элементов матрицы при т = 10' равно ти х т = 10'о).
Простой пример разреженной матрицы дает трехдиа~ональиая .иат- рииа 130 а1 а О О ...О о аз1 абаз абаз 0 - О о 0 азз азз аз~ ... О О 0 О 0 0 " аул-|,щ-з ащ-1,ш-1 ащ-1,и 0 0 0 0 ... О ап,и-1 анп все ненулевые элементы которой расположены на главной и двух соседних с ней диагоналях. Число этих элементов равно Зт — 2, что при большом тп много меньше общего числа шз эле- ментов матрицы. Многие приложения приводят к системам уравнений с так называемыми ленточными матрицами. Матрица А называется ленточной с полушириной ленты, равной 1, если а,~ — — 0 для ~1 — Я > 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
