Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 11
Текст из файла (страница 11)
Наиболее употребительной векторной нормой является евклидова длина Однако использование этой нормы сделало бы слишком трудоемкимн некоторые из наших вычислений. Вместо нее мы определим в этой главе норму вектора из п компонент следующим образом: л 1х5= Х 1 г1. г-1 Эта норма обладает многими из аналитических свойств евклидо- вой длины, именно (~х,~~() О, если хФО, (~0~>=0, )~сх~)= — )с~-~„'х',! для всех скаляров с, ))х+у)~(.()х(~~-,'~у,"~. Некоторые из геометрических свойств евклидовой длины теряются, но они не слишком важны здесь.
Умножение вектора х на матрицу А приводит к новому вектору Ах, норма которого может очень отличаться от нормы вектора х. Это изменение нормы прямо связано с той чувствительностью, которую мы хотим измерять. Область возможных из- г) Это неверно и в отсутствие ошибок округления — Прим. нерее. 3. ЛИНЕЙНЫЕ СИСТЕМЫ УРАВНЕНИЙ менений может быть задана двумя числами (Ах~,' М = шах — ';;)-', т Ах) лт= ппп — ' ( ха) Максимум и минимум берутся по всем ненулевым векторам. Заметим, что если А вырождена, то т=О.
Отношение М/лт называется числом обусловхеныости матрицы А, щах— ~~.4х'( х ~~~4 сопп(А)= ) ~ ~~ * 3п ьт Рассмотрим систему уравнений Ах=ь и другую систему, полученную изменением правой части. А (х+Л )=Ь+ЛЬ. Будем считать ЛЬ ошибкой в Ь, а Лх — соответствующей ошибкой в х, хотя нам нет необходимости предполагать, что ошибки малы. Поскольку А (Лх) =ЛЬ, то определения Ч и т Немедленно ведут к неравенствам ЦЬЦ~МЦхЦ и цльц~ цл )ц Следовательно, при тпФΠ— сопд (А) — ' (ах( ~, 'ль( (ь( Величина ЦЛЩ)ЬЦ есть относительное изменение правой части, а величина ПЛЕЙ)хЦ вЂ” относительная ошибка, вызванная этим изменением. Использование относительных изменений и~реет то преимущество, что они безразиерньй т. е.
нечувствительны к общим масштабирующим множителям '). Полученное неравенство показывает, что число обусловленности выполняет роль множителя в увеличении относительной ошибки. Изменения правой части могут повлечь за собой изменения в решении, большие в сопд(А) раз. Оказывается, что то же самое справедливо в отношении изменений в коэффициентах матрицы. ') То есть не меняются при умножении вектора н его возмущения на одно н то же число.— Прим, иерее, зл.
оаксловленность мхтннцы Число обусловленности является также мерой близости к вырожденностн. Хотя мы не имеем еще математических средств, необходимых для точной формулировки этого утверждения, можно рассматривать число обусловленности как величину, обратную к относительному расстоянию от данной матрицы до множества вырожденных матриц. Некоторые нз основных свойств числа обусловленности вы- водятся просто. Ясно, что М)т и потому сопд(А))1.
Если Р— матрица перестановок, то компоненты вектора Рх лишь порядком отличаются от компонент вектора х. Отсюда следует, что ()Ркй=йхй для всех х и, значит, сопд (Р) =-1. В частности, сопб(1)=1. Если А умножается на скаляр с, то и М и и будут умножены на модуль этого скаляра, так что сопб (сА) =сеид (А).
Если Р— диагональная матрица, то сопд(Щ= ппп(ан( ' Последние два свойства в известкой мере объясняют, почему сопб(А) является лучшей мерой близости к вырождениости, чем определитель матрицы А. В качестве крайнего примера рассмотрим диагональную матрицу порядка 100 с числом 0.1 на главной диагонали, Тогда де1(А)= — 10-'", что обычно считается малым числом. Но сопд(А)=-1, и компоненты вектора Ах лишь множителем 0.1 отличаются от соответствующих компонент вектора х. Для линейных систем уравнений такая матрица А ведет себя скорее как единичная, а не как вырожденная матрица.
Следующий пример иллюстрирует понятие числа обусловленности: (9.7 6.6) ' '-( ) х-(0) Ясно, что Ах=Ь и йЬ!(=-13.8, )(хй=1. Если заменить правую часть на (9.70) ' а линейные системы уРАВнений 58 то решением будет вектор (0.34) Пусть ЛЬ=Ь вЂ” Ь' и Лх=х — х'. Тогда йЛЬ!~ — 0.01, йЛх~~ —.1.63.
Очень малое возмущение, внесенное нами в Ь, совершенно изменило х. Действительно, относительные изменения равны = 0.0007246, — ', = 1.63. ,'( х) Так как сонг((А) характеризует максимальное возможное увеличение, то сопп (А) ) о оооте — 2249.4. На самом деле выбранные Ь и ЛЬ как раз и дают максимум, так что для этого примера сопд (А) =2249.4. Важно понимать, что в данном примере речь шла о точных решениях двух слабо различающихся систем уравнений и что метод, которым были получены эти решения, здесь не важен. ,Пример конструировался с очень большим числом обусловленности так, чтобы эффект изменений в Ь был отчетливо выражен; однако, подобного же поведения можно ожидать в любой задаче с большим числом обусловленности.
Предположим, что мы хотим решить систему, в которой ам=-0.1, а все остальные элементы в А и Ь вЂ” целые числа, и сонпс((А)=!О'. Предположим, далее, что у нас двоичная машина с 27 битами для дробной части и что мы каким-то образом умеем вычислять точное решение для системы, уже записанной в память машины. Тогда единственная ошибка будет связана с двоичным представлением числа 0.1, и тем ие менее можно ожидать, что 101К 2-27 ~ 10 — 3 Ж Другими словами, простой акт записи матрицы коэффициентов в машине может вызвать изменения в третьей значащей цифре компонент правильного решения.
Число обусловленности также играет фундаментальную роль в анализе ошибок округлений, совершенных в процессе гауссова исключения. Предположим, что все элементы и А, и Ь точно представляются числами с плавающей точкой, и пусть х„— вектор, составленный из чисел с плавающей точкой, который ЭХ ОБУСЛОВЛЕННОСТЬ МЛТРИЦЫ получен на выходе подпрограммы решения линейных уравнений типа той, какую мы представим в следующем параграфе. Предположим также, что точная вырожденность матрицы, если она имеет место, не была обнаружена и что не было ни машинных нулей, ии переполнений.
Тогда можно установить следующие неравенства: ) ь — Ах„( ( р сонг) (А) () '. (х„) Здесь )т — основание системы для представления чисел с плавающей точкой, а ( — число разрядов дробной части, так что ~)-' имеет примерно величину машинного эпсилон, о котором было сказано в гл. 2. Величина р ниже определяется более точно, но обычно ее значение не превосходит р. Первое неравенство говорит, что, как правило, можно рассчитывать на то, что относительная невязка будет иметь величину, сравнимую с ошибкой округления, независимо от того, насколько плохо обусловлена матрица. Зто обстоятельство было проиллюстрировано примером в предыдущем параграфе. Второе неравен- стао требует, чтобы А была не вырождена; в него входит точное решение х. Это неравенство вытекает непосредственно из первого и определения сонг) (А); его смысл — относительная ошибка будет мала, если мало число сопс((А), но оиа может быть очень велика, если матрица почти вырождена.
В предельном случае, когда А вырождена, но это не было обнаружено в процессе вычислений, первое неравенство все же сохраняет силу, в то время как второе не имеет смысла. Чтобы точнее определить величину р, необходимо ввести понятие матричной нормы н установить некоторые вспомогательные неравенства. Читатели, которые ие интересуются такими деталями, могут опустить остальную часть этого параграфа.
Определенная ранее величина М называется нормой матрицы. Обозначение матричной нормы такое же, как и у векторной нормы ) А ~(= шах '~, )х) Вследствие нашего специального определения для йхй нетрудно показать, что ) А ) =- гпах,',,'а,,'~, ! где а; — столбцы матрицы А. Если бы мы выбрали евклидову длину вектора, то ||А~) вычислялась бы гораздо труднее. Зто обсуждается в гл.
9. з. линейные системы тяхвнвний Основной результат в исследовании ошибок округлений гауссовом исключении принадлежит Дж. Уилкинсону. Он д казал, что вычисленное решение х, точно удовлетворяет систе (А+Е)х,=Ь, где Š—, матрица, элементы которой имеют величину порядк ошибок округлений в элементах матрицы А. Встречаются редки ситуации, когда промежуточные матрицы, полученные в ходе гауссова исключения, имеют много большие элементы, чем А, и накопление ошибок округлений в этих больших матрицах оказывает определенное влияние на полученный результат; можно, однако, ожидать, что если величина р определена равен-! ством — !=Ф Пе!' !! А!! то р лищь в редких случаях будет больше, чем р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
