Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 18
Текст из файла (страница 18)
гсе~л 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) =О, 1 -1, 2, ..., 1'г' — 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, У(), О„ = (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). Для числа итераций я=и(е) верны оценки (11) и (12). Чтобы убедиться в этом, достаточно свестн задачу (22) к эквивалентной задаче для явной схемы + Схь = О, й = О, 1, ..., х,:=- В"'и ю (25) та+ где х„=Вг"шм С =В "АВ "' — самосопряженный положительный оператор с границами спектра (, и (,; Т ~ ~Ъ (26) В самом деле, так как В = В* > О, то существует В" = (В"')* > О, Действуя оператором В " на ураане- 12о гл.
пт. ггппкнпс ьлгквгьичгскпх гглвнкнии пнс (22), получаем (25) для х„=Во'иь Обратный ход рассуждений очевиден. Остается доказать эквцвалептность неравенств (23) п (26). Рассмотрпм функционал /= ((А — "(В)у, р) = — (Ау, р) — 7(Ву, р) = = (АВ 'п(В"-"у), В-'"-(В'"у)) — 7(Во-'), Вп') ) = = (Сх, х) — 7(х, х) = ((С вЂ” тВ)х, х), где х В'пу. Так как р (а значпт, и х) — произвольный вектор пз Л, то пз равопства У=((Л вЂ” 7В)у, у) ИС вЂ” 7К)х, х) (27) следует, что операторы Л вЂ” 7В и С вЂ” 7В имеют одпнаковые знаки. Если, например, Л вЂ” 7,В -=-О, то прп равенство (27) дает С вЂ” т,Е ~ 0 н т. д. Для явной схемы имеем оценку 1х„з < д„зх,1.
Подставляя сюда х„= В"'и„= В-"'г„г„= Л р, — (", получаем оценку (24). Для методов Зсйдсля и верхней релаксации В те В*, и потому нельзя воспользоваться чебытиевскпм набором параметров. и б. Попеременно-треугольный метод 1. Попеременно-треугольный метод. Будем рассматривать неявную итерационную схему В "+' " — ', Ау„=), я=0,1,... (1) тл. д Если оператор В представляет собой пропзведгние конечного числа экономичных операторов, то он также экономичен. Так„ экономичным является оператор В = В,Вп равный произведению треугольных операторов В, и Вз. Рассмотрим так называемый попеременно-трерзольяый метод — метод (1), для которого оператор В имеет впд В = (В+ юЛ,)В '(Рл+ юЛ,), (2) где Ю тле>0, В~=Ли Л,-)-Лт=-Л, Л=Л" >О, ы > 0 — параметр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
