Бабенко - Основы численного анализа (947491), страница 120
Текст из файла (страница 120)
Эти обстоятельства вынуждают нас искать другие способы дискретизации. Глаза О. Численное решение. краеее|х задач 3. Метод прогонки. Рассмотрим вопрос о практической реализации разностной схемы (6), а именно вопрос о решении системы уравнений (6). Пусть Лп — матрица системы. Прежде всего заметим, что ПРИ )1 < 11О ИМЕЕТ МЕСТО РанеиетВО Ап = 4~юг+ ШаХО|п а ИЗ НЕРаВЕН- ь' ства (8) вытекает соотношение Л„' ~, < д Нетрудно понять, что ~А,, ', ) С ) О, где С некоторая константа,.
не зависящая от 6 = и 1. Б самом деле, если бы 11п1:А„1~, = О, то, поскольку шах )хь! < )А„' ! шах шах (~ь', 'с| ), )сг! 1 1|<тяп — 1 последовательность сеточных функций, являющихся решениями системы (6), при и " оо стремились бы к нулю, что невозможно.
Таким образом, соне),(Ап) = ~Л„., Л ' . 1< й г. (16) 3 ад а ч а 1. Пусть В -- ленточная матрица с шириной .тенты 21 З 1. Покажите, что если решать систему уравнений Вх = а методом Гаусса без перестановки строк и столбцов, то число умножений и делений на прямом ходе равно (й 8 1)йп — О(1), а чи|ло сложений состав чает 1лп+ О(1). Обратный ход требует (й+ 1)п+ 0(Ц умножений и делений и (й — 1)п+ О(1) сложений. Замвчанив. Возможно, что при малом й и большом п метод Гаусса оптимален по числу операции.
В случае систем уравнений с трехдиагональной матрицей широко известна некоторая реализация метода исключения Гаусса, именуемая методом прогонки. Мы будем рассматривать не систему (6), а систему более общего вида: оо о+ соя| = йо, Ьогг 1+ пего и-Сггв 1 = дя, ~пгп — 1 + Опгп Йп. й = 1, 2..., ., и, — 1. (17) Этот факт л|ы уже отмечали и его последствия увидим несколько ниже. Матрица А„ трехдиагональяая и принадлежит к семейству якобиевых матриц; для таких матриц решение системы и вычисление обратной можно органиювать очень экономно. Более общий класс, чем класс трехдиагонсльных матриц, образуют так называемые ленточные матрицы. Матрицу В назовем ленточной, если ее элементы Ь,з могут быть отличны от нуля лишь в позициях, удовлетворяющих условию ~1 — у ~ < 1ч Тогда величина 2й+ 1 называется и|ириной ленты.
О ленточных матрицах уместно говорить, когда й фиксировано, а порядок матрицы п может неограниченно возрастать. Если решать систему, матрица которой ленточная, то метод Гаусса будет весьма экономным по числу операций. з 3, О решении краевых задач лкгпадам прогонки 587 Дадим сначала формальное описание этого метода. Из первого уравне- ния системы (17) найдем го =- ьо г1 + тМ Ьь(св агь+ ць.г) = авиа — свгвга =-- дии нз которого находим гь =- сряьт1 + цю (18) где рь — Ьы1ь--1 Чь = аь + Ььбь-~' сь 6,=— аь —, Ььбь 1 (19) Таким образом, формулы (19) справедливы для значений Ь = 1, 2 ... ..., и — 1; отправляясь от найденных значений бо, Оо, по ним можно вычислить бв, пь при й = 1, 2 ..., и — 1. Решая совместно последнее уравнение системы (17) и уравнение (18), отвечающее й =- п — 1, найдем значения „и г„, если только получеяная система совместна. Зная г„ по формуле (18) определим гь (М = п — 2, п — 3, ..., 0).
Вычисление величин бь, пь (й = О, 1, ..., и. 1) называется врлмььм ходам прогонки, а вычисление гь ее обратным ходом. Заметим, что при обратом ходе мы не пользуемся уравнениями (17)„так как это приводит к резкой потере точности. 3 ад ач а 1'. Обьяснить, почему это происходит. Покажем, что если выполняются неравенства ~аЦ вЂ” (Ьь — 'сь > д, А = О, 1, ..., и (20) (Ьо = с„= 0), то прямой и обратньш ходы прогонки можно осуществить. В самом деле.
Ь'=; — «1. со )со! 'ао о +д Считая, что;С ~ < 1 прп т < Ь вЂ” 1, имеем « .<1, )сзо (сь 'гь ~аь —,Ьь! бу — 1 ,'ао! — )Ьь! ~гь~ — б и поэтому ба < 1 (1г = 1, 2, ..., а — 1). Рассмотрим систему Ьиги — 3 апяп аи г — 1 — г, — 1ги=й — 1 где бо — — со/ао, Чо =- Уо/ао Допустим, чго найдены такие б„г1 (З = О, 1, ..., й — 1), что г~ .—. бугтт1 + цу (у = О, 1, ..., 1 — 1). Т1одставляя последнее соотношение прп 1 = Й вЂ” 1 в соответствующее уравнение системы (17), придем к равенству 588 Гласа О.
Числезшсе решение крассах задач Детерминант этой системы равен — (а„+ Ь б„з), и поскольку ~а„Ь„с„— з > а„— 'Ь„(~б„-з >',а„! — (Ь„! > б, то он отличен от нуля, и, стало быть, можно определить е„ы „, и тем самым осуществить обратный ход. Рассмотрим вопрос о росте величин пь( (й =- О, 1, ..., и — 1).
Заметим, что при Ь = 1, 2, .... и — 1 Ььг)ь-з~ Ы Ьь Ы йь «, ' ~Ъ вЂ” +, !ау,- — ~Ььбь з 'ал, — Ььбь д/ ~сь~ л-Ь' ~сЦ вЂ” 'Ь Отсюда, согласно предложению 1 з 1 гл. 7, , с, + Ь , сз' + б, ;с~~ + Ь Потребуем, чтобы ,'Ь ! < 1, ~ = 1, 2, ..., и . 1, )сз.(+ б и тогда ~~1ь < ~йс = ~ (йз Рз ' = б) '. Отметим, что для системы (6) условие (21) выполняется автоматически, а неравенства (20) вытекают из неравенств (7) и требования д(т) > Ь > О.
В З 3 гл. 8 мы проанализировали влияние погрешностей округления на величину погрешности, с которой мы получаем решение системы линейных уравнений методом Гаусса. Не составляет труда провести детальный анализ и метода прогонки. Однако мы не будем делать этп элементарные и не очень интересные выкладки, а ограничимся наводящими соображениялзи. Из общих соображении ясно, что погрешность в решении должна быть величиной = сопс) (А)а, где н = 2 ', а 1 разрядность чисел в машине. Отсюда в случае системы (6) в силу формулы (16) следует, что погрешность порядка Ь Яв. Именно такую величину погрешности мы получим, если самым тщательным образом проследим за ростом погрешностей округления.
Пусть зь приближенное решение системы (6) и Ь ь =- зь - Уь; тогда величины ь (1с = О, 1 .... и) удовлетворяют системе (6), но с правой частью 7ь + Ьуы где бЯ .=- Ь <э(Йь з -- 2длл + дзь з) — с1ьбзь. Так как мы имеем право изменить правые части системы (6) лишь на величину ех Ьт, с тем чтобы не нарушить оценку (10), то в силу случайного характера величин Ьхь нужно потребовать, чтобы )беь < Сй~. (22) 33.
О решенно краеемя задач мето0ож прогонно 339 Тем самылт получаем оценку снизу на величину допустимого шага Ь з' < < СЬь, откуда в < Стье. 3 а д а ч и. В 32 гл.8 мы установили, что при определенных уочовиях квадратная матрица может быть представлена в виде произведения нижней треутольоой и верхней треугольной матриц.
2. Пусть Л -- матрица системы (17). Покажите, что матрицу. Л„можно представить в виде Аа = б„й„, где Ь„и В имеют вид Покажите, что элементы этих матриц определяются по следующим Формулам: Ь,ст-э Ь, го = ао, т, =- о, — , П = , т, = 1, 2, ..., о, (23) г, и если выполнено условие (20), то рекурсивная процедура (23) не оборвется из-за возникновения препятствий типа г, = О при некотором т. Метод прогонки решения системы уравнении с трехдиагональной матрицей является сугубо последовательной процедурой, В последние годы болыпое значение придается построению параллельных алгоритмов, и в частности методам распараллеливания процесса решения систем линейных уравнений и в том числе системам с трехдиагональными матрицами. Следующие задачи посвящены однолту из методов распараллеливания.
3. Покажите, что решение системы разностных уравнений д, = а,г(, — Ь,с, эт1,— г (т = 1. 2, ..., и) с начальными данными т1 т = 1, г1е = ао., связано с величинами г, соотнопиниями гт =- т1,тт1, т (г = О, 1, ..., и). 4. Пусть вектор-столбец 11, = (дч д, т)' (г = О, 1, ..., о). Покажите, что 11, = 1;), ... Ь)э 11о,. где Ф= (1' 'О' ), т.— "1.,2 ..., о. Вычисление произведений Щ...
ьгэ может быть распараллелено. Схему. таких вычислений мы приведем ниже в случае восьми сомножителей ьгт... 1„т,. При этом последовательность выполнения вычислений такова: Ьгтьгг; тэ)зтэгь:, Ьгэьаь; Сатьгеб ЯЯг) МзФ); Яь0е) (1;ЭтЪ); ЯЯ ) 1;гз, ЮЮь) 1;гт; ЯЯггэтзьгь)ьэть Яэьггтэ.'зьгь)ь()ьч)еб (эгтэггчгзтэть)ЯьОььгт); ЯЯг12ьсгэ)Яьсгьт2тсгь). Таким образом, в данном случае работают четыре процессора (в оощем случае п(2 процессоров). В процессе вычислений будут найдены пять лишних произведений: 1„)ь1эь; ьгььгь; т)т12со 0ь|„тьэгт', ьгьггЩтэгь после вычисления величин ст, находятся величины т „1, и при вычислениях на и — 1 процессорах для этого потребуется два шага.
Тем самым разложение А =" 1 Я распараллелено. б. Покажите, как распара.'шеливается обратный ход, а именно — решение систем уравнений В у = д, лая = у. 590 Глава О. Числевеее ре1иеиое кресеык задач Замечании 1. Олисанный метод рагззараллмивания процесса решения системы линейных уравнений принадлежит Стоуну. 4. Корректность разностной краевой задачи. Рассмотрим вопрос о корректности разностной задачи (6), аппроксимирующей задачу (1.1),(1.2). Для дифференциальной задачи количественной мерой ее корректности явились неравенства (1.7),(1.8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
