Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 21
Текст из файла (страница 21)
2п 109 где х' †)ля координата вектора х. Точная формулировка и решение задачи оптимизации итерационного метода (2) содержатся в следующей теореме. Теорема 1. Пусть А — симметричная положительно определенная матрица, Л ы(А) >О и Л .,(А) >Π— ее наименьшее и наибольшее собственные значения. Пусть задано число итераций п. Среди методов вида (2) наименьшую погрешность 11х„— х11 имеет метод, для которого Если выбрать т„согласно (3), (4), го для погрешности будет справедлива оценка 1!х„— х!! (д„!!х» — х)!', (5) где 2р" ! )»'У Л„» (А) Ч~= ! !»л» рт= )+.у~ц ' ь — Л (А) Д о к а з а т е л ь с т в о. Для погрешности г,=х„— х получаем уравнение ели — гь +Агь=О, й=О, 1, ..., п — 1, гь — — хь — х.
(7) т»м Из уравнения (7) получим, что г„= (Š— т,А) (Š— т,,А)... (Š— т»А)г» для й=!, 2,..., и и, в частности, г„= Т„г„ где (10) (т~( тпах !7„(Л)~, "е!п<Л)ЧЛ~'чп»х(Л) где 1„(Л) = (1 — т,Л) (1 — г,Л) ... (1 — т„Л). Таким образом, приходим к задаче о нахождении пнп шах ! )„(Л) ~, »» П'" »»» Лп»КНЛ)~Л~Л»»ах!Л! уже рассмотренной в примере 2 из п. 4 $ 5. Полученные в этом примере формулы (29) для параметров т, совпадают с формулами (3), (4), а величина отклонения при данных параметрах равна !т~ =д„, где д„определяется согласно (6). Теорема 1 доказана. пе Т„= (Š— т„А) (Š— т.,А)... (Š— т,А).
Поскольку ҄— симметричная матрица, ее норма совпадает с ее спектральным радиусом (см. $6 гл. 1) и выполняется оценка !!г.Ж И !1М, (9) где т — максимальное по модулю собственное значение матрицы Т„. Оценка (9) неулучшаема, т. е. найдется вектор г„для которого она выполняется со знаком равенства. Для доказательства теоремы остается подобрать параметры т„т„..., т„так, чтобы минимизировать !т~. Пусть Л„й=1, 2, ..., гп,— собственные числа матрицы А. Не ограничивая общности, можно считать, что 0(Л,„(А) =Л»<Л,<... <Л =Л (А). Согласно (8) имеем !т~= щах !(1 — т,Ль)(1 — т,Ль) ... (1 — т„Ль)~.
(11) »мь~»ь Очевидно, что Итерационный метод (2) с параметрами т„определенными согласно (3), (4), называется явным итера!(ионным методом с чебышевским набором параметров. 3 а м е ч а н и е. В случае л = 1 метод (2) — (4) совпадает с методом простой итерации ха„— хо + Аха = /, где 2 Л ~о(А)+Л -(А) Из теоремы ! следует, что т=то является оптимальным значением параметра т в методе простой итерации.
Оценка (б), (6) в случае и ! принимает вид !!х~ — х!! ( ро(!хо — х!!. Точно так же для любой итерации й справедлива оценка !!хо+о — х!!(ро(хо — х!!, откуда И хо — 1(р.'!! хо — и Эта оценка погрешности метода простой итерации была получена другим спо- собом в $4 (оценка (13) из $4). Подсчитаем число итераций, достаточное для получения заданной точности в при использовании явного метода с чебышевским набором параметров.
Из оценки (5) получим, что !!х„— х!!(е!!х,— х!1, если д„(в, где д„определено согласно (б). Таким образом прихо- дим к неравенству решая которое относительно л= р,") 1, получим 1 1+ г'! — ео — ) Ро е Последнее неравенство будет выполнено, если потребовать 1/ро,~ )2/в, т. е. п)л,(е) = (12) 1п (!/рд В наиболее неблагоприятном случае, когда отношение =Л ы (А)/Л „(А) мало, имеем 1п — =!и! + ~ ) =2 1/'$ (, 1 ~Гй/ и из (12) получим следующее приближенное выражение для числа итераций: (13) Таким образом, при малых $ явный итерационный метод с чебышевским набором параметров требует для достижения заданной точности е числа итераций л,Ц) =0(1/Д).
Именно в этом состоит его преимущество перед методом простой итерации, для которого согласно (!4) из э 4 имеем л,($) =0(1/$). 2. Численная устойчивость итерационного метода с чебышев. ским набором параметров. Как уже отмечалось в примере 2 нз п. 4 $5 оценка погрешности (5) остается одной и той же при различном упорядочении набора итерационных параметров (3). Теоретически эти параметры можно использовать в любом порядке.
Например, можно взять их в том порядке, как это указано в формуле (3). Можно использовать параметры в обратном порядке, т. е. положить ть = ' , й = 1,2, ..., а. ! + Ра~л-а+д Однако при практическом применении метода было обнаружено, что порядок выбора параметров существенно влияет на численную устойчивость метода. Оказалось, что использование параметров в произвольном порядке может привести к недопустимо сильному возрастанию вычислительных погрешностей. Дело в том, что рассматриваемый метод, вообще говоря, не гарантирует монотонного убывания погрешности от итерации к итерации.
Запишем уравнение для погрешности (7) в виде за+~= (Š— тг -~А)гь Норма оператора перехода Š— т,~,А данного итерационного метода может оказаться больше единицы для нескольких соседних итераций, что и приведет к возрастанию погрешности. Иногда вычислительная погрешность возрастает настолько сильно, что происходит переполнение арифметического устройства ЭВМ. Здесь можно провести аналогию с вычислением произведения нескольких чисел. Рассмотрим следующий пример. Пусть на некоторой ЭВМ машинным нулем является число М,=10-~, а машинной бесконечностью — число М =10', где р>0. Попытаемся вычислить на этой ЭВМ произведение пяти чисел 10~", 1Ом', 10-~", !О'м', 10-'"".
Это произведение равно 10м4 и принадлежит допустимому интервалу чисел (М„М ). Однако результат вычисления на ЭВЫ будет зависеть от того, в каком порядке перемножаются данные числа. При перемножении в порядке убывания ИГ"'.1О"' 10"' 10-"* 10 "" уже выполнение первого умножения приводит к переполнению, так ия как 1О''п)М„. После этого вычисления прекращаются, и мы просто не сможем вычислить все произведение. При перемножении в порядке возрастания 1О-зрм. 1О-мз 1Орм. 1Орп. 1Оври после первого умножения получаем число 1О '"'(М„которое полагается равным нулю, следовательно, равным нулю оказывается и все произведение. Если же расположить сомножителя в таком порядке: 10 "410'п)ОЗ""10 "'10ха Ф то удается довести вычисления до конца и получить правильный результат. В настоящее время известен алгоритм построения такого упорядоченного набора итерационных параметров (3), для которого итерационный метод (2) является устойчивым.
Подробное изложение этого алгоритма можно найти в 1321г 3. Неявный чебышевский итерационный метод. Скорость схо. димости явного метода (2), (3) зависит, как мы видели, от отношения ф=Л 1 (А)/Л (А) минимального собственного числа матрицы А к максимальному: чем больше ф, тем выше скорость сходи- мости. Рассмотрим теперь неявный итерационный метод В ~" ~ +Ахь=/, /г= О, 1, ..., х, задан, (14) чь+1 с симметричной положительно определенной матрицей В и переменными параметрами т,~,. Как и в случае стационарных методов (см. $ 4), скорость сходимости метода (14) будет определяться уже не отношением собственных чисел матрицы А, а отношением 5=Л „(В 'А)/Л „(В 'А) минимального и максимального собственных чисел обобщенной задачи Ар=ЛВр.
(15) При соответствующем выборе матрицы В это отношение будет больше чем Л „(А)/Л „(А), а следовательно, итерационный метод (!4) будет сходиться быстрее, чем явный метод (2). Теория неявных итерационных методов легко сводится к теории явного метода. Для неявного чебышевского метода справедлива Теор ем а 2. Пусть А и  — сшиметричные положительно определенные матрицы, а Л,(В 'А), Л „(В 'А) — соответственно наименьшее и наибольшее собственные значения задачи (15). Пусть задано число итераций и. Метод (14) имеет минимальную погрешность !!х„— х1~„если параметрьч т, определить согласно (3), (4), где л ы(В ~л) Леах (и При этом справедлива оценка |~х„— хам!,(д„!!х,— х1~„ (16) пз еде у Л (В 'А) Доказательство.
Погрешность г,=х,— х удовлетворяет однородному уравнению В о" +Ага=О, я=О, 1, ..., го — — хо — х. (18) том Умножим уравнение (18) на матрицу В " и обозначим п,=В"гв. Тогда получим уравнение +Сов=О, А=О, 1, ..., по=ВИ(хо — х), (19) а+1 где С=В "*АВ "*. Уравнение (19) отличается только обозначениями от уравнения (7), которому удовлетворяет погрешность явного итерационного метода. Поэтому нам остается лишь проверить выполнение условий теоремы 1 по отношению к матрице С. Матрица С является симметричной и положительно определенной, причем ее спектр совпадает со спектром обобщенной задачи на собственные значения (15). В частности, Л „(В-'А) является минимальным собственным числом Л,„(С) матрицы С, а Л „(В 'А)— максимальным.
Следуя теореме 1, выберем параметры т, согласно (3), (4), где $=Л,„(С)Ф „(С). Тогда для решения уравнения (19) будет выполняться оценка !!и.!! ~4.!!и.!!. Подставляя сюда по=В"'г„, А=О, а, получим !!гв!!в~(о) !!го!!в, т. е. придем к требуемой оценке (16). Теорема 2 доказана. Замечание. Прн условиях теоремы 2 наряду с оценкой ((6) справедлнва н оценка !! х» — х1 в ( е в1хо — к!! в. для доказательства достаточно переписать уравнение (!8) в виде (!9), где ох=Авва, С=Аз В-'А'ь, н повторить рассужденяя теоремм 2. Так же как и в случае явного метода, численная устойчивость неявного итерационного метода зависит от способа упорядочения итерационных параметров.
Алгоритм построения устойчивого набора итерационных параметров тот же, что и для явного метода. 4. Случай, когда точные границы спектра неизвестны. В теоремах 1 и 2 фигурируют точные границы спектра матриц А и В-'А соответственно. Очень часто минимальные и максимальные собственные значения не известны точно, а известны лишь оценки для них. Например, если выполнены матричные неравенства Т,В<А<7,В (20) !14 с некоторыми константами 7,>7,>0, то можно утверждать, что Х ы(В-'А))7о )ь (В-'А)(7а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
