Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 52
Текст из файла (страница 52)
Из (4) имеем ((гв((> < ((('~ (А)((з ((г ((з. (б) (Вскюу далее на протяжении этого параграфа пгщ знаком нормы будем иметь в виду норму (( ((т.) Рассмотрим следующую оптимизационную задачу. Найти такие итерационные параметры тв,..., тп „чтобы варма ((Ов(А)(( была минимальной. Так как матрица А являогсн симметричной. то матрица Ов(А) также будет симметричной. Отсюда следует, что если Л являвтхя собственным значением А, то 1гп(Л) является собственпыи значением О (А).
Таким образом, Глава б. Численные мегсны алгебры как )Т„] < 1 ва ] — 1, 1], то по предположению имеет место строгое неравенство паах фи(Л)] < шах ф~и(Л)] = 1,,а. (9) Рассмотрим многочлеп Бя(Л) = г,а,'аа(Л) — с/,а(Л). Пусть М+т М вЂ” т яу сав —, у =О,..., и. 2 2 и Из равенства Т (х) =- сги(пагссаях) имеем ~)и(Л') = (-1)Ч;.' ПосколькУ Лг О (Гч М], то, согласно (9), ]Ц (Л')] с 1,,'.
Отскша следует, что зайпВ (Ла) = з12пг)~~(Лг). Точки Л",..., Ла расположены мовоаоино на отрезко ]д, М]. Поскольку Я„(Л) меняет знак при переходе от каждой из этих точек к следующей, то в„(Л) имеет га корней па (/а, М]. Кровав того, З. (О) = ()"„(О) — аи(О) = 1 — 1 = а. Мы получили многочлеи степени и, который имеет и+ 1 нуль; следо. вательно, Я (Л) г— в О 62е(Л) = — Юэ(Л) Оь и) шах ]с/„(Л)) = г„° Мы пришли к противоречию с (9).
Лемьаа доказана. Заметим, что данный мношчлен ая,", решает также исжужую оптимизационную задачу, тэк как по построению он имеет иа отрезке ]д, М] и нулей. Оценим скорость сходимости полученного мштша. Воспользуемся явным представлением многочленов Чебышева Лцг =- х + ь/хг — 1. Т (т) = [Лаа -~- Лг)/2, М+д При х = — имеем М-д г — М+д )](М+р]г (тМх /д)г М-1. ~ а,М-„/ (,ГМ+,/д)(,/М д)' Введем обозначение Ле = (г/М -~- чахла)/(т/М вЂ” г/гл). Из (1О) имеем Ла = Ле, Лг = Л,, Так как Лг ( 1, то при болыпих и /М+/а1 1 1„=- Т, ~ /1 - -Л~. ~М вЂ” д/ 2 уб. Оптимизация скорости с:юлимосли Поскольку Лвл н Лз одного знака, то 1н > Л )2 = Л(()г. хнсм = х"' — Ре,(АЦАхю — Ь), где й1.
= глмм — и, и Рее л(Л) = Л ~(1)е е(Л) — 1). Ил1еем гшл' = О~ (А)гн', (~г'ьл'(~г < с ч,((г"'((з, где нч, — — Ц), и в итоье (12) )(г ")(а < и, ... о„„,((гс((э. Рассмотрим случай о, ж (с, т.о. о, = ьйч Тогда, обозначив х" = у', можно записать итерационный процесс (12) в видо у' =у — Ф. (АНАу" — Ь). Соответствующая оценка погрсшвоьти имеет злщ ((у" — Х((з < (ол)" ((у' — Х((э. Такой итерационный процесс нззывакп оиптмплькмм (по |иглу итера- лгяй) лнксйнмлл 1-шааовмм плверал1люннмм процессом. В частном случае й = 1, спгласно (6), выполияютгл соотиосаеыкя и-„— зл — 1 Л ила М+ „ лс-я йу-р ЛУ~-р' Рле(Л) = 1 — ЛС)ее(Л) = 1 1 =, о милн и-я Таким образом, оптппзяьльк|ял1 лвнейнмо одчошаеоемй итсрациоюкьи1 процесс имеет вид умм = у' — — (Ау* — Ь), М+р а погрешносп* оценивается следующим образом: ((ус — Х(), < ( "1 ((у'- Х()т 1йу+рг (этот мвгсд мы уже построили выше в этом параграфе).
На основе приведенных псхтроений можно предложить несколько типов итерационных процессов, В одколс глучае зздаютс» последовательностью значений ое = П < и, < пз ° °, пРиближеним хн' опРеделнют по РекУРРептной фоРмУле Глава 6. Численные методы алгебры 280 4?Ь(Л) = (1 — ггЛ)... (1 — г, Л) = Г)ь(Л), то тг явлшотся величинами, обратными к кор«гяь«многочлсна С)~~(Л). Но О, /М+ — 2ЛЛ по ДоказвнпомУ выше Г)гь(Л) =- Ьт ~Тг ~ ), т. е. коРни вшго мно- М-р гочлела равны И-Ьр И-р (21-1)т Л = — — — — соз ', 1'=1,...,1ь 2 2 29 Ото«сда следует, что значения т, надо брать из совокупности (14) < 2 у' = 1,..., 13 + -( — о Мзг)' (15) зафиксировав последовательно«ггь т« =- Л,..., гь = Л., мы имеем алго- «1 ус ритм (2) для вычисления у"4' по у'.
При больших Ь п произвольном выборе уг,...,уь алгоритм вычисления по форыулам (2), (15) также неустойчив к погрегпностлм округло ппя. ййк, например, если взять т, = Л,, то согласно (3) уравнение для — ! погрешности имеет вид г' = (Š— г,А)г' '. При наличии округлений ово запшпется в аиде г' =- (Š— НА)Н ' + р' '. Последовательно вырывая г' через предьгдущие, имеем равенство ь-« ," =Д(Š—,А)г(Щ+~ Ц (Š— гтА)РЧ =е,ттс«<л ЗДесь к гв пРимеиаетсв опеРатоР 14еь(А) с ноРмой оь = )Ьь! ' ( 1, в то время как операторы, применяемые к ро могут быть с очень большими нормами. При реальных вычислениях для обеспечения устойчивости алгоритма к округлениям осущестзлюот «перемешввание«чисел т,.
Алгоритм перемелпявавнв в случае Ь = 2 заключается в следующем. Последовательна, при 1 = 1,..., 1 строится «наиболее перемещенная«перестановка чисел 1,..., 2Д При 1 она состоит из двух чисел 2, 1. Пусть уже пестр««жа перытввовкз (Ь,',..., Ь',,); следующая перестанов«ьз бератся е виде (21 4 1 — Ь««,Ь«« 2«4 1 — 1з,ЬЗ ',...). Например, прв 1 = 4 зта перестановка имеет вид (11, 6, 14, 3, 10, 7, 15, 2, 12, 5, 13, 4, 9, В, 16, 1).
Прн таком алгоритме выбора Можно проверитгь что к«юффнцвеиты многочленов Гье (А) быстро растут с ргктом 1, поэтому прп больших Й алгоритм вычисления х", использующий информацию о значенкях этих коэффициентов, сильно чувствителен к вычислительной погрешности. В связи с этны для вычисления хь используют метод (2). Поскольку из (4) следует, что 281 16. Оптимизация скорости схолимости итерацианньог параметров норма опера»ора перехода всегда ве булст презаг- ходить 1. Зэдаваягь й = 2', строим п»бчипу чишл Ь»»,..., 1и и производим итграцаи (2) при »начевиях т(26'; — 1) 1 , = 2/ (Ы ч- р — (Ы вЂ” р) соз 21 (18) ь — Т ((Ы +1»)В 2А с М вЂ” р (17) Запишсм гтх»тношекие (17) последоватслыго для й = тг — 1, 1» =- »г, й = и + 1.
Получим .-»= -» Т /(Ы+1»)В-2А) а г"- =1„,та, ( Ы ) ((Ы-1 р) — 2А) с "+' = -' Т 1'(Ытр)В 2А'1 (18) Мпогочлены Чебышева связаны рскуррентным ссотиошениеы Та»»(;г) — 2Та(х) -~-Тх»(т) = О. Умнажим первое уравнение (18) на 1„», третье — на гхг», а к обеим (М -~- р)Ь' — 2Л частям второго уравнения приманим матрючу — 21я — .. СклаМ вЂ” р Чывая результаты, получим г »„»г" — 21х гх Р 1„+гг"т~ = Ы-р =~ Т ((Ы+ р)В 2А) т ((Ы У р)б 2А) — 28 (М+р)Я вЂ” 2А /(Ы.~-р)Л вЂ” 2А1)»д »»г».
Ы-р "~ Ы вЂ” р Как ужс отмечалось выше, 1ьшаговыу» оптимальный прациш обладает тем недостатком, чта число итераций абязатильио должно быть кра» яым й. В случал большого значения й (а шо на практике имею место, чак ках при атом улучшаатся скорость гиодимогти) зто ведет к дошшнигельиым затратам прв решении сиг»нь»ы. Пгжтавим задачу построения итерационного процегх:а, который при ли;бам 1 данг чакую жс оцспку для пагрсшног»ти, как и й-шаговый оптвмальный процесс.
Исходя из»акая послшовки задачи, потребуем, стобы при любом й вектор погрешности г удовлетворял уравненюо Глава Е. Численные мепнь< алгебры 282 Выражение в фигурных сиобках в (20) равно нулю в силу (19). Таким образом, погрешности г" искомого итерационного процесса должны удовлетворять трехчленному соотвошонию (М бр)Š— 2А 1 -<г" ' — 2«„— "+«л г"з =О. (21) М вЂ” р Так как гь = х" — Х, то подставляя эзо выражение в (21), и<мучим х"+< = хл -1- ыяы„<(хл — х" ') — — (1+ ыиыь <)(Ах" — Ь), М+р где ыи = «л/«ь, <.
Разделив обе части (23) иа «э.><, получим и+р 1 — 2 ыэеыьые « =О, М вЂ” р (25) откуда // М~;р ы„= 1 / ~2 — — ы„<) при и ) О, ыз = «о/«<. (26) /~И-р Такиы образом, люжно рскуррентна вычислять величины ьь из (26) и затем векторы х +' из (26). Для получения совокупности векторов х<,..., х" потребуется произвести и умножений матрицы иа вектор, 0(п) умножений векторов па числа, сложений векторов и операций с чисзами.
При этом дзя всех «<, вследствие (Б), (9), выполняется оценка ((х' — Х((з < «;,')(х'- Х((з. (27) Квадратное уравнение и — 2 ы-~-1=0 2 М«р М вЂ” р (М -<- р)Š— 2А <хп — 2«л- хь 4- «ь.«<х М вЂ” р =(- -' (и-~-р)е-2А — <Š— 2«ь -~- «„з<Е) Х. (22) и — р Всзцдствие (19) и равенства «л = 7„'(ь«-+~) имеем /МжрТ (23) ~ -р)ь и с<ютношеиие (22) ыожет быть переписано в виде и р| М-р Мы получили требуемое рекурревтпос <иотвошепие.
Приведем с<о к Галсе уж;бному виду. В<недотепе (23) рввонство (24) можно переписать в виде 2 «ь,ХЯ+' — (1„„, О «ь,)Хл+ «я,Хь-' = — («ьз, + «„,)(Акь — Ь) М 4- р 283 16. Оптимнзапи» скорости схслвмости имеет два положительных корня Наимевыннй из этих корней, равный М+и /М 1-д~з ъ'М вЂ” чгд 1 М вЂ” д (,М вЂ” ! /,/М,г 1, Ле обгпначим черш ы. Итерзционвый процесс (25), (26) называют опшпмальнгхм (по количеству итераций) лппгйшхм пгпс!ш!пшвгихм пров,сшсм. При !хилизации процосса (25), (26) после лкбых й применений матрицы А мы получаем оптимальный рсзулыат в слпшлс (6). Из гкшаиного видно, что по скорости сходимосги ггтерагшогшый процесс (25), (26) предпочтительнео, чем (12).
Однако иногда от него отквзыва~отся в пользу [!2) из-за соображений' эковолгии памяти ЭВМ. Получим более наглядную оценку скорог;тв сходпмости построенных итерапиовных процессов. Согласно (27) и (11) для оптвмальпого итерационного процесса вьгполпяет~м оценка ()х — Х((з < 2Л„"!(х" — Х)(з. Норма погрешности гь уменьшится по крайней мере в е ! раз, если 2Лс" < с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
