Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 15
Текст из файла (страница 15)
В наихудшем случае вычисленное к составляло 0.44 от подлинного к. Алгоритм реализован ЬАРАСК- подпрограммой в1асоп. Внутри таких программ ЬАРАСК'а, как вйевнх, имеется обращение к в1асоп с получением оценки числа обусловленности. (В действительности, чтобы избежать переполнения в случае выронсценной матрицы, выдается число, обратное к оценке числа обусловленности.) Мас1аЬ содержит другой оценщик обусловленности тсопб. Ма11аЬ-программа сопд1 вычисляет точное число обусловленности (~А ' ~)г 11А)~г с помощью алгоритмов, обсуждаемых в разд. 5.4; она работает намного медленнее, чем тсопб. Оценивание относительного числа обусловленности Алгоритм из предыдущего раздела можно применить и к оцениванню относительного числа обусловленности кся(А = 11А д) 1А)(~ (см. (2.8)) или вычислению границы ))(А д) )г!)) (см. (2.9)).
Обе задачи можно свести к одной и той же, а именно оцениванию величины 111А д.д)), где д — вектор с неотрицательными компонентами. Чтобы пояснить это, введем вектор е, все компоненты которого равны единице. Из части 5 леммы 1.7 следует, что ~)Х11„= 11Хе(~ для матрицы Х с неотрицательными элементами. Поэтому 111А '! 1А)!) = ))(А '! )А1е11 =111А '! д)), где д = )А1е.
Глава 2. Решение линейных уравнений Мы собираемся оценить Ц(А '! дЦ следующим образом. Пусть С йай(ды..., д„), тогда д = Се. Отсюда Ц)А '!.дЦ = Ц)А ').СеЦ = Ц)А ') СЦ = Ц)А 'Сш = ЦА 'СЦ (2.12) Последнее равенство справедливо, так как Ц1'Ц = Ц!У/Ц для любой матрицы 1'. Таким образом, достаточно оценить шах-норму матрицы А 'С. Это можно сделать, применяя алгоритм Хэйджера (т.е.
алгоритм 2.5) к матрице (А 'С)г = СА т; в результате будет получена оценка числа Ц(А 'С)тЦ» —— ЦА 1СЦ, (см. часть 6 леммы 1.7). При этом нужны произведения матрицы СА т и транспонированной матрицы А»С с векторами. Умножение на диагональную матрицу С выполняется тривиально, а умножения на А» и А производятся, как и в предыдущем разделе, с использованием 1 П-разложения матрицы А. 2.4.4. Практичные оценки ошибки Приведем две практичные оценки ошибки в приближенном решении х системы Ах = Ь.
Используя неравенство (2.5), получаем первую оценку: Цх — хЦ, 1 ЦгЦ«е ошибка= ) ) < ЦА Ц (2.13) где г = Ах — Ь вЂ” невязка вектора х. Число ЦА»Ц оцениваем, применяя алгоритм 2,5 к матрице В = А ~; это дает оценку для ЦВЦ» = ЦА Ц~ = ЦА 'Ц, (см. части 5 и 6 леммы 1.7). Наша вторая оценка вытекает из более точного неравенства (2.9); — Ц~4 '~'~"ШЦхЦ ЦхЦ Величину Ц)А ') )г)Ц оцениваем с помощью алгоритма, основанного на равенствах (2.12). Оценка (2.14) (модифицированная, квк это описано ниже в разделе «Возможные неприятности») вычисляется такими БАРАСК- программами, как, например, вкевчх. Имя переменной, соответствующей в БАРАСК'е этой оценке, есть РЕвв (от Рог»еагб ЕВВог). Пример 2.4.
Используя тот же набор тестовых примеров, что и для рис. 2.1 и 2.2, мы вычисляли первую оценку ошибки (2.13) и подлинную ошибку. Результаты можно видеть на рис. 2.3. На плоскости переменных (подлинная ошибка, оценка ошибки) каждой системе Ах = Ь, решенной посредством метода СЕРР, соответствует символ е и каждой системе, решенной методом ОЕСР, соответствует символ +.
Если бы оценка совпадала с подлинной ошибкой, то символ е или + лежал бы на сплошной диагональной линии. Поскольку оценка всегда больше ошибки, то все символы находятся выше диагонали. Если отношение оценки к подлинной ошибке меньше 10, то символы попадают в полосу между сплошной диагональю и первой нцлдиагональной штрихованной линией. Если указанное отношение заключено между 10 и 100, то символы попадают в полосу между двумя первыми штрихованными наддиагоналями. Большинство оценок 2А. Анализ ошибок Пойлинная ошибка ло сравнению с оценкой ошибки, о=аЕРР, +=ОЕСР 10 1О 10-12 в о в н -1я Ф ю О 10 10 10 1в 10 10 1О 10 Подлинная ошибка Рис. 2.3. Оценка ошибки (2.13) по сравнению с подлинной ошибкой, о = СЕРР, + = СЕСР.
ошибки соответствует этой полосе и лишь несколько оценок в 1000 раз превосходят подлинную ошибку. Таким образом, вычисляемая нами оценка ошибки указывает число верных десятичных разрядов результата, на 1 — 2 или, в редких случаях, 3 разряда меньшее правильного числа. По поводу Маг)аЬ-программы, производящей этн графики, см., как и выше, НОМЕРАСЕ/Ма!!аЬ/р)гос.ш. О Пример 2.5. Приведем пример, иллюстрирующий различие между оценками ошибки (2.13) и (2.14). Этот пример покажет также, что метод СЕСР иногда может быть точнее метода СЕРР.
Был взят набор плохо масштабированных задач, построенных следующим образом. Размерности тестовых матриц меняются от 5 до 100 и каждая матрица имеет вид произведения А = РВ. Матрица В получается присоединением к единичной матрице очень малых (порядка 10 1) внедиагональных элементов, генерируемых случайным образом; таким образом, В обусловлена очень хорошо. Матрица Р— диагональная, причем ее диагональные элементы образуют геометрическую прогрессию, начинающуюся с 1 и кончающуюся числом 10'~. (Иными словами, отношение 4+1;1.1/4н не зависит от 1). Матрицы А имеют числа обусловленности к(А) = (!А 1)! ~)А~( почти равные 1014, т.е. очень плохо обусловлены; в то же время, их относительные числа обусловленности ксн(А) = !((А 1(.
)А!П = !ПВ 1( )В)(( почти равны 1. Как и выше, машинная точность е равна 2 вв 10 Глава 2. Решение линейных уравнений Подлинная ошибка по сравнению с оценкой ошибки (2.13), 0=6ЕРР, е=6ЕСР |о' к 1о Ю к ой юе к Ф пю" О 1о" 1о" 1о" 1о" ю ю Подлинная ошибка (а) Подлинная ошибка по сравнению с оценкой ошибки (2.14], 0=6ЕРР, +=6ЕСР 1а" 1о ю к ю к э ю о Ю к Е 1ОЯ О 1о" 1о" 1О" 1о н 1о 1о" Подлинная ошибка (Ь) Рис. 2.4.
(а) Оценка ошибки (2.13) по сравнению с подлинной ошибкой; (Ь) оценка ошибки (2.14) по сравнению с подлинной ошибкой. 67 2.4. Анализ ошибок Покои понентная относительная обратная ошибка, о = ОЕРР, + = ОЕСР 1О 1О 1О 10кн 1О '* 1Оки 10 1е 1О" О 1О Ю Ю Ю Ю Ю те Ю Ю тш Размерность матРицы (с) Рнс. 2.4. Продолжение. (с) Покомпонентная относительная обратная ошибка яз теоремы 2.3.
Примеры вычислялись посредством уже упоминавшейся Маь1аЬ-программы НОМЕРАСЕ/МаНаЬ/р1чо1.ш. Ни в каком нз примеров коэффициенты роста дрр и дср не были больше числа 1.33, а обратная ошибка, указываемая теоремой 2.2, ни разу не превзошла 10 ть. Оценщик Хэйджера был очень точен во всех случаях, давая оценку, совпадающую с подлинным числом обусловленности 10'4 во многих десятичных разрядах.
На рис. 2.4 изображены оценки (2.13) и (2.14) для этих примеров, а также покомпонентная относительная обратная ошибка, указываемая формулой из теоремы 2.3. Кластер из знаков + в верхнем левом углу рис. 2.4(а) показывает, что, хотя метод СЕСР вычисляет решение с очень малой погрешностью порядка 10 'з, оценка (2.13) обычно дает весьма пессимистическое значение, близкое к Рб з.
Так происходит потому, что число обусловленности равно 10'4 и оценка ошибки близка к 10 'е 1014 = 10 з, за исключением маловероятного случая, когда обратная ошибка много меньше числа с 10 'е. Кластер нз кругов вверху и посреди того же рисунка свидетельствует, что метод СЕРР имеет ббльшую погрешность (порядка 10 а); оценка же (2.13) по-прежнему обычно близка к 10 з. В противоположность этому, оценка (2.14) почти совершенно точна, что иллюстрируется плюсами н кругами на диагонали рис. 2.4(Ь). Этот рисунок снова показывает, что метод СЕСР имеет почти идеальную точность, тогда как метод СЕРР теряет почти половину верных разрядов.
Это различие в точности объясняется рисунком 2.4(с), показывающим покомпонентную относительную 68 Глава 2. Решение линейных уравнений обратную ошибку из теоремы 2.3 для методов СЕРР и СЕСР. Из рисунка видно, что второй метод имеет почти идеальную обратную ошибку в покомпонентном относительном смысле; поскольку соответствующее относительное число обусловленности равно 1, достигается очень высокая точность. Напротив, метод СЕРР не вполне устойчив в этом смысле, теряя от 5 до 10 верных десятичных разрядов. В разделе 2.5 будет показано, как итерационно улучшить приближенное решение х. Один шаг этого итерационного процесса повышает точность решения, вычисленного методом СЕРР, до уровня точности решения, найденного в методе СЕСР.
Поскольку последний требует значительно большей работы, он очень редко используется на практике. О Возможные неприятности К сожалению, как уже отмечалось в начале разд. 2.4, оценки (2.13) и (2.14), будучи реализованы на практике, не всегда дают правильные результаты. В данном разделе описаны (немногочисленные1) причины, почему это может происходить, и практические приемы, помогающие частично исправить положение. Во-первых, как указано в разд. 2.4.3, оценка для ЦА 'Ц, выдаваемая алгоритмом 2.5 (и другими подобными алгоритмами), является лишь нижней границей, хотя вероятность того, что эта граница составляет менее 1/10 от точного значения, очень мала. Во-вторых, существует хотя и малая,но ненулевая вероятность того, что, вследствие округлений при вычислении невязки т = Ах — Ь, число ЦтЦ станет неправдоподобно малым, фактически, нулем; это сделает слишком малой вычисленную нами оценку ошибки. Чтобы предупредить такую возможность, можно добавить к ~т~ некоторую малую величину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
