Ефимов А.В., Золотарев Ю.Г. - Математический анализ (специальные разделы) (1081344), страница 46
Текст из файла (страница 46)
При применении итерационных методов существеннь1м является быстрота сходимости построенных приближений. Заметим, что при решении систем уравнений иа ЭВМ, даже точными методами, решение может определяться с некоторой ~погрешностью. Это объясняется как погрешностью при вводе коэффициентов системы (1) в ЭВМ, так и необходи.
мастью проведения округлений в процессе решения .системы уравнений на ЭВМ. Если порядок рассматриваемой системы линейных уравнений (1) невелик (не превосходит нескольких десятков), то обычно для решения такой системы можно пользоваться стандартными программами решения линейных систем уравнений, которыми снабжена используемая 2бе Х. Численные методы ретненнл елсебр. и дифференч. урелнеиия ЭВМ. Поэтому в этой главе основное внимание будет уделено тем методам, которые наиболее часто применяются при решении больших систем линейных уравнений. Теоретически решение системы (1) дается формулой х=А — 'Ь, где А ' — матрица, обратная к А. Матрица А ' называется усгпойчивой, если малым изменениям элементов матрицы А соответствуют малые изменения в элементах матрицы А ', и неустойчивой — в противном случае.
Из выражения (2) видно, что если матрица А ' устойчива, то малые погрешности свободных членов и коэффициентов системы (1) вызывают малые изменения в решении х этой системы. Если же матрица А ' неустойчива, то малые погрешности правых частей и коэффициентов системы (1) могут существенно исказить ее решение, Матрица А называется плохо обусловленной, если соответствующая ей обратная матрица А ' будет неустойчивой.
Прн решении систем уравнений с плохо обусловленными матрицами нужно быть предельна осторожным, так как погрешность решения может оказываться недопустимо большой. Заметим, что хотя и существуют опенки обусловленности матрицы (чнсла обусловленнгсти), их определение требует значительно большего объема вычислений, чем решение системы (1). Чтобы одновременно с определением решения системы (1) приблизительно оценить гюгрешность этого решения, поступают следующим образом. Выбирается некоторый вектор у(л>, напримерунн = (1, ..., 1)г, и вычисляется вектор Ь<л~ = Ау<с>. Затем одновременно одним и тем же методом решаются системы уравнений Ах = Ь и Ау = Ь'"~.
Объем вычислений при этом возрастает незначительно. Если окажется, что отношение (!у — у<с> )11 (1 у )! достаточно мало, то считают, что и при решении системы (1) не возникло сильного возрастания погрешности. Конечно, подобные рассуждения не являются строгими, но достоверность нх выводов достаточно велика. 2.
Метод Гаусса. Наиболее простым и распространенным методом решения системы (1) является м е т о д Г а у с с а последовательното исключения неизвестных. Метод имеет много различных вычислительных схем. Рассмотрим схему единственного деления. Допустим, что система (1) такова, что атт ~ О. Разделив все коэффициенты и свободный член первого уравнения системы (1) на ац, получим уравнение (3) лн Затем из каждого нз остальных уравнений системы (1) вычтем уравнение (3), умноженное на соответствующий коэффициент ац. В резуль.
тате получим систему Ж а)!~ =-а,т — а)!1ат,, 1=-2,:5, ..., и. 5 <. Системы линейным алгебраичасним уравнений 261 Предполагая, что а~вв< ~ О, проделаем аналогичную операцию. Про должая далее, получим систему уравнений треугольного вида х, + а«<в< х, + ... + а«<>„< х, < + а< << х„= а««„+ „ хв+ ... +а<в>„< хл < + а',а' х„=а<аз>„+ „ х„< +а<"-,'<„хл = а<"-,« <л< х„=а„„+„ решение которой является решением системы (1). Подставляя х„, определенное последним уравнением системы (5), в предпоследнее уран.
пение этой же системы, определим х„,; зная х„и х„„из следующего уравнения найдем х„,. Этот процесс повторяется, пока не будут найдены все компоненты решения системы (5). Итак, для решения системы (2) по схеме единственного деления сначала строится вспомогательная треугольная система(прямой ход), а затем она решается (обратный код), Отметим также, что попутно можно найти дегА=а а<и...а<'-«.
— и вд °- Реализация метода Гаусса требует выполнения Чв (аа + За' — и) опе аций умножения и деления. аметим, что если на Й-м шаге вычислительного процесса элемент а~ма ", на который мы должны делить все коэффициенты первого урав пения оставшейся системы, равен нулю или очень мал, то этим уравнением нельзя пользоваться для исключения хв из других уравнений системы из-за резкого возрастания вычислительной погрешности (или астапова при переполнении). Поэтому приходится либо менять местами уравнения системы (1), либо изменять номера у искомых иеизвестнык. Приведем <рОРТРАН-программу схемы единственного деления Гаусса: 01МЕХ81ОХ А(Х, Х+1) Х (Х) 1 РОКМАТ (8Р7.
4(8 Р7. 4/8Р7.4) КЕАО (1,1) А 1)О 2 1=1, Х вЂ” 1 С=А(1,1) 1)О 2 ) =2, Х+1 1Р(3 — 1) 2,2, 3 3 А (1, Л) *=А(1,3)/А(1,1) 00 2 К=2,Х 262 Х, Численные методы раотения алгабр. и дифферанц. уравнений 1Р (К вЂ” !) 2,2,4 А (К, 1) =А(К,Я) — А(1, ))тА(К,!) СО5)Т15!иЕ Х(5!) =А(5), Х+ 1)/А(1Ч, Х) 00 51=1, И вЂ” 1 С=О. !)О 6,) =1, 5! — 1 !Р (1 — Я) 6,7,7 С = С+ А (М вЂ” 1, 5! + 1 — Я) вХ (Я + 1 — )) СОИТ1)т!БЕ Х (5! — 1) = А(И вЂ” 1, (т)-1-1) — С РОКМАТ (15Х, 'Х=',Р 12.5) ЮЙ!ТЕ (3,8) Х Е5!П ЗТОР 4 2 7 6 5 8 3.
Ленточные матрицы, Метод прогонки. Если матрица А такова, что ее элементы ам удовлетворяют условию аы О при ~! — !'!)т, тп(п, (6) (7) а п„тх, я+а„к ~х. ~+а, клх„= дн а„„,х„, +а„„х„=т(„. то матрица А называется ленточной матриней. Ленточные матрицы часто встречаются при решении прикладных задач. К решению системы (1), когда матрица А удовлетворяет условию (6), приходят, например, при определении кубического сплайна (см. 2 1 гл. !Х) н при решении краевых задач для обыкновенных днф. ференциальных уравнений в частных производных. Для всех подобных задач характерно, что число уравнений в системе (1) велико, но число пт намного меньше и.
Это значительно уменьшает общее число арифметических и логических операций, необходимых для решения системы (1). Особенно удобно решать системы линейных уравнений вида (1) с ленточными матрицами при небольших значениях тп. Рассмотрим случай т = 1. Тогда система уравнений (1) может быть представлена в виде а„х,+а,ах, амх, + авв ха+а„хв а„х, + а„х, + ам х, 5 1. Системы линейнеа алгебраических уравнений 263 Применим для решения атой системы ехему единственного деления Гаусса. Разделив первое уравнение на р, = ам, приведем его к виду Х,— т)1ХЕ=и„ГДЕ т)тнн — —, и,= — ' л„ рт Рт Умножая зто уравнение на ам и вычитая получившееся соотношение из второго уравнения системы (7), получаем уравнение Р, х, + аел хл = т(т, где Р, = аее + ает т)„4 1 = т(а — а„и, — (11 1 того же вида, что и первое уравнение системы (7). Итак, в результате первого шага метода Гаусса мы приходим к системе того же вида, что и система (7), но содержащей а — 1 уравнений.
В результате выполнения (й — 1)-го шага метода Гаусса придем к системе рл хе+а„с+1 ха+1 ~ Дф ° ае»-1, лхл+ат» 1, е» тхе+1+ат+1, а+а =с(е+1, (8) а„,, 1 х„т+ а, „х„ 1(н Разделив первое уравнение системы (8) на рл, получим уравнение ам Ф+1 4''1 х„— г)л хе+1 *= и„де = — ', ид =— Рл .,) Умножив его на ах+1 е и вычитая из второго уравнения системы (8), получим, аналогично предыдущему, ре+1 хе+1+ ал+1, а+ з хе+, —— Щ1, где рл+т -ал+кд+з+ а,+, „г)л, с(а+1 - т(д+, — а„+,е ид. Таким (т) образом, каждый шаг исключения неизвестных переводит систему (8) в систему того же вида. В применении к системе (7) схема единственного деления Гаусса может быть реализована следующим образом: атт г1, Рт =ам т)т Рт Рт (9) Рл = ае.
» 1 ат 1 + алм г7, = — — '- —, Рл Ф фт = г(» — ак е 1 ил 1, и„= —, lг = 2, 3, ..., и, ре (10) х„= д„хе+1+ ид, й = 1..., и — 1, ил что позволяет последовательно определять х„„..., х,. 264 Х. Численные методы ресненнл елгебр. н дифференц. уреенений Полученный таким образом метод решения системы (7) называется методом прогонки. Вычисление величин 4е н ил по схеме (9) называется прямой прогонкой, а решение системы (10) — обратной прогонкой. Метод прогонки для решения системы (7) и-го порядка требует выполнения 9п арифметических операций. Приведем ФОРТРАН-программу решения системы (7) методом прогонки, вводя дополнительно величины а,е а„„+, — — О н массивы: А (А!) = (а„, ам, ..., а„, ~), В (А!) = (ац, ..., а„„), С(А!) (анн асс, ...,а, ь,а„,„«.~), Р(А!) (й, ...,й„), Х (М) = (х,, ..., х„), сг (Ж) = (ды ..., 4„), У (7у) (и„, ..., и„).
Программа запишется в таком виде: 01МЕЫБ10г) А(Ы), В(51), С(Щ, 0(Ы), Х(5)), Я(Х), У(Х) 1 РОВМАТ (5 Р 5.2) КЕАО (1,1) А, В, С, Р Я (1) = — С (1) 1В (1) (.)(1) = )г (1)!В (1) 1гО 2 К=-2, Н Р = А (К) еЯ (К вЂ” 1) + В (К) Я (К) = — С (К) 1Р 2 () (К) = (Р (К) — А (К)е() (К 1))!Р Х (1ч) = 1) (о1) РО 3!=2,Н 3 Х(И+1 — 1)=Я(Я+1 — 1)еХ(5)+2 1)+11(ь( 1 1 1) 4 РО)(МАТ (15Х, 'Х=',Р 12.5') Жй!ТЕ (3,4) Х ВТОР Е510 4, Итерационные методы. Наиболее употребительным итерационным методом решения систем линейных уравнений является метод простой итерации.
Пусть система уравнений (1) имеет единственное рещение. Как показано в п. 2б $ 4 гл. П1, решение ме системы (1) является неподвижной точкой оператора се! Ух= (! — 0А) х+17Ь=См+Ье, С=(С~у), (11) где 1 — единичная матрица, а !) — некоторая неособая матрнпа, т. е. хе= Уме= Схе+Ь'. (12) й 1. Системы лииеяиыл елгебреииесиил урлеиеииа зев нлн, Итерацнонный процесо л/л+О =Сх(л1+Ье, о=О, 1, ..., (13) начатый с произвольного элемента х/е/, будет сходящимся, если будет, например, выполнено одно нз условий: л а,= птах ~ ч,', 1С„/! <:! (для пространства Е„') (14) 1~Щи / ! / л л Х1/с ал = ~ ~;»', С1/) с. 1 (для пространства Е„').
(15) л 1/! Прн этом нз прннцнпа сжатых отображеннй вытекает н оценка приближения и 1! х(м) — ле !1„( — т!! ФО! — //е 11„, у — 1, 2, 1 — и Приведем программу метода простой нтерацнн: ЕХЕ6 РРОЯТКАН 1/1МЕН810Н С ((т), М), В ()т1), Р (1Ч), Х (Щ ! РОКМАТ (8 Р 6.4'8 Р 6.4'4 Р 6.4) йЕАР (1,!) С, В 1/О 2 3=1,М 2 Х(Л)= В(Л) 3 Н=О. 1/О 4 1=1, Н Е=О. 1)0 5 К = 1, (т! 5 Е = Е + С (1, К) еХ (К) 1/(1) = Е+В(1) Р=АВ5 (Х(1) — 1) (1)) 1Р (Р.ОТ. Н)- Н= Р 4 СОЫТ1М13Е РО 6 1.=1,(т( 6 Х(1.)=О(Ь) 1Р (Н вЂ” 0,001) 7,7,3 8 РАМАТ (!5 Х, 'Х =',Р 7.4) 7 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
