main (1160446), страница 4
Текст из файла (страница 4)
Но если разумно организовать вычисления, то можно найтикоординаты ( + 1)-й итерации по явным формулам.Рассмотрим метод Зейделя при = 1:1 −∑︀=2+1=11 ,11 ∈ Z+ .Видно, что +1находится по явной формуле. Рассмотрим вторую координату ( + 1)-й1итерации:∑︀−2 2 − 21 +11=3+1=222, ∈ Z+ .можно найти по явной формуле.известна, то координату +1Так как координата +121Продолжая вычисления, получим, что каждый элемент ( + 1)-й итерации можно найти по явным формулам от уже известных элементов. Заметим, что метод Зейделя проств реализации, но медленно сходится.Каноническая запись итерационных методовДля исследования сходимости итерационных методов удобно записывать их в матричномвиде. Представим матрицу в виде = 1 + + 2 ,где 1 — нижнетреугольная матрица с нулевой главной диагональю, — диагональнаяматрица, 2 — верхнетреугольная матрица с нулевой главной диагональю:⎛⎞⎛⎞⎛⎞0 12 · · · 100 ··· 011 0 · · ·0⎜ 21⎜ 0 22 · · ·⎜0 0 · · · 2 ⎟0 · · · 0⎟0 ⎟⎜⎟⎜⎟⎜⎟1 = ⎜ .,=,=⎟⎜⎟⎜ ...........
⎟ .2.. .⎠.......... ⎠⎝ ..⎝ ..⎝.. ..... ⎠1 2 · · · 000· · · 00···0Перепишем матричное уравнение (1) в виде(1 + + 2 ) = .Оставим в левой части слагаемое с матрицей , остальные слагаемые перенесем в правуючасть уравнения: = − 1 − 2 .Предположим, что матрица обратима ( ̸= 0, = 1, ). Тогда получим: = −1 − −1 1 − −1 2 .(3)20Запишем итерационные методы Якоби и Зейделя исходя из уравнения (3):Метод Якоби :Метод Зейделя :+1 = −1 − −1 1 − −1 2 , ∈ Z+ ,+1 = −1 − −1 1 +1 − −1 2 , ∈ Z+ .Рассмотрим эти два метода записав их в виде:Метод Якоби :+1 + (1 + 2 ) = , ∈ Z+ ,Метод Зейделя :( + 1 )+1 + 2 = , ∈ Z+ .Наконец, перепишем эти соотношения в видеМетод Якоби :Метод Зейделя : ∈ Z+ ,(4)− ) + = , ∈ Z+ .(5)(+1 − ) + = ,( + 1 )(+1Из формул (4) и (5) видно, что если в каждом из методов последовательность итерацийсходится, то она сходится к решению системы (1).Мы видим, что один и тот же итерационный метод можно записать различными способами.
Поэтому целесообразно ввести какую-то стандартную (каноническую) форму записиитерационных методов.Канонической формой записи двухслойного итерационного метода решения системы (1) называется его запись в видеОпределение.+1+1 − + = ,+1(6)где ∈ Z+ , начальное приближение 0 задано, +1 — положительное вещественное число, называемое итерационным параметром, +1 — некоторая обратимая матрица.Определение. Если в методе (6) параметр +1 и матрица +1 не зависят от номераитерации (+1 = , +1 = ), то такой метод называется стационарным, в противном случае — нестационарным.Определение.неявным.Если +1 = , то метод (6) называется явным, в противном случае —При рассмотрении итерационных методов обычно исследуют условия, при которых данный метод сходится, и оценивают скорость сходимости метода.Рассмотрим далее еще несколько примеров итерационных методов: метод простой итерации, метод Ричардсона и попеременно-треугольный итерационный метод.
В этих методахвведение параметров и позволяет увеличить скорость сходимости по сравнению с методами Якоби и Зейделя.Метод простой итерацииМетод простой итерации (метод релаксации) определяется итерационной схемой вида+1 − + = , > 0, ∈ Z+ , 0 — задано.(7)§5. Примеры и канонический вид итерационных методов решения СЛАУ21Метод РичардсонаМетод Ричардсона определяется итерационной схемой вида+1 − + = , +1 > 0, ∈ Z+ , 0 — задано.+1(8)Замечание. Для итерационных методов (7) и (8) в случае, когда матрица являетсясимметричной и положительно определенной, известен такой набор итерационных параметров (Чебышевский набор), при котором сходимость этих методов будет наиболеебыстрая.Попеременно-треугольный итерационный методПредставим матрицу в виде = 1 + 2 ,где 1 — нижнетреугольная⎛0.5110⎜ 210.522⎜1 = ⎜ ...⎝ ...12матрица, 2 — верхнетреугольная матрица:⎞⎛···00.51112···⎜ 0···0 ⎟0.5···22⎟⎜..
⎟ , 2 = ⎜ .........⎝ ... ⎠.· · · 0.50012...⎞⎟⎟⎟.⎠· · · 0.5Попеременно-треугольный метод имеет вид+1 − + = , ∈ Z+ ,(9)где > 0, > 0 — итерационные параметры, позволяющие, вообще говоря, ускорить процесс сходимости итерационного метода, матрица — единичная. Рассматриваемый методформально является неявным, однако можно показать, что ( + 1)-я итерация выражаетсяс помощью явных формул за три шага. Введем обозначения:( + 1 )( + 2 ) +1 = ( + 2 )+1 − ,+1 − .Вектор = − называется невязкой на -й итерации.
+1 =Определение.В нашем случае невязка известна. Предположим, что матрицы +1 и +2 имеютобратные. На первом шаге решим уравнение( + 1 ) +1 = .Заметим, что ( +1 ) — нижнетреугольная матрица. Нахождение вектора решения системы с нижнетреугольной матрицей осуществляется по явным формулам, начиная с первойкомпоненты вектора +1 . На втором шаге аналогично решим уравнение с верхнетреугольной матрицей ( + 2 ):( + 2 ) +1 = +1 .На третьем шаге найдем ( + 1)-ю итерацию по формуле+1 = + +1 .Таким образом, несмотря на то, что попеременно-треугольный итерационный метод является неявным, его реализация не представляет никакой трудности.22§6Теоремы о сходимости итерационных методовРассмотрим матричное уравнение вида(1) = ,где || ≠ 0, ( × ), = (1 , 2 , . .
. , ) , = (1 , 2 , . . . , ) .Рассмотрим также двухслойный стационарный метод решения уравнения (1):+1 − + = ,(2)где ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица порядка ( × ).Чтобы говорить о сходимости итерационного метода, необходимо ввести линейное пространство и определить в нем норму. Внимательный читатель может помнить из курсалинейной алгебры, что в конечномерном пространстве все нормы эквивалентны. То естьнайдутся такие константы, при помощи которых можно оценить одну норму через другую.Но при исследовании сходимости итерационных методов будем устремлять к нулю параметры этих методов, и если они будут участвовать в записях констант перехода от однойнормы к другой, то смысл таких оценок, вообще говоря, может сойти на нет. Поэтому всегда при рассмотрении сходимости итерационных методов будем указывать, в какой именнонорме производится исследование.Пусть — линейное вещественное пространство размерности :dim = .Рассмотрим два произвольных вектора и из этого пространства: ∈ , = (1 , 2 , .
. . , ) , ∈ , = (1 , 2 , . . . , ) .Определим скалярное произведение двух векторов, заданных в ортонормированном базисепространства :∑︁(, ) = .=1Введем евклидову норму:√︀‖‖ = (, ) =(︃ ∑︁)︃ 122.=1Эту норму также часто называют среднеквадратичной нормой.Далее будем считать, что понятия линейный оператор и матрица эквивалентны. Рассмотрим самосопряженный положительный линейный оператор = * > 0.Линейный оператор называется положительным (неотрицательным),если (, ) > 0 ∀ ∈ , ̸= (соответственно (, ) > 0 ∀ ∈ ). Положительностьоператора обозначается как > 0.Определение.В дальнейшем понятия положительный оператор и положительно определенный линейный оператор считаются тождественными.§6. Теоремы о сходимости итерационных методов23Скалярным произведением в смысле оператора называется скалярноепроизведение, определяемое соотношениемОпределение.(, ) = (, ).Энергетической нормой, порождаемой линейным самосопряженным положительно определенным оператором , называется норма, задаваемая соотношением√︀√︀‖‖ = (, ) = (, ).Определение.Задача.Пусть = * > 0.
Доказать, что ∃ > 0 : (, ) > (, ) = ‖‖2 .Рассмотрим свойства положительного самосопряженного линейного оператора.Если = * > 0, то определены(︁)︁*(︁ 1 )︁*(︁)︁111 *−1 = −1 > 0, 2 = 2 > 0, − 2 = − 2 > 0.Определение.векторОпределение.Погрешностью итерационного метода на -й итерации называется = − .(3)Итерационный метод сходится в норме ‖·‖, если ‖ ‖ → 0 при → ∞.Выразим из формулы (3) и подставим в уравнение (2).
Получим однородное уравнение: +1 − + = 0,(4)где ∈ Z+ , 0 = 0 − .Приступим к исследованию задачи (4). Выразим ( + 1)-ю итерацию через -ю с учетомтого, что для матрицы существует обратная. Домножим уравнение (4) на −1 слева: +1 − + −1 = 0.Выразим из уравнения погрешность на ( + 1)-й итерации: +1 = − −1 = ( − −1 ) = .Таким образом, мы получили матрицу , которая связывает погрешность на предыдущейитерации с погрешностью на следующей: = − −1 .(5)Матрица из равенства (5) называется матрицей перехода от -й итерации к ( + 1)-й.Определение.Итерационный метод (2) решения системы (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицыперехода по модулю меньше единицы.
(Без доказательства,доказательство см. [1], стр.92).Теорема 1.Таким образом, сходимость итерационного метода (2) всецело зависит от свойств матрицы S, а именно, от ее спектра.Заметим, что данная теорема практически неприменима, так как задача нахожденияполного спектра матрицы аналитически решается крайне редко.Приступим к рассмотрению вопроса сходимости итерационного метода. В дальнейшембудем считать, что линейное пространство задано над полем R вещественных чисел.24(теорема Самарского). Пусть — самосопряженный положительно определенный оператор, — положительное вещественное число и выполнено операторное неравенство − > 0.(6)2Теорема 2Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичнойнорме при любом начальном приближении:⎯⎸∑︁)︁2⎸ (︁ ‖ − ‖ = ⎷ − −→ 0,=1→∞∀0 .Пусть = −.
Введем числовую последовательность = ( , ).Покажем, что { } — невозрастающая и ограниченная снизу последовательность. Для этогорассмотрим +1 :Доказательство.+1 = ( +1 , +1 ) = ( , ) = (( − −1 ) , ( − −1 ) ).(7)Воспользуемся линейностью скалярного произведения и преобразуем правую часть равенства:( , ) − ( , −1 ) − ( −1 , ) + 2 ( −1 , −1 ).(8)В силу того, что оператор — самосопряженный ( = * ), получим(︀)︀ (︀)︀ (︀)︀ −1 , = −1 , * = , −1 .Преобразуем выражение (8): − 2 ( , −1 ) + 2 ( −1 , −1 ) = − 2(︁(︁)︁ )︁ − −1 , −1 .2Подставив полученное выражение в равенство (7), получим тождество(︁(︁+1 − )︁ −1 −1 )︁(9)+ 2 − , = 0,2(︀)︀в котором оператор − 2 положителен по условию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
