Норри Д. - Введение в метод конечных элементов (1050664), страница 35
Текст из файла (страница 35)
Разбиение матрицы на части н сохранение только тех блоков, которые необходимы а текущий момент «ременн, снижают требоваяня к овератнвной памяти (и тем самым поаволяют решать задвчи большей размерностн), ио появляются дополнительные издержки за счет обмена межлу оперативной н внешней памятью, поскольку тре.
буютс» дополнительные обслуосивоющпл программы, для которых нужны память н время. Хотя блочная схема в принципе могла бы работать с меньшим объемом оперативной йамятн, чем описанный выше подход с треугольной активной областью, н, следовательно, допускает решение задач большей рлзмерноств, нз-вв дополнительного вычислительного вреэйрнн другие подходы оказываются предпочтительнее. Ею~и акт алая треугш ьна область не помегцвется целиком в оперативной памятв, то можно прибегать к процедурам, лля которых память требуется меньщвми порцнямн [!9). Испольюванне раэреженноств метр»им коэффициентов, обсуждаемое в .следующем разделе, может ) В слу в рллвювле оо нт вро ол мй ллрвк р Е лв р О ло«оюв л нарвав кр|поре», то рв В и ш ввш Вгю .
Н Геывв ' ой рулвироекк кожвг аи неоехолл о вереул р»л «ок о >Р вл вий. Гшеа !е расширить применимость прямых методов без обращении н блочным методамо безусловным разбиением. С другой стороны, для решения больших задач может прнменятьсн условное рзз. биение. Если зтн подкоды достигают пределов своей примени. мости (или даже раньше), то слелует использовать нтервцнон.
ные методы. юде. ОпеРАции с РАзрежеииыми.мАтрицАми Обычно снчметрнчная ленточная матрица хоэффнцвентов со. держит много нулей как ядоль краев ленты '), так н Внутри ее Редкость ненулевых членов в ленте может быть даже тайой, что число нулевык членов превышает чнсро ненулевых. В большинстве прнмых методов, в их простейшей форме, эсе элеыевты внутри ленты предполагаютсн ненулевыми; соответственно устав»вани»ются требоняння к памяти н объему вычислений. Однако программа может использовать некоторую проверку для предотвращения фактических нычнслений с нулямн.
Эффективность таких бесхитростных подходо» прнменнтелыга к некоторой конкретной задаче повышается, если раэреженаость уменьшить за счет.уыеньшеннв ширины ленты матрицы коэффнцие»- тов. Как отмечалось ранее, ширина ленты аавнсит от способа нумерации уздов. Нумерация, обеспечивающая минимум шн. ризы ленты, обычно очевидна только для простых задач.
В слу. ча»х больших задач лля уменьшения шнрнны ленты могут быть использованы подпрограммы автомятнчесюй перенумерации узлов (см. равд, 10.4.4]. В таких случаях становится все более важным использовать разреженную природу матриц для умень. щения требуемых памяти и вычислений. В математическом плане алгоритмы для рззреженаых матриц должны учитывать очень вам»у|а идею, состоящую в том, что граф матрицы является ключом к ее структуре [2[.
..К относительно простому твпу процедур для разреженных матрИц относятся профиль»аж методьг лсключе»яя, использующие детальную форму профиля ленты з). Каждой строке магри. цы коэффнцнен!Ов соотяетствуют маркеры, указмвающие номера крайнего левого н крайнего правого ненулевых эдемептов. Внутренние элементы рассмзтриваютс» как ненулевые более сложные процедуры исключают нз памяти нулевые элементы, поэтому нужно запоминать размещение всех ненулевьж коэффнцисятов. Методы, с помощью которык зто можно сделать, детально изложены в работях [20, 21[. В цевострочиом четоде «зждой строке матрицы н памяти соответствует строка ') д очна»»зтреаз с» змзшэмч Г ачьв яэ фз.мл ') Грези»и «зжд ю зз э .
т . »ю н теэ я лсмз нгл МЕ Едн Р МГЫМ УГЕВ Ее З Г Ша Мюззаяя»Раааа»а ЯЗЗ целых чисел, указывающая номера ненулевых элементов Другой подход использует для каждой строки матрицы булеву строку, иногда называемую б»нар»од маской. Бинарная маска предста»лист собой еоследоштельность двоичных чисел, соответствующих элементам строки мзтрнцы: ненулевые элементы в ней казываются.единицей, в нулевме обозначаются нулем. ри использовании методов для разреженных матриц появлиется трудность, состоящая в том, что некоторые элементы матрицы коэффициентов, первоначально считавшиеся нулямн, становятся ненулевым» в процессе вычислений. Это называется залоднением.
Желательно уменьшить его, насколько это воз. можно, так как каждый дополнительный ненулевой элемент вызывает впоследствии дополнительные вычисления. Одни нз алпзрнтмов, который во многих случаях значительно уменьшает заполнение, основан на автоматнчжкой перенумерацнн узлов. Другой подход состоит в том, что в методе исключения Гаусса [22! не сохраняются члены меньше заранее заданной величины. Опыт показывает, что требуетсп большая изобретательность для уменьшения объема памдти и вычислений за счет.нсполь. зевания нулей внутри ленты. Было предложено много разлнчнык схем, в тои числе фронтальный метод Айронса (см. равд.
10.2.4) н разложение Холесского для разреженных матриц в изложении Дженнингса н Теффа [23[. Другие процедуры н дополнительные подробностн о разреженных матрицах изложе ны в работах [24 — 32[. Хот» е алгоритмах для разреженных матриц обслуживающие программы сами могут требовать зяачнтельной оперативной намети н существенных чычнсленнй, нз публикаций следует, что обычно доетнгаетс» выигрыш в общей стоимости решения (по крайней мере для больших задач) по сраянению с эквивалентнымн алгорнтмпмн для неразреженных матриц.
Для дебольогнх систем уравнений такие алгоргпмы могут не давать существенного преимущества. Усложнение программы обычно ве дает нынгрыша для малых систем. Например, Бнркгоф и Фикс [2[ прн обсуждении схем исключения.для ленточных матрац отмечают, что выигрыш в эффективности, который может бьсть достигнут за счет нспользонаниа изощренных схем, рсякопначнтелен, если число нензпестных не превышает 2000» Чтобы обеспечить максимальную зффектнвность 'решения больших н сложных задач, нужно учитывать в стратегии программирования оборудование и операционную систему [33[. ге з т.
НтеРАционное уточнение Точность решения, полученного прямым методом, может быть Значительно улучшена сравнительно небольшнмн дополбитель. Г веге ными вычислениями') — посредством игерациоллого улушиенил, или угачлелма. Пусть Х вЂ” решение, полученное прямым методом. Используя арифметику с двойной точностью, вычисляют невяэку (10.21) В= — АХ После этого решают новое матричное уравнение АУ=В П0.22) для переменной У с использованием треугольных матриц разло. ження А в прямом методе.
Затем я качестэе улучшенного реше. пня принимают Х = Х + У. (10.23) Если Х и У вычислены точно, то Х будет тачно удовлетворять уравнению (10.1), так кзк нэ рапенсти (10.21) — (10.23) следует АХ=АХ-(-АУ= — В+В=В, (1024) Поскольку Х и У яычислены не абсолютно точно, Х оказы. веется приближенным, но более точным решением, чем Х. Этот процесс можно повторить для повышения точности решение Если элеыенты У мали по срйанеиню с соотэетстауюшими элементамн Х, то ма кио было бы ожндатц что система урзвпе. ннй (10.1] хорошо обусловлена и что Х вЂ” точное решение Это, однако, ле всегда гэк (34). Если У не мало, то это означает, что матрица А плохо обусловлена. Если число обусловленности матрицы А не очень велико, то прн последующих итерационных уточнениях Х обычно еще сходится к более точному значению. Дополнительную информацию об итерационных уточненняк можно найти в работе (34). гезк точность Прн «ыборе и применении метала решения системы линейных алгебраических уравнений важно учитывать требоэаннн к объему памяти') и времени нычнслений, но нельзя игнорировать точность.
Количество вычислительных операций метала влияет как на точность решения (посредстэом ошибок аппроксимации и округления), так и нв время и стоимость вычистений. Здесь уместно рассмотреть, каким образом возникают яы числительные ошибки. Обычно вычислительная машина пылал. ') тр йпэап к объему пвчйтп увггпчйвпюгсп, гпп пйп пгойхпзныа сахраппгь пггрппу А н гйэугппм пи атйпцы ее рззэаъеээя. ') Ойычпыч авхяпшэ огйаэпчпппе эп оппратппэую пзчэ и и ег пп. же а э ппч ва ып пй ч вэею ей, эйп псппиогпгшъпий пэютп ( зычно хн. споюй). Логпди й и уййг пй э и ггпй пнийпл пгогп и йэз наст арифметические операции, нспользу» заданную длину слова для каждого числа. Для объяснений примем десятичную запись чисел, хотя обычно числа хранятся не э десятичной форме, а, ивиример, а двоичной нлн «осьмеричнай.
Предположим, что длина слояа э вычислительной машине равна !О значащим цифрам и выполня~атся действия с числами 685378,9879 и 437896,4879. Простое сложение этих двух чисел дает 112327о,4758, на так как можно записать лишь 1О десятичнык цифр, то вычаслнтельная машина запишет в качестве сумин 1123275,475 или 1123275,476 и соответствии с используемым пра. нилом округления И э том, и а другом случаях произойдет по.
теря существенной информации, и аноснмые ошибки сложным образом будут увеличиваться е последующих вычислениях. Предположим, что к предыдущей сумме должно быть прибан. лена число 111111,1111. Прибавление 111111,)111 к 1123276,475 дает 1234386,586 как при усечении, так и при округлении. Аналогично, прибавление 11 Н 11,11)1 к 1123275 476 дает 1234386, 587 Чтобы получить точное значение суммы, нужно прибавить 111111, 111! к 11-значной форме предыдущей суммы, в результате чего получаетсн 1234386,5869. Необхалныо заметить, что округление дает приближенный резулшпт, более близкий к точному значению, чем усечение (при усеченин ошибке равна почти единице десятой значащей цифры), но оба резуль. тата содержат ошибку.
Последующие операции сложения, вычитания, умножения нлн деленна приводят в результате усече. ння иоследавательно к ошибкам и девятом знаке, восьмом н так далее. Прн округлении будет происходить точно такай же процесс, но с меньшей скоростью. Слелойательно, в любам случае численный результат э итоге бупет содержать ошибку, которая заяисит от длины слова н количества н типа иынолненных операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
