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