Главная » Просмотр файлов » Дж. Деммель - Вычислительная линейная алгебра

Дж. Деммель - Вычислительная линейная алгебра (1156793), страница 15

Файл №1156793 Дж. Деммель - Вычислительная линейная алгебра (Дж. Деммель - Вычислительная линейная алгебра) 15 страницаДж. Деммель - Вычислительная линейная алгебра (1156793) страница 152019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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 от точного значения, очень мала. Во-вторых, существует хотя и малая,но ненулевая вероятность того, что, вследствие округлений при вычислении невязки т = Ах — Ь, число ЦтЦ станет неправдоподобно малым, фактически, нулем; это сделает слишком малой вычисленную нами оценку ошибки. Чтобы предупредить такую возможность, можно добавить к ~т~ некоторую малую величину.

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

Тип файла
PDF-файл
Размер
40,83 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее