Численные методы. Ионкин (2013) (1160444), страница 4
Текст из файла (страница 4)
⎠1 2 · · · 000· · · 00···0Перепишем матричное уравнение (1) в виде(1 + + 2 ) = .Оставим в левой части слагаемое с матрицей , остальные слагаемые перенесем в правуючасть уравнения: = − 1 − 2 .Предположим, что матрица обратима ( ̸= 0, = 1, ). Тогда получим: = −1 − −1 1 − −1 2 .(3)20Глава 1. Численные методы линейной алгебрыЗапишем итерационные методы Якоби (МЯ) и Зейделя (МЗ) исходя из уравнения (3):МЯ : +1 = −1 − −1 1 − −1 2 , ∈ Z+ ,МЗ : +1 = −1 − −1 1 +1 − −1 2 , ∈ Z+ .Рассмотрим эти два метода без обращения матрицы :МЯ : +1 + (1 + 2 ) = , ∈ Z+ ,МЗ : ( + 1 )+1 + 2 = , ∈ Z+ .Перепишем эти соотношения в видеМЯ : (+1 − ) + = ,МЗ : ( + 1 )(+1 ∈ Z+ ,(4)− ) + = , ∈ Z+ .(5)Из формул (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.522 · · ·⎜ 0.. ⎟ , 2 = ⎜ ........⎝ .... ⎠.· · · 0.50012...⎞⎟⎟⎟.⎠· · · 0.5Итерационная схема попеременно-треугольного метода имеет вид( + 1 )( + 2 )+1 − + = , > 0, ∈ Z+ ,(9)где > 0, > 0 — итерационные параметры, позволяющие, вообще говоря, ускорить процесс сходимости итерационного метода.
Рассматриваемый метод формально является неявным, однако можно показать, что (+1)-ая итерация выражается с помощью явных формулза три шага. Введем обозначения:+1 = ( + 2 )+1 − ,+1 − .Определение. Вектор = − называется невязкой на -ой итерации. +1 =В нашем случае невязка известна. На первом шаге решим уравнение( + 1 )+1 = .Заметим, что ( +1 ) — нижнетреугольная матрица.
Нахождение вектора решения системы с нижнетреугольной матрицей осуществляется по явным формулам, начиная с первойкомпоненты вектора +1 . На втором шаге аналогично решим уравнение с верхнетреугольной матрицей ( + 2 ):( + 2 ) +1 = +1 .На третьем шаге найдем ( + 1)-ую итерацию по формуле+1 = + +1 .Таким образом, несмотря на то, что метод Самарского является неявным, его реализацияне представляет никакой трудности.22§6Глава 1. Численные методы линейной алгебрыТеоремы о сходимости итерационных методовРассмотрим матричное уравнение вида = ,(1)где || ≠ 0, ( × ), = (1 , 2 , .
. . , ) , = (1 , 2 , . . . , ) .Рассмотрим также двухслойный стационарный метод решения уравнения (1):+1 − + = ,(2)где ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица размера ( × ).Чтобы говорить о сходимости итерационного метода, необходимо ввести линейное пространство и определить в нем норму. В курсе линейной алгебры доказывается, что в конечномерном пространстве все нормы эквивалентны. То есть найдутся такие константы, припомощи которых можно выразить одну норму через другую. Но при исследовании сходимости итерационных методов мы будем устремлять к нулю параметры этих методов, и еслиони будут участвовать в записях констант перехода от одной нормы к другой, то смыслтаких оценок, вообще говоря, может сойти на нет.
Поэтому всегда при рассмотрении сходимости итерационных методов мы будем указывать, в какой именно норме производитсяисследование.Пусть — линейное вещественное пространство размерности :dim = .Рассмотрим два произвольных вектора и из этого пространства: ∈ , = (1 , 2 , . . . , ) , ∈ , = (1 , 2 , . . . , ) .Определим скалярное произведение двух векторов, заданных в ортонормированном базисепространства :∑︁(, ) = .=1Введем евклидову норму:‖‖ =√︀(, ) =(︃ ∑︁)︃ 122.=1Эту норму также часто называют среднеквадратичной нормой.Далее будем считать, что понятия линейный оператор и матрица эквивалентны. Рассмотрим самосопряженный положительный линейный оператор = * > 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)-ой.Теорема 1. Итерационный метод (2) решения системы (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицыперехода по модулю меньше единицы.
(Без доказательства).Таким образом, сходимость итерационного метода (2) всецело зависит от свойств матрицы S, а именно, от ее спектра.Заметим, что данная теорема практически неприменима, так как задача нахожденияполного спектра матрицы аналитически решается крайне редко.Приступим к рассмотрению вопроса сходимости итерационного метода. В дальнейшембудем считать, что линейное пространство задано над полем R вещественных чисел.24Глава 1.
Численные методы линейной алгебрыТеорема 2 (теорема Самарского). Пусть — самосопряженный положительно определенный оператор, — положительное вещественное число и выполнено матричное неравенство − > 0.(6)2Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичнойнорме при любом начальном приближении:⎯⎸∑︁)︁2⎸ (︁ ‖ − ‖ = ⎷ − −→ 0,=1→∞∀0 .Доказательство. Введем числовую последовательность = ( , ) > 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}
