Численные методы. Ионкин (методичка) (2015) (1160451), страница 4
Текст из файла (страница 4)
Поэтому целесообразно ввести какую-то стандартную (каноническую) форму записиитерационных методов.Канонической формой записи двухслойного итерационного метода решения системы (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 положителен по условию. Следовательно, второе слагаемоетождества неотрицательно.Отсюда следует, что +1 6 , что и означает монотонностьпоследовательности { }.
Так как > 0, то = ( , ) > 0.У невозрастающей последовательности { }, все члены которой неотрицательны, потеореме Вейерштрасса существует предел :lim = .→∞Для дальнейшего доказательства нам понадобится свойство положительно определенного линейного оператора, которое мы сформулируем в виде задачи.Пусть — вещественное линейное пространство, — положительный линейный не обязательно самосопряженный оператор в . Доказать, чтоЗадача.∃ > 0 : (, ) > ‖‖2 , ∀ ∈ .(10)§6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
