Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 14
Текст из файла (страница 14)
Метод последввательно44 сверхрелаксации (ВОР) является подобным ал~оритмом для процесса Гаусса — Зейделя. Он может ускорять сходимость в такой степени, что весьма широко используется прн решении конечно-разностных уравнений, моделирующих двумерные эллиптические краевые задачи. Опять-таки этого метода нет в библиотеках программ. Имеется еще семейство итерационных методов, называемых методами сааряженных градиентов нли сопряженных направлений. Хорошее изложение этих алгоритмов можно найти в книге Фаддеев, Фаддеева (!963). Методы этой группы по-видимому довольно успешны для симметричных положительно определенных матриц н не.содержат предположений относительно структуры матрицы Л. Есть ряд опубликованных алгоритмов метода сопряженных градиентов, 3, линейные системы уРАВнений УПРАЖНЕНИЯ 3.1.
Найдите решение следующей системы порядка 3 1. 00 О. 80 О. 84 х, ег! (О. 80) !.00 0.90 0.81 хз = ег!(0.90) Определение функции ег! см. в упр, !.1. Воспользуйтесь подпрограммами РЕСОМР и 80ЕНЕ. Выведите оценку обусловленности матрицы и решение хд, хэ, хз. Напечатайте также сумму х,+х,+хз и сравните ее со значением ег((!.00). Почему эти два числа так близки? Если вы не сумеете ответить на этот вопрос, загляните е 9 4.1. 3.2. Что будет получено на выходе следу!ощей программы: Р1 МЕНЯ!ОХ А(10,10),%ОКК(10),! РЧТ(!О) учР1М = 10 И=2 А(1,1) = 3.
А(1,2) = б. А(2,1) = 1. А(2,2) = 2. САУЛ. РЕСОМР(ЫР!М, Н, А, СОНР, 1РЧТ, %ОКК) %К(ТЕ(6,1) А(2,2) АЧК1ТЕ(6,1) СОКР 1 ЕОКМАТ(Е16,6) ВТОР ЕНР а) Объясните подробно, как связано значение заел!ента А (2,2) после обращения к РЕСОМР с машинным эпсилон вашей плавающей системы? Объясните в общих чертах, как связана с машинным эпсилон значение СОХР (Не нужно вспоминать все детали вычисления СОКР.) Если у вас есть доступ к арифметике другой разрядности, измените программу, внлючая и РЕСОМР, и снова ответьте на те же вопросы. б) Какой результат был бы получен, если бы эту программу пропустили на советской вычислительной машине Сетунь? (См.
таблицу в 9 2 !). 3.3. Эта задача заключается в проверке двух неравенств 1' Ь вЂ” Ах„) '„Л ",!,'х,!~ з, ' ' ~рсопб(Л) 8 !!х !~ где норма вектора х есть число ,'! х !) = ~~~, ! х! !. г=! а норма матрицы со столбцами ау равна (! А (! = шах !~ ау !!.
! УПРЛЖНЕНИЯ Вы должны экспериментально проверить наши утверждения о том, что в пер. вом иерааенстве р почти всегда меньше, чем р, и что величина СОН Р, вычисляемая подпрограммой РЕСОМР, является удовлетворительной оценкой для сопб(А) во втором неравенстве. Возьмите любую матрицу А, элементы которой точно представляются числами с плавающей точкой. Так как второе неравенство предполагает зна. ние точного решения, та либо возьмите Ь, для которого вы знаете точный нек.
тор х, либо возьмите х и вычислите Ь=Ах. Удостоаерьтесь, что в А, Ь и х нет ошибок округления, так что равенство Ах=Ь выполняется точно. С помощью РЕСОМР фактаризуйтс матрицу и вычислите СОКР. Для вычисления х, используйте ВОБЛ'Е. Вычислите ()Л)(, Щ), ))Ь вЂ” Ахч)( и ()х — хч(). Предусмотрите хранение копий А и Ь, поскольку они изменяются подпрограм. мами. Вычислите р так, чтобы первое неравенство было в действительности равенством. Если вы обнаружите, что р много больше, чем й, внимательно пронерьте свою программу. Болыпие значения р теоретачески возможны, однако онн случаются очень редко.
Они связаны с ростом величины элементов матрицы в процессе исключения. Относительно дальнейшей информации см. книгу Уилкннсон ((963). Используя ваше значение р, проверьте, будет.ти удовлетворяться второе неравенство, в котором сопб (А) заменено аа СО".4Р. Если это не так, то причина в том, что СОЫР значительно меньше подлинного числа обуслов.тенности. Опять-таки подобные примеры очень редки. Выполните это задание для нескольких различных матриц как с числами обусловленности, близкими к (, так и с очень большими числами обусловленности.
ЗА, Обратная к матрице А может быть определена как матрица Х, столбцы которой удовлетворяют условиям Ах =е, где е есть гий столбец единичной матрицы. Напишите подпрограмму с заголовком ВРВВО()т)НЕ )ЫУЕВТ (МР)М, Ы, Д, Х, СОМО, И УТ, (УОВК), входом которой яаляется матрица порядка Лl, а выходом — матрица Х, прнблизкающая обратную к А, а также оценка обусловленности и информация о ведущих элементах. Ваша подпрограмма должна обращаться к РЕСОМР только один раз, а к ВРЕМЕ всего л раз, по одному вызоау для каждого столбца матрицы Х Содержимое Х не определено, если РЕСОМР обнаруживает вырождснность.
Проверьте вашу подпрограмму на некоторых матрицах, элементы которых могут быть точно представлены чнслав1и с плавающей точкой и для которых вы знаете Л -И Имеется несколько способов оценки точности результатов: '„ЛХ вЂ” ) '„ (~ХА — ) ф )'Х вЂ” А Можно было бы также дважды использовать подпрограмму !МУЕКТ; первый раз для обращения А и второй раз для обращения Х. Результатом будет.матрица 7., которая совпала бы с А, не будь округлений. Таким образом, еще одной мерой точности является величина () 7 — Л ((.
Можете ли вы вывести неравенство, включающее р, сопб(А) и ))-г, которое оценивает, насколько велико может быть ((7.— А)(? э. линейные системы уплпн ений — 1 1 4 О 1 4 ! 1 4 1 О 1 4 1 1 — 1 Как меняется оценка обусловленности этой матрицы по мере роста ее порядка? Какие специальные свойства имеет факторнзованиый массив, получаемый на выходе ОЕСОМР? Как упростить алгоритм гауссова исключения для этого специального случая? Каь бы вы стали решать линеш:ую спето зу очень высокого порядка с такой матра«зе1«? О2 Да ® СЕ) 12 7 0 11 13 15 16 1 3 10 14 О О ! '! 10 ц1онн 10 нюни 15 панин 3.5. Напишите фортран. подпрограмму, которая вычисляет определитель квадратной матрицы А порядка о из разложения, аычисленного подпрограм мой ))ЕСОМР.
Используйте логарифмы, как предложено в й 3.3, или какой. нибудь другой прием, чтобы избежать переполнений и машинных нулей. 3.5. Пусть 0.1 0.2 0.3, О.! А=~ 0.4 0.5 0.6 ), Ь вЂ”..~ 0.3 ~. 'ч0.7 0.3 0.9, '0.5 7 а) Покажите, что система линейных урааиеаий Ах=-Ь имеет много решений. Опишите множество возможных решений. б) Предполо«ким, что система Ах=Ь решалась посредством ВЕСОМР и 5ОЕНЕ на гипотетической машине, которая точно эыголняет арифметику.
Поскольку решений много, нет оснований ожидать, что будет аычислено какосто одно, частное решение. Что произойдет? в) С помощ«по ))ЕСОМР и 50СЪ'Е аычислите решение иа машине, для которой )) есть степень двойки. Так как иа подобной машине некоторые элементы А не являются точными числами с планающей точкой, то матрица, задаваемая подпрограмме ВЕСОМР, не будет точна вырожденнои.
Какое решение получена? Почему? В каком смысле оно будет «хорошигм решением? В каном смысле оно будет «плохими решением? 3.7. При интерполировании данных ~ ) бическими гплайначи возникает, как мы увидим в следующей главе, такая трехдиагональная матрица: УПРАЖНЕНИЯ 77 3.8. Требуется рассчитать усилия в плоской ферме, состоябдей яз 17 стержней, которая изображена на диаграмме. Предполагается, что стержни фермы соединены в узлах шарнирами без трения.
Теорема из элементарной механики утверждает, что поскольку число узлов / и число стержней ш связаны соотношением 27 — 3= я, то ферма статически определима. Это значит, что усилия полностью определяются условиями статического равновесия в узлах. Пусть Гл обозначает горизонтальные, а г" — вертикальные компоненты сил.
Если ног ложитьа= ып 45'=-соз 45' и допустить лбалые перемешения, то условиями равновесия будут: цвел 10 т Напишите фортран-программу, которая использует подпрограммы ВЕСОМР и 30ь17Е для нахождения усилий из этой линейной системы урвана. ний. Хоро7йо ли обусловлена матрица линейной системы? узел 2 ( цвел 3 ( цзеп 4 ( цвел 5 ~ цвел б ( цвел 7 ( узел 8 ( цзвл 9 ~ 2, Г„= -сг,у, + 7; + аЛ = О, Лб Гг ~Л з 3 ГЗ/з О1 ;Р г„= -Л +Л = О, ~Г =7'з — 1О О; ;~- г„= -7б +7а = о, ХГг= ут =О1 2б Г» = Куб —,7е + Гдуб +,7!а = О> 2; Г„= аЛ + ут + куб — 15 = О; ~;Г, = — У, — аД, +Д, +ау„= О, ;РГ„= -аЛ -Л, — бааз О; Х Г. = -Л,а +7;б = О.
лаГ =Уы =01 Х Г, = -2, + аб,7„= О, ХГ,--Л -ббуш-О; Х Г. = -иуш -Л. +Л, = О, Хг, = аЛ +7' 2.Г. = -аЛ б -,Ггт = О. Предположим, что задано множество вещественных абсцисс х„..., х„и соответствующие ординаты уо..., д„. Здесь х,( <х,~...(х„а каждое р; — некоторое вещественное число, отвечающее хо определенное математически нлн являющееся результатом какого-либо наблюдения.
Задача одномерной интерполяции состоит в построении функции )', такой, что ~(х;)=у; для всех (, и прн этом ~(х) должна принимать «разумные> значения для х, лежащих между заданными точками. Критерий разумности меняется от задачи к задаче и ему, возможно, никогда не будет дано точного определения, Если ординаты (у«) происходят от гладкой математической функции н ошибки в них не превосходят уровня округлений, то можно рассчитывать, что задача имеет удовлетворительное р шение. Читатель, быть может, знаком, например, с линейной иь терполяцией в таблице логарифмов.
Если точки (хь у;) получены из очень точных экспериментальных наблюдений, то зачастую их можно считать лишенными ошибок, и тогда вполне разумно интерполировать их гладкой, функцией. Если, с другой стороны, эти точки проистекают из сравнительно грубых экспериментов, то неправомерно требовать от иитерполнрующей функции точно удовлетворять таким данным. Позволяя значениям )(х;) отличаться от у„можно очень хорошо отразить характер изменения данных и даже поправить некоторые из содер>кащихся в них ошибок. Приближение данных, не являющееся точной интерполяцией, обсуждается в гл. 9. Многие методы там совершенно иные. Цели интерполяции разнообразны, но почти всегда в ее основе — желание иметь быстрый алгоритм вычисления значений ~(х) для х, не содержащихся в таблице данных (хо рл).
Компактная таблица данных и небольшая подпрограмма интерполирования могут заменить очень длинную таблицу значений функции. Подчас нужно находить значения )' (х) или ) "(х) в промежуточных точках или вычислять интеграл от функции ) по произвольному подинтервалу (а, Ь) интервала (х„х„). вл, полнномилльнля интенполяция 79 Очень важно для задачи интерполирования определение того, как должна вести себя приемлемая функция между заданными точками.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
