Н.И. Ионкин - Численные методы, страница 4

Кроме этого необходимо операций извлечения квадратного корня. Заметим, что метод справедлив только вслучае, если матрица системы линейных уравнений эрмитова.§5Примеры и канонический вид итерационных методов решения СЛАУРассмотрим матричное уравнение(1) = ,где || ≠ 0, ( × ), = (1 , 2 , . . .

, ) , = (1 , 2 , . . . , ) .Распишем систему (1) покоординатно:∑︁ = ,(2) = 1, .=1Выделим -ое слагаемое в сумме:−1∑︁=1 + +∑︁=+1 = , = 1, .§5. Примеры и канонический вид итерационных методов решения СЛАУ25Предположим, что элементы главной диагонали матрицы отличны от нуля: ̸= 0, = 1, .

Тогда уравнение (2) разрешимо относительно : −−1∑︀ =+1=1 =∑︀ −, = 1, .Все итерационные методы основаны на построении последовательностивекторов = (1 , . . . , ) такой, что → при → ∞, где — точноерешение матричного уравнения (1). Вектор называется -й итерациейметода.Отметим, что при выборе итерационного метода важно, чтобы метод быллегко реализуем и сходился к решению достаточно быстро.Итерационный метод называется двухслойным, если длявычисления текущей итерации используются только элементы предыдущей итерации.Определение.Замечание.говым.Двухслойный итерационный метод также называют одноша-Для того, чтобы начать процесс построения последовательности , необходимо задать начальное приближение 0 .

Далее будем предполагать, чтоначальное приближение уже задано.Рассмотрим в качестве примера два простейших двухслойных итерационных метода: метод Якоби и метод Зейделя.Метод ЯкобиМетод Якоби является явным итерационным методом и задается правилом −+1=−1∑︀=1 −∑︀=+1 , = 1, , ∈ Z+ .Забегая вперед, заметим, что метод Якоби является легко реализуемым, нопри этом медленно сходящимся, особенно при больших .26Глава I . Численные методы линейной алгебрыМетод ЗейделяМетод Зейделя, в отличие от метода Якоби, является неявным итерационнымметодом и задается уравнением −+1=−1∑︀=1 +1−∑︀=+1 = 1, , ∈ Z+ .,В правой части уравнения используются координаты ( + 1)-й итерации, поэтому метод Зейделя является неявным. Но если разумно организовать вычисления, то можно найти координаты ( + 1)-й итерации по явным формулам.Рассмотрим метод Зейделя при = 1:1 −=+11∑︀=21 ,11 ∈ Z+ .находится по явной формуле.

Рассмотрим вторую коордиВидно, что +11нату ( + 1)-й итерации:2 − 21 +1−1=+12∑︀=32 22, ∈ Z+ .Так как координата +1известна, то координату +1можно найти по явной12формуле. Продолжая вычисления, получим, что каждый элемент ( + 1)-йитерации можно найти по явным формулам от уже известных элементов.Заметим, что метод Зейделя прост в реализации, но медленно сходится.Каноническая запись итерационных методовДля исследования сходимости итерационных методов удобно записывать ихв матричном виде.

Представим матрицу в виде = 1 + + 2 ,где 1 — нижнетреугольная матрица с нулевой главной диагональю, — диагональная матрица, 2 — верхнетреугольная матрица с нулевой главной диагональю:§5. Примеры и канонический вид итерационных методов решения СЛАУ⎛0⎜⎜ 21⎜1 = ⎜ .⎜ ..⎝10···0···.....2···.⎞⎛110⎟⎜⎜ 00⎟⎟⎜, =⎜ ... ⎟⎟⎜ ...⎠⎝000···22···.....0···⎞27⎛0⎟⎜⎜00 ⎟⎟⎜, 2 = ⎜ ... ⎟⎟⎜ ... ⎠⎝00.⎞12···10···⎟2 ⎟⎟... ⎟. ⎟⎠0.....0···.Перепишем матричное уравнение (1) в виде(1 + + 2 ) = .Оставим в левой части слагаемое с матрицей , остальные слагаемые перенесем в правую часть уравнения: = − 1 − 2 .Предположим, что матрица обратима ( ̸= 0, = 1, ).

Тогда получим: = −1 − −1 1 − −1 2 .(3)Запишем итерационные методы Якоби и Зейделя исходя из уравнения (3):Метод Якоби :Метод Зейделя :+1 = −1 − −1 1 − −1 2 ,+1=−1 −−1+11 −−1 ∈ Z+ ,2 , ∈ Z+ .Рассмотрим эти два метода записав их в виде:Метод Якоби :+1 + (1 + 2 ) = , ∈ Z+ ,Метод Зейделя :( + 1 )+1 + 2 = , ∈ Z+ .Наконец, перепишем эти соотношения в видеМетод Якоби :Метод Зейделя : ∈ Z+ ,(4)− ) + = , ∈ Z+ .(5)(+1 − ) + = ,( + 1 )(+1Из формул (4) и (5) видно, что если в каждом из методов последовательностьитераций сходится, то она сходится к решению системы (1).Мы видим, что один и тот же итерационный метод можно записать различными способами. Поэтому целесообразно ввести какую-то стандартную(каноническую) форму записи итерационных методов.28Глава I .

Численные методы линейной алгебрыКанонической формой записи двухслойного итерационногометода решения системы (1) называется его запись в видеОпределение.+1+1 − + = ,+1(6)где ∈ Z+ , начальное приближение 0 задано, +1 — положительное вещественное число, называемое итерационным параметром, +1 — некотораяобратимая матрица.Если в методе (6) параметр +1 и матрица +1 не зависят от номера итерации (+1 = , +1 = ), то такой метод называется стационарным, в противном случае — нестационарным.Определение.Если +1 = , то метод (6) называется явным, в противном случае — неявным.Определение.При рассмотрении итерационных методов обычно исследуют условия, прикоторых данный метод сходится, и оценивают скорость сходимости метода.Рассмотрим далее еще несколько примеров итерационных методов: методпростой итерации, метод Ричардсона и попеременно-треугольный итерационный метод. В этих методах введение параметров и позволяет увеличитьскорость сходимости по сравнению с методами Якоби и Зейделя.Метод простой итерацииМетод простой итерации (метод релаксации) определяется итерационной схемой вида+1 − + = , > 0, ∈ Z+ , 0 — задано.(7)Метод РичардсонаМетод Ричардсона определяется итерационной схемой вида+1 − + = , +1 > 0, ∈ Z+ , 0 — задано.+1(8)Для итерационных методов (7) и (8) в случае, когда матрица является симметричной и положительно определенной, известен такойнабор итерационных параметров (Чебышевский набор), при котором сходимость этих методов будет наиболее быстрая.Замечание.§5.

Примеры и канонический вид итерационных методов решения СЛАУ29Попеременно-треугольный итерационный методПредставим матрицу в виде = 1 + 2 ,где 1 — нижнетреугольная матрица, 2 — верхнетреугольная матрица:⎛⎞⎛⎞0.51112···10.5110···0⎜ 0⎜ 210.522 · · ·2 ⎟0.522 · · ·0 ⎟⎜⎟⎜⎟1 = ⎜ .,=⎜⎟...... ⎟ .....2....⎝⎠⎝ ....... ⎠..00· · · 0.512 · · · 0.5Попеременно-треугольный метод имеет вид+1 − + = , ∈ Z+ ,(9)где > 0, > 0 — итерационные параметры, позволяющие, вообще говоря,ускорить процесс сходимости итерационного метода, матрица — единичная.Рассматриваемый метод формально является неявным, однако можно показать, что ( + 1)-я итерация выражается с помощью явных формул за тришага.

Введем обозначения:( + 1 )( + 2 )+1 − ,+1 − +1 =.Вектор = − называется невязкой на -й итерации. +1 = ( + 2 )Определение.В нашем случае невязка известна. Предположим, что матрицы + 1 и + 2 имеют обратные. На первом шаге решим уравнение( + 1 ) +1 = .Заметим, что ( + 1 ) — нижнетреугольная матрица. Нахождение векторарешения системы с нижнетреугольной матрицей осуществляется по явнымформулам, начиная с первой компоненты вектора +1 .

На втором шагеаналогично решим уравнение с верхнетреугольной матрицей ( + 2 ):( + 2 ) +1 = +1 .На третьем шаге найдем ( + 1)-ю итерацию по формуле+1 = + +1 .Таким образом, несмотря на то, что попеременно-треугольный итерационныйметод является неявным, его реализация не представляет никакой трудности.30§6Глава I .

Численные методы линейной алгебрыТеоремы о сходимости итерационных методовРассмотрим матричное уравнение вида(1) = ,где || ≠ 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) .Рассмотрим также двухслойный стационарный метод решения уравнения (1):+1 − + = ,(2)где ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица порядка ( × ).Чтобы говорить о сходимости итерационного метода, необходимо ввестилинейное пространство и определить в нем норму. Внимательный читательможет помнить из курса линейной алгебры, что в конечномерном пространстве все нормы эквивалентны.

То есть найдутся такие константы, при помощикоторых можно оценить одну норму через другую. Но при исследовании сходимости итерационных методов будем устремлять к нулю параметры этихметодов, и если они будут участвовать в записях констант перехода от однойнормы к другой, то смысл таких оценок, вообще говоря, может сойти на нет.Поэтому всегда при рассмотрении сходимости итерационных методов будемуказывать, в какой именно норме производится исследование.Пусть — линейное вещественное пространство размерности :dim = .Рассмотрим два произвольных вектора и из этого пространства: ∈ , = (1 , 2 , . . .

, ) , ∈ , = (1 , 2 , . . . , ) .Определим скалярное произведение двух векторов, заданных в ортонормированном базисе пространства :(, ) =∑︁ .=1Введем евклидову норму:√︀‖‖ = (, ) =(︃ ∑︁=1)︃ 122.§6. Теоремы о сходимости итерационных методов31Эту норму также часто называют среднеквадратичной нормой.Далее будем считать, что понятия линейный оператор и матрица эквивалентны. Рассмотрим самосопряженный положительный линейный оператор = * > 0.Линейный оператор называется положительным (неотрицательным), если (, ) > 0 ∀ ∈ , ̸= (соответственно (, ) >> 0 ∀ ∈ ). Положительность оператора обозначается как > 0.Определение.В дальнейшем понятия положительный оператор и положительно определенный линейный оператор считаются тождественными.Скалярным произведением в смысле оператора называется скалярное произведение, определяемое соотношениемОпределение.(, ) = (, ).Энергетической нормой, порождаемой линейным самосопряженным положительно определенным оператором , называется норма,задаваемая соотношением√︀√︀‖‖ = (, ) = (, ).Определение.Задача.2= ‖‖ .Пусть = * > 0.

Доказать, что ∃ > 0 : (, ) > (, ) =Рассмотрим свойства положительного самосопряженного линейного оператора.Если = * > 0, то определены(︁ 1 )︁*(︁(︁)︁*)︁111 *−1 = −1 > 0, 2 = 2 > 0, − 2 = − 2 > 0.Погрешностью итерационного метода на -й итерацииназывается вектор = − .(3)Определение.Определение.при → ∞.Итерационный метод сходится в норме ‖·‖, если ‖ ‖ → 0Выразим из формулы (3) и подставим в уравнение (2).