А.А. Самарский - Теория разностных схем (1989) (1160092), страница 89
Текст из файла (страница 89)
е. й, Ь, й. Это — специальный случай задачи (2) иэ $1. Сеточные уравнения имеют вид Лу = Л,у+ Л у = — ~(х), хан 1ое, у)те = О, (37) 532 гл. х. мктоды гкшкния свточных гг»внвнни Систему уравнений (37) »южно ааписать в операторном виде о Ау '~, где Ау = — Лу в пространстве Н 42 сеточных функций, заданных на ю» и обращающихсн в нуль на границе 71 сетки. В Н вводится 'скалярное произведение (У г) = Х У(х)о(з)" лле» и норма 1у!) У(у, у). Оператор А подробно изучен в гл. 1Ч.
Он является самосопряженпым, положительным и имеет собственные аначения 4 /. л»1Ь . лйй А ЬА А = — ~з(пз ' + з(пз — ' 2= ЬА'1 г г /' Ь, = 1, 2,..., Х- 11а= 1, 2, так что а.»лй 8 Аль «1= ш1пХА А = — з1п — 72 = шахХА А = 2 соз 12 /2 г .1 2 — »2 (38) по которой находится (/2 + 1)-я итерация. Для явной схемы (14) с чебышевским набором параметров вычисления ведутся по формуле А+1 А У1112 = У~ 1,+ т»+ /» + —, ~у11 1,12+ у/1+1,22+ у1,,1, 1+ У1,,1,+1 — 4у1122) + т»+171»12 й т йз 4 где т»+1 ) О2 4 ' 1+р2„. 2 А+2 По количеству действий для нахождения у оба метода отли(аются мало.
Поэтому их сравнивать надо по числу итераций; Закачу (37) мы в дальнейшем будем называть модельной и использовать в качестве эталона при сравнении методов. Сравним по числу итераций метод простой итерации (34), (34') и метод с чебьппевским набором параметров (14), (29). Для задачи (37) схема простой итерации записывается так (здесь, как и всюду в дальнейшем, при рассмотрении итерационных процессов .
для конкретных рааностных уравнений, номер птерации й будем писать сверху над функцией у): »+1 А / А у = у + т (Лу + 7/, (39) г ь» где т = = †. Подставляя в (39) аначение т„ получаем 2 формулу А А . А А А+1 У11 1 12+ З/1+1ЛА + З 132 1+ У11ЛА+1 й 4 + 4 21(2' 6 $. двтхслонныв итирйционнык схимы 533 польэуясь формулами (38), найдем 6 .= — = (й — ж— та й кь вайа г при й» (. Задавая эатем точность, например, с = 2е-" ю $0-а, 3,2 получаем па($) ж — „' для схемы с чебышевским набором пара- 2 метров (ЧНП),па($) т — для схемы простой итерации (СПИ).
Составим таблицу для числа итераций: и спи чнп 1/10 200 32 1/50 5 000 160 1/100 20 000 320 Отсюда видно, что метод простой итерации требует аначительно больше итераций, чем метод с ЧНП. Следует иметь в виду, что оценки для числа итераций получены для любого начального приближения (любого элемента у, из пространства Н), т.
е. худшей сходимости быть не может; число итераций может лишь уменьшиться, если хорошо выбрать начальное приближение. б. О вычислительной устойчивости итерационных методов. Описанный выше итерационный метод в ЧНП иэвестен давно (иногда его нааывают также методом Ричардсона), однако до недавнего времени он почти не использовался в практике вычислений.на ЭВМ при решении сеточных уравнений. Дело в том, что этот метод научался нами для идеального вычислительного процесса (с бесконечным числом знаков), в то время как на ЭВМ вычисления ведутся с конечным числом знаков, в связи с чем имеются числа, являющиеся машинной бесконечностью М и машинным нулем.
Если в процессе вычислений появляется число М~М„, то происходит останов машины (авост). С точки зрения идеального вычислительного- процесса нули(, и параметры т„можно упорядочить любым иэ и! способов. Любые две последовательрости параметров (та) будут эквивалентны, так как для них верна одна и та же априорная оценка, и точность $ достигается за одно и то же число итераций. При вычислениях на ЭВМ раэличные последовательности (т„) неэквивалентны. Если испольэовать в методе с ЧНП параметры 1а, например, в порядке роста: гй = со$2 и, /Р = (12у...ю па 2Ь вЂ” '1 (4(). или в обратном порядке, полагая гй= — со$2 я, й=(,2, ...,и, 2а — 1 (42) то при достаточно малых ф возможен авост вследствие нарастания промежуточных значений у„при /р» и. Это свяэано с немо- 35 л. А.
Самарааай 634 гл. х. методы Решения сеточных уРАВнениЙ потопным характером приближения у„к и из-за того, что норма оператора перехода Е„=Š— т,А от (л — 1)-й к л-й итерации при отрицательных 1~ может быть больше единицы. Поясним ситуацию на простом примере. Пример. Требуется решить систему уравнений Р(х<-,) — 2Р(х<) + и(х<+,) О, х< = й, 1 < < ( Ф вЂ” 1, ' и(0) 1, У(1) =О, Ь= 1/)У, аппроксимирующих задачу и" = О, 0 < е < 1, и(0) = 1, и(1) 0; точное решение и(х) = 1 — х, Р(х,) 1 — х<. В етом случае 4 . лЛ 4 аль, ель у,= — вш — Т,= — сов .Е=19— Л 2 2" 3 < й 2 Л 2 Ау = — у-, Возьмем 19 уравнений (<т"=20) и положим в =10 '. Теоретическая оценка (ЗЗ) дает п,(в) = 63,2, так что' и= 64, и параметры т„т„..., т„при и = 64 выбираем по формулам (29) и (41).
Реаультаты вычислений даны в таблице 3. В первой строке указан Таблица 3 57 5 10« 2,0 10< 2,5 10<< З,З 10« 3,7 10< номер итерации л, во второй строке — величина ьл = ~ у» — ул-< )с — — шах ~ул(х;) — ул, (е<)]. ос<члг Итерационный процесс расходится, и при й 64 наступает аварийный останов машины. Если брать параметры т, в обратном порядке, т. е. определять 1А дня (29) по формулам (42), то неустойчивость итерационной схемы выражена более сильно и авост наступает при й 12 (см. таблицу 4). Ошибки округления можно трактовать как возмущение правой' части уравнения И) на каждом шаге. Итерационная схема (14) с параметрами (29), (41) или (42) неустойчива по правой части.
Причина неустойчивости в том, что норма оператора ЯА= Š— тАА — оператора перехода от ()< — 1)-й итерации к й-й итерации — при отрицательных 1» может быть болыпе единицы, так 536 ГЛ. Х МЕТОЩ~» РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ Предположим, что 1», ) ) 0,5, э <0,01.
Тогда а ~ЯА ~= 3(1 6$)+ 0($))3'0~9 = 2~7 П!!Я»~) 2~7 з-«, Формулы (30) п (31) фактически выражают устойчивость схемы И4) с набором параметров (29) по начальным данным. В случае реального вычислительного процесса, как показывают приведенные выше примеры, необходимо исследовать устойчивость итерационной схемы по правой части, а также устойчи'вость по начальным данным при переходе от у, к р( для любого й 1, 2, ..., л. Как было показано в гл.
Ч(, 3 1, устойчивость по правой части есть следствие равномерной устойчивости по начальным данным, т. е. устойчивости при переходе от любого у» к любому рн где й >) > О. 7. Упорядочение итерационных параметров. Возникает теоретическая проблема — упорядочить множество итерационных параметров (т,) так, чтобы для чебышевской схемы И4) с соответствующей последовательностью параметров т„т„..., т„влияние ошибок округления было минимальным н в процессе вычислений не возникало больших пронек»уточных значений, зависящих от и.
Приведем решение этой задачи и укажем способ упорядочения множества М„параметров (т,), при котором схема И4) устойчива (т. е. найдем «устойчивый набора). Множество 6))а = ( — соз()ь Д» = †„ 8«(»), ( = 1, 2, ..., Е) упорядочено, если построена последовательность целых нечетных чисел 8. =, (8.И), 6.(2), ..., 8.(л)), 1 6.(П < 2е - 1 при $ 1, 2, ..., и.
Параметры (т„) вычисляются по формуле т,=, ',, а,= — соз~,— "8.(й)~, я=1,2,..., . (43) (+ Р«о« Таким образом, достаточно упорядочить множество п нечетных чисел 6 . Алгоритм построения множества 6„ основан на поэтапных переходах от мнол»еств 6 кхмножествам 6, и от 6,„к 6, »ь При этом используются следующие формулы. Переход от 6 к 8, возможен по одной из двух групп формул: 8, (2» — 1) =6„(1), 6, (2») -4Е« — 6, (21 — 1), 1= 1, 2, ..., Е», (44) или 8, (21 — 1) = 6„(»), 6, (20 4Е«+ 2 — 6, (2( — 1), (45) 1, 2, ..., т. з э. дВухслОЙные итегьционные схемы 537 Переход от О, к 91 +~ сводится к добавлению члена О, +,(2т+1) 2т+1, так что 9, ~,(1)- 9, П), 1=1, 2, ..., 2т, (46) В,„+,(2т+ 1) = 2т+1. Если п есть степень 2: п 21, р>Π— целое число, то для оп- ределения О„последовательно применяются формулы (44) при т=1, 2,..., 21 ' и учитывается, что 9, (1).
Например, 'если и ' 1В 2', то строятся последовательно множества 91 = (1, 3), О, = (1, 7, 3, 9, О. = (1„ 15, 7, 9, 3, 13, 5, 11), 911 (1, 31, 15, 17, 7, 25, 9, 23, 3, 29, 13, 19, 5, 27, 11, 21). При переходе от 0 к О,„, согласно (44), после каждого члена 0 (8) ставится член 91 (28) 4т — 0 (1). Рассмотрим общий случай, когда и~Π— любое целое число. Представим его в виде п=2'+21+ ...+2', где Ф~Π— целое число, й,~Π— целые числа, й~>й«+1+1, 1= 1, 2, ..., 1 — 1, й, > О. Образуем последовательность целагх нечетных чисел и;=~ч.",2' ', )=1,2,...,Ф, и,=1, (47) $1 и положим и„., 2п+ 1, что формально соответствует аначению й~+1 — 1. Иэ (47) видно, что а,+, — 1 аз-а,-э 4 =2 п).
Возможны два случая: 1) г) = й« вЂ” й;+1~~2, так что п~.1 = 2 1"и;+1; 2) г;= й; — й;+1(2, т.е. г; =1, щ+1 = 2и;+1. Алгоритм построения упорядоченного множества О„основан на правилах перехода от 01) к О„, Пусть множество В„известно. Найдем гь 1) Если г, ~ 2, то по формулам (44) строим цепочку множеств Оаа -« О 1 .-~ ... -«. 9, , что соответствует значениям т = п;; ) ае) ''' 11„' 1' г. 2пп ..., 2Ч-1щ . Так как щ+, = 2 'щ+ 1, то 9„ + находится, Э" ю согласно (46), при2т = 2 1пй 2) Если г> — — 1, т.
в. п1 = (п,+, — 1)/2, то, пользуясь (45), определяем Ор,; и затем по формулам (46) находим Ощ+, = Оэщ+1 После этого переходим от О„,.+, к О„,, и т. д. 538 гл. х. методы Решения сеточных РРАВнении Вычисления начинаются с ) 1, при котором п, 1 и 0„0, (1).
Если й,=в, то п=п,— нечетное число, и вычисления заканчиваются при у Ф вЂ” 1 после применения формулы ь, (46). Если й, ) О, то п — четное число:. п = 2 п„пр|., = 2и + 1. Так как й,+, = — 1, то г, > 2 и при переходе от 0„ к 0„ применяются формулы (44) для значений ьс-г 1 и = ип 2п„..., 2 п~ = — и.
Отметим, что формулы (45) всегда используются только один раз, после чего применяется формула (46), в то время как (44) 2гт-1 применяется ' раз. Алгоритм описан полностью. П р н м е р 1. и = 90, и = 2'+ 2'+ 2'+ 2, т. е. й, = 6, й, = 4, й,=З, й,=1; п,=1, п,=5, п,=11, п,=45; г,=2, г,=1, г,=2. Теперь можно указать цепочку последовательно вычисляемых множеств, которая приводит к 0„= 0„: 0,-0. 0,-0.-0„-6„-0,.-0., О,. О,. Здесь 0,„(т= 5) обозначает то множество, которое, в отличие от остальных 0~, вычисляется по формулам (45).
Переход от каждого члена етой цепочки к последующему осуществляется, как было. описано выше, по формулам (44), (45) или (46). Пример 2. п 25, п ° 2'+2'+2', й,=4, й,=З, й, О; ~;=1,~ =3;и, 1,и1=3эпз 25. Достаточно указать цепочку множеств в,-в,-в.-в.-в„-в.,-в,. Таким образом, польауясь указанным выше алгоритмом, мы получаем упорядоченное множество и нулей полинома Чебьппева Т„(г) и соответствующим образом перенумерованный (сустойчивыйз) набор параметров т„т„..., г„, определяемых по формуле (43). Условимся в дальнейшем полученное множество обозначать И„=( — соз( — 0„(О), 1=1,2, ...,п~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
