main (1160446), страница 5
Текст из файла (страница 5)
Следовательно, второе слагаемоетождества неотрицательно.Отсюда следует, что +1 6 , что и означает монотонностьпоследовательности { }. Так как > 0, то = ( , ) > 0.У невозрастающей последовательности { }, все члены которой неотрицательны, потеореме Вейерштрасса существует предел :lim = .→∞Для дальнейшего доказательства нам понадобится свойство положительно определенного линейного оператора, которое мы сформулируем в виде задачи.Пусть — вещественное линейное пространство, — положительный линейный не обязательно самосопряженный оператор в .
Доказать, чтоЗадача.∃ > 0 : (, ) > ‖‖2 , ∀ ∈ .(10)§6. Теоремы о сходимости итерационных методов25Воспользуемся свойством (10): существует константа > 0 такая, что)︁(︁(︁ )︁ − −1 , −1 > ‖ −1 ‖2 > 0.2Введем вектор : = −1 .(11)(12)Устремим к бесконечности в равенстве (9):(︁(︁)︁− )︁+ 2 lim − , = 0.→∞2Устремим теперь к бесконечности в неравенстве (11) и примем во внимание полученноеравенство:0 6 lim ‖ ‖2 6 0.→∞Получим, чтоlim ‖ ‖ = 0.→∞Выразим погрешность на -й итерации из равенства (12): = −1 .Оператор −1 существует вследствие предположения > 0. Очевидно, что ‖ ‖ 6 ‖−1 ‖‖ ‖,но ‖−1 ‖ не зависит от . Следовательно,lim ‖ ‖ = lim ‖ − ‖ = 0.→∞→∞Так как в ходе доказательства мы не использовали начальное приближение, то ономожет быть произвольным.Пусть = * > 0.
Тогда метод Якоби сходится в среднеквадратичнойнорме при любом начальном приближении, если выполнено неравенство:Следствие 1.2 > ,где = 1 + + 2 , = diag(11 , 22 , . . . , ).Доказательство.еслиВ методе Якоби = 1, а = . По теореме Самарского метод сходится, − > 0.2В нашем случае1 − > 0,2а это выполняется в силу условия 2 > . Следовательно, метод Якоби сходится в среднеквадратичной норме при любом начальном приближении.Пусть положительная симметричная матрица ( = * > 0) являетсяматрицей со строгим диагональным преобладанием:Следствие 2.
>∑︁| |, = 1, .=1,̸=Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении 0 .26Доказательство.Рассмотрим квадратичную форму с матрицей :(, ) =∑︁ 6,=1∑︁| | | | | |.(13),=1Для дальнейшей оценки квадратичной формы (13) воспользуемся неравенством 62 +22 :1 ∑︁1 ∑︁2(, ) 6| | | | +| | | |2 .22,=1,=1Преобразуем правую часть неравенства с учетом того, что матрица является симметричной (| | = | |):∑︁1 ∑︁1 ∑︁| | | |2 +| | | |2 =| | | |2 .22,=1,=1,=1Вынесем суммирование по индексу и воспользуемся свойством диагонального преобладания матрицы :⎛⎞∑︁∑︁∑︁2⎝⎠| | +| | <22 = (2, ),=1=1,̸==1где = diag(11 , 22 , . . . , ).
Таким образом, мы получили, что(, ) < (2, ).Из этого неравенства следует, что 2 > .Следовательно, выполняется условие следствия 1, и итерационный метод Якоби сходится при любом начальном приближении.Задача.Пусть матрица = * > 0. Доказать, что > 0, = 1, .Пусть = * > 0. Тогда метод Зейделя сходится в среднеквадратичнойнорме при любом начальном приближении 0 .Следствие 3.Доказательство. Из условия теоремы Самарского следует, что для сходимости методаЗейделя достаточно выполнения неравенства − > 0.2(14)Представим матрицу в виде = 1 + + 2 . В канонической записи метода Зейделя = 1, = 1 + .
Тогда достаточное условие (14) преобразуется к виду + 1 −1 + + 2> 0.2И, следовательно,(15) + 1 − 2 > 0.Запишем это неравенство в виде(, ) + (1 , ) − (2 , ) > 0, ̸= .§7. Оценка скорости сходимости итерационных методов27Так как = * , то 2* = 1 . Тогда(2 , ) = (, 2* ) = (, 1 ) = (1 , ).Следовательно, неравенство (15) принимает вид(16) ̸= .(, ) > 0,Если матрица симметричная и положительно определенная, то все ее диагональные элементы больше нуля (см.
задачу). Следовательно, матрица также является положительноопределенной, откуда следует неравенство (16).Следствие 4.Пусть = * > 0, 2 = max > 0. Если 0 < <16622 ,то метод простойитерации сходится в среднеквадратичной норме при любом начальном приближении 0 .Из условия теоремы Самарского следует, что для того, чтобы методпростой итерации сходился в среднеквадратичной норме при любом начальном приближении, достаточно выполнения неравенстваДоказательство. − > 0.2(17)В методе простой итерации = .
Следовательно, условие (17) преобразуется к виду − > 0.2(18)Неравенство (18) выполнено, если − 2 > 0, что справедливо, если1 − 2 > 0.2Из положительности параметра следует, что для сходимости метода простой итерациидостаточно выполнения условия20< < .2§7Оценка скорости сходимости итерационных методовРассмотрим матричное уравнение вида = ,(1)где || ̸= 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) и двухслойный стационарный метод решения этого уравнения:+1 − + = ,(2)где ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица размера ( × ).Введем погрешность = − .
Тогда из уравнения (2) получим задачу: +1 − + = 0, ∈ Z+ , 0 = 0 − .(3)28Предположим, что выполняется оценка‖ +1 ‖ 6 ‖ ‖,0 < < 1.(4)Тогда можно говорить о скорости сходимости итерационного метода (2) в зависимостиот параметра . Применив эту оценку раз получим:(5)‖ ‖ 6 ‖ 0 ‖.При 0 < < 1 видно, что ‖ ‖ −→ 0. Заметим, что чем ближе параметр к нулю, тем выше→∞скорость сходимости метода (2). Кроме того, оценка (5) позволяет посчитать необходимоечисло итераций для достижения заданной точности > 0:‖ − ‖ 6 ‖0 − ‖(6)Из неравенств (5) и (6) получим11> .Прологарифмируем обе части второго неравенства: 6 ,>ln 1.ln 1Таким образом, для достижения заданной точности достаточно провести число итераций,равное[︃]︃ln 10 () =, где [] — целая часть числа .ln 11называется скоростью сходимости итерационного метода.Пусть — вещественное линейное пространство размерности .
Введем в скалярноепроизведение и среднеквадратичную норму:Определение.Величина ln(, ) =∑︁ , ‖‖ =√︀(, ).=1Пусть = * > 0. Введем энергетическую норму, порождаемую оператором :√︀‖‖ = (, ).В пространстве существует ортонормированный базис { } из собственных векторовоператора : = , ̸= , = 1, ,{︃1 при = ,( , ) = =, = 1, .0 при ̸= ,Тогда любой вектор ∈ можно однозначно разложить по этому базису:=∑︁ , = (, ).=1Кроме того, в линейном пространстве с заданной в нем нормой и ортонормированнымбазисом выполняется равенство Парсеваля:‖‖2 =∑︁=12 , ∈ .(7)§7.
Оценка скорости сходимости итерационных методов29(об оценке скорости сходимости). Пусть = * > 0, = * > 0. Пустьтакже существует число , 0 < < 1, такое, что выполнено операторное неравенство:Теорема 11+1−66.Тогда для погрешности итерационного метода (2) решения системыоценка:‖ +1 ‖ 6 ‖ ‖ , ∈ Z+ .Доказательство.(8)(1) справедлива(9)(︁)︁11 *Так как = * > 0, то существует матрица − 2 = − 2 . Домно1жим обе части уравнения (3) на − 2 слева:121 +1 − + − 2 = 0.(10)1Введем вектор = 2 и перепишем задачу (10) через вектор :11 +1 − + − 2 − 2 = 0.Выразим +1 через :11 +1 = − − 2 − 2 = .Здесь матрица11 = − − 2 − 2(11)называется матрицей перехода от -й итерации к ( + 1)-й итерации вектора .В силу определения +1 и с учетом самосопряженности оператора верно равенство2121‖ +1 ‖ = ( +1 , +1 ) = ( 2 +1 , 2 +1 ) = ( +1 , +1 ) = ‖ +1 ‖ .Таким образом, чтобы доказать утверждение теоремы, достаточно получить оценку‖ +1 ‖ 6 ‖ ‖.Покажем, что — самосопряженный оператор:(︁)︁(︁)︁(︁)︁11 *1 *1 * * = − − 2 − 2 = − − 2 * − 2 = .Пусть – собственные значения матрицы .
В силу самосопряженности матрицы влинейном пространстве существует ортонормированный базис из собственных векторовоператора : = , ̸= , = 1, .(12)Покажем, что все собственные значения не превосходят по модулю : | | 6 , = 1, .1Подставим выражение из (11) в (12) и умножим слева обе части равенства на 2 :(︁ 1)︁11 2 − − 2 = 2 , = 1, .1Введем вектор = − 2 и перепишем это равенство в виде( − ) = , = 1, .30Отсюда следует равенство:1 − .Умножим левую и правую части этого равенства скалярно на вектор : =(, ) =1 − (, ).Воспользуемся неравенством (8) из условия теоремы:1−1 − 1+(, ) 6(, ) 6(, ).Из данных неравенств и неравенства ̸= следует, что (, ) > 0 и, следовательно,| | 6 , = 1, .Разложим вектор по ортонормированному базису { } из собственных векторов матрицы :∑︁()() = , = ( , ).=1Найдем разложение для +1 :+1= =∑︁() =∑︁() .=1=1Запишем равенство Парсеваля (7) для +1 :2‖ +1 ‖ = (︁∑︁() )︁2.=1В силу того, что | | 6 , = 1, , верно неравенство2‖ +1 ‖ 6 2 (︁∑︁)︁() 2= 2 ‖ ‖2 .=1Из этого неравенства следует оценка ‖ +1 ‖ 6 ‖ ‖, которая, как мы показали выше,эквивалентна утверждению теоремы.Замечание.Оценка (9) справедлива и в энергетической норме ‖·‖ .Пусть , — самосопряженные положительно определенные операторы,и пусть существуют 2 > 1 > 0, для которых выполняется условиеСледствие 1.1 6 6 2 .Тогда, если2,1 + 2то двухслойный итерационный метод решения системы уравнений сходится, и вернаоценка‖+1 − ‖ 6 ‖ − ‖ ,(13) = 0 =где =1−1+ ,=12 .§8.
Исследование скорости сходимости ПТИМ31Для того, чтобы воспользоваться теоремой 1, рассмотрим неравенство (8)1+из условия теоремы. Очевидно, что 1 = 1− и 2 = . Сложив эти равенства, получимДоказательство.1 + 2 =22., =1 + 2Вычитая из второго равенства первое, получим2 − 1 =2= (1 + 2 ),1−2 − 11=, = .1 + 21+2Таким образом, оценка (13) выполнена с найденной выше константой .=Сформулируем следующее следствие для метода простой итерации:+1 − + = , ∈ Z+ .Пусть — самосопряженный положительно определенный оператор, а 1и 2 — его минимальное и максимальное собственные значения:Следствие 2.1 = min , 2 = max .166166Кроме того, пусть =21 +2 .Тогда верна оценка‖+1 − ‖ 6 ‖ − ‖,где =1−1+ ,=12 .Доказательство следствия 2 очевидно.§8Исследование скорости сходимостиПТИМРассмотрим матричное уравнение вида(1) = ,где || ≠ 0, ( × ), = (1 , 2 , . . .
, ) , = (1 , 2 , . . . , ) .Представим матрицу в виде = 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, > 0, ∈ Z+ .Обозначим = ( + 1 )( + 2 ).32(о сходимости ПТИМ). Пусть — самосопряженный положительно определенный оператор и > 4 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
