Ильин, Позняк - Линейная алгебра (947283), страница 37
Текст из файла (страница 37)
Это приводит нас к следующим двум условиям, каждое из которых является достаточным для сходимости модифицированного метода простой итерации л ~~)~~~а>1 ~(! (дЛя 1=1> 2, ...> и); /1 !м> л ~ — ы~(1 (для 1=1, 2, ..., и). 1 >м> ') См., например, книгу: В.
И. Крылов, В. В. Бобков нП. И. Монастырный. Вычислительные методы высшей математнкн, том 1. — Минск: Вышайшан школа, 1972> с. 111 — 112. !гл. е итарлциоиныя методы !74 4. Метод Зейделя. Представим симметричную матрицу (6,2) в виде суммы трех матриц А = Р + 7. + О, где Р— диагональная матрица (6.23), а 1 и У соответственно строго левая и строго правая матрицы, имеющие вид О еаа ... ваа О О ... а се О О ...
О аи О ... О У= в., 'аее ... О ') Достаточно заметить, чго если у векюра Х Ф-я коорляната равна единице, а все остальные нулю, то (АХ, Х) = ньа > О. и удовлетворяющие условию Е' = К Метод Зейделя получается из общего неявного метода простой итерации в том частном случае, когда стационарный параметр т равен единице, а матрица В равна сумме Р + 7.. Таким образом, последовательные итерации в методе Зейделя определяются соотношением (Р + Е) (Х„+, — Х„) + АХь = Е.
Докажем, что метод Зейделя сходится для любой симметричной и положительно определенной матрицы А. В силу теоремы 6.2 достаточно доказать, что для любой такой матрицы А выполнено условие 2(Р+7.) >А. (6.27) Для доказательства (6.27) заметим, что для любого вектора Х (2 (Р + Е) Х, Х) = (РХ, Х) + (РХ, Х) + (ЕХ, Х) +((.Х, Х) = =(РХ, Х)+ (РХ, Х)+ (ВХ, Х)+ (Х, УХ) = = (РХ, Х) + (АХ, Х). Таким образом, для доказательства неравенства (6.27) достаточно убедиться в положительной определенности матрицы Р, но она сразу вытекает из того, что у положительно определенной и симметричной матрицы А все элементы, лежащие на главной диагонали, являются положительными '). Сходимость метода Зейделя доказана.
5. Метод верхней релаксации. Этот метод получается из общего неявного метода простой итерации в том частном случае, когда ч = се, В = Р + юС, а параметр се выбран так, чтобы являлось наименьшим наибольшее по модулю собственное значение матрицы Š— ю(Р + ыЕ) ' А, осуществляющей переход от й-й итерации к (й+ !)-й.
Докажем, что если матрица А является симметричной и положительно определенной, то для сходимости метода верхней релаксации достаточно, чтобы было выполнено условие О < се < 2. В силу теоремы 6.2 для сходимости достаточно выполнение условий в > О, 2 (Р + св~) > юА. 1 |1 ИТЕРАЦИОННЪ|Е МЕТОДЫ РЕШЕНИЯ ЛИНЕЯНЪ|Х СИСТЕМ 175 (6.13) а более общим соотношением В вм ь + АХ» —— г". тьы При этом, как и выше,  — некоторая легко обратимая квадратная матрица порядка и. При таком выборе итерационной последовательности для погрешности ЕА = ХА — Х итерационной схемы получится соотношение В х~+ л + АР О тем (6.15*) ') Пафвутка Львович Чебмшев (1821 — 1894) — великий Русский мвтемвткк к механик.
Второе из этих условий для любого вектора Х приводит к неравенству (2 ()О + о|В) Х, Х) > (ШАХ, Х). (6.28) Последнее неравенство эквивалентно каждому из неравенств в следующей цепочке: (АХ, Х) + (ш(,Х, Х) + (ш(Х, Х) > (шАХ, Х), (2 — о|) (ВХ, Х) + (ш)ОХ, Х) + ( ш1.Х, Х) + + (Х, ШАХ) > (шАХ, Х), (2 — о|) (ВХ, Х) > О. Из последнего неравенства и из положительной определенностиО заключаем, что (6.28) справедливо при 2 — ш > О, т. е.
прн ш < 2. Итак, доказано, что условия О < |о < 2 обеспечивают сходимость метода верхней релаксации. 6. Случай несимметричной матрицы А. В случае несимметричной матрицы А мы можем умножить матричное уравнение (6.1) слева на матрицу А' и заменить уравнение (6,1) уравнением АХ = Р, в котором г" = А'Р, А = А'А, так что матрица А является симметричной и (как легко убедиться) положительно определенной. 7.
Итерационный метод П. Л. Чебышева «). Всюду выше при рассмотрении Общего неявного метода простой итерации мы предполагали, что итерационный параметр т принимает одно и то же постоянное значение. Естественно возникает идея рассмотреть более общий случай, когда в указанном методе значения итерационного параметра зависят от номера й итерации. В таком случае последовательность итераций будет определяться не соот- ношением ггл. е итвэхциоиныв мвтоды 176 Предположим, что обе матрицы А и В симметричны и поло- жительно определенны. Тогда, как уже отмечалось выше, най- дутся положительные постоянные у, и у, такие, что у,В ~ А ~у,В.
Будем считать, что эти постоянные у, и у, нам заданы и еще раз напомним, что эти постоянные равны соответственно наимень- шему и наибольшему собственным значениям задачи АХ = »ВХ. Оценим энергетическую норму погрешности «Е»«э. Напомним еще раз, что для симметричной и положительно определенной матрицы В существует симметричная и положительно определенная матрица Виэ такая, что Ви'Ви' = В. Как и выше, договоримся обозначать символом В-и' матрицу, обратную к мат- рице Ви'.
Для оценки нормы погрешности Е» сделаем замену, положив Е» В-и'У». При такой замене соотношение для погрешно- сти У» переходит в следующее соотношение для У». Ур„,— — (Š— ту„»С) У» (й=О, 1, 2, ...), где через С обозначена матрица вида С = В-и' А В-и'. Убе- димся в том, что квадрат обычной нормы вектора У„ равен квад- рату энергетической нормы вектора Е». В самом деле, «У, «э=(У, У ) =(В~"л, В~~'2) =(ВЯ, 2 ) =«Е «э.
Таким образом, для оценки энергетической нормы 2» достаточно оценить обычную норму У». Оценим норму «У, «. Прежде всего заметим, что из неравенств у, (ВХ, Х) ~ (АХ, Х) < у, (ВХ, Х) с помощью замены Х = = В-и' У получаются неравенства у, (У, У) ~ (СУ, У) ~ ~ у, (У, У). Последние неравенства эквивалентны тому, что у,Е ~ С ~ у,Е. Поскольку кроме того матрица С = = В-и'А В-и' симметрична, то все собственные значения этой матрицы вещественны и расположены на отрезке (7„7,1. После- довательно записывая соотношение У»+, — — (Š— т„+, С) У„для номеров й = О, 1, ..., мы придем к следующему равенству: У„= П (Š— ч,С) ° У„ с ! из которого сразу же вытекает, что «)У»« ~ П(Š— ч,С) .«У,«. Но тогда нз равенства «У„« =«Е»«в вытекает, что «Я»~ ~ д» «2,«в, где д» = ~П (Š— ч7С) .
Следовательно, итера1ю=! циониый процесс сходится при условии, что последовательность «д»«стремится к нулю, причем тем быстрее, чем меньше вели- чины д». а!1 итяя»ционнын мнтоды яашения линвяных систям 1тт Поскольку каждое значение о» является функцией параметров т„т„..., т», возникает задача построения оптимального набора итерационных параметров нз условия минимума о» для фиксированного А. Перейдем к решению этой задачи. Предположим, что все собственные значения Х, матрицы С лежат на заданном сегменте [у„у,[.
Учитывая симметрию матрицы С, мы приходим к следующей задаче оптимизации: найти пип !!»(т„т„..., т») = пни П(Š— т,С) = ( 1! (!!! У=! = ппп ~шах ~ П (1 — т;),) . (тг! ! ~ ~ 1=! Поскольку все», лежат на отрезке [у,, у,), то расширяя область по которой берется максимум, мы получим, что ш!и р» (т„т,, ..., т„) ~ пйп ~ шах ~ П (1 — т1!) ("1! [ч.) !у,КС<т 1! ! Полученная огрубленная задача имеет более простое решение. Кроме того, при решении такой задачи ие используется информация о конкретном расположении собственных значений )!, на отрезке [у„у,), а учитываются лишь границы этого отрезка. Такой подход позволяет построить набор оптимальных параметров для матриц произвольной структуры.
Перейдем к решению указанной огрубленной задачи оптимизации, Положим Р (!) = П (1 — т1!) и заметим, что полипом Р (!) у=! удовлетворяет условию нормировки Р (0) = 1. С помощью замены переменной 2 Уз+У! Уа У!)) 2 ! т+т / т 1 т!+т~ ! тэ — 7!» 1 — Яр! т+ъl та где р, = —, т, —, мы отобразим отрезок у, ~ ! ~ у, тя — 7! 2 !!+7~ т!+ 7! в отрезок — 1 ~ 8 ~ 1, причем точка ! = 0 переходит в точку ~0 ) 1 оо При такой замене рассматриваемая задача оптимизации переходит в следующую задачу: среди всех полиномов Р» (5) степени й, с удовлетворяющих условию нормировки Р» !» — ~ = 1, найти таРо кой, для которого шах !Р (5) [ минимален.
15!к! !гл. е нтв хционныи мвтоды 17В Таким полиномом, как известно, является полипом Чебышева Р» (5) = Та (5) (Т» (5а) ) ', где соз(йагссоэ5) при 15~ ~1, —,,' И5+ 5-1)'+(5- '5 — )") при ~5~»1. Так как и!ах *)Т» (5)~ = 1, то !5 !а,! нпп шах (Р»(!)~= 1 (а!1 т,чача. т»(5,) ' 1 2Р! причем, =!7»= — !, где р, 7'а (5а) ! -1- Ра!а Для вычисления оптимального исходить из равенства Ута — У т Ута+ Ут набора параметров будем РА (!) П (1 т/!) а)»ТА ( Р ) 7=! 12»Ь ~ й»12»Ь, 2Р! Уъ — У1. гдв д» вЂ” — —, при р,= .
Рг» Р та+Рта ( 1 — та!» мы учли, что 5 = — ~. Приравняем корни полииомов, Ра стоящих в левой и в правой частях этого равенства. Так как полипом Р» (!) имеет корни 1, = 1/т! (!' = 1, 2, ..., й), а полипом 2! — 1 Т» (5) имеет корни 51 = соз — и (1 = 1, 2, ..., я), то учи- 1 — Ра5 1 — 5аРа тывая, что 7 = —, получим (/=1,2, ... та т) та я; 5! определены выше). Итак, оптимальными значениями итерационных параметров та 2! — ! будут значения т, = —, где 51 = соз — и, 1=1,2, ... ..., я. Итерационный процесс с указанным оптимальным набором параметров называется чебышевским.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
