А.А. Самарский - Введение в численные методы (1113832), страница 18
Текст из файла (страница 18)
(13) Умножая (!3) на с„п суммируя по й= О, 1, 4 в (с, = 1), получим ь И Р„(А) $, = ~~Г~ слАл$, = ~~ сеХ~ье, —.— Р„(),„) ь,. г-о Лг О Сравнивая зто с Р„(А)е, Х,(Р„(А))$„видны, что ),(Р„(А)) = Р„О.(А]). Собственные значения операторного полипома Р„(А) определяются как полппомы Р„(Х) от соответствующих собственных значений оператора А, а собственные функции — те же, что и у оператора А. В силу самосопряженности оператора Р„(А) его норма равна наибольшему по модулю собственному значению 1Р„(А)~ = шах ! Р„(),)). гсг~л 114 Гл гп Решение алгеГРлнчесгчих увлвнегчип Собственные значения )., оператора А лежат на отрезке (Тч, т,): тч < Х, ~ т,. Очевидно, что гвае ) Рх (Х,)! ~ (шак ) Р„(х) (, гххви тгхххтг где непрерывный аргумент х принимает все значения на отРезке (Уь Тг), и, следовательно, задача о минпмУме 1Р„(А)1 сводится к задаче о миинмаксе полинома Р„(т), т.
е, о нахождении ш1в шах (Р„(х)(. (ча) т ххвтг Отобразим отрезок (то т,) ва отрезок ( — 1, П, полагая 1 ((уг — уг) г; уг + уг), 1 ~( 1~ (1~ при уг ~ (х ( уч. (14) Тогда 1'„(1) = Р,„(г), Условие нормировки Р„(0) = 1 приаимает вид Р„(1„) =- 1, 1 =- — 1,гр . (15) Итак, требуется найти полипом, нанменее уклоняющийся от нуля на отрезке -1:- =1-.= 1, так чтобы шах ~Р„(1)~ был минимален прп дополнительном условии нормвровкп (15). Таким полиномом является полипом т„(г) Р„(1) = —" Т„(г,) ч (10) где 7„(Й вЂ” почином Чебыигева, Т (г) —.
сов(п атосов Г) при )1) (1, (17) т„(1) = — ((1 + )г'г' — 1)" + (1 ~1 1)" ] при )1)) 1. (18) Полипом Чебышева имеет нули 21 — 1 (ч =- сов —, я, г = 1, 2,..., п. 2н (19) Полипом Р„(х) = (1 — т,х)(1 — тхх)...(1 — т„х) имеет нули х, = 1/та Требуя, чтобы корни зтик полпиомов совпадали, и учитывая связь (14) между х и г, получаем 2 = ((т, + тг) + + (»х — Т,)й)ть откУда следУет т, = 2/(Тх + Т, + ((г — 1,)й), К = 1, 2, ..., гг.
(20) Эта формула сохраняет силу при любом способе упоря- 1 ь дВухслОйнАя нтеглционнАН сххмА 115 дочения нулей полинома Чебышева; например, вместо 21 — 1 (19) можно положить 11= — соэ, л. Имея зто в виду, приходим к формуле (9). Заметим, что если и = 1, то получаем т; = т, — оптимальный параметр метода простой итерации. Итак, параметры т„ ть . т„ определены согласно (9). Найдем теперь ((„= шах (Р„(х)(= 1пах )Ро(1)~ = тгмхлт. -1Л1 .1 так как шах ) Т„(1)! =- 1. Имеем )(о) > 1; поэтому для — 1Л!Л1 )Тх(11) ~ воспользуемся формулой (18) при 1=11.
Преоб- разуем входящие в пее выражения: — 1 Г 1 1 ос (г,(~ )Тг,' 1 = — ~ у —, — 1 = — (1 ~ У 1 — р,~ .= "о 7 ро оо М~'Л). '(1 а)/(1 $)= 1о о = (1 ~ Л)'/(1 — Б) = (1 ~ Л)/(1 ~ Л), так что ) Г )+ )т То — 1 = —, (го( — у (о — 1 =- р„и Р, (То(1„)(= ~ +р,~= Оценка (10) доказана.
3. Вычислительная устойчивость и упорядочение пара- метров. Итерационный метод (8) с чебышевским набором параметров (т„) иногда называют Алетодозо Ричардсона, Известен он давно, однако до недавнего времени почти пе использовался на практике из-за вычис,лительной не- устойчивости, Поясним зто понятие па примере.
Возьмем систему уравнений иП вЂ” 1) — 2и(И+иИ+1)=0, 1 -1, 2, ..., У вЂ” 1, (21) и(0) = 1, и(% = О. Ге решением является и(1) 1 — хь х, = (Ь, Ь = 1/)г'. Будем искать решение этой задачи чебышевскпм итера- 116 тл, 111. Рршение АНГИБРАических уРАВнений цпонным методом для дс 20. Значение и,(е) мы можем вычислить. Оно может быть нецелым. Выбираем ближайшее целое и ~ и,. Для данных снс и е имеем и(е) = 04. Зная 4 . хла 4 аль Т = — зш —, Та = — соз —, У' 2 4 можно вычислить т, по формуле (20). В качестве началь- ного приближения берется функция (1, 1= — О, Оказывается, что для метода (8), (9) небезразлично, в каком порядке берутся нули р» полпнома Чебышева. Рассмотрим два способа нумерации нулей: 27а — 1 са,)ра =сов —.л, й=1, 2, ..., и, ."х л =- соз,—, Хп = — сов —, 2а' ' 2а' 29 — 1 к,) (с» =- — соз, и.
Результаты расчетов приводятся в табл. 1. Тайнлпсса 1 Набор а, Набор а, * =нпахСР Сх 1 — а Ст )! х а н а с и А =нпахСУ Са 3 — р на 9 а х а н с — с н 39.6 2,6 10а 6 2,10н 3,3 10" 1,2 !О" Ч 1СС!а Авпбт 0,12 27 1,9 10н 3,7 10' 2,6 10" 2,5 10'" 3.3 Ыпн ",н'.1ска .анснбат о 7 9 11 12 53 )н «7 59 60 61 62 63 64 )Три меньших апаченилх ДС н и может оказаться, что рост провсенсуточных аначеппй р„не приводит к авосту, однако происходит накопление ошибок округления,п после п итераций условие окончания итераций 1Л р, — /1 ( ~ е1Арн — 11 не выполняется. 5 ' ДВУХСЛОЙНАЯ ИТЕРАЦИОННАЯ СХЕМА 117 Зтп две осооенностп вычислительного процесса — рост промежуточных значений, прнводнщих к авосту, н накопление ошибок округления — мы характеризуем одним термином — вычислительная неустойчивость.
Причина вычислительной неустойчивости чебышевского метода в том, что нормы (!Е»+,(! оператора перехода Е»+»=Š— т»юЛ для некоторых итераций болыпе единицы, а вычислительный процесс является реальным, т. е, имеются ограничения сн»ээу п сверху па допустимые числа (есть ъ»ашиппый пуль и машинная бесконечность) п в каждом акте вычислений появляются ошибки округлений. Вычислим норму для Е,=Š— т„А. Так как Е» = — Е», то !/Евт»(! =- В»э)э /(Е»ь»х, х)). Ич условий (,Е(А ( Рв!=э -- Т,Е следует (т»-,уэ — 1)Е ( т»»,Л вЂ” Е - (т»з,у, — 1)Е, Подставляя сюда выражение для т»„, н учитывая, что 1 — т»у» = т,'(» — 1 = р„получаем р (1 Н») р (1, р») Отсюда находим рв (1 ! !»») нри РА > (Э 1 т рву» 1Е,„,1, =)~„Л— рв (1 — р») — прп )»» (О, 1тр и» так что (!Е»»,(((1 для всех )»»)О и !(Е».„,(!)1 прн р,( — (1 — р»)э'(2р»).
Так как и (2п — 1) я — сов,— ', (и»( — сов . л = сов —.', 1» =-1,2 ... и 2н 2и 2и' то для большего числа номеров й имеем !!О»(!) 1, и сслп подряд используется много параметров т„для которых !!.э»!!) 1, то происходит накопление погрешности округленэтй Й рост итерационных приближений, что и приводит и вычислительной неустойчивости. Чтобы ослабить этот эффект, естественно попытаться чередовать параметры т». Для которых ((Е»!!) 1, с параметрамя, для которых ~'о»(! ( 1, На этом пути н проводится построение такоп последовательности параметров (т,), для которой сходпээость ктераций носит монотонны!1 характер и вычислительная неустойчивость отсутствует. Пмеется правило такого упорядочения нулеп 118 гл.
ггг, Рвшепив хлГРБРхичкских РРАБНГ(глгй 21 — 1 1(= — соз: я полинома Чебышева, а тем самым н 2п параметров (т„), для любого и, прп котором имеет место вычислительная устойчивость. Ыы приведем это правило для случая, когда и есть степень числа 2, и= 2', р) 0 — целое числов). Обозначим упорядоченное по этому правилу множество пулей й через где 0("~ — одно иэ нечетных чисел 1, 3, 5, ..., 2п — 1. Задача своднтся к уиорядоченн(о множества и нечетных (и( (20 (пп чпсел: Оп = — - (О(, Ов,....
Оо (. Исхо((я пз множества О, = (!), постропм множество 0„=- О.,р ио формулам 0"'"' = 0(ою «1-1 еслп О, известны. Соответствующую последователь(но ность параметров (т(,) оупен называть устойчивыл япбороль Пусть, например, а = 16 = 2'. Последовательно па, д .. О, = (!), О, = (1,' 3), О, = (1,' 7, 3, 5), О„ = (1, 15, 7, 9, 3, 13, 5, 1!), О,. = (1, 31, 15, 17, 7, 25, 9, 23, 3, 29, !3, 19, 5, 27, 11, 21).
Прп переходе от О., к 0»„, достаточно ' (по Оп ( после каждого Ом ( поставить число, равное 4т — Оы „ (нумерацэя соответстнует 0„,). «Устойчивая» последовательность О не завпспт от задачн. Сходнмость итераций для этого набора параметров (т(,) носит немонотонпьгй характер, но колебання здесь невелики и в конечном счете затухают. Приведем р('зультаты расчетов для задачп (21) по схеме (8), (9) с устойчивым набором параметров (тл): В 1 4 8 1а 24:(2 48 50 02 а(, 89 8 4,7 1 1 0,2 0 1 О 04 1,5 10 » 0,7 Ш *' 8,7 10' ' 4.
Неявные схемы. Метод Зейделя н метод верхней релаксации сходятся быстрее явного метода простой птерацпн. Поэтому переход к неявным схелгам оправдывает ») Правило упорядочения (т») дэв любого и можно нвйгн в (6, 9), м с двухслойная иткгхцнонная схгмх (тй себя. Как нужно выбирать оператор В) Основным является общее требование минимума действий ()(е) для нахон'денна решония с точностью е >О, которое сводится и двум требованиям: 1) о минимуме числа итераций, которое зависит как от В, так и от выбора (т,); 2) о минимуме числа действий для решения уравнения ВУь„, = Р'ю (экономичность оператора В).
Примером может быть треугольный оператор, соответствующий треугольной матрице. Покажем теперь, что результаты, полученные выше для явной схемы, мон'но перенестп на неявную схему. Рассмотрим неявную схему В " ' ' " + Ауд = у, а = О, 1,..., для всех у, ен Н, йчт (22) где А Ае > О, В = Ве > О и (23) тнВ~А =; (,В, .(, >О. Выбирая итерационные параметры (ть ) по формулам (9) н упорядочивая их в соответствии с предыдущим пунктом, получим для решения задачи (22) оценку врп ИУ вЂ” Ив-т~~Ч.1АУо — Лв-~ У = —,',,и 1 р,=, $= — ', (24) 1+УГ 7 где (, и уз — числа, входящне в (23).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
