Н.И. Ионкин - Электронные лекции (2010), страница 3

. ; = 1, . . . , - начальное приближение. Запишем метод Зейделя (МЗ):+1=0 = 1, . . . , :∑︀−1∑︀ − =1 − =+1 =+1=Вектор = ,=+1тогда можно выразитьОбозначим черезЗадан вектор∑︁−1∑︁∑︁ +1 − − , =1 =+1 = 0, 1, . . . ; = 1, . . . , ;также изначально задан.Представим матрицув виде: = 1 + + 2 ,где⎛⎞00 ··· 0⎜ 210 · · · 0⎟⎜⎟1 = ⎜ ....⎟....⎝ ....⎠1 2 · · · 0— нижнетреугольная матрица с нулями на главной диагонали,⎛⎞11 0 · · ·0⎜ 0 22 · · ·0 ⎟⎜⎟ = ⎜ .... ⎟.... ⎠⎝ ....00 · · · — диагональная матрица,⎛⎞0 12 · · · 1⎜0 0 · · · 2 ⎟⎜⎟2 = ⎜ .. .. . .. ⎟.

⎠⎝. ...0 0 ···0(3)Примеры и канонический вид итерационных методов решения СЛАУ15— верхнетреугольная матрица с нулями на главной диагонали. Очевидно, такое разложениевсегда осуществимо. Подставим предстваление (3) в (1):(1 + + 2 ) = = − 1 − 2 Предположим теперь, что∃−1 .Тогда: = −1 − −1 1 − −1 2 Метод Якоби можно записать следующим образом:+1 = −1 − −1 (1 + 2 )или(+1 − ) + = Метод Зейделя:+1 = −1 − −1 1 +1 − −1 2 или( + 1 )(+1 − ) + = Из приведенных записей видно, что итерационные методы можно записать в различном виде.Поэтому целесообразно иметь единую форму записи итерационного метода.Определение. Канонической формой записи двухслойного итерационного метода решенияСЛАУ (1) называется его запись в виде:+1+1 − + = ,+1 = 0, 1, . . .

; 0— задан(4)+1 > 0 - итерационный параметр,+1 - обратимая матрица.Если+1 = ,то метод (4) называется явным. Если+1 = , +1 = ,то метод (4)называется стационарным.Метод простой итерации (ПИ, или метод релаксации) имеет следующий вид:+1 − + = , >0Рассмотрим более подробно попеременно-треугольный итерационный метод (ПТИМ):( + 1 )( + 2 )Здесь+1 > 0, > 0+1 − + = ,+1— итерационные параметры,⎛0⎜ 21 22⎜21 = ⎜ ....⎝ ..1 2112 = 0, 1, . . .

; 01 + 2 = ,⎞···0···0 ⎟⎟. ⎟,... ⎠..· · · 2где— задан(5)Теоремы о сходимости итерационных методов⎛16⎞12 ⎟⎟. ⎟.. ⎠.12 · · ·22···2112⎜0⎜2 = ⎜ ..⎝ .0.....0···.2Реализация попеременно-треугольного итерационного метода может быть осуществлена по явнымформулам. Пусть: +1 =+1 − +1+1 = ( + 2 ) +1 = − Тогда:( + 1 )+1 = ,где( + 1 )—нижнетреугольная матрица,Из этого уравнения, путем обращения нижнетреугольной матрицы по явным формулам выписывается+1вектор .( + 2 ) +1 = +1 ,где( + 2 )—верхнетреугольная матрица,+1По известному вектору , обращая верхнетреугольную матрицу по явным формулам можно+1найти вектор , и далее:+1 = + +1 +1 .Таким образом, несмотря на то, что ПТИМ - неявный итерационный метод, его реализацияпроста и сводится к попеременному обращению нежнетреугольной и верхнетреугольной матриц(отсюда- название метода).§6Теоремы о сходимости итерационных методовРассмотрим матричное уравнение вида = ,где— матрица размера(1)( × ), || ≠ 0Рассмотрим также матричное уравнение вида+1 − + = ,где = 0, 1, 2, .

. . , ∃ −1 ,и задан вектор начального приближенияРассмотрим линейное пространство H, такое чтоdim = Возьмем 2 произвольных вектора x и y из этого пространства: ∈ , = (1 , 2 , . . . , ) ∈ , = (1 , 2 , . . . , )Введем скалярное произведение векторов(, )(, ) =∑︁=1по формуле: (2)0Теоремы о сходимости итерационных методов17Введем норму вектора x:1|||| = (, ) 2Замечание. Есть “слабые нормы”, которые обладают не поточечной близостью. Решениясистем стараются брать в сильной норме, входные данные - в слабой, чтобы максимальнорасширить область применения метода.Рассмотрим самосопряженный оператор = * > 0Определение. Будем говорить о скалярном произведении векторов x и y “в смысле D”, если(, ) = (, )Это позволяет нам ввести энергетическеую норму:Определение.

Энергетическая норма - норма, которая задается соотношением:1|||| = (, ) 2Вспомним некоторые свойства самосопряженного положительно определенного оператораD, известные из теории операторов:1.∃−1 = (−1 )* > 02.∃ 2 = ( 2 )* > 03.∃− 2 = (− 2 )* > 01111из этих свойств следует, что существует такое>0:(, ) ≥ ||||2В дальнейшем нам потребуется понятие положительной или неотрицательной определенностиоператора.Определение.

> 0 ⇔ (, ) > 0,∀ ̸= 0 ≥ 0 ⇔ (, ) ≥ 0,∀ ∈ Задача. Дано: Оператор > 0, - вещественное линейное пространство с заданным скалярнымпроизведением. Доказать, что:(, ) = ( + *, )2Доказательство. Для решения задачи воспользуемся следующими равенстввами, верными длявещественного простаранства:( * , ) = (, ) = (, ),Представим операторв виде суммы:=+ *2+∀ ∈ − *. Тогда:2 + * − *, ) + (, ) =22)︁1 (︁ * + * + *(, ) +( , ) − (, ) = (, ),⏞22 ⏟2(, ) = (=0∀ ∈ Теоремы о сходимости итерационных методов18Определение.

Погрешность итерационного метода = − Определение. Метод(3)(2) сходится, если|| || → 0( → ∞)Из определения погрешности ясно, что решению матричного уравнения (2) на n-ой итерациисоответствует вектор = + ,где– точное решение системы.Используя это соотношение, перепишем уравнение (2) через вектор погрешности:где +1 − + = 0,(4) = 0, 1, 2, .

. .Умножим уравнение (4) на −1слева: +1 − + −1 = 0Следовательно, +1 = − −1 = ( − −1 ) = Таким образом, получим матрицу S: = − −1 (5)Определение. S называется матрицей перехода от n-й итерации к (n+1)-йТеорема 1(о сходимости итерационных методов). Итерационный метод (2) решения задачи(1) сходится при любом начальном приближении тогда и только тогда, когда все собственныезначения матрицыпо модулю меньше единицы.Замечание. Эта теорема хороша, но редко применима, т.к.

в большинстве случаев искатьсобственные значения трудно.Замечание. Далее всюду будем рассматривать только вещественные простарнства.Теорема 2(Самарского). Пусть оператор = * > 0 (* = )Пусть выполнено неравенство − 0, 5 > 0, ( > 0)(6)Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичной нормепри любом начальном приближении, то есть|| − || =(︃ ∑︁=1)︃ 21( − )→ 0, → ∞Теоремы о сходимости итерационных методов = ( , )Доказательство. ВведемРассмотрим19+1 :+1 = ( +1 , +1 ) = ( , ) == (( − −1 ) , ( − −1 ) ) = (( − −1 ) , ( − −1 ) ) =[︀]︀= ( , ) − ( −1 , ) + ( , −1 ) − ( −1 , −1 ) =если учесть, что{( −1 , ) = ( −1 , * ) = ( , −1 )},получим[︀]︀= − 2( , −1 ) − ( −1 , −1 ) =(︁)︁= + 2 ( − ) −1 , −1 2⎛⎞+1−+ 2 ⎝( − 0, 5 ) −1 , −1 ⎠ = 0⏟⏞Итак:>0 по условиюСледовательно, и все скалярное произведение больше либо равно нулю.

А стало быть, +1 ≤ ,и последовательность{ }не возрастает и имеет предел.Воспользуемся свойством положительно определенного оператора: если оператор C >0, то2∃ > 0 : (, ) ≥ |||| , ∀ ∈ Из этого свойства следует неравенство:(︀)︀( − 0, 5 ) −1 , −1 ≥ || −1 ||2 ,>0где +1 − + 2|| −1 ||2 ≤ 0При→∞получимlim || −1 || = 0→∞Введем = −1 .Отсюда = −1 Оценим норму погрешности:|| || ≤ ||−1 || * || ||В силу независимости−1 от n и стремлению к нулю нормы|| ||при→∞получим,чтоlim || || = 0→∞Так как мы нигде не использовали начальное приближение0остается верной для любого начального приближения 0 ,то формулировка теоремыТеоремы о сходимости итерационных методов20Cледствие.

Пусть = * > 0. (Напомним, что = 1 ++2 , где 1 и 2 - нижнетреугльнаяи верхнетреугольная матрицы, а = (11 , 22 , . . . , ))Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении0 ,если2 > .Доказательство.(+1 − ) + = =1условию: 2 > ⇒ − 0, 5 > 0 ⇒т.е. B=D,Повыполнено условие теоремы, а значит методсходится.Cледствие. Пусть = * > 0∑︁ >| |, = 1, (7)=1,̸=Тогда метод Якоби сходится при любом начальном приближении0Доказательство.

Возьмем произвольный вектор x, и распишем для него скалярное произведение22(, ), используя известное неравенство ≤ +:2(, ) =∑︁ ≤,=1∑︁| | * | | * | | ≤,=11 ∑︁1 ∑︁| |2 +| |2 =2 ,=12 ,=11 ∑︁1 ∑︁2| | +| |2 ==2 ,=12 ,=1= { = } =∑︁| |2=,=1∑︁2 (+=1∑︁| |)=1,̸=Воспользуемся свойством диагонального преобладания (7)(, ) < 2∑︁ 2 = (2, ) ⇒ 2 > =1а значит, по следствию 1 метод Якоби сходится при любомCледствие. Пусть0 = * > 0Тогда метод Зейделя сходится при любом начальном приближении0Теоремы о сходимости итерационных методов21Доказательство. По определению метода Зейделя имеем: = 1 + , = 1Для доказательства утверждения, в силу теоремы Самарского, достаточно доказать, что − 0, 5 > 0Поскольку = 1 + + 2 ,то это соотношение преобразуется к следующему виду:2(1 + ) > 1 + + 21 + − 2 > 0Следовательно,((1 + − 2 ), ) > 0, ∀ ̸= 0, ∈ (1 , ) + (, ) − (2 , ) > 0 ⇒ (, ) > 0Последнее следствие верно, так как = * ,а значит1* = 2(1 , ) = (, 1* ) = (, 2 ) = (2 , )Стало быть, для любого ненулевого вектора из требуется выполнения неравенства (, ) >0.

В силу самосопряженности оператора это соотношение выполняется, кроме того, все вышепривиденныепереходы равносильны, а значит выполнено условие теоремы Самарского.Cледствие. Пусть = > 0,2 = max ,20< < .2Тогда метод простой итерации (релаксации) сходится.Доказательство. В нашем случае,=. Докажем, что − 0.5 > 0,тогда утверждение будет следовать из теоремы Самарского. Запишем цепочку неравенств:<2,20, 5 2 < 1,что означает, что для любого– собственного значения матрицы0, 5 < 1,1 − 0, 5 > 0,то есть − 0.5 > 0.– выполненоОценка скорости сходимости итерационных методов§722Оценка скорости сходимости итерационных методовРассмотрим СЛАУ = ,где– матрица размера × ,(1)|| ≠ 0.Запишем общий вид итерационного метода решения СЛАУ:где − обратимаяматрица,+1 − + = ,0 > 0,- задано,(2) = 0, 1, .

. .Введем обозначение: = − .Тогда дляможно записать: +1 − + = 0(3)Для оценки скорости сходимости итерационных методов мы будем стремиться для некоторогои некоторой нормы доказать т.н.- оценку:‖ +1 ‖ ≤ ‖ ‖,0 < < 1.(4)Тогда‖ ‖ ≤ ‖ 0 ‖, → ∞ ⇒ ‖ ‖ → 0.Пусть– линейное пространство размерности(, ) =∑︁. ∀, ∈ определим: ,=1‖‖ =Пусть = * > 0.√︀(, ).Определим:(, ) = (, ),√︀‖‖ = (, )Найдем число итераций0 (),– энергетическая норма векторанеобходимое для того, чтобы‖ − ‖ < ‖0 − ‖.Из (4) следует, что‖ − ‖ ≤ ‖0 − ‖.Потребуем, чтобы ≤ .Тогда1≤ ln(︂ )︂1,11≥ ln ,∀ > 0 ()выполнялось:Оценка скорости сходимости итерационных методов23⎤ln 1⎦.0 () = ⎣ln 1⎡ln 1 называется скоростью сходимости итерационного метода.*Пусть = > 0.

Тогда ∃{ } – ортонормированный базис (ОНБ) из собственных векторов. Разложим вектор по этому базису:Число=∑︁ .=1Для вектораимеет место равенство Парсеваля:2‖‖ =∑︁2 .=1Теорема. Пусть * = > 0, * = > 0,∃ : 0 < < 1,1+1−≤≤.(5)Тогда итерационный метод (2) сходится к решению (1) и выполнена оценка‖ +1 ‖ ≤ ‖ ‖ .Замечание.