Годунов С.К., Рябенький В.С. Разностные схемы (введение в теорию) (1185928), страница 48
Текст из файла (страница 48)
Считая„что норма первоначальной ошибки аа порядка единицы. ]]еа]! — 1, в силу замечания п. 4 $35 о разумном порядке Оценим наибольшее отклонение (;)'„ многочлена 0»()») = =— Тд()») от нуля на отрезке а < )» < Ь. Как известно из теории аппроксимации функций,многочлен Чебышева Т,(х) принимает наибольшее по модулю значение на отрезке — 1 < х < ! в й+ 1 точках, к числу которых принадлежат концы этого отрезна. Поэтому из (10) следует, что 1 д(хп) (х + /х» — !)д+ (х — /х2 — 1)» зш эллиптические злдхчи 1гл. и точности, которого следует добиваться, решая задачу итерациями, надо выбрать й из условия 1/" М, т. е.
2 1и М+1и 2 М 21п М+!п 2 (14) Пля погашения первоначальной погрешности в е раз надо выбрать й из условия (г„(» е-', т. е. й М 0(М). 2 з/ч (15) Выбрав й из этого условия, можно затем первые /г шагов итерации принять за первый цикл итераций и повторять весь цикл с тем же набором параметров тг, ть ..., тд. Для уменьшения нормы погрешности в М' раз потребуется такое число ч циклов, чтобы е- !/М', т 21п М. Общее число элементарных шагов итерационного процесса за т циклов будет /гт ж ( " М) 2 1п М = 0(М!п М). Опо лишь в конечное число раз ! +!п2 2 2 + !п 2/!!и л11 »(! + 1п 2 и =и +'тп +,(Льи — гр), и !п=ф, и задано.
пег! о (15) превосходит число (! 4) элементарных шагов итерационного процесса, не использующего зацикливание. Таким образом, использование цикла с /г ж(1+!п2)/(2 т/т!) дает упрощение без существенного увеличения числа итераций. Использовать циклы длины й « 1/(2 угч!) нецелесообразно. Например, при й =! процесс Ричардсона (4) превратится в процесс простых итераций (1) с оптимальным выбором т. Число шагов процесса для уменьшения нормы первоначальной ошибки !~ге!! в е раз будет ж2Мт/х', как показано в п. 2 $ 35.
Это число в 0(М) раз превышает число шагов, необходимых для этой же цели прн выборе длины й цикла в соответствии с (!5). 3. Нумерация итерационных параметров. Формулы (!1) задают оптимальный набор итерационных параметров тг, ть ... ..., тд (при заданном фиксированном й). Переставим как-либо члены последовательности тг, т„..., ты расположив их в некотоРой очеРеДности хгп1 = (хг, хп, ..., хя), и бУДем вести итеРации по формулам ИТГРМ!НН С ПЕРЕМЕННЫМ ШАГОМ 317 ! с,', = П (1 — т, Р„1 с"„. Проследим за эволюцией с,', с ростом ! при г = М вЂ” 1, з = = М вЂ” 1.
В этом случае Рга Рм-ьм-1 Рвах (а М а 5'= ',"-' ' =П(1 — т,Ь). ам-ь м-1 ! (! 7) Рассмотрим линейные функции 1 — тгР, ! = 1, 2, ..., й, нули которых Р1 = !/т; определяются формулами (1!). Из этих фор- 2/ — ! ! . а+3 мул видно, что при < †, или 1 < — , справедливо не- 2А 6' 6 равенство Р! < —, и поэтому (рис. 45) Ь !1 — т1о|>1 при 1< —, а+3 (18) 1 1 1 1 Если й = М, а) 1, то Р1 а+ —,т! 2 ~lч М' а М' и поэтому ( 1 — т1Ь ) — М'. а При идеальной реализации алгоритма (16) результат финальной, й-й итерации не зависит от выбранной очередности х!А> = (х!, хь ..., ха). Но при реальном расчете, который ведется на машине с конечным числом знаков, этот порядок крайне важен. От него при больших'й резко зависит чувствительность результата к ошибкам округления, допускаемым на промежуточных шагах процесса, т.е.
вычислительная устойчивость алгоритма. Прежде чем приводить приемлемые порядки хм' = = (хих„..., ха), заметим, что исходный алгоритм (4), отвечающий х<А! = (1, 2,..., й), практи- л а ра чески непригоден. /-яа Разберемся в механизме возникновения неустойчивости в этом случае. Пусть начальная Рис. 46. погрешность з' имеет вид еа = = ~ с,',аРо' ", с,', = 1, и расчет ведется точно, без ошибок округления.
Тогда коэффициенты погрешности 1-го приближения а = = ~„с„ф ' выражаются формулой % ! ГО а! эллиптические злдхчи (гл, и З(В Таким образом, величина Ц(, определенная формулой (17), увеличивается сначала примерно в М' раз за один шаг, а потом медленнее. В силу (18) этот рост продолжается во всяком случае до тех пор, пока ! ( (й + 3)/6, так что при ! — А/6 величина с,'„,, „а вместе с ней и 11аЧ, окажется очень большой и тем большей, чем больше число й.
При этом порядки величин значений приближения и' =(и(~,) могут выйти за пределы допустимых для данной машины уже при умеренных й, й « М. Если гипотетически считать, что этого не произошло и что счет продолжается точно, то к шагу ! = й величина с' вновь уменьшится, так что $4 ~~9'. Но дело в том, что даже если и не произошло переполнения ячеек машинной памяти прн ! й/6, то неизбежные малые относительные ошибки округления при ! й/6 велики по абсолютной величине. Они носят случайный характер, так что в их разложении в конечный ряд Фурье будут присутствовать всечлены, в частности член вида ,((, и с(,(ф ' причем с,, — величина не малая по абсолютной величине.
Покажем, что при дальнейших шагах итерации ошибка с(, ((р(! '1, внесенная на гармонику ф(' '1 в результате округления на шаге ! й/6, не претерпевает существенного погашения и недопустимо искажает результат. Вызванный ею вклад сь (ф~ ' ' в приближение иь, полученное на последнем, й-м шаге, выражается формулой Но при ! > (А + 3)/6, очевидно, (г Ь вЂ” а! Ь 1(( > — ) Ь + а — 1 > — М-'. 2 ) 2 ) 4 Поэтому 1 тт 1 ъ~ 1 — т(а-1 — —, Ц (1 — т!а) (х1 — — ) — 1, м ° .И м!) ! (+! так что еь, — с, „ и погашения погрешности округления не произошло.
Практическая непригодность нумерации параметров нм! = (1, 2, ..., й) показана. Если на 1-м шаге процесса (13) внесена погрешность округления „(и н с„ф ' 319 итеилции с пеееменным шагом то на й-м шаге она разовьется в Поэтому целесообразно стремиться к такому выбору хев = = (хь хм ..., ха), при котором имеет место оценка (19) при умеренном значении А. Пусть с'„фц " — компонента погрешности еа нулевого приближения. К 1-му шагу она разовьется в Если норма этой функции велика, то ее округление дает значительный по абсолютной величине вклад во все гармоники. Может оказаться, что вклад, полученный некоторыми гармониками, при дальнейших итерациях не погашается и сильно искажает результат.
Поэтому естественно стремиться к такому выбору хм! = (хь хм..., ха), при котором выполнено неравенство 1 гпах Ц(! — тг!г) (В ами~ь г-~ (20) при умеренном значении В. В работе В. И. Лебедева и С. А. Финогенова, ЖВМ и МФ 11, № 2, (1971), и в работе А. А. Самарского [23] указаны различные целесообразные способы нумерации параметров и освешена история вопроса.
Приведем результаты работы В. И. Лебедева и С. А. Финогенова. В ней предполагается, что й является степенью числа 2, т. е. й = 2', и указаны реккурентные формулы для построения х(м Именно, при ! = 1 х<м =(1, 2). Если при й = 2'-' порядок х(' '1 уже определен: х(' 1=(хп х„..., х,~ ~), то полагаем х(з)=(хи 2 +! — х„х, 2'+1 — х,..., 2'+1 — хз~ — ~) (21) ЭЛЛИПТИЧЕСКИЕ ЗАДАЧИ 1гл. 1! В частности, при !' = 2, ! = 3, ! = 4 последовательно полу- чаем (1, 4, 2, 3); (1, 8, 4, 5, 2, 7, 3, 6); (1, 16, 8, 9, 4, 13, 5, !2, 2, 15, 7, 1О, 3, 14, 6, 11). а — ив пп+1 д — — (Л и + Л ив+' — 1р(х, !! )1, и"+!( =й „~ =ф(з „), т,и=1,2,...,М вЂ” !. Для погрешности е =и — и получим выражение м-! Г А "= 2 А!Э»,;-[П ОЗ.<,>)"...
г, я-1 ! 1 где ! — 2тМ1 в!п'— Х;(т) =— 1 + 2тМ' в[п'— 2М 1=1,2,..., Й. При заданном и оптимальным является такой выбор чисел ть тв,..., тм при котором величина !пах ПЛг(т!) Х,(т!) из 1г-1 принимает наименьшее значение. Если не пользоваться точным знанием чисел Х„(т) и Х,(т), а лишь границами, где они лежат, возникает задача чебышевского типа для произведения дробно- линейных функций, подобная рассмотренной в п. 2 для много- членов. Постановка этой задачи, как впрочем и предложение использовать для решения уравнения Пуассона процесс установления При указанном способе (2!) упорядочения итерационных параметров числа А и В в неравенствах (19) и (20) можно выбрать независимыми от й и от 1.
Алгоритм упорядочения параметров, указанный А. А. Самарским, формулируется несколько сложнее, но при этом й не обязательно степень двойки. Число й может иметь вид й = = (2)+1)2'. Вместо (19), (20) установлены другие оценки, гарантирующие устойчивость в некотором сл!ысле. 4. Метод Дугласа — Рэкфорда. В схеме переменных направлений (6) э 35 будем считать итерационный параметр т завися. щим от номера шага, положив НТЕРАШАН С ПЕРЕМЕННЫМ ШАГОМ З2! со схемой переменных направлений, принадлежит Дугласу, Пис- ману и Рэкфорду. В работе Дугласа и Рэкфорда 1956 года, ко- торую мы здесь изложим, было дано приближенное решение этой задачи. При их выборе итерационных параметров число шагов итерационного процесса, нужное для уменьшения ошибки в е раз, есть 0(1п М), а число арифметических действий есть 0(М !ПМ), Покажем, что, задав произвольно положительное д,д(1, можно так выбрать итерационные параметры т!, тм ..., тд в количестве й = О(!пМ), чтобы выполнялись неравенства ! [Ле (т!)Лв(т!)! [Лу (ту)Лв(ту)[ ' ' [Лг (тА)Ле(ЕА)[ ! < уеье (22) г,з=!,2,...,М вЂ” 1.
Тогда !!а" [! ( д [!еа!!. Если производить первые й итераций с итерационными параметрами ть тн, ..., тю затем следующие Й итераций, снова используя тн т„..., тю то для уменьшения нор- мы погрешности в е раз потребуется, очевидно, некоторое не за- висящее от М число таких циклов, содержаших по и = 0(1п М) итераций каждый. Обоснуем равенство (22) и при этом объясним, как можно выбРать паРаметРы ть тм..., тА. Очевидно, что ! Л;(т)! < 1, 1 = 1, 2, ..., М вЂ” 1, т ) О. Поэтому для выполнения при любых г, з = 1, 2, ..., М вЂ” 1 не- равенства (22) достаточно, чтобы при любом ! = 1, 2, ..., М вЂ” ! хотя бы один из Ф сомножителей Л!(тр), р = 1, 2, ..., й, удо- влетворял неравенству я1 1 — 2т М' н1не— 2М ( 1/Ц [Ль(т )! (23) ! + 2трМ 5!пав 2 2М Все числа 2М~Е!п —, 1=1, 2, ..., М вЂ” 1, принадлежат отрезку а(~0 5и'(р(2Ме =Ь (24) Итак, для выполнения (22) достаточно ввиду (23), чтобы для каждого значения р из отрезка (24) хотя бы при одном т, т = т,, тм ..., тн, выполнялись неравенства и тем более достаточно, чтобы выполнялись неравенства — 1уУе) ~~ 1 — трр ( у д.
11 с. К. Гануева, В, с. Рнбеньннн 322 эллиптические задачи [гл и Для этого нужно, чтобы для каждого )г из отрезка (24) при некотором т„, р = 1, 2, ..., й, выполнялись неравенства 1 Ъ~г? < т )э < 1 + )/Ч. Зададим )хр и тп соответственно формулами (25) тр — — ~, р=1,2,..., Е (26) Тогда при возрастании Р от )ьр до )хпчч число ти)ь пробегает отрезок (25). Очевидно, что, выбрав й из условия Ри ) Ь, т. е.
й > Л !и — + 1 = А (2!и М + !п у) + 1, 1 А= !+ъ/д 1 — ч/д (27) мы н получим по формуле (26) интересующую иас последовательность ть тм ., тго ЗАДАЧИ и больших значениях й и М. Какие гармоники зйн и будут преобладать в ряде Фурье для погрешности еь, полученной в результате расчета при хоо = (й, а — 1, ..., 1) с ошибками округления? 3. Пусть Л вЂ” самосопряженный оператор, собственные значения которого лежат на отРеэке 0 ( Риы ( Р ( 1ьи *. КакомУ Условию долхсно УдовлетворятЬ ЧИСЛО ОбуСЛОВЛЕННОСтИ Ч = рьчь/рыаю ЧтвбЫ дЛя рЕШЕНИя ураВНЕНИя Лх = гр сходился и был вычислительно устойчив процесс Ричардсона ха+~ = х — та+ (Лх" — р) при произвольном выборе тз 1/Нь рань ( Мэ ( рмчз, 1 = 1, и, й произвольно? 4. Почему при использовании схемы Дугласа — Рэкфорда очередиогть использования параметров ть тз.
.. ть не влияет существенным образом на вычислительную устойчивость итерационного процесса? !. )нежно ли выбрать итерационные параметры ть тз, °, ть так, чтобы за конечное число шагов итерационного процесса (4) получи,пось точное решение раэностной задачи Дирихле? Сколько для этого надо сделать итераций? Выдерживает ли такой прпеч решения обобщение на случай, когда точные значении собственных чисел р„ неизвестны? 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
